The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
En raison des récents progrès technologiques basés sur le traitement du Big Data, de nombreuses applications présentent des modèles de communication irréguliers ou imprévisibles entre les nœuds de calcul des systèmes de calcul haute performance (HPC). Les infrastructures de communication traditionnelles, par exemple les réseaux d'interconnexion torus ou fat-tree, risquent de ne pas bien gérer leurs problèmes de mise en relation avec ces nouvelles applications émergentes. Il existe déjà de nombreux algorithmes de mappage d'applications efficaces en matière de communication pour ces topologies de réseau non aléatoires typiques, qui utilisent des nœuds de calcul proches pour réduire les distances du réseau. Cependant, pour les modèles de communication imprévisibles ci-dessus, il est difficile de mapper efficacement leurs applications sur des topologies de réseau non aléatoires. Dans ce contexte, nous recommandons d'utiliser des topologies de réseau aléatoires comme infrastructures de communication, qui ont attiré de plus en plus d'attention pour l'utilisation d'interconnexions HPC en raison de leur petite taille. diamètre et la longueur moyenne du chemin le plus court (ASPL). Nous réalisons une étude comparative pour analyser l'impact des performances de cartographie des applications sur les topologies de réseaux non aléatoires et aléatoires. Nous proposons d'utiliser des métriques intégrant la topologie, c'est-à-dire diamètre et à la ASPL, et répertorient plusieurs algorithmes de mappage d'applications basés sur Diameter/ASPL pour comparer leurs performances de planification des tâches, en supposant que le modèle de communication de chaque application est imprévisible pour le système informatique. L'évaluation avec une charge de travail d'application composée importante montre que, par rapport aux topologies non aléatoires, les topologies aléatoires peuvent réduire le délai d'exécution moyen jusqu'à 39.3 % grâce à une méthode de cartographie connectée aléatoire et jusqu'à 72.1 % grâce à un algorithme de cartographie basé sur le diamètre/ASPL. . De plus, par rapport à la méthode de cartographie topologique de base, la stratégie de cartographie topologique basée sur le diamètre/ASPL proposée peut réduire jusqu'à 48.0 % de la durée de vie et jusqu'à 78.1 % du temps d'exécution moyen, et améliorer jusqu'à 1.9 fois l'utilisation du système sur des topologies aléatoires.
Yao HU
National Institute of Informatics
Michihiro KOIBUCHI
National Institute of Informatics
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
Yao HU, Michihiro KOIBUCHI, "Application Mapping and Scheduling of Uncertain Communication Patterns onto Non-Random and Random Network Topologies" in IEICE TRANSACTIONS on Information,
vol. E103-D, no. 12, pp. 2480-2493, December 2020, doi: 10.1587/transinf.2020PAP0006.
Abstract: Due to recent technology progress based on big-data processing, many applications present irregular or unpredictable communication patterns among compute nodes in high-performance computing (HPC) systems. Traditional communication infrastructures, e.g., torus or fat-tree interconnection networks, may not handle well their matchmaking problems with these newly emerging applications. There are already many communication-efficient application mapping algorithms for these typical non-random network topologies, which use nearby compute nodes to reduce the network distances. However, for the above unpredictable communication patterns, it is difficult to efficiently map their applications onto the non-random network topologies. In this context, we recommend using random network topologies as the communication infrastructures, which have drawn increasing attention for the use of HPC interconnects due to their small diameter and average shortest path length (ASPL). We make a comparative study to analyze the impact of application mapping performance on non-random and random network topologies. We propose using topology embedding metrics, i.e., diameter and ASPL, and list several diameter/ASPL-based application mapping algorithms to compare their job scheduling performances, assuming that the communication pattern of each application is unpredictable to the computing system. Evaluation with a large compound application workload shows that, when compared to non-random topologies, random topologies can reduce the average turnaround time up to 39.3% by a random connected mapping method and up to 72.1% by a diameter/ASPL-based mapping algorithm. Moreover, when compared to the baseline topology mapping method, the proposed diameter/ASPL-based topology mapping strategy can reduce up to 48.0% makespan and up to 78.1% average turnaround time, and improve up to 1.9x system utilization over random topologies.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2020PAP0006/_p
Copier
@ARTICLE{e103-d_12_2480,
author={Yao HU, Michihiro KOIBUCHI, },
journal={IEICE TRANSACTIONS on Information},
title={Application Mapping and Scheduling of Uncertain Communication Patterns onto Non-Random and Random Network Topologies},
year={2020},
volume={E103-D},
number={12},
pages={2480-2493},
abstract={Due to recent technology progress based on big-data processing, many applications present irregular or unpredictable communication patterns among compute nodes in high-performance computing (HPC) systems. Traditional communication infrastructures, e.g., torus or fat-tree interconnection networks, may not handle well their matchmaking problems with these newly emerging applications. There are already many communication-efficient application mapping algorithms for these typical non-random network topologies, which use nearby compute nodes to reduce the network distances. However, for the above unpredictable communication patterns, it is difficult to efficiently map their applications onto the non-random network topologies. In this context, we recommend using random network topologies as the communication infrastructures, which have drawn increasing attention for the use of HPC interconnects due to their small diameter and average shortest path length (ASPL). We make a comparative study to analyze the impact of application mapping performance on non-random and random network topologies. We propose using topology embedding metrics, i.e., diameter and ASPL, and list several diameter/ASPL-based application mapping algorithms to compare their job scheduling performances, assuming that the communication pattern of each application is unpredictable to the computing system. Evaluation with a large compound application workload shows that, when compared to non-random topologies, random topologies can reduce the average turnaround time up to 39.3% by a random connected mapping method and up to 72.1% by a diameter/ASPL-based mapping algorithm. Moreover, when compared to the baseline topology mapping method, the proposed diameter/ASPL-based topology mapping strategy can reduce up to 48.0% makespan and up to 78.1% average turnaround time, and improve up to 1.9x system utilization over random topologies.},
keywords={},
doi={10.1587/transinf.2020PAP0006},
ISSN={1745-1361},
month={December},}
Copier
TY - JOUR
TI - Application Mapping and Scheduling of Uncertain Communication Patterns onto Non-Random and Random Network Topologies
T2 - IEICE TRANSACTIONS on Information
SP - 2480
EP - 2493
AU - Yao HU
AU - Michihiro KOIBUCHI
PY - 2020
DO - 10.1587/transinf.2020PAP0006
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E103-D
IS - 12
JA - IEICE TRANSACTIONS on Information
Y1 - December 2020
AB - Due to recent technology progress based on big-data processing, many applications present irregular or unpredictable communication patterns among compute nodes in high-performance computing (HPC) systems. Traditional communication infrastructures, e.g., torus or fat-tree interconnection networks, may not handle well their matchmaking problems with these newly emerging applications. There are already many communication-efficient application mapping algorithms for these typical non-random network topologies, which use nearby compute nodes to reduce the network distances. However, for the above unpredictable communication patterns, it is difficult to efficiently map their applications onto the non-random network topologies. In this context, we recommend using random network topologies as the communication infrastructures, which have drawn increasing attention for the use of HPC interconnects due to their small diameter and average shortest path length (ASPL). We make a comparative study to analyze the impact of application mapping performance on non-random and random network topologies. We propose using topology embedding metrics, i.e., diameter and ASPL, and list several diameter/ASPL-based application mapping algorithms to compare their job scheduling performances, assuming that the communication pattern of each application is unpredictable to the computing system. Evaluation with a large compound application workload shows that, when compared to non-random topologies, random topologies can reduce the average turnaround time up to 39.3% by a random connected mapping method and up to 72.1% by a diameter/ASPL-based mapping algorithm. Moreover, when compared to the baseline topology mapping method, the proposed diameter/ASPL-based topology mapping strategy can reduce up to 48.0% makespan and up to 78.1% average turnaround time, and improve up to 1.9x system utilization over random topologies.
ER -