A fast parallel algorithm for slicing floorplans

Author

Chen, Cheng-Hsi ; Tollis, Ioannis G.

Author_Institution

Dept. of ECE, Concordia Univ., Montreal, Que., Canada

fYear

1993

fDate

3-6 May 1993

Firstpage

1774

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(log² 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;

fLanguage

English

Publisher

ieee

Conference_Titel

Circuits and Systems, 1993., ISCAS '93, 1993 IEEE International Symposium on

Conference_Location

Chicago, IL

Print_ISBN

0-7803-1281-3

Type

conf

DOI

10.1109/ISCAS.1993.394088

Filename

394088

Link To Document

https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2610919