An Asynchronous Algorithm for Balancing Unpredictable Workload on Distributed-Memory Machines

ETRI Journal

关键词: Task Migration;    Load Balancing;    Unpredictable Workload;    Distributed-Memory Machine;   

Others  :  1184116
DOI  :  10.4218/etrij.98.0198.0403

【 摘 要 】

It is challenging to parallelize problems with irregular computation and communication. In this paper, we propose an asynchronous algorithm for balancing unpredictable workload on distributed-memory machines. By using an initial workload estimate, we firs

   

【 参考文献 】

• [1]S. Ranka, Proc. of Workshop on Solving Irregular Problems on Distributed-Memory Machines, IPPS'96, 1996.
• [2]A. Ferreira and J. Rolim, Proc. of Workshop on Parallel Algorithms for Irregularly Structured Problems, Irregular'96, 1996.
• [3]A. Ferreira and J. Rolim, Proc. of Workshop on Solving Irregularly Structured Problems in Parallel, Irregular'97, 1997.
• [4]C.-L. Wang, P.B. Bhat and V.K. Präs Anna, "High-performance computing for vision," Proceedings of the IEEE, vol. 84, no. 7, 1996, pp. 931-946.
• [5]A. Huertas, C. Lin and R. Nevatia, "Detection of Buildings from Monocular Views of Aerial Scenes Using Perceptual Grouping and Shadows," Proc. of Image Understanding Workshop, 1993, pp. 253-260.
• [6]Gerard Medioni and Ramakant Nevatia, "MATCHING IMAGES USING LINEAR FEATURES," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. PAMI-6, no. 6, 1984, pp. 675-685.
• [7]V. Prasanna and C. Wang, "Scalable Parallel Implementations of Perceptual Grouping on Connection Machine CM-5," Pmc. of International Conference on Pattern Recognition, 1994, pp. 229-233.
• [8]D. Bader and J. Jaja, "Practical Parallel Algorithms for Dynamic Data Redistribution, Median Finding, and Selection," Proc. of International Parallel Processing Symposium, 1996, pp. 292-301.
• [9]A.N. Choudhary, B. Narahari and R. Krishnamurti, "An efficient heuristic scheme for dynamic remapping of parallel computations," Parallel Computing, vol. 19, no. 6, 1993, pp. 621-632.
• [10]Nikos Chrisochoides, Nashat Mansour and Geoffrey Fox, "Performance evaluation of load balancing algorithms for parallel single-phase iterative PDE solvers," Proceedings of the Scalable High-Performance Computing Conference, 1994, pp. 764-772.
• [11]I. Foster and B. Toonen, "Load Balancing Algorithms for the Parallel Community Climate Model," Proc. of Scalable High-Performance Computing Conference, 1994.
• [12]Dimitris Gerogiannis and Stelios C. Orphanoudakis, "Load balancing requirements in parallel implementations of image feature extraction tasks," IEEE Transactions on Parallel and Distributed Systems, vol. 4, no. 9, 1993, pp. 994-1013.
• [13]Brian Van Voorst, Rakesh Jha, Luiz Pires and Mustafa Muhammad, "Implementation and results of hypothesis testing from the C3I parallel benchmark suite," Proceedings of the International Parallel Processing Symposium, IPPS, 1997, pp. 192-196.
• [14]R. Blumofe, C. Joerg, B. Kuszmaul, C. Leiserson, K. Randall and Y. Zhou, "Cilk: An Efficient Multithreaded Runtime System," Proc. of Symposium on Principles and Practice of Parallel Programming, 1995.
• [15]C. Wen, S. Chakrabarti, E. Deprit, A. Krishnamurthy and K. Yelick, "Runtime Support for Portable Distributed Data Structures," Proc. of Workshop on Languages, Compilers, and Runtime Systems for Scalable Computers, 1995, pp. 111-120.
• [16]C. Wen, S. Chakrabarti, E. Deprit, A. Krishnamurthy and K. Yelick, "Runtime Support for Portable Distributed Data Structures," Proc. of Workshop on Languages, Compilers, and Runtime Systems for Scalable Computers, 1995, pp. 111-120.
• [17]Cray T3D System Architecture Overview, 1993.