Cours 7 — Programmation concurrente & calcul distribué

Patrick Fournier

MAT8186 — Techniques avancées en programmation statistiques R

Automne 2023

Programmation concurrente

Généralités

  • Objectif: gains en performance
  • Approches possibles
    • Améliorer algorithme
    • Améliorer implémentation
    • Améliorer hardware
    • Paralléliser

Limitations

  • Parallélisation ⇒ opérations supplémentaires
    • Ordonnancement (scheduling)
    • Communication inter-processus (IPC)
  • ∃ # processus optimal
    • Dépend du problème, algorithme, implémentation, environnement...

Type de parallélisme

  • Mémoire partagée
    • Toutes les unités de calcul (cores) partagent la même mémoire
  • Mémoire distribuée
    • Noeud (node): ensemble cores/mémoire
    • Chaque node possède une copie des données

Exemple: Mémoire partagée

Mémoire partagée

Exemple: Mémoire distribuée

Mémoire distribuée

Communication inter-processus (IPC)

  • ↗ # processus ⇒ ↗ puissance de calcul 😀
  • ↗ # processus ⇒ ↗ communications 😥
  • Souvent, principale source de ralentissement dù au parallélisme
    • Plus prononcé lorsque la mémoire est distribuée
  • Solution: optimiser la topologie

Exemple: Manager/Workers

⇔ Graphe biparti.

Managers/workers

Exemple: Fully Connected

⇔ Graphe complet.

Fully connected

Exemple: Ring

⇔ Cycle.

Ring topology

R & MPI

Paraléllisme en R

  • Plusieurs options
  • Package important: snow
  • Pour le calcul distribué (pas seulement sur R): MPI
  • Rmpi 🤝🏽 snow

Terminologie

  • Rank: id du processus
  • Master: manager, rang 0
  • Slave: worker, rang = 1, 2, etc.
  • Comm: canal de communication, 1, 2, etc

Commandes essentielles

  • Créer les workers: mpi.spawn.Rslaves
  • Détruire les workers: mpi.close.Rslaves
  • Quitter: mpi.finalize, mpi.quit
  • Faire exécuter une commande à tous les workers: mpi.bcast.cmd ou mpi.remote.exec
  • Obtenir le rang d'un worker: mpi.comm.rank
  • Exemple: basic.R

Communication point-to-point

  • MPI: Message Passing Interface
  • Opérations de base
    • Envoyer un message: mpi.send
    • Recevoir un message: mpi.recv
  • Arguments obligatoires
    • x, type, dest/source, tag
  • Exemple: ring_add.R

Exemple: ring_add.R

Exemple1 -- 0
Exemple1 -- 1
Exemple1 -- 2
Exemple1 -- 3

Communication blocante vs. non blocante

  • Comm. blocante: attend la fin de la communication avant de retourner
  • Comm. non blocante: retourne immédiatement!
  • mpi.isend, mpi.irecv
  • Comm non blocante > blocante
  • Risque de deadlock
  • Comm. non-blocantes dans ring_add.R

Exercice

  • Chaque worker recoit un entier de 1 à \( n \) différent
  • Il exécute la fonction dist0 avec \( m \) vallant cet entier
  • Le vecteur retourné est envoyé au manager qui les concatène
  • Le manager affiche le résultat

Communication collective

  • Exemple déjà vu: mpi.bcast.cmd
  • Même effet que mpi.send à tous les workers
  • Diviser une liste entre les workers: mpi.scatter.Robj2slave
  • Rassembler le résultat: mpi.gather.Robj
    • À appeller par chaque worker en plus du manager
  • Exemple: dist_scale.R

Exemple: dist_scale.R

dist_scale -- 0
dist_scale -- 1
dist_scale -- 2

Exercice

  • Calculez \( \pi \) en utilisant l'identité \( \pi = \int_0^1 \frac{4}{1 + x^2} \)
  • Utilisez \( m \) workers
  • Divisez \( [0, 1] \) en \( n \times m \) parties
  • Chaque worker calcule sa partie de la somme de Riemann
  • Le manager combine le tout et affiche le résultat

Embarassingly parallel problems

  • ∅ communication entre les workers ⇒ parallélisation facile
  • En R: lapply & cie

Exemples

  • Intégration numérique
  • Échantillonage préférentiel
  • Transformée de Fourier
  • Études de simulation
  • Algorithmes génétiques
  • Forêts aléatoires
  • Force brute

Snow et Rmpi

  • Simple network of workstations
  • Types de clusters
    • SOCK
    • MPI
  • Défaut: MPI si possible, SOCK sinon
    • MPI ↔ Rmpi disponible
  • cl <- makeCluster(n) et laisser Snow décider

Fonctions importantes

  • parLapply: comme vous pensez
    • Variantes existent
  • clusterCall: appelle une fonction
  • clusterExport: définit des variables