| 講演名 | 2004/11/25 多ネット等長チャネル配線におけるチャネル高さ最小化手法(レイアウト)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会-) 久保 ゆき子, 宮下 弘, 梶谷 洋司, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 高速な同期で信号を伝送するVLSI配線システムでは複数の出力信号を同じタイミングで指定した端子へ伝送する等遅延配線が要求される.遅延は複雑な環境で決まるが,配線長が大略等しい(等長配線)条件が充たされなければ等遅延配線実現は容易ではない.このような要求に対しいくつかの提案がなされているが,筆者らはチャネル配線問題を解く組織的なアルゴリズムを提案している.更にその方式における経路選択の多様性を利用して総長最小化問題を解いている.しかしながらそこではチャネルの高さについての考慮がなく,ソースからシンクまでの長さが延びてしまう欠点をもつ.本稿はこ叩こ続く研究であり,総長最小性を保ったままチャネルの高さを小さくすることを目的とする.しかし厳密解は従来のチャネル高さ最小化問題を包含する難問なのでここでは経路修正によりチャネル高さの減少をはかる探索的アルゴリズムを提案する.はじめに上述のチャネル等長配線かう総長最小化を実現する方式を紹介する.次にその手法により得られる配線結果を初期解とし,配線経路を繰り返し修正することによりチャネル高さを減少させる手続きを提案する.経路の修正はシミュレーティッドアニーリングを用いて制御する.このアルゴリズムをプログラム実装し,アルゴリズムの性能を検定するためランダムデータを生成し適用したところ,初期解の高さを概ね30%削減するという結果を得た。 |
| 抄録(英) | In VLSI system, a set of signals is often required to be propagated within a torelable 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%. |
| キーワード(和) | チャネル等長配線 / 水平線分 / 垂直制約 / トラック割り当て / 探索的手法 / SA |
| キーワード(英) | Channel equi-length routing / Horizontal segments / Vertical constraints / Simulated Annealing / Track Assignment |
| 資料番号 | VLD2004-68,ICD2004-154,DC2004-54 |
| 発行日 |
| 研究会情報 | |
| 研究会 | VLD |
|---|---|
| 開催期間 | 2004/11/25(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | VLSI Design Technologies (VLD) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 多ネット等長チャネル配線におけるチャネル高さ最小化手法(レイアウト)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会-) |
| サブタイトル（和） | |
| タイトル（英） | Stochastic Equi-Length Channel Routing with Channel Height Minimization |
| サブタイトル（和） | |
| キーワード(1)（和/英） | チャネル等長配線 / Channel equi-length routing |
| キーワード(2)（和/英） | 水平線分 / Horizontal segments |
| キーワード(3)（和/英） | 垂直制約 / Vertical constraints |
| キーワード(4)（和/英） | トラック割り当て / Simulated Annealing |
| キーワード(5)（和/英） | 探索的手法 / Track Assignment |
| キーワード(6)（和/英） | SA |
| 第 1 著者 氏名（和/英） | 久保 ゆき子 / Yukiko KUBO |
| 第 1 著者 所属（和/英） | 北九州市立大学国際環境工学部 Faculty of Environmental Engineering, The University of Kitakyushu |
| 第 2 著者 氏名（和/英） | 宮下 弘 / Hiroshi MIYASHITA |
| 第 2 著者 所属（和/英） | 北九州市立大学国際環境工学部 Faculty of Environmental Engineering, The University of Kitakyushu |
| 第 3 著者 氏名（和/英） | 梶谷 洋司 / Yoji KAJITANI |
| 第 3 著者 所属（和/英） | 北九州市立大学国際環境工学部 Faculty of Environmental Engineering, The University of Kitakyushu |
| 発表年月日 | 2004/11/25 |
| 資料番号 | VLD2004-68,ICD2004-154,DC2004-54 |
| 巻番号（vol） | vol.104 |
| 号番号（no） | 478 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |