Abstract
The performance of parallel computing systems using the master/worker model for distributed grid computing tends to be degraded when large data sets have to be dealt with, due to the impact of data transmission time. In our previous study, we proposed a parallel transferable uniform multi-round algorithm (PTUMR), which efficiently mitigated this impact by allowing chunks to be transmitted in parallel to workers in environments that were homogeneous in terms of workers’ computation and communication capacities. The proposed algorithm outperformed the uniform multi-round algorithm (UMR) in terms of application turnaround time, but it could not be directly adapted to heterogeneous environments. In this paper, therefore, we propose an extended version of PTUMR suitable for heterogeneous environments. This algorithm divides workers into appropriate groups based on both computation and communication capacities of individual workers, and then treats each group of workers as one virtual worker. The new PTUMR algorithm is shown through performance evaluations to significantly mitigate the adverse effects of data transmission time between master and workers compared with UMR, achieving turnaround times close to the theoretical lower limits even in heterogeneous environments.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Foster, I., Kesselman, C.: The GRID Blueprint for a New Computing Infrastructure. Morgan Kaufmann Publishers, San Francisco (1998)
Foster, I., Kesselman, C., Tuecke, S.: The Anatomy of the Grid. International Journal of Supercomputer Applications 15(3), 200–222 (2001)
Bharadwaj, V., Ghose, D., Mani, V., Robertazzi, T.G.: Scheduling Divisible Loads in Parallel and Distributed Systems. IEEE Computer Society Press, Los Alamitos (1996)
Robertazzi, T.G.: Ten Reasons to Use Divisible Load Theory. Journal of IEEE Computer 36(5), 63–68 (2003)
Gerogiannis, D., Orphanoudakis, S.C.: Load Balancing Requirements in Parallel Implementations of Image Feature Extraction Tasks. IEEE Trans. Parallel and Distributed Systems 4(9), 994–1013 (1993)
Yang, Y., Casanova, H.: UMR: A Multi-Round Algorithm for Scheduling Divisible Workloads. In: Proc. of International Parallel and Distributed Processing Symposium (IPDPS 2003), Nice, France (April 2003)
Yang, Y., Casanova, H.: A Multi-Round Algorithm for Scheduling Divisible Workload Applications: Analysis and Experimental Evaluation. Technical Report of Dept. of Computer Science and Engineering, University of California CS20020721 (2002)
Beaumont, O., Legrand, A., Robert, Y.: Optimal Algorithms for Scheduling Divisible Workloads on Heterogeneous Systems. In: Proc. of International Parallel and Distributed Processing Symposium (IPDPS 2003), Nice, France (April 2003)
Cyril, C., Beaumont, O., Legrand, A., Robert, Y.: Scheduling Strategies for Master-Slave Tasking on Heterogeneous Processor Grids. Technical Report 2002-12, LIP (March 2002)
Rosenberg, A.L.: Sharing Partitionable Workloads in Heterogeneous NOWs: Greedier Is Not Better. In: Proc. of the 3rd IEEE International Conference on Cluster Computing (Cluster 2001), California, USA, pp. 124–131 (October 2001)
Yamamoto, H., Tsuru, M., Oie, Y.: Parallel Transferable Uniform Multi-Round Algorithm for Achieving Minimum Application Turnaround Times for Divisible Workload. In: Yang, L.T., Rana, O.F., Di Martino, B., Dongarra, J. (eds.) HPCC 2005. LNCS, vol. 3726, pp. 817–828. Springer, Heidelberg (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Yamamoto, H., Tsuru, M., Oie, Y. (2006). A Parallel Transferable Uniform Multi-Round Algorithm in Heterogeneous Distributed Computing Environment. In: Gerndt, M., Kranzlmüller, D. (eds) High Performance Computing and Communications. HPCC 2006. Lecture Notes in Computer Science, vol 4208. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11847366_6
Download citation
DOI: https://doi.org/10.1007/11847366_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-39368-9
Online ISBN: 978-3-540-39372-6
eBook Packages: Computer ScienceComputer Science (R0)