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

3次元VLSI配線並列アルゴリズムに関する研究

3D VLSI布线并行算法研究

基本信息

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

来源：
https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-04650300/
关键词：
3次元VLSI VLSI配線平面グラフ非交差道辺彩色直並列グラフ

项目摘要

3次元VLSI設計に関して種々の理論的観点から調査・検討を行ない,問題点を明らかにした.更に並列配線アルゴリズムの理論的基礎を与え,そのプロトタイプを設計し,理論的に解析した.1.VLSIの配線経路を求める問題は,格子グラフで素な道を求める問題に帰着できる.本研究では,2つの入れ子になった長方形上に端子対が置かれたときに,それらの長方形で囲まれた平面格子グラフ内で各端子対を結ぶ辺素な道を求めるO(klog k)時間のアルゴリズムを与えた.kは端子対数である.平面格子グラフ上の辺素な道は4層格子グラフ上の点素な道(4層配線)に変換できるので,3次元VLSI上では有用なアルゴリズムである.また,種々の問題を解く上で有用となる新しいデータ構造Variable-Priority Queueを開発した.2.スケジューリング問題などに応用を持つが一般には解くことが困難とされているグラフの辺彩色問題が,直並列グラフに限定するとO(n△)時間で解けることを示し,そのアルゴリズムを設計した.nはグラフの点数,△は最大次数である.3.平面グラフの2つの面の周上にだけ端子対がある場合に,各端子対を結ぶ最短非交差道を求めるO(n log n)時間のアルゴリズムを与えた.nはグラフの点数である.非交差道とは辺や点を共有するかもしれないが交差はしない道の集合である.非交差道問題はVLSI設計において概略配線を求める際に解くことが必要となり,特に,配線領域を減少させたい場合には最短非交差道を求めることが有用である.4.1つの長方形上に端子対が置かれたときに,その周囲の格子グラフ内で辺素な道を求めるO(k log k)時間のアルゴリズムを与えた.kは端子対数である.また,外境界が長方形ならばそれを2層配線に変換でき,任意の形状の場合でも3層配線に変換できることを示した.また,最小の領域面積で配線する手法も与えた.

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 and design of the parallel distribution network are discussed. 1. The VLSI distribution network is solved. In this study, two pairs of terminals are arranged on rectangular lattice, and two pairs of terminals are arranged on rectangular lattice. In this study, O(klog k) time is calculated for each terminal pair. Plane lattice lattice on the pixel road reverse 4-layer lattice lattice on the pixel road (4-layer alignment) change, 3-dimensional VLSI on the useful 2. The problem of color selection is solved in general, and the problem of color selection is solved in time. △ Maximum number of times Non-intersection of the two sides of the road, the common point, the intersection of the two sides of the road. The problem of non-intersecting channels is solved in VLSI design. In particular, the distribution field is reduced. In the case of finding the shortest non-intersecting channel, the problem is useful. 4.1 The terminal pairs on the rectangle are arranged in O(k log k) time. The outer boundary is rectangular, and the outer boundary is rectangular. The outer boundary is rectangular. The smallest area of the field is the line.