DPAHMA: a novel dual-population adaptive hybrid memetic algorithm for non-slicing VLSI floorplans

摘要

Floorplanning is a crucial part of very large-scale integration (VLSI) physical design flow. It primarily determines the position of the blocks on a chip by considering the area, the total wirelength, etc., in light of several real-world limitations such as delay, price, and chip performance. Adopting B*-tree representation, this paper proposes a novel dual-population adaptive hybrid memetic algorithm called DPAHMA to handle the VLSI floorplanning problem effectively by optimizing the chip area and the total wirelength. Three main ideas are presented in this paper, including new definitions of crossover and mutation operators based on B*-tree encoding that overcome the shortcomings of the existing method, such as overly complicated operations on binary trees and a lack of diversity; a dynamic self-adjusting objective function, namely WeightDS, which is able to find solutions more suitable for the user-specified weight; and a main-auxiliary population mechanism by which a candidate population is introduced to assist the normal population in the global search phase. To make full use of the information obtained by the local search method, the candidate population keeps its high-quality solutions. The individuals from the candidate population crossover with the individuals from the normal population before the end of each iteration to obtain higher-quality solutions as much as possible. Experimental results for MCNC and GSRC benchmarks show that DPAHMA obtains floorplans effectively with better area and total wirelength than those of the state-of-the-art floorplanners.