PARALLEL R-DIMENSIONAL PLACEMENT ON A VECTOR MINISUPERCOMPUTER

In this paper we describe the parallel implementation of a circuit pla cement algorithm which is based on a numerical optimization technique. The target machine is the Alliant FX/80, which is a shared memory mul tiprocessor with up to eight advanced computational elements which are individually capable of vector operation. The objective of the circui t placement problem is to arrange n logic blocks in an r-dimensional s pace so as to minimize the length of the interconnect wiring among the blocks. Special cases of the problem result when r=1 (the linear plac ement problem), r=2 (two dimensional placement of gate arrays or stand ard cells) and r=3 (three dimensional placement of chips on printed ci rcuit boards using the surface mount technology). The interconnect req uirements among blocks are specified by an n x n connectivity matrix C , where C-ij indicates the number of connections between blocks i and j. By expressing the total wire length as a quadratic form z=X'BX, the placement problem is reformulated as an eigenvalue problem; here B is an n x n positive semi-definite matrix which is in turn derived from C. X is a row vector of the position coordinates x(1), x(2),...,x(n) o f the n blocks. The minimization of z boils down to the problem of fin ding the eigenvector X of matrix B which minimizes z: the minimum eige nvalue represents the minimum cost function.