Abstract
One of the distinct characteristics of computing platforms shared by multiple users such as a computational grid is heterogeneity on each computer and/or among computers. Temporal heterogeneity refers to variation, along the time dimension, of computing power (or communication bandwidth) available for a task on a computer, and spatial heterogeneity represents the variation among computers. In minimizing the average parallel execution time of a target task on a spatially heterogeneous computing system, it is not optimal to distribute the target task linearly proportional to the average computing powers available on computers. In this study, based on a theoretical model of heterogeneous computing environment, an approach to load balancing for minimizing the average parallel execution time of a target task is discussed. The approach of which validity has been verified through simulation considers temporal and spatial heterogeneities in addition to the average computing power on each computer.
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
R. Buyya, “High Performance Cluster Computing,” Prentice Hall, 1999.
Ian Foster and Carl Kesselman (ed.), “The Grid: Blueprint for a New Computing Infrastructure,” Morgan Kaufmann, 1998.
R.F. Freund and H. J. Siegel “Heterogeneous Processing”, Computer, vol. 26, no.6, pp13–17, June 1993.
S. Ali, H. Siegel, M. Maheswaran, D. Hensgen and S. Ali, “Task Execution Time Modeling for Heterogeneous Computing Systems,” IEEE 9th Heterogeneous Computing Workshop, pp185–199, May 2000.
C.-Z. Xu, L. Y. Wang, and N.-T. Fong, “Stochastic Prediction of Execution Time for Dynamic Bulk Synchronous Computations,” Proceedings of International Parallel and Distributed Processing Symposium, San Francisco, April 2001.
Atakan Dogon and Fusun Ozguner, “Trading off Execution Time for Reliability in Scheduling Precedence-Constrained Tasks in Heterogeneous Computing,” Proceedings of International Parallel and Distributed Processing Symposium, San Francisco, April 2001.
J. Schopf and F. Berman, “Stochastic Scheduling,” CS Dept. Technical Report, #CS-99-03, University of California, San Diego.
X. Zhang and Y. Yan, “Modeling and Characterizing Parallel Computing Performance On Heterogeneous Networks of Workstations”, Proc. Seventh IEEE Symp. Parallel and Distributed Processing, pp25–34, October 1995.
M. Maheswaran and H. Siegel, “A Dynamic Matching and Scheduling Algorithm for Heterogeneous Computing Systems”, Proc. Heterogeneous Computing’ 98, pp57–69, 1998.
T. Thanalapati and S. Dandamudi, “An Efficient Adaptive Scheduling Scheme for Distributed Memory Multicomputers,” IEEE Transactions on Parallel and Distributed Systems, vol. 12, no. 7, pp758–768, July 2001.
Y. Zhang, A. Sivasubrmaniam, J. Moreira and H. Franke, “Impact of Workload and System Parameters on Next Generation Cluster Scheduling Mechanisms,” IEEE Transactions on Parallel and Distributed Systems, vol. 12, no. 9, pp967–985, September 2001.
J. Huang and S.-Y. Lee, “Effects of Spatial and Temporal Heterogeneity on Performance of a Target Task in Heterogeneous Computing Environments,” to be presented at the 15th ISCA International Conference on Parallel and Distributed Computing Systems, September 19–21, 2002.
H. David, “Order Statistics,” John Wiley and Sons Inc., 1970.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lee, SY., Huang, J. (2002). A Theoretical Approach to Load Balancing of a Target Task in a Temporally and Spatially Heterogeneous Grid Computing Environment. In: Parashar, M. (eds) Grid Computing — GRID 2002. GRID 2002. Lecture Notes in Computer Science, vol 2536. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36133-2_7
Download citation
DOI: https://doi.org/10.1007/3-540-36133-2_7
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00133-1
Online ISBN: 978-3-540-36133-6
eBook Packages: Springer Book Archive