https://scholars.lib.ntu.edu.tw/handle/123456789/118332
標題: | An Approximation Algorithm and Dynamic Programming for Reduction in Heterogeneous Environments | 作者: | PANGFENG LIU Kuo, May-Chen Wang, Da-Wei |
關鍵字: | Branch-and-bound search; Dynamic programming; Heterogeneous workstation cluster; Reduction protocol; Scheduling optimization; Slowest-node-first heuristic | 公開日期: | 2009 | 卷: | 53 | 期: | 3 | 起(迄)頁: | 425-453 | 來源出版物: | Algorithmica (New York) | 摘要: | 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. |
URI: | http://ntur.lib.ntu.edu.tw//handle/246246/155143 https://www.scopus.com/inward/record.uri?eid=2-s2.0-61349149361&doi=10.1007%2fs00453-007-9113-7&partnerID=40&md5=b4693bf7f3963f6af2d4a6a3012fd5a4 |
ISSN: | 01784617 | DOI: | 10.1007/s00453-007-9113-7 | SDG/關鍵字: | 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 |
顯示於: | 資訊工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。