講演名 | 2008-06-27 数理計画法に基づく大規模配置最適化枠組みの提案(レイアウト,信号処理,LSI,及び一般) 董 青, 楊 波, 李 静, 中武 繁寿, |
---|---|
PDFダウンロードページ | PDFダウンロードページへ |
抄録(和) | 近年の大規模配置においては、2次計画配置手法(QP)が広く利用されているが、その後に続くリーガライゼーションの結果、最適配線長が甚だ失われてしまう傾向にある。セル分配法は、QPとリーガライゼーションに対して、配線長最適化の観点から一貫性を持たせるができる。本稿では、大規模配置に対して、QP,セル分配、リーガライゼーションから構成される3ステップ最適化枠組みを提案する。提案するセル分配法は、セル重なり除去の制約を考慮する際にも、配線長の最適性を理論的に保証する。この提案の鍵は、QPの解空間の解析し、セルの移動時の総配線長の増分をセル移動距離に換算することにより、セル分配問題の最適化関数を線形化できることにある。結果として、提案するセル分配法は、線形計画法により配線長に関する準最適解を得ることができる。 |
抄録(英) | The quadratic placement (QP) followed by the legalization is widely used for modem large scale circuits, but the resultant wire-length tends to be far from the optimum after the legalization. The cell spreading serves the consistency between the QP and the legalization with respect to minimizing the wire-length. This paper presents a three-step optimization framework, which is composed of QP, the cell spreading and the legalization, for large scale placement. Our cell spreading theoretically guarantees the optimality for minimizing the wire-length even when considering constraints for removing overlaps among cells. The key is in analyzing a solution space of QP and in the linearization of the cell spreading problem, where an increase in the total wire-length is represented in terms of the sum of the displacement of the spreading cells. As a result, our cell spreading can attain the semi-optimal placement with respect to the wirelength by linear programming. |
キーワード(和) | 大規模配置 / 数理計画法 / 2次計画法 / 線形計画法 |
キーワード(英) | large-scale placement / mathematical programming / quadratic programming / linear programming |
資料番号 | CAS2008-23,VLD2008-36,SIP2008-57 |
発行日 |
研究会情報 | |
研究会 | VLD |
---|---|
開催期間 | 2008/6/20(から1日開催) |
開催地(和) | |
開催地(英) | |
テーマ(和) | |
テーマ(英) | |
委員長氏名(和) | |
委員長氏名(英) | |
副委員長氏名(和) | |
副委員長氏名(英) | |
幹事氏名(和) | |
幹事氏名(英) | |
幹事補佐氏名(和) | |
幹事補佐氏名(英) |
講演論文情報詳細 | |
申込み研究会 | VLSI Design Technologies (VLD) |
---|---|
本文の言語 | ENG |
タイトル(和) | 数理計画法に基づく大規模配置最適化枠組みの提案(レイアウト,信号処理,LSI,及び一般) |
サブタイトル(和) | |
タイトル(英) | A Large-scale Placement Framework Based on Mathematical Programming |
サブタイトル(和) | |
キーワード(1)(和/英) | 大規模配置 / large-scale placement |
キーワード(2)(和/英) | 数理計画法 / mathematical programming |
キーワード(3)(和/英) | 2次計画法 / quadratic programming |
キーワード(4)(和/英) | 線形計画法 / linear programming |
第 1 著者 氏名(和/英) | 董 青 / Qing DONG |
第 1 著者 所属(和/英) | 北九州市立大学大学院国際環境工学研究科 Graduate School of Environmental Engineering Graduate School of Environmental Engineering, University of Kitakyushu |
第 2 著者 氏名(和/英) | 楊 波 / Bo YANG |
第 2 著者 所属(和/英) | 北九州市立大学大学院国際環境工学研究科 Graduate School of Environmental Engineering Graduate School of Environmental Engineering, University of Kitakyushu |
第 3 著者 氏名(和/英) | 李 静 / Jing LI |
第 3 著者 所属(和/英) | 北九州市立大学大学院国際環境工学研究科 Graduate School of Environmental Engineering Graduate School of Environmental Engineering, University of Kitakyushu |
第 4 著者 氏名(和/英) | 中武 繁寿 / Shigetoshi NAKATAKE |
第 4 著者 所属(和/英) | 北九州市立大学大学院国際環境工学研究科 Graduate School of Environmental Engineering Graduate School of Environmental Engineering, University of Kitakyushu |
発表年月日 | 2008-06-27 |
資料番号 | CAS2008-23,VLD2008-36,SIP2008-57 |
巻番号(vol) | vol.108 |
号番号(no) | 107 |
ページ範囲 | pp.- |
ページ数 | 5 |
発行日 |