著者

久保 ゆき子 高島 康裕 中武 繁寿 梶谷 洋司

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.41, no.4, pp.881-888, 2000-04-15

参考文献数

10

被引用文献数

8

---

平面配線領域上に指定された複数の点を相互に結ぶスタイナ木を別のスタイナ木へ変換するアルゴリズムFlipを提案する.これは,現スタイナ木の1枝をそれを含む面上のパスで迂回させる操作である.Flipは高速で働き,また任意のスタイナ木から任意のスタイナ木へ多項式回の適用で到達できることが証明できるので,VLSI配線における複雑な評価に対する有効なアルゴリズムになる.Flipは,2層HV配線領域のスタイナ木にも適用できるよう拡張される.例として採用した総配線長,クロストーク,スキュー,VIA数などの複合評価関数に対応する実験では,従来の構成的手法では達成できない特徴を有する結果を得ることができた.また,類似の手法であるrip-up and reroute手法との差異を付録で論ずる.Given a Steiner tree thatconnects designated terminals on a plane routing area, the Flip isdefind as a procedure that makes a current Steiner tree change itsconfiguration.It is to replace one of the edges of the Steiner treewith a detour on an adjacent face.Since the procedure runs quickly, and the reachability is proved, theidea can be a useful routing algorithm if it is implemeted bysimulated annealng.The idea is enhanced to the 2-layer HV routing.The performance of the algorithm was experimented for multipleobjectives.Some unique and satisfiable results were observed.The difference from the rip-up and reroute strategy is discussed in Appendix.