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
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
工学部