クロストークノイズとシールド効果を考慮したクロスポイント割り当ての高速解法

• Item type: SIG Technical Reports(1)
• 公開日: 2003-11-27
• タイトル: クロストークノイズとシールド効果を考慮したクロスポイント割り当ての高速解法
• タイトル / 言語: en
• タイトル: A Fast Algorithm for Crosspoint Assignment under Crosstalk Constraints with Shielding Effect
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: エスアイアイ・イーディーエー・テクノロジ株式会社システム開発部／北九州市立大学国際環境工学部
• 著者所属: エスアイアイ・イーディーエー・テクノロジ株式会社システム開発部
• 著者所属: エスアイアイ・イーディーエー・テクノロジ株式会社システム開発部
• 著者所属: 北九州市立大学国際環境工学部
• 著者所属: 北九州市立大学国際環境工学部
• 著者所属(英): en
• 著者所属(英): Systems Development Department, SII EDA Technologies Inc./Faculty of Environmental Engineering, The University of Kitakyushu
• 著者所属(英): en
• 著者所属(英): Systems Development Department, SII EDA Technologies Inc.
• 著者所属(英): en
• 著者所属(英): Systems Development Department, SII EDA Technologies Inc.
• 著者所属(英): en
• 著者所属(英): Faculty of Environmental Engineering, The University of Kitakyushu
• 著者所属(英): en
• 著者所属(英): Faculty of Environmental Engineering, The University of Kitakyushu
• 著者名: 木田, 圭治; 朱小科; 庄昌文; 高島, 康裕; 中武, 繁寿
• 著者名(英): Keiji, Kida; Xiaoke, Zhu; Changwen, Zhuang; Yashuhiro, Takashima; Shigetoshi, Nakatake
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本稿では，ディープサブミクロンにおけるクロストークノイズとシールド効果を考慮したクロスポイント割り当て問題の高速解法を提案する．まず，概略配線セル境界を通過するネットの位置決め(クロスポイント割り当て問題)に対して，距離制約とシールド効果を考慮する{d 1}-ピッチ制約を導入する．この制約下でのクロスポイント割り当て問題は，許容解が存在する場合には，整数線形計画法に基づく手法により，厳密解を得ることができる．しかし，整数線形計画法による解法は多くの処理時間を必要とするため大規模な配線システムへの適用は困難である．本稿ではこの問題を解くための高速な発見的手法を提案する．実験において整数線形計画法の基づく手法と発見的手法を実データに適用し，発見的手法が十分高速に準最適解を導くことを確認した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper, we present a fast algorithm for Crosspoint Assignment, that takes into consideration crosstalk noise and shielding effects in deep sub-micron design. In our formulation, for crosspoint assignment problem(deciding a position where a global routing tree crosses a global routing cell boundary), we introduce {d,1}-pitch constraint that takes into consideration crosstalk with shielding effects. Under the constraints, an integer linear programming based algorithm can output an exact optimum solution if there exists a feasible solution. But, the integer linear programming based algorithm can not be applied to the typical routing system for the large scale design because it takes much calculating time. Therefore, we provide a fast heuristic algorithm for this problem. In experiments, we tested integer linear programming based algorithm and heuristic algorithm for industrial examples, and demonstrated that our heuristics ran quickly and attained near optimum solutions.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11451459
• 書誌情報: 情報処理学会研究報告システムLSI設計技術（SLDM）; 巻 2003, 号 120(2003-SLDM-112), p. 205-210, 発行日 2003-11-27
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会