제한적 벤드 수를 고려한 2-D 배선 알고리즘 = Bend-Constrained Global Routing Algorithm in Two-Dimensional Arrays

국문 초록 (Abstract)

VISI 및 MCM 레이아웃 설계시 고성능 회로에 적용할 수 있는 2-D 배선 방법에 대하여 그래프이론을 바탕으로 한 알고리즘을 제안한다. 칩 면적 및 성능 향상을 위하여 소수의 제한적인 벤드 수를 사용하여 셀의 최대 net 밀도가 최소화되도록 배선한다. 본 논문에서는 배선 영역을 반복적으로 4개로 분할하여 net당 4개의 벤드를 허용할때의 셀밀도의 상한선을 구하고 quad-tree의 각 레벨에서 적은 크기의 linear program과 network min-cost flow 알고리즘의 2 단계 기법을 이용하여 net 당 4개의 벤드로 제한된 배선 결과를 제안한다. 마지막으로 주어진 임의의 벤드 수의 상한치를 만족하는 일잔적인 배선 알고리즘이 제안된다. 본 논문에서는 이론적 기반을 마련한 동시에 실험 결과 제안된 알고리즘의 효용성을 입증하였다.

다국어 초록 (Multilingual Abstract)

This is the first paper that addresses a graph-theoretic framework to solve the bend-constrained global routing problem in two dimensional arrays of VLSI and MCMs. The objective is to route n nets with minimum density of global cells, using at most four bends per net. There are a number of applications where it is necessary to limit the number of bends on each wire. In this paper, we first derive a tight upper-bound for the worst case density of global cells. Then, at each level of an underlying quad-tree, we present a novel 4-bend routing algorithm by decomposing the original problem at level into two subproblems that can be solved optimally based on a two-stage approach of a small-sized linear programming followed by network min-cost flow. The first stage also contribute to inherently decompose the multi-terminal nets into two-terminal nets, by assigning terminals to four cutlines of each level of the quad tree. Thus, the complexity of the second stage is significantly reduced by considering only decomposed two-terminal nets. Finally, we present an extension that permits a limited degree of control over the number of bends. This paper focuses on both theoretic and empherical results, experimental results showed the effectiveness of the proposed algorithm.

목차 (Table of Contents)

• 요약
• Abstract
• 1. Introduction
• 2. Problem Formulation
• 3. 4-Bend Global Routing based on 4-Way Top-Down Recursion
• 4. Depth-Constrained Terminal Propagation
• 5. Experimental Results
• 6. Conclusion
• References
• 저자소개