Programmation Parallèle Haute Performance PDF
Programmation Parallèle Haute Performance PDF
Programmation Parallèle Haute Performance PDF
Guy Tremblay
Hiver 2017
Table des matières
1
TABLE DES MATIÈRES 2
Références 791
Partie I
Introduction à la concurrence et au
parallélisme
6
Chapitre 1
Introduction : Programmation
concurrente et parallèle ⇒
transparents
7
Chapitre 2
8
Chapitre 3
• Thread :
– Un thread représente (généralement) une fonction (une méthode) en
cours d’exécution.
1
SP=Stack Pointer, FP=Frame Pointer, IP=Instruction Pointer.
2
Tas = heap.
9
Concepts de base 10
Figure 3.1: Processus vs. thread dans l’environnement Unix (source inconnue).
Concepts de base 11
Remarques :
• Il faut bien distinguer entre le programme en tant que «code» — code source
ou code compilé, une notion statique — et le programme en tant que «code
en cours d’exécution» — une notion dynamique.
Par exemple, un même programme Java — un même code (compilé) — peut
avoir plusieurs instances différentes en cours d’exécution (exemple Unix) :
$ javac Foo.java
$ java Foo & java Foo & java Foo &
– Programme séquentiel
– Programme concurrent
Est-ce vrai qu’un seul doigt suffit pour indiquer à quel endroit on est rendu dans
l’exécution d’un programme séquentiel?
Exercice 3.1: Un seul doigt suffit-il vraiment?
Concepts de base 13
Les figures 3.3 à 3.6 illustrent les différences entre applications multicontextes et
applications parallèles.
Concepts de base 14
Figure 3.3: Exécution concurrente non parallèle vs. exécution concurrente et paral-
lèle de throis threads : tiré de [SMR09].
Concepts de base 16
Figure 3.4: Exécution d’un programme effectuant des entrées/sortie de façon con-
currente avec threads vs. de façon séquentielle sans thread.
Figure 3.5: Exécution d’une application multicontextes sur une machine séquentielle
vs. une machine parallèle.
Concepts de base 18
Figure 3.6: Exécution d’une application parallèle sur une machine séquentielle vs.
une machine parallèle.
Concepts de base 19
1. Soit un programme P1 qui est IO-bound et qui s’exécute sur M1 en 1.6 secon-
des.
Si on exécute P1 sur M8 , quel temps d’exécution peut-on s’attendre à obtenir?
2. Soit un programme P2 qui est CPU-bound et qui s’exécute sur M1 est 1.6
secondes.
Si on exécute P2 sur M8 , quel temps d’exécution peut-on s’attendre à obtenir?
Exercice 3.2: Effet d’ajouter des coeurs sur des programmes CPU-bound ou IO-
bound.
Concepts de base 20
Remarques additionnelles :
• Les catégories qui précèdent ne sont pas mutuellement exclusives. Par ex-
emple, de nombreuses machines parallèles modernes, qu’on utilise essentielle-
ment pour développer des applications parallèles, sont des multi-ordinateurs,
donc des machines composées d’un ensemble de processeurs (avec mémoire dis-
tribuée) interconnectés par un réseau. On programme souvent ces machines
avec des langages de programmation où l’on doit tenir compte de la distribu-
tion (principalement des données) et où les échanges d’information se font par
l’envoi de messages.
• L’état d’un thread est caractérisé par les valeurs des variables du thread à
un instant donné, y compris les variables implicites, notamment le compteur
d’instruction (IP).
• Action atomique = Une action qui examine ou change l’état d’un thread de
façon indivisible.
Programme Ruby 3.1 Petit programme Ruby avec deux thread s simples.
PRuby . pcall (
-> { puts " Thr1 : ."
puts " Thr1 : .. "
puts " Thr1 : ... "
},
-> { puts " Thr2 : +"
puts " Thr2 : ++ "
puts " Thr2 : +++ "
}
)
Ici, c’est ce résultat qui est produit parce que les deux threads sont petits et
simples, et donc le premier thread peut s’exécuter rapidement et entièrement parfois
même avant que le deuxième thread ne s’exécute.
Concepts de base 23
Thr1: ..
Thr1: ...
Thr2: ++
Thr2: +++
Fin du programme
Concepts de base 24
Programme Ruby 3.2 Petit programme Ruby avec deux thread s simples, mais
avec des temps d’exécution variables.
def jiggle
sleep rand / 10.0
end
PRuby . pcall (
-> { puts " Thr1 : ."
jiggle
puts " Thr1 : .. "
jiggle
puts " Thr1 : ... "
},
-> { puts " Thr2 : +"
jiggle
puts " Thr2 : ++ "
jiggle
puts " Thr2 : +++ "
}
)
The reason that threading bugs can be infrequent, sporadic, and hard to
repeat, is that only a very few pathways out of the many thousands of
possible pathways through a vulnerable section can actually fail.
The point is to jiggle the code so that threads run in different orderings
at different times. The combination of well-written tests and jiggling can
dramatically increase the chance of finding errors.
Pour qu’un programme concurrent soit considéré correct, il doit produire le bon
résultat peu importe la vitesse à laquelle s’exécute chacun des thread s.
Soit alors le Programme PRuby 3.2, une version modifiée du Programme PRuby 3.1
dans lequel on a introduit un délai arbitraire d’exécution entre chacune des instruc-
Concepts de base 25
tions puts. Un tel délai — introduit ici par un appel à la méthode jiggle3 —
permet de modéliser explicitement des variations dans la vitesse d’exécution des
thread s, ce qui est souvent utile pour déboguer un programme concurrent.
L’exemple d’exécution 3.1 (p. 26) illustre divers résultats d’exécution possibles
du Programme Ruby 3.2 : les deux premiers éléments de la trace sont toujours
les mêmes — à cause de l’ordre de lancement des deux thread s et de l’absence de
jiggle au début du thread — mais ensuite l’ordre change d’une exécution à l’autre
(ou presque ,) selon la durée du délai aléatoire produit par jiggle. On peut noter
aussi la dernière exécution, où même les deux chaînes émises sur la sortie standard
sont entrelacées — l’une des chaînes s’imprime avant que le saut de ligne de la chaîne
précédente n’ait été imprimé.
3
Traduction de jiggle : secouer, se trémousser.
Concepts de base 26
$ ruby entrelacement.rb
Thr1: .
Thr2: +
Thr1: ..
Thr1: ...
Thr2: ++
Thr2: +++
Fin du programme
$ ruby entrelacement.rb
Thr1: .
Thr2: +
Thr2: ++
Thr2: +++
Thr1: ..
Thr1: ...
Fin du programme
$ ruby entrelacement.rb
Thr1: .
Thr2: +
Thr2: ++
Thr1: ..
Thr1: ...
Thr2: +++
Fin du programme
$ ruby entrelacement.rb
Thr1: .
Thr2: +
Thr2: ++
Thr2: +++Thr1: ..
Thr1: ...
Fin du programme
...
Programme Ruby 3.3 Programme avec deux thread s qui modifient une variable
partagée avec l’opération «+=».
x = 0
PRuby . pcall (
-> { x += 1 } ,
-> { x += 2 }
)
L’exemple d’exécution 3.2 donne alors des résultats possibles d’exécution, mon-
trant clairement la présence d’une situation de compétition.
Programme Ruby 3.4 Programme avec deux thread s qui modifient une variable
partagée avec l’opération «+=», mais avec des délais introduits entre les opérations
non-atomiques.
x = 0
PRuby . pcall (
-> { jiggle ; reg = x ; jiggle ; reg = reg + 1; x = reg } ,
-> { jiggle ; reg = x ; jiggle ; reg = reg + 2; x = reg }
)
4
En fait, dans une machine RISC typique, où les opérations arithmétiques se font uniquement
sur les registres, on aurait les (pseudo-)instructions suivantes :
LOAD r1, x
r1 = r1 + 1
STORE r1, x
Concepts de base 29
$ ruby competition2.rb
x = 2
$ ruby competition2.rb
x = 1
$ ruby competition2.rb
x = 3
$ ruby competition2.rb
x = 3
$ ruby competition2.rb
x = 2
Soit l’algorithme suivant, où l’on suppose que la ligne retournée est EOF lorsque la
fin de fichier est atteinte :
Programme Ruby 3.5 Programme avec deux thread s qui modifient une variable
partagée avec l’opération «+=», et ce à l’intérieur d’une section critique correctement
protégée par un verrou.
x = 0
PRuby . pcall (
-> { mutex . synchronize { x += 1 } } ,
-> { mutex . synchronize { x += 2 } }
)
Le programme Ruby 3.5 est une version révisée du programme Ruby 3.3, mais
cette fois sans situation de compétition, donc le programme imprimera toujours
«x = 3».
Dans les deux thread s, la modification de x est effectuée à l’intérieur d’une section
critique protégée par un verrou d’exclusion mutuelle — objet mutex instance de la
classe Mutex. Lorsqu’on utilise un tel verrou, le bloc de code qui suit synchronize
est assuré de s’exécuter de façon complètement atomique, sans interférence par
d’autres thread s exécutant eux aussi des sections critiques protégées par le même
verrou!
Concepts de base 32
Soit le segment de code Ruby suivant qui trouve l’élément maximum parmi un
tableau de nombres entiers positifs :
a = [10 , 62 , 173 , 823 , 32 , 99 , 9292 , 0 , 1]
m = 0
PRuby . pcall ( 0... a . size ,
- >( i ) { m = a [ i ] if a [ i ] > m }
)
Programme Ruby 3.6 Petit programme Ruby illustrant une situation potentielle
d’interblocage.
mut1 = Mutex . new
mut2 = Mutex . new
PRuby . pcall (
-> { mut1 . synchronize {
mut2 . synchronize {
puts " Dans thr1 "
}
}
},
-> { mut2 . synchronize {
mut1 . synchronize {
puts " Dans thr2 "
}
}
}
)
Par contre, dans certains cas, . . . rien n’arrive, rien n’est imprimé! Pour ex-
pliquer ce dernier comportement, supposons la séquence suivante d’exécution des
instructions de thr1 et thr2 — i.e., un entrelacement possible de l’exécution de
Concepts de base 35
leurs instructions — obtenu par exemple en ajoutant «jiggle» dans thr1 après
l’acquisition du premier verrou :
Dans cet exemple où deux verrous sont utilisés, la solution pour éviter un in-
terblocage est relativement simple : il faut toujours acquérir les deux verrous dans
le même ordre, donc interchanger les deux premières instructions de thr2.
Concepts de base 36
Ce dernier cas tient au fait que dans certains langages, les threads d’un pro-
gramme peuvent être considérés comme des unités d’exécution, dans la mesure où
on lance au départ un certain nombre de threads, qui exécutent ensuite les diverses
tâches exprimés par l’algorithme et le programme.
Dans les chapitres qui suivent, nous réserverons donc la notion de thread pour
des objets actifs créés et manipulés par le langage utilisé pour programmer notre
algorithme parallèle. Dans ce qui suit, nous traiterons plutôt de tâches, au niveau
logique et algorithmique.
Concepts de base 37
Au niveau algorithmique, on commence par identifier les tâches les plus fines
possibles (granularité aussi fine que nécessaire en fonction du problème : voir plus
bas), sans tenir compte des ressources ou contraintes de la machine — en d’autres
mots, on suppose une machine «idéale» avec des ressources illimitées.
Ensuite, on détermine les dépendances entre ces tâches : si une tâche T1 doit
s’exécuter avant une tâche T2 , par exemple parce que T1 produit un résultat utilisé
par T2 , alors on dit qu’il y a une dépendance (de données) de T1 vers T2 . On peut
ainsi construire un graphe des dépendances de tâches. Ce graphe ne permet
ensuite de mieux comprendre le comportement de l’algorithme parallèle.
C’est souvent aussi à partir de ce graphe qu’on pourra développer un programme
parallèle efficace, qui tiendra compte des ressources matérielles — par exemple,
pour diminuer les coûts de synchronisation et communication, on pourra décider
de combiner ensemble des petites tâches pour obtenir des tâches plus grosses. On
traitera de ces questions dans un chapitre ultérieur.
Concepts de base 38
p(x) = ax2 + bx + c
Une racine r de p(x) est une valeur telle que p(r) = 0. Pour un polynome
de 2e degré, la formule suivante permet de trouver les racines, en supposant ici
qu’au moins une racine existe (b2 ≥ 4ac) :
√
−b + b2 − 4ac
r1 =
2a
√
−b − b2 − 4ac
r2 =
2a
Pour cet exemple, nous allons décomposer le calcul de r1 en une suite d’instructions
simples dites «à trois adresses», soit deux opérandes, une destination pour le résultat
et un opérateur — donc des pseudo-instructions machines ou du pseudo code-octet.
Ce seront alors ces instructions qui représenteront nos tâches à paralléliser.
Remarque : En pratique, on ne procèra généralement pas à une décomposition
aussi fine des instructions. Ici, on le fait pour illustrer plus clairement les notions
de dépendances et de graphes de dépendances.
Voici un segment de code pour calculer la racine r1 et l’affecter à la variable r1 :
t0 = -1 * b
t1 = b * b
t2 = 4 * a
t3 = t2 * c
t4 = t1 - t3
t5 = sqrt t4
t6 = t0 + t5
t7 = 2 * a
r1 = t6 / t7
La Figure 3.7 présente un graphe de dépendances pour ces tâches :
• Un cercle dénote une tâche. Son contenu indique l’instruction à exécuter pour
cette tâche.
• Une flèche allant d’une tâche vers une autre indique que la deuxiême tâche
— celle au bout de la flèche — ne peut s’exécuter que lorsque la première a
Concepts de base 39
Figure 3.7: Graphe de dépendances des tâches pour le calcul de la racine r1 d’un
polynome de 2e degré.
Concepts de base 40
Temps Degré de
parallé-
lisme
0 4
1 1
2 1
3 1
4 1
5 1
Figure 3.8: Version révisée du graphe de dépendances des tâches pour le calcul de
la racine r1 d’un polynome de 2e degré.
Concepts de base 43
Dans notre exemple, comme on le voit bien dans la Figure 3.8, la longueur du
chemin critique est de 5. En supposant que chaque tâche s’exécute en une (1)
unité de temps, il faudra donc, au mieux, 6 unités de temps pour que l’algorithme
s’exécute.
Plus exactement, le meilleur temps d’exécution possible varie en fonction du
nombre d’unités d’exécution disponibles, comme l’indique le tableau suivant :
Nb. Temps
d’UE min.
1 9
2 6
3 6
4 6
... ...
Voici par contre une autre cédule, qui conduit à un temps d’exécution plus long :
0: t0, t1
1: t2, t7
2: t3
3: t4
4: t5
5: r6
6: r7
• On dit d’un algorithme (ou d’un programme) parallèle qu’il est dimensionnable
(scalable) lorsque son degré de parallélisme augmente au moins de façon linéaire
avec la taille du problème.5
• On dit d’une architecture qu’elle est dimensionnable si la machine continue
à fournir les mêmes performances par processeur lorsque l’on accroît le nombre
de processeurs.
5
«Scalability is a parallel system’s ability to gain proportionate increase in parallel speedup with
the addition of more processors.» [Gra07].
Concepts de base 46
If the granularity is too fine, the performance can suffer from the in-
creased communication overhead. On the other side, if the granularity
is too coarse, the performance can suffer from load imbalance.
Source : http: // en. wikipedia. org/ wiki/ Granularity
Note : Dans le cas d’un programme parallèle avec mémoire partagée, on peut
substituer «communication» par «synchronisation».
On discutera de la notion de granularité plus en détail lorsqu’on traitera de
méthodologie de programmation parallèle.
Concepts de base 47
Concepts de base 48
Figure 3.9: Graphe de flux de données pour le calcul de la racine r1 d’un polynome
de 2e degré.
Concepts de base 49
t0 = a[0] + a[1]
t1 = t0 + a[2]
t2 = t1 + a[3]
t3 = t2 + a[4]
t4 = t3 + a[5]
t5 = t4 + a[6]
somme = t5 + a[7]
t0 = a[0] + a[1]
t1 = a[2] + a[3]
t2 = a[4] + a[5]
t3 = a[6] + a[7]
t4 = t0 + t1
t5 = t2 + t3
somme = t4 + t5
Programme Ruby 3.7 Algorithme récursif pour effectuer la sommation des élé-
ments d’un tableau.
def somme ( a , i , j )
if i == j
a[i]
else
mid = ( i + j ) / 2
• Certaines tâches — branche then vs. branche else — sont exécutées unique-
ment si une certaine condition est satisfaite. Dans ce cas, on parle alors d’une
dépendance de contrôle. Ici, ce type dépendance est indiqué par une flèche
en pointillée, la tâche qui calcule la condition étant indiquée par un rectangle
pointillé aux coins arrondis.
Concepts de base 55
Figure 3.15: Arbre d’activations des instances de fonction pour le calcul récursif de
la sommation des éléments d’un tableau de 8 éléments.
Quant à la Figure 3.15, elle présente un arbre d’activation des fonctions pour
le calcul récursif de la somme des éléments d’un tableau comptant 8 éléments. On
constate que la structure de cet arbre est elle aussi semblable à la structure du
Concepts de base 56
Plus formellement :
L(P1 ) ∩ E(P2 ) = {}
L(P2 ) ∩ E(P1 ) = {}
E(P1 ) ∩ E(P2 ) = {}
Ruby concurrency is when two tasks can start, run, and complete in
overlapping time periods. It doesn’t necessarily mean, though, that they’ll
ever both be running at the same instant (e.g., multiple threads on a
single-core machine). In contrast, parallelism is when two tasks liter-
ally run at the same time (e.g., multiple threads on a multicore proces-
sor).
[. . . ]
Ruby concurrency without parallelism can still be very useful, though, for
tasks that are IO-heavy6 (e.g., tasks that need to frequently wait on the
network).
Source : https: // www. toptal. com/ ruby/ ruby-concurrency-and-parallelism-a-practical-primer
Dans ce qui suit, nous allons présenter un problème avec parallélisme dont le
programme est CPU-bound, puis un problème avec concurrence dont le programme
est IO-bound. Dans ce dernier cas, nous verrons que même si Ruby/MRuby ne
permet pas le «vrai» parallélisme, un programme concurrent peut quand même
s’exécuter plus rapidement qu’un programme séquentiel.
6
IO-bound.
Concepts de base 59
def somme_threads ( a )
def bornes_tranche ( k , n , nb_threads )
b_inf = k * n / nb_threads
b_sup = ( k + 1) * n / nb_threads - 1
b_inf .. b_sup
end
nb_threads = 10
threads = (0... nb_threads ). collect do | k |
Thread . new { sommation_seq ( a , bornes_tranche (k , a . size , nb_threads ) ) }
end
Benchmark . bmbm do | bm |
bm . report ( ’ sequentiel ’ ) do
somme_seq ( a )
end
def titre_du_cours_seq
COURS . collect { | cours | titre_du_cours ( cours ) }
end
def titre_du_cours_threads
threads = COURS . collect do | cours |
Thread . new { titre_du_cours ( cours ) }
end
threads . map (&: value )
end
Benchmark . bmbm do | bm |
bm . report ( ’ sequentiel ’ ) do
titre_du_cours_seq
end
Figure 3.16: Temps pour diverses exécutions pour la «somme» des éléments d’un
tableau. (Exécution sur japet.labunix.uqam.ca)
Concepts de base 63
Figure 3.17: Temps pour diverses exécutions pour la lecture et l’analyse d’une liste
d’URIs. (Exécution sur japet.labunix.uqam.ca)
Concepts de base 64
NB = 20
loop do
a = Array . new
futures = []
(0... NB ). each do | i |
futures << PRuby . future { a [ i ] = 0 }
end
65
Chapitre 4
66
Ruby 67
Figure 4.2: Les 10 premières positions du palmarès «The 2016 Top Programming
Languages» (IEEE Spectrum).
Selon une enquête faite par la revue IEEE Spectrum en 2016,1 Ruby est parmi
les 10 langages de programmation les plus utilisés : voir Figure 4.2.
Note : «Rankings are created by weighting and combining 12 metrics from 10
sources.»
Philosophie de Ruby
Ruby, comme Perl et Python [Bla04], est un langage à typage dynamique — un
langage dit de «script» — avec une syntaxe flexible (on verra comment plus loin) :
Ruby. . . est un langage open-source dynamique qui met l’accent sur la
simplicité et la productivité. Sa syntaxe élégante en facilite la lecture et
l’écriture. https: // www. ruby-lang. org/ fr/
# JRuby # MagLev
jruby-1.6.8 maglev[-head]
maglev-1.0.0
jruby[-1.7.19]
jruby-head # Mac OS X Snow Leopard Or Newer
jruby-9.0.0.0.pre1 macruby-0.10
macruby-0.11
# Rubinius macruby[-0.12]
macruby-nightly
rbx-1.4.3
macruby-head
rbx-2.4.1
rbx[-2.5.2] # IronRuby
rbx-head ironruby[-1.1.3]
ironruby-head
# Opal
opal
Figure 4.4: Quelques organisations qui utilisent JRuby. Source : «JRuby 9000 Is Out;
Now What?, T. Enebo and C. Nutter, RubyConf 2015, https://www.youtube.com/watch?v=
KifjmbSHHs0
Ruby 73
$ ruby hello0 . rb
Bonjour le monde !
------------------------------------
$ cat hello1 . rb
# !/ usr / bin / env ruby
$ ls -l hello1 . rb
- rwxr - xr - x . 1 tremblay tremblay 46 26 jun 09:52 hello1 . rb *
$ ./ hello1 . rb
Bonjour le monde !
>> 2 + 4
=> 6
>> 8 * 100 / 2
= > 400
>> _ + _
= > 800
>> _ / 3
= > 266
>> _ / 3.0
= > 88.66666666666667
# On peut creer une nouvelle " session " ( interne ) qui modifie self ,
# l ’ objet courant .
>> irb [10 , 20]
>> self
= > [10 , 20]
>> size
=> 2
>> ^ D
= > #< IRB :: Irb : @context =#< IRB :: Context :0 x0000000170a660 > ,
@signal_status =: IN_EVAL , @scanner =#< RubyLex :0 x0000000191a7c0 > >
>> self
= > [10 , 20]
Ruby 76
4.4 Tableaux
>> a [0]
= > 10
>> a [2]
= > 30
>> a [2] = 55
= > 55
>> a
= > [10 , 20 , 55]
>> a . size
=> 3
>> a . size
=> 3
>> a [5] = 88
= > 88
>> a . size
= > ??
>> a
= > ??
Ruby 78
>> a [ -1]
= > 88
• L’indice du dernier élément d’un tableau a est a.size-1. On peut aussi ac-
cèder au dernier élément avec l’indice -1, à l’avant-dernier avec l’indice -2,
etc.
Ruby 79
Exemple Ruby 4.4 Les tableaux et leurs opérations de base (suite 1).
? > # Tableaux heterogenes .
?> a
= > [10 , 20 , 55 , nil , nil , 88]
>> a
= > [10 , 20 , 55 , nil , nil , 88 , nil , nil , " abc " ]
>> a << 12
= > [12]
• Les tableaux sont hétérogènes, i.e., ils peuvent contenir des éléments de types
variés.
Ruby 80
• Une opération fréquemment utilisée est push, qui a comme alias «<<».
Exemple Ruby 4.5 Les tableaux et leurs opérations de base (suite 2).
? > # Tranches de tableaux .
? > a = [10 , 20 , 30 , 40 , 50]
= > [10 , 20 , 30 , 40 , 50]
>> a [0..2]
= > [10 , 20 , 30]
>> a [3..3]
= > ??
>> a [7..7]
= > ??
3
Voir http://ruby-doc.org/core-2.2.0/Array.html pour la liste complète.
Ruby 81
>> a [1..3]
= > [20 , 30 , 40]
>> a [1...3]
= > [20 , 30]
>> s1 . size
=> 3
>> s1
= > " abc "
>> s1
= > " abcdef "
• L’opération «+» concatène deux chaînes pour produire une nouvelle chaîne
(opération fonctionnelle, immuable) alors que l’opérateur «<<» ajoute (append)
des caractères à la fin d’une chaîne existante (opération impérative, mutable).
Exemple Ruby 4.7 Les chaînes de caractères et leurs opérations de base (suite).
>> # Egalite de valeur * sans * partage de reference .
? > a , b = ’ abc ’ , ’ abc ’
= > [ " abc " , " abc " ]
>> a == b
= > true
>> a . equal ? b
= > false
>> a [0] = ’X ’
=> "X"
>> a
= > " Xbc "
>> b
= > " abc "
• En Ruby, il est considéré de bon style qu’une méthode qui retourne un booléen
se termine par «?», par exemple, equal?, empty?, nil?, block_given?, etc.
Ruby 84
>> a == b
= > true
>> a . equal ? b
= > true
>> a [0] = ’X ’
=> "X"
>> a
= > " Xbc "
>> b
= > " Xbc "
• Une chaîne produite avec les doubles guillemets permet d’interpoler une ou
des expressions. Dans une telle chaîne, «#{...}» indique alors une expression
qui doit être évaluée — on dit aussi interpolée. Si cette expression produit un
résultat qui n’est pas une chaîne, alors la méthode to_s sera implicitement
appelée — voir plus bas.
• On peut aussi définir une chaîne avec de simples guillemets, mais dans ce cas
aucune interpolation n’est effectuée (chaine textuelle).
>> s
= > " abc \ ndef \ nghi \ n "
>> r . join ( " \ n " ) # Donc : s . split ("\ n "). join ("\ n ") != s
= > " abc \ ndef \ nghi "
• Une sous-chaine peut être la chaine vide ("") si la chaine continent deux
séparateurs consécutifs ou si la chaine débute ou se termine par un séparateur.
4.6 Symboles
>> : a . object_id
= > 365128
>> : a . object_id
= > 365128
Ainsi, bien que deux chaînes peuvent avoir la même valeur tout en étant
distinctes l’une de l’autre — ch1 == ch2 mais !(ch1.equal? ch2) — ce n’est
pas le cas avec les symboles — sym1 == sym2 implique sym1.equal? sym2.
• Les symboles sont souvent utilisés comme clés pour les hashes, de même que
pour les keyword arguments — voir plus bas.
Ruby 89
>> " abc " . to_sym . equal ? " abc " . to_sym
= > true
Ruby 90
4.7 Hashes
>> # Indexation .
? > hash [: abc ]
= > ??
>> hash [: de ]
= > ??
>> hash
= > {: abc = >2300 , : de = >2 , : ghijk = >5 , " de " = >55}
Exemple Ruby 4.13 Les hashes et leurs opérations de base (suite) : Création et
initialisation.
? > # Creation d ’ un Hash sans valeur par defaut .
? > h1 = {} # Idem : h1 = Hash . new
= > {}
>> h1 [: xyz ]
= > nil
>> h2 [: xyz ]
=> 0
>> h2 [: abc ] += 1
=> 1
Ruby 92
>> p h3 [: x ] , h3 [: y ]
[]
[]
= > [[] , []]
>> p h4 [: x ] , h4 [: y ]
[]
[]
= > [[] , []]
• Si aucune valeur par défaut n’a été spécifiée pour un hash, la valeur retournée
pour une clé non définie est nil. Par contre, au moment de la création du
hash, il est possible de spécifier la valeur qui doit être retournée par défaut,
i.e., la définition à retourner si la clé n’est pas explicitement définie.
Attention : Avec la forme simple de valeur initiale — Hash.new(v) — la
valeur v est la même pour toutes les clés. Si v est un tableau, il sera donc
partagé par toutes les clés — ce qui n’est généralement pas l’effet désiré.
Pour associer un tableau vide à chaque nouvelle clé, il faut plutôt utiliser
la forme avec un bloc, lequel reçoit en argument l’objet Hash (h) et la clé
nouvellement rencontrée (k).
Ruby 94
• En Ruby, toute valeur différente de false ou nil peut être interprétée comme
une valeur «vraie».
• Bien que nil et false soient tous deux faux, seul nil est nil?.
Ruby 96
• Bien qu’il existe aussi des opérateurs and et or, on utilise plutôt les opérateurs
&& et ||.
Ces derniers opérateurs sont évalués en mode «court-circuité». En d’autres
mots, on évalue uniquement la portion d’expression nécessaire pour s’assurer
que le résultat soit vrai ou faux, selon l’opérateur utilisé — puisqu’on a que
«false && x == x» et que «true || x == x».
Ruby 97
>> x
NameError : undefined local variable or method ’x ’ for main : Object
[...]
>> x ||= 3
=> 3
>> x
=> 3
>> x ||= 8
=> 3
>> x
=> 3
Une autre façon d’interpréter son comportement est de dire qu’il retourne la
première valeur non fausse (différente de false ou de nil), ou sinon la dernière
valeur.
• L’opérateur «||=» est semblable, mais pas complètement, à l’opérateur «+=»
— et à de nombreux autres opérateurs — en ce qu’il dénote une forme abréviée
d’une expression binaire :5
x += 1 # x = x + 1
x /= 2 # x = x / 2
• On utilise souvent l’opérateur «||=» pour donner une valeur initiale à une
variable à la condition qu’elle ne soit pas déjà initialisée.
5
http://www.rubyinside.com/what-rubys-double-pipe-or-equals-really-does-5488.
html
Ruby 99
>> add ( 2 , 3 )
=> 5
>> add 20 , 30 # Les parentheses sont optionnelles .
=> 50
>> abs ( 3 )
=> 3
>> abs ( -3 )
=> 3
-x
end
>> abs2 ( 23 )
=> 23
>> abs2 ( -23 )
=> 23
Ruby 100
• Dans un if, le then n’est requis que si on utilise le if comme expression sur
une seule ligne — les règles de style de Ruby veulent qu’on omette le then si
le if est écrit sur plusieurs lignes.
• Le résultat retourné par une méthode est la dernière expression évaluée par
la méthode. Les méthodes add suivantes sont donc équivalentes — mais la
première est considérée d’un «meilleur style» :
def add ( x , y )
x + y
end
def add ( x , y )
return x + y
end
Le style Ruby veut que return soit utilisée seulement pour retourner un ré-
sultat «au milieu» d’une série d’instructions, i.e., avant la dernière instruction
ou expression d’une méthode. La méthode abs2 illustre une telle utilisation.
• Remarque importante : Comme l’illustre l’un des exemples, les parenthèses
pour un appel de méthodes peuvent être omises. Par contre, si ces parenthèses
sont présentes, alors il ne doit pas y a avoir d’espaces entre le nom de la
méthode et les parenthèses, car dans ce dernier cas, les parenthèses pourraient
indiquer le début d’une expression complexe :
add ( 2 , 3 ) # OK ,
add 2 , 3 # OK ,
add ( 2 , 3 ) # Pas OK /
add (1+1) , (2+1) # OK ,
Ruby 101
>> 2.+( 3 )
=> 5
>> 2.+ 3
=> 5
>> 2. send ( :+ , 3 )
=> 5
• Les opérateurs (dits «infixes») pour les expressions sont des méthodes comme
les autres. Une expression telle que «2 + 3» est donc un appel à la méthode
«+» de l’objet «2» avec l’objet «3» comme argument.
>> div ( 12 , 3 )
=> 4
>> div ( 12 , 0 )
RuntimeError : Oops ! Division par zero :(
from ( irb ):4:in ’ div ’
[...]
from / home / tremblay /. rvm / rubies / jruby -1.7.16.1/ bin / irb :13:in ’( root ) ’
x / y
end
>> div ( 12 , 3 )
=> 4
• Tel qu’indiqué précédemment, le caractère «;» est utilisé seulement pour sé-
parer des instructions apparaissant sur une même ligne. Contrairement aux
langage C et Java, le «;» ne sert donc pas à terminer une instruction — un
saut de ligne suffit.
• Lorsqu’une instruction simple doit être exécutée de façon conditionnelle, il est
considéré de bon style d’utiliser une garde, donc :
instruction_simple if condition
if condition
instruction_simple
end
Dans un tel cas, il est aussi suggéré de toujours utiliser une condition positive,
si nécessaire en utilisant unless. Exemple : on veut retourner le premier
élément d’un tableau a si un tel élément existe :
return a[0] unless a.empty?
... plutôt que ...
return a[0] if !a.empty?
while b > 0
a, b = b, a % b
end
a
end
>> pgcd ( 12 , 8 )
=> 4
>> pgcd ( 80 , 120 )
=> 40
Ruby 104
• Une instruction while s’exécute tant que la condition indiquée reste vraie (i.e.,
non false, non nil).
x , y = [10 , 20 , 30]
# x == 10 && y == 20
x , * y = [10 , 20 , 30]
# x == 10 && y == [20 , 30]
Ruby 105
Exemple Ruby 4.22 Structures de contrôles : Itération sur les index avec for et
each_index.
? > # Instruction for
def somme ( a )
total = 0
for i in 0... a . size
total += a [ i ]
end
total
end
total
end
Exemple Ruby 4.23 Structures de contrôles : Itération sur les éléments avec for
et each.
? > # Instruction for ( bis )
def somme ( a )
total = 0
for x in a
total += x
end
total
end
total
end
• Une expression telle que 0..n est un Range (intervalle) qui génère les valeurs
0, 1, . . . , n. Par contre, un Range tel que 0...n génère les valeurs 0, 1, . . . , n-1.
On parle donc de Range inclusif (..) vs. exclusif (...) — voir plus haut.
Une boucle telle que «for i in 0...a.size» permet donc traiter tous les
indices valides de a, donc 0, 1, . . . , a.size-1.
Exemple Ruby 4.24 Paramètres des méthodes : valeur par défaut et nombre
variable d’arguments.
? > # Argument optionnel et valeur par defaut .
def foo ( x , y = 40 )
x + y
end
>> foo ( 3 , 8 )
= > ??
>> foo ( 3 )
= > ??
>> bar ( 1 , 2 , 3 , 4 , 5 )
= > ??
>> bar ( 1 , 2 )
= > ??
>> bar ( 23 )
??
??
??
??
Exemple Ruby 4.25 Paramètres des méthodes : arguments par mots-clés (keyword
arguments).
>> # Arguments par mot - cles ( keyword arguments ).
def diviser ( numerateur : , denominateur : 1 )
numerateur / denominateur
end
>> diviser 10
ArgumentError : missing keyword : numerateur
from ( irb ):31
from / home / tremblay /. rvm / rubies / ruby -2.1.4/ bin / irb :11:in ’ < main > ’
• Depuis Ruby 2.0,6 on peut définir des méthodes où les paramètres et arguments
sont définis par des mots-clés — keyword arguments — donc semblables à ce
qu’on retrouve en Smalltalk [Gol89].
• Les paramètres par mot-clés permettent de spécifier les arguments lors d’un
appel de méthode sans avoir à respecter un ordre strict quant à la position des
arguments — voir les deux premiers appels à diviser.
• On peut, ou non, spécifier une valeur par défaut pour les arguments par mots-
clés.
6
On peut aussi définir de telles méthodes en Ruby 1.9, mais pour ce faire il faut manipuler
explicitement un hash.
Ruby 110
• De tels paramètres sont souvent utiles pour les arguments optionnels, par
exemple, res_si_absent. La présence du mot-clé rend alors l’appel plus clair
quant au rôle de l’argument additionnel.
Ainsi, la méthode premier_index aurait pu être définie et utilisée comme suit,
mais le rôle de l’argument additionel aurait été moins clair :
def premier_index ( a , x , res_si_absent = nil )
...
end
x * y
end
Indiquez ce qui sera affiché par chacun des appels suivants :
# a.
puts foo ( 2 , 3 )
# b.
puts foo 2 , 3 , 5
# c.
puts foo ( " ab " , " cd " , 3 )
# d.
puts foo ( " ab " , " cd " )
# b.
puts bar ( 123 )
# c.
puts bar ( 0 , 10 , 20 , 99 , 12 )
puts foo ( 10 , 20 , 30 )
Qu’est-ce qui sera affiché?
Exercice 4.3: Définition d’une méthode avec plusieurs sortes d’arguments.
Ruby 113
Exemple Ruby 4.26 Un script avec une classe (simple) pour des cours.
$ cat cours . rb
# Definition d ’ une classe ( simple !) pour des cours .
class Cours
attr_reader : sigle
def to_s
sigles_prealables = " "
@prealables . each do | c |
sigles_prealables << " #{ c . sigle } "
end
Exemple Ruby 4.26 Un script avec une classe (simple) pour des cours (suite).
if $0 == __FILE__
# Definition de quelques cours .
inf1120 = Cours . new ( : INF1120 , ’ Programmation I ’ )
inf1130 = Cours . new ( : INF1130 , ’ Maths pour informaticien ’ )
inf2120 = Cours . new ( : INF2120 , ’ Programmation II ’ ,
inf1120 )
inf3105 = Cours . new ( : INF3105 , ’ Str . de don . ’ ,
inf1130 , inf2120 )
puts inf1120
puts inf3105
puts inf1120 . sigle
puts inf1120 . titre
end
Ruby 114
Exemple Ruby 4.27 Appel du script avec une classe pour des cours.
$ ruby cours . rb
< INF1120 ’ Programmation I ’ ( ) >
< INF3105 ’ Str . de don . ’ ( INF1130 INF2120 ) >
INF1120
NoMethodError : undefined method ‘ titre ’ for #< Cours :0 x13969fbe >
( root ) at cours . rb :34
• Une définition de classe est introduite par le mot-clé class, suivi du nom de
la classe, suivi des attributs et méthodes, suivi de end.
• Il n’est possible d’accèder à un attribut d’un objet que si une méthode appro-
priée, publique, a été définie.
Ruby 115
Pour la classe Cours, définissez une méthode qui permet d’obtenir le titre d’un cours
et une autre méthode qui permet de modifier le titre d’un cours.
Utilisez ensuite cette dernière méthode pour changer le titre du cours inf1120 en
"Programmation Java I".
Exercice 4.4: Méthodes pour lire et modifier le titre d’un cours.
7
Un getter dans la terminologie Java.
Ruby 116
4.13 Lambda-expressions
Les lambda-expressions — λ-expressions — sont le fondement de la programmation
fonctionnelle.
Ruby 117
• Une lambda-expression peut être vue comme une «fonction anonyme» — une
Ruby 119
fonction ou méthode sans nom. On peut affecter une telle expression à une
variable, qui réfère alors à cette fonction.
• Une lambda-expression peut aussi être vue comme une expression dont on
retarde l’exécution, expression qui ne sera évaluée qu’au moment où on fera
un appel explicite à call.
• Une lambda-expression est dénotée par le mot clé lambda suivi d’un bloc. Le
style Ruby veut qu’on utilise l’une de deux notations possibles pour les blocs :
– Si le bloc est court (une seule ligne), on utilise «{...}».
– Si le bloc comporte plusieurs lignes, on utilise «do...end», sur des lignes
distinctes.
Règle générale, dans ce qui suit, nous respecterons ce style, sauf parfois pour
rendre plus compacte la mise en page du texte ou des diapositives.
Exemple Ruby 4.29 Les lambda-expressions, comme n’importe quel autre objet,
peuvent être transmises en argument.
>> # Une methode pour executer deux fois du code ( sans arg .).
def deux_fois ( f )
f . call
f . call
end
• Dans plusieurs cas, on retrouve une structure semblable à celle de cet exemple,
à savoir, une méthode qui exécute un unique bloc de code reçu en dernier argu-
ment. Bien que cela puisse faire avec des lambdas, comme l’illustre l’exemple,
Ruby rend cela encore plus facile avec les blocs, qu’on verra à la prochaine
section.
Exemple Ruby 4.30 Les lambda-expressions, comme n’importe quel objet, peu-
vent être retournées comme résultat d’une fonction.
• Une lambda-expression étant un objet comme n’importe quel autre, elle peut
être retournée comme résultat d’une méthode, ou même d’une autre lambda-
expression.
Ruby 122
Exemple Ruby 4.31 Le bloc d’une lambda-expression capture les variables non-
locales.
? > # Le bloc d ’ une lambda - expression ’ capture ’
# les variables non - locales utilisees dans le bloc .
? > x = 23
= > 23
>> x = 999
= > 999
/INF/ =~ x
Exemple Ruby 4.32 Les appels à une lambda-expression peuvent aussi être faits
avec «.()» plutôt qu’avec call — mais c’est rarement utilisé!
>> lambda { 0 }.()
=> 0
>> inc .( 3 )
=> 4
Ruby 125
4.14 Blocs
Un bloc est un segment de code entre accolades {. . . } ou entre do. . . end :
a . each_index do |i|
total += a[i]
end
L’utilisation des blocs en Ruby est étroitement liée à l’instruction yield. Voici
tout d’abord quelques définitions du verbe anglais «to yield » :
Exemple Ruby 4.33 Une méthode pour exécuter deux fois un bout de code —
avec un bloc.
>> # Une autre methode pour executer deux_fois du code , avec bloc !
def deux_fois
yield
yield
end
>> deux_fois do
print ’ Bonne ’
print ’ journee !\ n ’
end
Bonne journee !
Bonne journee !
= > nil
>> deux_fois
LocalJumpError : no block given ( yield )
from ( irb ):1:in ’ deux_fois ’
from ( irb ):3
from / home / tremblay /. rvm / rubies / ruby -2.1.4/ bin / irb :11:in ’ < main > ’
Ruby 127
>> k_fois ( 3 ) do
print ’ Bonne ’
print ’ journee !\ n ’
end
Bonne journee !
Bonne journee !
Bonne journee !
• Un bloc est indiqué par un bout de code entre {...} (lorsque sur la même
ligne) ou do... end (lorque sur plusieurs lignes).
• Toute méthode, en plus des arguments explicites, peut recevoir un bloc comme
argument implicite. Ce bloc–argument étant implicite, il n’a pas besoin d’être
indiqué dans la liste des arguments — bien qu’il puisse l’être : voir plus loin.
Exemple Ruby 4.34 Une méthode pour évaluer une expression — avec lambda,
avec bloc implicite et avec bloc explicite.
>> # Methode pour evaluer une expression : avec lambda .
def evaluer ( x , y , expr )
expr . call ( x , y )
end
>> evaluer ( 10 , 20 ) { |a , b | a * b }
= > 200
>> evaluer ( 10 , 20 ) { |a , b | b / a }
=> 2
>> evaluer ( 10 , 20 ) { |a , b | b / a }
=> 2
>> evaluer ( 10 , 20 )
=> 0
Ruby 129
>> foo
= > nil
>> foo { 2 }
= > [ Proc , 0 , []]
>> foo { | x | x + 1 }
= > [ Proc , 1 , [[: opt , : x ]]]
• De la même façon qu’un lambda peut recevoir des arguments, un bloc peut
aussi en recevoir.
• Si le dernier paramètre de l’en-tête d’une méthode est préfixé par «&», alors
le bloc transmis à l’appel de la méthode sera associé à cet argument, donc le
bloc devient explicite. Dans ce cas, c’est comme si le bloc avait été transformé
en un lambda et associé au paramètre ; on peut donc l’appeler explicitement
avec call, mais aussi l’exécuter avec yield.
Même question que la précédente, mais cette fois en utilisant un bloc implicite pour
le prédicat plutôt qu’une lambda-expression.
Exercice 4.6: Une méthode pour identifier un sous-ensemble de préalables d’un
cours.
Ruby 130
Ruby utilise un certain nombre de sigils pour indiquer la portée des variables
— pour indiquer dans quelles parties du programme une variable est connue et
accessible :
Matz [the designer of Ruby] stated more than one time that sigils for
globals and for instance variables are there to remind you that you should
not use them directly. You should encode the global information in a class
or a constant, and access the instance variables via accessor methods.
When you’re writing quick & dirty code you can use them, but globals
are evil and the sigils are there to reify a code smell.
Source : http: // c2. com/ cgi/ wiki? TheProblemWithSigils
>> set_x
= > 88
>> x # Inchangee !
= > 22
Ruby 131
>> x = 44
= > 44
>> executer_bloc { x = 55 }
= > 55
>> x # Modifiee !
= > 55
? > executer_bloc { z = 88 }
= > 88
>> z
NameError : undefined local variable or method ’z ’ for main : Object
[...]
Ruby 132
>> set_x_glob
= > " abc "
>> $x_glob
= > " abc "
>> $x_glob
= > [10 , 20]
>> foo ( 0 )
= > [1 , nil ]
>> foo ( 99 )
= > [ nil , " BAR " ]
Ruby 133
>> # Mais un bloc definit une nouvelle portee , avec des variables
# strictement locales !
? > def bar ( * args )
args . each do | x |
r = 10
puts x * r
end
r
end
= > : bar
>> bar ( 10 , 20 )
100
200
NameError : undefined local variable or method ’r ’ for main : Object
[...]
4.16 Modules
Modules are a way of grouping together methods, classes, and constants.
Modules give you two major benefits:
Source : http: // ruby-doc. com/ docs/ ProgrammingRuby/ html/ tut_ modules. html
module M2
C1 = ’ abc ’
end
M1 :: C1 != M2 :: C1 # = > true
• Un module Ruby, tout comme un package en Java, permet une forme d’encapsu-
lation en permettant de définir des espaces de noms indépendants — des
namespaces distincts. Deux modules peuvent donc définir des constantes ou
des méthodes avec les mêmes noms sans qu’il n’y ait de conflit.
module Module1
def self . zero
0
end
def un
1
end
def val_x
@x
end
def inc_inc ( y )
inc ( y )
inc ( y )
end
end
class C1
include Module1
def initialize ( x )
@x = x
end
def inc ( y )
@x += y
end
end
class C2
include Module1
end
Ruby 136
>> c1 . zero
NoMethodError : undefined method ’ zero ’ for #< C1 :0 x12cf7ab @x =99 >
...
>> c1 . un
=> 1
>> c1 . val_x
= > 99
>> c1 . inc_inc ( 100 )
= > 299
• Une méthode de classe d’un module — comme pour une classe — est indiquée
par le préfixe «self.» devant le nom de la méthode. On peut aussi indiquer
le nom du module ou de la classe — par ex., «def Module1.zero» — mais le
style Ruby suggère d’utiliser plutôt «def self.zero».
• Une méthode de classe peut être appelée avec un appel de la forme suivante :
NomDuModule . nom_methode
• Une méthode d’instance d’un module ne peut être appelée que par l’inter-
médiaire d’un objet dont la définition de classe a inclus, avec include,
le module.
La méthode d’instance est alors exécutée comme si elle avait été définie di-
rectement comme méthode d’instance de la classe ayant effectuée l’inclusion.
• Une méthode d’instance définie dans un module peut faire référence à des
attributs ou méthodes qui ne sont pas définies dans le module. Évidem-
ment, pour que ces références soient valides à l’exécution, les attributs ou mé-
thodes en question doivent être définis dans la classe ayant effectué l’inclusion.
>> a
= > [10 , 20 , 30 , 40]
>> a ??
= > ??
>> a ??
= > ??
• Toute classe qui, comme Array, définit une méthode each et inclut le module
Enumerable, hérite automatiquement d’un grand nombre de méthodes :
Ruby 142
>> a
= > [100 , 200 , 300 , 400]
? > # Quantificateurs .
? > a . all ? { | x | x > 0 }
= > true
>> a . reduce ( :+ )
= > 1000
>> a . reduce ( :* )
= > 2400000000
>> a . map { | x | x / 10 }
= > ??
>> a . group_by { | x | x % 2 }
= > {0= >[100 , 200 , 300 , 400]}
Voir p. 139 pour une liste plus détaillée des opérations du module Enumerable.
Exemple Ruby 4.39 Une mise en oeuvre, en Ruby, de quelques méthodes du mo-
dule Enumerable, méthodes qui utilisent la méthode each de la classe ayant exécuté
l’appel «include Enumerable».
# Mise en oeuvre possible , en Ruby , de quelques methodes
# du module Enumerable : on utilise * uniquement * each !
module Enumerable
def include ?( elem )
each do | x |
return true if x == elem
end
false
end
def find
each do | x |
return x if yield ( x )
end
nil
end
accum
end
end
Ruby 147
Les exemples Ruby qui suivent présentent la méthode «<=>» et les méthodes
définies par le module Comparable.
>> # Tris .
? > a . sort
= > [10 , 29 , 33 , 44]
• Une collection qui définit une méthode each, qui inclut le module Enumerable
et dont les éléments peuvent être comparés avec l’opérateur «spaceship» hérite
automatiquement d’une méthode sort, ainsi que des méthodes min et max.
Par défaut, i.e., sans bloc après sort (idem pour max et min), la comparaison
se fait avec l’opérateur «<=>». Par contre, on peut aussi spécifier une méthode
de comparaison en transmettant un bloc, qui doit retourner -1, 0, 1 comme
l’opérateur «<=>».
• Lorsque la méthode «<=>» est définie par une classe et que cette classe inclut
le module Comparable, diverses méthodes deviennent alors automatiquement
disponibles.
Ruby 149
Dans cet exemple, l’ordre entre deux Cours est déterminé par l’ordre entre
leurs sigles. Donc, étant donné deux cours c1 et c2, c1 <=> c2 == c1.sigle
<=> c2.sigle.
class Cours
include Comparable
if $0 == __FILE__
# Definition de quelques cours .
inf1120 = Cours . new ( : INF1120 , ’ Programmation I ’ )
inf1130 = Cours . new ( : INF1130 , ’ Maths pour informaticien ’ )
inf2120 = Cours . new ( : INF2120 , ’ Programmation II ’ , inf1120 )
inf3105 = Cours . new ( : INF3105 , ’ Str . de don . ’ , inf1130 , inf2120 )
# Quelques expressions
puts inf3105 < inf1120
puts inf2120 >= inf1130
cours . sort . each { | c | puts c }
end
------------------------------------
Que fait la méthode suivante? Quel nom plus significatif pourrait-on lui donner?
class Array
def mystere ( p )
reduce ( [[] , [] , []] ) do | res , x |
res [1 + ( x <= > p )] << x
res
end
end
end
def each
@elements . each do | x |
yield ( x )
end
end
Ruby 153
def cardinalite
count
end
def contient ?( x )
include ? x
end
def to_s
" { " << map { | x | x . to_s }. join ( " , " ) << " } "
end
end
• La classe Ensemble définit une classe pour des objets représentant des en-
sembles d’éléments, i.e., des collections où chaque élément n’est présent au
plus qu’une seule fois.
• Un opérateur (infixe) tel que «<<» est défini comme n’importe quelle autre
méthode.
Puisqu’on doit modéliser un ensemble, où chaque élément n’est présent au plus
qu’une seule fois, si l’élément est déjà présent dans le tableau des @elements
(include?), alors on ne l’ajoute pas aux @elements.
Dans cet exemple, le résultat retourné par «<<» est self, i.e., l’objet lui-même
— équivalent au this de Java. Ceci permet de chaîner plusieurs appels les
uns à la suite des autres : voir l’exemple Ruby 4.43, qui présente quelques
expressions utilisant cette classe.
Ruby 154
• La classe Ensemble définit une méthode each, qui permet d’itérer sur les
éléments d’un ensemble.
• Soulignons que pour que les méthodes somme et produit fonctionnent cor-
rectement, un élément de l’ensemble doit pouvoir répondre aux messages «+»
et «*».
Supposons que dans la classe Array, on veuille définir les méthodes map et select,
et ce utilisant each ou each_index. Quel code faudrait-il écrire?
class Array
def map
...
end
def select
...
end
end
Tableau 4.2: Les principaux caractères spéciaux utilisés dans les expressions
régulières.
Ruby 159
Exemple Ruby 4.44 Une expression régulière est un objet de classe Regexp.
>> # Exemples de base .
>> re = / ab .* zz$ /
=> / ab .* zz$ /
>> re . class
=> Regexp
• Une expression régulière peut être créée à l’aide d’une expression utilisant les
barres obliques — /.../ — ou en créant explicitement avec new un objet de
classe Regexp.
Ruby 160
Exemple Ruby 4.45 Une expression régulière peut être utilisée dans une opération
de pattern-matching avec «=˜».
>> # Exemples de base ( suite ).
• L’opération de base pour matcher une chaine et une expression régulière est
l’opérateur «=~».
Ruby 161
Cet opérateur est en fait une méthode de la classe Regexp, mais une version
symétrique est aussi définie dans la classe String. Les appels suivants sont
donc équivalents (les parenthèses sont optionnels!) :
– re =~ ch
– re.=~( ch )
– re.=~ ch
– ch =~ re
• La méthode «=~» retourne la position dans la chaine où débute le match si
un tel match a pu être trouvé. Elle retourne nil si aucun match n’a pu être
trouvé.
• La méthode «!~» retourne true si aucun match n’a pu être trouvé, sinon elle
retourne false.
Ruby 162
>> # Un "." * ne matche pas * un saut de ligne ... sauf avec l ’ option m .
# Un \ s matche un saut de ligne .
Exemple Ruby 4.47 L’option «x» permet de mieux formater des expressions
régulières complexes.
>> motif = /(#{ CODE_REG }) # Le code regional
- # Un tiret
(#{ TEL }) # Le numero de tel .
/x
= > /((? - mix :\ d {3})) # Le code regional
- # Un tiret
((? - mix :\ d {3} -\ d {4})) # Le numero de tel .
/x
>> motif . match " Tel .: 514 -987 -3000 ext . 8213 "
= > #< MatchData " 514 -987 -3000 " 1: " 514 " 2: " 987 -3000 " >
• Par défaut, le pattern matching se fait ligne par ligne, et le «.» ne matche pas
un saut de ligne — alors qu’un \s va le matcher.
Par contre, si on indique l’option «m» — pour multi-lignes — alors le «.»
pourra matcher un saut de ligne.
• En mode ligne par ligne, le mode par défaut, les ancres «^» et «$» dénotent
le début et la fin de la ligne.
Exemple Ruby 4.49 Les méthodes d’un objet MatchData, objet retourné par
l’opération Regexp#match.
>> # Les objets MatchData .
>> m = /(#{ CODE_REG }) -(#{ TEL })/. match " FOO "
= > nil
>> m . pre_match
= > " Tel .: "
>> m . post_match
= > " ext . 8213 "
Exemple Ruby 4.50 Les groupes avec noms et les variables spéciales «$i» définies
par la méthode «=˜».
# Des groupes avec noms explicites .
>> m = /(? < code_reg >#{ CODE_REG }) -(? < tel >#{ TEL })/.
match " Tel .: 514 -987 -3000 ext . 8213 "
= > #< MatchData " 514 -987 -3000 " code_reg : " 514 "
tel : " 987 -3000 " >
>> m [: code_reg ]
= > " 514 "
>> m [: tel ]
= > " 987 -3000 "
• Il existe aussi des variables spéciales pour le match dans son ensemble, la partie
avant le match, la partie après, etc., mais les règles de style Ruby veulent qu’on
évite de les utiliser : si on a besoin de ces élément, on utilise plutôt un objet
MatchData explicite créé avec la méthode match et on utilise les méthodes
associées.
m = code_permanent .
match " CP : DEFG11229988 . "
p m [1]
p m [5]
p m . pre_match
p m . post_match
Exemple Ruby 4.51 Les arguments d’un programme Ruby et les variables
d’environnement.
$ cat argv . rb
# !/ usr / bin / env ruby
i = 0
while arg = ARGV . shift do
puts " ARGV [#{ i ++}] = ’#{ arg } ’ (#{ arg . class }) "
end
$ echo $FOO
$ ./ argv . rb
ENV [ ’ FOO ’] = ’’
-----
$ ./ argv . rb 1234 ’ abc " " def ’ abc def " ’"
ARGV [0] = ’1234 ’ ( String )
ARGV [1] = ’ abc " " def ’ ( String )
ARGV [2] = ’abc ’ ( String )
ARGV [3] = ’def ’ ( String )
ARGV [4] = ’’’ ( String )
ENV [ ’ FOO ’] = ’’
-----
# b.
NB =2 argv2 . rb [1 , 2] [3]
# c.
unset NB ; argv2 . rb [1009 , 229342] [334]
>> res
= > " 123\ n "
Ruby 173
$ ./ print - et - al . rb
*** Avec puts :
123
...
123
...
*** Avec print :
123...
123...
*** Avec p :
123
...
" 123 "
...
Ruby 175
imprimer ( : puts , [123 , 456] , [ " 123 " , " 456 " ] )
imprimer ( : print , [123 , 456] , [ " 123 " , " 456 " ] )
imprimer ( :p , [123 , 456] , [ " 123 " , " 456 " ] )
$ ./ print - et - al . rb
*** Avec puts :
123
456
...
123
456
...
*** Avec print :
[123 , 456]...
[ " 123 " , " 456 " ]...
*** Avec p :
[123 , 456]
...
[ " 123 " , " 456 " ]
...
Ruby 176
Exemple Ruby 4.55 Écriture d’un objet qui n’a pas de méthodes to_s et
inspect.
$ cat print - et - al . rb
# !/ usr / bin / env ruby
class Bar
def initialize ( val ); @val = val ; end
end
$ ./ print - et - al . rb
*** Avec puts :
#< Bar :0 x000000015022a0 >
...
*** Avec print :
#< Bar :0 x00000001502110 >...
*** Avec p :
#< Bar :0 x00000001501f80 @val =10 >
...
Ruby 177
Exemple Ruby 4.56 Écriture d’un objet qui a des méthodes to_s et inspect.
$ cat print - et - al . rb
# !/ usr / bin / env ruby
class Foo
def initialize ( val ); @val = val ; end
def inspect ; "#< Foo : val =#{ @val } > " ; end
end
$ ./ print - et - al . rb
*** Avec puts :
10
...
*** Avec print :
10...
*** Avec p :
#< Foo : val =10 >
...
• Outre printf, plusieurs autres méthodes sont disponibles pour émettre sur
le flux de sortie standard (ou tout autre flux, si on utilise un objet approprié
comme récepteur du message), notamment puts, print et p.
Ruby 178
• Donc, en gros (mais pas tout à fait dans le cas des tableaux), on a les équiva-
lences suivantes :
puts x print x.to_s; print "\n"
p x print x.inspect; print "\n"
• Remarque : p est particulièrement utile pour déboguer, car on voit plus ex-
plicitement le type d’un objet — e.g., dans le cas d’une chaine, les guillemets
sont indiqués explicitement, dans le cas d’un tableau, on a les crochets et les
virgules, etc.
Exemple Ruby 4.57 Différentes façon de lire et d’afficher sur stdout le contenu
d’un fichier texte.
$ cat cat . rb
# !/ usr / bin / env ruby
xxx
...
xxx
...
Ruby 180
Exemple Ruby 4.57 Différentes façon de lire et d’afficher sur stdout le contenu
d’un fichier texte.
$ cat cat . rb
# !/ usr / bin / env ruby
fich . close
xxx
...
xxx
...
Ruby 181
Exemple Ruby 4.57 Différentes façon de lire et d’afficher sur stdout le contenu
d’un fichier texte.
$ cat cat . rb
# !/ usr / bin / env ruby
xxx
...
xxx
...
Ruby 182
Exemple Ruby 4.57 Différentes façon de lire et d’afficher sur stdout le contenu
d’un fichier texte.
$ cat cat . rb
# !/ usr / bin / env ruby
xxx
...
xxx
...
Ruby 183
Exemple Ruby 4.58 Différentes façon de lire et d’afficher sur stdout le con-
tenu d’un fichier texte, dont une façon qui permet de recevoir les données par
l’intermédiaire du flux standard d’entrée.
$ cat cat . rb
# !/ usr / bin / env ruby
xxx
...
xxx
...
xxx
...
Ruby 184
Un fichier peut évidemment être ouvert dans d’autres modes que la lecture. La
figure 4.5 donne les différents modes pouvant être utilisés.
Ruby 185
>> $ ?
= > #< Process :: Status : pid 30019 exit 0 >
Figure 4.6: Deux points de vue sur les flux associés à un processus : a) Vue de
l’intérieur du processus — on lit sur STDIN et on écrit sur STDOUT et STDERR;
b) Vue de l’extérieur du processus — on écrit sur STDIN et on lit de STDOUT et
STDERR.
Ruby 188
$ ./ commandes2 . rb
-- stdout - -
3 5
-- stderr - -
$ ./ commandes3 . rb
-- out - -
-- err - -
wc : xsfdf . txt : Aucun fichier ou dossier de ce type
Ruby 189
• Comme dans un script shell, on peut utiliser les backticks pour lancer l’exécution
d’un programme externe et obtenir son résultat.
Toutefois, bien qu’on puisse utiliser les backticks, règle générale on utilise
plutôt la forme avec %x{...}.
• Le statut retourné par la commande est dans la variable «$?», commme dans
un script shell.
• Pour interpoler les variables spéciales, il n’est pas toujours nécessaire de les
mettre entre accolades.
• Ces deux forme ne donnent pas accès explicite aux différents flux. Plus spé-
cifiquement, le résultat retourné est ce qui est produit sur le flux de sortie
standard (stdout).
• On peut utiliser le module Open3 pour un contrôle plus fin des flux, notamment
pour avoir accès au flux d’erreur (stderr).
• Signalons que les noms des flux utilisés à l’intérieur du bloc sont arbitraires,
comme l’illustre le dernier exemple.
Ruby 190
NoMemoryError
ScriptError
LoadError
NotImplementedError
SyntaxError
SignalException
Interrupt
StandardError -- default for rescue
ArgumentError
IndexError
StopIteration
IOError
EOFError
LocalJumpError
NameError
NoMethodError
RangeError
FloatDomainError
RegexpError
RuntimeError -- default for raise
SecurityError
SystemCallError
Errno::*
SystemStackError
ThreadError
TypeError
ZeroDivisionError
SystemExit
fatal -- impossible to rescue
Exemple Ruby 4.62 Une méthode div qui attrape et traite diverses exceptions.
>> def div ( x , y )
begin
z = x / y
rescue ZeroDivisionError = > e
puts " *** Division par 0 (#{ e }) "
p e . backtrace
nil
rescue Exception = > e
puts " *** Erreur = ’#{ e . inspect } ’ "
end
end
= > : div
>> div 3 , 0
*** Division par 0 ( divided by 0)
[ " ( irb ):4: in ’/ ’ " ,
" ( irb ):4: in ’ div ’" , " ( irb ):14: in ’ irb_binding ’" ,
" / home / tremblay /. rvm / rubies / ruby -2.1.4/ lib / ruby /2.1.0/ irb / workspace . rb :86: in ’ eval
...,
" / home / tremblay /. rvm / rubies / ruby -2.1.4/ bin / irb :11: in ’< main > ’ " ]
= > nil
Exemple Ruby 4.63 Une méthode traiter_fichier qui attrape et traite des
exceptions et qui s’assure de restaurer le système dans un bon état, qu’une exception
soit signalée ou non — dans ce cas-ci, en s’assurant de fermer le descripteur du fichier
ayant été ouvert.
>> def traiter_fichier ( fich )
f = File . open ( fich )
begin
traite r_contenu_ fichier ( f . readlines )
puts " +++ Traitement termine "
rescue Exception = > e
puts " *** Erreur = ’#{ e . inspect } ’ "
ensure
f . close
end
Exemple Ruby 4.66 Exemples illustrant l’instruction raise utilisée pour resig-
naler une exception.
>> def executer
begin
yield
rescue Exception = > e
puts " classe = #{ e . class }; message = ’#{ e . message } ’ "
raise
end
end
= > : executer
• Il est aussi possible d’utiliser l’instruction raise pour signaler une exception.
Les deux sont en fait des synonymes.
Ruby 196
– On utilise fail lorsqu’on veut signaler une nouvelle exception, donc suite
à un problème qu’on vient tout juste de détecter — premier appel/signal.
– On utilise raise lorsqu’on désire resignaler une exception, qui a déjà
signalée. Par exemple, on exécute une clause rescue, on fait certains
traitements, puis on resignale la même exception pour que les méthodes
appelantes puissent elles aussi traiter l’exception. Dans ce cas, il n’est
pas nécessaire d’indiquer explicitement le nom de l’exception.
Ruby 197
>> a = *10
= > [10]
>> a = *(1..10)
= > [1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10]
# Mais ...
>> *(1..10)
SyntaxError : ( irb ):41: syntax error , unexpected ’\ n ’ ,
expecting :: or ’[ ’ or ’. ’
...
>> *10
SyntaxError : ( irb ):33: syntax error , unexpected ’\ n ’ ,
expecting :: or ’[ ’ or ’. ’
...
Ruby 199
Exemple Ruby 4.68 Utilisation de l’opérateur «*» du coté gauche d’une affecta-
tion parallèle (multiple).
>> # Dans la partie gauche d ’ une affectation parallele , un * permet de
# << deconstruire > > un tableau . Dans ce cas , la variable
# prefixee avec * doit etre unique et va denoter un sous - tableau
# d ’ elements .
>> foo ( 10 )
x = 10
= > []
>> foo ( 10 , 20 )
x = 10
args [0] = 20
= > [20]
>> foo ( 10 , 20 , 30 )
x = 10
args [0] = 20
args [1] = 30
= > [20 , 30]
Exemple Ruby 4.70 Utilisation de l’opérateur «&» pour rendre explicite un bloc
comme paramètre d’une méthode.
>> # L ’ operateur prefixe & utilise devant le dernier parametre
# rend explicite le bloc transmis a l ’ appel de la methode .
# Ce parametre est alors un objet Proc pouvant
# etre execute avec call .
>> call_yield ( 99 )
= > 99
>> call_yield ( 99 ) { | x | x + 10 }
= > [ Proc , 109 , 109]
Ruby 202
>> call_yield ( 2 ) { | x | 2 * x }
= > [ Proc , 4 , 4]
def + @
puts " self = #{ self } "
end
end
= > :+ @
>> foo + 10
self = #< Foo :0 x000000019910c8 >; autre = 10
= > nil
>> + foo
self = #< Foo :0 x000000019910c8 >
= > nil
• Les symboles tels que «:+» et «:-» dénotent par défaut les opérateurs bi-
naires.
• Pour référer aux opérateurs (préfixes) unaires, on utilise les symboles «:+@»
ou «:+@».
• Comme n’importe quelles autres méthodes, les méthodes pour les opétateurs,
tant binaires qu’unaires, peuvent être définies par le programmeur.
Ruby 205
Ruby 206
8
https://rvm.io/
Ruby 207
Ruby 208
• Tests d’intégration : Les tests d’intégration vérifient que les principaux sous-
systèmes fonctionnent correctement, c’est-à-dire que les différents modules qui
composent un sous-système donné sont correctement intégrés ensemble. Ces
tests peuvent être vus comme une forme de tests unitaires, l’unité étant alors
un groupe (cohésif ) de modules plutôt qu’un unique module.
• Tests d’acceptation : Les tests d’acceptation sont des tests, de niveau système,
effectués lorsque le système est prêt à être déployé, donc juste avant qu’il soit
livré et officiellement installé.
• Les cas de tests devraient être développés et écrits (codés) avant le code lui-
même!
• Du nouveau code ne devrait jamais être écrit s’il n’y a pas déjà un cas de test
qui montre que ce code est nécessaire.
Cadres de tests
Qu’on utilise ou non une telle approche de développement piloté par les tests, il
est malgré tout fondamental, lorsqu’on écrit un programme, de développer des tests
appropriés qui vérifient son bon fonctionnement. De plus, il est aussi important
que ces tests puissent être exécutés fréquemment et de façon automatique — ne
serait-ce que pour assurer que tout fonctionne bien lorsque des modifications sont
effectuées (tests de non régression du code).
De nos jours, il existe de nombreux outils qui permettent d’automatiser l’exécution
des tests unitaires, qui facilitent le développement de tels tests et leur association
au code testé, et ce peu importe le langage de programmation utilisé. Ces outils
sont appelés des cadres de tests (tests frameworks).
Le cadre de tests le plus connu est JUnit [BG98, Bec01, HT03], popularisé par
les promoteurs de l’approche XP (eXtreme Programming). Des cadres équivalents
existent pour divers autres langages.9 Dans ce qui suit, nous allons présenter un
cadre de tests développé pour Ruby et maintenant intégré au noyau du langage :
MiniTest.
Mais auparavant, il est utile de comprendre comment fonctionnent de tels cadres
de tests. Tout d’abord, la caractéristique la plus importante de tous les cadres de
tests est qu’on utilise des assertions pour décrire et spécifier ce qui doit être vérifié.
En JUnit, de telles assertions ont la forme suivante et ont toujours la propriété que
rien n’est signalé si l’assertion est vérifiée :
assertEquals ( expectedResult , value )
assertEquals ( expectedResult , value , precision )
assertTrue ( booleanExpression )
assertNotNull ( reference )
etc .
En d’autres mots, ceci implique qu’aucun résultat n’est produit ou généré si le
test ne détecte pas d’erreur.
9
Par exemple, voir http://www.xprogramming.com/software.htm.
Ruby 210
• Ils permettent l’exécution automatique des tests — support pour les tests de
(non-)régression, pour l’intégration continue, etc..
• Ils permettent l’organisation structurée des jeux d’essais (cas de tests, suites
de tests, classes de tests).
Plus spécifiquement :
– Un cas de tests porte sur une fonctionnalité limitée, une instance partic-
ulière d’une méthode ou procédure/fonction.
– Une suite de tests regroupe un certain nombre de cas de tests, qui représen-
tent diverses instances liées à une même procédure ou groupe de procé-
dures liées entre elles.
– Une classe de tests, dans un langage objet, regroupe l’ensemble des suites
de tests permettant de tester l’ensemble des fonctionnalités du module,
c’est-à-dire de la classe. Un programme de tests joue le même rôle dans
un contexte impératif et procédural (non orienté objets).
• Des tests unitaires «classiques», avec des assertions, qui conduisent à des tests
semblables à ce qu’on obtient en Java avec JUnit.
Ruby 211
Dans cette forme, un programme de tests pour une méthode bar d’une classe Foo
aurait l’allure suivante :
class TestFoo < MiniTest :: Unit :: TestCase
def setup
@foo = Foo . new
end
def t e s t_ b ar _ e st _ in i t ia l em e n t_ 0
assert_equal 0 , @foo . bar
end
...
end
• Des tests unitaires dits de «spécifications», avec des «exceptations», qui con-
duisent à des tests semblables à ce qu’on obtient avec RSpec [CAD+ 10], un gem
Ruby qui définit un langage de tests — un langage-spécifique au domaine10
pour les tests.
Dans cette forme, un programme de tests pour une méthode bar d’une classe
Foo aurait l’allure suivante :
describe Foo do
describe " # bar " do
before do
@foo = Foo . new
end
C’est cette dernière forme que nous allons présenter dans les exemples qui suivent.
10
DSL = Domain Specific Language [Fow11].
Ruby 212
Exemple Ruby 4.73 Une suite de tests pour la classe Ensemble (partie 1)
require ’ minitest / autorun ’
require ’ minitest / spec ’
require_relative ’ ensemble ’
describe Ensemble do
before do
@ens = Ensemble . new
end
describe ’# contient ? ’ do
it " retourne faux quand un element n ’ est pas present " do
refute @ens . contient ? 10
end
# ...
Ruby 213
Exemple Ruby 4.74 Une suite de tests pour la classe Ensemble (partie 2)
# ...
@ens << 10
assert @ens . contient ? 10
end
# ...
Ruby 214
Exemple Ruby 4.75 Une suite de tests pour la classe Ensemble (partie 3)
# ...
describe ’# cardinalite ’ do
it " retourne 0 lorsque vide " do
@ens . cardinalite . must_equal 0
end
Les exemples Ruby 4.73–4.75 présentent une suite de tests pour la classe Ensemble
— voir l’exemple Ruby 4.42 (p.-152) pour la mise en oeuvre de cette classe.
• Le bloc de code indiqué par before sera exécuté avant chaque cas de test. Il
sert à définir le contexte d’exécution de chacun des tests. Ici, pour éviter la du-
plication de code, on alloue un nouvel objet Ensemble, initialement vide, qu’on
affecte à la variable @ens. Puisque cette variable est une variable d’instance
du test, elle sera accessible dans chacun des cas de test.
Ruby 215
• Chaque appel à it décrit un cas de test spécifique, qui ne devrait tester qu’une
et une seule chose. Règle générale (règle de style, pas syntaxe), il ne devrait
y avoir qu’une seule assertion (expectation) par tests.
• Une assertion telle que «assert expr » affirme que l’expression expr est vraie.
Si c’est le cas, le test réussit — donc, en mode non verbeux, un «.» sera
affiché. Par contre, si expr est fausse, alors le test échoue et un message
d’erreur approprié sera affiché — voir plus bas.
Une assertion telle que «refute expr » affirme que l’expression expr est fausse
— dont «refute expr » est équivalent à «assert !expr ».
• La clause «res.must_be_same_as @ens» affirme que res et @ens dénotent en
fait le même objet. Cette clause est donc équivalente à la suivante :
assert res . equal ? @ens
============================
Avec simple assert
============================
1) Failure:
Ensemble::#cardinalite#test_0003_retourne [...] [ensemble_spec.rb:61]:
Failed assertion, no message given.
============================
Avec must_equal/assert_equal
============================
1) Failure:
Ensemble::#cardinalite#test_0003_retourne [...] [ensemble_spec.rb:61]:
Expected: 2
Actual: 0
Ruby 216
Exemple Ruby 4.76 Des exemples d’exécution de la suite de tests pour la classe
Ensemble.
======================
Execution ordinaire
======================
$ ruby ensemble_spec.rb
Run options: --seed 43434
# Running:
........
-------------------------------------------------------------
======================
Execution ’verbeuse’
======================
$ ruby ensemble_spec.rb -v
Run options: -v --seed 18033
# Running:
# Running:
...FF...
1) Failure:
Ensemble::#cardinalite#test_0002_retourne 1 lorsqu’un seul et meme element est ajoute,\
1 ou plusieurs fois [ensemble_spec.rb:54]:
Expected: 1
Actual: 0
2) Failure:
Ensemble::#cardinalite#test_0003_retourne le nombre d’elements distincts peu importe\
le nombre de fois ajoutes [ensemble_spec.rb:62]:
Expected: 2
Actual: 0
La figure 4.8 (p. 219) présente la liste détaillée des expectations de MiniTest.
Ruby 219
Exemple Ruby 4.78 Quelques autres méthodes de MiniTest — dans le style avec
expectations.
gem ’ minitest ’
require ’ minitest / autorun ’
require ’ minitest / spec ’
describe Array do
let (: vide ) { Array . new }
before do
@singleton_10 = Array . new << 10
end
it " retourne les elements separes par des virgules ( bis ) " do
a = vide << 10 << 20 << 30
virgule = /\ s * ,\ s */
a . to_s
. must_match
/^\[\ s *10#{ virgule }20#{ virgule }30\ s *\] $ /
end
end
end
Ruby 222
• Dans l’étape de setup des tests, lorsqu’on veut définir des objets pouvant être
utilisés dans plusieurs cas de tests, on peut utiliser deux approches :
– Objet défini avec une expression simple : on peut utiliser let, qui reçoit
comme argument un Symbol (arg. explicite) et un bloc (arg. implicite).
On peut ensuite utiliser directement l’identificateur dans les tests.
– Objet plus complexe (ou grand nombre d’objets) : on utilise la méthode
before. Dans ce cas, les objets sont des variables d’instance du test,
donc doivent leurs noms doivent être précédés du sigil «@».
Dans les deux formes, les objets ainsi définis sont évalués/recréés pour chaque
cas de test, et ce dans le but d’assurer l’indépendance de chacun des tests.
– NomDeClasse
– NOM_DE_CONSTANTE
– nom_de_methode
– nom_de_parametre_ou_variable
• Indentation avec deux (2) espaces blancs seulement, jamais des carac-
tères de tabulation.
• Jamais de blancs à la fin d’une ligne.
• Des blancs autour des opérateurs binaires (y compris =), après les
virgules, les deux points et les points-virgules, autour des { et avant
les }.
• Pas de blanc avant ou après [ et ], ou après !.
• Jamais de then pour une instruction if/unless et jamais de paren-
thèses autour des conditions (on est en Ruby, pas en Java ou C!) :
# NON # OK
if ( condition ) then if condition
... ...
end end
Ruby 224
# NON
une_methode_sans_arg ()
# OK
une_methode_sans_arg
# NON # OK
if condition une_instr if condition
une_instr
end
# NON # OK
unless expr if expr
... si faux ... ... si vrai ...
else else
... si vrai ... ... si faux ...
end end
Ruby 225
• Pour les blocs, on utilise {...} lorsque le corps peut s’écrire sur une
seule ligne. Autrement, on utilise do ... end.
# NON # OK
col . map do | x | ... end col . map { | x | ... }
# NON # OK
def m_rec ( ... ) def m_rec ( ... )
if expr return res_base if expr
return res_base
else ...
... res_rec
return res_rec end
end
end
• Des espaces sont mis autour des parenthèses des définitions de méthodes, con-
trairement à ce qui est suggéré dans ce guide :
# Style suggere dans le guide .
def methode (a , b , c )
...
end
• Les méthodes map (collect), select (find_all), reject doivent être utili-
sées pour produire une nouvelle collection, et non pour leurs effets de bord.
Notamment, voici un exemple à ne pas faire s’il est demandé d’utiliser le style
fonctionnel :
# NON
res = []
a . map { | x | res << foo ( x ) }
# OK
a . map { | x | foo ( x ) }
Dans cet exemple, le résultat produit par le map n’est pas utilisé. Le map est en
fait utilisé comme «un faux each», donc n’est pas dans un style fonctionnel.
Si l’instruction est trop longue pour la ligne, alors on utilise la forme avec une
instruction if :
if condition
instruction
end
• Il faut éviter les effets de bord dans les gardes — i.e., la condition d’une garde
ne devrait rien modifier :
puts x if x = ARGV . shift # NON !
Dans certains cas simples, on peut accepter une affectation en début d’une
instruction if si l’effet de bord est bien visible au tout début du code :
if x = ARGV . shift
puts x
end
Ruby 228
# OK
(1.. n ). reduce (1.0) { | res , x | x == 0 ? res : res / x }
# et parce que
( res = v ) == v
Ruby 229
class Foo
attr_reader : bar
attr_writer : bar
def initialize
self . bar = 0
end
end
class Foo
attr_reader : bar
attr_writer : bar
def initialize
self . bar = 0
end
end
L’exemple Ruby 4.79 montre une définition possible des méthodes attr_reader et
attr_writer. Comme c’est souvent le cas en Ruby, il y a plusieurs façons différentes
d’obtenir le même résultat. L’exemple Ruby 4.80 montre donc une autre définition
possible de ces mêmes méthodes.
Ruby 231
232
Chapitre 5
2. Parallélisme de boucles
3. Parallélisme de données
4. Parallélisme «Coordonnateur/Travailleurs»
233
Patrons de programmation en PRuby 234
• Etc.
5.2.1 Factoriel
Comme premier exemple, nous allons définir dDifférentes versions d’une fonction
pour calculer la factorielle d’un nombre n — fact( n ) = 1×2×3×. . .×(n−1)×n.
r1 * r2
end
end
fact_ ( 1 , n )
end
r1 * r2
end
fact_ ( 1 , n )
end
Le Programme Ruby 5.3 présente une version récursive parallèle avec pcall. Quelques
remarques :
• Plutôt qu’avoir un if avec une branche then et une branche else complexe
imbriquée et indentée, on retourne immédiatement et directement le résultat
approprié dans le cas de base : «return i if i == j».
• Les deux appels récursifs, au lieu d’être faits l’un après l’autre, sont faits en
parallèle, et ce en utilisant la méthode pcall.
Plus précisément, la méthode pcall de la bibliothèque PRuby — méthode
de classe (statique) — reçoit en argument deux ou plusieurs lambdas. Ces
différents lambdas sont alors évalués de façon concurrente — en parallèle si les
ressources le permettent. De plus, l’appel à pcall ne se termine que lorsque
tous les appels des lambdas ont complété. Un appel à la méthode pcall est
donc bloquant pour le thread appelant et introduit une forme de barrière de
synchronisation entre les threads exécutant les lambdas.
• Avant de faire les appels récursifs, on affecte les deux variables r1 et r2 à
nil — on aurait aussi pu écrire «r1 = r2 = nil». Ces affectations sont
Patrons de programmation en PRuby 238
nécessaires pour que les variables r1 et r2 indiquées dans les lambda soient
déjà déclarées et visibles, et donc puissent être modifiées pour obtenir les
résultats des appels récursifs : dans un lambda, si une variable non-locale
existe dans l’environnement, alors c’est cette variable qui est utilisée.
• Une expression lambda peut aussi être dénotée par le symbole «->». De plus,
dans un appel de méthode, les parenthèses, à moins qu’il n’y ait ambiguité à
cause de la précédence des opérateurs, peuvent être omises. L’appel à pcall
aurait donc pu être écrite de différentes façons comme suit — le caractère «\»
indique une continuation de l’instruction à la ligne suivante :
PRuby . pcall \
lambda { r1 = fact (i , mid , seuil ) } ,
lambda { r2 = fact ( mid +1 , j , seuil ) }
...
• La méthode pcall peut être vue comme une forme de cobegin/codend. Dans
un langage comme MPD, on aurait écrit quelque chose comme suit — co =
cobegin = fork et oc = coend = join — donc avec une syntaxe différente
du pcall mais avec un comportement semblable :
co
r1 = fact_( i, mid )
// r2 = fact_( mid+1, j )
oc
Patrons de programmation en PRuby 239
Programme Ruby 5.4 Fonction récursive parallèle pour calculer fact(n) avec
troncation de la récursion.
def fact ( n , seuil )
def fact_ ( i , j , seuil )
# Probleme simple , mais non trivial
# = > solution iterative sequentielle .
return ( i .. j ). reduce (:*) if j - i <= seuil
r1 * r2
end
fact_ ( 1 , n , seuil )
end
• Effectuer des appels récursifs entrainent certains coûts. Ces coûts sont encore
plus élevés lorsque ces appels récursifs sont effectués en parallèle, avec des
threads / (voir séance de laboratoire).
Pour le Programme Ruby 5.4, dessinez l’arbre d’activation des appels de méthodes
qui génèrent des threads pour l’appel fact( 20, 3 ).
Exercice 5.2: Arbre d’activation pour l’appel à fact(20, 3).
Programme Ruby 5.5 Fonction récursive parallèle pour calculer fact(n) avec
des futures.
def fact ( n , seuil )
def fact_ ( i , j , seuil )
# Probleme simple .
return ( i .. j ). reduce (:*) if j - i <= seuil
# Probleme complexe .
mid = ( i + j ) / 2
r1 = PRuby . future { fact_ (i , mid , seuil ) }
r2 = PRuby . future { fact_ ( mid + 1 , j , seuil ) }
r1 . value * r2 . value
end
fact_ ( 1 , n , seuil )
end
Le Programme Ruby 5.5 présente une autre version du calcul de factoriel avec un
seuil de récursion :
• Dans le Programme Ruby 5.4 (idem pour le Programme Ruby 5.3), pour que
les threads enfants puissent retourner un résultat au thread parent, le par-
ent doit déclarer une variable appropriée, laquelle est ensuite utilisée comme
variable non-locale du lambda. Or, ceci complexifie inutilement le lancement
d’un thread exécuté pour évaluer une expression et retourner un résultat —
par opposition à un thread exécuté pour ses effets de bord. L’utilisation de
Patrons de programmation en PRuby 242
future permet de simplifier ce cas où un thread est utilisé pour évaluer une
expression, ce qui permet de rendre la version parallèle semblable à la version
séquentielle.
Le Programme Ruby 5.5 crée deux (2) futures pour évaluer les deux appels récursifs
en parallèle.
Peut-on améliorer ce programme pour créer des threads de granularité plus grossière
— donc réduire le nombre de threads créés — tout en restant autant parallèle?
Indice : Que fait le thread parent pendant que ses enfants — les deux appels
récursifs — s’exécutent?
Exercice 5.3: Fonction récursive parallèle pour calculer fact(n), mais avec le
thread parent qui fait du travail utile.
Dessinez l’arbre d’activation des threads pour l’appel fact( 20, 3 ) pour la version
améliorée de fact produite pour l’exercice précédent.
Exercice 5.4: Arbre d’activation des threads pour l’appel à fact(20, 3) avec
version améliorée de fact.
Programme Ruby 5.6 Fonction séquentielle itérative pour faire la somme de deux
tableaux.
def somme_tableaux ( a , b )
DBC . require a . size == b . size # Precondition : omise ailleurs .
c
end
Quelques remarques :
• Une précondition a été indiquée pour assurer que les deux tableaux sont de
même taille. Dans les versions qui suivent de cette fonction, cette précondition
sera omise pour simplifier le code présenté.
Programme Ruby 5.7 Fonction parallèle itérative à granularité fine pour faire la
somme de deux tableaux avec pcall.
def somme_tableaux ( a , b )
c = Array . new ( a . size )
c
end
Le Programme Ruby 5.7 présente une version parallèle utilisant pcall. La som-
mation pour chacun des éléments peut se faire de façon totalement indépendante — il
s’agit d’une forme de parallélisme dite «embarrassingly parallel ». Il est donc possible
Patrons de programmation en PRuby 244
de créer un thread distinct pour chacun des éléments, et c’est ce qui est fait ici. Dans
ce cas, on parle aussi de parallélisme à granularité (très!) fine, puisque chaque thread
n’effectue qu’un tout petit calcul, exécute un tout petit nombre d’instructions. La
Figure 5.2 illustre le graphe de dépendances des tâches pour des tableaux de taille n
(variante d’un graphe vu précédemment).
Remarques additionnelles :
• Une telle instruction pcall crée une famille de threads, indexée par les élé-
ments du Range. Avec pcall, on peut donc lancer l’exécution de plusieurs
threads, soit en spécifiant deux ou plusieurs lambda sans argument, soit en
spécifiant un Range et une lambda avec un argument (entier).
Figure 5.2: Graphe de dépendances des tâches pour le calcul parallèle de la somme
de deux tableaux.
Est-ce que cette méthode sera performante si on traite deux gros tableaux?
Exercice 5.5: Performances si deux gros tableaux?
Patrons de programmation en PRuby 245
# On retourne le resultat .
c
end
Créer des threads coûte cher et en créer un pour chaque élément d’un tableau
ne sera assurément pas performant. Ainsi, si l’on doit additionner 1000 éléments
sur une machine avec 4 processeurs, on créera donc 1000 threads, dont l’exécution
devra ensuite être répartie entre les 4 processeurs. Beaucoup de travail pour rien!
Pour obtenir un programme performant, il est généralement préférable d’utiliser
un nombre de threads qui soit du même ordre de grandeur que le nombre de pro-
cesseurs. Ici, cela signifie que chaque thread devrait prendre en charge la somme de
plusieurs éléments, et non pas un seul.
Patrons de programmation en PRuby 246
Le Programme Ruby 5.8 présente une telle fonction, dite «à granularité grossière» :
• Les indices associés à une tranche pour un thread sont obtenus avec la fonction
indices_tranche, qui retourne un Range. Par exemple, si on a 100 éléments
(a.size == 100) et 4 threads (nb_threads == 4), alors les tranches des dif-
férents threads seront réparties comme suit :
– thread 0 : 0..24
– thread 1 : 25..49
– thread 2 : 50..74
– thread 3 : 76..99
Pour que cette façon simple de déterminer les indices à traiter fonctionne
correctement, il faut que le nombre d’eléments à traiter soit un multiple du
nombre threads. Cette condition est vérifiée dans la précondition. On verra
ultérieurement comment calculer ces intervalles d’indices sans imposer cette
condition. On verra aussi d’autres façons de répartir les éléments à traiter
entre les divers threads.
Dans le cas plus général, donc avec k threadset n éléments, voir la figure 5.3
pour la répartition résultante.
Figure 5.3: Répartition par blocs d’éléments adjacent de n éléments entre k threads.
Chaque thread traite n/k éléments adjacents — pour simplifier, on suppose que n
est divisible par k.La figure du haut présente une distribution d’un tableau, alors
que la figure du bas présente le graphe de dépendances des tâches pour la somme
de deux tableaux mais où un bloc de tâches est attribué à chacun des threads.
Patrons de programmation en PRuby 248
Figure 5.4: Estimation de la valeur de π à l’aide d’une méthode Monte Carlo (source :
http://i.stack.imgur.com/uYrT5.jpg).
La figure 5.4 illustre comment on peut estimer la valeur de π à l’aide d’une telle
méthode. Supposons qu’on ait une cible carrée de taille 2 par 2 dans laquelle est
Patrons de programmation en PRuby 249
• Valeur de π : π = 4 AAcercle
carré
>> a . map { | x | 10 * x }
=> [10 , 110 , 210 , 310 , 410 , 510 , 610 , 710 , 810 , 910]
>> a
=> [1 , 11 , 21 , 31 , 41 , 51 , 61 , 71 , 81 , 91]
>> a . map ! { | x | 10 * x }
=> [10 , 110 , 210 , 310 , 410 , 510 , 610 , 710 , 810 , 910]
>> a
=> [10 , 110 , 210 , 310 , 410 , 510 , 610 , 710 , 810 , 910]
Figure 5.6: Exemples d’exécution de la méthode Ruby map (du module Enumerable).
Patrons de programmation en PRuby 251
Programme Ruby 5.9 Fonction parallèle pour estimer la valeur de π à l’aide d’une
méthode Monte Carlo (style fonctionnel).
def nb_dans_cercle_seq ( nb_lancers )
nb = 0
nb_lancers . times do
# On genere un point aleatoire .
x , y = rand , rand
nb
end
Le Programme Ruby 5.9 présente une mise en oeuvre parallèle avec des futures
de cette approche, qui travaille uniquement dans le cadra supérieur droit, tel qu’illustré
dans la Figure 5.5 :
Pour ceux plus familiers avec une approche impérative, le Programme Ruby 5.10
présente une version équivalente, mais dans un style plus «impératif». Soulignons
toutefois qu’en Ruby, c’est le Programme Ruby 5.9 qui est considéré comme ayant
«le meilleur style».
Patrons de programmation en PRuby 253
sommation_tableau ( [99] ).
must_equal 99
mid = a . size / 2
r1 = PRuby . future { sommation_tableau ( a [0.. mid -1]) }
r2 = sommation_tableau ( a [ mid ... a . size ] )
r1 . value + r2
end
Exercice 5.8: Sommation des éléments d’un tableau avec parallélisme itératif à
granularité grossière.
Patrons de programmation en PRuby 255
• L’itérateur each_index reçoit chacun des indices des éléments d’une collection,
et applique un bloc à chaque indice reçu. Cette méthode n’est toutefois valide
que pour un objet Array, et non pour un Range.
Dans les deux cas, la valeur retournée par l’appel à la méthode est la collec-
tion elle-même, i.e., celle sur laquelle s’applique la méthode each ou each_index.
L’exemple Ruby 5.1 présente quelques exemples simples.
Patrons de programmation en PRuby 256
Exemple Ruby 5.1 Différences entre each et each_index pour les Array et Range.
>> [10 , 20 , 30]. each { | x | puts x }
10
20
30
= > [10 , 20 , 30]
Programme Ruby 5.11 Fonction parallèle itérative à granularité fine pour faire
la somme de deux tableaux avec peach.
def somme_tableaux ( a , b , _nb_threads )
c = Array . new ( a . size )
c
end
Le Programmme Ruby 5.11 présente une version avec parallélisme de boucle à gran-
ularité fine pour la somme de deux tableaux.
c
end
Le Programmme Ruby 5.12 quant à lui présente une version avec parallélisme de
boucle à granularité grossière pour la somme de deux tableaux. Comme on le
constate, c’est une version très simple, semblable à la version séquentielle, sauf pour
la spécification du nombre de threads à utiliser. De plus, cette version est tout à fait
équivalente à celle du Programme Ruby 5.8 quant à la répartition des éléments entre
les threads, et ce même si elle est beaucoup plus simple. Quelques explications :
• Les threads vont se partager les diverses itérations de la boucle. Ces itérations
peuvent être distribuées de différentes façons :
– Par défaut — ou lorsqu’on indique simplement «static: true» — la
répartition se fait par groupes d’éléments adjacents, comme dans le Pro-
gramme Ruby 5.8 :
col . peach { ... }
=
col . peach ( static : true ) { ... }
Ici, on parle d’une répartition statique parce qu’on sait, dès le lancement des
threads, quelles seront les itérations traitées par chaque thread.
Signalons que contrairement au Programme Ruby 5.8, le nombre d’éléments à
traiter n’a pas besoin d’être divisible par le nombre de threads. Si le nombre
d’éléments n’est pas exactement divisible, les éléments seront répartis le plus
uniformément possible entre les threads. Par exemple, si on doit répartir 20
éléments entre 6 threads, les 2 premiers threads traiteront 4 éléments alors que
les 4 threads suivants en traiteront 3.
Patrons de programmation en PRuby 259
• Lorsqu’ une valeur numérique est spécifiée, par exemple «static: k», on a
alors une répartition statique et cyclique par bloc de k éléments.
Par exemple, si on a 12 éléments à répartir entre 3 threads, on aurait donc les
associations suivantes — ti dans une position du tableau indique que c’est le
thread i qui traite cet élément :
– static: true :
t0 t0 t0 t0 t1 t1 t1 t1 t2 t2 t2 t2
– static: 1 :
t0 t1 t2 t0 t1 t2 t0 t1 t2 t0 t1 t2
– static: 2 :
t0 t0 t1 t1 t2 t2 t0 t0 t1 t1 t2 t2
– static: 3 :
t0 t0 t0 t1 t1 t1 t2 t2 t2 t0 t0 t0
– static: 4 :
t0 t0 t0 t0 t1 t1 t1 t1 t2 t2 t2 t2
Le Programme Ruby 5.13 présente une autre version du calcul de π, cette fois en
utilisant un peach. Solution simple, n’est-ce pas? Mais on verra bientôt qu’il est
possible de faire encore plus simple!
Patrons de programmation en PRuby 261
c
end
Le Programme PRuby 5.14 présente une fonction séquentielle itérative pour calculer
le produit de deux matrices. Ces matrices sont des objets de la classe Matrice. Voir
l’URL suivant pour une description de l’API de cette classe :
http://www.labunix.uqam.ca/~tremblay/INF5171/pruby/Matrice.html
On remarque qu’une précondition sur la taille des matrices à multiplier a été
spécifiée. La même condition s’applique évidemment aux versions parallèles, même
si cette condition ne sera plus indiquée explicitement.
Le Programme PRuby 5.15 présente une version parallèle à granularité très fine
du produit de matrices. Chaque élément du résultat — matrice c — peut être calculé
de façon indépendante, donc avec un algorithme avec parallélisme embarrassant.
Dans cette version, on lance donc un thread pour chaque élément du résultat!
Clairement cette solution risque de ne pas être efficace, car un très (trop!?) grand
nombre de threads seront lancés.
Patrons de programmation en PRuby 262
Programme Ruby 5.15 Fonction parallèle à granularité (très!) fine pour ef-
fectuer le produit de deux matrices.
def produit ( a , b )
c = Matrice . new ( a . nb_lignes , b . nb_colonnes )
nbl = c . nb_lignes # Vars ... pour mise en page
nbc = c . nb_colonnes
c
end
c
end
• Un seul peach est utilisé, au niveau des lignes. Pour le traitement des diverses
colonnes d’une ligne, on utilise plutôt un each, donc un traitement itératif
séquentiel.
Programme Ruby 5.17 Fonction parallèle à granularité encore plus grossière pour
effectuer le produit de deux matrices, avec répartition entre les threads par blocs de
lignes.
def produit ( a , b )
c = Matrice . new ( a . nb_lignes , b . nb_colonnes )
c
end
Figure 5.7: Distribution par bloc vs. distribution cyclique pour un tableau à
1 dimension (source : http://www.dais.unive.it/~calpar/New_HPC_course/5_
Parallel_Patterns.pdf).
Patrons de programmation en PRuby 265
Figure 5.8: Distribution par bloc vs. distribution cyclique pour une matrice à 2
dimensions (source : http://www.dais.unive.it/~calpar/New_HPC_course/5_
Parallel_Patterns.pdf).
Patrons de programmation en PRuby 266
Figure 5.9: Différents types de distribution des données pour un tableau 8 × 8 entre
quatre (4) processus en HPF. Les données pour le processus 0 sont en gris foncé
(source : [Fos95]). Sur la première ligne : différents modes de répartition par blocs
— dont blocs de lignes (gauche) et blocs de colonnes (centre). Sur la deuxième
ligne : différents modes de répartition cyclique.
Patrons de programmation en PRuby 267
R = [f (c1 ), . . . , f (cn )]
• Calcul de préfixes : une telle opération applique une opération binaire associa-
tive sur les divers éléments de la collection pour obtenir un résultat qui sera une
autre collection de même taille, où le ième éléments de la collection résultante
est obtenu par une série d’applications de l’opération binaire sur les i premiers
éléments. Plus précisément, soit ⊕ une opération binaire et C = [c1 , . . . , cn ]
une collection. Le calcul de préfixes sur C avec ⊕ produira alors le résultat R
satisfaisant la condition suivante, donc tel que Ri = c1 ⊕ c2 ⊕ . . . ⊕ ci :
Les notions d’application avec map et de réduction avec reduce ne sont pas
nouvelles. Le premier langage à introduire de telles opérations fut Lisp, et ce dès
les années 60. Par la suite, de nombreux langages, surtout les langages fonctionnels,
ont défini de telles opérations. De nos jours, la plupart des langages définissent de
telles opérations. L’exemple d’exécution 5.1 présente un exemple d’application et un
exemple de réduction exprimés dans trois langages : Lisp [Ste84], Haskell [Tho96] et
Ruby. De telles opérations sont aussi redevenues (très!) «à la mode» ces dernières
années avec l’introduction du modèle Map/Reduce de Google [DG08], popularisé
notamment grâce à Hadoop [Whi15].
• Ruby :
[1 , 2 , 3 , 4]. map { | x | 2 * x }
=>
[2 , 4 , 6 , 8]
• Lisp :
• Haskell :
n’ont pas d’effet de bord — donc pas d’interactions entre elles — on en déduit qu’une
application map est naturellement parallèle : toutes les applications de la fonction
aux divers éléments de la collection peuvent se faire en parallèle.
Dans le cas d’une réduction, si la fonction binaire utilisée pour la réduction est
associative — ce qui est habituellement le cas pour les opérations utilisées dans des
telles β-réductions, par exemple, +, ∗, MAX, MIN — alors l’ordre d’évaluation n’a pas
d’importance. On peut donc parenthéser cette expression de façon différente sans
changer le résultat2 . Par exemple, pour l’expression de réduction présentée plus
haut avec n = 8, alors les deux façons suivantes de parenthéser l’expression sont
équivalentes :
Figure 5.11: Graphes de dépendances pour une réduction β vs. une réduction β-
logarithmique.
Le Programme Ruby 5.18 présente une version parallèle d’une fonction pour ef-
fectuer la somme de deux tableaux à l’aide de pmap, et ce à l’aide de parallélisme à
granularité grossière, où les éléments à additionner sont répartis par blocs d’éléments
adjacents entre les nbt threads— par défaut, le mode de répartition est «static:
true». Difficile de faire plus simple!
Patrons de programmation en PRuby 274
Dans le Programme Ruby 5.19, qui utilise un pmap, on constate qu’après le pmap, il
est nécessaire de faire la sommation des résultats produits par chacun des threads. Il
s’agit donc d’un cas typique de réduction. Le Programme Ruby 5.20 présente donc
une nouvelle, et dernière, version parallèle de la fonction evaluer_pi, cette fois en
utilisant preduce. Là aussi, difficile de faire plus simple et plus succinct!
Patrons de programmation en PRuby 275
5.4.6 Factoriel
Programme Ruby 5.21 Fonction parallèle pour calculer fact(n) avec preduce.
def fact ( n , nbt )
(1.. n ). preduce ( 1 , nb_threads : nbt ) do | prod , k |
prod * k
end
end
Soit la classe Ensemble traitée dans le labo #1. dont voici une version possible :
class Ensemble
def initialize ( * elements )
@elements = []
elements . each do | x |
@elements << x unless @elements . include ? x
end
end
def max
fail " L ’ ensemble est vide " if cardinalite == 0
m = @elements [0]
@elements . each do | x |
m = [m , x ]. max
end
m
end
...
end
On veut une version parallèle de cette méthode — pmax.
1. Peut-on simplement remplacer each par peach pour obtenir une version avec
parallélisme de boucles?
Donnez une mise en oeuvre d’une méthode pselect qui est version parallèle de
select.
>> a = [*1..10]
=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Votre mise en oeuvre doit être aussi parallèle que possible. . . bien qu’une partie
puisse être faite de façon séquentielle — difficile de faire autrement /
Hypothèse/indice :
Créer des threads de façon dynamique peut être couteux, surtout si le nombre
de threads est élevé. De plus, comme on l’a vu avec l’exemple du calcul récursif et
parallèle de la fonction pour factoriel, il arrive souvent que le seul travail effectué
par un thread . . . soit de créer d’autres threads et d’attendre qu’ils terminent pour
combiner les solutions produites par les appels récursifs.
Les coûts élevés de création des threads peuvent être réduits lorsqu’on crée, une
seule fois, un nombre fixe de threads. Cette approche est particulièrement efficace
lorsque le nombre de threads est du même ordre de grandeur que le nombre de
processeurs.
Malheureusement, une répartition statique entre un nombre fixe de threads ne
fonctionne bien que si le travail à effectuer par chacun des threads prend sensible-
ment le même temps.
Patrons de programmation en PRuby 282
Supposons une répartition statique des tâches entre quatre (4) threads où chaque
thread est exécuté par un processeur indépendant et où le temps requis pour que
chaque thread traite son groupe de tâches est comme suit — l’unité de mesures n’a
pas d’importance :
• Thread 0 : 10
• Thread 1 : 40
• Thread 2 : 20
• Thread 3 : 20
Exercice 5.12: Temps d’exécution et accélération pour des tâches de temps vari-
able.
Ce qu’il faudrait est une approche qui permet d’utiliser un nombre fixe et
limité de threads, créés en une seule fois, tout en permettant une répartition
plus égale du travail à faire entre les threads. Une telle approche est possible avec
une répartition dynamique des tâches ainsi qu’avec l’utilisation d’une approche
de type «Coordonnateur/Travailleurs».
Patrons de programmation en PRuby 283
$ wc foo.txt
4 10 40 foo.txt
Le problème qu’on veut traiter est le suivant : étant donné une liste de fichiers
(Array), on veut obtenir une liste de résultats équivalents à ceux produit par wc.
Le Programme Ruby 5.22 présente une première solution, mise en oeuvre avec
pmap :
Pour que le traitement se fasse de façon parallèle, un pmap est utilsé sur la liste
des fichiers. Aucun argument n’étant spécifié, on utilisera donc PRuby.nb_threads
threads — i.e., un nombre fixe de threads — et une répartition statique par bloc —
pmap = pmap() = pmap( static: true, nb_threads: PRuby.nb_threads ).
Une solution simple au problème identifié dans l’exercice 5.13 consiste à définir
wc comme suit :
def wc ( fichs )
fichs . pmap ( dynamic : true ) do | fich |
wc1 ( fich )
end
end
Patrons de programmation en PRuby 285
Un appel à pmap qui utilise «dynamic: true» est équivalent à un appel avec
«dynamic: 1». Comme dans le cas statique, on va créer un nombre fixe de threads
— égal à PRuby.nb_threads si le nombre de threads n’est pas spécifié explicitement.
La différence par rapport à static est que ces threads vont se répartir les éléments
à traiter non pas au moment du lancement des threads, mais en cours d’exécution,
au fur et à mesure où les éléments de la collection auront été traités.
Donc, lorsqu’un thread est activé, sa première action est d’obtenir le prochain
élément à traiter parmi ceux qui ne sont pas encore traités. Lorsque le thread
termine de traiter cet élément, il tente alors d’obtenir le prochain élément qui n’a
pas encore été traité. Finalement, l’exécution du thread se termine lorsqu’il n’y
a plus aucun élément à traiter.
Cette façon de procéder permet de mieux répartir la charge de travail entre les
threads. Ainsi, il est possible que pendant qu’un thread traite un très gros fichier
— donc très long à parcourir — un autre thread traite plusieurs petits fichiers. Au
final, les chances que tous les threads finissent en même temps, ou presque, sont
donc améliorées.
Il est aussi possible d’augmenter la granularité des tâches simplement en spéci-
fiant comme valeur un entier supérieur à 1. Dans notre exemple, si on avait utilisé
l’appel «fichs.pmap( dynamic: 5 ) {. . . }», alors un thread aurait obtenu les noms
de fichiers à traiter par blocs de 5 — ou moins pour le dernier bloc lorsque le nombre
total d’éléments n’est pas divisible par 5.
terminé ← false
WHILE !terminé DO
obtenir une tâche du sac_tâches # Bloquant!
IF il restait une tâche à exécuter THEN
exécuter la tâche obtenue... possiblement
en générant de nouvelles tâches
ELSE
terminé ← true
END
END
END
res
end
• C’est la méthode each qui permet à chacun des threads d’obtenir une tâche
du sac. Un thread donné ne recevra pas toutes les tâches, uniquement un
sous-ensemble — en d’autres mots, les tâches vont se répartir entre les divers
threads par l’intermédiaire du each, mais pas nécessairement de façon uniforme
puisqu’il s’agit d’un comportement dynamique.
– Si un thread tente d’obtenir une tâche et que le sac n’est pas vide, alors
l’une des tâches est retirée du sac et retournée au travailleur — c’est un
sac, donc l’ordre de retrait des tâches est indéterminé.
– Si un thread tente d’obtenir une tâche et que le sac est présentement
vide, alors le comportement dépend de l’état des autres threads, d’où
l’importance de connaitre le nombre de threads qui se partagent le sac :
∗ Il y a encore des threads actifs, i.e., qui ne sont pas bloqués en attente
d’une tâche : dans ce cas, le thread est mis en attente. . . parce qu’un
des autres threads encore actifs pourrait ajouter une nouvelle tâche
dans le sac.
∗ Le thread est le dernier thread actif : dans ce cas, il est impossible
que d’autres tâches soient ajoutées au sac. Tous les threads bloqués
doivent alors être réactivés en signalant que le sac est définitivement
vide, qu’il n’y aura plus de tâches à traiter, et donc qu’ils peuvent —
Patrons de programmation en PRuby 288
Cet exemple permet d’illustrer le fonctionnement d’un sac de tâches, mais son
utilisation n’est pas strictement nécessaire, puisqu’un simple pmap avec dynamic
aurait été suffisant. C’est le cas parce que toutes les tâches sont créées une fois pour
toute par le coordonnateur, au moment de la création du sac lorsque les travailleurs
sont lancés. En d’autres mots, l’exécution d’une tâche n’entraîne pas la création de
nouvelles tâches.
res
end
Le Programme Ruby 5.24 présente une fonction mystere qui utilise un TaskBag et
où l’ajout de nouvelle tâches se fait vraiment de façon dynamique — une nouvelle
tâche peut être ajoutée au sac (avec TaskBag#put) pendant la traitement d’une
tâche.
Plus précisément, au début de la fonction mystere, le coordonnateur ajoute
une seule et unique tâche dans le sac — la tâche 1..n. Par la suite, ces sont les
travailleurs qui ajoutent de nouvelles tâches de la forme (m+1)..j (dans le while).
res
end
end
1. Que fait cette méthode? Quel nom plus significatif peut-on lui donner?
2. Écrivez une version équivalente de cette méthode, mais qui utilise plutôt du
parallélisme de boucles — donc avec peach ou peach_index.
10 20 30 40 50 100 200 50 40 30 20 10
Supposons qu’on ne considère que les temps indiqués, donc en ignorant les autres
surcoûts d’exécution.
Pour chaque appel ci-bas, indiquez quelles tâches seront attribuées à chaque
thread et quel sera le temps total d’exécution.
Note : On suppose que les threads obtiennent les tâches dans l’ordre de priorité de leur
numéro — donc le premier thread obtient la première tâche, etc., puis par la suite si deux
threads veulent une tâche «en même temps», alors c’est le thread avec le plus petit numéro
qui obtient une tâche en priorité.
3
https://golang.org/
Patrons de programmation en PRuby 292
Unix tradition strongly encourages writing programs that read and write
simple, textual, stream-oriented, device-independent formats. Under clas-
sic Unix, as many programs as possible are written as simple filters,
which take a simple text stream on input and process it into another
simple text stream on output.
Despite popular mythology, this practice is favored not because Unix pro-
grammers hate graphical user interfaces. It’s because if you don’t write
programs that accept and emit simple text streams, it’s much more diffi-
cult to hook the programs together.
E. Raymond [Ray04]
cat $1.tex \
| sed ’/\\begin{figure}/,/\\end{figure}/d’ \
| sed ’/\\begin{table}/,/\\end{table}/d’ \
| grep -v "^%" \
| tr "[~]" "[ ]" \
| tr "[\t]" "[\n]"\
| tr "[ ]" "[\n]"\
| grep -v ’\\’ \
| wc -w
Figure 5.15: Script Unix pour supprimer des commandes LATEX dans un fichier et
compter le nombre de «vrais» mots d’un document.
• sed : “The sed utility is a stream editor that reads one or more text files,
makes editing changes according to a script of editing commands, and writes
the results to standard output.
• grep : “The grep utility searches files for a pattern and prints all lines that
contain that pattern.”
4 A
LTEX est un langage et système pour composer des documents, fondé sur l’utilisation de TEX.
Les commandes LATEX sont indiquées par des identificateurs qui débutent par un «\», par exemple,
\section{...}, \title{...}, \begin{...}, etc.
Patrons de programmation en PRuby 293
Note : Rôle de l’option “-v” de grep : “Print all lines except those that contain
the pattern.
• tr : “The tr utility copies the standard input to the standard output with
substitution or deletion of selected characters.”.
• wc : “The wc utility reads one or more input files and, by default, writes the
number of newline characters, words and bytes contained in each input file to
the standard output.”.
Note : Rôle de l’option “-w” de wc : “Count words delimited by white space
characters or new line characters.”
Un filtre est défini à l’aide d’une lambda-expression, laquelle doit recevoir deux
arguments. Ce sont ces arguments qui donnent accès aux deux canaux associés
au filtre — le canal d’entrée, typiquement dénoté par cin, et le canal de sortie,
typiquement dénoté par cout :
Figure 5.16: Les principales méthodes de la classe Channel : initialize, get, put,
each et close (1ère partie).
Patrons de programmation en PRuby 296
Figure 5.16: Les principales méthodes de la classe Channel : initialize, get, put,
each et close (2e partie).
Patrons de programmation en PRuby 297
Programme Ruby 5.25 Fonction pour trier les mots d’un fichier, en s’assurant
que chaque mot apparaît au plus une fois.
def trier_mots_uniques ( fich_entree , fich_sortie )
generer_mots = lambda do | cin , cout |
cin . each do | ligne |
ligne . split ( /\ s +/ ). each { | mot | cout << mot }
end
cout . close
end
2. Le canal de sortie, sur lequel le processus peut appeler la méthode put, dans
le but de transférer un élément au voisin droite. Un synonyme pour cette
méthode est l’opérateur «<<».
Dans notre exemple, la tâche globale est décomposée en six (6) sous-tâches
plus simples, six processus qui pourront s’exécuter de façon concurrente et qui
s’échangeront des données et se synchroniseront par l’intermédiaire des canaux qu’ils
partagent :
• PRuby.pipeline_source : Cette méthode crée un processus, sans canal d’entrée,
qui reçoit en argument un nom de fichier (ou un Array) et qui émet sur son
canal de sortie les lignes — l’une après l’autre — puis qui ferme le canal de
sortie lorsque la fin du fichier est rencontrée, ce qui a pour effet d’émettre
PRuby::EOS sur ce canal de sortie.
5
Il est aussi possible de ne pas attendre/bloquer. Pour ce faire, il suffit d’appeler run avec
l’argument :NO_WAIT.
Patrons de programmation en PRuby 300
• generer_mots : Reçoit sur son canal d’entrée des lignes de texte et émet sur
son canal de sortie les mots – les suites de caractères sans espace blanc —
contenus sur chacune des lignes.
• trier : Reçoit sur son canal d’entrée une suite de mots et émet sur le canal
de sortie ces même mots, mais triés.
• supprimer_doublons : Reçoit sur son canal d’entrée une suite de mots triés
et n’émet sur le canal de sortie que la première occurrence d’un mot lorsqu’un
mot apparaît plusieurs fois de suite (mots consécutifs, puisque triés).
Figure 5.17: Graphe des processus et de leurs canaux pour les filtres et le pipeline
du Programme Ruby 5.25.
abc def
abc xx ! def
xx
Patrons de programmation en PRuby 301
Les éléments qui transiteront dans chacun des canaux seront alors les suivants —
indiqués sous forme d’une liste, en ignorant les caractères de saut de ligne, l’élément
à la position 0 indiquant le premier élément à transiter sur le canal, etc — on ignore
les "\n" :
c0: [’abc def’, ’abc xx ! def’, ’xx’, EOS]
c1: [’abc’, ’def’, ’abc’, ’xx’, ’!’, ’def’, ’xx’, EOS]
c2: [’abc’, ’def’, ’abc’, ’xx’, ’def’, ’xx’, EOS]
c3: [’abc’, ’abc’, ’def’, ’def’, ’xx’, ’xx’, EOS]
c4: [’abc’, ’def’, ’xx’, EOS]
• On veut produire en sortie un fichier texte, avec les mêmes caractères, y com-
pris les blancs, mais où toutes les lignes sont exactement de longueur n — sauf
peut-être la dernière ligne.
• La seule différence au niveau des caractères émis est que lorsqu’on rencontre
deux caractères «*» consécutifs dans le flux d’entrée, alors on doit les rem-
placer par le caractère unique «^».
Entree:
-------
abc ** dsds cssa
ssdsx
fssfdfdfdfdfdf
s.s.**xtx*zy
Sortie:
-------
abc
^ ds
ds c
ssas
sdsx
fssf
dfdf
dfdf
dfs.
s.^x
tx*z
y
Figure 5.18: Exemple d’un fichier d’entrée et du fichier de sortie correspondant pour
le problème de Jackson avec n=4.
Patrons de programmation en PRuby 304
Figure 5.19: Graphe des processus et de leurs canaux pour les filtres et le pipeline
du Programme Ruby 5.26.
res = []
# Ecriture initiale dans le premier canal => amorce le flux des donnees.
c1 << 10
Le Programme Ruby 5.27 illustre la création d’un petit pipeline (linéaire) com-
portant trois processus et quatre canaux (c1, c2, c3 et c4). Tant les canaux que
les processus sont créés explicitement, dans un style semblable à ce qu’on écrirait
dans le cadre du langage Go.6
6
https://golang.org/
Patrons de programmation en PRuby 308
• Le pipeline construit dans l’exemple est semblable à celui qui serait obtenu
avec l’utilisation de l’opérateur «|» : ...| p1 | p2 | p3 | ...
Lorsqu’on manipule des pipelines dans le style Unix, la création des canaux
et leur association aux processus est implicite — les canaux sont créés et
liés aux processus par la bibliothèque PRuby, lors de l’appel à la méthode
«|». Par contre, dans le style Go, on doit créer explicitement les canaux et les
transmettre explicitement aux processus (via la méthode go) pour les lier.
7
Notons que, dans notre exemple, il n’y a pas de source ou puits explicite, et ce pour simplifier
la présentation du code.
Patrons de programmation en PRuby 309
Programme Ruby 5.28 Fonction pour trier les mots d’un fichier, en s’assurant
que chaque mot apparaît au plus une fois — version avec streams.
def trier_mots_uniques ( fich_entree , fich_sortie )
PRuby :: Stream . source ( fich_entree )
. flat_map { | ligne | ligne . split ( /\ s +/ ) }
. filter { | mot | /^\ w + $ / =~ mot }
. sort
. uniq
. sink ( fich_sortie )
end
Le Programme Ruby 5.28 présente une fonction pour trier les mots d’un fichier,
en s’assurant que chaque mot apparaît au plus une fois — donc une fonction avec
un effet identique à celui de la fonction du Programme Ruby 5.25 (p. 298).
Ici, cette fonction utilise les streams de la bibliothèque PRuby pour obtenir l’effet
désiré, et ce en utilisant aussi du parallélisme de flux.
Quelques explications :
• Un stream est une forme de collection sur laquelle plusieurs des méthodes
associées aux collections Ruby peuvent être utilisées — donc, plusieurs des
méthodes du module Enumerable. Certaines de ces méthodes produisent un
résultat qui est lui-même un stream — e.g., map, filter, reject, etc. — alors
que d’autres produisent un résultat d’un autre type — e.g., reduce.
• Une caractéristique importante d’un stream est qu’il s’agit typiquement d’une
collection potentiellement infinie — donc non bornée (unbounded )
— produite de façon incrémentale. Des exemples de tels flux de don-
nées sont des données en temps réel, par exemple, informations de réseaux
de senseurs, paquets de traffic Internet, données financières (on-line financial
trading), fichiers de journalisation (log files), etc.
8
https://docs.oracle.com/javase/8/docs/api/java/util/stream/package-summary.
html
Patrons de programmation en PRuby 310
Exemple Ruby 5.2 Exemples pour illustrer les méthodes flat_map, filter et
uniq de la classe PRuby::Stream.
# Exemple flat_map
a = [1 , 0 , 2 , 0 , 3 , 4 , 0]
r = [1 , 1 , 2 , 2 , 3 , 3 , 4 , 4]
# Exemple filter
a = [1 , 2 , 3 , 4]
r = [2 , 4]
# Exemple uniq .
a = [3 , 1 , 4 , 2 , 2 , 3 , 1]
r = [3 , 1 , 4 , 2]
Programme Ruby 5.29 Fonction parallèle itérative à granularité fine pour faire
la somme de deux tableaux avec pcall.
def somme_tableaux ( a , b )
c = Array . new ( a . size )
c
end
Programme Ruby 5.30 Fonction parallèle itérative pour faire la somme de deux
tableaux avec pcall.
# Les indices pour la tranche du thread no . k .
def indices_tranche ( k , n , nb_threads )
( k * n / nb_threads )..(( k + 1) * n / nb_threads - 1)
end
c
end
Programme Ruby 5.31 Fonction parallèle itérative pour faire la somme de deux
tableaux avec pcall.
def somme_seq_cyclique ( a , b , c , num_thread , nb_threads )
( num_thread ... a . size ). step ( nb_threads ). each do | k |
c[k] = a[k] + b[k]
end
end
c
end
c
end
316
Chapitre 6
317
Métriques de performance 318
Dans les sections qui suivent, nous allons examiner diverses métriques perme-
ttant de caractériser les performances d’un algorithme, ou d’un programme, par-
allèle. La plupart de ces métriques seront , comme on l’a fait pour analyser les
Métriques de performance 319
Une telle approche est semblable à celle décrite par G. Blelloch [Ble96], qui parle
plutôt de la notion de profondeur (depth) du calcul associée à un algorithme.
Définition 2 La profondeur d’un calcul effectué par un algorithme est définie comme
la longueur de la plus longue chaîne de dépendances séquentielles présentes
dans ce calcul.
longueur du chemin critique (critical path length) est aussi parfois utilisé au lieu du
terme profondeur.
Nb. Temps
d’UE min.
1 9
2 6
3 6
4 6
... ...
Figure 6.1: Graphe de dépendances pour calcul d’une racine d’un polynome de
deuxième degré pour illustrer la notion du meilleur temps parallèle comme longueur
du plus long chemin.
Métriques de performance 322
Figure 6.2: Graphe de dépendances pour calcul de la somme d’un tableau de huit
éléments, pour illustrer la notion du meilleur temps parallèle comme longueur du
plus long chemin.
Métriques de performance 323
Ici, on parle de coût d’un algorithme puisque si une machine qui exécute cet
algorithme doit, à un certain point de son fonctionnement, avoir jusqu’à p(n) pro-
cesseurs, alors la machine dans son ensemble avec les p(n) processeurs doit fonction-
ner durant TP (n) cycles, et ce même si certains des processeurs ne sont pas utilisés
durant tout l’algorithme.
6.3.2 Travail
Une autre caractéristique intéressante d’un algorithme parallèle est celle du travail
total effectué par l’algorithme.
Le travail effectué par un algorithme parallèle nous donne donc, d’une certaine
façon, le temps requis (plus précisément, un ordre de grandeur) pour faire simuler
l’exécution de l’algorithme parallèle par un programme à un seul processus, pro-
gramme qui simulerait l’exécution parallèle de plusieurs opérations en exécutant,
une après l’autre, les diverses opérations. On reviendra ultérieurement sur cette
notion de simulation.
plus précis du nombre total exact d’opérations exécutées qui tient compte du
fait que ce ne sont pas nécessairement tous les processeurs qui travaillent durant
toute la durée de l’algorithme.
• Séquentiel :
• Parallèle :
Soit le graphe suivant, qui représente les opérations et leurs dépendances pour faire
la somme d’un tableau v comptant n éléments :
Une autre différence importante entre le coût et le travail est la suivante :alors
que le travail est une métrique compositionnelle, ce n’est pas le cas pour le coût.
Plus précisément, soit S1 et S2 deux segments de code. Le travail effectué pour
la composition séquentielle de ces deux segments de code sera simplement la somme
du travail de chaque segment. En d’autres mots, on aura l’équivalence suivante :
Par contre, cette équivalence ne s’applique pas nécessairement pour le coût, puisque
les différentes étapes peuvent ne pas utiliser le même nombre de processeurset que
le coût ne s’intéresse qu’au nombre maximum de processeurs requis. Pour le travail,
Métriques de performance 330
co [j = 1 to lg(n)]
proc( a, n )
oc
}
Algorithme 6.1: Petit algorithme pour illustrer que le coût n’est pas une métrique
compositionnelle. Quel est le temps de cet algorithme? Quel est son travail? Quel
est son coût?
6.3.4 Optimalité
Soit un problème pour lequel on connaît un algorithme séquentiel optimal s’exécutant
en temps TS∗ (n) (pour un problème de taille n).
Métriques de performance 331
Soulignons qu’un algorithme optimal, dans le sens décrit dans cette définition,
assure que l’accélération résultante (voir prochaine section) de l’algorithme optimal
sur une machine à p processeurs sera Θ(p), c’est-à-dire résultera en une accélération
linéaire.
Question : L’algorithme avec le graphe de l’exercice précédent est-il optimal en
travail? En coût?
Métriques de performance 332
TP (1, n)
Arp =
TP (p, n)
TS∗ (n)
Aap =
TP (p, n)
1
Notons qu’on peut aussi vouloir utiliser des algorithmes et programmes parallèles dans le but
surtout de résoudre des problèmes de plus grande taille. Ceci est particulièrement le cas lorsque
qu’on utilise des machines parallèles à mémoire distribuée, dont l’espace mémoire est plus grand,
puisque composé de la mémoire des différentes machines.
Métriques de performance 333
Quelle est en théorie la meilleure accélération absolue qu’il est possible d’obtenir?
TS∗ (n)
Aap = ≤ ?
TP (p, n)
Exercice 6.2: Meilleure accélération pour une machine avec p processeurs.
• Registres ;
2
• Cache(s) ;
• Mémoire (DRAM).
Les niveaux les plus près du processeur ont un temps d’accès plus rapide, mais
sont plus coûteux à mettre en oeuvre, donc sont de plus petite taille.
Il arrive parfois que l’exécution d’un programme sur une machine uni-processeur
nécessite un espace mémoire qui conduit à de nombreuses fautes de caches, par
ex., à cause de la grande taille des données à traiter. Or, lorsqu’on exécute le
même programme mais sur une machine multi-processeurs avec une mémoire cache
indépendante pour chaque processeur, le nombre total de fautes de caches est alors
réduit de façon importante (parce que l’ensemble des données peut maintenant entrer
dans l’ensembles des mémoires cache), conduisant à une accélération supérieure à
une accélération linéaire.
d’autres mots, le cas idéal est lorsque les p processeurs sont utilisés à 100 % — ce
qui est très rare!.
Signalons aussi que, en pratique, on mesurera l’efficacité comme on le fait pour
l’accélération, c’est-à-dire, en variant le nombre de threads et en définissant p comme
le nombre de threads utilisés.
Par contre, un processus, au sens Unix du terme, contient en gros les éléments
suivants :
– Registres ;
– Variables locales ;
– Tas (heap) ;
– Descripteurs de fichiers et pipes ouverts/actifs ;
– Gestionnaires d’interruption ;
– Code du programme.
Dans le cas des threads, certains des éléments qui sont présents dans le contexte
d’un processus et qui sont requis pour exécuter les divers threads — par ex.,
le code du programme — sont plutôt partagés entre les threads, des threads
étant toujours définis dans le contexte d’un processus.
Or, la création et l’amorce d’un nouveau thread ou processus demande toujours
d’allouer et d’initialiser un contexte approprié. De plus, un changement de
contexte survient lorsqu’on doit suspendre l’exécution d’un thread (parce qu’il
a terminé son exécution, parce qu’il devient bloqué, ou parce que la tranche
de temps (time slice) qui lui était allouée est écoulée) et sélectionner puis
réactiver un nouveau thread.
Effectuer ces opérations introduit donc des surcoûts qui peuvent devenir im-
portant si, par exemple, le nombre de threads est nettement supérieur au
nombre de processeurs, conduisant ainsi à de nombreux changement de con-
texte.
Métriques de performance 337
• La section qui suit est (en partie) une traduction et (en partie) une adaptation
du chapitre intitulé «Performance analysis» du livre de M.J. Quinn «Parallel
Programming in C with MPI and OpenMP » [Qui03, Chap. 7].
• Parmi les modifications, des détails supplémentaires ont été ajoutés pour les
manipulations algébriques, et certains éléments de notation ont été simplifiés
ou modifiés pour refléter la notation utilisée dans la première partie des notes
de cours :
Notation de Quinn Notation utilisée
Temps partie σ(n) σ
séquentielle
Temps partie ϕ(n) ϕ
parallèle
Accélération ψ(n, p) ψ
T (1, n) = σ + ϕ (6.1)
Définition 10 (Loi d’Amdahl) Soit f la fraction des opérations qui doivent être
exécutées de façon séquentielle, avec 0 ≤ f ≤ 1. Alors, l’accélération maximale ψ
pouvant être obtenue avec p processeurs est la suivante :
1
ψ ≤
f + (1 − f )/p
Exemples :
ϕ(n)
T (p, n) = σ(n) + + κ(n, p)
p
L’effet Amdahl
Règle générale, la complexité de κ(n, p) est plus faible que celle de ϕ(n). C’est-à-dire
que le temps d’exécution augmente plus rapidement (en fonction de n) que le temps
de synchronisation et communication (en fonction de n et p).
Donc, pour un nombre fixe de processeurs, l’accélération va généralement aug-
menter lorsqu’on augmente la taille du problème. En d’autres mots, plus la taille
du problème est grande, plus l’accélération est grande.
⇒ L’accélération augmente
Notons par s la fraction du temps d’exécution parallèle consacrée aux opérations
séquentielles, i.e., s est définie comme suit : 5
σ
s =
σ + ϕ/p
σ = (σ + ϕ/p)s
5
On remarque la différence par rapport à la définition de la fraction f , où f était définie par
rapport au temps séquentiel (pour un processeur) et non par rapport au temps parallèle (pour p
processeurs) :
σ
f =
σ+ϕ
Donc, alors que f était la fraction du temps pour l’exécution de la partie intrinsèquement séquen-
tielle sur une machine uniprocesseur, s est la fraction du temps pour l’exécution de la partie
intrinsèquement séquentielle sur machine parallèle à p processeurs.
Métriques de performance 343
6
Et :
ϕ = (σ + ϕ/p)(1 − s)p
ψ ≤ p + (1 − p)s
Cette accélération peut donc être inteprétée comme étant définie comme suit
(voir Figure au tableau) :7
Signalons que Gustafson [Gus88] a formulé cette loi après avoir constaté, ex-
périmentalement, que certains problèmes s’exécutaient de façon très efficace, i.e.,
avec une forte accélération, sur des machines avec un grand nombre de processeurs
(accélération ≈ 1016–1020 pour 1024 processeurs).
Exemple :
8
http://en.wikipedia.org/wiki/Gustafson’s_law
Métriques de performance 345
• Loi d’Amdhal
• Gustafson-Barsis
– (1 + 4*9) / 10 = 37 / 10 = 3.7
Alors :
σ = eT (1, n)
Donc :
ϕ
T (p, n) = σ + (6.4)
p
(1 − e)T (1, n)
= eT (1, n) + (6.5)
p
Soit l’accélération9 , notée ψ, définie comme suit :
T (1, n)
ψ = (6.6)
T (p, n)
Donc :
T (p, n) = eT (1, n) + (1 − e)T (1, n)/p [De (6.5)]
= eψT (p, n) + (1 − e)ψT (p, n)/p [Déduit de (6.6)]
Exemples [KF90] :
• Pour qu’une machine soit utilisée efficacement, il faut que la charge soit bien
balancée entre les processeurs — temps de travail équivalent pour chacun des
processeurs.
Supposons qu’on a 12 tâches à distribuer. Pour p = 2, 3, 4, 6 et 12, la charge
sera bien balancée entre les processeurs. Par contre, pour d’autres valeurs
de p, la charge ne sera pas bien balancée, même si l’accélération s’améliore.
Or, un débalancement de la charge va conduire à des valeurs anormalement
croissantes de la fraction e.
Programme Java 6.1 Une fonction parallèle evaluerPi (et sa fonction auxiliaire
nbDansCercleSeq) pour approximer la valeur de π à l’aide de la méthode de Monte
Carlo à plusieurs threads.
@SuppressWarnings ( " unchecked " )
public static double evaluerPi ( final int nbLancers ,
int nbThreads ) {
ExecutorService pool =
Executors . newFixedThreadPool ( nbThreads );
Future < Integer > lesNbs [] = new Future [ nbThreads ]; // unchecked cast
for ( int k = 0; k < nbThreads ; k ++ ) {
lesNbs [ k ] = pool . submit ( () -> {
return nbDansCercleSeq ( nbLancers / nbThreads );
} );
}
int nbTotalDansCercle = 0;
for ( int k = 0; k < nbThreads ; k ++ ) {
try { nbTotalDansCercle += lesNbs [ k ]. get (); }
catch ( Exception ie ) {}
}
pool . shutdown ();
Figure 6.7: Graphe donnant le temps d’exécution du programme Pi.java pour dif-
férents nombres de threads. Les temps sont indiqués pour trois (3) séries différentes
d’exécution.
La Figure 6.7 présente les temps d’exécution pour trois séries distinctes d’exécution
du programme Java 12.2, et ce en faisant varier le nombre de threads — 1, 2, 4, 8,
16, . . . , 1024 threads. Dans tous les cas, on effectue un total de 10 000 000 lancers
— donc 10 000 000 lancers partagés entre les divers threads.
Quelques remarques sur ces expérimentations et résultats :
• L’échelle des x, qui indique le nombre de threads Java, est logarithmique. C’est
ce qui explique que l’écart entre les valeurs indiquées sur cet axe est constant,
même si à chaque fois on double le nombre de threads.
Métriques de performance 352
• Le temps pour une exécution avec un certain nombre de threads n’est pas
toujours le même — il varie d’une fois à une autre. Cela est tout à fait normal
et usuel, car plusieurs facteurs peuvent influencer le temps d’exécution —
ordre différent de préemption des threads, temps variable d’accès au cache ou
à la mémoire, etc.
figures 6.8 et 6.9, quant à elles, présentent les deux graphes suivants :
Méthodologie pour la
programmation parallèle et patrons
d’algorithmes
7.1 Introduction
Ce chapitre présente tout d’abord une «méthodologie» — en fait, plutôt une «heuris-
tique» — pour la programmation parallèle en mémoire partagée — donc avec threads
— qui s’inspire de l’approche PCAM présentée par I. Foster [Fos95] :
http://wotug.org/parallel/books/addison-wesley/dbpp/
355
Méthodologie de programmation parallèle 356
7.2.1 Objectifs
Les objectifs (parfois contradictoires) qui sont visés par l’approche PCAM sont les
suivants :
DEBUT
FIN
FIN
Figure 7.1: Arbre de décision pour choisir entre une stratégie statique vs. dynamique
d’association (mapping) des tâches aux threads.
Source : http://www.dais.unive.it/~calpar/
Figure 7.2: Courbe illustrant l’effet général de la taille des grains (des tâches) sur
le temps d’exécution.
Figure 7.3: Courbe illustrant l’effet général de la taille des grains (des tâches) sur
la performance.
Méthodologie de programmation parallèle 363
Parallélisme «embarrassant»
Certains problèmes peuvent facilement être décomposés en un grand nombre de
parties indépendantes, donc où chaque partie peut s’exécuter en parallèle, sans
aucune contrainte ou dépendance. On parle alors de parallélisme «embarrassant»
(embarassingly parallel ).
• Parce que créer et gérer une tâche parallèle et un thread peut être relativement
coûteux. Pour la figure 7.5, utiliser une tâche parallèle et un thread pour
chaque pixel impliquerait d’avoir un million de threads!
Parallélisme «semi-embarrassant»
Un problème avec parallélisme «semi-embarrassant», comme pour le cas précé-
dent, peut être décomposé en un grand nombre de tâches qui sont indépendantes,
mais pas tout à fait complètement : les tâches interagissent, mais de façon limitée,
et souvent uniquement vers la fin de l’exécution des tâches.
Un problème relativement simple ayant cette propriéte est celui visant à estimer
la valeur de π à l’aide d’une méthode de Monte Carlo : voir section 5.2.3 (p. 248). Le
graphe de dépendances des tâches ressemble alors à celui de la figure 7.7 : le gros du
travail — la simulation des lancers — se fait de façon complètement indépendante
par chacun des threads, et ce n’est qu’à la toute fin qu’il suffit d’additionner les
résultats calculés par chacun d’entre eux!
Méthodologie de programmation parallèle 368
Parallélisme récursif
De nombreux problèmes peuvent être résolus par un algorithme récursif, et ce en
utilisant l’approche «diviser-pour-régner» — voir sections A.1 et 5.2 pour plus de
détails. L’approche diviser-pour-régner peut être décrite comme suit :
SI le problème est simple ALORS
On trouve la solution directement
SINON
On décompose le problème en sous-problèmes
On résout récursivement les sous-problèmes
On combine les solutions des sous-problèmes
pour obtenir la solution du problème initial
FIN
• Etc.
Mais, comme on l’a vu dans un exercice fait précédememnt, il est tout à fait
possible de mettre en oeuvre une stratégie diviser-pour-régner. . . sans utiliser de
récursion — par exemple, avec un pool de threads et un sac de tâches.
Dans les premières machines parallèles de type SIMD — Single Instruction, Mul-
tiple Data — une telle forme de parallélisme était le fondement même des calculs
parallèles — en fait, la seule forme exploitable de parallélisme. Toutefois, une par-
ticularité de ces machines, qu’on ne cherche pas à reproduire lorsqu’on développe des
algorithmes avec parallélisme de données, est le fait que dans une machine SIMD,
c’est exactement la même instruction qui s’exécute sur tous les processeurs en
même temps, de façon synchrone.
Dans les machines modernes où le parallélisme de données est aussi le fondement
des calculs — par exemple les GPU — le modèle SIMD a été assoupli et chaque unité
d’exécution va exécuter le même segment de code — souvent appelé kernel — donc
la même procédure. On se rapproche donc d’un modèle SPMD — Single Program,
Méthodologie de programmation parallèle 371
res . peach_index do | k |
res [ k ] = foo ( col [ k ] )
end
res
end
Parallélisme de résultat
Une stratégie intéressante et souvent utile dans le contexte du parallélisme de don-
née, stratégie proposée par Carriero & Gelernter [CG89], est celle du parallélisme
de résultat. Dans cette approche, on identifie le parallélisme en partant du produit
final, i.e., en partant du résultat désiré et en tentant de le décomposer en morceaux
indépendants. On attribue ensuite à chaque travailleur la tâche de produire un
morceau du résultat final.
Méthodologie de programmation parallèle 372
Rappel : X
C[i, j] = A[i, k] × B[k, j]
k
On veut paralléliser la fonction histogramme présentée plus bas, fonction qui produit
un histogramme pour les entiers d’un tableau elems.
Chaque nombre d’elems est un entier compris entre 0 et val_max (incl.). Les bornes
du tableau résultant, e.g., histo, sont comprises entre 0 et val_max (incl.) tel que :
histo[val] = nombre d’occurrences de val dans elems
histo == [0, 4, 1, 4, 0, 0, 0, 0, 0, 1, 2]
histogramme
end
Exercice 7.1: Production d’un histogramme pour une série d’entiers bornés.
Décomposition géométrique
La motivation de ce patron est la suivante, patron aussi appelé décomposition du
domaine :
This pattern is used when (1) the concurrency is based on parallel updates
of chunks of a decomposed data structure, and (2) the update of each
chunk requires data from other chunks.
Source : http: // www. cise. ufl. edu/ research/ ParallelPatterns/
Méthodologie de programmation parallèle 377
• Un Noeud a toujours deux enfants, gauche et droite, mais n’a pas de champ
valeur.
On obtient alors facilement un algorithme parallèle récursif tel qu’illustré dans
le Programme Ruby 7.1.
Voici un petit exemple d’arbre avec deux noeuds internes et trois feuilles crées
et manipulés avec les méthodes du Programme Ruby 7.1 :
a = Noeud.new(
Noeud.new( Feuille.new(10),
Feuille.new(30) ),
Feuille.new(40)
)
#<Noeud:0x48b67364
@droite=#<Feuille:0x189cbd7c @valeur=40>,
@gauche=#<Noeud:0x7bf3a5d8
@droite=#<Feuille:0x42e25b0b @valeur=30>,
@gauche=#<Feuille:0x39b43d60 @valeur=10>
>
>
puts a.somme
=>
80
Méthodologie de programmation parallèle 378
def somme
@valeur
end
end
...
def somme
fg = PRuby . future { gauche . somme }
fd = droite . somme
fg . value + fd
end
end
Méthodologie de programmation parallèle 379
381
Approche PCAM et exemples de programmes 382
surgery
surery -- Suppression de g
surey -- Suppression de r
survey -- Insertion de v
surgery
urgery -- Suppression de s
rgery -- Suppression de u
gery -- Suppression de r
ery -- Suppression de g
very -- Insertion de v
vey -- Suppression de r
svey -- Insertion de s
suvey -- Insertion de u
survey -- Insertion de r
surgery
survery -- Substitution de g par v
survey -- Suppression de r
Programme Ruby 8.1 Fonction récursive pour calculer la distance d’édition entre
deux chaines avec un cout unitaire pour les opérations.
def cout_subst ( c1 , c2 )
c1 == c2 ? 0 : 1
end
# Cas recursifs
avec_insertion =
distance ( ch1 , ch2 [0.. -2] ) + 1
avec_suppression =
distance ( ch1 [0.. -2] , ch2 ) + 1
avec_substitution =
distance ( ch1 [0.. -2] , ch2 [0.. -2] ) +
cout_subst ( ch1 [ -1] , ch2 [ -1])
La figure 8.2 présente l’arbre des appels récursifs pour un appel initial à la fonction
avec «distance( "ad", "axe" )».
Que constate-t-on quant aux appels récursifs qui sont effectués lors du calcul de la
distance d’édition entre "ad" et "axe"?
Exercice 8.1: Arbre des appels récursifs pour le calcul de distance d’édition.
Approche PCAM et exemples de programmes 384
Figure 8.2: Arbre des appels pour un appel initial à distance("ad", "axe").
Approche PCAM et exemples de programmes 385
Figure 8.3: Arbre des appels pour un appel initial à distance("ad", "axe") avec
indication des résultats retournés — cas de base notés par «=», cas récursifs notés
par «=>».
Approche PCAM et exemples de programmes 386
D(0, 0) = 0
D(i, 0) = D(i − 1, 0) + coûtsup (ch1[i − 1])
D(0, j) = D(0, j − 1) + coûtins (ch2[j − 1])
D(i − 1, j) + coûtsup (ch1[i − 1])
D(i, j) = min D(i, j − 1) + coûtins (ch2[j − 1])
D(i − 1, j − 1) + coûtsub (ch1[i − 1], ch2[j − 1])
(*) Note :
• "abc"[0...0] == ""
• "abc"[0...3] == "abc"
Approche PCAM et exemples de programmes 387
# Cas recursifs .
((1.. n1 )*(1.. n2 )). each do |i , j |
d [i , j ] = [ d [i -1 , j ] + 1,
d [i , j -1] + 1,
d [i -1 , j -1] + cout_subst ( ch1 [ i ] , ch2 [ j ] )
]. min
end
d [ n1 , n2 ]
end
Approche PCAM et exemples de programmes 388
a x e
_ _ _ _
| 0 1 2 3
a | 1 1 2 3
d | 2 2 2 2
s u r v e y
_ _ _ _ _ _ _
| 0 1 2 3 4 5 6
s | 1 0 1 2 3 4 5
u | 2 1 0 1 2 3 4
r | 3 2 1 1 2 3 4
g | 4 3 2 2 1 2 3
e | 5 4 3 3 2 2 3
r | 6 5 4 4 3 2 3
y | 7 6 5 5 4 3 2
Parallélisme de résultat : Chaque entrée de la matrice peut être vue comme une
tâche indépendante
Approche PCAM et exemples de programmes 390
Programme omis
Approche PCAM et exemples de programmes 393
Figure 8.7: Cylindre à l’état initial mais discrétisé — découpé en petits segments.
Tt [i − 1] + Tt [i + 1]
=
2
Approche PCAM et exemples de programmes 396
Quelques remarques
Effet de l’augmentation du nombre de points
• Plus le nombre de points utilisés (le nombre de segments utilisés pour la dis-
crétisation de l’espace) est grand — mais en autant qu’on reste dans les limites
de précision de calcul — alors plus la solution numérique finale est précise.
Toutefois, le temps pour arriver à un point fixe est alors plus long.
Ainsi, dans l’exemple précédent, supposons qu’on utilise 60 segments (au lieu de
6), toujours pour une précision de deux chiffres après le point. Alors :
T0 = 1.00 0.00 0.00 0.00 . . . 0.00 0.00 0.00 10.00
.
.
.
T33 = 1.00 0.86 0.73 0.61 . . . 6.08 7.28 8.60 10.00
Quant au point fixe, il ne serait atteint qu’après plusieurs centaines d’itérations.
Partitionnement
Pour un point donné (discrétisation spatiale du cylindre), il va falloir calculer sa
température au temps (discrétisation temporelle) t = 0, t = 1, t = 2, etc.
Notons par Tt [i] la valeur du point T [i] au temps t. Supposons que comme dans
notre exemple précédent, nous ayons aussi 6 points (i = 0, . . . , 5) et que nous voulons
calculer pour t = 0, 1, 2, . . . , 9.
Il nous faudra alors calculer les différentes valeurs illustrées à la figure 8.8, qui
représentent donc les différentes tâches de granularité les plus fines.
Communications
Il nous faut ensuite identifier les dépendances entre les différentes valeurs (tâches)
pour pouvoir identifier les communications potentielles.
L’équation de Jacobi est la suivante :
Tt [i − 1] + Tt [i + 1]
Tt+1 [i] =
2
Les dépendances sont donc celles illustrées dans la figure 8.9.
Approche PCAM et exemples de programmes 398
Agglomération
À un premier niveau, on peut agglomérer les tâches de façon verticale, donc en
combinant ensemble les tâches responsables de calculer, pour un point donné, les
différentes valeurs dans le temps. En d’autres mots, on effectue alors une aggloméra-
tion selon la dimension temporelle. On obtient alors les dépendances illustrées à la
figure 8.10.
Figure 8.10: Dépendances des tâches lorsqu’une tâche est pour un seul et unique
point (segment) — agglomération temporelle.
Figure 8.11: Dépendances des tâches lorsqu’une tâche est pour un groupe de points
(segments) — agglomération spatiale.
Approche PCAM et exemples de programmes 402
Mapping
Puisque nous allons programmer cette solution en MPI/C (solution de Mattson,
Sanders et Massingill [MSM05]), nous allons donc utiliser une association statique
entre tâches et processus, typique des programmes SPMD (Single Program, Multiple
Data) qu’on retrouve en MPI.
• Version séquentielle :
http://www.labunix.uqam.ca/~tremblay/INF7235/Materiel/heat-seq.c
Tt [i − 1] + Tt [i + 1]
Tt+1 [i] =
2
Or, lorsqu’on calcule de façon séquentielle, de gauche à droite, les différentes
valeurs, on peut alors accélérer la convergence en utilisant la nouvelle valeur du
voisin gauche plutôt que l’ancienne.
Dans ce cas, on utilise alors l’équation suivante dite de Gauss–Seidel :
Tt+1 [i − 1] + Tt [i + 1]
Tt+1 [i] =
2
Pour notre exemple précédent (six points), on aurait alors les itérations suiv-
antes :
Approche PCAM et exemples de programmes 403
R N R N R N
T0 = 1.00 0.00 0.00 0.00 0.00 10.00
405
Chapitre 9
9.1 Introduction
Ce document présente un aperçu des Threading Building Blocks (TBB) d’Intel. La
figure 9.1 présente une vue d’ensemble des différents éléments de TBB [Rob09].
Dans le présent document, nous allons nous concentrer plus spécifiquement sur les
algorithmes parallèles génériques.
• TBB met l’accent sur une approche de parallélisme de données, tout en perme-
ttant quand même les approches de parallélisme de contrôle et de parallélisme
de flux (pipelines).
406
TBB 407
• TTB s’inspire de l’approche proposée par Cilk [FLR98, MRR12] pour l’ordon-
nancement des tâches — appelé «task stealing» :
– Permet de réduire les surcoûts liés à la création et à l’ordonnancement
des tâches/threads ;
– Assure une utilisation efficace des caches (meilleure localité).
• TBB utilise des templates C++ pour exprimer et réaliser les principaux pa-
trons de programmation parallèle — parallélisme de boucles, de flux (pipeline),
récursif (diviser-pour-régner), etc.
1. Pour chacun des programmes C++ ci-bas, indiquez ce qui sera affiché si on
compile (avec g++) puis on exécute.
Dans tous les cas, on suppose qu’un #include <cstdio> est présent au début
du fichier.
inc ( 0 )
pgm1.cpp
void inc ( int x ) { x += 1; }
pgm2.cpp
void inc ( int & x ) { x += 1; }
pgm3.cpp
void inc ( int x ) { x += 1; }
pgm4.cpp
void inc ( int & x ) { x += 1; }
pgm5.cpp
void incinc ( int * x_ , int * y_ , int n ) {
int x = * x_ , y = * y_ ; // Copy - in (= > copies locales ).
for ( int i = 0; i < n ; i ++ ) {
x ++; y ++; // Traitement sur copies locales .
}
* x_ = x ; * y_ = y ; // Copy - out (= > met a jour arguments ).
}
x = y = 0;
incinc ( &x , &y , 10 ); printf ( " % d % d \ n " , x , y );
x = y = 0;
incinc ( x , y , 10 ); printf ( " % d % d \ n " , x , y );
}
TBB 412
Programme C++ 9.1 Une procédure générique pour echanger le contenu de deux
variables.
template < typename T >
void echanger ( T & x , T & y ) {
T tmp = x ;
x = y;
y = tmp ;
}
float a , b ;
...
echanger < float >( a , b ); // void echanger ( float & , float & );
...
...
template <>
struct Foo <0 >
{
enum { val = 1 };
};
------------------------------------------
Exercice 9.1: Une utilisation non-triviale, et quelque peu étonnante, des templates.
TBB 416
• -> type_du_resultat : peut être omis si le type du résultat est void ou si une
unique instruction «return expr;» est explicitement présente dans le corps
de la λ-expression.
x = 9;
r = [=]{ return x + 1; }();
// x == 9 && r == 10
x = 9;
r = [& x ]{ return x ++; }();
// x == 10 && r == 9
x = 9;
r = [&]{ return x ++; }();
// x == 10 && r == 9
Il faut noter que puisqu’une λ-expression génère un type anonyme, connu unique-
ment du compilateur, le type auto est la seule façon de déclarer et définir explicite-
ment une variable associée à une λ-expression.
x = 9;
r = [&]( int y ){ x += 2; return x + y ; }( 25 );
// x == 11 && r == 36
x = 9;
r = 0;
[x , & r ]( int y ){ r = x + y ; }( 25 );
// x == 9 && r == 34
TBB 418
/*
lambdas.cpp: In lambda function:
lambdas.cpp:11:23: erreur:
assignment of read -only variable ’x’
r = [=]( int y ){ x += 2; return x + y; }( 100 );
*/
Pour chacun des segments de code C++ ci-bas, indiquez ce qui sera affiché si on
compile (avec g++) puis on exécute.
int a [ n ];
init_zero (a , 0);
printf ( " % d \ n " , a [0] );
// Exemples d ’ utilisation .
int a [4] = {10 , 20 , 93 , 12};
sr = [0...50, 50...100]
R :: R ( const R & );
// Copy constructor
R ::~ R ();
// Destructor
R :: R ( R & r , split );
// Split range r into two subranges .
TBB 424
// a == {11 , 21 , 94 , 13}
// a == {11 , 21 , 94 , 13}
Programme TBB 9.6 Une version parallèle d’une procédure effectuant la somme
de deux tableaux.
// Version parallele avec lambda - expression et code explicite .
void additionner_par (
const float a [] ,
const float b [] ,
float c [] ,
const blocked_range < size_t > r )
{
parallel_for ( r ,
[=]( blocked_range < size_t > r ) {
for ( size_t i = r.begin(); i < r.end(); i++ ) {
c [ i ] = a [ i ] + b [ i ];
}
}
);
}
• Range& range :
Intervalle à traiter
• Value identity :
Élément neutre de l’opérateur de réduction ; doit aussi être l’élément neutre
(à gauche) de Func::operator().
Programme TBB 9.7 Fonction sommePar pour calculer la somme des éléments d’un
tableau.
# include " tbb / parallel_reduce . h "
using namespace tbb ;
Programme TBB 9.8 Fonction sommePar pour calculer la somme des éléments d’un
tableau.
// Version correcte avec parallel_reduce .
float sommePar ( float a [] , size_t n )
{
return parallel_reduce (
blocked_range < size_t >(0 , n ) ,
0. f ,
[=]( blocked_range < size_t > r , float acc ) {
for ( size_t i = r . begin (); i < r . end (); i ++ ) {
acc += a [ i ];
}
return acc ;
},
std :: plus < float >()
);
}
TBB 433
return 0;
}
elems == { 10, 1, 3, 3, 3, 2, 9, 1, 1, 1, 3, 10 }
histo == { 0, 4, 1, 4, 0, 0, 0, 0, 0, 1, 2 }
Donnees d ’ entree :
- elems : Tableau d ’ entiers non - negatifs
(0 ≤ elems [ i ] ≤ valMax )
Resultat :
- Pointeur vers le tableau ( dynamique ) de
l ’ histogramme resultant
( alloue dynamiquement par la fonction )
*/
// On initialise l ’ histogramme .
for ( int i = 0; i <= valMax ; i ++ ) {
histo [ i ] = 0;
}
return histo ;
}
TBB 437
return nb_occ ;
}
En utilisant les Threading Building Blocks d’Intel, écrivez une version parallèle de
la fonction histogramme. Utilisez une approche de parallélisme de résultat —
même si cela implique de parcourir plusieurs fois la matrice elems.
return
parallel_reduce ( blocked_range < size_t >(0 , nb ) ,
init () ,
foo ,
bar
);
}
Les arguments partitioner et group sont donc optionnels, d’où leur absence
dans les exemples précédents. Dans les explications qui suivent, nous allons
nous concentrer sur le rôle du partitioner.
Le rôle d’un partitioner avec un Range est de déterminer jusqu’à quel point
les intervalles doivent effectivement être décomposés et distribués entre les
divers threads.
Les deux partitioners de base sont les suivants :
1
Il faut aussi savoir qu’il existe aussi des variantes de parallel_for qui utilisent directement
des Index plutôt qu’un Range. Voir l’URL suivant : http://www.threadingbuildingblocks.
org/docs/help/reference/algorithms/parallel_for_func.htm.
TBB 441
private :
T my_begin ;
T my_end ;
size_t my_grainsize ;
};
TBB 442
// Split constructor
// = > definit un nouvel objet blocked_range
//
// r = range existant qu ’ on veut " splitter ".
//
blocked_range ( blocked_range & r , split )
{
T middle
= r . my_begin + ( r . my_end - r . my_begin ) / 2 u ;
Programme TBB 9.11 Des appels à une procédure additionner par l’intermédiaire
d’un parallel_for utilisant un simple_partitioner(). La procédure appelée
affiche une trace d’exécution indiquant les bornes de l’intervalle à traiter.
void additionner ( const float a [] , const float b [] ,
float c [] ,
blocked_range < size_t > r )
{
printf ( " additionner ( a , b , c , [% d , % d ) )\ n " ,
r . begin () , r . end () );
// int grainsize = 1;
additionner ( a, b, c, [500 , 501) )
additionner ( a, b, c, [750 , 751) )
additionner ( a, b, c, [875 , 876) )
additionner ( a, b, c, [812 , 813) )
.
.
.
additionner ( a , b , c , [59 , 60) )
additionner ( a , b , c , [60 , 61) )
additionner ( a , b , c , [626 , 627) )
...
additionner ( a , b , c , [484 , 485) )
additionner ( a , b , c , [371 , 372) )
...
additionner ( a , b , c , [498 , 499) )
additionner ( a , b , c , [499 , 500) )
additionner ( a , b , c , [467 , 468) )
C’est ce qui fait que, dans la version plus récente de TBB, on suggère d’utiliser
plutôt un auto_partitioner(), et donc de laisser au système d’exécution TBB
le choix de déterminer si l’intervalle doit ou non être décomposé, en fonction
de la charge de travail des threads. C’est donc pour cette raison que c’est le
auto_partitioner() qui est utilisé par défaut, lorsque cet argument est omis.
TBB 448
.
.
.
Programme TBB 9.12 Fonction pour calculer le nième nombre de Fibonacci à l’aide
de parallélisme récursif réalisé avec parallel_invoke.
# include " tbb / parallel_invoke . h "
using namespace tbb ;
On peut aussi utiliser des groupes de tâches, tel que présenté dans le programme
TBB 9.13. Les opérations associées à un tel objet sont les suivantes :2
template < typename Func >
void run ( const Func & f );
Programme TBB 9.13 Fonction pour calculer le nième nombre de Fibonacci à l’aide
de parallélisme récursif réalisé avec un task_group.
# include " tbb / parallel_invoke . h "
using namespace tbb ;
2
http://www.threadingbuildingblocks.org/docs/help/reference/task_groups/task_
group_cls.htm
TBB 451
int a [ N ] = ...;
...
p(x) = r2
where (r1 , r2 ) = f3 (f2 (f1 (f0 (x, 0))))
Donc :
p(x) = r2 = dx3 + cx2 + bx + a
Cette façon d’exprimer l’évaluation à l’aide d’une série de fonctions conduit alors
à du parallélisme de spécialistes associé à du parallélisme de flux pour l’évaluation
du polynome en un grand nombre de valeurs : chaque processus (filtre) du pipeline
traite les différentes valeurs, mais pour un coefficient spécifique, et c’est la com-
position des fonctions du pipeline qui permet d’obtenir l’évaluation pour un point
donné.
Cette méthode peut évidemment être généralisée à un nombre arbitraire de co-
efficients.
• Le programme TBB 9.15 définit une classe pour représenter des Paires de
valeurs.
• Le programme TBB 9.17 crée ensuite les différents filtres, puis les compose en
un pipeline.
Programme TBB 9.15 Classe Paire pour représenter des tuples formés de deux
composants.
class Paire {
public :
double x ;
double y ;
public :
Paire ( double x , double y ) :
x ( x ) , y ( y ) {}
};
TBB 455
Programme TBB 9.16 Trois sortes de filter pour manipuler des valeurs et des
coefficients pour évaluer un polynome.
class GenererVals : public filter {
int prochain = 0;
int nbVals ;
double * vals ;
public :
GenererVals ( double * vals , int nbVals ) :
filter ( serial_in_order ) , nbVals ( nbVals ) , vals ( vals ) {}
Programme TBB 9.17 Programme TBB pour évaluer un polynome en une série de
points, à l’aide d’une approche fondée sur le parallélisme de flux, et utilisant les
filtres du programme TBB 9.16.
//
// Exemple d ’ utilisation .
//
//
// On suppose qu ’ on a les trois tableaux suivants :
// coeffs : les nbCoeffs coefficients definissant le polynome
// vals : les nbVals valeurs a utiliser pour evaluer le polynome
// resultats : les nbVals resultats
//
pipeline p ;
p . run ( nbCoeffs );
void foo ()
{
tick_count t0 = tick_count :: now ();
... action being timed ...
tick_count t1 = tick_count :: now ();
9.9.2 Dimensionabilité
Règle générale, dans un programme TBB, on laisse le soin au système d’exécution de
choisir le nombre de threads ; on se concentre plutôt sur l’identification des
tâches.
Par contre, il est quand même possible — et parfois utile — de contrôler le
nombre de threads utilisés pour exécuter un programme. Pour ce faire on utilise un
objet task_scheduler_init spécifié comme suit :
3
http://www.threadingbuildingblocks.org/docs/help/reference/timing/tick_count_
cls.htm
TBB 458
task_scheduler_init (
int max_threads = automatic ,
stack_size_type thread_stack_size =0
)
Comme l’indique la documentation TBB : «An optional parameter to the con-
structor [. . . ] allows you to specify the number of threads to be used for task exe-
cution. This parameter is useful for scaling studies during development,
but should not be set for production use.»
Donc, on utilise un tel objet uniquement pour déterminer dans quelle mesure un
programme TBB est dimensionable (scalable), i.e., quel est l’effet de varier le nombre
de threads sur les performances du programme.
Le programme TBB 9.19 présente un squelette de programme permettant de faire
de telles mesures de dimensionabilité.
[F]or scheduling loop iterations, Threading Building Blocks does not re-
quire the programmer to worry about scheduling policies. Threading
Building Blocks does away with this in favor of a single, automatic,
divide-and-conquer approach to scheduling. Implemented with
work stealing (a technique for moving tasks from loaded processors
to idle ones), it compares favorably to [OpenMP’s] dynamic or guided
scheduling, but without the problems of a centralized dealer.
Source : «Intel Threading Building Blocks: Outfitting C++ for Multi-
Core Processor Parallelism», Reinders, 2007.
• Chaque thread utilise un deque (double ended queue) ayant les opérations
suivantes :
4
Le modèle présenté, utilisant un deque, est une des façons possibles de mettre en oeuvre cette
approche. D’autres structures de données plus complexes pour la mise en oeuvre du sac de tâches
sont possibles, par exemple, une pile de files : voir [Rei07].
TBB 460
– Lorsque T crée une nouvelle tâche (SPAWN), alors l’ajout se fait avec
D.push.
– Lorsque T termine le traitement d’une tâche, alors son comportement est
le suivant pour obtenir une nouvelle tâche à exécuter :
∗ Si D.empty? est false, alors il va traiter une tâche locale. Donc la
prochaine tâche à traiter est , obtenue avec D.pop.
∗ Si D.empty? est true, alors T va voler une tâche à un autre thread
T 0 choisi aléatoirement (s’il y en a un qui a des tâches dans son
deque). Donc la prochaine tâche à traiter estobtenue avec D0 .remove,
où D0 est le deque du thread T 0 qui est «victime du vol»!.
Fait : Lorsqu’il y a suffisamment de tâches locales à traiter, le deque est
donc manipulé comme une pile.
– Le coût pour traiter une tâche locale (non volée) est faible — à toute fin
pratique, ce coût est équivalent à celui d’un simple appel de procédure/-
fonction.
Le coût de création et traitement d’une tâche n’est élevé que lorsque cette
tâche «migre» du deque d’un thread (victime) au deque d’un autre thread
(voleur).
– L’arbre des tâches est exploré localement en profondeur (depth-first), ce
qui minimise l’espace requis pour les appels (et blocs d’activation) tout
en utilisant efficacement les caches — on dit que le code s’exécute alors
pendant que le cache est chaud.
L’exploration en largeur (breadth-first) ne se fait que si un ou des threads
sont effectivement libres (sans tâche à exécuter) et n’ont aucun travail
à effectuer. Ceci favorise alors l’exploration en parallèle, puisque ces
TBB 461
tâches sont plus hautes dans l’arbre d’exécution, mais sans en payer le
côut lorsque le parallélisme ne peut pas être exploité faute de ressources
(threads et processeurs).
Voir le document suivant :
http://www.labunix.uqam.ca/~tremblay/INF5171/Materiel/vol-de-taches.
pdf
Programme TBB 9.20 Une mise en oeuvre parallèle du tri rapide (quicksort) avec
une approche style parallélisme récursif, et avec un seuil de récursion.
void partitionner ( int * a , size_t taille , size_t & posPivot )
{
// Pour simplifier : On selectionne le premier element comme pivot .
auto pivot = a [0];
posPivot = 0;
partitionner ( a , n , posPivot );
tbb :: parallel_invoke (
[=]{ parallel_qs_rec (a , posPivot , seuil ); } ,
[=]{ parallel_qs_rec ( a + posPivot +1 , n - posPivot -1 , seuil ); }
);
}
};
TBB 464
Programme TBB 9.21 Une mise en oeuvre du tri rapide (quicksort) avec un objet
de type Range, qui effectue le partitionnement et qui fait tout le travail, utilisé dans
un parallel_for.
struct qs_range {
int * a ;
size_t taille , seuil ;
Figure 9.5: Accélérations obtenues pour différentes tailles de tableau (échelle loga-
rithmique) et pour les deux variantes des deux procédures de tri rapide avec deux
façons de choisir le pivot.
TBB 466
Figure 9.6: Temps d’exécution obtenus pour différentes tailles de tableau (échelle
logarithmique) et pour les deux variantes des deux procédures de tri rapide avec
deux façons de choisir le pivot.
TBB 467
# pivot = mediane
# n seq p_for p_invoke
4000 0.0011 0.0051 0.0030
8000 0.0025 0.0082 0.0016
16000 0.0052 0.0103 0.0026
32000 0.0118 0.0100 0.0031
64000 0.0250 0.0141 0.0063
128000 0.0544 0.0187 0.0095
256000 0.1151 0.0296 0.0230
512000 0.2558 0.0509 0.0462
1024000 0.5174 0.0859 0.0928
2048000 1.0928 0.1589 0.1804
# pivot = pos0
# n seq p_for p_invoke
4000 0.0012 0.0069 0.0008
8000 0.0026 0.0062 0.0014
16000 0.0058 0.0094 0.0020
32000 0.0130 0.0096 0.0036
64000 0.0273 0.0159 0.0072
128000 0.0584 0.0200 0.0123
256000 0.1259 0.0342 0.0290
512000 0.2692 0.0693 0.0508
1024000 0.5771 0.1145 0.1256
2048000 1.2233 0.2006 0.2444
Quelques constatations :
• Si on examine les temps d’exécution — voir détails dans le tableau plus haut —
on constate que c’est la version avec parallel_for et le choix de pivot qui «ap-
proxime» (naivement) la médiane qui génère les meilleurs temps d’exécution.
Et la version parallel_invoke avec choix du pivot approximant la médiane
a aussi de meilleurs temps d’éxécution, même si son accélération relative à la
version séquentielle (avec même choix de pivot) n’est pas aussi bonne.
TBB 468
10.1 Introduction
Ce chapitre présente un bref aperçu d’OpenMP = «Open Multi-Processing».
469
OpenMP 470
• Une région parallèle est délimitée par une instruction, simple ou composite,
i.e., un bloc d’instructions — instructions comprises entre «{» et «}».
...
}
Si une copie locale d’une variable globale doit plutôt être utilisée, on doit le
spécifier explicitement avec une clause private :
int x = 0;
...
}
OpenMP 474
• Avec un pragma :
# pragma omp parallel num_threads (10)
Dans tous les cas, il s’agit d’une «suggestion», et non pas une «obligation»
pour le système d’exécution d’allouer exactement le nombre de threads in-
diqués — en d’autres mots, cela permet de spécifier le nombre maximum de
threads qu’on désire utiliser.
OpenMP 475
– Répartition des itérations d’un for (loop splitting) : les diverses itérations
de la boucle for qui suit sont réparties entre les différents threads :
# pragma omp for
for ( ... ) {
...
}
– Distribution par sections : chacune des section qui suit est exécutée par
un unique thread.
# pragma omp sections
{
omp_set_num_threads ( nb_threads );
omp_set_num_threads ( nb_threads );
– Une boucle utilisée pour effectuer une réduction peut être codée en spé-
cifiant une opération et une variable de réduction — voir plus loin pour
des exemples :
# pragma omp for reduction( <op>: var )
Les opérations possibles <op> sont les suivantes : +, *, -, &, |, &&, ||,^,
min, max.
Remarque : Depuis la version 4.0 (juillet 2013), il est aussi possible
d’utiliser une opération de réduction définie par le programmeur :
[In version 4.0,] The reduction clause [. . . ] was extended and
the declare reduction construct [. . . ] was added to support user
defined reductions.
OpenMP 479
• Exécution unique où c’est le premier thread arrivé, et seulement lui, qui exécute
l’instruction qui suit :
# pragma omp single
Les valeurs possibles pour <op> sont les opérateurs binaires de base : +, *,
-, &, |, &&, ||, ^, <<, >>
Note : La différence entre une section critique (avec critical) et une instruc-
tion atomique (avec atomic) c’est que dans le premier cas, on peut indiquer
un bloc arbitraire d’instructions, alors que dans le deuxième cas on ne peut
indiquer qu’une seule instruction de manipulation d’une variable simple. De
telles opérations atomiques sont généralement mises en oeuvre sans utilisation
de verrous, donc de façon beaucoup plus efficace. On verra ultérieurement des
exemples en Java.
OpenMP 480
schedule( runtime )
schedule( auto )
• Statique : répartition statique entre les threads. Si la valeur chunk est absente,
alors les différentes itérations sont réparties de façon relativement uniforme
entre les différents threads — itérations adjacentes. Si la valeur chunk est
présente, alors les différentes itérations sont réparties par groupe de chunk en-
tre les threads, conduisant ainsi à une répartition cyclique — appelé interleaved
en OpenMP.
• Dynamique : répartition dynamique entre les threads. Chaque thread obtient
chunk itérations à traiter. Si la valeur chunk est absente, alors si elle considérée
égale à 1.
• guided (guidée) : répartition dynamique entre les threads, mais avec un com-
portement qui varie en cours d’exécution quant au nombre d’itérations allouées
à chaque fois. La première fois, chaque thread obtient un certain nombre
d’itérations à traiter. Puis, à chaque fois subséquente, le nombre qui lui est
attribué diminue de façon exponentielle — i.e., que le nombre obtenu est un
certain pourcentage (qui dépend de l’implémentation) du nombre obtenu la fois
précédente. Toutefois, la diminution du nombre d’itérations cesse lorsqu’on
atteint la valeur de chunk, qui est de 1 si rien n’est indiqué.
Le terme «guided » vient de «guided self-scheduling».
Similar to dynamic scheduling, but the chunk size starts off large and
decreases to better handle load imbalance between iterations. The optional
chunk parameter specifies the minimum size chunk to use.
https: // software. intel. com/ en-us/ articles/ openmp-loop-scheduling
OpenMP 482
10.6 Exemples
Les exemples qui suivent sont tirés et adaptés (simplifiés!) de deux articles provenant
du site Web de Sun/Oracle :
/* Print thread ID . */
printf ( " Hello World from thread = % d \ n " , tid );
}
}
2
http://developers.sun.com/solaris/articles/omp-intro.html
3
http://developers.sun.com/solaris/articles/studio_openmp.html
OpenMP 484
omp_set_dynamic (0);
omp_set_num_threads (20);
int sum = 0;
int sum = 0;
omp_set_dynamic (0);
omp_set_num_threads ( nb_threads );
• Le code du thread peut être une λ-expression (PRuby/Ruby, Java), une fonction
explicite (C) ou du code arbitraire (OpenMP)
Note : Certains de ces exemples seront présentés en MPD, un langage qui utilise
une instruction de type cobegin/coend pour lancer des threads. Bien que nous ne
verrons pas ce langage dans le cours, les exemples devraient quand même pouvoir
être compris — et être facilement traduits en Ruby/PRuby.
OpenMP 490
Exemple
Soit le code séquentiel suivant :
def foo ( k )
f2 ( f1 ( k )) + f1 ( k )
end
r = Array . new ( N )
r . each_index do | k |
r [ k ] = foo ( k )
end
On veut paralléliser ce code. Il s’agit d’un problème embarrassingly parallel, et
on veut définir une solution à granularité (très) fine.
OpenMP 491
MPD
(Avec thread «explicite», join implicite.)
int r[N]
co [k = 0 to N-1] # Co-begin/co-end.
r[k] = foo(k)
oc
OpenMP/C
(Avec thread implicite, join implicite.)
omp_set_num_threads ( N );
PRuby (bis)
(Avec thread explicite (bloc), join explicite.)
r = Array . new ( N )
r . each_index do | k |
r [ k ] = futures [ k ]. value
end
OpenMP/C
(Avec thread implicite, join implicite.)
omp_set_num_threads ( N );
PRuby (ter)
(Avec thread implicite, join implicite.)
PRuby . nb_threads = N
r = Array . new ( N )
r . peach_index ( static : 1 ) do | k |
r [ k ] = f2 ( f1 ( k )) + f1 ( k )
end
OpenMP/C
(Avec thread implicite, join implicite.)
omp_set_num_threads ( N );
C/Pthreads
(Avec thread explicite, join explicite.)
void * foo ( void * arg )
{
int k = ( int ) arg ;
int resultat = f2 ( f1 ( k )) + f1 ( k );
pthread_attr_t attr ;
pthread_attr_init (& attr );
pthread_attr_setscope (& attr , PTHREAD_SCOPE_SYSTEM );
pthread_t * trIds
= ( pthread_t *) malloc ( N * sizeof ( pthread_t ));
for ( int k = 0; k < N ; k ++ ) {
pthread_create ( & trIds [ k ] , & attr ,
foo , ( void *) k );
}
10.B Exercices
10.B.1 Traitement d’une liste chainée
Soit un programme C contenant le code suivant :
typedef struct Noeud {
struct Noeud * suivant ;
long valeur ;
} Noeud ;
...
On veut paralléliser la boucle for. Quels résultats produiront chacune des séries
d’annotations ci-bas.
Chapitre 11
Figure 11.1: Les premières architectures parallèles étaient des machines SIMD (Sin-
gle Instruction, Multiple Data), donc avec une unique unité de contrôle et plusieurs
unités de calcul (PE = processing element).
Programmation parallèle OpenCL 500
Figure 11.3: Ensuite sont apparus les premiers multi-ordinateurs = groupe de pro-
cesseurs connectés par un réseau. L’utilisation d’un réseau permet plusieurs trans-
actions à la fois, ce qui permet d’avoir un plus grand nombre de processeurs.
Programmation parallèle OpenCL 501
Figure 11.4: Puis sont apparues les architectures parallèles hybrides — les grappes
de multi-processeurs.
Programmation parallèle OpenCL 502
11.1 Introduction
11.1.1 Que signifie l’acronyme «GPGPU»?
General-purpose computing on graphics processing units (GPGPU, rarely
GPGP or GP2 U) is the use of a graphics processing unit (GPU), which
typically handles computation only for computer graphics, to perform
computation in applications traditionally handled by the central process-
ing unit (CPU).
Donc :
• GPU = Matériel
Source : http://www.nvidia.com/object/GPU_Computing.html
Multicore CPUs and manycore GPUs have emerged and gradually dom-
inated state-of-the-art high-performance computing. Although contem-
porary CPUs and GPUs are manufactured using the same semiconduc-
tor technology, the computational performance of GPUs increases more
rapidly than that of CPUs. Divergent design choices drive them into
devices of different capabilities given the same order of transistor count.
CPUs are optimized for high-performance, task-parallel work-
loads since more transistors are dedicated to control logics such as branch
prediction and out-of-order execution in each processing element. GPUs
are optimized for high-performance data-parallel workloads since
more transistors are dedicated to arithmetic logics such as floating-point
calculation and transcendental function in each processing element.
«A Closer Look at GPGPU » Hu & Che, ACM Computing Surveys, 2016.
Programmation parallèle OpenCL 508
Source : https://www.khronos.org/assets/uploads/developers/library/overview/opencl_
overview.pdf
Les compute devices sont utilisés comme accélérateurs!
Programmation parallèle OpenCL 509
Source : https://www.khronos.org/assets/uploads/developers/library/overview/opencl_
overview.pdf
Programmation parallèle OpenCL 510
C’est le programmeur qui est responsable des transferts de données entre le CPU
et le GPU!
Les différents niveaux de mémoire :
• Mémoire du host
1. Global Memory
Memory that can be read from all work items. It is physically the device’s
main memory.
2. Constant Memory
Also memory that can be read from all work items. It is physically the
device’s main memory, but can be used more efficiently than global mem-
ory if the compute units contain hardware to support constant memory
cache. The cost memory is set and written by the host.
3. Local Memory
Memory that can be read from work items within a work group. It is
physically the shared memory on each compute units.
4. Private Memory.
Memory that can only be used within each work item. It is physically the
registers used by each processing element.
Source : http://www.fixstars.com/en/opencl/book/OpenCLProgrammingBook/applicable-platforms/
Programmation parallèle OpenCL 511
Les GPUs modernes (style Nvidia) utilisent une approche d’exécution SIMT
pour les processing elements de bas niveau :
Source : https://www.irisa.fr/alf/downloads/collange/talks/sisdmt_scollange.pdf
Advantages/Disadvantages:
- Control-flow done using «masking», i.e., some threads may not do any work
Étant donné l’architecture décrite ci-haut, quel vous semble le modèle de program-
mation (le «patron d’algorithme parallèle») le plus naturel pour un GPU?
Exercice 11.1: Patron de programmation pour GPU.
Programmation parallèle OpenCL 512
Source : http://www.ks.uiuc.edu/Research/gpu/files/upcrc_opencl_lec1.pdf
Programmation parallèle OpenCL 513
L’exécution d’un kernel se fait pour chaque work item, lesquels sont regroupés
en work groups.
Source : https://software.intel.com/sites/landingpage/opencl/optimization-guide/Basic_
Concepts.htm
Source : https://software.intel.com/sites/landingpage/opencl/optimization-guide/Basic_
Concepts.htm
Programmation parallèle OpenCL 514
Source : http://www.ks.uiuc.edu/Research/gpu/files/upcrc_opencl_lec1.pdf
Programmation parallèle OpenCL 515
• Devices à utiliser.
• Espace mémoire.
• Queue de commandes.
Source : http://www.ks.uiuc.edu/Research/gpu/files/upcrc_opencl_lec1.pdf
Programmation parallèle OpenCL 516
Source : http://www.fixstars.com/en/opencl/book/OpenCLProgrammingBook/online-offline-compilation
• Pas de récursion.
• Etc.
Programmation parallèle OpenCL 517
// //// / / / // / / / / // / / / / // / / / / // /
// FICHIER somme_tableaux . cl
// //// / / / // / / / / // / / / / // / / / / // /
c [ i ] = a [ i ] + b [ i ];
}
L’ensemble des numéros d’identification des différents work items est l’index
space.
Exemples de résultats produits par index_space (version Ruby) :
index_space ( 1 , [3] )
== [[0] , [1] , [2]]
index_space ( 2 , [2 , 3] )
== [[0 , 0] , [0 , 1] , [0 , 2] ,
[1 , 0] , [1 , 1] , [1 , 2]]
index_space ( 3 , [3 , 2 , 2] )
== [[0 , 0 , 0] , [0 , 0 , 1] , [0 , 1 , 0] , [0 , 1 , 1] ,
[1 , 0 , 0] , [1 , 0 , 1] , [1 , 1 , 0] , [1 , 1 , 1] ,
[2 , 0 , 0] , [2 , 0 , 1] , [2 , 1 , 0] , [2 , 1 , 1]]
// //// / / / // / / / / // / / / / // / / / / // /
// FICHIER somme_tableaux . c
// //// / / / // / / / / // / / / / // / / / / // /
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
*/
//
Programmation parallèle OpenCL 522
# ifdef __APPLE__
# include < OpenCL / cl .h >
# else
# include < CL / cl .h >
# endif
//
Programmation parallèle OpenCL 523
return programme ;
}
//
Programmation parallèle OpenCL 524
//
Programmation parallèle OpenCL 525
//
Programmation parallèle OpenCL 526
//
Programmation parallèle OpenCL 527
//
Programmation parallèle OpenCL 528
cl_mem buffer_b =
clCreateBuffer ( contexte ,
CL_MEM_READ_ONLY | CL_MEM_COPY_HOST_PTR ,
sizeof ( float ) * N , b , NULL );
cl_mem buffer_c =
clCreateBuffer ( contexte ,
CL_MEM_WRITE_ONLY , // Pour lire le resultat .
sizeof ( float ) * N , NULL , NULL );
//
Programmation parallèle OpenCL 529
//
Programmation parallèle OpenCL 530
return 0;
}
Programmation parallèle OpenCL 531
// //// / / // / / / / / / / / / / / / / / / / / / / / /
// FICHIER produits_matrices . cl
// //// / / // / / / / / / / / / / / / / / / / / / / / /
// //// / / // / / / / / / / / / / / / / / / / / / / / /
// FICHIER produits_matrices . c
// //// / / // / / / / / / / / / / / / / / / / / / / / /
# ifdef __APPLE__
# include < OpenCL / cl .h >
# else
# include < CL / cl .h >
# endif
//
Programmation parallèle OpenCL 534
return programme ;
}
//
Programmation parallèle OpenCL 535
//
Programmation parallèle OpenCL 536
cl_device_id device ;
clGetDeviceIDs ( plateforme , CL_DEVICE_TYPE_GPU , 1 ,
& device , NULL );
//
Programmation parallèle OpenCL 537
cl_kernel kernel =
clCreateKernel ( programme , " produit_matrices " , NULL );
//
Programmation parallèle OpenCL 538
//
Programmation parallèle OpenCL 539
//
Programmation parallèle OpenCL 540
size_t nb_taches [] = {N , N };
clEnqueueNDRangeKernel ( queue , kernel , 2 , NULL , nb_taches ,
NULL , 0 , NULL , NULL );
//
Programmation parallèle OpenCL 541
//
Programmation parallèle OpenCL 542
//
Programmation parallèle OpenCL 543
return 0;
}
Programmation parallèle OpenCL 544
Tableau 11.1: Temps d’exécution du produit de matrices sur Mac Book pour diverses
tailles de matrices (valeurs de N = nombre de lignes/colonnes). Le temps d’exécution
est celui obtenu avec time au niveau du shell pour lancer l’exécution du programme.
Figure 11.7: Graphe d’accélération sur MacBook pour la version parallèle OpenCL
par rapport à la version séquentielle pour N assez grand. Pour les N plus petits, le
temps séquentiel obtenu avec time est nul, donc ne peut être utilisé pour calculer
une accélération. Pour N = 2048, la version séquentielle ne peut pas s’exécuter par
manque de mémoire.
Programmation parallèle OpenCL 545
* result = r ;
}
Programme parallèle en OpenMP/C
void sommation_tableau ( const float a [] ,
float * result ,
int N )
{
float r = 0.0;
* result = r ;
}
Programmation parallèle OpenCL 546
Figure 11.8: Opérations effectuées par un algorithme SIMD pour la sommation des
éléments d’un tableau, en utilisant un tampon auxiliaire.
Programme séquentiel en C
void sommation_tableau ( const float a [] ,
float * result ,
int N )
{
// On alloue le tampon et on copie le tableau .
float * tampon =
( float *) malloc ( N * sizeof ( float ) );
for ( int i = 0; i < N ; i ++ )
tampon [ i ] = a [ i ];
free ( tampon );
}
Programmation parallèle OpenCL 548
free ( tampon );
}
Programmation parallèle OpenCL 549
// //// / / // / / / / / / / / / / / / / / / / / / / / /
// FICHIER sommation_tableau . cl
// //// / / // / / / / / / / / / / / / / / / / / / / / /
tampon [ i ] = a [ i ];
barrier ( CLK_LOCAL_MEM_FENCE );
barrier ( CLK_LOCAL_MEM_FENCE );
}
if ( i == 0 ) {
* resultat = tampon [0];
}
}
Programmation parallèle OpenCL 550
$ sommation_tableau 128
OK pour 128 elements
$ sommation_tableau 256
OK pour 256 elements
$ sommation_tableau 512
OK pour 512 elements
$ sommation_tableau 1024
*** Erreur: resultat incorrect: 24275.000000 -- 49317.000000
$ sommation_tableau 2048
*** Erreur: resultat incorrect: 24275.000000 -- 98634.000000
$ sommation_tableau 4096
*** Erreur: resultat incorrect: 24275.000000 -- 201257.000000
$ sommation_tableau 8192
*** Erreur: resultat incorrect: 24275.000000 -- 405363.000000
Programmation parallèle OpenCL 552
Found 2 device(s)
Device 0
Name: Intel(R) Core(TM) i5-4260U CPU @ 1.40GHz
Vendor: Intel
Compute Units: 4
Global Memory: 4294967296
Local Memory: 32768
Workgroup size: 1024
Device 1
Name: HD Graphics 5000
Vendor: Intel
Compute Units: 280
Global Memory: 1610612736
Local Memory: 65536
Workgroup size: 512
Faits :
• Si le nombre de work items est plus grand que le nombre de coeurs et que le
programmeur ne spécifie pas la décomposition en groupes, alors c’est OpenCL
qui gére la décomposition en groupes, dans un ordre arbitraire.
Par exemple :
2048 items avec un workgroup size de 512
⇒ 4 «passes»
⇒ le kernel est lancé sur les 512 coeurs 4 fois
⇒ pas le bon résultat pour cet exemple /
Source : http://www.nvidia.com/content/GTC/documents/1409_GTC09.pdf
Programmation parallèle OpenCL 554
Une solution correcte pour sommation_tableau nécessite donc d’utiliser une ap-
proche «semblable» à ce que fait la version Ruby suivante :
def sommation_tableau ( a , N )
resultats = Array . new ( nb_groupes )
total = 0
(0... nb_groupes ). each do | k |
total += resultats [ k ]
end
end
Programmation parallèle OpenCL 555
Pour otenir une solution correcte, il faut alors gérer et manipuler explicitement
les groupes et numéros de groupe et avoir en argument un pointeur vers un tableau
des resultats. Voici le kernel — notez get_local_id(0) et get_group_id(0) :
// // // / / / / / / / / / / / / / / / / / / / / / / / / / / / /
// FICHIER sommation_tableau - wg . cl
// // // / / / / / / / / / / / / / / / / / / / / / / / / / / / /
barrier ( CLK_LOCAL_MEM_FENCE );
}
if ( i == 0) {
resultats [ get_group_id (0)] = tampon [0];
}
}
Programmation parallèle OpenCL 556
Programmation parallèle OpenCL 557
L’extrait du programme qui appelle le kernel est présenté ci-bas. Chaque groupe
calcule un résultat intermédiaire, et ces résultats sont ensuite être combinés.
Programmation parallèle OpenCL 558
Voici donc la version révisée du segment de code du programme principal qui appelle
le kernel :
float a [ N ];
initialiser ( a , N );
cl_mem buffer_a =
clCreateBuffer ( contexte , CL_MEM_READ_ONLY | CL_MEM_COPY_HOST_PTR ,
sizeof ( float ) * N , a , NULL );
cl_mem buffer_resultats =
clCreateBuffer ( contexte , CL_MEM_WRITE_ONLY ,
sizeof ( float ) * nb_groupes , NULL , NULL );
size_t nb_taches [] = { N };
size_t tailles_groupes [] = { taille_groupe };
clEnqueueNDRangeKernel ( queue , kernel , 1 , NULL , nb_taches ,
tailles_groupes , 0 , NULL , NULL );
11.6 Conclusion
• L’utilisation de GPU est intéressante pour de nombreux problèmes avec du
parallélisme de données — et pas uniquement pour le traitement graphique!
Programmation parallèle et
concurrente avec Java
12.1 Lambda-expressions
Nous allons illustrer les lambda-expressions à l’aide de variables et d’interfaces
(explicites), pour mieux comprendre leur typage et montrer aussi que les lambda-
expressions sont des objets.
Une lambda-expression est un objet qui représente une méthode anonyme et
l’affectation à une variable est une façon de lui donner un nom. . . et de rendre
explicite la méthode associée.
560
Programmation Java 561
L’interface Future<V>
A Future represents the result of an asynchronous computation. Methods are pro-
vided to check if the computation is complete, to wait for its completion, and to
retrieve the result of the computation. The result can only be retrieved using method
get when the computation has completed, blocking if necessary until it is ready.
Cancellation is performed by the cancel method. Additional methods are provided
to determine if the task completed normally or was cancelled. Once a computation
has completed, the computation cannot be cancelled.
public interface Future <V > {
boolean cancel ( boolean mayInterruptIfRunning )
V get ()
boolean isCancelled ()
boolean isDone ()
}
Note : Les interfaces Callable<V> et Future<V> sont définies dans java.util.concurrent,
donc il faut faire un import!
Programmation Java 562
Un exemple : Function<T,R>
@FunctionalInterface
public interface Function <T ,R > {
// Applies this function to the given argument .
R apply ( T t )
}
Programmation Java 563
Runnable r0
= () -> { System . out . println ( " Dans r0 " ); };
r0 . run ();
int x = 0;
Runnable r1
= () -> System . out . println ( " x = " + x );
r1 . run ();
r2 . run ();
f . foo ();
b . bar ();
Par contre :
int x = 0;
Runnable r2
= () -> System . out . println ( " x = " + x );
r2 . run ();
x = 3;
Runnable r3
= () -> System . out . println ( " x = " + x );
r3 . run ();
-----------------------
Lambdas . java :57: error : local variables referenced from a
lambda expression must be final or effectively final
Runnable r2 = () -> System . out . println ( " x = " + x );
^
Lambdas . java :61: error : local variables referenced from a
lambda expression must be final or effectively final
Runnable r3 = () -> System . out . println ( " x = " + x );
Programmation Java 564
int xx = 0 , yy = 22;
Callable < Integer > c2 = () -> { return xx + yy ; };
try { ... c2 . call () ... } ...
int z = 22;
Function < Integer , Integer > f2
= ( w ) -> { return w + z ; };
int y = 0;
Addable a3 = w -> w + y ;
... a3 . add (20) ...
Par contre :
int y = 0;
=>
Lambdas . java :111: error : variable y is already defined in
method main ( String [])
Addable a4 = ( int y ) -> { return y + y ; };
Une interface avec plusieurs méthodes mais une seule non définie dans
Object
interface MonFooable {
void foo ();
int hashCode ();
String toString ();
}
MonFooable mf0 = () -> System . out . println ( " Dans mf0 " );
mf0 . foo ();
Programmation Java 566
interface MesRunnables {
void run0 ();
void run1 ();
}
MesRunnables rs0 = () -> System . out . println ( " Dans rs0 " );
----
Lambdas . java :140: error : incompatible types :
MesRunnables is not a functional interface
MesRunnables rs0 = () -> System . out . println ( " Dans rs0 " );
^
multiple non - overriding abstract methods found
in interface MesRunnables
Programmation Java 567
La classe Thread est, en partie, définie comme dans le Programme Java 12.1.
Programmation Java 568
Cycle de vie d’un thread «primitif» Les étapes de base d’utilisation d’un
thread sont les suivantes :
1. On crée un objet Thread.
2. On lance l’exécution de l’objet Thread avec la méthode start().
L’appel de cette méthode effectue alors, entre autre, un appel à la méthode
run() de l’objet.
3. On attend la fin de l’exécution de l’objet Thread en appelant la méthode
join().
Création et activation de threads Les deux principales façons pour créer une
instance de la classe Thread sont les suivantes :
• On définit une classe qui hérite de la classe Thread et qui définit une méthode
run :
class C extends Thread {
...
void run () { ... }
...
}
C c = new C ( ... );
c . start ();
Version PRuby
co [ k = 0 to nb_threads -1]
pfoo ( k , bar ( k ) );
oc
Versions PRuby
# Avec pcall .
PRuby . pcall ( 0... nb_threads ,
lambda { | k | pfoo ( k , bar ( k ) ) }
)
# Avec future .
fs = (0... nb_threads ). map do | k |
PRuby . future { pfoo ( k , bar ( k ) ) }
end
fs . map (&: value )
Programmation Java 573
Version PRuby
ExecutorService pool
= Executors.newCachedThreadPool();
Future<Integer>[] fs
= new Future [ nbThreads ]; // unchecked cast
int r []
= new int [ nbThreads ];
pool.shutdown();
Programmation Java 577
Programme Java 12.2 Une fonction parallèle evaluerPi (et sa fonction auxili-
aire nbDansCercleSeq) pour approximer la valeur de π à l’aide de la méthode de
Monte Carlo. Il s’agit de la version Java d’une fonction Ruby vue précédemment :
Programme Ruby 5.10 (style impératif).
public static int nbDansCercleSeq ( int nbLancers ) {
Random rnd = new Random ();
int nb = 0;
for ( int k = 0; k < nbLancers ; k ++ ) {
double x = rnd . nextDouble ();
double y = rnd . nextDouble ();
if ( x * x + y * y <= 1.0 ) {
nb += 1;
}
}
return nb ;
}
//
Figure 12.1: Graphe donnant le temps d’exécution du programme Pi.java pour dif-
férents nombres de threads. Les temps sont indiqués pour trois (3) séries différentes
d’exécution.
La Figure 12.1 présente les temps d’exécution pour trois séries distinctes d’exécu-
tion du programme Java 12.2, et ce en faisant varier le nombre de threads pour
effectuer un total de 10 000 000 lancers — donc 10 000 000 de lancers partagés
entre les divers threads. Pour plus de détails sur ces expérimentations et résultats,
voir la section 6.A.
Programmation Java 580
Autres graphes : Temps et accélération sur japet pour 100 000 000 de
lancers
Programmation Java 581
Autres graphes : Temps et accélération sur linux pour 100 000 000 de
lancers
Programmation Java 582
Autres graphes : Temps et accélération sur linux pour 1 000 000 000 de
lancers
Programmation Java 584
Note : Étant donné que nous utiliserons Java «de base» — donc les packages «stan-
dards» seulement, otamment java.util.concurrent — nous utiliserons toujours
du parallélisme fork–join.
Programme Java 12.3 Parallélisme récursif avec création récursive d’un seul
thread, l’autre sous-problème étant traité par le thread parent.
//
// Parallelisme recursif avec seuil utilisant du parallelisme
// fork - join avec un seul Thread .
//
public static void somme_par_rec1_ij ( int a [] , int b [] ,
int c [] ,
int i , int j ,
int seuil ) {
if ( j - i + 1 <= seuil ) {
somme_seq_tranche ( a , b , c , i , j );
} else {
int mid = ( i + j ) / 2;
Thread gauche = new Thread (
() -> somme_par_rec1_ij ( a , b , c , i , mid , seuil )
);
gauche . start ();
somme_par_rec1_ij ( a , b , c , 0 , n -1 , seuil );
return c ;
}
Programmation Java 586
return c ;
}
Programmation Java 587
Programme Java 12.5 Parallélisme à granularité (très!) fine avec des Futures —
un thread par position du tableau.
//
// Parallelisme style fork - join a granularite fine avec Futures .
//
@SuppressWarnings ( " unchecked " )
public static int [] somme ( int a [] , int b [] ) {
int n = a . length ;
int c [] = new int [ n ];
return c ;
}
Programmation Java 589
return c ;
}
Programmation Java 590
int n = a . length ;
int [] c = new int [ n ];
ExecutorService pool
= Executors . newFixedThreadPool ( nbTravailleurs );
return c ;
}
Programmation Java 591
Description de newFixedThreadPool :
public static
ExecutorService newFixedThreadPool(int nThreads)
Creates a thread pool that reuses a fixed number of threads oper-
ating off a shared unbounded queue.
ExecutorService pool
= Executors . newFixedThreadPool ( nbTravailleurs );
int n = a . length ;
int [] c = new int [ n ];
tailleTache
1000 100 10 1
newFixedThreadPool 0.14 0.18 0.77 8.52
ForkJoinPool 0.13 0.17 0.37 4.45
• ForkJoinTask :
https: // docs. oracle. com/ javase/ 8/ docs/ api/ java/ util/ concurrent/
ForkJoinPool. html
• ForkJoinPool :
https: // docs. oracle. com/ javase/ 8/ docs/ api/ java/ util/ concurrent/
ForkJoinPool. html
Les temps d’exécution du tableau 12.1 ont été obtenus avec «time -p», pour
des tableaux comportant n =10 000 000 d’entiers, avec 8 threads (nbTravailleurs)
sur une machine avec 8 coeurs (Linux CentOS), et ce pour différentes valeurs de
tailleTache.
Question : Temps séquentiel? Temps par blocs d’éléments adjacents?
Programmation Java 595
synchronized( <objetQuelconque> ) {
<instructions à exécuter de façon exclusive>
}
En termes d’effets, la solution qui suit est équivalente à la précédente, bien que
la précédente soit plus explicite quant au comportement de la méthode (pas besoin
de regarder sa mise en oeuvre pour voir qu’il y a exclusion mutuelle) :
class Compteur {
private int val = 0;
Est-ce que le comportement des deux classes suivantes diffère? Si oui de quelle
façon?
class Compteur {
private int val1 = 0 , val2 = 0;
class Compteur {
private int val1 = 0 ,
val2 = 0;
Le Programme Java 12.10 présente une classe Java appelée Semaphore réalisée
sous forme d’un moniteur. Quelques remarques concernant cet exemple :
• Un appel à la méthode wait() doit toujours être indiqué à l’intérieur d’une in-
struction try/catch, puisqu’il est possible que l’exception InterruptedException
soit signalée (exception qui indique que le thread a été interrompu et doit ter-
miner son exécution).
Le programme Java 12.11 illustre des exemples d’appels faits sans que le thread
appelant soit en possession du verrou.
Programmation Java 600
Programme Java 12.11 Extrait de programme Java qui illustre les erreurs sig-
nalées par des appels à wait() ou notify() sans que le thread appelant soit en
possession du verrou.
Object verrou = new Object ();
=>
-----
=>
Donc, ceci signifie que l’on ne peut pas se baser strictement sur le niveau
de priorité Java pour assurer un ordonnancement spécifique des threads.
Programmation Java 604
• Méthodes : ≈ 50 méthodes!
Programmation Java 605
Lors de l’accès à un verrou, toutes les copies locales des variables du thread
sont mises à jour à partir de la mémoire. Lors de la libération du verrou,
toutes les variables modifiées sont copiées en mémoire.
Citation de http://www.javaperformancetuning.com/news/qotm030.shtml :
try {
t1 . join (); t2 . join ();
} catch ( Exception e ){}
void lockInterruptibly ()
// Acquires the lock unless the current thread
// is interrupted .
Condition newCondition ()
// Returns a new Condition instance
// that is bound to this Lock instance .
boolean tryLock ()
// Acquires the lock only if it is free
// at the time of invocation .
void unlock ()
// Releases the lock .
}
Pourquoi définir une telle interface ainsi que diverses classes qui mettent en oeuvre
cette interface? Réponse extraite de http://download.oracle.com/javase/1.5.
0/docs/api/java/util/concurrent/locks/Lock.html :
Programmation Java 611
Lock l = ...;
l . lock ();
try {
// Se c t i o n c r i t i q u e ou on accede
// a la r e s s o u r c e p r o t e g e e par
// le verrou l .
...
} finally {
l . unlock ();
}
int getHoldCount ()
protected Thread getOwner ()
protected Collection < Thread > getQueuedThreads ()
int getQueueLength ()
protected Collection < Thread > getWaitingThreads ( Condition condition )
int getWaitQueueLength ( Condition condition )
boolean hasQueuedThread ( Thread thread )
boolean hasQueuedThreads ()
boolean hasWaiters ( Condition condition )
boolean isFair ()
boolean isHeldByCurrentThread ()
boolean isLocked ()
void lock ()
void lockInterruptibly ()
Condition newCondition ()
String toString ()
boolean tryLock ()
boolean tryLock ( long timeout , TimeUnit unit )
void unlock ()
}
Programmation Java 613
void acquire ()
void acquire ( int permits )
Programmation Java 614
void acquireUninterruptibly ()
void acquireUninterruptibly ( int permits )
int availablePermits ()
int drainPermits ()
protected Collection < Thread > getQueuedThreads ()
int getQueueLength ()
boolean hasQueuedThreads ()
boolean isFair ()
protected void reducePermits ( int reduction )
void release ()
void release ( int permits )
boolean tryAcquire ()
boolean tryAcquire ( int permits )
boolean tryAcquire ( int permits , long timeout , TimeUnit unit )
boolean tryAcquire ( long timeout , TimeUnit unit )
}
int await ()
// Waits until all parties have invoked await on this barrier .
int getNumberWaiting ()
// Returns the number of parties currently waiting at the barrier .
Programmation Java 615
int getParties ()
// Returns the number of parties required to trip this barrier .
...
void reset ()
// Resets the barrier to its initial state .
}
void await ()
// Causes the current thread to wait until
// the latch has counted down to zero ,
// unless the thread is interrupted .
void countDown ()
// Decrements the count of the latch , releasing all waiting
// threads if the count reaches zero .
long getCount ()
// Returns the current count .
...
}
Programmation Java 616
V exchange ( V x )
// Waits for another thread to arrive at this
// exchange point ( unless the current thread
// is interrupted ) , and then transfers the given
// object to it , receiving its object in return .
int getAndDecrement ()
Programmation Java 617
int getAndIncrement ()
int getAndSet ( int newValue )
int incrementAndGet ()
int intValue ()
long longValue ()
void set ( int newValue )
String toString ()
...
}
Exemples :
• Supposons un seul et unique thread :
AtomicInteger ai = new AtomicInteger ( 17 );
assert ai . compareAndSet ( 17 , 23 );
assert ai . get () == 23;
ai . get () == ? ?;
Quelle est la valeur — ou les valeurs — qui peut être retournée par ai.get()?
Exercice 12.9: Valeur possible pour un AtomicInteger
Programmation Java 618
do {
valeurAvant = valeur . get ();
valeurApres = valeurAvant + 1;
} while ( ! valeur . compareAndSet ( valeurAvant ,
valeurApres ) );
return valeurApres ;
}
AtomicReference ( V initialValue )
V get ()
V getAndSet ( V newValue )
// Atomically sets to the given value
// and returns the old value .
String toString ()
}
Pour manipuler des Doubles de façon atomique, on doit définir soi même une
classe appropriée :
class AtomicDouble {
private AtomicReference < Double > value ;
interface Runnable {
void run ();
}
Un Callable permet de retourner un résultat :)
public interface Callable <V > {
V call ()
// Computes a result , or throws an exception
// if unable to do so .
}
Future<V>
A Future represents the result of an asynchronous computation. Methods are pro-
vided to check if the computation is complete, to wait for its completion, and to
retrieve the result of the computation. The result can only be retrieved using method
get when the computation has completed, blocking if necessary until it is ready.
Cancellation is performed by the cancel method. Additional methods are provided
to determine if the task completed normally or was cancelled. Once a computation
has completed, the computation cannot be cancelled.
public interface Future <V > {
boolean cancel ( boolean mayInterruptIfRunning )
// Attempts to cancel execution of this task .
V get ()
// Waits if necessary for the computation
// to complete , and then retrieves its result .
boolean isCancelled ()
// Returns true if this task was cancelled
// before it completed normally .
boolean isDone ()
// Returns true if this task completed .
}
Exemple d’utilisation :
Programmation Java 621
class App {
ExecutorService executor = ...
ArchiveSearcher searcher = ...
try {
displayText ( future . get ()); // use future
} catch ( ExecutionException ee ) {
cleanup (); return ;
}
}
}
Interface Executor
L’interface de base pour les pool de threads est la suivante :
public interface Executor {
public void execute ( Runnable task );
}
Interface ExecutorService
Extraits de l’interface :
public interface ExecutorService {
boolean awaitTermination ( long timeout , TimeUnit unit )
// Blocks until all tasks have completed execution after
// a shutdown request , or the timeout occurs , or
// the current thread is interrupted , whichever happens first .
<T > T
invokeAny ( Collection < Callable <T > > tasks )
// Executes the given tasks , returning the result of one that has
// completed successfully ( i . e . , without throwing an exception ) , if any do .
boolean isShutdown ()
// Returns true if this executor has been shut down .
boolean isTerminated ()
// Returns true if all tasks have completed following
// shut down .
void shutdown ()
// Initiates an orderly shutdown in which previously
// submitted tasks are executed ,
// but no new tasks will be accepted .
<T > Future <T > submit ( Callable <T > task )}
// Submits a value - returning task for execution
// and returns a Future representing the pending
// results of the task .
int getActiveCount ()
// Returns the approximate number of threads that are
// actively executing tasks .
long getCompletedTaskCount ()
// Returns the approximate total number of tasks that have
// completed execution .
...
Programmation Java 624
void purge ()
// Tries to remove from the work queue all Future tasks
// that have been cancelled .
...
void shutdown ()
// Initiates an orderly shutdown in which previously submitted
// tasks are executed , but no new tasks will be accepted .
}
Remarque : ThreadPoolExecutor est une sous-classe de AbstractExecutorService,
laquelle classe définit, entre autres, la méthode suivante :
<T > Future <T > submit ( Callable <T > task )
Effets des paramètres (du constructeur) sur le comportement des threads et du
pool :
• A ThreadPoolExecutor will automatically adjust the pool size according to the bounds
set by corePoolSize and maximumPoolSize.
When a new task is submitted in method execute, and fewer than corePoolSize
threads are running, a new thread is created to handle the request, even if other
worker threads are idle.
If there are more than corePoolSize but less than maximumPoolSize threads run-
ning, a new thread will be created only if the queue is full.
By setting corePoolSize and maximumPoolSize the same, you create a fixed-size
thread pool. By setting maximumPoolSize to an essentially unbounded value such
as Integer.MAX_VALUE, you allow the pool to accommodate an arbitrary number of
concurrent tasks.
• If the pool currently has more than corePoolSize threads, excess threads will be
terminated if they have been idle for more than the keepAliveTime. This provides
Programmation Java 625
a means of reducing resource consumption when the pool is not being actively used.
If the pool becomes more active later, new threads will be constructed.
• Any BlockingQueue may be used to transfer and hold submitted tasks. The use of
this queue interacts with pool sizing:
– If fewer than corePoolSize threads are running, the Executor always prefers
adding a new thread rather than queuing.
– If corePoolSize or more threads are running, the Executor always prefers
queuing a request rather than adding a new thread.
– If a request cannot be queued, a new thread is created unless this would exceed
maximumPoolSize, in which case, the task will be rejected.
static ExecutorService
newFixedThreadPool ( int nThreads )
// Creates a thread pool that reuses a fixed set
// of threads operating off a shared unbounded queue .
static ExecutorService
newSin gleThreadE xecutor ()
// Creates an Executor that uses a single worker
// thread operating off an unbounded queue .
// Tasks are guaranteed to execute sequentially ,
// and no more than one task will be active
// at any given time .
}
Quelques informations supplémentaires :
• newCachedThreadPool : Creates a thread pool that creates new threads as needed,
but will reuse previously constructed threads when they are available. These pools
Programmation Java 626
will typically improve the performance of programs that execute many short-lived
asynchronous tasks. Calls to execute will reuse previously constructed threads if
available. If no existing thread is available, a new thread will be created and added
to the pool. Threads that have not been used for sixty seconds are terminated and
removed from the cache. Thus, a pool that remains idle for long enough will not
consume any resources. Note that pools with similar properties but different details
(for example, timeout parameters) may be created.
• newFixedThreadPool : Creates a thread pool that reuses a fixed set of threads op-
erating off a shared unbounded queue. If any thread terminates due to a failure
during execution prior to shutdown, a new one will take its place if needed to execute
subsequent tasks.
Object get ()
// Returns the value in the current thread ’s copy
// of this thread - local variable .
goes away, all of its copies of thread-local instances are subject to garbage collection
(unless other references to these copies exist).
public class SerialNum {
// The next serial number to be assigned
private static int nextSerialNum = 0;
• ArrayBlockingQueue<E>
• ConcurrentHashMap<K,V>
• ConcurrentLinkedDeque<E>
• ConcurrentLinkedQueue<E>
• ConcurrentSkipListMap<K,V>
• ConcurrentSkipListSet<K,V>
ConcurrentHashMap<K,V> :
• ConcurrentHashMap :
– It is thread safe without synchronizing the whole map.
– Reads can happen very fast while write is done with a lock.
– There is no locking at the object level.
– The locking is at a much finer granularity at a hashmap bucket level.
VarInteger () {
lock = new ReentrantLock ();
atomicVal = new AtomicInteger ( 0 );
}
// On lance la minuterie .
long tempsDebut = System . currentTimeMillis ();
// On arrete la minuterie .
long tempsFin = System . currentTimeMillis ();
System . out . format ( " %7 d " , ( tempsFin - tempsDebut ) );
}
System . out . format ( " \ n " );
}
Programmation Java 632
Programmation Java 633
Programmation Java 634
Programmation Java 635
Programmation Java 636
Programmation Java 637
Programmation Java 638
• Le stream étant parallèle, son contenu doit être examiné avec forEachOrdered
pour que l’impression se fasse en respectant l’ordre des éléments triés.
Pour plus de détails sur les streams Java, voir la documentation en ligne d’Oracle :
https://docs.oracle.com/javase/8/docs/api/java/util/stream/package-summary.
html
Effet de flat_map (version Ruby) :
>> [[10 , 20 , 30] , [] , [88 , 99]].
flat_map { | x | x }
= > [10 , 20 , 30 , 88 , 99]
Programme Java 12.14 Fonction pour trier les mots d’un fichier, en s’assurant
que chaque mot apparaît au plus une fois — version avec streamsde Java 8.0.
private static Stream < String >
lignes ( String nomFichier ) {
try {
return
new BufferedReader (
new FileReader ( nomFichier )
). lines ();
} catch ( Exception e ) {
...
}
}
Pair ( T f , U s ) {
first = f ;
second = s ;
}
Pair < String , String >[] a = ( Pair < >[]) new Pair < String , String >[ N ];
- - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Programmation Java 641
Pair < String , String >[] a = new Pair < String , String >[ N ];
- - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Generiques . java :42: error : generic array creation
Pair < String , String >[] a = new Pair < String , String >[ N ];
Pair < String , String >[] a = ( Pair < String , String >[]) new Pair [ N ];
- - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Generiques . java :55: warning : [ unchecked ] unchecked cast
Pair < String , String >[] a = ( Pair < String , String >[]) new Pair [ N ];
^
required : Pair < String , String >[]
found : Pair []
double r
= sommation_pr (a , 0 , a . length -1 , 100 , pool );
System . out . println ( r );
Qu’est-ce qui sera imprimé par le segment de code ci-haut selon les différentes valeurs
possibles suivantes pour pool :
1. Executors.newCachedThreadPool()
2. new ForkJoinPool(4)
3. Executors.newFixedThreadPool(4)
try {
return gauche . get () + droite ;
} catch ( Exception e ) {
assert false : " *** Exception : " + e ;
return 0.0 D ;
}
}
Programmation Java 644
double r
= sommation_pr (a , 0 , a . length -1 , 2, pool );
System . out . println ( r );
Qu’est-ce qui sera imprimé par le segment de code ci-haut selon les différentes valeurs
possibles suivantes pour pool :
1. Executors.newCachedThreadPool()
2. new ForkJoinPool(4)
Programme Java 12.16 Sommation des éléments d’un tableau avec des
RecursiveTask et un ForkJoinPool.
class SommationRT extends RecursiveTask < Double > {
private double [] a ;
private int inf , sup , seuil ;
@Override
public Double compute () {
if ( sup - inf + 1 <= seuil ) {
return sommation_tranche (a , inf , sup );
}
// Utilisation .
ForkJoinPool pool = new ForkJoinPool ( nbThreads );
SommationRT rt = new SommationRT (a , 0 , a . length -1 , seuil );
double r = pool . invoke ( rt );
Programmation Java 646
V get ()
// Waits if necessary for the computation to complete ,
// and then retrieves its result .
V join ()
// Returns the result of the computation when it is done .
// This method differs from get () in that abnormal completion
// results in RuntimeException or Error , not ExecutionException ,
// and that interrupts of the calling thread do not cause
// the method to abruptly return by throwing InterruptedException .
}
• Une cellule d’une IStructure peut être lue avec get. Toutefois, lorsque la
cellule est vide, le thread appelant est mis en attente jusqu’à ce que la cellule
ait été remplie par un autre thread.
• Une cellule d’une IStructure ne peut être écrite, avec put, qu’une seule et
unique fois. C’est une erreur (AlreadyFullException) d’écrire plus d’une
fois dans une cellule donnée d’une IStructure. Si des lecteurs sont attentes
au moment de l’écriture, ils sont réactivés de façon à obtenir la valeur qui
vient d’être écrite.
Le Programme Java 12.19 présente un petit cas de test, avec le processeur lecteur
(thread getter) mis en attente et réactivé lors de l’écriture par un autre thread.
/* *
* Obtient le ieme element de la I - Structure .
*
* @requires 0 <= i && i < taille de la I - Structure
*
* @param i Index
* @return L ’ element a la position indiquee
*/
T get ( int i );
}
class AlreadyFullException
extends RuntimeException {}
Programmation Java 649
Programme Java 12.18 Une classe concrète IStructureMonitor qui met en oeu-
vre l’interface IStructure.
import java . util . concurrent . locks .*;
650
Chapitre 13
651
Chapitre 14
652
Chapitre 15
653
Exemples MPI 654
Le programme principal
# include < mpi .h >
# include < stdio .h >
# include < stdlib .h >
# include < math .h >
# include < assert .h >
...
//
Exemples MPI 655
// On << dispatche > > les trois processus , en plus du programme principal .
if ( numProc == 0 ) {
int x = 10;
MPI_Send ( &x , 1 , MPI_INT , 1 , DONNEES , MPI_COMM_WORLD );
MPI_Finalize ();
return ( 0 );
}
Exemples MPI 656
//
Exemples MPI 657
//
Exemples MPI 658
//
Exemples MPI 660
return sommeTotale ;
}
Exemples MPI 661
NX : Nombre de points
uk : vecteur des temperatures au temps t
ukp1 : vecteur des temperatures au temps t plus 1
1.0: " longueur " du cylindre
Posons :
dx = 1.0 / NX
dt = 0.5 * dx * dx
Alors :
ukp1 [ i ]
= uk [ i ] + dt / ( dx * dx ) * ( uk [ i +1] - 2 * uk [ i ] + uk [i -1])
= uk [ i ] + (0.5 * dx * dx )/( dx * dx ) * ( uk [ i +1] - 2 * uk [ i ] + uk [i -1])
= uk [ i ] + 0.5 * ( uk [ i +1] - 2 * uk [ i ] + uk [i -1])
= uk [ i ] + 0.5 * uk [ i +1] - 0.5 * 2 * uk [ i ] + 0.5 * uk [i -1]
= uk [ i ] + 0.5 * uk [ i +1] - uk [ i ] + 0.5 * uk [i -1]
= 0.5 * uk [ i +1] + 0.5 * uk [i -1]
= ( uk [ i +1] + uk [i -1] ) / 2
*/
Exemples MPI 663
# define NX (1000*16)
# define LEFTVAL 1.0
# define RIGHTVAL 10.0
# define NSTEPS 10000
double dx = 1.0 / NX ;
double dt = 0.5 * dx * dx ;
initialize ( uk , ukp1 );
return ( 0 );
}
Exemples MPI 665
double dx = 1.0 / NX ;
double dt = 0.5 * dx * dx ;
if ( myID != 0)
MPI_Recv ( & uk [0] , 1 , MPI_DOUBLE , leftNbr , 0 ,
MPI_COMM_WORLD , & status );
if ( myID != numProcs -1)
MPI_Recv ( & uk [ numPoints +1] , 1 , MPI_DOUBLE , rightNbr , 0 ,
MPI_COMM_WORLD , & status );
MPI_Finalize ();
670
Chapitre 17
Exécution et débogage de
programmes parallèles MPI avec
OpenMPI
671
Débogage de programmes MPI 672
Un cluster — une grappe de processeurs, une grappe de calcul — est donc une machine
parallèle MIMD de type multi-ordinateurs ayant les caractéristiques suivantes :
• Les diverses machines — les divers «noeuds» — sont intégrées en un système unique,
(généralement) avec un réseau dédié.
• Les divers noeuds sont des machines de «faible coût», où chaque noeud «pourrait»
en théorie être utilisé comme une machine ou station de travail normale. Toutefois,
en pratique, généralement un seul des noeuds — le «head node» — est accessible
directement aux usagers.
Débogage de programmes MPI 673
quark21.hpc.uqam.ca
numProc = 1, nbProcs = 5
quark22.hpc.uqam.ca
numProc = 2, nbProcs = 5
quark23.hpc.uqam.ca
numProc = 3, nbProcs = 5
quark24.hpc.uqam.ca
numProc = 4, nbProcs = 5
Débogage de programmes MPI 675
Signalons que n’importe quel programme ou commande peut être exécuté avec
mpirun :
Autres trucs :
• Lorsqu’on utilise des printf pour générer une trace d’exécution, il est préférable de
mettre une instruction fflush immédiatement après le printf, pour assurer que les
impressions se fassent dans un ordre qui reflète le plus possible l’exécution réelle :
fflush( stdout );
Il faut aussi savoir que les programmes parallèles peuvent parfois contenir des Heisen-
bug. Plus précisément, il peut arriver qu’un programme parallèle ne fonctionne pas
— par exemple, à cause d’erreurs de synchronisation entre processus — mais que
le programme fonctionne sans problème quand on rajoute des instructions printf
pour tenter de le déboguer!1
Lorsqu’on utilise des traces d’exécution, il faut aussi tenir compte du fait que la
quantité totale d’information générée sera multipliée par le nombre de processeurs
— ce qui peut parfois rendre difficile de comprendre les informations ainsi produites.
1
On parle de Heisenbug car l’effet d’observer le programme modifie son comportement, dans
l’esprit du principe d’incertitude d’Heisenberg en physique.
Débogage de programmes MPI 677
• Lorsqu’une erreur d’exécution est générée par MPI, le message contient généralement
le numéro du processeur (virtuel) et autres informations. Par exemple, le message
suivant a été produit par le processeur 0 :
• «According to the MPI standard, message buffering may or may not occur when
processes communicate with each other using MPI_Send.»
Cette question sera abordée ultérieurement.
Débogage de programmes MPI 680
• On peut demander, avec l’option «--tag-output», que chaque impression sur stdout
soit automatiquement préfixée du numéro du processus : voir figure 17.1.
Idem pour «--timestamp-output», mais un timestamp est aussi affiché.
int signal;
MPI_Send( &signal, 1, MPI_TYPE_NULL, 1, 0, MPI_COMM_WORLD );
...................
int signal;
MPI_Recv( &signal, 1, MPI_INT, MPI_ANY_SOURCE, 0, MPI_COMM_WORLD, &statut );
quark21.hpc.uqam.ca
numProc = 1, nbProcs = 3
quark22.hpc.uqam.ca
numProc = 2, nbProcs = 3
---------------------------------------
Figure 17.2: Création de plusieurs processus sur un noeud unique ou sur un groupe
limité de noeuds. Cet exemple illustre aussi le fait que le programme exécuté par
mpirun peut aussi être une simple commande Unix.
Débogage de programmes MPI 683
// Processus 0
int signal ;
MPI_Send (& signal , 1 , MPI_DATATYPE_NULL , 1 , 0 , MPI_COMM_WORLD );
// Processus 1
int signal ;
MPI_Recv (& signal , 1 , MPI_INT , MPI_ANY_SOURCE , 0 , MPI_COMM_WORLD , & st );
===========================================================================
quark22.hpc.uqam.ca
numProc = 2, nbProcs = 3
quark21.hpc.uqam.ca
numProc = 1, nbProcs = 3
===========================================================================
18.1 Introduction
Ce chapitre présente trois stratégies pour effectuer le produit de matrices dans un contexte
de programmation parallèle par échange de messages. Ces trois stratégies reposent sur une
distribution des données par blocs.
684
Produit parallèle de matrices 685
En d’autres mots, avec une distribution par blocs, les coûts des communications aug-
mentent moins rapidement lorsqu’on augmente le nombre de processeurs — en fonction de
√
p plutôt qu’en fonction de p (augmentation linéaire).
La figure 18.1 présente une décomposition en neuf (9) «blocs» pour neuf (9) processus
d’une matrice 3 × 3, où chaque bloc indique les produits qui doivent être effectués et
additionnés pour calculer le résultat de Cij dont est responsable le processus Pij — pour
une matrice de plus grande taille, il suffirait d’intepréter les aij comme des sous-matrices,
i.e., de vrais «gros blocs» d’éléments.
Plus précisément, le processus Pij est «responsable» des éléments d’index i, j de cha-
cune des matrices, i.e., il doit initialement stocker les éléments appropriés des matrices de
départ A et B, et calculer/stocker l’élément correspondant de la matrice résultat C. Dans
Produit parallèle de matrices 686
la figure 18.1, les cercles en pointillés indiquent l’élément a et l’élément b stockés par le
processus Pij ; pour tous les autres éléments, des communications avec d’autres processus
sont donc nécessaires.
• A:N ×P
• B :P ×M
• C :N ×M
La figure 18.2 présente la solution «standard» habituelle. Les figures 18.3 et 18.4,
quant à elles, présentent une solution alternative où les boucles ont été organisées de façon
différente — la boucle la plus interne est devenue la boucle externe.
Produit parallèle de matrices 687
Figure 18.1: Matrice résultat C : calculs (produits et sommes) à effectuer pour une
matrice 3×3 (avec 9 blocs, pour 9 processus). Les items en pointillés indiquent des
éléments qui sont locaux au processus, à cause de la distribution par blocs. Tous
les autres items sont non-locaux, donc doivent être obtenus via des communications.
Produit parallèle de matrices 688
// C = A * B
//
// A: N × P
// B: P × M
// C: N × M
// C = A * B
//
// A: N × P
// B: P × M
// C: N × M
// C = A * B
//
// A: N × P
// B: P × M
// C: N × M
//
initialize ( C , N , M , 0.0 );
Figure 18.5: Ordre de calcul des produits dans la méthode de Mattson, Sanders et
Massingil [MSM05] (voir code plus loin).
La figure 18.5 illustre quels calculs (produits) sont effectués à chacune des étapes (k =
0, 1, 2) du programme MPI vu en cours (adaptation de [MSM05]). Dans cette méthode de
calcul, chacun des processus Pij effectue, à l’étape k (k = 0, 1, . . . , n − 1), le produit de
aik · bkj .
La figure 18.6, quant à elle, indique les communications qui doivent être effectuées
avant le début des calculs de la zéroième étape, pour assurer que les dépendances de don-
Produit parallèle de matrices 691
nées soient correctement satisfaites — une figure équivalente, décalée de façon appropriée,
pourrait être produite pour les étapes 1 et 2. Les items entourés d’un petit rond sont
ceux qui doivent être transmis, par le processus Pij . Les figures qui suivent illustrent les
communications aux étapes subséquentes.
• myID_i = myID / NB
• myID_j = myID % NB
P0 P1 P2
P3 P4 P5
P6 P7 P8
Soit alors les instructions MPI_Comm_split suivantes :
MPI_Comm lignes , colonnes ;
/*
* Solution parallele pour le produit de matrices , avec allocation
* dynamique des matrices et distribution par blocs .
*
* Chaque matrice est allouee sous forme d ’ un << vecteur > > lineaire de
* la taille appropriee . Les diverses routines doivent donc manipuler
* explicitement les pointeurs plutot que de faire des simples
* operations d ’ indexation .
*
* Source : Le code programme est essentiellement tire de " Patterns for
* Parallel Programming " , T . G . Mattson , B . A . Sanders and
* B . L . Massingill , Addison - Wesley , 2005.
*
* Diverses modifications mineures ont toutefois ete apportees pour
* simplifier un peu le code , notamment dans la facon d ’ initialiser
* les matrices , et ce dans le but de verifier ( avec des assertions )
* que le resultat final est bien celui attendu . Le style des
* declarations a aussi ete quelque peu modifie , notamment en
* utilisant le plus possible des declarations locales ( le plus pres
* du point d ’ utilisation ). Finalement , les echanges de blocs se font
* par l ’ intermediaire de Bcast a des sous - groupes ( memes lignes ou
* meme colonnnes ) plutot que par des envois point -a - point .
*
* Argument du programme :
* - Facteur multiplicatif pour taille de la matrice
*
* Note : bien que l ’ approche puisse traiter des matrices
* rectangulaires ( A : N X P , B : P X M , et donc C : N X M ) , pour
* simplifier l ’ utilisation du programme , un seul argument est
* specifie sur la ligne de commande , donc on traite
* effectivement des matrices carrees . De plus , pour assurer le
* respect de la condition que la taille soit divisible par la
* racine carre du nombre de processeurs , l ’ argument N ne
* determine pas la taille de facon exacte mais un facteur
* multiplicatif d ’ un nombre predefini produit des premiers
* entiers 2 , 3 , etc .
*/
int _DEBUG = 0;
# define DEBUG ( x ) if ( _DEBUG ) x
//
Produit parallèle de matrices 698
// / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / /
// Signature des operations auxiliaires sur les matrices .
// / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / /
/*
* Les operations qui suivent sur les matrices sont liees a la
* representation interne utilisee , a savoir , une matrice est
* representee par un vecteur ( lineaire ) -- donc il faut " jouer " de
* facon explicite avec l ’ adresse de base , les indices , le stride ,
* etc .
*
*/
//
Produit parallèle de matrices 699
// / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / /
// Operations pour debogage et test .
// / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / /
//
Produit parallèle de matrices 700
// / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / /
// Fonction auxiliaire pour distribution des blocs de donnees .
// / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / /
//
Produit parallèle de matrices 701
// / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / /
// Programme principal .
// / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / /
//
Produit parallèle de matrices 702
//
Produit parallèle de matrices 703
//
// On effectue le produit a l ’ aide des NB phases .
//
initialize ( C , dimNb , dimMb , dimMb , 0.0 );
//
Produit parallèle de matrices 704
MPI_Finalize ();
return ( 0 );
}
//
Produit parallèle de matrices 705
// / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / /
// Mise en oeuvre des diverses operations auxiliaires .
// / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / /
//
// Operations pour manipulation des matrices par bloc .
//
void initialize ( double *A , int dimNb , int dimMb , int stride , double v )
{
// A contient l ’ adresse de base du bloc , donc pointe a la premiere ligne !
for ( int i = 0; i < dimNb ; i ++ ) {
double * pt = A ;
for ( int j = 0; j < dimMb ; j ++ ) {
* pt ++ = v ;
}
A += stride ; // Adresse de la prochaine ligne .
}
}
//
Produit parallèle de matrices 706
Quelques explications :
• Tel qu’indiqué plus haut, la programme effectue le produit C = A × B, avec A: dimN × dimP,
B: dimP × dimM et C: dimN × dimM.
Toutefois, en pratique, pour simplifier l’appel du programme, dimM = dimP = dimN
= N, où N est l’argument du programme.
• NB = Nombre de sous-blocs sur une ligne ou sur une colonne, donc NB×NB =
numProcs.
• dimKb, avec K∈{N,P,M} = nombre d’éléments de base (double) dans un bloc selon
la dimension dimK, donc dimKb = dimK / NB.
Performances
La figure 18.9 présente les accélérations obtenues sur turing.hpc.uqam.ca (30 processeurs
physiques) pour différentes tailles de matrices (N X N) et différents nombres de processus
(donc avec des processeurs virtuels lorsque le nombre de processus est supérieur à 30).
Produit parallèle de matrices 708
Comme précédemment, les cercles pointillés indiquent des données locales au processus
Pij : on remarque que les bij sont déjà tous au bon endroit pour effectuer la zéroième étape,
mais pas les aij . Avant d’effectuer les calculs des produits de la zéroième étape, les éléments
a appropriés doivent donc être transmis aux autres processus, tel que cela est illustré par
les flèches (normales) sur la figure 18.11.
En examinant la figure 18.10, on peut aussi remarquer qu’à l’étape 1, ces sont les valeurs
bij utilisées à l’étape 0 qui seront utilisées pour les produits calculés à cette nouvelle étape
— et ainsi de suite pour chacune des étapes subéquentes.
À une étape de l’algorithme de Fox, on va donc effectuer les opérations suivantes :
• Dans chacune des colonnes, on va «décaler» (vers le haut, de façon cyclique) les
valeurs de b pour qu’elles soient disponibles à l’étape suivante de calcul.
Les diverses communications sont illustrées, pour la zéroième étape, à la figure 18.11,
où les flèches en pointillées représentent des «décalages» (vertical, au niveau des colonnes,
et cyclique). Signalons aussi qu’à l’étape subséquente, pour chacun des processus, ce sera le
b reçu qui sera à nouveau transmis pour poursuivre le décalage vertical, ce qui assurera que
tous les éléments b de la colonne auront ultimement été traités par chacun des processus
— voir figure 18.12.
Produit parallèle de matrices 710
714
Chapitre 20
Andrews [And00, Chap. 1 et 9] indique qu’il existe trois (3) patrons de base pour les
interactions entre processus concurrents communiquant par l’intermédiaire de messages :
• Producteur/Consommateur.
• Client/Serveur.
• Pairs interagissants.
Ces patrons de base peuvent être combinés de différentes façons pour organiser les
interactions entre processus. Ainsi, au chapitre 9, Andrews présente sept (7) patrons, qu’il
nomme «paradigmes d’interactions» entre processus. Les trois (3) premiers paradigmes,
que nous allons brièvement présenter, s’appliquent plus particulièrement aux applications
parallèles, alors que les quatre (4) autres (que nous ne présenterons pas) sont orientés plus
spécifiquement vers les applications distribuées.
Les trois «paradigmes d’interaction entre processus» d’Andrews qui nous intéressent
sont les suivants [And00, Chap. 9] :
715
Paradigmes d’interaction entre processus 716
20.1 Coordonnateur/travailleurs
On peut distinguer deux grandes classes de programmes parallèles avec coordonnateur et
travailleurs, qui se distinguent par la façon dont le travail est réparti entre les travailleurs :
REPETER
Envoyer les valeurs appropriées aux processus <<voisins>>
Recevoir les valeurs des processus <<voisins>>
Effectuer le traitement (en fonction des nouvelles valeurs)
JUSQUE condition pour terminer satisfaite
• Un algorithme pipeline contient lui aussi des réceptions et envois. Par contre,
les valeurs envoyées à une étape résultent généralement du traitement des données
reçues à cette même étape. La structure générale est donc habituellement la suivante,
plus précisément ici dans le cas d’un pipeline linéaire :
BOUCLER
Recevoir les valeurs du processus voisin <<précédent>>
SORTIR QUAND fin de flux rencontrée (EOS)
Effectuer le traitement
Transmettre les valeurs au voisin <<suivant>>
FIN
Annexes
720
Appendix A
La stratégie «diviser-pour-régner»
pour la conception d’algorithmes
récursifs
A.1 Diviser-pour-régner
– Diviser-pour-régner = approche descendante à la résolution d’un problème :
• On décompose le problème à résoudre en sous-problèmes plus simples.
• On trouve la solution des sous-problèmes.
• On combine les solutions des sous-problèmes pour obtenir la solution du problème
initial.
Cette approche conduit, de façon naturelle (mais pas obligatoirement), à un algorithme
récursif :
• Question = comment obtenir la solution des sous-problèmes?
• Réponse = en appliquant la même approche diviser-pour-régner descendante aux
sous-problèmes, et ce jusqu’à ce que le problème à résoudre soit trivial.
721
Stratégie diviser-pour-régner 722
if ( v <= A [ m ]) {
pos = trouverPosRec (A , inf , m , v )
} else {
pos = trouverPosRec (A , m +1 , sup , v )
}
}
}
– Analyse de l’algorithme :
T (n) = n ∈ Θ(n)
k
X
n = n × k = n lg n
i=1
Note : il est important de pouvoir faire, lorsque nécessaire, une telle analyse informelle
(basée sur la structure de l’arbre, le nombre de noeuds, le travail effectué dans chaque
noeud, etc.) de la complexité (même non exacte) . . . parce que cela nous permet souvent
de mieux comprendre le fonctionnement de l’algorithme (récursivité, nombre de niveaux
d’appel, nombre de sous-tâches générées, etc.).
Stratégie diviser-pour-régner 727
Dans certains cas, la majeure partie du travail se fait au niveau de la division en sous-
problèmes (par ex., quicksort) alors que pour d’autres cas la majeure partie du travail se
fait au niveau de la combinaison des solutions aux sous-problèmes (par ex., tri par fusion).
– De façon générique, la stratégie diviser-pour-régner peut être exprimée de la façon in-
formelle (pseudocode) telle que présentée à l’algorithme A.3.
T (n) = T (n − 1) + n − 1
= [T (n − 2) + n − 2] + n − 1
= T (n − 2) + (n − 2) + (n − 1)
= T (n − 3) + (n − 3) + (n − 2) + (n − 1)
= ...
= T (n − i) + (n − i) + (n − i + 1) + . . . + (n − 2) + (n − 1)
= ...
= T (1) + 1 + 2 + . . . + (n − 2) + (n − 1)
= 0 + 1 + 2 + . . . + (n − 2) + (n − 1)
n−1
X
= i
i=0
n(n − 1)
=
2
– Malgré le résultat obtenu pour l’analyse du pire cas, le tri rapide est généralement
considéré comme un tri intéressant. De façon relativement rigoureuse, ceci peut être montré
en utilisant une analyse de la complexité moyenne (cf. le cours INF4100). Ceci peut aussi
être montré, de façon informelle, tel qu’illustré dans les paragraphes qui suivent.
posPivot = inf
int pivot = A [ posPivot ]
La boucle for qui suit immédiatement le choix du pivot peut alors débuter son exécu-
tion sous la condition que le pivot est initialement à la position inférieure du tableau.
Supposons maintenant que l’on dispose d’une fonction posMediane jouant un rôle
d’oracle et qui, en temps Θ(n), peut trouver la position de l’élément médiane de A.1
Remplaçons alors les deux instructions mentionnées plus haut par la suite d’instructions
suivantes :
En supposant que les deux moitiés sont effectivement réparties de façon égale (grâce
au choix de la médiane comme pivot), on obtiendrait alors une décomposition équilibrée
(générant deux sous-problèmes de tailles presqu’identiques) semblable à celle du tri par
fusion.
La question qui se pose alors est de savoir s’il est possible de déterminer la médiane
en temps linéaire. En d’autres mots, est-il possible de réaliser, ou même simplement
approximer, le comportement de l’oracle calculant la médiane? La réponse à cette question
est positive :
1. En fait, il existe un algorithme qui permet effectivement de déterminer, en temps
linéaire, la médiane d’un groupe d’éléments.
2. Une autre façon d’obtenir une approximation de la médiane pourrait être d’utiliser
un algorithme de type Las Vegas, c’est-à-dire, un algorithme aléatoire (probabiliste).
Par exemple, on pourrait choisir, de façon aléatoire, un certain nombre fixe d’éléments
du tableau (par ex., cinq éléments choisis au hasard) et ensuite identifier, en temps
constant (puisqu’on a un nombre fixe d’éléments), la médiane parmi ces cinq élé-
ments. La valeur espérée serait alors une approximation de la médiane qui ferait
en sorte que, en moyenne, les deux sous-tableaux générés lors du partitionnement
seraient de tailles équivalentes.
distinguent tout d’abord par leur complexité dans le pire cas : O(n lg n) par opposition à
O(n2 ). Ils se distinguent aussi en fonction de l’espace requis pour exécuter chacun d’eux :
Algorithme (coût Coût de la décom- Coût de l’assem- Coût pour la Complexité totale
pour chaque ap- position en sous- blage des sous- partie non-
pel) problèmes solutions récursive
Tri par fusion O(1) O(n) O(n) O(n lg n)
En d’autres mots, le gros du travail dans le cas de tri par fusion se fait au moment de
la combinaison des solutions (fusion des parties déjà triées), alors que la décomposition en
sous-problèmes semblables au problème initial est trivial (on divise en deux parties de taille
équivalente, indépendamment du contenu, en utilisant simplement l’index milieu). Par
contre, dans le tri rapide, c’est la décomposition en sous-problèmes qui est coûteuse (par-
titionnement en deux parties comportant les éléments inférieurs vs. supérieurs au pivot)
alors que la combinaison des solutions est triviale (les deux parties sont déjà triées et dans
le bon ordre).
– Dans l’abstrait, les surcoûts (overhead ) associés à la gestion des appels récursifs (par
ex., allocation et copie des arguments sur la pile) peuvent être ignorés. En pratique, ces
surcoûts peuvent devenir significatifs et il peut devenir plus efficace, à partir d’une certaine
taille de problème, d’utiliser une approche asymptotiquement moins efficace, mais avec un
coefficient plus faible au niveau des surcoûts. La stratégie diviser-pour-régner avec seuil
(avec coupure) devient alors, en gros, celle illustrée à l’algorithme A.5 (en supposant une
décomposition dichotomique, c’est-à-dire en deux sous-problèmes) :
Dans l’un ou l’autre de ces cas, le temps d’exécution résultant est alors de complexité
exponentielle ou factorielle, ce qui rend donc l’algorithme tout à fait inefficace et inutilis-
able, sauf pour de (très) petites valeurs de n. (Pour s’en convaincre, il suffit d’identifier et
d’analyser les équations de récurrence associées à des telles décompositions récursives.)
• Sortie : On désire obtenir le nombre de noms distincts qui sont présents dans le
fichier commentaires.txt.
Stratégie diviser-pour-régner 735
On peut dire que l’algorithme non récursif suivant utilise une stratégie diviser-pour-
régner, puisqu’il y a décomposition du problème initial en sous-problèmes plus simples,
lesquels sous-problèmes sont résolus de façon indépendante :
DEBUT
noms <- obtenir la liste des noms contenus dans le fichier commentaires.txt
noms_tries_et_uniques <- trier (de façon unique) les noms
nb <- nombre d’éléments dans noms_tries_et_uniques
RETOURNER( nb )
FIN
En fait, on peut dire que la stratégie diviser-pour-régner, sans récursivité, est la base
même de la décomposition fonctionnelle.
Finalement, il est intéressant de noter que cet algorithme peut être mis en oeuvre de
façon très simple sur une machine Unix/Linux, et ce au niveau même du shell :
Note : une fonction, au sens mathématique du terme, n’est qu’une forme spéciale de
constante!
– Dans un langage fonctionnel, les fonctions sont des valeurs manipulables comme toutes
les autres (“citoyens de première classe”). Il est donc possible, et naturel, de transmettre
des arguments à une fonction qui sont eux-mêmes des fonctions, de retourner un résultat
qui est une fonction, de conserver une fonction dans une structure de données, etc.
– La programmation fonctionnelle est intéressante à cause de son style déclaratif, très près
de ce qu’on écrirait en mathématiques. Il est donc plus facile de raisonner à propos d’un
programme, c’est-à-dire, de déterminer les propriétés satisfaites par le programme) : on
peut utilier le raisonnement par substitution (raisonnement équationnel ): “equals can be
replaced by equals”, comme en mathématique.
– La plupart des langages fonctionnels modernes utlisent les séquences (listes) comme
structures de données de base. Les algorithmes s’expriment donc souvent en termes de
manipulations de listes.
– De façon générique, la stratégie diviser-pour-régner peut être exprimée de la façon in-
formelle (pseudocode) présentée à l’algorithme A.3 (p. 727).
– Dans un langage fonctionnel, l’utilisation de la stratégie diviser-pour-régner peut être
exprimée de façon explicite et générique (donc favorisant la réutilisation) en définissant un
groupe de fonctions appropriées, tel que cela est illustré dans l’extrait de code Haskell 1.
Quelques explications concernant cette fonction :
• La fonction reçoit cinq arguments, les quatre premiers étant eux-mêmes des fonc-
tions — les commentaires (partie à droite de “–”) indiquent le type de l’argument
correspondant :
Stratégie diviser-pour-régner 737
diviserPourRegner
estSimple -- (Probleme -> Bool) ->
resoudreProblemeSimple -- (Probleme -> Solution) ->
decomposerProbleme -- (Probleme -> [Probleme]) ->
combinerSolutions -- (Probleme -> [Solution] -> Solution) ->
probleme -- Probleme ->
-- Solution
= resoudreProbleme probleme
where
resoudreProbleme probleme
| estSimple probleme = resoudreProblemeSimple probleme
| otherwise = combinerSolutions probleme sousSolutions
where sousSolutions = map resoudreProbleme sousProblemes
sousProblemes = decomposerProbleme probleme
fois2 x = 2 * x
plus x y = x + y
plus1 x = plus 1 x -- Autre facon: plus1 = plus 1
Stratégie diviser-pour-régner 738
Dans l’extrait de code Haskell 1, la fonction map applique donc la fonction resoudreProbleme
à chacun des sous-problèmes de la liste sousProblemes et retourne une liste des
sousSolutions.
• Une fonction de tri de type quicksort. On verra plus en détail cet algorithme à la
prochaine section.
• Une fonction pour calculer le nième nombre de Fibonnaci.
Stratégie diviser-pour-régner 739
Programme Java A.1 Classe abstraite Java pour patron (template pattern)
diviser-par-régner générique.
//
// Une classe Java abstraite et generique pour representer des problemes
// a resoudre par une approche diviser-pour-regner.
//
}
Stratégie diviser-pour-régner 741
Factoriel f
= new Factoriel( 1, Integer.parseInt(args[0]) );
f.resoudre();
System.out.println( f.solution() );
}
}
Stratégie diviser-pour-régner 742
Programme Java A.3 Classe concrète Java pour tri par fusion (première partie).
//
// Tri par fusion vu comme une instance de la classe generique.
//
class TriFusion extends ProblemeDPR<Integer[]> {
Integer[] elems;
Programme Java A.4 Classe concrète Java pour tri par fusion (deuxième partie).
public static void main(String[] args) {
if (args.length == 0) {
System.out.println( "Usage:" );
System.out.println( " java TriFusion n" );
System.exit(1);
}
• Version control
• Unit testing
• Build automation
Version control needs to come before anything else. It’s the first bit of infrastructure
we set up on any project.»
744
Aperçu de git 745
Ceci signifie qu’on peut préserver un historique détaillé de l’évolution locale d’un
projet sans interférer avec le code dans le dépôt central. Ce n’est que lorsqu’on
est certain que tout est correct qu’on peut alors faire un push pour transmettre les
changements appropriés au dépôt central.
• Avec git, on garde la trace non pas des noms de fichiers comme dans les autres
systèmes. . . mais bien des contenus.
• Avec git, la création de tags et de branchs est peu coûteusen, donc il ne faut pas
s’en priver.
• Index — appelé aussi staging area = Fichiers, nouveaux et modifiés, ayant été
ajoutés avec git add , donc sous le contrôle de git.
L’index regroupe les fichiers qui formeront le prochain commit.
Figure B.1: Les trois niveaux d’un dépôt local git. Adapté de [Cha09].
La figure B.1 présente les trois niveaux d’un projet sour le contrôle de git, et les
principales actions qui permettent de «transférer» un fichier d’un niveau à un autre.
Aperçu de git 750
$ more ~/.gitconfig
[user]
name = Guy Tremblay
email = [email protected]
[color]
ui = auto
$ cd ProjetJava
$ more .gitignore
*.class
# Fichiers d’archives
*.jar
*.war
$ ls
$ ls -a
. .. .git
$ ls .git
branches config description HEAD hooks info objects refs
$
$ git status
# On branch master
#
# Initial commit
#
# Untracked files:
# (use "git add <file>..." to include in what will be committed)
#
# factoriel.rb
# factoriel_spec.rb
nothing added to commit but untracked files present (use "git add" to track)
$ git status
# On branch master
nothing to commit, working directory clean
$ git log
commit fd77def4c0e84ef3855035bd6dd3d3645f6b3602
Author: Guy Tremblay <[email protected]>
Date: Mon Sep 7 09:04:41 2015 -0400
$ emacs factoriel.spec
...
$ git status
# On branch master
# Changes not staged for commit:
# (use "git add <file>..." to update what will be committed)
# (use "git checkout -- <file>..." to discard changes in working directory)
#
# modified: factoriel.rb
#
no changes added to commit (use "git add" and/or "git commit -a")
$ git log
commit 0e6e655637e23c367270a29739811a8f3d86ab21
Author: Guy Tremblay <[email protected]>
Date: Mon Sep 7 09:04:58 2015 -0400
commit fd77def4c0e84ef3855035bd6dd3d3645f6b3602
Author: Guy Tremblay <[email protected]>
Date: Mon Sep 7 09:04:41 2015 -0400
$ git status
On branch master
Changes not staged for commit:
(use "git add <file>..." to update what will be committed)
(use "git checkout -- <file>..." to discard changes in working
directory)
modified: factoriel.rb
no changes added to commit (use "git add" and/or "git commit -a")
Aperçu de git 755
$ git diff
diff --git a/factoriel.rb b/factoriel.rb
index 5d63d76..7ba6e02 100644
--- a/factoriel.rb
+++ b/factoriel.rb
@@ -1,5 +1,6 @@
require ’pruby’
def fact_seq_lineaire( n )
if n == 0
Différences index vs. dépôt — fichiers ajoutés mais non commités : «git
diff --cached»
$ git add factoriel.rb
$ git status
On branch master
Changes to be committed:
(use "git reset HEAD <file>..." to unstage)
modified: factoriel.rb
$ git diff
def fact_seq_lineaire( n )
if n == 0
Aperçu de git 756
modified: factoriel.rb
modified: factoriel.rb
$ git diff
diff --git a/factoriel.rb b/factoriel.rb
index 7ba6e02..9b6e7e2 100644
--- a/factoriel.rb
+++ b/factoriel.rb
@@ -1,6 +1,9 @@
require ’pruby’
def fact_seq_lineaire( n )
if n == 0
+#
+# Ecrit par Guy Tremblay, 2015.
+#
def fact_seq_lineaire( n )
if n == 0
def fact_seq_lineaire( n )
if n == 0
def fact_seq_lineaire( n )
if n == 0
def fact_seq_lineaire( n )
if n == 0
.
.
.
$ emacs factoriel.rb
$ git status
# On branch master
# Changes not staged for commit:
# (use "git add <file>..." to update what will be committed)
# (use "git checkout -- <file>..." to discard changes in working directory)
#
# modified: factoriel.rb
#
no changes added to commit (use "git add" and/or "git commit -a")
$ git status
# On branch master
nothing to commit, working directory clean
Pour laisser tomber des modifications ajoutées mais pas encore com-
mitées
$ git status
# On branch master
nothing to commit, working directory clean
$ emacs factoriel.rb
...
$ git add factoriel.rb
$ git status
# On branch master
# Changes to be committed:
# (use "git reset HEAD <file>..." to unstage)
Aperçu de git 760
#
# modified: factoriel.rb
#
$ git status
# On branch master
# Changes not staged for commit:
# (use "git add <file>..." to update what will be committed)
# (use "git checkout -- <file>..." to discard changes in working directory)
#
# modified: factoriel.rb
#
no changes added to commit (use "git add" and/or "git commit -a")
$ git stash
Saved working directory and index state WIP on master: 9cddf4b Ajout d’un commentaire explica
HEAD is now at 9cddf4b Ajout d’un commentaire explicatif
$ git stash list
stash@0: WIP on master: 9cddf4b Ajout d’un commentaire explicatif
You are in ’detached HEAD’ state. You can look around, make experimental
changes and commit them, and you can discard any commits you make in
this state without impacting any branches by performing another checkout.
If you want to create a new branch to retain commits you create, you
Aperçu de git 761
may do so (now or later) by using -b with the checkout command again. Example:
$ git status
# HEAD detached at fd77def
$ git log
commit fd77def4c0e84ef3855035bd6dd3d3645f6b3602
Author: Guy Tremblay <[email protected]>
Date: Sat Sep 5 09:41:33 2015 -0400
• Un dépôt git est une arborescence de commits. Une branche est simplement un
chemin alternatif de la branche principale de l’arborescence — du tronc (trunk ).
• En git, on est toujours sur une branche :le projet principal est simplement la branche
nomméemaster.
• C’est l’opération merge qui permet d’intégrer — de fusionner — une autre branche
dans la branche courante :
– S’il n’y a aucun conflit — il n’y a pas une même ligne qui est modifiée dans
les deux branches — alors il n’y a rien de spécial à faire.
– S’il y a un conflit — une ou plusieurs lignes ont été modifiées dans les
deux branches — alors il faut résoudre le conflit, donc choisir les bonnes
modifications.
Remarque : Le principe est le même pour créer une branche à partir de n’importe quel
autre commit que HEAD.
$ git branch -a
* CORRECTION_BOGUE_CAS_BASE
master
$ emacs factoriel.rb
$ git status
# On branch CORRECTION_BOGUE_CAS_BASE
# Changes not staged for commit:
# (use "git add <file>..." to update what will be committed)
# (use "git checkout -- <file>..." to discard changes in working directory)
#
# modified: factoriel.rb
#
no changes added to commit (use "git add" and/or "git commit -a")
$ git status
# On branch master
nothing to commit, working directory clean
$ git branch -a
* master
• Si vous faites alors git status, vous pourriez obtenir quelque chose comme suit
(projet en C) :
$ git status
# On branch master
# Your branch is ahead of ’origin/master’ by 2 commits.
#
# Untracked files:
# (use "git add <file>..." to include in what will be committed)
#
# foo.o
# a.out
nothing added to commit but untracked files present (use "git add" to track)
C’est tout à fait correct : les fichiers binaires et exécutables générés par le processus
de compilation et d’assemblage du programme n’ont pas à être mis sous le contrôle
du code source. De plus, ce que vous avez dans votre compte est une copie locale du
dépôt (origin/master), auquel vous ne pouvez évidemment pas accéder en mode
écriture!
Aperçu de git 767
• Pour voir les différents commits effectués, vous pouvez utiliser la commande suiv-
ante :
$ git log
• Pour donner un nom symbolique explicite à votre commit, par exemple VERSION_SEQUENTIELLE_OK,
vous pouvez utiliser la commande suivante :
1 Introduction
Ce document présente quelques rappels1 sur les caractéristiques d’un programme bien écrit
— un programme écrit dans un bon style de programmation. Il présente tout d’abord
quelques principes généraux. Il présente ensuite les notions d’abstraction procédurale et
de couplage. Finalement, il présente divers contre-exemples et exemples, exprimés pour
la plupart en Ruby, illustrant concrètement quelques-unes de ces mauvaises, ou bonnes,
caractéristiques.
1
INF3135 ?
769
Style et qualité du code 770
• Rasoir d’Occam3 :
«La perfection est atteinte non pas quand il n’y a plus rien à ajouter, mais
quand il n’y a plus rien à retirer.»
• Citation de C.A.R. Hoare (The Emperor’s Old Clothes, CACM, February 1981) :
• Rule of Simplicity: Design for simplicity; add complexity only where you must.
• Rule of Transparency: Design for visibility to make inspections and debugging easier.
Plus spécifiquement :
Note : Ne pas oublier qu’une méthode Ruby retourne toujours un résultat, même
s’il peut être nil ou être ignoré ⇒
• La méthode doit utiliser tous les paramètres. Si un paramètre n’est pas du tout
utilisé, alors il devrait être supprimé de l’en-tête.
• Les paramètres utilisés pour retourner un code de statut ou un code d’erreur de-
vraient apparaître à la fin de la liste des paramètres.
• Sauf exception, une méthode ne devrait pas avoir plus de sept (7) paramètres.
Style et qualité du code 776
4 La notion de couplage
Le niveau de couplage entre deux unités de programme décrit la force des dépendances
qui existent entre ces unités. Plus le couplage est élevé, plus des changements dans une
unité risquent d’avoir des répercussions sur l’autre unité.
La force du couplage dépend du nombre de connexions entre les unités.
Par exemple, une méthode avec un seul paramètre possède un niveau de couplage plus
faible avec ses clients qu’une méthode qui compte six ou sept paramètres.
La force du couplage dépend aussi de la visibilité et du type des connexions entre les
unités de programme.
Par exemple, un couplage explicite par l’intermédiaire d’arguments est préférable (plus
faible) à un couplage implicite par l’intermédiaire de variables globales (plus fort).
Il existe un certain nombre de formes typiques de couplage entre unités de programme.
Les formes suivantes, qui représentent des niveaux de couplage nul ou faibles, sont consid-
érées acceptables :
• Aucun couplage : les deux unités de programme ne sont aucunement liées entre
elles. Dans ce cas, on peut changer une unité de programme sans que cela n’ait
d’impact sur l’autre.
• Couplage par objets : les deux unités s’échangent des objets (structures de don-
nées complexes mais fonctionnellement cohésives) par l’intermédiaire de paramètres.
• Couplage par variables d’instance : les deux unités sont dans la même classe et
s’échangent de l’information par l’intermédiaire de variables d’instance de la classe.
En conclusion, l’objectif est de minimiser le plus possible le couplage entre deux unités
de programme, de rendre les liens clairs et explicites autant que possible.
Style et qualité du code 777
5 Refactoring
Qu’est-ce que le refactoring ?
Réponse : Lorsqu’on a des tests unitaires et que notre programme exécute avec succès
ces tests!
Style et qualité du code 779
c
end
Mieux — Élimination du code répétitif
def additionner ( a , b )
a , b = b , a if a . size > b . size
c = Array . new ( b . size )
c
end
Style et qualité du code 781
def additionner ( a , b )
n = [ a . size , b . size ]. max
c = Array . new ( n )
(0... n ). each do | i |
additionner_element ( i , a , b , c )
end
c
end
Style et qualité du code 782
def additionner_element ( i , a , b , c )
c [ i ] = element (i , a ) + element (i , b )
end
def additionner ( a , b )
n = [ a . size , b . size ]. max
c = Array . new ( n )
(0... n ). each do | i |
additionner_element ( i , a , b , c )
end
c
end
8
http://en.wikipedia.org/wiki/Coupling_(computer_programming)
Style et qualité du code 783
def additionner ( a , b )
n = [ a . size , b . size ]. max
c = Array . new ( n )
(0... n ). each do | i |
c [ i ] = element (i , a ) + element (i , b )
end
c
end
def additionner ( a , b )
n = [ a . size , b . size ]. max
(0... n ). map do | i |
element (i , a ) + element (i , b )
end
end
Style et qualité du code 784
...
end
joe = Personne . new ( " Joe Bidon " , " ... " ,
Time . new (2000 , 12 , 12) )
puts age ( joe )
Mieux — Couplage de niveau objets (Time)
class Personne
... # Inchangee ...
...
end
joe = Personne . new ( " Joe Bidon " , " ... " ,
Time . new (2000 , 12 , 12) )
class Time
def age
... ( Time . now - self ) ...
end
end
joe = Personne . new ( " Joe Bidon " , " ... " ,
Time . new (2000 , 12 , 12) )
Mauvais — Le cas spécial semble simplement une alternative «comme une autre»
def somme ( a )
if a . nil ?
0
else
a . reduce (0 , :+)
end
end
a . reduce (0 , :+)
end
Style et qualité du code 787
Mieux — Une méthode qui a comme précondition que a n’est pas nil = Principe «Fail
early, fail fast»
def somme ( a )
fail " *** Dans somme : a = nil !? " if a . nil ?
a . reduce (0 , :+)
end
Style et qualité du code 788
Mauvais — Variables déclarées inutilement de façon globale, initialisées sans besoin, nom
inutilement complexe pour une variable d’itération (index)
def trier ( a )
n = a . size
index_min = 0
tmp = a [ i ]
a [ i ] = a [ index_min ]
a [ index_min ] = tmp
end
end
Mieux — Code simple, intervalle avec borne exclusive, variable introduite au point
d’utilisation, garde, instruction simple pour échanger
def trier ( a )
n = a . size
(0... n ). each do | i |
index_min = i
( i +1... n ). each do | j |
index_min = j if a [ j ] < a [ index_min ]
end
a [ index_min ] , a [ i ] = a [ i ] , a [ index_min ]
end
end
Style et qualité du code 789
# Test 2
contenu = [ " abc " , " def " , " ghi " ]
File . open ( " foo . txt " , " w " ) do | fich |
fich . puts contenu
end
assert_equal " 12 foo . txt \ n " , % x { wc -c foo . txt }
FileUtils . rm_f " foo . txt "
Style et qualité du code 790
yield
# Test 1
avec_fichier " foo . txt " , [ " abc " , " def " , " ghi " ] do
assert_equal " 3 foo . txt \ n " , % x { wc -l foo . txt }
assert_equal " 3\ n " , % x { wc -l < foo . txt }
end
# Test 2
avec_fichier " foo . txt " , [ " abc " , " def " , " ghi " ] do
assert_equal " 12 foo . txt \ n " , % x { wc -c foo . txt }
end
Références
[Amd67] G.M. Amdahl. Validity of the single processor approach to achieving large
scale computing capabilities. In Proc. 1967 AFIPS Conf., volume 30, page
483. AFIPS Press, 1967.
[AS85] H. Abelson and G.J. Sussman. Structure and Interpretation of Computer Pro-
grams. The MIT Press, McGraw-Hill Book Co., Cambridge, Ma., 1985.
[BG98] K. Beck and E. Gamma. Test infected: Programmers love writing tests. Java
Report, 3(7):37–50, 1998.
[Bla04] C. Blaess. Scripts sous Linux—Shell Bash, Sed, Awk, Perl, Tcl, Tk, Python,
Ruby. Eyrolles, 2004.
[But14] P. Butcher. Seven Concurrency Models in Seven Weeks: When Threads Un-
ravel. Pragmatic Bookshelf, 2014.
791
Bibliographie 792
[Dix11] P. Dix. Service-Oriented Design with Ruby and Rails. Addison-Wesley Profes-
sional Ruby Series, 2011.
[FLR98] M. Frigo, C.E. Leiserson, and K.H. Randall. The implementation of the Cilk-5
multithreaded language. In PLDI ’98. ACM, 1998.
[HT03] A. Hunt and D. Thomas. Pragmatic Unit Testing In Java with JUnit. The
Pragmatic Bookshelf, 2003.
[KF90] A.H. Karp and H.P Flatt. Measuring parallel processor performance. Com-
munications of The ACM, 33(5):539–543, May 1990.
[KKT01] J. Keller, C. Kessler, and J. Traff. Practical PRAM Programming. John Wiley
& Sons, Inc., 2001.
[MB00] R. Miller and L. Boxer. Algorithms Sequential & Parallel. Prentice-Hall, 2000.
[QA76.9A43M55].
[MPT78] M.D. McIlroy, E.N. Pinson, and B.A. Tague. Unix time-sharing system for-
ward. The Bell System Technical Journal, 57(6–2), 1978.
[MS+ 85] J.R. McGraw, S. Skedzielewski, et al. SISAL: Streams and iteration in a
single assignment language—language reference manual version 1.2. Technical
Report M-146, Lawrence Livermore National Laboratory, 1985.
[MSM05] T.G. Mattson, B.A. Sanders, and B.L. Massingill. Patterns for Parallel Pro-
gramming. Addison-Wesley, 2005.
[Pac97] P.S. Pacheco. Parallel Programming with MPI. Morgan Kaufman Publ., 1997.
[Qui03] M.J. Quinn. Parallel Programming in C with MPI and OpenMP. McGraw-Hill,
2003.
[Rei07] J. Reinders. Intel Threading Building Blocks: Outfitting C++ for Multi-Core
Processor Parallelism. O’Reilly Media, 2007.
[RK03] P.N. Robillard and P. Kruchten. Software Engineering Process with the UP-
EDU. Addison-Wesley, 2003.
[RTH13] S. Ruby, D. Thomas, and D.H. Hansson. Agile Web Development with Rails
4. THe Pragmatic Bookshelf, 2013.
[SMR09] M.J. Sottile, T.G. Mattson, and C.E. Rasmussen. Introduction to Concurrency
in Programming Languages. Chapman and Hall/CRC, 2009.
[ST95] D.B. Skillicorn and D. Talia. Programming Languages for Parallel Processing.
IEEE Computer Society Press, 1995.
[Ste84] G.L. Steele Jr. Common LISP: The Language. Digital Press, 1984.
[Swi08] T. Swicegood. Pragmatic Version Control Using Git. The Pragmatic Book-
shelf, 2008.
[WCS96] L. Wall, T. Christiansen, and R.L. Schwartz. Programming Perl (2nd Edition).
O’Reilly, 1996.