A parallel circuit-partitioned algorithm for timing-driven standard cell placement

Simulated annealing based standard cell placement for VLSI designs has long been acknowledged as a computation-intensive process, and as a result, several research efforts have been undertaken to parallelize this algorithm. Parallel placement is most needed for very large circuits. Since these circuits do not fit in memory, the traditional approach has been to partition and place individual modules. This causes a degradation in placement quality in terms of area and wirelength. Our algorithm is circuit-partitioned and can handle arbitrarily large circuits on duster-of-workstations-type parallel machines, such as the Intel Paragon and IBM SP-2. Most previous work in parallel placement has minimized just area and wirelength, but with current deep submicron designs, minimizing wirelength delay is most important. As a result the algorithm discussed in this paper also supports timing driven placement for partitioned circuits. The algorithm, called mpiPLACE, has been tested on several large industry benchmarks on a variety of parallel architectures. (C) 1999 Academic Press.