On Using Tabu Search for Design Automation of VLSI Systems

• Published in: Journal of heuristics 2003-01, Vol.9 (1), p.75
• Main Authors: Emmert, John M, Lodha, Sandeep, Bhatia, Dinesh K
• Format: Article
• Language: English
• Subjects: Algorithms; Automation; CAD; Computer aided design; Computer engineering; Field programmable gate arrays; Graphs; Heuristic; Integrated circuits; Optimization; Problem solving; Studies; Wire drawing
• ISSN: 1381-1231; 1572-9397
• DOI: 10.1023/A:1021893712145

Tabu search is a meta-heuristic problem solving technique that, when applied carefully, provides near optimal solutions in a very short time. In this paper, we have described the use of tabu search for solving problems related to very large scale integrated (VLSI) circuit design automation. Specifically, we have demonstrated the use for VLSI circuit partitioning and placement. We present a tabu search based circuit bi-partitioning technique that partitions circuits with the goal of minimizing the size of the cutset between the partitions. Then, we use tabu search techniques along with force directed placement techniques to accomplish the physical placement of VLSI circuits on regular two-dimensional arrays with the goal of minimizing the placement time. We use empirical data from partitioning and placement of benchmark circuits to test our techniques. Our methods show improvement when compared to partitioning techniques from the literature and commercially available placement tools. Relative to the literature, our tabu search bi-partitioning technique improves on the best known minimum cuts for several benchmark circuits. Relative to commercially available computer aided design tools, our tabu search based placement approach shows dramatic (20x) speedup in execution time without negative impact on the quality of the solution. [PUBLICATION ABSTRACT]