| 講演名 | 1997/3/7 配線幅最適化とバッファ挿入を伴うスタイナ木生成アルゴリズム 岡本 匠, Cong Jason, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 本論文では、配線幅最適化とバッファ挿入を伴う効率的なスタイナ木生成アルゴリズムを提案する。1つのソースと複数のシンクを持つネットに対して、ソースに座標、各シンクに固有の座標と要求到着時刻が与えられた場合に、提案するアルゴリズムは、ソースの要求到着時刻(遅延余裕度)が最大となるように、スタイナ木及びその配線幅とバッファ挿入位置を決定する。これらの処理は従来独立に最適化されていたが、本アルゴリズムでは、A-treeアルゴリズムとダイナミックプログラミングに基づく配線幅最適化/バッファ挿入アルゴリズムを組み合わせることにより、遅延と総容量(配線容量とバッファの入力端子容量)のトレードオフを考慮しながら、同時に最適化することができる。実験結果により提案アルゴリズム有効性を示す。 |
| 抄録(英) | This paper presents an efficient algorithm for buffered Steiner tree Construction with wire sizing. Given a source and n sinks of a signal net, with given positions and a required arrival time associated with each sink, the algorithm finds a Steiner tree with buffer insertion and wire sizing so that the required arrival time (or timing slack) at the source is maximized. The unique contribution of our algorithm is that it performs Steiner tree construction, buffer insertion, and wire sizing simultaneously with consideration of both critical delay and total capacitance minimization by combining the performance-driven A-tree construction and dynamic programming based buffer insertion and wire sizing, while tree construction and the other delay minimization techniques were carried out independently in the past. Experimental results show the effectiveness of our approach. |
| キーワード(和) | スタイナ木 / バッファ挿入 / 配線幅最適化 / タイミング最適化 |
| キーワード(英) | Steiner tree / buffer insertion / wire sizing / timing optimization |
| 資料番号 | VLD96-107,ICD96-217 |
| 発行日 |
| 研究会情報 | |
| 研究会 | VLD |
|---|---|
| 開催期間 | 1997/3/7(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | VLSI Design Technologies (VLD) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 配線幅最適化とバッファ挿入を伴うスタイナ木生成アルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | Buffered Steiner Tree Construction with Wire Sizing for Interconnect Layout Optimization |
| サブタイトル（和） | |
| キーワード(1)（和/英） | スタイナ木 / Steiner tree |
| キーワード(2)（和/英） | バッファ挿入 / buffer insertion |
| キーワード(3)（和/英） | 配線幅最適化 / wire sizing |
| キーワード(4)（和/英） | タイミング最適化 / timing optimization |
| 第 1 著者 氏名（和/英） | 岡本 匠 / Takumi Okamoto |
| 第 1 著者 所属（和/英） | NEC C&C研究所 C&C Research Laboratories, NEC Corp. |
| 第 2 著者 氏名（和/英） | Cong Jason / Jason Cong |
| 第 2 著者 所属（和/英） | Dept. of Computer Science, Univ. of California Dept. of Computer Science, Univ. of California |
| 発表年月日 | 1997/3/7 |
| 資料番号 | VLD96-107,ICD96-217 |
| 巻番号（vol） | vol.96 |
| 号番号（no） | 556 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |