https://scholars.lib.ntu.edu.tw/handle/123456789/118332
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.author | PANGFENG LIU | en |
dc.contributor.author | Kuo, May-Chen | en |
dc.contributor.author | Wang, Da-Wei | en |
dc.creator | Liu, Pangfeng; Kuo, May-Chen; Wang, Da-Wei | - |
dc.date | 2009 | en |
dc.date.accessioned | 2009-05-06T05:22:59Z | - |
dc.date.accessioned | 2018-07-05T01:55:31Z | - |
dc.date.available | 2009-05-06T05:22:59Z | - |
dc.date.available | 2018-07-05T01:55:31Z | - |
dc.date.issued | 2009 | - |
dc.identifier.issn | 01784617 | - |
dc.identifier.uri | http://ntur.lib.ntu.edu.tw//handle/246246/155143 | - |
dc.identifier.uri | https://www.scopus.com/inward/record.uri?eid=2-s2.0-61349149361&doi=10.1007%2fs00453-007-9113-7&partnerID=40&md5=b4693bf7f3963f6af2d4a6a3012fd5a4 | - |
dc.description.abstract | Network of workstation (NOW) is a cost-effective alternative to massively parallel supercomputers. As commercially available off-the-shelf processors become cheaper and faster, it is now possible to build a cluster that provides high computing power within a limited budget. However, a cluster may consist of different types of processors and this heterogeneity complicates the design of efficient collective communication protocols. For example, it is a very hard combinatorial problem to find an optimal reduction schedule for such heterogeneous clusters. Nevertheless, we show that a simple technique called slowest-node-first (SNF) is very effective in designing efficient reduction protocols for heterogeneous clusters. First, we show that SNF is actually a 2-approximation algorithm, which means that an SNF schedule length is always within twice of the optimal schedule length, no matter what kind of cluster is given. In addition, we show that SNF does give the optimal reduction time when the cluster consists of two types of processors, when the ratio of communication speed between them is at least two. When the communication speed ratio is less than two, we develop a dynamic programming technique to find the optimal schedule. Our dynamic programming utilizes the monotone property of the objective function, and can significantly reduce the amount of computation time. Finally, combined with an approximation algorithm for broadcast 2004, we propose an all-reduction algorithm which sends the reduction answer to all processors, with approximation ratio 3.5. We conduct three groups of experiments. First, we show that SNF performs better than the built-in MPI-Reduce in a test cluster. Second, we observe a factor of 93 times saving in computation time to find the optimal schedule, when compared with a naive dynamic programming implementation. Thirdly, we apply the theoretical results to a branch-and-bound search and show that they can reduce the search time of the optimal reduction schedule by a factor of 500, when the cluster has three kinds of processors. © 2007 Springer Science+Business Media, LLC. | - |
dc.format | application/pdf | en |
dc.format.extent | 602999 bytes | - |
dc.format.mimetype | application/pdf | - |
dc.language | en | en |
dc.language.iso | en_US | - |
dc.relation.ispartof | Algorithmica (New York) | en_US |
dc.subject | Branch-and-bound search; Dynamic programming; Heterogeneous workstation cluster; Reduction protocol; Scheduling optimization; Slowest-node-first heuristic | - |
dc.subject.other | Approximation ratios; Branch-and-bound search; Collective communications; Combinatorial problems; Communication speed; Computation time; Computing power; Dynamic programming techniques; Heterogeneous clusters; Heterogeneous environments; Heterogeneous workstation cluster; Monotone properties; Network of workstations; Objective functions; Optimal reductions; Optimal schedules; Parallel supercomputers; Reduction algorithms; Schedule lengths; Scheduling optimization; Search time; Slowest-node-first heuristic; Theoretical results; Approximation algorithms; Communication; Heuristic methods; Optimization; Scheduling; Scheduling algorithms; Supercomputers; Systems engineering; Dynamic programming | - |
dc.title | An Approximation Algorithm and Dynamic Programming for Reduction in Heterogeneous Environments | en |
dc.type | journal article | en |
dc.identifier.doi | 10.1007/s00453-007-9113-7 | - |
dc.identifier.scopus | 2-s2.0-61349149361 | - |
dc.relation.pages | 425-453 | - |
dc.relation.journalvolume | 53 | - |
dc.relation.journalissue | 3 | - |
dc.identifier.uri.fulltext | http://ntur.lib.ntu.edu.tw/bitstream/246246/155143/1/15.pdf | - |
item.fulltext | with fulltext | - |
item.openairetype | journal article | - |
item.languageiso639-1 | en_US | - |
item.openairecristype | http://purl.org/coar/resource_type/c_6501 | - |
item.grantfulltext | open | - |
item.cerifentitytype | Publications | - |
crisitem.author.dept | Networking and Multimedia | - |
crisitem.author.dept | Computer Science and Information Engineering | - |
crisitem.author.orcid | 0000-0002-5466-9960 | - |
crisitem.author.parentorg | College of Electrical Engineering and Computer Science | - |
crisitem.author.parentorg | College of Electrical Engineering and Computer Science | - |
顯示於: | 資訊工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。