implicit.org 26.2 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
#+TITLE: Usage implicit de MPI dans ScalFmm
#+AUTHOR: Martin Khannouz
#+LANGUAGE:  fr
#+STARTUP: inlineimages
#+OPTIONS: H:3 num:t toc:t \n:nil @:t ::t |:t ^:nil -:t f:t *:t <:t
#+OPTIONS: TeX:t LaTeX:t skip:nil d:nil todo:nil pri:nil tags:not-in-toc
#+EXPORT_SELECT_TAGS: export
#+EXPORT_EXCLUDE_TAGS: noexport
#+TAGS: noexport(n)

 
# #+BEGIN_SRC sh 
# export SCALFMM_DIR=/home/mkhannou/scalfmm
# cd $SCALFMM_DIR
# git checkout mpi_implicit
# spack install scalfmm@src+mpi+starpu \^starpu@svn-trunk+mpi+fxt \^openmpi
# #+END_SRC

19
* Abstract
20
We live in a world were computer capacity get larger and larger, unfortunatly, our old algorithm ain't calibrate for such computer so it is important to find new paradigme to use the full power of those newest machine and then go faster than ever.
21 22

The Fast Multipole Methode (FMM) is one of the most prominent algorithms to perform pair-wise particle interactions, with application in many physical problems such as astrophysical simulation, molecular dynmics, the boundary element method, radiosity in computer-graphics or dislocation dynamics. Its linear complexity makes it an excellent candidate for large-scale simulation.
23
* Introduction
24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53
** N-Body problem
<<sec:nbody_problem>>
In physics, the /n-body/ problem is the problem of predicting the individual motions of a group of celestial objects interacting with each other gravitationally.
Solving this problem has been motivated by the desire to understand the motions of the Sun, Moon, planets and the visible stars.
It then has been extended to other field like electrostatics or molecular dynamics.

NOTE: Come from wikipedia, not sure this is studious.

** Fast Multipole Method (FMM)
*** Description
The Fast Multipole Method (FMM) is a hierarchical method for the n − body problem introduced in [[sec:nbody_problem]] that has been classified to be one of the top ten algorithms of the 20th century by the SIAM (source).
In the original study, the FMM was presented to solve a 2D particle interaction problem, but it was later extended to 3D.
The FMM succeeds to dissociate the near and far field and still uses the accurate direct computation for the near field.
The original FMM proposal was based on a mathematical method to approximate the far field and using an algorithm based on a quadtree/octree for molecular dynamics or astrophysics.
The algorithm is the core part because it is responsible for the calls to the mathematical functions in a correct order to approximate the interactions between clusters that represent far particles.
When an application is said to be accelerated by the FMM it means the application uses the FMM algorithm but certainly with another mathematical kernel that matches the problems.
The FMM is used to solve a variety of problems: astrophysical simulations, molecular dynamics, the boundary element method, radiosity in computer-graphics and dislocation dynamics among others.

NOTE: Directly come from Bérenger thesis.

*** Algorithm
The FMM algorithm rely on an octree (quadtree in 2 dimensions) obtained by splitting the space of the simulation recursivly in 8 parts (4 parts in 2D). The building is shown on figure [[fig:octree]].

#+CAPTION: On the left side is the box with all the particles. In the middle is the same box as before, split three time in four parts. Whiche give 64 smaller boxes in the end. On the right is the quadtree (octree in 3D) with an height of 4 built from the different splitting. On top of it is the root of the tree that hold the whole box and so all particles.
#+name: fig:octree
[[./figure/octree.png]]


#+CAPTION: FMM algorithm.
[[./figure/FMM.png]]
54

