The crossing distribution problem

TitleThe crossing distribution problem
Publication TypeConference Paper
Year of Publication1991
AuthorsMarek-Sadowska, M, Sarrafzadeh, M
Conference NameComputer-Aided Design, 1991. ICCAD-91. Digest of Technical Papers., 1991 IEEE International Conference on
Date Publishednov
Keywordscircuit layout CAD, complexity, computational complexity, crossing distribution problem, global routing, net ordering
AbstractThe authors study the problem of `properly' distributing the set of crossings (i.e., intersection of nets) of a given global routing among the regions. Each region is assigned a quota, being the maximum number of crossings allowed in that region, which depends on its area and its complexity (e.g., the number of nets going through it and the number of terminals it contains). The crossing distribution problem (CDP) is to find a net ordering at each boundary so as to minimize the total number of crossings and to satisfy the quotas. The authors propose an O(mn2+m zeta;3/2) time algorithm for CDP, where m is the number of modules, n is the number of nets, and zeta; is the number of crossings