Parallel algorithms are described for two physical design problems. The target machine is the Alliant FX/80, which is a shared-memory multiprocessor with up to eight advanced computational elements which are individually capable of vector operation. First, the parallel implementation of a circuit-placement algorithm is described that is based on a numerical-optimization technique. The objective of the circuit-placement problem is to arrange n logic blocks in an r-dimensional space so as to minimize the length of the interconnect wiring among the blocks. The problem is known to be NP-complete. Special cases of the problem result when r = 1 (the linear-placement problem), r = 2 ( 2D placement of gate arrays or standard cells ), and r = 3 ( 3D placement of chips on prin ted-circuit boards using surface-mount technology).
Next, a parallel implementation of Kernighan and Lin's algorithm for the 2-way circuit-partition problem is described. Given n logic blocks and their connectivity matrix C, the problem is to generate a balanced 2-way partition of the blocks such that the wiring across the partition is minimum. The partition problem is NPcomplete, but the Kernighan-Lin heuristic algorithm generates a near-optimal solution. VLSI layout, placement, partitioning, shared-memory muhiprocessor, vector supercomputer Most optimization problems in the physical design of integrated circuits are known to be NP-hard, and they are solved using heuristic techniques. Examples of this phenomenon are provided by the linear-placement problem and the 2-way circuit-partition problem ~. There is a tradeoff between the optimality of the final solution and the runtime requirements of the heuristic algorithm ; it is generally true that a heuristic with a larger time complexity generates a better quality solution to the