Parallelizing Tabu Search on a Cluster of HeterogeneousWorkstations
In this paper, we present the parallelization of tabu search on a network of workstations using PVM. Two parallelization strategies are integrated: functional decomposition strategy and multi-search threads strategy. In addition, domain decomposition strategy is implemented probabilistically. The pe...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | , , |
| Format: | article |
| Published: |
2020
|
| Subjects: | |
| Online Access: | https://eprints.kfupm.edu.sa/id/eprint/275/1/J_Yamani_JOH_May2002.pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1864513399781588992 |
|---|---|
| author | Al-Yamani, Ahmad |
| author2 | Sait, Sadiq M. Youssef, H. unknown |
| author2_role | author author author |
| author_facet | Al-Yamani, Ahmad Sait, Sadiq M. Youssef, H. unknown |
| author_role | author |
| dc.creator.none.fl_str_mv | Al-Yamani, Ahmad Sait, Sadiq M. Youssef, H. unknown |
| dc.date.*.fl_str_mv | 2020 |
| dc.format.none.fl_str_mv | application/pdf |
| dc.identifier.none.fl_str_mv | https://eprints.kfupm.edu.sa/id/eprint/275/1/J_Yamani_JOH_May2002.pdf Parallelizing Tabu Search on a Cluster of HeterogeneousWorkstations. JOURNAL OF HEURISTICS 8 (3): 277-304 MAY 2002. |
| dc.language.none.fl_str_mv | en |
| dc.relation.none.fl_str_mv | https://eprints.kfupm.edu.sa/id/eprint/275/ |
| dc.rights.*.fl_str_mv | info:eu-repo/semantics/openAccess |
| dc.subject.none.fl_str_mv | Computer |
| dc.title.none.fl_str_mv | Parallelizing Tabu Search on a Cluster of HeterogeneousWorkstations |
| dc.type.none.fl_str_mv | Article PeerReviewed info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/article |
| description | In this paper, we present the parallelization of tabu search on a network of workstations using PVM. Two parallelization strategies are integrated: functional decomposition strategy and multi-search threads strategy. In addition, domain decomposition strategy is implemented probabilistically. The performance of each strategy is observed and analyzed. The goal of parallelization is to speedup the search in finding better quality solutions. Observations support that both parallelization strategies are beneficial, with functional decomposition producing slightly better results. Experiments were conducted for the VLSI cell placement, an NP-hard problem, and the objective was to achieve the best possible solution in terms of interconnection length, timing performance (circuit speed), and area. The multiobjective nature of this problem is addressed using a fuzzy goal-based cost computation. Key Words: tabu search, parallel tabu search, metaheuristic, functional decomposition, multi-search threads, combinatorial optimization, VLSI, standard cell design, placement, fuzzy logic |
| eu_rights_str_mv | openAccess |
| format | article |
| id | KFUPM_14d05e5c78bd289b1c8fccd5371654d4 |
| identifier_str_mv | Parallelizing Tabu Search on a Cluster of HeterogeneousWorkstations. JOURNAL OF HEURISTICS 8 (3): 277-304 MAY 2002. |
| language_invalid_str_mv | en |
| network_acronym_str | KFUPM |
| network_name_str | King Fahd University of Petroleum and Minerals |
| oai_identifier_str | oai::275 |
| publishDate | 2020 |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | Parallelizing Tabu Search on a Cluster of HeterogeneousWorkstationsAl-Yamani, AhmadSait, Sadiq M.Youssef, H.unknownComputerIn this paper, we present the parallelization of tabu search on a network of workstations using PVM. Two parallelization strategies are integrated: functional decomposition strategy and multi-search threads strategy. In addition, domain decomposition strategy is implemented probabilistically. The performance of each strategy is observed and analyzed. The goal of parallelization is to speedup the search in finding better quality solutions. Observations support that both parallelization strategies are beneficial, with functional decomposition producing slightly better results. Experiments were conducted for the VLSI cell placement, an NP-hard problem, and the objective was to achieve the best possible solution in terms of interconnection length, timing performance (circuit speed), and area. The multiobjective nature of this problem is addressed using a fuzzy goal-based cost computation. Key Words: tabu search, parallel tabu search, metaheuristic, functional decomposition, multi-search threads, combinatorial optimization, VLSI, standard cell design, placement, fuzzy logicArticlePeerReviewedinfo:eu-repo/semantics/publishedVersioninfo:eu-repo/semantics/articleapplication/pdfhttps://eprints.kfupm.edu.sa/id/eprint/275/1/J_Yamani_JOH_May2002.pdf Parallelizing Tabu Search on a Cluster of HeterogeneousWorkstations. JOURNAL OF HEURISTICS 8 (3): 277-304 MAY 2002. enhttps://eprints.kfupm.edu.sa/id/eprint/275/2020info:eu-repo/semantics/openAccessoai::2752019-11-01T13:23:24Z |
| spellingShingle | Parallelizing Tabu Search on a Cluster of HeterogeneousWorkstations Al-Yamani, Ahmad Computer |
| status_str | publishedVersion |
| title | Parallelizing Tabu Search on a Cluster of HeterogeneousWorkstations |
| title_full | Parallelizing Tabu Search on a Cluster of HeterogeneousWorkstations |
| title_fullStr | Parallelizing Tabu Search on a Cluster of HeterogeneousWorkstations |
| title_full_unstemmed | Parallelizing Tabu Search on a Cluster of HeterogeneousWorkstations |
| title_short | Parallelizing Tabu Search on a Cluster of HeterogeneousWorkstations |
| title_sort | Parallelizing Tabu Search on a Cluster of HeterogeneousWorkstations |
| topic | Computer |
| url | https://eprints.kfupm.edu.sa/id/eprint/275/1/J_Yamani_JOH_May2002.pdf |