文献

J-GLOBAL ID：202002222517903212   整理番号：20A1864640

Prim-Dijkstraは優れたタイミング駆動ルーティングツリーを達成する【JST・京大機械翻訳】

Prim-Dijkstra Revisited Achieving Superior Timing-driven Routing Trees

著者 (7件)： Alpert Charles J. (Cadence Design Systems Inc., Austin, TX, USA) ,  Chow Wing-Kai (Cadence Design Systems Inc., Austin, TX, USA) ,  Han Kwangsoo (Cadence Design Systems Inc. & University of California, San Diego, Austin, TX, USA) ,  Kahng Andrew B. (University of California, San Diego, San Diego, CA, USA) ,  Li Zhuo (Cadence Design Systems Inc., Austin, TX, USA) ,  Liu Derong (Cadence Design Systems Inc., Austin, TX, USA) ,  Venkatesh Sriram (University of California, San Diego, San Diego, CA, USA)
資料名： ACM Proceedings  (ACM Proceedings)
号： ISPD ’18  ページ： 10-17  発行年： 2018年 
JST資料番号： D0698C  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： Prim-Dijkstra(PD)構築[1]は,最短経路と最小ワイヤ長ルーティングツリーを効率的にトレードオフする方法として20年以上前に初めて提示された。このアプローチは,時間試験に通し,主要な半導体設計方法論と電子設計自動化ツールに統合されている。PDは,古典的プライムとDijkstraスパニング木アルゴリズムを混合することにより,ワイヤ長(WL)とソースシンク経路長(PL)の矛盾する目的を最適化する。しかし,本研究が示すように,PDはWLとPLの両方に対して有意な準最適性を示すことがある。この品質劣化は,(i)ワイヤ遅延が全段遅延のはるかに大きな要素を形成するため,特に,タイミング駆動ルーティングが重要であり,(ii)現代の設計は,低容量配線を重要にする,厳しい電力制約(例えば,モバイル,IoT)である。その結果,市場主導製品[2]を構築するために,ルーティングのための良好なタイミングと電力トレードオフを達成する必要がある。本研究では,最悪の迂回ではなく,木のあらゆるシンクに対する迂回を最適化するために,目的関数における全迂回コストを組み込んだ新しい問題定式化を導入した。次に,WLとPLの両方を同時に減らすためにツリーを修復することによって,元のPD構成で直接改善する新しいPD-II構成を提案した。PD-IIアプローチは,両方の目的に対して改善を達成し,実質的にゼロの追加実行時間コストに対して,PD上の明確なウィンを作れる。PD-IIはスパニング木アルゴリズム(グローバルルーティングの播種に有用である)である。しかしながら,Steiner木はタイミング推定に必要であるので,本研究はまた,PD-IIツリーをバランスSteiner木に変換するためのDASと呼ばれる後処理アルゴリズムを含む。実験結果は,この構築が最近の最先端の学術ツール,SALT[36]を高ファンアウトネットに対して凌駕し,DAC 2012コンテストベンチマーク設計[37]から,サイズ≧32端末の20Kネットに対して平均で同様のWLで36.46%のPL改善を達成することを示した。Please refer to this article’s citation page on the publisher website for specific rights information. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  最適化 ,  半導体 ,  電力 ,  配線 ,  *経路選定 ,  端末装置 ,  目的関数 ,  金属線 ,  スパンニング木 ,  定式化 ,  携帯電話 ,  Steiner木
準シソーラス用語： 配線長 ,  実行時間 , 【Automatic Indexing@JST】

著者キーワード (7件)： 迂回コスト ,  改善されたトレードオフ ,  ルーティング ,  浅い光 ,  スパンニング木 ,  Steiner木 ,  樹木

分類 (2件)： 集積回路一般  (NC03161C) ,  計算機網  (JC03000K)

タイトルに関連する用語 (1件)： ルーティング