講演名 2009-03-11
最小総変位配置実現問題における高速最適化手法(レイアウト,システムオンシリコンを支える設計技術)
河野 祐貴, 高島 康裕, 高橋 篤司,
PDFダウンロードページ PDFダウンロードページへ
抄録(和) 本稿では,最小総変位配置実現問題に対し,高速に最適解を出力する手法APRを提案する.近年のLSI製造技術の進歩により,1チップ上に搭載可能な素子数が増大している.これに対し,設計期間の短縮のためには,重なりを無視した概略配置から詳細配置の構成や一度配置を作成した回路の小変更に対応するEngineer Change Orderなどの既存配置に似ている配置を得る手法が重要となっている.これは最小総変位配置実現問題として定式化できる.この問題に対し,制約グラフが有向非循環グラフに制限される特性を利用して,既存手法を高速化するAPR法を提案する.そして,提案手法が最適解を出力することを証明し,実験によりその有効性を確認する.
抄録(英) In this paper, we propose a fast optimization method, called Augmenting path based Placement Realization (APR), to solve the minimum perturbation placement realization problem. In recent years, a progress of the LSI process achieves the increase of the elements on one chip. To shorten the turn-around time, it becomes important to obtain the similar placement to the model placement, for example, for the detailed placement from the gloval placement in which the overaps between elements are not considered or for the Engineer Change Order in which the circuit is changed after the placement. This is captured by the minimum perturbation placement realization problem. To solve this problem, we propose APR, which is a speed up method of the previous work by its constraint graph being directed acyclic. We prove that our method outputs the optimization placement and conduct its efficiency empirically.
キーワード(和) 最小総変位配置実現問題 / 最適配置 / APR
キーワード(英) Minimum Perturbation Placement Realization Problem / Placement / APR
資料番号 VLD2008-137
発行日

研究会情報
研究会 VLD
開催期間 2009/3/4(から1日開催)
開催地(和)
開催地(英)
テーマ(和)
テーマ(英)
委員長氏名(和)
委員長氏名(英)
副委員長氏名(和)
副委員長氏名(英)
幹事氏名(和)
幹事氏名(英)
幹事補佐氏名(和)
幹事補佐氏名(英)

講演論文情報詳細
申込み研究会 VLSI Design Technologies (VLD)
本文の言語 JPN
タイトル(和) 最小総変位配置実現問題における高速最適化手法(レイアウト,システムオンシリコンを支える設計技術)
サブタイトル(和)
タイトル(英) Fast Optimization on Minimum Perturbation Placement Realization
サブタイトル(和)
キーワード(1)(和/英) 最小総変位配置実現問題 / Minimum Perturbation Placement Realization Problem
キーワード(2)(和/英) 最適配置 / Placement
キーワード(3)(和/英) APR / APR
第 1 著者 氏名(和/英) 河野 祐貴 / Yuki KOUNO
第 1 著者 所属(和/英) 北九州市立大学国際環境工学部情報メディア工学科
Faculty of Environmental Engineering, The University of Kitakyushu
第 2 著者 氏名(和/英) 高島 康裕 / Yasuhiro TAKASHIMA
第 2 著者 所属(和/英) 北九州市立大学国際環境工学部情報メディア工学科
Faculty of Environmental Engineering, The University of Kitakyushu
第 3 著者 氏名(和/英) 高橋 篤司 / Atsushi TAKAHASHI
第 3 著者 所属(和/英) 東京工業大学大学院理工学研究科集積システム専攻
Department of Communications and Integrated Systems Graduate School of Science and Engineering, Tokyo Institute of Technology
発表年月日 2009-03-11
資料番号 VLD2008-137
巻番号(vol) vol.108
号番号(no) 478
ページ範囲 pp.-
ページ数 6
発行日