Exploring Asynchronous MMC Based Parallel SA Schemes for Multiobjective Cell-Placement on a Cluster of Workstations
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,...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | , , |
| Format: | article |
| Published: |
2020
|
| Subjects: | |
| Online Access: | https://eprints.kfupm.edu.sa/id/eprint/230/1/JCCpaper.ps |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | 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. |
|---|