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

3次元VLSIレイアウト設計アルゴリズムに関する研究

3D VLSI版图设计算法研究

基本信息

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

来源：
https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-07650408/
关键词：
VLSIレイアウト二層配線アルゴリズム非交差道辺彩色

项目摘要

3次元VLSI設計に関して種々の理論的観点から調査・検討を行ない,問題点を明らかにした.更に並列配線アルゴリズムの理論的基礎を与え,そのプロトタイプを設計し,理論的に解析した.1.均等辺彩色問題で,従来より知られているO(km^2)時間のアルゴリズムを更に発展させ,より効率の良いO(m^2/k+mn)時間のアルゴリズムを与えた.ここでnはGの点数,mは辺数である.2.f-辺彩色が通常の辺彩色アルゴリズムを用いて求めることができることを示し,次いで,多重グラフのf-辺彩色問題が単純グラフの通常の辺彩色問題に容易に多項式時間で帰着できることを示した.3.直並列グラフを一般化した部分k木に対してf-辺彩色問題を線形時間で解く逐次アルゴリズムを与えた.また,O(n/logn)個のプロセッサを用いてO(logn)時間でf-辺彩色問題を解く最適な並列アルゴリズムも与えた.ここでnは入力の大きさである.本アルゴリズムはこれまで知られていなかったものであり重要な成果である.4.2次元平面上にいくつかの障害物および二層配線領域があるときに,指定された2組の端子対を結ぶ2本の道で長さの和が最小なアルゴリズムをO(nlogn)時間,O(n)の記憶量で求めた,ただし,障害物および二層配線領域は軸平行な長方形であるとする.5.平面領域A内でそれぞれの端子対を結ぶ直交線分からなるk本の道で,互いに交差せず,長さの総和が最小なアルゴリズムをO(nlogn)時間で求めた.ここではn=r+kである.ただし,長方形の内部にr個の長方形障害物がある平面領域Aにおいて,k個の端子対が外側の長方形の周および内部の一つの長方形障害物の周にのみあるとする.

3-D VLSI design is related to the theoretical point of investigation, investigation and discussion, the problem point is clear. 1. The problem of color equalization is solved in O(km^2) time and O (m^2/k + mn) time, and the problem of color equalization is solved in O(km^2) time and O(m^2/k+mn) time.ここでnはGの点数,mは辺数である.2.f-辺彩色が通常の辺彩色アルゴリズムを用いて求めることができることを示し,次いで, Multiple color problems are simple and easy to solve in polynomial time. 3. Straight color problems are generalized in part. 3. F-color problems are linear and easy to solve in polynomial time. O(n/logn) times for solving the f-color problem.ここでnは入力の大きさである. This is the first time that we have ever known about this problem. 4.2 On the dimensional plane, we have always known about this problem. 4.2 On the dimensional plane, we have always known about this problem. 4.2 On the dimensional plane, we have always known about this problem. The two-layer wiring field is parallel to the axis of the rectangle. 5. The plane field A is parallel to the axis of the rectangle. The terminal pair is perpendicular to the orthogonal line. k This path is parallel to the axis of the rectangle. The intersection difference is O(nlogn).ここではn=r+kである. R rectangular barriers in the rectangular interior A rectangular perimeter in the rectangular interior K rectangular barriers in the rectangular perimeter A rectangular perimeter in the rectangular interior.