PLACEMENT OF SHAPEABLE BLOCKS

A simulated annealing-based algorithm is presented for the placement of shapeable blocks for IC layouts. The algorithm minimizes both the enveloping area and the estimated total wire length of a set of blocks interconnected by nets. The size of the blocks may vary within limits. Overlap among blocks is allowed but increasingly penalized as the optimization process continues. The presence of overlap is found to be essential for obtaining good solutions to the placement problem. The various terms in the cost function are discussed in detail. In addition to the sequential implementation the authors present a parallel implementation of the placement algorithm on an experimental multiprocessor architecture using a clustered simulated annealing algorithm. Both for the sequential and parallel implementation it is concluded that the placement algorithm performs well, near-optimal solutions within reasonable computation time are archieved.