Premium
Double‐row planar routing and permutation layout
Author(s) -
Tsukiyama Shuji,
Kuh Ernest S.
Publication year - 1982
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230120307
Subject(s) - permutation (music) , routing (electronic design automation) , heuristic , computer science , integrated circuit layout , very large scale integration , row , completeness (order theory) , algorithm , minification , floorplan , realization (probability) , generalization , representation (politics) , mathematics , mathematical optimization , integrated circuit , computer network , mathematical analysis , statistics , physics , database , politics , acoustics , political science , law , embedded system , operating system
Problems on layout for ICs (integrated circuits) and PCBs (printed circuit boards) are usually solved by heuristic approaches because they are complex. This article considers a special problem of double‐row planar routing. The problem represents a generalization of the permutation layout problem to which estimation of bounds and some algorithms have been proposed recently. Our approach is based on the interval graphical representation introduced in the single‐row single‐layer PCB problem. The objective function for minimization is the breadth of the realization, i.e., the total number of vertical tracks required to realize a given net list specified in terms of terminals on two parallel rows. The problem is shown to be intractable in the sense of NP‐completeness; however, a polynomial‐time heuristic algorithm is proposed. An upper bound for the breadth for an initial solution is given. Iterative improvement is next used. The algorithm has been programmed in FORTRAN and ran on the VAX 11/780 computer.