A model for the automatic mapping of tasks to processors in heterogeneous multi-cluster architectures

Authors

  • Laura Cristina De Giusti School of Computer Science, UNLP, Argentina
  • Franco Chichizola School of Computer Science, UNLP, Argentina
  • Marcelo Naiouf School of Computer Science, UNLP, Argentina
  • Ana Ripoll Computer and Operating Systems Architecture Departament, Universidad Autónoma de Barcelona, Barcelona, Spain
  • Armando Eduardo De Giusti School of Computer Science, UNLP, Argentina

Keywords:

Parallel Systems, Cluster and Multi-Cluster Architectures, Performance Prediction Models, Mapping of Tasks to Processors, Homogeneous and Heterogeneous Processors

Abstract

This paper discusses automatic mapping methods for concurrent tasks to processors applying graph analysis for the relation among tasks, in which processing and communicating times are incorporated. Starting by an analysis in which processors are homogeneous and data transmission times do not depend on the processors that are communicating (a typical case in homogeneous clusters), we progress to extend the model to heterogeneous processors having the possibility of different communication levels, applicable to a multicluster. Some results obtained with the model and future work lines are presented, particularly, the possibility of obtaining the required optimal number of processors, keeping a constant efficiency level.

Downloads

Download data is not yet available.

References

[1] Grama A., Gupta A., Karypis G., Kumar V., "An Introduction to Parallel Computing. Design and Analysis of Algorithms", Pearson Addison Wesley, 2nd Edition, 2003
[2] Leopold C., "Parallel and Distributed Computing. A survey of Models, Paradigms, and Approaches", Wiley Series on Parallel and Distributed Computing. Albert Zomaya Series Editor, 2001
[3] A.V. Aho, J.E. Hopcroft, and J.D. Ullman.The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Massachusetts, 1974
[4] S. Akl, “Parallel Computation. Models and Methods”, Prentice-Hall, Inc., 1997.
[5] M. J. Flynn, Computer Architecture: Pipelined and Parallel Processor Design. Jones and Bartlett, 1995
[6] Baker M., R. Buyya. "Cluster Computing at a Glance". R. Buyya Ed., High Performance Cluster Computing: Architectures and Systems, Vol. 1, Prentice-Hall, Upper Saddle River, NJ, USA,pp.3-47,1999.
[7] Zoltan Juhasz (Editor), Peter Kacsuk (Editor), Dieter Kranzlmuller (Editor), Distributed and Parallel Systems : Cluster and Grid Computing (The International Series in Engineering and Computer Science). Springer; 1 edition (September 21, 2004).
[8] D. Culler, R. Karp, D. Patterson, A. Sahay, K. E. Schauser, E. Santos, R. Suramonian and T. von Eicken, “LogP: Towards a Realistic Model of Parallel Computation}", SIGPLAN Notices (USA), vol 28 N° 7, pp 1-12, 1993.
[9]C. Roig, “Algoritmos de asignación basados en un nuevo modelo de representación de programas paralelos”, Tesis Doctoral, Universidad Autónoma de Barcelona, 2002.
[10] Valiant L.G.. A Bridging Model for Parallel Computation. Communications of the ACM, 33(8): 103-111, August 1990.
[11] A. Kalinov, S. Klimov. Optimal Mapping of a Parallel Application Processes onto Heterogeneous Platform. Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS’05), April 2005
[12] J. Cuenca, D. Gimenez, and J. Martinez, “Heuristics for Work Distribution of a Homogeneous Parallel Dynamic Programming Scheme on Heterogeneous Systems”, Procss of the 3rd International Workshop on Algorithms, Models and Tools for Parallel Computing on Heterogeneous Networks (HeteroPar’04), July 5-8, 2004 Cork, Ireland, IEEE CS Press.
[13] Y. Kishimoto and S. Ichikawa, “An Execution-Time Estimation Model for Heterogeneous Clusters”, Proceedings of the 18th International Parallel and Distributed Processing Symposium (IPDPS 2004), 26-30 April 2004, Santa Fe, New Mexico, USA, CDROM/Abstracts Proceedings, IEEE Computer Society 2004.
[14] M. Garey and D. Johnson. Computers and Intractability. W.H. Freeman and Co. S. Francisco, 1979.

Downloads

Published

2007-03-01

How to Cite

De Giusti, L. C., Chichizola, F., Naiouf, M., Ripoll, A., & De Giusti, A. E. (2007). A model for the automatic mapping of tasks to processors in heterogeneous multi-cluster architectures. Journal of Computer Science and Technology, 7(01), p. 39–44. Retrieved from https://journal.info.unlp.edu.ar/JCST/article/view/801

Issue

Section

Original Articles

Most read articles by the same author(s)

1 2 3 4 > >>