For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Scheduling for Gather Operation in Heterogeneous Parallel Computing Environments
Fukuhito OOSHITA Susumu MATSUMAE Toshimitsu MASUZAWA
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2003/04/01
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Algorithms and Data Structures
heterogeneous parallel computing environment, gather operation, collective communication operation, scheduling algorithm,
Full Text: PDF(316.4KB)>>
A heterogeneous parallel computing environment consisting of different types of workstations and communication links plays an important role in parallel computing. In many applications on the system, collective communication operations are commonly used as communication primitives. Thus, design of the efficient collective communication operations is the key to achieve high-performance parallel computing. But the heterogeneity of the system complicates the design. In this paper, we consider design of an efficient gather operation, one of the most important collective operations. We show that an optimal gather schedule is found in O(n2k-1) time for the heterogeneous parallel computing environment with n processors of k distinct types, and that a nearly-optimal schedule is found in O(n) time if k=2.