Title :
A fast parallel algorithm for slicing floorplans
Author :
Chen, Cheng-Hsi ; Tollis, Ioannis G.
Author_Institution :
Dept. of ECE, Concordia Univ., Montreal, Que., Canada
Abstract :
A parallel algorithm, which is based on the EREW PRAM (exclusive read, exclusive write parallel random access machine) is presented. It is shown that the area optimization problem of slicing floorplans can be solved in O(l log n) time, using O( n) processors, where l is the height of the slicing tree and n is the number of modules. Since in practice, the slicing tree is balanced, the algorithm takes O(log2 n) time, and thus the problem is in NC
Keywords :
circuit layout CAD; computational complexity; network topology; parallel algorithms; trees (mathematics); EREW PRAM; NC problem; area optimization problem; computation time; exclusive read, exclusive write parallel random access machine; floorplans; parallel algorithm; slicing; slicing tree; Area measurement; Circuits; Costs; Parallel algorithms; Phase change random access memory; Position measurement; Process design; Semiconductor device measurement; Topology; Very large scale integration;
Conference_Titel :
Circuits and Systems, 1993., ISCAS '93, 1993 IEEE International Symposium on
Conference_Location :
Chicago, IL
Print_ISBN :
0-7803-1281-3
DOI :
10.1109/ISCAS.1993.394088
