Modeling Irregular Kernels of Task-based codes: Illustration with the Fast Multipole Method - Archive ouverte HAL Access content directly
Reports (Research Report) Year : 2017

Modeling Irregular Kernels of Task-based codes: Illustration with the Fast Multipole Method

(1, 2) , (3) , (2) , (1) , (1)
1
2
3

Abstract

The significant increase of the hardware complexity that occurred in the last few years led the high performance community to design many scientific libraries according to a task-based parallelization. The modeling of the performance of the individual tasks (or kernels) they are composed of is crucial for facing multiple challenges as diverse as performing accurate performance predictions, designing robust scheduling algorithms, tuning the applications, etc. Fine-grain modeling such as emulation and cycle-accurate simulation may lead to very accurate results. However, not only their high cost may be prohibitive but they furthermore require a high fidelity modeling of the processor, which makes them hard to deploy in practice. In this paper, we propose an alternative coarse-grain, empirical methodology oblivious to both the target code and the hardware architecture, which leads to robust and accurate timing predictions. We illustrate our approach with a task-based Fast Multipole Method (FMM) algorithm, whose kernels are highly irregular, implemented in the \scalfmm library on top of the starpu task-based runtime system and the simgrid simulator.
L'augmentation significative de la complexité matérielle qui s'est produite ces quelques dernières années a amené la communauté de calcul haute performance à mettre au point de nombreuses bibliothèques scientifiques sur le principe d'une parallélisation à base de tâches. La modélisation de la performance des tâches individuelles (ou noyaux) qui les composent est cruciale pour faire face aux multiples challenges aussi variés que la réalisation de prédictions de performance précises, la mise au point d'algorithme d'ordonnancement robustes, l'optimisation des applications, etc. La modélisation à grain fin tel que l'émulation et la simulation à la précision du cycle peut permettre des résultats très précis. Toutefois, non seulement leur coût élevé peut être prohibitif mais elles requièrent de surcroît une modélisation très fidèle du processeur, ce qui les rend difficiles à déployer en pratique. Dans ce papier, nous proposons une méthodologie alternative, à plus gros grain, empirique, transparente à la fois pour le code et l'architecture cibles, ce qui permet des prédictions robustes et précises. Nous illustrons notre approche avec une méthode méthode multipolaire rapide (FMM) à base de tâches, dont les noyaux sont hautement irréguliers, implémentée dans la librairie ScalFMM au-dessus du moteur d'exécution StarPU et du simulateur SimGrid.
Fichier principal
Vignette du fichier
rapport.pdf (1.58 Mo) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01474556 , version 1 (01-03-2017)

Identifiers

  • HAL Id : hal-01474556 , version 1

Cite

Emmanuel Agullo, Bérenger Bramas, Olivier Coulaud, Luka Stanisic, Samuel Thibault. Modeling Irregular Kernels of Task-based codes: Illustration with the Fast Multipole Method. [Research Report] RR-9036, INRIA Bordeaux. 2017, pp.35. ⟨hal-01474556⟩
812 View
307 Download

Share

Gmail Facebook Twitter LinkedIn More