A METHODOLOGY FOR ADAPTIVE RESOLUTION OF NUMERICAL PROBLEMS ON HETEROGENEOUS HIERARCHICAL CLUSTERS

Wahid Nasri, Sonia Mahjoub, Slim Bouguerra

2006

Abstract

Solving a target problem by using a single algorithm or writing portable programs that perform well is not always efficient on any parallel environment due to the increasing diversity of existing computational supports where new characteristics are influencing the execution of parallel applications. The inherent heterogeneity and the diversity of networks of such environments represent a great challenge to efficiently implement parallel applications for high performance computing. Our objective within this work is to propose a generic framework based on adaptive techniques for solving a class of numerical problems on cluster-based heterogeneous hierarchical platforms. Toward this goal, we refer to adaptive approaches to better adapt a given application to a target parallel system. We apply this methodology on a basic numerical problem, namely solving the matrix multiplication problem, while determining an adaptive execution scheme minimizing the overall execution time depending on the problem and architecture parameters.

References

  1. Barchet-Estefanel, L. A. and Mounié, G., 2004, Identifying Logical Homogeneous Clusters for Efficient Wide-area Communications, In Proceedings of the Euro PVM/MPI, 2004.
  2. Beaumont, O., Boudet, V., Rastello, F. and Robert, Y., 2001, Matrix Multiplication on Heterogeneous Platforms, IEEE Transactions on Parallel and Distributed Systems, 12 (10), 2001.
  3. Blumofe, R. D. and Leiserson, C. E., 1998, SpaceEfficient Scheduling of Multithreaded Computations, SIAM Journal on Computing, 27(1), 1998.
  4. Bosilca, G., Chen, Z., Dongarra, J., Eijkhout, V., Fagg, G. E., Fuentes, E., Langou, J., Luszczek, P., PjesivacGrbovic, J., Seymour, K., You, H. and Vadhiyar, S. S., 2005, Self Adapting Numerical Software (SANS) Effort, IBM Journal of Research and Development, 2005.
  5. Capello, F., Fraigniaud, P., Mans, B. and Rosenberg, A. L., 2005, An Algorithmic Model for Heterogeneous Hyper-Clusters: Rationale and Experience, International Journal of Foundations of Computer Science 16(2), 195-215, 2005.
  6. Chen, Z., Dongarra, J., Luszczek, P. and Roche, K., 2003, Self Adapting Software for Numerical Linear Algebra and Lapack for Clusters, Parallel Computing, 2003.
  7. Daoudi, E. M., Gautier, T., Kerfali, A., Revire, R. and Roch, J.-L., 2005, Algorithmes parallèles à grain adaptatif et applications, Techniques et Sciences Informatiques, Hermès, 2005.
  8. Desprez, F. and Suter, F., 2004, Impact of mixedparallelism on parallel implementations of the Strassen and Winograd matrix multiplication algorithms, Concurrency and computation : practice and experience, 16, 2004.
  9. Dutot, P. -F., Mounié, G. and Trystram, D., 2004, Scheduling Parallel Tasks - Approximation Algorithms, chapter 26 of the handbook of scheduling, edited by Joseph Y-T. Leung, 2004.
  10. Eskenazi, E. M., Fioukov, A. V., Hammer, D. K., Obbink, H. and Pronk, B., 2004, Analysis and Prediction of Performance for Evolving Architectures, In Proceedings of the 30th EUROMICRO Conference (EUROMICRO'04), 2004.
  11. Frigo, M. and Johnson, S., 1998, FFTW : an adaptive software architecture for the Fast Fourier Transform, In Proceedings of ICASSP, 1998.
  12. Hartmann, O., Kuhnemann, M., Rauber, T. and Runger, G., 2006, Adaptive Selection of Communication Methods to Optimize Collective MPI Operations, In Proceedings of the 12th Workshop on Compilers for Parallel Computers (CPC'06), 2006.
  13. Hong, B. and Prasanna, V. K., 2002, Adaptive Matrix Multiplication in Heterogeneous Environments, In Proceedings of the 9th International Conference on Parallel and Distributed Systems (ICPADS'02), 2002.
  14. Hunold, S., Rauber, T. and Runger, G., 2004, Multilevel Hierarchical Matrix Multiplication on Clusters, In Proceedings of the 18th International Conference on Supercomputing, 2004.
  15. Lastovetsky, A. and Reddy, R., 2004, On performance analysis of heterogeneous parallel algorithms, Parallel Computing, 30, 2004.
  16. Li, J., 1996, A poly-algorithm for parallel dense matrix multiplication on two dimensional process grid topologies, PhD Thesis, University of Mississippi, 1996.
  17. Lowekamp, B. B. and Beguelin, A., 1996, ECO: Efficient Collective Operations for Communication on Heterogeneous Networks, In Proceedings of the 10th International Parallel Processing Symposium, 1996.
  18. McCracken, M. O., Snavely, A. and Malony, A. D., 2003, Performance Modeling for Dynamic Algorithm Selection, International Conference on Computational Science, 2003.
  19. Nasri, W., Trystram, D. and Achour, S., 2006, Adaptive Algorithms for the Parallelization of the Dense Matrix Multiplication on Clusters, International Journal of Computational Science and Engineering, to appear, 2006.
  20. Ngoko, Y., 2005, Poly-algorithmes pour une programmation efficace des problèmes numériques. Exemple du produit de matrices, Master Thesis, University of Yaoundé I, 2005.
  21. Ohtaki, Y., Takahashi, D., Boku, T. and Sato, M., 2004, Parallel Implementation of Strassen's Matrix Multiplication Algorithm for Heterogeneous Clusters, IPDPS'04, 2004.
  22. Roche, K. J. and Dongarra, J. J., 2002, Deploying parallel numerical library routines to cluster computing in a self adapting fashion, Parallel Computing, Advances and Current Issues, 2002.
  23. Thomas, N., Tanase, G., Tkachyshyn, O., Perdue, J., Amato, N. M. and Rauchwerger L., 2005, A Framework for Adaptive Algorithm Selection in STAPL, In Proceedings of PPoPP'05, 2005.
  24. Whaley, R. C., Petitet, A. and Dongarra, J. J., 2001, Automated empirical optimizations of software and the ATLAS project, Parallel Computing, 27, 2001.
  25. Wolski, R., Spring, N. and Peterson, C., 1997, Implementing a Performance Forecasting System for Metacomputing : The Network Weather Service, In Supercomputing, 1997.
Download


Paper Citation


in Harvard Style

Nasri W., Mahjoub S. and Bouguerra S. (2006). A METHODOLOGY FOR ADAPTIVE RESOLUTION OF NUMERICAL PROBLEMS ON HETEROGENEOUS HIERARCHICAL CLUSTERS . In Proceedings of the First International Conference on Software and Data Technologies - Volume 1: ICSOFT, ISBN 978-972-8865-69-6, pages 345-350. DOI: 10.5220/0001314103450350


in Bibtex Style

@conference{icsoft06,
author={Wahid Nasri and Sonia Mahjoub and Slim Bouguerra},
title={A METHODOLOGY FOR ADAPTIVE RESOLUTION OF NUMERICAL PROBLEMS ON HETEROGENEOUS HIERARCHICAL CLUSTERS},
booktitle={Proceedings of the First International Conference on Software and Data Technologies - Volume 1: ICSOFT,},
year={2006},
pages={345-350},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0001314103450350},
isbn={978-972-8865-69-6},
}


in EndNote Style

TY - CONF
JO - Proceedings of the First International Conference on Software and Data Technologies - Volume 1: ICSOFT,
TI - A METHODOLOGY FOR ADAPTIVE RESOLUTION OF NUMERICAL PROBLEMS ON HETEROGENEOUS HIERARCHICAL CLUSTERS
SN - 978-972-8865-69-6
AU - Nasri W.
AU - Mahjoub S.
AU - Bouguerra S.
PY - 2006
SP - 345
EP - 350
DO - 10.5220/0001314103450350