Parallelization of Iterative Heuristic for Performance-Driven Low-Power VLSI Standard Cell Placement.

Abstract

The complexity involved in VLSI design and its sub-problems has always made them ideal application areas for non-deterministic iterative heuristics. However, the major drawback has been the large runtime involved in reaching acceptable solutions especially in the case of multi-objective optimization problems. Among the acceleration techniques proposed, parallelization of these heuristics is one promising alternate. The motivation for Parallel CAD include faster runtimes, handling of larger problem sizes, and exploration of larger search space. In this work, the development of parallel algorithms for Tabu Search, applied on multi-objective VLSI cell-placement problem is presented. In VLSI circuit design, placement is the process of arranging circuit blocks on a layout. In standard cell design, placement consists of determining optimum positions of all blocks on the layout to satisfy the constraint and improve a number of objectives. The placement objectives in our work are to reduce power dissipation and wire-length while improving performance (timing). The parallelization is achieved on a cluster of workstations interconnected by a low-latency network (ethernet), by using Message Passing Interface (MPI) communication libraries. Circuits from ISCAS-89 are used as benchmarks. Results for parallel Tabu Search are compared with its sequential counterpart as a reference point for both, the quality of solution as well as the execution time.