Tabu Search: A Meta Heuristic for Netlist Partitioning

[摘要] The main goal of the paper is to explore the effectiveness of a new method calledTabuSearch[1] on partitioning and compare it with two techniques widely used in CAD toolsfor circuit partitioningi.e., Sanchis Interchange method and Simulated Annealing, interms of the running time and quality of solution. The proposed method integrates thewell known iterative multi-way interchange method with Tabu Search and leads to avery powerful network partitioning heuristic. It is characterized by an ability to escapelocal optima which usually cause simple descent algorithms to terminate by using ashort term memory of recent solutions. Moreover, Tabu Search permits backtracking toprevious solutions, which explore different directions and generates better partitions.The quality of the test results on MCNC benchmark circuits are very promising inmost cases. Tabu Search yields netlist partitions that contain 20%–67% fewer cut netsand are generated 2/3 to (1/2) times faster than the best netlist partitions obtained byusing an interchange method. Comparable partitions to those obtained by SimulatedAnnealing are obtained 5 to 20 times faster.

[学科分类] 电子、光学、磁材料