Title :
Provably good parallel algorithms for channel routing of multi-terminal nets
Author :
Krishnamurthy, Sridhar ; JáJá, Joseph
Author_Institution :
Dept. of Electr. Eng., Maryland Univ., College Park, MD, USA
Abstract :
The channel-routing problem of a set of multiterminal nets in the knock-knee model is considered. An approach is developed to route all the nets within d+α tracks, where d is the channel density, and 0⩽α⩽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 concurrent-read, exclusive write (CREW) PRAM model on 0(n/p +log n) time, with p processors, 1⩽p⩽n. Where n is the size of the input
Keywords :
parallel algorithms; CREW; PRAM model; channel density; channel routing; knock-knee model; layer assignment algorithms; linear time sequential implementations; multiterminal nets; parallel algorithms; Approximation algorithms; Contracts; Cost function; Ear; Educational institutions; Parallel algorithms; Parallel programming; Phase change random access memory; Routing; Very large scale integration;
Conference_Titel :
Frontiers of Massively Parallel Computation, 1988. Proceedings., 2nd Symposium on the Frontiers of
Conference_Location :
Fairfax, VA
Print_ISBN :
0-8186-5892-4
DOI :
10.1109/FMPC.1988.47469
