Premium
A routing procedure for an IC module with many pins—a solution to a circular permutation layout problem
Author(s) -
Ozawa Takao
Publication year - 1985
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.3230150105
Subject(s) - routing (electronic design automation) , permutation (music) , computer science , recursion (computer science) , multipath routing , equal cost multi path routing , process (computing) , static routing , mathematics , algorithm , computer network , routing protocol , physics , acoustics , operating system
This article considers routing for an IC module with many pins which is mounted on a board. Routing for such an IC module must be planar. It is also constrained by the order of pins and the congestion between pins (the number of wires passing between adjacent pins) of the module. The routing procedure presented in this paper is recursive: First, routing to a particular pin passing between two adjacent pins is tried in order to fix the relative position of the module on the board. If this can be done, the set of pins is divided into two subsets. Then routing to a pin or two in each of the subsets is tried. If this is successful, routing to a pin or two is tried again in each of the resulting smaller subsets. This process is repeated, if possible, until the entire routing for the module is completed. If no legal routing is found in the recursion process, the procedure goes back to the beginning of the recursion and tries a new initial routing until all the possible initial routings are exhausted. The time complexity and the space complexity of the procedure are O( l 2 ) and O(l), respectively, in the worst case where l is the number of pins of the module. The procedure can be regarded as a solution to a circular permutation layout problem.