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,...
محفوظ في:
| المؤلف الرئيسي: | |
|---|---|
| مؤلفون آخرون: | , , |
| التنسيق: | article |
| منشور في: |
2020
|
| الموضوعات: | |
| الوصول للمادة أونلاين: | https://eprints.kfupm.edu.sa/id/eprint/230/1/JCCpaper.ps |
| الوسوم: |
إضافة وسم
لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!
|
| _version_ | 1864513399778443264 |
|---|---|
| author | Sait, Sadiq M. |
| author2 | Zaidi, Ali Mustafa Ali, Mustafa I. unknown |
| author2_role | author author author |
| author_facet | Sait, Sadiq M. Zaidi, Ali Mustafa Ali, Mustafa I. unknown |
| author_role | author |
| dc.creator.none.fl_str_mv | Sait, Sadiq M. Zaidi, Ali Mustafa Ali, Mustafa I. unknown |
| dc.date.*.fl_str_mv | 2020 |
| dc.format.none.fl_str_mv | application/postscript |
| dc.identifier.none.fl_str_mv | https://eprints.kfupm.edu.sa/id/eprint/230/1/JCCpaper.ps Exploring Asynchronous MMC Based Parallel SA Schemes for Multiobjective Cell-Placement on a Cluster of Workstations. Cluster Computing, The Journal of Networks, Software Tools and Applications. ISSN ISSN: 1386-7857 (print version), ISSN: 1573-7543 (electronic version) (Submitted) |
| dc.language.none.fl_str_mv | en |
| dc.publisher.none.fl_str_mv | Springer US |
| dc.relation.none.fl_str_mv | https://eprints.kfupm.edu.sa/id/eprint/230/ http://www.springer.com/computer/communications/journal/10586 |
| dc.rights.none.fl_str_mv | cc_by_nc_nd info:eu-repo/semantics/openAccess |
| dc.subject.none.fl_str_mv | Computer |
| dc.title.none.fl_str_mv | Exploring Asynchronous MMC Based Parallel SA Schemes for Multiobjective Cell-Placement on a Cluster of Workstations |
| dc.type.none.fl_str_mv | Article NonPeerReviewed info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/article |
| description | 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. |
| eu_rights_str_mv | openAccess |
| format | article |
| id | KFUPM_877045a2df5894f2e9b6a95be5ff4a33 |
| identifier_str_mv | Exploring Asynchronous MMC Based Parallel SA Schemes for Multiobjective Cell-Placement on a Cluster of Workstations. Cluster Computing, The Journal of Networks, Software Tools and Applications. ISSN ISSN: 1386-7857 (print version), ISSN: 1573-7543 (electronic version) (Submitted) |
| language_invalid_str_mv | en |
| network_acronym_str | KFUPM |
| network_name_str | King Fahd University of Petroleum and Minerals |
| oai_identifier_str | oai::230 |
| publishDate | 2020 |
| publisher.none.fl_str_mv | Springer US |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| rights_invalid_str_mv | cc_by_nc_nd |
| spelling | Exploring Asynchronous MMC Based Parallel SA Schemes for Multiobjective Cell-Placement on a Cluster of WorkstationsSait, Sadiq M.Zaidi, Ali MustafaAli, Mustafa I.unknownComputerSimulated 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.Springer USArticleNonPeerReviewedinfo:eu-repo/semantics/publishedVersioninfo:eu-repo/semantics/articleapplication/postscripthttps://eprints.kfupm.edu.sa/id/eprint/230/1/JCCpaper.ps Exploring Asynchronous MMC Based Parallel SA Schemes for Multiobjective Cell-Placement on a Cluster of Workstations. Cluster Computing, The Journal of Networks, Software Tools and Applications. ISSN ISSN: 1386-7857 (print version), ISSN: 1573-7543 (electronic version) (Submitted) enhttps://eprints.kfupm.edu.sa/id/eprint/230/http://www.springer.com/computer/communications/journal/10586cc_by_nc_ndinfo:eu-repo/semantics/openAccess2020oai::2302019-11-01T13:23:07Z |
| spellingShingle | Exploring Asynchronous MMC Based Parallel SA Schemes for Multiobjective Cell-Placement on a Cluster of Workstations Sait, Sadiq M. Computer |
| status_str | publishedVersion |
| title | Exploring Asynchronous MMC Based Parallel SA Schemes for Multiobjective Cell-Placement on a Cluster of Workstations |
| title_full | Exploring Asynchronous MMC Based Parallel SA Schemes for Multiobjective Cell-Placement on a Cluster of Workstations |
| title_fullStr | Exploring Asynchronous MMC Based Parallel SA Schemes for Multiobjective Cell-Placement on a Cluster of Workstations |
| title_full_unstemmed | Exploring Asynchronous MMC Based Parallel SA Schemes for Multiobjective Cell-Placement on a Cluster of Workstations |
| title_short | Exploring Asynchronous MMC Based Parallel SA Schemes for Multiobjective Cell-Placement on a Cluster of Workstations |
| title_sort | Exploring Asynchronous MMC Based Parallel SA Schemes for Multiobjective Cell-Placement on a Cluster of Workstations |
| topic | Computer |
| url | https://eprints.kfupm.edu.sa/id/eprint/230/1/JCCpaper.ps |