Pipelining the Fast Multipole Method over a Runtime System

Emmanuel Agullo; Bérenger Bramas; Olivier Coulaud; Eric Darve; Matthias Messner; Toru Takahashi

hal-00703130, version 1

Pipelining the Fast Multipole Method over a Runtime System

Emmanuel Agullo () ^1, 2, Bérenger Bramas ^1, 2, Olivier Coulaud (, ) ^1, 2, Eric Darve^a^, 3, 4, Matthias Messner ^1, 2, Toru Takahashi^b^, 5

N° RR-7981 (2012)

Résumé : Fast Multipole Methods (FMM) are a fundamental operation for the simulation of many physical problems. The high performance design of such methods usually requires to carefully tune the algorithm for both the targeted physics and the hardware. In this paper, we propose a new approach that achieves high performance across architectures. Our method consists of expressing the FMM algorithm as a task flow and employing a state-of-the-art runtime system, StarPU, in order to process the tasks on the different processing units. We carefully design the task flow, the mathematical operators, their Central Processing Unit (CPU) and Graphics Processing Unit (GPU) implementations, as well as scheduling schemes. We compute potentials and forces of 200 million particles in 48.7 seconds on a homogeneous 160 cores SGI Altix UV 100 and of 38 million particles in 13.34 seconds on a heterogeneous 12 cores Intel Nehalem processor enhanced with 3 Nvidia M2090 Fermi GPUs.

a – Stanford University
b – Nagoya University
1 : HiePACS (INRIA Bordeaux - Sud-Ouest)
INRIA – Université de Bordeaux – CNRS : UMR5800 – CERFACS
2 : Laboratoire Bordelais de Recherche en Informatique (LaBRI)
CNRS : UMR5800 – Université Sciences et Technologies - Bordeaux I – École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB) – Université Victor Segalen - Bordeaux II
3 : Mechanical Engineering Department
Stanford University
4 : Institute for Computational and Mathematical Engineering (iCME)
Stanford University
5 : Department of Mechanical Science and Engineering
Nagoya University

Collaboration : PlaFRIM;FastLA

hal-00703130, version 1
http://hal.inria.fr/hal-00703130
oai:hal.inria.fr:hal-00703130
Contributeur : Olivier Coulaud <>
Soumis le : Vendredi 1 Juin 2012, 09:16:22
Dernière modification le : Lundi 15 Avril 2013, 09:16:37

Voir la fiche détaillée

Documents associés

PDF :

arXiv : 1206.0115

Exporter

Bibtex EndNote TEI RefWorks

