Title :
Parallel algorithms for single row routing in narrow streets
Author :
Das, Saibal ; Saxena, Sanjeev
Author_Institution :
Dept. of Comput. Sci. & Eng., Indian Inst. of Technol., Kanpur, India
Abstract :
In this paper, the problem, of obtaining an optimal layout for the single row routing problem in narrow streets (maximum number of tracks in either street is at most 2) on parallel computers is studied. An O(log n) time parallel algorithm with O(n/logn) processors on a CREW PRAM and an O(log2n) time cost-optimal algorithm on a tree machine is obtained
Keywords :
VLSI; circuit layout CAD; integrated circuit layout; network routing; parallel algorithms; CREW PRAM; IC design; VLSI layout; narrow streets; optimal layout; parallel algorithms; single row routing; tree machine; Algorithm design and analysis; Computer science; Concurrent computing; Data engineering; Data structures; Parallel algorithms; Phase change random access memory; Printed circuits; Routing; Sufficient conditions;
Conference_Titel :
VLSI Design, 1995., Proceedings of the 8th International Conference on
Conference_Location :
New Delhi
Print_ISBN :
0-8186-6905-5
DOI :
10.1109/ICVD.1995.512070
