著者

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

出版者

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

雑誌

情報処理学会論文誌 (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.

著者

リ シューティン ヤン タン 高島 康裕 村田 洋

出版者

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

雑誌

情報処理学会研究報告システムLSI設計技術(SLDM) (ISSN:09196072)

巻号頁・発行日

vol.2008, no.38, pp.43-48, 2008-05-01

---

IP 再利用等においては,利用する IP の特性を考慮して設計を行なう必要がある.特にフロアプランにおいては,近傍の配線の状況の影響を受けやすい IP は障害物として考慮する必要がある.しかし,従来の HPWL 方式では,障害物の考慮を評価中に組み込むのは不可能であった.本稿では,ヤンらが[5]において提案した手法を基に,障害物を考慮した最小配線長評価アルゴリズムの改良を検討し,より実用的な近似手法を提案する.実験により,提案手法が HPWL 評価手法と比較して,数倍程度の時間で実現できることを確認した.IP-reuse can enhance the design productivity only if the design methodology treats the IPs in a proper way. Especially in the floor-planning phase, sensitive IPs should be treated as routing obstacles, which is impossible when the conventional HPWL-based method is used for routing estimation. This paper proposes an obstacle-aware minimum wiring length (MWL) estimation algorithm, based on the theoretical result in [5], through algorithmic improvements and practical approximation. The experimental results suggests that MWL-based estimation is now possible with only few times larger computational cost comparing to the HPWL-based estimation.

著者

リ シューティン ヤン タン 高島 康裕 村田 洋

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. VLD, VLSI設計技術 (ISSN:09135685)

巻号頁・発行日

vol.108, no.23, pp.7-12, 2008-05-02

---

IP再利用等においては,利用するIPの特性を考慮して設計を行う必要がある.特にフロアプランにおいては,近傍の配線の状況の影響を受けやすいIPは障害物として考慮する必要がある.しかし,従来のHPWL方式では,障害物の考慮を評価中に組み込むのは不可能であった.本稿では,ヤンらが[5]において提案した手法を基に,障害物を考慮した最小配線長評価アルゴリズムの改良を検討し,より実用的な近似手法を提案する.実験により,提案手法がHPWL評価手法と比較して,数倍程度の時間で実現できることを確認した.