Bibliographic Information
- Other Title
-
- フローグラフによるLSI多層配線問題の解法
- フローグラフ ニヨル LSI タソウ ハイセン モンダイ ノ カイホウ
Search this article
Abstract
Advances in VLSI fabrication technology have made it possible to use more than two routing layers for interconnection. In such a multi-layer routing technology, one of the important objective functions is via-minimization, that is, the number of vias should be kept as small as possible. A topological planar routing (TPR) was proposed to solve this via-minimization problem. TPR is a layer assignment method which assigns each net to one of the layers without crossing other nets in the same layer. Although an optimum TPR is unfortunately known as an NP-complete problem, it can be approximately solved in polynomial time for the channel layout model as a minimum-cost maximum-flow problem using a flow graph. In this paper, we propose an improved TPR for more general layout model like a macrocell layout model, where planarity testing and a flow graph are modified to treat our model. An experimental result shows that our improvements increase an efficiency of usage of multi-layers.
Journal
-
- 山口大学工学部研究報告
-
山口大学工学部研究報告 45 (1), 83-90, 1994-10
山口大学工学部
- Tweet
Details 詳細情報について
-
- CRID
- 1050845762384335744
-
- NII Article ID
- 110000216970
-
- NII Book ID
- AN00244228
-
- ISSN
- 03727661
-
- NDL BIB ID
- 3904932
-
- Text Lang
- ja
-
- Article Type
- departmental bulletin paper
-
- Data Source
-
- IRDB
- NDL
- CiNii Articles