权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

3次元VLSI設計超並列アルゴリズムに関する研究

3D VLSI设计大规模并行算法研究

基本信息

批准号：
05650339
负责人：
西関隆夫
金额：
$ 1.34万
依托单位：
Tohoku University
依托单位国家：
日本
项目类别：
Grant-in-Aid for General Scientific Research (C)
财政年份：
1993
资助国家：
日本
起止时间：
1993 至无数据
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-05650339/
关键词：
非交差道 3次元VLSI 配線アルゴリズム平面グラフ平面領域

项目摘要

3次元VLSI設計に関して種々の理論的観点から調査・検討を行ない,問題点を明らかにした.更に並列配線アルゴリズムの理論的基礎を与え,そのプロトタイプを設計し,理論的に解析した.とりわけレイアウト設計の一層配線問題で現れる最短非交差道問題に焦点をあて,いくつかの評価基準の下で最適な非交差道を考察し,平面グラフおよび平面領域の非交差道を求める効率のよいアルゴリズムを与えた.1.平面グラフの外周上に全ての端子がある場合に,長さの総和最小な非交差道,すなわち最短非交差道をO(n log n)時間で求めるアルゴリズムを与えた.ここでnは入力の大きさである.2.平面グラフの2つの面の周上に全ての端子がある場合に,最短非交差道をO(n log n)時間で求めるアルゴリズムを与えた.このアルゴリズムは面積最小な配線設計に応用できる有用な結果である.3.上記2つのアルゴリズムを変更すれば,各道の長さに対して非減少な任意の評価関数を最小にする非交差道が求まることを示した.このアルゴリズムは長さの最大値が最小な非交差道を求めることができ,遅延時間が小さな配線設計に利用できる.4.軸並行な多角形の内部にいくつかの軸平行な多角形障害物がある平面領域で,2つの多角形の周上に全ての端子がある場合に,最短非交差道を求めるアルゴリズムを与えた.このアルゴリズムは,平面領域の問題を平面グラフの問題に帰着させることにより非交差道を求めたものである.5.長方形の内部に幾つかの長方形障害物があり,2つの長方形の周上に全ての端子がある場合に対し,最短非交差道をO(n log n)時間で求めるアルゴリズムを与え,その計算時間は係数の範囲内で最適であることを示した.

3-D VLSI design is related to the theoretical point of investigation, investigation and discussion, the problem point is clear. In addition, the theoretical basis of parallel wiring is analyzed. The shortest non-intersecting path problem is the problem of the shortest non-intersecting path in the design of a single layer. The problem of the shortest non-intersecting path in the design of a single layer is the problem of the shortest non-intersecting path. The problem of the shortest non-intersecting path in the design of a single layer is the problem of the shortest non-intersecting path in the design of a single layer. The problem of the shortest non-intersecting path in the design of a single layer is the design of a single O(n log n) time is the shortest non-intersection path, and O(n log n) time is the shortest non-intersection path. The shortest non-intersection path O(n log n) time is O(n log n). 3. Note 2 above: The length of each channel is not reduced, and the number of non-intersecting channels is minimized. The maximum value of the length of the polygon is the minimum non-intersecting channel. The delay time is small. The layout design is utilized. 4. The axis parallel polygon is used in the interior of the polygon. The axis parallel polygon is used in the plane field. The 2 polygon is used in the circumference. The terminal is used in the case of the shortest non-intersecting channel. However, the problems in the planar field are solved by the problems in the planar field. 5. There are several rectangular obstacles inside the rectangle, and there are all terminals on the circumference of the rectangle. For the occasion, the shortest non-intersection path is O(n log n) time, and the calculation time is optimal within the range of the coefficient.