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

3D VLSI设计并行算法研究

• 批准号: 03650287
• 负责人: 西関 隆夫
• 金额: $ 1.54万
• 依托单位: Tohoku University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for General Scientific Research (C)
• 财政年份: 1991
• 资助国家: 日本
• 起止时间: 1991 至 无数据
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-03650287/
• 关键词: VLSI配線; 並列アルゴリズム; グラフの辺彩色; 格子点列挙; 2変数整数計画問題

3次元VLSI設計に関して種々の理論的観点から調査・検討を行い,問題点を明らかにした。更に並列配線アルゴリズムの理論的基礎を与え,そのプロトタイプを設計し,理論的に解析した。1.VLSIの一般配線問題は平面(格子)グラフで点素な道を求める問題として定式化できる。配線領域を表す平面グラフG及び同電位にしたい端子対の集合(既ちネット)がいくつか与えられたとき,各ネットの端子を連結する道で互いに点素なものを求めたい。本研究ではネットの端子が平面グラフGに3つの面上にだけ置かれていて,各端子対の2つの端子が同じ面上にある場合に対し,Gに点素な道がある限りそれらを具体的に求める線形時間アルゴリズムを与えた。2.与えられた凸m角形内部のすべての整数格子点を列挙するO(K+m+logn)時間のアルゴリズムを与えた。ここでKは列挙された格子点の個数であり,nは凸m角形の大きさ,すなわちm角形を包含する軸平行な長方形の垂直,水平な辺のうち短い方の長さである。さらに,m個の制約式を持つ2変数整数計画問題を解くO(mlogm+logn)時間のアルゴリズムを与えた。ここでnは計画問題の許容解空間である凸多角形の大きさを表す。このアルゴリズムは従来知られているアルゴリズムより単純であり,時間計算量も改善している。3.グラフG=(V,E)のf辺彩色とは同じ色の辺が各点での接続辺中に高々f(v)本しか存在しないようにGの全ての辺を彩色することである。そのために必要な最小の色数はX'_f(G)と書かれる。X'_f(G)【less than or equal】max{「(d(v)+p(vw))/f(v)」:v,w∈V}であることは従来から知られていた。ここでd(v)は点vの次数,P(vw)は点v,w間の多重辺数である。本研究では上式右辺の色数でグラフGをf辺彩色する効率のよいアルゴリズムを与えた。その計算時間はO(|E|△_flog|E|)あるいはO(|E|√|E|log|E|)である。

Three dimensional VLSI design に masato し て kind 々 の 観 point of the theory of か ら survey, 検 for line を い, trouble spots を Ming ら か に し た. More に parallel wiring ア ル ゴ リ ズ ム の theory を and え そ の プ ロ ト タ イ プ を し design, theory of analytical し に た. 1. In VLSI, the general wiring problem is グラフで in a plane (lattice)グラフで in a dot element な in a channel を in a める problem, と in a て in a fixed pattern, で in a る in る. Wiring field を table す plane グ ラ フ G and び with potential に し た い terminal の seaborne collection (both ち ネ ッ ト) が い く つ か and え ら れ た と き, each ネ ッ ト の terminal link を す る way で mutual い に point element な も の を o め た い. This study で は ネ ッ ト の terminal が plane グ ラ フ に 3 G つ の surface に だ け buy か れ て い て, terminals の seaborne 2 つ の terminal が with じ surface に あ る occasions に し seaborne, G に point element な way が あ る limit り そ れ ら を specific に o め る linear time ア ル ゴ リ ズ ム を and え た. 2. With え ら れ た convex m Angle internal の す べ て の integer column grid point を 挙 す る O (K + m + logn) time の ア ル ゴ リ ズ ム を and え た. こ こ で K は column 挙 さ れ た lattice point number で の あ り, n は convex m Angle の big き さ, す な わ ち m Angle を contains す る の vertical axis parallel な rectangle, horizontal な 辺 の う ち short い party の long さ で あ る. さ ら に, m の restricted type を hold 2 - つ く integer program problem を solution of O (mlogm + logn) time の ア ル ゴ リ ズ ム を and え た. The でn planning problem <s:1> accommodating solution space である convex polygonal <s:1> large さを さを table す. こ の ア ル ゴ リ ズ ム は 従 to know ら れ て い る ア ル ゴ リ ズ ム よ り 単 pure で あ り, time computation も improve し て い る. 3. グ ラ フ G = (V, E) の f 辺 color と は with じ color の 辺 が each point で の meet 続 辺 に high 々 f (V) in this し か exist し な い よ う に G の full て の 辺 を color す る こ と で あ る. Youdaoplaceholder0 ために ために necessary な minimum <s:1> number of colors ために X'_f(G)と book れる れる. X '_f (G) (less than or equal] Max {" (d (v) + p (vw))/f (v) ", v, w ∈ v} で あ る こ と は 従 to か ら know ら れ て い た. Youdaoplaceholder0 でd(v) で point v <s:1> degree,P(vw) 辺 point v,w <s:1> multiple 辺 numbers である. This study で は type on the right 辺 の chromatic number で グ ラ を フ G f 辺 color す る sharper rate の よ い ア ル ゴ リ ズ ム を and え た. Youdaoplaceholder0 そ the calculation time is ある O(E / △_flog/E)ある ある O(E / √ E/log E /)である.

项目成果

S.Nakano: "Scheduling File Transfers under Port and Channel Constraints" Lecture Notes in Computer Science. 557. 43-51 (1991)

S.Nakano：“在端口和通道约束下安排文件传输”计算机科学讲义。

鈴木 均: "平面グラフの点素な道" 東北大学通研シンポジウム論文集. 28. 119-126 (1991)

Hitoshi Suzuki：“平面图中的点离散路径”东北大学研究研讨会论文集 28. 119-126 (1991)。

X.Zhou: "An Efficient Algorithm for EdgeーColoring SeriesーParallel Multigraphs" Lecture Notes in Computer Science. (1992)

X.Zhou：“边缘着色系列并行多重图的有效算法”计算机科学讲义（1992）。

中野 眞一: "グラフをfg辺彩色する近似アルゴリズム" 日本応用数理学会論文誌. 1. 195-211 (1991)

Shinichi Nakano：“图 fg 边着色的近似算法”日本应用数学学会汇刊 1. 195-211 (1991)。

西関 隆夫: "離散構造とアルゴリズム第4章グラフの辺彩色問題" 近代科学社, 230 (1992)

Takao Nishiseki：《离散结构与算法第 4 章图边缘着色问题》Kindai Kagakusha，230（1992）