Ordonnancemenent d’entr ́ee-sortie p ́eriodiques avec des chaines bicolore: modèles et algorithmes

Observations show that some HPC applications periodically alternate between (i) op- erations (computations, local data-accesses) executed on the compute nodes, and (ii) I/O transfers of data and this behavior can be predicted before-hand. While the compute nodes are allocated separately to each application, the storage is shared and thus I/O access can be a bottleneck leading to contention. To tackle this issue, we design new static I/O scheduling algorithms that prescribe when each application can access the storage. To design a static algorithm, we emphasize on the periodic behavior of most applications. Scheduling the I/O volume of the different applications is repeated over time. This is critical since often the number of application runs is very high. In the following report, we develop a formal background for I/O scheduling. First, we define a model, bi-colored chain scheduling, then we go through related results existing in the literature and explore the complexity of this problem variants. Finally, to match the HPC context, we per- form experiments based on use-cases matching highly parallel applications or distributed learning frameworkDes observations ont montré qu’en calcul haute performance, les applications alternent entre (i) des opérations (calculs, accès à données locales) exécutées sur les nœuds de calcul, et (ii) des transferts de données en entrée/sortie et que ce comportement pouvait être prédit en amont. Alors que les nœuds de calcul sont alloués séparément à chaque application, l’espace de stockage est partagé, par conséquent, son accès peut-être un goulet d’étranglement causant de la contention. Afin de limiter ce problème, nous proposons de nouveaux algorithmes statiques d’ordonnancement d’entrée/sorties spécifiant quand chaque application a accès au stockage. Pour concevoir un algorithme statique, nous insistons sur le comportement périodique de la plupart des applications : ’ordonnancement des d’entrées/sorties des différentes applications se répète au cours du temps ce qui est souvent critique car le nombre d’exécutions des applications est très élevé. Dans le rapport suivant, nous développons un cadre théorique pour l’ordonnancement d’entrée/sortie. Tout d’abord, nous définissons un modèle, l’ordonnancement de chaînes bicolores, puis nous parcourons les résultats liés existant dans la littérature et explorons la complexité de cette variante du problème. Enfin, pour coller au contexte du calcul haute performance, nous effectuons des expériences basées sur de vrais casd’utilisation correspondant à des applications hautement parallèles ou à de l’apprentissage distribué