臺灣博碩士論文加值系統

在需要高效能運算的應用程式中，all-to-all personalized communication是一個很重要的集體通訊模式。這個通訊模式是有規律的且能被有效率地實作在同質性叢集系統。然而，因為經濟的考量，在今日的高效能叢集運算環境中，異質性(heterogeneity)是常見的且處理器可能有著不同的運算和通訊能力，即使在同一個叢集中的處理器也是。
因此在異質環境中，為了達到好的通訊效率，一些新的演算法需要被提出。這篇論文主要討論在異質性叢集系統中的排程演算法且設計模擬器對這些排程演算法作一些實驗和觀察。對於all-to-all personalized communication和all-to-some communication而言，我們希望能夠
有效率的排程通訊事件(communication events)，使得這兩個通訊模式之通訊排程的完成時間越早越好。

All-to-all personalized communication is a very important collective communication pattern in high performance computing applications.The communication pattern is regular and can be efficiently implemented in a homogeneous cluster system. However, due to economical consideration, in today's high-performance cluster computing environments, heterogeneity is very common and processors could have very different computation and communication profile, even in the same
cluster. As a result new algorithms must be deployed in order to achieve good communication efficiency in heterogeneous environments.This paper discusses scheduling algorithms for Heterogeneous Networks of Workstations (so called HNOW) systems, and designs simulators to conduct experiments on them. We want to make communication events with all-to-all personalized and all-to-some communication efficiently
scheduled, and the final goal is to reduce the completion time of the communication schedule for heterogeneous networks of workstations.

1 Introduction 4
2 Problem Description 6
3 Algorithms 8
3.1 Matching-Based Algorithm ............................ 8
3.2 Greedy Algorithm .................................... 8
3.3 Open Shop Algorithm ................................. 9
3.4 Caterpillar Algorithm ............................... 9
3.5 Randomized Algorithms .............................. 10
4 Our Experimental Approach 13
4.1 Communication Model ................................. 13
4.1.1 Synchronous model ............................... 13
4.2 Implementation of the Simulators .................... 14
4.2.1 Schedule generation ............................. 14
4.2.2 Schedule simulation ............................. 15
5 Experimental Results and Observation 18
5.1 Experiment Guildlines ................................ 18
5.1.1 Synchronous all-to-all personalized communication 19
5.1.2 Asynchronous all-to-all personalized communication 21
5.1.3 Synchronous all-to-some communication ............ 22
5.1.4 Asynchronous all-to-some communication ........... 24
6 Conclusion 27

[1] T.Anderson, D. Culler, and D.Patterson.
A case for networks of workstations (now). In IEEE Micro,
pages 54-64, Feb 1995.
[2] P. B. Bhat, V. K. Prasanna and C. S. Raghavendra.
Adaptive communication algorithms for distributed
heterogeneous systems. In Proceedings of the 7th IEEE
Intnl. Symposium on High Performance Distributed Computing
(HPDC), 1998.
[3] http://www.cacr.caltech.edu/Publications/annreps/annrep95/
compsci4.html
[4] E. Lawler.Combinatorial Optimization: Networks and Matroids.
Holt and Rinehart and Winston, 1976.
[5] D.B. Shmoys, C. Stein and J. Wein.
Improved approximation algorithms for shop scheduling
problems. SIAM J. Comput., 23(3):617-632, June 1994.
[6] P. B. Bhat, V. K. Prasanna and C. S. Raghavendra.
Adaptive communication algorithms for distributed
heterogeneous systems. Manuscript, Dept. of EE-Systems,
University of Southern California, May 1998.
[7] P. Brucker. Scheduling Algorithms. Springer, 1995.
[8] T. Gonzalez and S. Sahni. Open shop scheduling
to minimize finish time. Journal of the ACM, 23(4):
665-679, Oct. 1976.
[9] L.H. Jamielson, P.T. Mueller and H.J. Siegel.
FFT algorithms for SIMD parallel processing systems.
Journal of Parallel and Distributed Computing, 3(1):
48-71, March 1986.
[10] R. Libeskind-Hadas and J. Hartline.
Efficient multicast in heterogeneous networks of
workstations. In Proceedings of 2000 International
Workshop on Parallel Processing, 2000.
[11] M. Banikazemi, J. Sampathkumar, S. Prabhu, D. Panda and
P. Sadayappan. Communication modeling of heterogeneous
networks of workstations for performance characterization
of collective operations. In Proceedings of International
Workshop on Heterogeneous Computing, 1999.