An Approximation Algorithm for Synchronous Broadcast in Heterogeneous Environments
Date Issued
2006
Date
2006
Author(s)
Chang, Juih-Sien
DOI
en-US
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 PC or workstation cluster that provides high computing power within a limited budget. However, a cluster may consist of different types of processors and this heterogeneity within a cluster complicates the design of efficient collective communication protocols.
This paper introduces a synchronous communication model where the communication cost is deter-mined by both sender and receiver. In this synchronous model both sender and receiver of a message must wait until the current communication finishes. Although this synchronous broadcast scheduling problem is NP-hard, we propose a greedy algorithm with a competitive ratio 3. The time complexity of the greedy algorithm is bounded by O(n log n) where n is the number of processors.
Subjects
廣播排程
異質環境
同步
Broadcast Schedule
Heterogeneous Environment
Synchronous
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-95-R93922098-1.pdf
Size
23.31 KB
Format
Adobe PDF
Checksum
(MD5):661da9ac763ee4e7686c2cbab7357fc3