Virtual topologies for massively parallel computations. (c2015)
In their essence, recursive search tree algorithms are nothing but mere enumeration of the solution space. Most of the time is spent generating new search tree nodes with very little computation performed at each tree node. Massively parallel computations that are based on such algorithms often suff...
محفوظ في:
| المؤلف الرئيسي: | |
|---|---|
| التنسيق: | masterThesis |
| منشور في: |
2015
|
| الموضوعات: | |
| الوصول للمادة أونلاين: | http://hdl.handle.net/10725/2122 https://doi.org/10.26756/th.2015.13 |
| الوسوم: |
إضافة وسم
لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!
|
| _version_ | 1864513457406083072 |
|---|---|
| author | Jahed, Karim A. |
| author_facet | Jahed, Karim A. |
| author_role | author |
| dc.creator.none.fl_str_mv | Jahed, Karim A. |
| dc.date.none.fl_str_mv | 2015-09-09T05:55:58Z 2015-09-09T05:55:58Z 2015 2015-09-09 2015-05-28 |
| dc.identifier.none.fl_str_mv | http://hdl.handle.net/10725/2122 https://doi.org/10.26756/th.2015.13 |
| dc.language.none.fl_str_mv | en |
| dc.publisher.none.fl_str_mv | Lebanese American University |
| dc.rights.*.fl_str_mv | info:eu-repo/semantics/openAccess |
| dc.subject.none.fl_str_mv | Virtual computer systems Electric network topology Parallel processing (Electronic computers) Lebanese American University -- Dissertations Dissertations, Academic |
| dc.title.none.fl_str_mv | Virtual topologies for massively parallel computations. (c2015) a case study |
| dc.type.none.fl_str_mv | Thesis info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/masterThesis |
| description | In their essence, recursive search tree algorithms are nothing but mere enumeration of the solution space. Most of the time is spent generating new search tree nodes with very little computation performed at each tree node. Massively parallel computations that are based on such algorithms often suffer from a large communication overhead due to the exponential growth in the number of tasks generated at each search-tree level. Cores would spend computation time generating and exchanging tasks rather than traversing the search tree. This communication overhead will only increase as we scale-up the computation, up to the point where adding new cores negatively affects the computational time. To address this issue, we propose virtual topologies: an architecture-oblivious communication graph imposed on top of the physical network to limit and manage core-to-core communication. Using the Cluster Editing problem as a case study, we show that managed cooperation, coupled with an efficient task generation and load balancing strategy, is capable of dramatically reducing the communication overhead and improving the computational throughput. |
| eu_rights_str_mv | openAccess |
| format | masterThesis |
| id | LAURepo_01ba1f207489ee4da3c46fc2933c216c |
| 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/2122 |
| publishDate | 2015 |
| publisher.none.fl_str_mv | Lebanese American University |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | Virtual topologies for massively parallel computations. (c2015)a case studyJahed, Karim A.Virtual computer systemsElectric network topologyParallel processing (Electronic computers)Lebanese American University -- DissertationsDissertations, AcademicIn their essence, recursive search tree algorithms are nothing but mere enumeration of the solution space. Most of the time is spent generating new search tree nodes with very little computation performed at each tree node. Massively parallel computations that are based on such algorithms often suffer from a large communication overhead due to the exponential growth in the number of tasks generated at each search-tree level. Cores would spend computation time generating and exchanging tasks rather than traversing the search tree. This communication overhead will only increase as we scale-up the computation, up to the point where adding new cores negatively affects the computational time. To address this issue, we propose virtual topologies: an architecture-oblivious communication graph imposed on top of the physical network to limit and manage core-to-core communication. Using the Cluster Editing problem as a case study, we show that managed cooperation, coupled with an efficient task generation and load balancing strategy, is capable of dramatically reducing the communication overhead and improving the computational throughput.N/A1 hard copy: x, 42 leaves; col. ill.; 31 cm. avaiable at RNL.Bibliography: leaves 40-42.Lebanese American University2015-09-09T05:55:58Z2015-09-09T05:55:58Z20152015-09-092015-05-28Thesisinfo:eu-repo/semantics/publishedVersioninfo:eu-repo/semantics/masterThesishttp://hdl.handle.net/10725/2122https://doi.org/10.26756/th.2015.13eninfo:eu-repo/semantics/openAccessoai:laur.lau.edu.lb:10725/21222020-11-20T08:43:22Z |
| spellingShingle | Virtual topologies for massively parallel computations. (c2015) Jahed, Karim A. Virtual computer systems Electric network topology Parallel processing (Electronic computers) Lebanese American University -- Dissertations Dissertations, Academic |
| status_str | publishedVersion |
| title | Virtual topologies for massively parallel computations. (c2015) |
| title_full | Virtual topologies for massively parallel computations. (c2015) |
| title_fullStr | Virtual topologies for massively parallel computations. (c2015) |
| title_full_unstemmed | Virtual topologies for massively parallel computations. (c2015) |
| title_short | Virtual topologies for massively parallel computations. (c2015) |
| title_sort | Virtual topologies for massively parallel computations. (c2015) |
| topic | Virtual computer systems Electric network topology Parallel processing (Electronic computers) Lebanese American University -- Dissertations Dissertations, Academic |
| url | http://hdl.handle.net/10725/2122 https://doi.org/10.26756/th.2015.13 |