Memoirs of the Faculty of Engineering, Yamaguchi University

Back to Top

Memoirs of the Faculty of Engineering, Yamaguchi University Volume 45 Issue 1
published_at 1994-10

LSI multi-layer routing method using a flow graph

フローグラフによるLSI多層配線問題の解法
Watanabe Takahiro
Omotani Keiji
fulltext
640 KB
KJ00000156997.pdf
Descriptions
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.