Result: HIERARCHICAL MAPPING FOR HPC APPLICATIONS

Title:
HIERARCHICAL MAPPING FOR HPC APPLICATIONS
Authors:
CHUNG, I-Hsin, LEE JIAZHENG, Che-Rung, YEH-CHING CHUNG, Zhou
Source:
Special Issue on Large-Scale Parallel ProcessingParallel processing letters. 21(3):279-299
Publisher Information:
Singapore: World Scientific Publishing, 2011.
Publication Year:
2011
Physical Description:
print, 23 ref
Original Material:
INIST-CNRS
Subject Terms:
Control theory, operational research, Automatique, recherche opérationnelle, Electronics, Electronique, Computer science, Informatique, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Algorithmique. Calculabilité. Arithmétique ordinateur, Algorithmics. Computability. Computer arithmetics, Recherche information. Graphe, Information retrieval. Graph, Logiciel, Software, Systèmes informatiques et systèmes répartis. Interface utilisateur, Computer systems and distributed systems. User interface, Algorithme parallèle, Parallel algorithm, Algoritmo paralelo, Allocation ressource, Resource allocation, Asignación recurso, Calcul matriciel, Matrix calculus, Cálculo de matrices, Calcul réparti, Distributed computing, Cálculo repartido, Communication information, Information communication, Comunicación información, Complexité algorithme, Algorithm complexity, Complejidad algoritmo, Complexité temps, Time complexity, Complejidad tiempo, Extensibilité, Scalability, Estensibilidad, Haute performance, High performance, Alto rendimiento, Irrégularité, Irregularity, Irregularidad, Parallélisme, Parallelism, Paralelismo, Produit matrice, Matrix product, Producto matriz, Superordinateur, Supercomputer, Supercomputador, Théorie spectrale, Spectral theory, Teoría espectral, Algorithme irrégulier, Irregular Algorithm, Algoritmo irregular, HPC resource allocation, communication performance, task mapping
Document Type:
Academic journal Article
File Description:
text
Language:
English
Author Affiliations:
IBM T.J. Watson Research Center Yorktown Heights, New York 10598, United States
National Tsing-Hua University, Hsin-Chu, Tawain, Province of China
ISSN:
0129-6264
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=24600569
Rights:
Copyright 2015 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems
Accession Number:
edscal.24600569
Database:
PASCAL Archive

Further Information

As the high performance computing systems scale up, mapping the tasks of a parallel application onto physical processors to allow efficient communication becomes one of the critical performance issues. Existing algorithms were usually designed to map applications with regular communication patterns. Their mapping criterion usually overlooks the size of communicated messages, which is the primary factor of communication time. In addition, most of their time complexities are too high to process large scale problems. In this paper, we present a hierarchical mapping algorithm (HMA), which is capable of mapping applications with irregular communication patterns. It first partitions tasks according to their run-time communication information. The tasks that communicate with each other more frequently are regarded as strongly connected. Based on their connectivity strength, the tasks are partitioned into supernodes based on the algorithms in spectral graph theory. The hierarchical partitioning reduces the mapping algorithm complexity to achieve scalability. Finally, the run-time communication information will be used again in fine tuning to explore better mappings. With the experiments, we show how the mapping algorithm helps to reduce the point-to-point communication time for the PDGEMM, a ScaLAPACK matrix multiplication computation kernel, up to 20% and the AMG2006, a tier 1 application of the Sequoia benchmark, up to 7%.