%% hal-00703130, version 1
%% http://hal.inria.fr/hal-00703130
@techreport{agullo:hal-00703130,
    hal_id = {hal-00703130},
    url = {http://hal.inria.fr/hal-00703130},
    title = {{Pipelining the Fast Multipole Method over a Runtime System}},
    author = {Agullo, Emmanuel and Bramas, B{\'e}renger and Coulaud, Olivier and Darve, Eric and Messner, Matthias and Takahashi, Toru},
    abstract = {{Fast Multipole Methods (FMM) are a fundamental operation for the simulation of many physical problems. The high performance design of such methods usually requires to carefully tune the algorithm for both the targeted physics and the hardware. In this paper, we propose a new approach that achieves high performance across architectures. Our method consists of expressing the FMM algorithm as a task flow and employing a state-of-the-art runtime system, StarPU, in order to process the tasks on the different processing units. We carefully design the task flow, the mathematical operators, their Central Processing Unit (CPU) and Graphics Processing Unit (GPU) implementations, as well as scheduling schemes. We compute potentials and forces of 200 million particles in 48.7 seconds on a homogeneous 160 cores SGI Altix UV 100 and of 38 million particles in 13.34 seconds on a heterogeneous 12 cores Intel Nehalem processor enhanced with 3 Nvidia M2090 Fermi GPUs.}},
    keywords = {Fast multipole methods graphics processing unit;heterogeneous architectures;runtime system;pipeline;FMM},
    language = {Anglais},
    affiliation = {HiePACS - INRIA Bordeaux - Sud-Ouest , Laboratoire Bordelais de Recherche en Informatique - LaBRI , Mechanical Engineering Department , Institute for Computational and Mathematical Engineering - iCME , Department of Mechanical Science and Engineering},
    pages = {24},
    type = {Rapport de recherche},
    institution = {INRIA},
    number = {RR-7981},
    collaboration = {PlaFRIM;FastLA },
    year = {2012},
    month = May,
    pdf = {http://hal.inria.fr/hal-00703130/PDF/RR-7981.pdf},
}

%F hal-00703130, version 1
%0 Report
%U http://hal.inria.fr/hal-00703130
%2 INFO:INFO_DC
%T Pipelining the Fast Multipole Method over a Runtime System
%A Agullo, Emmanuel
%A Bramas, Bérenger
%A Coulaud, Olivier
%A Darve, Eric
%A Messner, Matthias
%A Takahashi, Toru
%+ HiePACS - INRIA Bordeaux - Sud-Ouest , Laboratoire Bordelais de Recherche en Informatique - LaBRI , Mechanical Engineering Department , Institute for Computational and Mathematical Engineering - iCME , Department of Mechanical Science and Engineering
%X Fast Multipole Methods (FMM) are a fundamental operation for the simulation of many physical problems. The high performance design of such methods usually requires to carefully tune the algorithm for both the targeted physics and the hardware. In this paper, we propose a new approach that achieves high performance across architectures. Our method consists of expressing the FMM algorithm as a task flow and employing a state-of-the-art runtime system, StarPU, in order to process the tasks on the different processing units. We carefully design the task flow, the mathematical operators, their Central Processing Unit (CPU) and Graphics Processing Unit (GPU) implementations, as well as scheduling schemes. We compute potentials and forces of 200 million particles in 48.7 seconds on a homogeneous 160 cores SGI Altix UV 100 and of 38 million particles in 13.34 seconds on a heterogeneous 12 cores Intel Nehalem processor enhanced with 3 Nvidia M2090 Fermi GPUs.
%2 Les méthodes multipôles rapides (FMM) sont une opération fondamentale pour la simulation de nombreux problèmes physiques. Leur mise en œuvre haute performance requiert habituellement d'optimiser attentivement l'algorithme à la fois pour la physique visée et la matériel utilisé. Dans ce papier, nous proposons une nouvelle approche qui atteint une performance élevée et portable. Note méthode consiste à exprimer l'algorithme FMM comme un flot de tâches et d'employer un moteur d'exécution, StarPU, afin de traiter les tâches sur les différentes unités d'exécution. Nous concevons précisément le flot de tâches, les opérateurs mathématiques, leur implémentations sur unité centrale de traitement (CPU) et processeur graphique (GPU) ainsi que les schémas d'ordonnancement. Nous calculons les potentiels et forces pour des problèmes de 200 millions de particules en 48.7 secondes sur une machine homogène SGI Altix UV 100 comportant 16O cœurs et de 38 millions de particules en 13.34 secondes sur une machine hétérogène composée d'un processeur Intel Nehalem accéléré avec 3 GPUs Nvidia Fermi M2090.
%G Anglais
%2 Rapport de recherche
%P 24
%8 2012-05-31
%K Fast multipole methods graphics processing unit;heterogeneous architectures;runtime system;pipeline;FMM
%Z RR-7981
%Z Equipe associée FastLA
%Z PlaFRIM;FastLA

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="report"><head>Rapports</head>
<biblStruct type="report" xml:id="hal-00703130"><monogr>
<author><persName><forename>Emmanuel</forename><surname>Agullo</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Bordeaux - Sud-Ouest</orgName>
<orgName type="team">HiePACS</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Université de Bordeaux</orgName>
<orgName type="institution">CNRS : UMR5800</orgName>
<orgName type="institution">CERFACS</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">LaBRI</orgName>
<orgName type="team">Laboratoire Bordelais de Recherche en Informatique</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR5800</orgName>
<orgName type="institution">Université Sciences et Technologies - Bordeaux I</orgName>
<orgName type="institution">École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)</orgName>
<orgName type="institution">Université Victor Segalen - Bordeaux II</orgName>
</affiliation>
</author>
<author><persName><forename>Bérenger</forename><surname>Bramas</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Bordeaux - Sud-Ouest</orgName>
<orgName type="team">HiePACS</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Université de Bordeaux</orgName>
<orgName type="institution">CNRS : UMR5800</orgName>
<orgName type="institution">CERFACS</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">LaBRI</orgName>
<orgName type="team">Laboratoire Bordelais de Recherche en Informatique</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR5800</orgName>
<orgName type="institution">Université Sciences et Technologies - Bordeaux I</orgName>
<orgName type="institution">École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)</orgName>
<orgName type="institution">Université Victor Segalen - Bordeaux II</orgName>
</affiliation>
</author>
<author><persName><forename>Olivier</forename><surname>Coulaud</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Bordeaux - Sud-Ouest</orgName>
<orgName type="team">HiePACS</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Université de Bordeaux</orgName>
<orgName type="institution">CNRS : UMR5800</orgName>
<orgName type="institution">CERFACS</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">LaBRI</orgName>
<orgName type="team">Laboratoire Bordelais de Recherche en Informatique</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR5800</orgName>
<orgName type="institution">Université Sciences et Technologies - Bordeaux I</orgName>
<orgName type="institution">École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)</orgName>
<orgName type="institution">Université Victor Segalen - Bordeaux II</orgName>
</affiliation>
</author>
<author><persName><forename>Eric</forename><surname>Darve</surname></persName>
<affiliation>
<orgName type="team">Mechanical Engineering Department</orgName>
<country>US</country>
<orgName type="institution">Stanford University</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">iCME</orgName>
<orgName type="team">Institute for Computational and Mathematical Engineering</orgName>
<country>US</country>
<orgName type="institution">Stanford University</orgName>
</affiliation>
</author>
<author><persName><forename>Matthias</forename><surname>Messner</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Bordeaux - Sud-Ouest</orgName>
<orgName type="team">HiePACS</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Université de Bordeaux</orgName>
<orgName type="institution">CNRS : UMR5800</orgName>
<orgName type="institution">CERFACS</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">LaBRI</orgName>
<orgName type="team">Laboratoire Bordelais de Recherche en Informatique</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR5800</orgName>
<orgName type="institution">Université Sciences et Technologies - Bordeaux I</orgName>
<orgName type="institution">École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)</orgName>
<orgName type="institution">Université Victor Segalen - Bordeaux II</orgName>
</affiliation>
</author>
<author><persName><forename>Toru</forename><surname>Takahashi</surname></persName>
<affiliation>
<orgName type="team">Department of Mechanical Science and Engineering</orgName>
<country>JP</country>
<orgName type="institution">Nagoya University</orgName>
</affiliation>
</author>
<title type="main" level="m">Pipelining the Fast Multipole Method over a Runtime System</title><title type="main" level="m">Pipelining the Fast Multipole Method over a Runtime System</title><imprint><biblScope type="publicationDate">2012-05-31</biblScope><biblScope type="pp">24</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/hal-00703130</idno><idno type="HALFile">http://hal.inria.fr/hal-00703130/PDF/RR-7981.pdf</idno></biblStruct>
</listBibl>
</listBibl>