A positioning problem of fictitious terminals for a parallel router based on area division

Author

Kamoshida, Atsushi ; Tsukiyama, Shuji

Author_Institution

Dept. of Electr. & Electron. Eng., Chuo Univ., Tokyo, Japan

Volume

3

fYear

1997

fDate

9-12 Jun 1997

Firstpage

1556

Abstract

A parallel detailed router based on the area division is an important tool to overcome the increase of CPU time and memory space required for routing of a very large multilayer sea-of-gates (SOG). In order to conduct such a parallel router independently in each divided area, fictitious terminals are introduced on the boarder of each divided area, and final routes connected to the fictitious terminals are sought in each divided area. In this paper, we consider a problem how to position such fictitious terminals on boarders, so as to make each detailed routing in a divided area easy. We formulate this problem as a minimum cost assignment problem, and propose an iterative improvement algorithm. We also show some experimental results which indicate the effectiveness of the algorithm and the formulation

Keywords

VLSI; circuit layout CAD; integrated circuit layout; iterative methods; logic CAD; logic arrays; network routing; parallel algorithms; VLSI layout; area division; detailed routing; fictitious terminals; iterative improvement algorithm; minimum cost assignment problem; parallel router; positioning problem; sea-of-gates; very large multilayer SOG; Costs; Delay estimation; Iterative algorithms; Local area networks; Microelectronics; Nonhomogeneous media; Routing; Timing; Transistors; Wire;

fLanguage

English

Publisher

ieee

Conference_Titel

Circuits and Systems, 1997. ISCAS '97., Proceedings of 1997 IEEE International Symposium on

Print_ISBN

0-7803-3583-X

Type

conf

DOI

10.1109/ISCAS.1997.621426

Filename

621426