Contents Menu

LSI multi-layer routing method using a flow graph

Memoirs of the Faculty of Engineering, Yamaguchi University Volume 45 Issue 1 Page 83-90
published_at 1994-10
KJ00000156997.pdf
[fulltext] 640 KB
Title
フローグラフによるLSI多層配線問題の解法
LSI multi-layer routing method using a flow graph
Creators Watanabe Takahiro
Creators Omotani Keiji
Source Identifiers
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.
Languages jpn
Resource Type departmental bulletin paper
Publishers 山口大学工学部
Date Issued 1994-10
File Version Version of Record
Access Rights open access
Relations
[ISSN]0372-7661
[NCID]AN00244228
Schools 工学部