Exploring Asynchronous MMC Based Parallel SA Schemes for Multiobjective Cell-Placement on a Cluster of Workstations - Sait, Sadiq M. (2020)
Simulated Annealing (SA) is a popular iterative heuristic used to solve a wide variety of combinatorial optimization problems. However, depending on the size of the problem, it may have large run-time requirements. One practical approach to speed up its execution is to parallelize it. In this paper, several parallel SA schemes based on the Asynchronous Multiple-Markov Chain model (AMMC) (described in~\cite{Lee96} and applied to standard-cell placement in~\cite{Chandy97}) are explored. We investigate the speedup and solution quality characteristics of each scheme when implemented on an inexpensive cluster of workstations for solving a multi-objective cell placement problem. This problem requires the optimization of conflicting objectives (interconnect wire-length, power dissipation, and timing performance), and Fuzzy logic is used to integrate the costs of these objectives \cite{junaid_cec2002,book1}. Experiments are performed on ISCAS-85/89 benchmark circuits. Our goal is to develop several AMMC based parallel SA schemes and explore their suitability for different objectives: achieving near linear speedups while still meeting solution quality targets, and obtaining higher quality solutions in the least possible duration.