多種フロ-理論と計算幾何学を用いた3次元VLSI設計アルゴリズム
使用多流理论和计算几何的 3D VLSI 设计算法
基本信息
- 批准号:01550275
- 负责人:
- 金额:$ 1.28万
- 依托单位:
- 依托单位国家:日本
- 项目类别:Grant-in-Aid for General Scientific Research (C)
- 财政年份:1989
- 资助国家:日本
- 起止时间:1989 至 无数据
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
3次元VLSI設計に関して種々の理論的観点から調査・検討を行い、問題点を明らかにした・更に並列配線アルゴリズムの理論的基礎を与え、そのプロトタイプを設計し、理論的に解析した。1.VLSIの一層配線問題は平面(格子)グラフでスタイナ-林を求める問題として定式化できる。配線領域を表す平面グラフG及び同電位にしたい端子の集合(即ちネット)がいくつか与えられたとき、各ネットの端子を連結する木で互いに点素なもの(即ちスタイナ-林)を求めたい。本研究ではネットの端子が平面グラフGの2つの面上にだけ置かれている場合に上の問題を解く並列アルゴリズムを与えた。端子が全て外周上にある場合にはO(n^3/1ogn)個のプロセッサ-を用いてO(log^2n)時間でスタイナ-林を求める。ここでnはグラフの点数である。端子が2つの面上にだけある場合にはO(n^6/logn)個のプロセッサ-を用いてO(log^2/n)時間で求める。あるいはO(n^3/logn)時間で求める。2.平面グラフで内素な道を求める並列アルゴリズムを与えた。このアルゴリズムはO(n^6/logn)個のプロセッサ-を用いればO(log^2n)時間で終了し、O(n^3/logn)個のプロセッサ-を用いればO(log^3n)時間で終了する。3.与えられた3-連結グラフを、指定された点を含みかつ指定された大きさの3つの連結部分グラフに分割するO(n^2)時間のアルゴリズムを与えた。ここでnはグラフの点数である。また辺数がO(n)である全域部分グラフを求めるO(n^2)時間も求めた。4.3次元VLSI配線のための多層チャネル配線アルゴリズムを設計し、その効率及び計算時間を解析した。またそれを用いて、3次元VLSI配線プログラムのプロトタイトを設計した。
3-dimensional VLSI design and analysis of software design and analysis of various theories and theories, and list the fundamentals and analysis of the distribution theory. 1.VLSI one of the wiring problems plane (grid) to determine the size of the problem-Lin asks for a solution to the problem. In the field of distribution, there is a set of terminals on the same level (that is, on the same level). Each terminal is connected to each other, and each terminal is connected to each other. The purpose of this study is to find out how to solve the problem on the plane of the terminal and list the problems on the plane of the terminal. The terminal has a full periphery full-cycle switch (n ^ 3
项目成果
期刊论文数量(5)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
H.Suzuki: "Finding Steiner Forests in Planar Graphs" Proc.First Ann.ACM-SIAM Symp.on Discrete Algorithms,. 1. 444-453 (1990)
H.Suzuki:“在平面图中寻找斯坦纳森林”Proc.First Ann.ACM-SIAM Symp.on 离散算法,。
- DOI:
- 发表时间:
- 期刊:
- 影响因子:0
- 作者:
- 通讯作者:
T.Nishizeki: "Planar Graph Problems" Computing. Supp.7. 53-68 (1989)
T.Nishizeki:“平面图问题”计算。
- DOI:
- 发表时间:
- 期刊:
- 影响因子:0
- 作者:
- 通讯作者:
H.Suzuki: "Variable-priority queue and doughnut reuting" Journal of Algorithms.
H.Suzuki:“可变优先级队列和环形reuting”算法杂志。
- DOI:
- 发表时间:
- 期刊:
- 影响因子:0
- 作者:
- 通讯作者:
鈴木均: "3-連結グラフの3分割アルゴリズム" 情報処理(創立30周年記念論文). 31. (1990)
Hitoshi Suzuki:“3 连通图的 3 分区算法”信息处理(30 周年论文)。(1990 年)。
- DOI:
- 发表时间:
- 期刊:
- 影响因子:0
- 作者:
- 通讯作者:
H.Suzuki: "Parallel Algorithms for Finding Steiner Forests in Planar Graphs" Proc.SIGAL Int.Symp.on Algorithms.
H.Suzuki:“在平面图中查找斯坦纳森林的并行算法”Proc.SIGAL Int.Symp.on 算法。
- DOI:
- 发表时间:
- 期刊:
- 影响因子:0
- 作者:
- 通讯作者:
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
西関 隆夫其他文献
Proceedings of GSIS International Symposium on Information Sciences of New Era : brain, mind and society : september 26-27, 2005 Sendai, Japan
GSIS 新时代信息科学国际研讨会论文集:大脑、心智与社会:2005 年 9 月 26-27 日日本仙台
- DOI:
- 发表时间:
2005 - 期刊:
- 影响因子:0
- 作者:
丸岡 章;西関 隆夫;堀口 進;東北大学大学院情報科学研究科 - 通讯作者:
東北大学大学院情報科学研究科
西関 隆夫的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('西関 隆夫', 18)}}的其他基金
グラフ描画アルゴリズムとそのWeb情報検索への応用
图形绘制算法及其在网络信息检索中的应用
- 批准号:
16092203 - 财政年份:2004
- 资助金额:
$ 1.28万 - 项目类别:
Grant-in-Aid for Scientific Research on Priority Areas
3次元VLSIレイアウト設計アルゴリズムに関する研究
3D VLSI版图设计算法研究
- 批准号:
07650408 - 财政年份:1995
- 资助金额:
$ 1.28万 - 项目类别:
Grant-in-Aid for General Scientific Research (C)
3次元VLSI設計並列高速アルゴリズムに関する研究
3D VLSI设计并行高速算法研究
- 批准号:
06650398 - 财政年份:1994
- 资助金额:
$ 1.28万 - 项目类别:
Grant-in-Aid for General Scientific Research (C)
3次元VLSI設計超並列アルゴリズムに関する研究
3D VLSI设计大规模并行算法研究
- 批准号:
05650339 - 财政年份:1993
- 资助金额:
$ 1.28万 - 项目类别:
Grant-in-Aid for General Scientific Research (C)
3次元VLSI配線並列アルゴリズムに関する研究
3D VLSI布线并行算法研究
- 批准号:
04650300 - 财政年份:1992
- 资助金额:
$ 1.28万 - 项目类别:
Grant-in-Aid for General Scientific Research (C)
3次元VLSI設計並列アルゴリズムに関する研究
3D VLSI设计并行算法研究
- 批准号:
03650287 - 财政年份:1991
- 资助金额:
$ 1.28万 - 项目类别:
Grant-in-Aid for General Scientific Research (C)
3次元VLSI設計アルゴリズムの効率化に関する研究
提高3D VLSI设计算法效率的研究
- 批准号:
02650254 - 财政年份:1990
- 资助金额:
$ 1.28万 - 项目类别:
Grant-in-Aid for General Scientific Research (C)
大規模ネットワークの計算機処理アルゴリズムに関するグラフ理論的研究
大规模网络计算机处理算法的图论研究
- 批准号:
X00210----475235 - 财政年份:1979
- 资助金额:
$ 1.28万 - 项目类别:
Grant-in-Aid for Encouragement of Young Scientists (A)
大規模システム及びネットワークの計算機処理に関するグラフ理論的研究
大规模系统和网络计算机处理的图论研究
- 批准号:
X00210----175174 - 财政年份:1976
- 资助金额:
$ 1.28万 - 项目类别:
Grant-in-Aid for Encouragement of Young Scientists (A)
相似海外基金
ニューラルネットワークによるVLSI配線最適化アルゴリズムの研究
基于神经网络的VLSI布线优化算法研究
- 批准号:
07780263 - 财政年份:1995
- 资助金额:
$ 1.28万 - 项目类别:
Grant-in-Aid for Encouragement of Young Scientists (A)
分散処理による多層VLSI配線システムの研究
采用分布式处理的多层VLSI布线系统研究
- 批准号:
06750421 - 财政年份:1994
- 资助金额:
$ 1.28万 - 项目类别:
Grant-in-Aid for Encouragement of Young Scientists (A)
3次元VLSI配線並列アルゴリズムに関する研究
3D VLSI布线并行算法研究
- 批准号:
04650300 - 财政年份:1992
- 资助金额:
$ 1.28万 - 项目类别:
Grant-in-Aid for General Scientific Research (C)