Two-dimensional placement using tabu search

Search based placement of modules is an important problem in VLSI design. I t is always desired that the search should converge quickly to a high quali ty solution. This paper presents a tabu search based optimization technique to place modules on a regular two-dimensional array. The goal of the techn ique is to speed up the placement process. The technique is based on a two- step placement strategy. The first step is targeted toward improving circui t routability and the second step addresses circuit performance. The techni que is demonstrated through placement of several benchmark circuits on acad emic as well as commercial FPGAs. Results are compared to placements genera ted by commercial CAE tools and published simulated annealing based techniq ues. The tabu search technique compares favorably to published simulated an nealing based techniques, and it demonstrates an average execution time spe edup of 20 with no impact on quality of results when compared to commercial tools.