| 講演名 | 2009-05-21 パス長制約付き点集合に対する矩形スタイナー木構成手法(物理設計,システム設計及び一般) 井上 雅文, 富岡 洋一, 小平 行秀, 高橋 篤司, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 配線の微細化に伴い,信号伝搬遅延に占める配線遅延の割合が無視できない程に大きくなってきており,配線遅延の低減を目的とした様々なアルゴリズムが提案されている.また,素子や配線の微細化や回路の高速化に伴い,始点から各終点端子までの信号伝搬遅延をそれぞれ個別に取り扱う必要が生じてきたため,配線木の各終点端子にそれぞれ異なる信号到着時間が仕様として与えられることも多くなった.そこで本稿では,配線木において信号源から終点端子への信号伝搬遅延が信号源から各終点端子へのパス長に比例すると仮定し,信号源から各終点端子へのパス長がその点に付加された正数以下となる枝総長が小さい矩形スタイナー木を構成する手法を提案する. |
| 抄録(英) | As the wire width decreases, the ratio of routing delay among signal propagation delay increases and the routing delay can not be ignored. In order to reduce the routing delay, a lot of algorithms have been proposed so far. Due to the miniaturization of elements and wires and the speedup of circuits, the signal propagation delays from the source to sinks in a routing tree are different to each other, and each sink is assigned its own allowable arrival time as the specification. We assume that the maximum path length from the source is assigned to each sink under the assumption that the routing delay is proportional to the wire length. In this paper, we propose a method that constructs a rectilinear Steiner tree whose total wire length is small and in which the path length from the source to each sink is less than the specification assigned to the sink. |
| キーワード(和) | 矩形スタイナー木 / 配線遅延 / パス長 / 配線総長 |
| キーワード(英) | rectilinear Steiner tree / routing delay / path length / total wire length |
| 資料番号 | VLD2009-4 |
| 発行日 |
| 研究会情報 | |
| 研究会 | VLD |
|---|---|
| 開催期間 | 2009/5/13(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | VLSI Design Technologies (VLD) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | パス長制約付き点集合に対する矩形スタイナー木構成手法(物理設計,システム設計及び一般) |
| サブタイトル（和） | |
| タイトル（英） | A RST Construction Method for Vertices With Maximum Path Length |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 矩形スタイナー木 / rectilinear Steiner tree |
| キーワード(2)（和/英） | 配線遅延 / routing delay |
| キーワード(3)（和/英） | パス長 / path length |
| キーワード(4)（和/英） | 配線総長 / total wire length |
| 第 1 著者 氏名（和/英） | 井上 雅文 / Masafumi INOUE |
| 第 1 著者 所属（和/英） | 東京工業大学大学院理工学研究科集積システム専攻 Department of Communications and Integrated Systems, Tokyo Institute of Technology |
| 第 2 著者 氏名（和/英） | 富岡 洋一 / Yoichi TOMIOKA |
| 第 2 著者 所属（和/英） | 東京工業大学大学院理工学研究科集積システム専攻 Department of Communications and Integrated Systems, Tokyo Institute of Technology |
| 第 3 著者 氏名（和/英） | 小平 行秀 / Yukihide KOHIRA |
| 第 3 著者 所属（和/英） | 会津大学コンピュータ理工学部 School of Computer Science and Engineering, the University of Aizu |
| 第 4 著者 氏名（和/英） | 高橋 篤司 / Atsushi TAKAHASHI |
| 第 4 著者 所属（和/英） | 大阪大学大学院工学研究科電気電子情報工学専攻 Division of Electrical, Electronic and Information Engineering, Osaka University |
| 発表年月日 | 2009-05-21 |
| 資料番号 | VLD2009-4 |
| 巻番号（vol） | vol.109 |
| 号番号（no） | 34 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |