A positioning problem of fictitious terminals for a parallel router based on area division
A. Kamoshida, S. Tsukiyama · 2002
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.