Provably Good Parallel Algorithms for Channel Routing of Multi-Terminal Nets
MARYLAND UNIV COLLEGE PARK SYSTEMS RESEARCH CENTER
Pagination or Media Count:
We consider the channel ronting problem of a set of multi-terminal nets in the knock-knee model. We develop a new approach to route all the nets within d alpha tracks, where d is the channel density, and 0 alpha d, such that the corresponding layout can be realized with three layers. Both the routing and the layer assignment algorithms have linear time sequential implementations. In addition both can be implemented on the CREW-PRAM model in 0np logn time, with p processors, 1 p n, and n is the size of the input.
- Computer Systems
- Operations Research