Martin Khannouz's avatar
Martin Khannouz committed
55 56
* State of the art
Nothing for now ...
57 58
** Task based FMM
*** Runtime
59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78
In the field of HPC, a runtime system is in charge of the parallel execution of an application.
A runtime system must provide facilities to split and to pipeline the work but also to use the hardware efficiently. In our case, we restrict this definition and remove the the thread libraries.
We list here some of the well-known runtime systems: [[https://www.bsc.es/computer-sciences/programming-models/smp-superscalar/programming-model][SMPSs]], [[http://starpu.gforge.inria.fr/][StarPU]], [[http://icl.cs.utk.edu/parsec/][PaRSEC]], [[https://software.intel.com/sites/landingpage/icc/api/index.html][CnC]], [[http://icl.cs.utk.edu/quark][Quark]], SuperMatrix and [[http://openmp.org/wp/][OpenMP]].
These different runtime systems rely on several paradigms like the two well-known fork-join or task-based models.
We can describe the tasks that composed an application and their dependencies with a direct acyclic graph (DAG); the tasks are represented by nodes/vertices and their dependencies by edges.
For example, the DAG given by A → B states that there are two tasks A and B , and that A must be finished to release B.
Such a dependency happens if A modifies a value that will later be used by B or if A read a value that B will modify.
The tasks-based paradigm has been studied by the dense linear algebra community and used in new production solvers such as [[http://icl.cs.utk.edu/plasma/news/news.html?id=212][Plasma]], [[http://icl.cs.utk.edu/magma/software/][Magma]] or Flame.
The robustness and high efficiency of these dense solvers have motivate the study of more irregular algorithms such as sparse linear solvers and now the fast multipole method.

NOTE: Directly come from Bérenger thesis.

NOTE: somehow, tell that scalfmm is using The StarPU runtime.

*** Sequential Task Flow
A sequential task flow is a sequential algorithm that describe the tasks to be done and their dependencies. On the other hand the tasks can be executed asynchronously and parralelly.
In that way, the main algorithm remain almost as simple as the sequential one and can unlock a lot of parralellisme.

It also create a DAG from which interesting property can be used to prove interesting stuff. (Not really sure)

79
*** Group tree
80 81 82 83 84 85 86 87
What is a group tree and what is it doing here ?
The task scheduling with a smart runtime such as StarPU cost a lot.
The FMM generate a huge amount of small tasks, which considerably increase the time spent into the scheduler.
The group tree pack particule or multipole together into a group and execute a task (P2P, P2M, M2M, ...) on a group of particles (or multipole) rather than only one particle (or multipole).
This granularity of the task and make the cost of the scheduler decrease.

TODO: image of the group tree

88 89 90
*** Distributed FMM
* Implicit MPI FMM
** Sequential Task Flow with implicit communication
91 92 93
Two differents things :
- Register data handle in starpu_mpi
- Define a data mapping function so each handle will be placed ton an mpi node.
94
** Data Mapping
95 96
One of the main advantage of using implicit mpi communication in starpu is that tha data mapping can be separated from the algorithm. It is then possible to change the data mapping without changing the algorithm.

97
*** Level Split Mapping
98 99
The level split mapping aim to balence work between mpi process by spliting evenly each level between all mpi processes.

100
*** Leaf Load Balancing
101 102 103
The leaf load balancing aim to balance the work between mpi process by evenly split leaf between mpi process.
Then the upper levels are split following the 13th algorithm present int Bérenger Thesis.

104
*** TreeMatch Balancing
105 106 107 108 109 110
TreeMatch is a tool developped at Inria Bordeaux which is accessible [[http://treematch.gforge.inria.fr/][here]].
TreeMatch aim to reorganize processus mapping to obtain the best performance.
It use as input the hardware topologie and information about MPI exchange.

This tool could be used to force certain data mapping in the implicit mpi version and achieve hihger performance.

111
** Result
112 113 114 115 116 117 118 119 120
*** Hardware
One node equal 2 Dodeca-core Haswell Intel® Xeon® E5-2680, 2,5GHz, 128Go de RAM (DDR4 2133MHz), 500 Go de stockage (Sata).
*** Aims
Compare explicit and implicit version.
But to measure the impact of implicit communication we need an implicit version as close to the explicit version as possible.
Mainly, this means, same particules onto the same grouped tree with same task executed on the same node.
*** Scripts and jobs
<<sec:result>>
The scripts of the jobs:
121
#+BEGIN_SRC
122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159
#!/usr/bin/env bash
## name of job
#SBATCH -J chebyshev_50M_10_node
#SBATCH -p longq
## Resources: (nodes, procs, tasks, walltime, ... etc)
#SBATCH -N 10
#SBATCH -c 24
# #  standard output message
#SBATCH -o chebyshev_50M_10_node%j.out
# # output error message
#SBATCH -e chebyshev_50M_10_node%j.err
#SBATCH --mail-type=ALL --mail-user=martin.khannouz@inria.fr
module purge
module load slurm
module add compiler/gcc/5.3.0 tools/module_cat/1.0.0 intel/mkl/64/11.2/2016.0.0
. /home/mkhannou/spack/share/spack/setup-env.sh
spack load fftw
spack load hwloc
spack load openmpi
spack load starpu@svn-trunk+fxt
## modules to load for the job
export GROUP_SIZE=500
export TREE_HEIGHT=8
export NB_NODE=$SLURM_JOB_NUM_NODES
export STARPU_NCPU=24
export NB_PARTICLE_PER_NODE=5000000
export STARPU_FXT_PREFIX=`pwd`/
echo "=====my job informations ===="
echo "Node List: " $SLURM_NODELIST
echo "my jobID: " $SLURM_JOB_ID
echo "Nb node: " $NB_NODE
echo "Particle per node: " $NB_PARTICLE_PER_NODE
echo "Total particles: " $(($NB_PARTICLE_PER_NODE*$NB_NODE))
echo "In the directory: `pwd`"
rm -f canard.fma > /dev/null 2>&1
mpiexec -n $NB_NODE ./Build/Tests/Release/testBlockedMpiChebyshev -nb $NB_PARTICLE_PER_NODE -bs $GROUP_SIZE -h $TREE_HEIGHT -no-validation | grep Average
#TODO probably move trace.rec somewhere else ...
mpiexec -n $NB_NODE ./Build/Tests/Release/testBlockedImplicitChebyshev -f canard.fma -bs $GROUP_SIZE -h $TREE_HEIGHT -no-validation | grep Average
160 161
#+END_SRC

162 163
and

164
#+BEGIN_SRC
165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200
#!/usr/bin/env bash
## name of job
#SBATCH -J chebyshev_50M_1_node
#SBATCH -p longq
## Resources: (nodes, procs, tasks, walltime, ... etc)
#SBATCH -N 1
#SBATCH -c 24
# #  standard output message
#SBATCH -o chebyshev_50M_1_node%j.out
# # output error message
#SBATCH -e chebyshev_50M_1_node%j.err
#SBATCH --mail-type=ALL --mail-user=martin.khannouz@inria.fr
module purge
module load slurm
module add compiler/gcc/5.3.0 tools/module_cat/1.0.0 intel/mkl/64/11.2/2016.0.0
. /home/mkhannou/spack/share/spack/setup-env.sh
spack load fftw
spack load hwloc
spack load openmpi
spack load starpu@svn-trunk+fxt
## modules to load for the job
export GROUP_SIZE=500
export TREE_HEIGHT=8
export NB_NODE=$SLURM_JOB_NUM_NODES
export STARPU_NCPU=24
export NB_PARTICLE_PER_NODE=50000000
export STARPU_FXT_PREFIX=`pwd`/
echo "=====my job informations ===="
echo "Node List: " $SLURM_NODELIST
echo "my jobID: " $SLURM_JOB_ID
echo "Nb node: " $NB_NODE
echo "Particle per node: " $NB_PARTICLE_PER_NODE
echo "Total particles: " $(($NB_PARTICLE_PER_NODE*$NB_NODE))
echo "In the directory: `pwd`"
rm -f canard.fma > /dev/null 2>&1
mpiexec -n $NB_NODE ./Build/Tests/Release/testBlockedChebyshev -nb $NB_PARTICLE_PER_NODE -bs $GROUP_SIZE -h $TREE_HEIGHT -no-validation | grep Kernel
201 202 203
#+END_SRC

The result given by the script after few minutes executing:
204 205

Result for 10 nodes.
206
#+BEGIN_EXAMPLE
207 208 209 210 211 212 213 214 215
=====my job informations ====
Node List:  miriel[022-031]
my jobID:  109736
Nb node:  10
Particle per node:  5000000
Total particles:  50000000
In the directory: /home/mkhannou/scalfmm
Average time per node (explicit Cheby) : 9.35586s
Average time per node (implicit Cheby) : 10.3728s
216 217
#+END_EXAMPLE

218 219 220 221 222 223 224 225 226 227 228 229 230 231
Result for 1 node.
#+BEGIN_EXAMPLE
=====my job informations ====
Node List:  miriel036
my jobID:  109737
Nb node:  1
Particle per node:  50000000
Total particles:  50000000
In the directory: /home/mkhannou/scalfmm
Kernel executed in in 62.0651s
#+END_EXAMPLE

As you can see, on only one node, it took a little more than one minutes to run the algorithm. It took only 10 seconds and 14 seconds for the explicit and implicit version.

Martin Khannouz's avatar
Martin Khannouz committed
232
* Notes
233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256
** Installing
First, install StarPu and its dependancy.
#+begin_src
pacman -S hwloc
svn checkout svn://scm.gforge.inria.fr/svn/starpu/trunk StarPU
cd StarPU
./autogen.sh
mkdir install
./configure --prefix=$PWD/install
make
make install
#+end_src

This are envirronement variable that might be useful to set. But of course, be smart and replace the path in STARPU_DIR by your path.
#+begin_src
export STARPU_DIR=/home/mkhannou/StarPU/install
export PKG_CONFIG_PATH=$STARPU_DIR/lib/pkgconfig:$PKG_CONFIG_PATH
export LD_LIBRARY_PATH=$STARPU_DIR/lib:$LD_LIBRARY_PATH
export STARPU_GENERATE_TRACE=1
export PATH=$PATH:$STARPU_DIR/bin
#+end_src

If you are on Debian or Debian like distribution, simpler way to install StarPU are described [[http://starpu.gforge.inria.fr/doc/html/BuildingAndInstallingStarPU.html][here]].

Martin Khannouz's avatar
Martin Khannouz committed
257 258 259
** Useful script
*** Setup on plafrim
To setup everything that is needed on plafrim I first install spack.
260
#+begin_src sh
Martin Khannouz's avatar
Martin Khannouz committed
261
git clone https://github.com/fpruvost/spack.git
262 263 264 265
#+end_src



Martin Khannouz's avatar
Martin Khannouz committed
266
Then you have to add spack binary in your path.
267 268

#+begin_src sh
Martin Khannouz's avatar
Martin Khannouz committed
269
PATH=$PATH:spack/bin/spack
270 271
#+end_src
If your default python interpreter isn't python 2, you might have to replace the first line of spack/bin/spack by
Martin Khannouz's avatar
Martin Khannouz committed
272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309
#+begin_src sh
#!/usr/bin/env python2
#+end_src
So the script is automaticly run with python 2.
Then, you have to add your ssh key to your ssh agent. The following script kill all ssh agent, then respawn it and add the ssh key.
#+begin_src sh
SSH_KEY=".ssh/rsa_inria"
killall -9 ssh-agent > /dev/null
eval `ssh-agent` > /dev/null
ssh-add $SSH_KEY
#+end_src

Because on plafrim, users can't connect to the rest of the world, you have to copy data there.
So copy spack directory, use spack to create a mirror that will be sent to plafrim so spack will be able to install package.

#+begin_src sh
MIRROR_DIRECTORY="tarball_scalfmm"
#Copy spack to plafrim
scp -r spack mkhannou@plafrim:/home/mkhannou
#Recreate the mirror
rm -rf $MIRROR_DIRECTORY
mkdir $MIRROR_DIRECTORY
spack mirror create -D -d $MIRROR_DIRECTORY starpu@svn-trunk+mpi \^openmpi
#Create an archive and send it to plafrim
tar czf /tmp/canard.tar.gz $MIRROR_DIRECTORY 
scp /tmp/canard.tar.gz mkhannou@plafrim-ext:/home/mkhannou
rm -f /tmp/canard.tar.gz
#Install on plafrim
ssh mkhannou@plafrim 'tar xf canard.tar.gz; rm -f canard.tar.gz'
ssh mkhannou@plafrim "/home/mkhannou/spack/bin/spack mirror add local_filesystem file:///home/mkhannou/$MIRROR_DIRECTORY"
ssh mkhannou@plafrim '/home/mkhannou/spack/bin/spack install starpu@svn-trunk+mpi+fxt \^openmpi'
#+end_src

TODO add script I add on plafrim side with library links.

*** Execute on plafrim
To run my tests on plafrim, I used the two following scripts.
One to send the scalfmm repository to plafrim.
310 311 312

#+include: "~/narval.sh" src sh

Martin Khannouz's avatar
Martin Khannouz committed
313 314 315
Note : you might have to add your ssh_key again if you killed your previous ssh agent.

Then, the one that is runned on plafrim. It configure, compile and submit all the jobs on plafrim.
316

Martin Khannouz's avatar
Martin Khannouz committed
317
#+begin_src sh
318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352
module add slurm
module add compiler/gcc/5.3.0 tools/module_cat/1.0.0 intel/mkl/64/11.2/2016.0.0

# specific to plafrim to get missing system libs
export LIBRARY_PATH=/usr/lib64:$LIBRARY_PATH

# load spack env
export SPACK_ROOT=$HOME/spack
. $SPACK_ROOT/share/spack/setup-env.sh

#Load dependencies for starpu and scalfmm
spack load fftw
spack load hwloc
spack load openmpi
spack load starpu@svn-trunk~fxt
cd scalfmm/Build
#Configure and build scalfmm and scalfmm tests
rm -rf CMakeCache.txt CMakeFiles > /dev/null
cmake .. -DSCALFMM_USE_MPI=ON -DSCALFMM_USE_STARPU=ON -DSCALFMM_USE_FFT=ON -DSCALFMM_BUILD_EXAMPLES=ON -DSCALFMM_BUILD_TESTS=ON -DCMAKE_CXX_COMPILER=`which g++`
make clean
make -j `nproc`

#Submit jobs
cd ..
files=./jobs/*.sh

for f in $files
do
    echo "Submit $f..."
    sbatch $f
    if [ "$?" != "0" ] ; then 
		echo "Error submitting $f."
        break;
    fi
done
Martin Khannouz's avatar
Martin Khannouz committed
353
#+end_src
354

355 356 357 358 359 360 361 362 363 364 365 366 367 368
*** Export orgmode somewhere accessible
A good place I found to put your orgmode file and its html part is on the inria forge, in your project repository.
For me it was the path /home/groups/scalfmm/htdocs.
So I created a directory named orgmode and create the following script to update the files.
#+begin_src sh
cd Doc/noDist/implicit
emacs implicit.org --batch -f org-html-export-to-html --kill
ssh scm.gforge.inria.fr "cd /home/groups/scalfmm/htdocs/orgmode/; rm -rf implicit"
cd ..
scp -r implicit scm.gforge.inria.fr:/home/groups/scalfmm/htdocs/orgmode/
ssh scm.gforge.inria.fr "cd /home/groups/scalfmm/htdocs/orgmode/; chmod og+r implicit -R;"
#+end_src


369 370
* Journal
** Implémentation mpi implicite très naïve
371 372 373 374 375 376 377 378
Cette première version avait pour principal but de découvrir et à prendre en main les fonctions de StarPU MPI.
Les premières étant starpu_mpi_init et starpu_mpi_shutdown. Mais rapidement ont suivies les fonctions pour /tagger/ les /handles/ de StarPU et les ajouter à des nœuds MPI.
À cela c'est ajouté la transformation de tous les appels à starpu_insert_task ou starpu_task_submit par starpu_mpi_insert_task.

Par soucis de simplicité chaque nœud MPI possède l'intégralité de l'arbre, même si ce n'est pas une solution viable sur le long terme.
Pour vérifier que tout fonctionnait correctement, je me suis amusé à /mapper/ toutes les données sur un premier nœud MPI et toutes les tâches sur un second.
J'ai ensuite pu valider que l'arbre du premier nœud avait les bons résultats et que le second nœud n'avait que des erreurs.

379
** Implémentation moins naïve
380 381 382 383
Dans l'idée de créer une version 0 un brin potable qui puisse faire du calcul avec plus de deux nœuds MPI, j'ai créé une fonction de /mapping/ des données.
Elle consistait à partager chaque niveau entre tous les processus de la manière la plus équitable possible.

#+CAPTION: Division de chaque niveau entre chaque processus. Groupe de l'arbre de taille 4.
Martin Khannouz's avatar
Martin Khannouz committed
384
[[./figure/naive_split.png]]
385

386
** Reproduction du mapping mpi explicite
387 388 389 390
Pour pouvoir effectuer des comparaisons il était nécessaire de reproduire le même /mapping/ de tâches la version MPI explicite.
Dans le cas de la version implicite telle qu'elle est actuellement implémentée, le /mapping/ des données infère le /mapping/ de tâches.
La façon la plus simple de procéder est de faire en sorte que les particules se retrouvent sur les mêmes nœuds MPI.

391
*** Premier problème des groupes
392 393 394 395 396
La disposition des particules sur les nœuds MPI étant décidé par un tri distribué, il était plus judicieux de sauvegarder le /mapping/ des particules dans un fichier puis de le charger (dans la version implicite) et d'utiliser ce /mapping/ pour influer le /mapping/ au niveau de la version implicite.
Le soucis du tri distribué est qu'il essaye d'équilibrer les particules sur les nœuds sans tenir compte des groupes de l'arbre groupé (/group tree/).

#+CAPTION: Problème issuent de la constitution des groupes.
#+NAME:   fig:SED-HR4049
Martin Khannouz's avatar
Martin Khannouz committed
397
[[./figure/group_issue1.png]]
398 399 400 401 402 403

Or le /mapping/ des données est fait avec la granularité des groupes de l'arbre groupé.

Une première solution serait de modifier un peu l'algorithme de l'arbre pour le forcer à faire des groupes un peu plus petit de telle sorte qu'ils correspondent aux groupes de la version MPI explicite.
Soucis, quand il faudra remonter dans l'arbre, que faire des cellules qui sont présentes sur plusieurs nœuds MPI, que faire de la racine ?

404
*** Solution retenue
405 406 407 408 409 410
Plutôt que d'essayer de reproduire un /mapping/ de données identique à celui de la version explicite quel que soit les particules, nous avons choisi de limiter le nombre de cas reproductibles et de ségmenter ce /mapping/ par niveau.
Ainsi avec un arbre parfait où chaque indice de morton possède le même nombre de particules, il est possible de reproduire le même /mapping/ de données sur un certain de nombre de niveaux.
Ce nombre varie en fonction de la taille des groupes de l'arbre groupé.

#+CAPTION: Méthode pour générer une particule à un indice de Morton donné.
#+NAME:   fig:SED-HR4049
Martin Khannouz's avatar
Martin Khannouz committed
411
[[./figure/morton_box_center.png]]
412

413 414 415 416 417 418 419 420 421 422 423
*** Solution apportée par la suite
Après discussion avec Bérenger il s'avèra qu'il n'était pas si difficile de reproduire le tri parrallèle. Ce à quoi je me suis attelé durant les jours qui on suivi.
Ainsi un constructeur a été ajouté à l'arbre bloqué pour décrire la taille de chaque bloque à chaque étage.
Cela requière un un pré-calcul qui est effectué par une fonction intermédiaire.
Cela revient à:
- Trier les particules selon leur indice de Morton.
- Compter le nombre de feuilles différentes.
- Répartir les feuilles en utilisant l'objet FLeafBalance.
- Créer les groupe des étages supérieurs en se basant sur l'interval de travail fourni par l'algorithme 13 de la thèse de Bérenger.

*** Validation des résultats
424 425 426
Pour valider ces résultats, j'ai réutilisé le système de nom de tâches fait pour simgrid. Ainsi j'ai pu indiquer, dans un fichier des informations à propos de chaque tâche.
Les indices de Morton ainsi que les nœuds MPI sur lesquels elles s'exécutent. 

427
**** Observation
428 429 430 431 432
Si l'on fait exception des niveaux où l'on sait que des erreurs de tâches se trouveront, on a :
- Plus de tâches dans la version explicite car elle a des tâches (P2P, M2L) symetriques.
- Toutes les tâches issuent de l'algorithme implicite se retrouvent dans l'ensemble des tâches explicite.
- Toutes les tâches sont au moins mapper sur le même nœud MPI. Les tâches symetriques étant parfois mappé sur deux nœuds différents.

433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455
*** Comparaison des performances
Pour comparer les performances entre l'approche explicite et implicite, il a été décidé d'ajouté un nouveau test judicieusement nommé testBlockedImplicitChebyshev. Ainsi les comparaisons se font sur la base d'un véritable noyaux de calcul et non un noyaux de test peu réaliste. Les résultats sont déroulés dans la section [[sec:result]]. Notez que les temps indiqués ne correspondent qu'au temps de création des noyaux ainsi que de l'objet correspondant à l'algorithme de la FMM. N'est pas compris tout le temps passé à construire l'arbre, à stocker les particules ou a les lire dans un fichier et à vérifier le résultats.

Le temps passé est compté de la manière suivante :
#+BEGIN_SRC C
//Start the timer
FTic timerExecute; 
//Creating some useful object
const MatrixKernelClass MatrixKernel;
GroupKernelClass groupkernel(NbLevels, loader.getBoxWidth(), loader.getCenterOfBox(), &MatrixKernel);
GroupAlgorithm groupalgo(&groupedTree,&groupkernel, distributedMortonIndex);
//Executing the algorithm
groupalgo.execute();
//Stop the timer
double elapsedTime = timerExecute.tacAndElapsed(); 
//Sum the result
timeAverage(mpi_rank, nproc, elapsedTime);
#+END_SRC

Les résultats dénotent deux choses :
- L'algorithme implicite répartis mal les calculs.
- Une situation curieuse : Avec le noyaux de test, l'implicite est 10x plus rapide, avec le noyau de Chebyshev, il est 5x plus lent.

Martin Khannouz's avatar
Martin Khannouz committed
456 457 458 459
Après une petite étude, cette curieuse situation n'était pas dû à une mauvaise répartition des particules car ladite répartition est la même.

Il s'avéra que pour le calcul du P2P, tous les nœuds s'attendaient en cascade, mais ce temps d'attente peut être réduit en definissant la constante suivante : STARPU_USE_REDUX.
Cela active la reduction au niveau des P2P et nous offre les même performances que l'algorithme explicite.
460

461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481
*** Erreurs rencontrées
Un /bug/ a fait son apparition dans la version MPI explicit où des segfaults apparaissent si l'arbre n'a pas au moins une particule dans chaque indice de Morton.
Cette erreur n'impacte pas encore la bonne progression du stage, car dans la pratique, il y a suffisament de particules pour remplir l'arbre.

** Autre /mapping/
*** Treematch
Suite à la présentation par Emmanuel Jeannot de l'outil TreeMatch qui permettrait de proposer des /mapping/ intéressant, il serait bon de profiter dudit outil.
Une structure de fichier pour communiquer avec TreeMatch serait la suivante :
#+BEGIN_EXAMPLE
123 7
124:6000
45:3000
23:400
#+END_EXAMPLE
Cette structure (simpliste) se lirait de la manière suivante :
- Le groupe 123 est situé sur le nœud 7.
- Le groupe 123 échange 6000 octets avec le groupe 124.
- Le groupe 123 échange 3000 octets avec le groupe 45.
- Le groupe 123 échange 400 octets avec le groupe 23.

Les groupes correspondent aux /handles/ de Starpu qui correspondent aux groupes de l'arbre bloqué.
482 483 484 485
Problème : L'algorithme Treematch semble placer des /workers/ sur des « nœud de calcul » proche.
Typiquement, si deux process mpi communiquent beaucoup il faut les mettre plus proche. Or dans notre cas, si deux process mpi communiquent beaucoup c'est essentiellement car il partage les même données. Données qu'il faudrait remapper sur un autre nœud.
Mais c'est données n'impliquent pas de forcément des transitions de données mpi ... si elles sont sur le même nœud mpi.

Martin Khannouz's avatar
Martin Khannouz committed
486 487 488 489 490 491 492 493 494 495 496 497
** What have been done so far ?
- Un arbre groupé identique à celui de la version explicite
- Des tâches très similaires celles de la version explicite
	- Quelque erreurs cependant (TODO check si elles y sont encore, car je pense les avoir corrigées)
- Création de scripts
	- Tout exporter sur plafrim
	- Compiler et lancer les jobs
		- La version starpu sur un nœud à 50M de particules
		- Les versions starpu mpi explicite et implicite sur 10 nœuds à 50M de particules
	- Exporter l'html du orgmode vers la forge	
- Reflexion à propos du graphe de flux de données pour Treematch
- Ajout de tests avec le noyau Chebyshev et la versin mpi implicite
498
- Symétriser l'algorithme implicite au niveau des P2P
499 500 501
- Modifier les jobs pour qu'il utilisent la même graine et générent le même ensemble de particules
- Post traiter les traces d'une exécution pour créer des graphiques.
      - Exploiter les scripts de Samuel
502

503 504

** Et après ?
505 506
- Comparaison des performances
	- Répartition des GFlop
507 508
		- Utiliser le noyau FChebFlopsSymKernel
		- Éventuellement utiliser le noyau FTaylorFlopsKernel
509 510
	- Répartition du temps de calcul
	- Mémoire utilisée par nœud
511 512 513
      - Volume de communication
      - Répartition des communications tâche
        - Quel tâche consomme le plus de communication
514
- Étude d'autres /mapping/
515 516
	- Proposer un formalisme simple pour transmettre le graphe de flux de données (Treematch)
	- Proposer un formalisme simple pour transmettre la topologie (Treematch)
517 518 519 520
- Limiter l'empreinte mémoire
	- Ne pas allouer les cellules numériques si ce n'est pas necessaire (/up/ et /down/)
	- Ne pas allouer les cellules symboliques si ce n'est pas necessaire
	- Distribuer l'arbre
521
- Post traiter les traces d'une exécution pour créer des graphiques.
522 523 524
      - Modifier la génération du trace.rec
            - Pour récupérer le temps d'attente active des comm mpi
            - Pour qu'il réagisse bien en distribué
525 526 527 528
- Valider les résultats mpi explicite avec l'algorithme sequentiel plutôt que l'algorithme mpi non bloqué
	- Reproduire l'arbre globale
	- Ne comparer que les cellules du nœud
- État de l'art load balancing sur non-uniforme