多ネット等長チャネル配線におけるチャネル高さ最小化手法

• Item type: SIG Technical Reports(1)
• 公開日: 2004-12-02
• タイトル: 多ネット等長チャネル配線におけるチャネル高さ最小化手法
• タイトル / 言語: en
• タイトル: Stochastic Equi - Length Channel Routing with Channel Height Minimization
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 北九州立大学国際環境工学部
• 著者所属: 北九州立大学国際環境工学部
• 著者所属: 北九州立大学国際環境工学部
• 著者所属(英): en
• 著者所属(英): Faculty of Environmental Engineering, The University of Kitakyushu
• 著者所属(英): en
• 著者所属(英): Faculty of Environmental Engineering, The University of Kitakyushu
• 著者所属(英): en
• 著者所属(英): Faculty of Environmental Engineering, The University of Kitakyushu
• 著者名: 久保, ゆき子; 宮下, 弘; 梶谷, 洋司
• 著者名(英): Yukiko, Kubo; Hiroshi, Miyashita; Yoji, Kajitani
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 高速な同期で信号を伝送するVLSI配線システムでは複数の出力信号を同じタイミングで指定した端子へ伝送する等遅延配線が要求される．遅延は複雑な環境で決まるが，配線長が大略等しい(等長配線)条件が充たされなければ等遅延配線実現は容易ではない．このような要求に対しいくつかの提案がなされているが，筆者らはチャネル配線問題を解く組織的なアルゴリズムを提案している．更にその方式における経路選択の多様性を利用して総長最小化問題を解いている．しかしながらそこではチャネルの高さについての考慮がなく，ソースからシンクまでの長さが延びてしまう欠点を持つ．本稿はこれに続く研究であり，総長最小性を保ったままチャネルの高さを小さくすることを目的とする．しかし厳密解は従来のチャネル高さ最小化問題を包含する難題なのでここでは経路修正によりチャネル高さの減少をはかる探索的アルゴリズムを提案する．はじめに上述のチャネル等長配線かつ総長最小化を実現する方式を紹介する．次にその手法により得られる配線結果を初期解とし，配線経路を繰り返し修正することによりチャネル高さを減少させる手続きを提案する．経路の修正はシミュレーティッドアニーリングを用いて制御する．このアルゴリズムをプログラム実装し，アルゴリズムの性能を検定するためランダムデータを生成し適用したところ，初期解の高さを概ね30％削減するという結果を得た。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In VLSI system, a set of signals is often required to be propagated within a tolerable skew of delays. Though the delay of a signal on a wire is determined by a complex electrical environment, it is hard to attain this requirement unless all the nets are routed within a certain skew of length from the source to sinks. There exists some equi-length algorithms to solve such a problem and we also propose a constructive algorithm for channel routing. But the length from a source to sinks of the routes obtained by the algorithm becomes long because it does not consider the height of the channel. In this paper, the algorithm that solves the channel height problem keeping the total length minimum is presented. Because our problem includes the difficulty of the original channel routing problem, it is difficult to obtain the best solution exactly. Therefore we propose a stochastic algorithm to modify parts of the routes iteratively. First, a basic algorithm of equidistance channel routing is introduced. Then the routes obtained by it is given as an initial solution and apply modifications iteratively. This modification process is controlled by Simulated Annealing. The proposed algorithm is implemented and applied to random data. The experimental result shows that the algorithm reduces the height of the channel about 30%.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11451459
• 書誌情報: 情報処理学会研究報告システムLSI設計技術（SLDM）; 巻 2004, 号 122(2004-SLDM-117), p. 113-118, 発行日 2004-12-02
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会