An Island-Based GA Implementation for VLSI Standard-Cell Placement

Abstract. Genetic algorithms require relatively large computation time to solve optimization problems, especially in VLSI CAD such as module placement. Therefore, island-based parallel GAs are used to speed up this procedure. The migration schemes that most researchers proposed in the past have migration near or after the demes converged [1,2]. How-ever, for the placement of medium or large standard-cell circuits, the time required for convergence is extremely long, which makes the above migration schemes non practical. In this paper, we propose a novel migra-tion scheme for synchronous island-based GA. Compared to the widely used ring topology that usually produces worse solutions at the begin-ning of the search but better solutions at later generations, the proposed migration scheme enables a parallel GA to outperform its serial version most of the time. Near linear speedup is obtained. We also implemented an asynchronous model that can achieve super-linear speedup.