文献

J-GLOBAL ID：200902286866842399   整理番号：09A1258066

双方向接続型の長さ上限を使用した障害物のある格子をルーティングするための高速長経路アルゴリズム

A Fast Longer Path Algorithm for Routing Grid with Obstacles Using Biconnectivity Based Length Upper Bound

著者 (3件)： KOHIRA Yukihide (Univ. Aizu, Aizu-Wakamatsu-shi, JPN) ,  SUEHIRO Suguru (Tokyo Inst. of Technol., Tokyo, JPN) ,  TAKAHASHI Atsushi (Osaka Univ., Suita-shi, JPN)
資料名： IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences (Institute of Electronics, Information and Communication Engineers)  (IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences (Institute of Electronics, Information and Communication Engineers))
巻： E92-A  号： 12  ページ： 2971-2978  発行年： 2009年12月01日 
JST資料番号： F0699C  ISSN： 0916-8508  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 最近のVLSIシステムでは,信号伝搬遅延は非常に高精度で仕様を実現する必要がある。仕様を充足するため,ネットのルーティングは,ルーティング遅延を増加させるためにしばしば迂回する必要がある。ルーティング方法は,ネットの仕様を同時に実現するため,障害物のあるルーティング領域をできるだけ多く使用しなければならない。本論文では,ルーティング格子におけるネットの経路を,長さができるだけ増加するように生成する,高速長経路アルゴリズムを提案する。提案したアルゴリズムでは,ルーティング領域の構造を考慮に入れた長さに対する上限を使用する。実験は,このアルゴリズムが障害物のあるルーティング領域を効率良く使用することを示す。(翻訳著者抄録)

シソーラス用語： *プリント基板 ,  *経路選定 ,  超LSI ,  遅れ ,  精度 ,  仕様 ,  ゲート回路 ,  遅延特性 ,  可制御性 ,  障害物 ,  性質 ,  上限 ,  高速アルゴリズム ,  経路 ,  長さ ,  部分グラフ ,  実験 ,  CAD【計算機】 ,  *通信操作
準シソーラス用語： 伝搬遅延 ,  高精度 ,  設計仕様 ,  配線遅延 ,  ゲート遅延 ,  双方向性 ,  配線長 ,  二部グラフ ,  評価実験

分類 (1件)： CAD,CAM  (JE10000A)

引用文献 (9件)：

• KOHIRA, Y. A maximum wire length router in routing area with obstacles using upper bound estimation considering connectivity. 21st Workshop on Circuits and Systems in Karuizawa, 2008. 2008, 569-574
• KOHIRA, Y. A fast longer path algorithm for routing grid with obstacles using biconnectivity based length upper bound. ASPDAC, 2009. 2009, 600-605
• OZDAL, M. M. Algorithmic study of single-layer bus routing for high-speed boards. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 2006, 25, 3, 490-503
• OZDAL, M. M. A length-matching routing algorithm for high-performance printed circuit boards. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 2006, 25, 12, 2784-2794
• ITAI, A. Hamiltonian paths in grid graphs. SIAM, Comput. 1982, 11, 4, 676-686

タイトルに関連する用語 (7件)： 双方向 ,  上限 ,  障害物 ,  格子 ,  ルーティング ,  経路 ,  アルゴリズム