Physical optimization algorithms for mapping data to distributed-memory multiprocessors
We present three parallel physical optimization algorithms for mapping data to distributed-memory multiprocessors, concentrating on irregular loosely synchronous problems. We also present a technique for efficient mapping of large data sets. The algorithms include a parallel genetic algorithm (PGA),...
Saved in:
| Main Author: | |
|---|---|
| Format: | masterThesis |
| Published: |
1992
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/10725/7959 http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php https://dl.acm.org/citation.cfm?id=168972 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1864513483497799680 |
|---|---|
| author | Mansour, Nashat |
| author_facet | Mansour, Nashat |
| author_role | author |
| dc.creator.none.fl_str_mv | Mansour, Nashat |
| dc.date.none.fl_str_mv | 1992 2018-05-30T11:47:30Z 2018-05-30T11:47:30Z 2018-05-30 |
| dc.identifier.none.fl_str_mv | http://hdl.handle.net/10725/7959 Mansour, N. (1992). Physical optimization algorithms for mapping data to distributed-memory multiprocessors. http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php https://dl.acm.org/citation.cfm?id=168972 |
| dc.language.none.fl_str_mv | en |
| dc.publisher.none.fl_str_mv | Syracuse University |
| dc.rights.*.fl_str_mv | info:eu-repo/semantics/openAccess |
| dc.subject.none.fl_str_mv | Computer science Artificial intelligence |
| dc.title.none.fl_str_mv | Physical optimization algorithms for mapping data to distributed-memory multiprocessors |
| dc.type.none.fl_str_mv | Thesis info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/masterThesis |
| description | We present three parallel physical optimization algorithms for mapping data to distributed-memory multiprocessors, concentrating on irregular loosely synchronous problems. We also present a technique for efficient mapping of large data sets. The algorithms include a parallel genetic algorithm (PGA), a parallel neural network algorithm (PNN) and a parallel simulated annealing algorithm (PSA). An important feature of these algorithms is that they deviate from the operation of their sequential counterparts in order to achieve reasonable speed-ups and, yet, they maintain similar solution qualities. PGA has excellent speed-ups by virtue of the natural evolution model on which it is based. PSA and PNN include communication schemes adapted to the properties of the mapping problem and of the algorithms themselves for reducing the communication overhead. The performances of the three physical optimization algorithms are evaluated and compared, among themselves and with previous good algorithms, for a variety of test cases. They are found to produce high quality mapping solutions and do not show a bias towards particular problem configurations. However, they are slower than previous algorithms. Further, the comparison results show that the three algorithms are suitable for different requirements of mapping time and quality. PGA produces the best solutions, followed by PSA and then PNN. But, PNN is the fastest and PGA is the slowest. The technique proposed for large problems is based on a pre-mapping graph contraction heuristic algorithm, which results in a smaller search space. Graph contraction leads to remarkable reductions in mapping time, while maintaining good mapping qualities. It allows large-scale mapping to become efficient, especially when the physical optimization algorithms are used. |
| eu_rights_str_mv | openAccess |
| format | masterThesis |
| id | LAURepo_59ca2d17f2c4d90461d48314740bb206 |
| identifier_str_mv | Mansour, N. (1992). Physical optimization algorithms for mapping data to distributed-memory multiprocessors. |
| language_invalid_str_mv | en |
| network_acronym_str | LAURepo |
| network_name_str | Lebanese American University repository |
| oai_identifier_str | oai:laur.lau.edu.lb:10725/7959 |
| publishDate | 1992 |
| publisher.none.fl_str_mv | Syracuse University |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | Physical optimization algorithms for mapping data to distributed-memory multiprocessorsMansour, NashatComputer scienceArtificial intelligenceWe present three parallel physical optimization algorithms for mapping data to distributed-memory multiprocessors, concentrating on irregular loosely synchronous problems. We also present a technique for efficient mapping of large data sets. The algorithms include a parallel genetic algorithm (PGA), a parallel neural network algorithm (PNN) and a parallel simulated annealing algorithm (PSA). An important feature of these algorithms is that they deviate from the operation of their sequential counterparts in order to achieve reasonable speed-ups and, yet, they maintain similar solution qualities. PGA has excellent speed-ups by virtue of the natural evolution model on which it is based. PSA and PNN include communication schemes adapted to the properties of the mapping problem and of the algorithms themselves for reducing the communication overhead. The performances of the three physical optimization algorithms are evaluated and compared, among themselves and with previous good algorithms, for a variety of test cases. They are found to produce high quality mapping solutions and do not show a bias towards particular problem configurations. However, they are slower than previous algorithms. Further, the comparison results show that the three algorithms are suitable for different requirements of mapping time and quality. PGA produces the best solutions, followed by PSA and then PNN. But, PNN is the fastest and PGA is the slowest. The technique proposed for large problems is based on a pre-mapping graph contraction heuristic algorithm, which results in a smaller search space. Graph contraction leads to remarkable reductions in mapping time, while maintaining good mapping qualities. It allows large-scale mapping to become efficient, especially when the physical optimization algorithms are used.N/A169 p: illIncludes bibliographical referencesSyracuse University2018-05-30T11:47:30Z2018-05-30T11:47:30Z19922018-05-30Thesisinfo:eu-repo/semantics/publishedVersioninfo:eu-repo/semantics/masterThesishttp://hdl.handle.net/10725/7959Mansour, N. (1992). Physical optimization algorithms for mapping data to distributed-memory multiprocessors.http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.phphttps://dl.acm.org/citation.cfm?id=168972eninfo:eu-repo/semantics/openAccessoai:laur.lau.edu.lb:10725/79592021-03-19T10:43:14Z |
| spellingShingle | Physical optimization algorithms for mapping data to distributed-memory multiprocessors Mansour, Nashat Computer science Artificial intelligence |
| status_str | publishedVersion |
| title | Physical optimization algorithms for mapping data to distributed-memory multiprocessors |
| title_full | Physical optimization algorithms for mapping data to distributed-memory multiprocessors |
| title_fullStr | Physical optimization algorithms for mapping data to distributed-memory multiprocessors |
| title_full_unstemmed | Physical optimization algorithms for mapping data to distributed-memory multiprocessors |
| title_short | Physical optimization algorithms for mapping data to distributed-memory multiprocessors |
| title_sort | Physical optimization algorithms for mapping data to distributed-memory multiprocessors |
| topic | Computer science Artificial intelligence |
| url | http://hdl.handle.net/10725/7959 http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php https://dl.acm.org/citation.cfm?id=168972 |