DÉDICACE

Je dédie ce travail avec ma profonde gratitude :

A l’homme de ma vie, mon exemple éternel ? à mon papa Youssef. Aucune dé-
dicace ne saurait exprimer l’amour et le respect que j’ai toujours eu pour vous. Rien
au monde ne vaut les efforts fournis jour et nuit pour mon éducation et mon bien
être. Que dieu vous garde dans son vaste paradis père, je ne vous oublierais jamais...

A ma mère Saloua. Tu représentes pour moi la source de tendresse et l’exemple

du dévouement qui n’a pas cessé de m’encourager et de prier pour moi. Ta prière
et ta bénédiction m’ont été d’un grand secours pour mener à bien mes études. Au-
cune dédicace ne saurait être assez éloquente pour exprimer ce que tu mérites pour
tous les sacrifices que tu n’as cessé de me donner depuis ma naissance, durant mon
enfance et même à l’âge adulte. Tu as fait plus qu’une mère puisse faire pour que
ses enfants suivent le bon chemin dans leur vie et leurs études. Je te dédie ce travail
en témoignage de mon profond amour. Puisse Dieu, le tout puissant, te préserver et
t’accorder la santé, la longue vie et le bonheur.

A Mon cher frère Khalil, les mots ne suffisent guère pour exprimer l’attachement,
l’amour et l’affection que je porte pour TOI. Mon ange gardien dans les moments
les plus délicats de cette vie mystérieuse.
Pour toi et ta petite famille Sawssen, Med Firas et la petite princesse Maram.

Nul de vaut une sœur comme toi ! Toi qui es là pour me rassurer quand j’ai peur
pour me consoler quand je suis triste ! Toi qui me redonne le sourire, ma deuxième
maman que j’aime le plus.
Je t’offre ce travail ma belle Khaoula, toi et et mon frère Marwen.

C’est à toi mon adorable ange Iyed, ma joie, mon petit trésor que tatati dé-
die ce travail pour te dire que tu resteras pour toujours le rayon du soleil qui égaye

i
ma vie. Je t’aime mon bébé et je te souhaite tout le bonheur, la réussite et la sérénité

Même si on a grandi ensemble, on a su forger notre propre personnalité, avant

de suivre notre destin. Nous ne sommes pas d’accord sur tout, mais tellement de
points en commun nous unissent. La vie nous trace des chemins, parfois opposés
qui espacent nos moments ensemble. Mais les joies et les peines partagées, chaque
merveilleux souvenir, passé ou à venir, font que tu auras toujours une place de choix
dans mon cœur.
La vie m’a fait un très beau cadeau en faisant de toi ma sœur... à toi Abir que je
dédie ce travail et à mon cher frère Bilel.

Quand je t’ai connu, j’ai trouvée l’homme de ma vie, mon âme sœur et la lumière
de mon chemin. Ma vie à tes cotés est remplie de belles surprises. Tes sacrifices, ton
soutien moral et matériel, ta gentillesse sans égal, ton profond attachement m’ont
permis d’avancer, d’aimer la vie, d’être plus forte et de t’aimer de tout mon cœur...
Pour mon grand amour, mon cher Achref Arfaoui..
Merci pour ton amour, ton amitié, merci d’être toujours là pour moi, pour me sou-
tenir, m’aider et m’écouter. Que dieu réunisse nos chemins pour un long commun
serein...Que Dieu te protège et te procure joie et bonheur et que notre amour reste
à jamais.
Pour toi et ta famille ARFAOUI ; la plus belle Kawthoura, mon père Kamel,
la petite ange Ikram que Dieu la garde dans son vaste paradis et mon petit frère
Khalilou.

En souvenir de notre sincère et profonde amitié et des moments agréables que

nous avons passés ensemble, je te dédie spécialement ce travail et parce que tu es ma
fidèle amie d’enfance je veux partager ma réussite avec toi, tu resteras ma meilleur
Safa Ouerghi.

A mes chères Ami(e)s Marwen Msehli, Mariem Selmi, Khaoula Achour.

Vous êtes pour moi des frères et sœurs sur qui je peux compter. En témoignage de
l’amitié qui nous uni et des souvenirs de tous les moments que nous avons passés
ensemble.
Je vous dédie ce travail et je vous souhaite une vie pleine de santé et de bonheur.

A tous ceux ou celles qui me sont chers et que j’ai omis involontairement de citer.
A tous mes enseignants tout au long de mes études.
A tous ceux qui ont participé de près ou de loin à la réalisation de ce travail. À tous
ceux qui ont cette pénible tâche de soulager les gens et diminuer leurs souffrances.

ii
 REMERCIMENT

J’adresse mes remerciements à madame Yosr SLAMA, maître assistante à la

Faculté des Sciences de Tunis pour son soutien et sa confiance. Je la remercie aussi
énormément pour avoir toujours répondu à mes questions et pour le savoir qu’elle
m’a transmis ainsi que ses conseils et ses encouragements.

J’aimerais saisir l’opportunité de remercier monsieur Zaher MAHJOUB, pro-

fesseur à la Faculté des Sciences de Tunis, pour son aide et pour avoir été à l’origine
du sujet de ce mastère.

Je remercie également tous les membres du jury de m’avoir honorée en acceptant

de juger ce modeste travail.

J’exprime toutes mes reconnaissances et gratitudes à l’administration et à l’en-

semble du corps enseignant de la Faculté des Sciences de Tunis, et notamment ceux
du Département des Sciences de l’Informatique, pour leurs efforts et leurs compé-
tences.

iii
 TABLE DES MATIÈRES

Introduction Générale 1

1 Concepts de base 4
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Calcul creux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.1 Matrices creuses . . . . . . . . . . . . . . . . . . . . . . . . . 5
[Link] Utilisation des matrices creuses . . . . . . . . . . . . 5
[Link] Structure des matrices creuses . . . . . . . . . . . . 5
[Link] Formats de compression . . . . . . . . . . . . . . . . 8
1.2.2 Programmes Creux . . . . . . . . . . . . . . . . . . . . . . . . 12
[Link] Produit matrice-vecteur creux : PMVC . . . . . . . . 12
[Link] Résolution des systèmes d’équation linéaire . . . . . 13
1.3 Parallélisme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.3.1 Machines parallèles . . . . . . . . . . . . . . . . . . . . . . . . 14
1.3.2 Parallélisation automatique . . . . . . . . . . . . . . . . . . . 15
[Link] Programme polyédrique . . . . . . . . . . . . . . . . 15
[Link] Les étapes de parallélisation automatique . . . . . . 16
[Link] Outils de parallélisation automatique . . . . . . . . . 17
1.3.3 Métrique de performances . . . . . . . . . . . . . . . . . . . . 18
[Link] Temps d’exécution . . . . . . . . . . . . . . . . . . . 18
[Link] Accélération . . . . . . . . . . . . . . . . . . . . . . . 18
[Link] Efficacité . . . . . . . . . . . . . . . . . . . . . . . . 19
1.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2 État de l’art 20
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2 Parallélisation par le modèle polyédrique . . . . . . . . . . . . . . . . 20
2.2.1 Modèle polyédrique de base . . . . . . . . . . . . . . . . . . . 21
2.2.2 Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

iv
TABLE DES MATIÈRES

[Link] Non inversibilité de la matrice de transformation . . 22

[Link] Traitement par instruction . . . . . . . . . . . . . . . 23
[Link] Affinité par morceaux . . . . . . . . . . . . . . . . . 23
2.3 Parallélisation des programmes creux . . . . . . . . . . . . . . . . . . 24
2.3.1 Optimisation du PMVC . . . . . . . . . . . . . . . . . . . . . 24
[Link] Optimisation par par restructuration des données . . 24
[Link] Proposition d’un nouveau format . . . . . . . . . . . 26
[Link] Optimisations spécifiques à des architectures parti-
culières . . . . . . . . . . . . . . . . . . . . . . . . . 27
[Link] Formats hybrides . . . . . . . . . . . . . . . . . . . . 27
2.3.2 Distribution du PMVC sur un SDGE . . . . . . . . . . . . . . 28
[Link] Fragmentation des matrices creuses . . . . . . . . . . 29
[Link] Produit fragment-vecteur . . . . . . . . . . . . . . . 29
2.4 Récapitulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

3 Approches proposées pour CSR 33

3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.3 Algorithme général pour CSR . . . . . . . . . . . . . . . . . . . . . . 35
3.4 Proposition pour le cas des matrices quelconques . . . . . . . . . . . . 35
3.4.1 Approche 1 : Succession de boucles . . . . . . . . . . . . . . . 37
[Link] Principe de base . . . . . . . . . . . . . . . . . . . . 37
[Link] Exemple . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.4.2 Approche 2 : Boucle englobante contenant des gardes . . . . . 39
[Link] Principe de base . . . . . . . . . . . . . . . . . . . . 39
[Link] Exemple . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.5 Matrices creuses particulières . . . . . . . . . . . . . . . . . . . . . . 40
3.5.1 Matrices bandes . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.5.2 Matrices MTA et MTD . . . . . . . . . . . . . . . . . . . . . 42
[Link] Matrices MTA . . . . . . . . . . . . . . . . . . . . . 42
[Link] Matrices MTD . . . . . . . . . . . . . . . . . . . . . 43
3.5.3 Matrices triangulaire par blocs . . . . . . . . . . . . . . . . . . 43
3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

4 Étude Expérimentale 46
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.2 Stratégies d’expérimentations . . . . . . . . . . . . . . . . . . . . . . 46
4.2.1 Les mesures utilisées . . . . . . . . . . . . . . . . . . . . . . . 47
4.2.2 OpenMP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.2.3 Environnement matériel et logiciel . . . . . . . . . . . . . . . 48
4.3 Étude expérimentale sur des matrices quelconques . . . . . . . . . . . 48
4.3.1 Versions séquentiels . . . . . . . . . . . . . . . . . . . . . . . . 48

v
TABLE DES MATIÈRES

[Link] Variation des Te en fonction de Nz . . . . . . . . . . 50

[Link] Variation des Te en fonction de n . . . . . . . . . . . 51
[Link] Variation des Te en fonction de m . . . . . . . . . . . 52
[Link] Comparaison entre Approche 1 et Approche 2 . . . . 52
4.3.2 Versions Parallèles . . . . . . . . . . . . . . . . . . . . . . . . 53
[Link] Version CSR original . . . . . . . . . . . . . . . . . . 53
[Link] Approche proposée (Approche 1) . . . . . . . . . . . 55
[Link] Comparaison entre Approche 1 et version CSR original 56
4.4 Étude expérimentale sur des matrices particulières . . . . . . . . . . 57
4.4.1 Matrices Blocs . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.4.2 Matrices bandes . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.4.3 Matrices MTA/MTD . . . . . . . . . . . . . . . . . . . . . . . 59
4.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

Bibliographie 63

vi
 LISTE DES TABLEAUX

4.1 Te en fonction de m avec n=50 et Nz=1275 . . . . . . . . . . . . . . 50

4.2 Te (en s) du calcul PMVC . . . . . . . . . . . . . . . . . . . . . . . . 50
4.3 Te en fonction de n avec Nz=1275, m=50 . . . . . . . . . . . . . . . . 54
4.4 Te en fonction de n obtenues par approche 1 avec Nz=1275, m=50 . . 55
4.5 Te en fonction de n avec variation du taille de Bloc . . . . . . . . . . 57
4.6 Te en fonction de n, mL et mU . . . . . . . . . . . . . . . . . . . . . 58
4.7 Te en fonction de n . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

vii
 TABLE DES FIGURES

1.1 Exemple d’une matrice creuse . . . . . . . . . . . . . . . . . . . . . . 5

1.2 Exemple d’une matrice triangulaire inférieure . . . . . . . . . . . . . 6
1.3 Exemple d’une matrice bande constante . . . . . . . . . . . . . . . . 6
1.4 Exemple d’une matrice inférieure par bloc . . . . . . . . . . . . . . . 7
1.5 Exemple d’une matrice quelconque . . . . . . . . . . . . . . . . . . . 7
1.6 Format de stockage BND . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.7 Format de stockage MSR . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.8 Format de stockage BSR . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.9 Format de stockage COO . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.10 Format de stockage CSR . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.11 Format de stockage ELL . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.12 Exemple d’un PMVC . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.13 Méthodes directes de résolution des programmes d’équation linéaire . 14
1.14 Accélération en fonction du nombre de processeur . . . . . . . . . . . 18

2.1 Tri des lignes par longueur . . . . . . . . . . . . . . . . . . . . . . . . 25

2.2 CM-CSR stocke la matrice triée par rangée en forme de colonne-ma jor 25
2.3 Stockage selon le format ELLPACK-R . . . . . . . . . . . . . . . . . 26
2.4 Algorithme ELLPACK-R . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.5 COO_S . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.6 Calcul de PMVC sur un système à grand échelle SDGE . . . . . . . . 30

3.1 Shéma explicatif du travail réalisé . . . . . . . . . . . . . . . . . . . . 34

3.2 Exemple d’une matrice creuse quelconque stockée selon le format CSR 36
3.3 Nouvelle format CSR . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.4 Exemple d’une matrice bande stockée selon le format CSR . . . . . . 41
3.5 Exemple d’une MTA stockée selon le CSR . . . . . . . . . . . . . . . 42
3.6 Exemple d’une MTD stockée selon le CSR . . . . . . . . . . . . . . . 43
3.7 Exemple d’une matrice TIB stockée selon le CSR . . . . . . . . . . . 44

viii
TABLE DES FIGURES

4.1 Exemple de deux matrices M1 et M2 de taille n=5 . . . . . . . . . . . 49

4.2 Te en fonction de Nz pour n=500 avec m=10 . . . . . . . . . . . . . . 51
4.3 Te en fonction de n pour Nz=1275 avec m=50 . . . . . . . . . . . . . 51
4.4 Te en fonction de m . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.5 Te en fonction de m . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.6 Te en fonction de n obtenues par CSR original avec Nz=1275, m=50,
th=3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.7 accélération et efficacité en fonction de n . . . . . . . . . . . . . . . . 54
4.8 Te en fonction de n pour Nz=1275 et m=50, th=3 . . . . . . . . . . . 55
4.9 Accélération et efficacité en fonction de n . . . . . . . . . . . . . . . . 56
4.10 Te en fonction de n pour Nz=1275 , m=50 et th=3 . . . . . . . . . . 56
4.11 Te en fonction de n avec Bloc=50, th=4 . . . . . . . . . . . . . . . . 57
4.12 Te en fonction de n avec mL=20, mU=50, th=4 . . . . . . . . . . . . 58
4.13 Te en fonction de n avec th=4 . . . . . . . . . . . . . . . . . . . . . . 59

ix
 INTRODUCTION GÉNÉRALE

Le calculascientifique est un domaine d’intersection des mathématiques, des

sciences deal’ingénieur et de l’informatique. L’informationatraitée en calcul scien-
tifique est constituée de très grands ensembles de points représentant les objets
modélisé[Link] algorithmes implémentent la résolution de ces objets et l’exécution
de ces programmes permet de les transformer, les modifier ou de les reproduire.
Ces objetsasont souvent stockées dansades tableaux multidimensionnels (des ma-
trices) parcourus par des nids de boucles pour leur appliquer les différents traite-
ments. La nature des problèmes modélisés se reflèteadans les valeurs stockées, par
exemple, générer des matrices dite creusesaavec des éléments ne portant pas d’in-
formation (valeurs nulles) mène à une classeade problèmes désignés comme calcul
creux. En opposition, le calcul dense est caractérisé par des tableauxasans valeurs
nulles (ou presque).

Les matricesacreuses nécessite pour des raisons de taille mémoire et de perfor-

mances de calcul d’appliquer un format de stockage desaéléments non nuls unique-
ment. Les techniques de stockage de ces éléments sont généralement par lignes ou par
colonnes comme par exemple (Compressed Sparse Row (CSR), Compressed Sparse
Column Storage (CCS), etc). Ces formats utilisent des tableaux contenant les coor-
données des éléments de la matrice compressée pour pouvoir facilement y accéder.
Les problèmesatraitant des matrices de grandes tailles qui à leurs tour modélisent
un grand nombre de données sont résolu parades programmes écrit sous forme de
nid de boucles imbriqués et la parallélisation de ces programmes permet à la fois
d’avoir des simulations plus rapides et de traiter des données plus grandes.

L’apparition desaarchitectures avec une capacité de parallélisme massif ont conduit

les chercheurs à développer des méthodes automatiques pour produire du code hau-
tement parallèle. Le modèle polyédrique avec sa représentationamathématique très
puissante permet l’optimisation et la parallélisation des programmes particulière-
ment des boucles. Ce modèle est devenu très populaire en raison de sa richesse

1
TABLE DES FIGURES

théorique en mathématique et son interprétation géométrique intuitive. Parmi les

contraintes imposées par ce modèle, c’est l’affinité des bornes de ses boucles. C’est-à-
dire, les programmes pouvant être parallélisés en utilisant le modèle polyédrique sont
des nids de boucles DOadont les bornes de chaque indice de boucle sont des fonc-
tions affines des indices de boucles englobantes et de constantes appelées paramètres
de structure. Mais, dans le cas ouala matrice est creuse, on parle du calcul creux.
les algorithmes permettant la résolution des problèmes appartenant au calcul creux
ont la structure de nids de boucles imbriquées ou les bornes des bouclesasont des
éléments de tableaux. Ils correspondent à des algorithmes creux. Par exemple, dans
la résolution de systèmes linéaires creux, la matrice creuse est souvent multipliée
par un vecteur dense, cette opération dite Produit matrice-vecteur creux(PMVC)
est fréquemment utilisée dans des différents domaines comme l’électromagnétique,
le classement de pages web ou des problèmes de transport et de livraison. Dans ce
cas, le caractère creux nécessite la réadaptation des méthodes connues en séquentiel
pour pouvoir les paralléliser.

C’est dans le cadre de cette problématique que se situe notre travail. Notre contri-
bution consiste à trouver une manière avec laquelle nous pouvons paralléliser facile-
ment des programmes polyédriques creux (PPC) particulièrement le PMVC. Pour ce
faire, Nous proposons dans un premier temps de faire l’état de l’art de ce problème.
Puis, nous choisissons le format de stockage CSR (Compressed Sparse Row) vu qu’il
traite des matrices de structure quelconque. Deux nouvelles approches peuvent être
envisagées pour modifier la structure de l’algorithme PMVC utilisant le CSR, la pre-
mière est une boucle englobant contenant des gardes IF-THEN-ELSE et la deuxième
est une succession de boucles. Par la complexité des programmes (diversité de la
structure des matrices), on ne peut pas espérer automatiser le processus pour toutes
les catégories des matrices quelconques.

Par ailleurs, nous proposons une nouvelle idée de compression de quelques ma-
trices creuses de structures particulières ou dite régulières comme les matrices bande
constante, les matrices bloc et les matrices qu’on a noté MTA ou MTD (voir chapitre
3, section 5). En effet, au lieu d’appliquer sur chaque type de matrice son format
de stockage convenable, nous avons utilisé le CSR et développé pour chaque une
un programme de calcul PMVC qui suit les contraintes du modèle polyédrique. Le
développement des ces nouveaux programmes adaptés au format polyédrique s’est
concrétisé par la mise en œuvre de ces nouvelles approches et la parallélisation de
ces algorithmes est devenu facile. L’utilisation de l’outil de parallélisation OpenMP
nous a permis d’avoir des résultats pertinents.
Le présent mémoire, résumant notre travail, est structuré comme suit :

Le premier chapitre présente quelques définitions, notations et concepts de base

qui introduisent le domaine du calcul creux et qui sont utiles pour la compréhension
du contexte de travail et des chapitres ultérieurs.

2
TABLE DES FIGURES

Dans le deuxième, nous présentons principalement l’état de l’art des travaux sur
la parallélisation automatique par le modèle polyédrique, les extensions de ce modèle
aux transformations affines par instructions et aux transformations par morceaux.
Puis, nous présentons quelque travaux sur la parallélisation des programmes creux
en particulier le PMVC.
Suite à cette étude des principales techniques de parallélisation connues dans la
littérature et la version original du calcul PMVC pour le CSR. Nous proposons dans
la première partie du chapitre trois deux nouvelles approches de transformation d’un
PPC en PP, en particulier l’algorithme PMVC. Nous détaillons ces approches avec
des exemples explicatives. Dans la deuxième partie, nous proposons une nouvelle idée
de stockage des matrices particulières en utilisant un seul format de compression :
le CSR.
Le quatrième chapitre présente les expérimentations effectuées et consiste à com-
parer la performance de nos approches par rapport aux versions originaux dans le
calcul du PMVC en séquentiel comme en parallèle.
Bien évidement, si ce mémoire aaapporté quelques contributions à la transformation
d’un programme PMVC en PP, de nombreux problèmes restent encore à résoudre.
C’est l’objet de la conclusion de les évoquer et d’insister sur les perspectives pro-
metteuses que ce travail a fait surgir.

3
CHAPITRE 1
CONCEPTS DE BASE

1.1 Introduction
Dans ce chapitre introductif, nous présentons un ensemble de définitions, concepts
et notations qui seront adoptés dans le reste du mémoire.
Notre étude se situe dans le cadre de la parallélisation automatique des programmes
polyédrique creux. Ainsi nous commençons dans la section 1.2 par définir le calcul
creux et les notions qui s’y rapportent. Le modèle polyédrique creux, thème princi-
pale de ce mémoire, est basé, comme son nom l’indique sur le modèle polyédrique.
Pour cela, nous consacrons la section 1.3 à la définition du parallélisme basé sur ce
modèle.

1.2 Calcul creux

Dans cette section, nous commençons par définir le calcul creux. Puis, nous pré-
sentons les principales notions se rapportant au calcul creux, nous donnons un aperçu
sur les matricesacreuses avec ses différentes structures, ses domaines d’utilisation et
les formats de compression qui les gèrent.

Definition 1.2.1. L’information traitée enacalcul scientifique est constituée de très

grands ensembles de points représentant les objets modélisésacomme les mailles
ou les points des images. Ainsi, les données sont souvent stockées dans des ta-
bleauxamultidimensionnels parcourus par des nids de boucles à plusieursaniveaux
pour leur appliquer différents traitements.
La nature des problèmesamodélisés se reflète dans les valeurs stockéesadans les ta-
bleaux utilisés. Ainsi, les maillages non structurés, par exemple, génèrent des ta-
bleaux avec des éléments ne portant pas d’information (valeursanulles). Cette classe
de problèmes est désignée comme calculacreux.

4
1.2 Calcul creux

1.2.1 Matrices creuses

Definition 1.2.2. Soit A une matrice réellead’ordre N, si le nombre d’élémentsanon
nuls de A noté NZ est trés petit (NZ=O(N)) alors A est une matrice creuse.
Une matrice estadonc dite creuse (en onglais sparse) si elle admet une grande pro-
portion d’éléments nuls [1].
Exemple 1.2.1. La figure 1.1 si dessous montre un exemple d’une matrice creuse.

Figure 1.1 – Exemple d’une matrice creuse

[Link] Utilisation des matrices creuses

Les matricesacreuses apparaissent dans diverses applications, y compris l’ana-
lyse structurelle,la modélisationastatistique, l’analyse de réseau électrique, l’ima-
gerie médicale, l’exploration de données, la recherchead’information et beaucoup
d’autres mais souvent dans la description desaphénomènes naturels par exemple
une matrice représentantala communication entre différents employés d’une grande
entrepriseaserait creuse si chaqueaemployé ne communique qu’avec uneapetite frac-
tion de tous les autres employés .
Nous citons dans la suite quelques exemples de matrices de structures différentes.

[Link] Structure des matrices creuses

Uneamatrice creuse peut avoir diverses structures selonales emplacements de
ses éléments non nuls. La structure d’une matrice peut être soitarégulière (triangu-
laire, en diagonale, bande constante, etc.) ouairrégulière (appelé aussi générale), par
exempleamatrice bande variable, matrice quelconque, etc.

Matrices régulières
Une matrice creuse est dite de structurearégulière si tous les élémentsanon nuls
au sein de celle-ci sontaregroupés de telle manière qu’ils forment une zone limi-
tée permettant facilementade repérer les éléments. Nous donnons quelque exemple
enarevue dans ce qui suit.

5
1.2 Calcul creux

• Matrice triangulaire On appelle matriceatriangulaire supérieure (respecti-

vement inférieure) une matrice carrée dont tous lesatermes "au-dessous" (respecti-
vement "au-dessus") de laadiagonale principale sont nuls.
La matrice de la figure 1.2 est un exemple d’une matrice triangulaire inférieure :

Figure 1.2 – Exemple d’une matrice triangulaire inférieure

• Matrice Bande constante Une matrice carrée M=(ai,j ) d’ordre n est ap-
pelée ’matrice bande’ si tous les coefficients ai,j non nuls sont situés dans une
bandeadélimitée par desaparallèles à la diagonale principale.
Une telleabande est déterminée par deux entiers mU (diagonal au dessus de la dia-
gonal principale) et mL (diagonal au dessous de la diagonal principale) positifsaou
nuls, tels que laalargeur d’une bande δ=mL+mU+1. La matrice suivante de la figure
1.3 est un exemple d’une matrice bande constante :

Figure 1.3 – Exemple d’une matrice bande constante

• Matrice inférieure par bloc Une matrice inférieure par blocs doit se confor-
mer à une manière cohérente de division des lignes et des colonnes : on groupe les
lignes en " groupes adjacents ", et les colonnes de la même manière.

6
1.2 Calcul creux

La matrice de la figure 1.4 est un exemple d’une matrice inférieure par bloc ou
la valeur du bloc égal à 2.

Figure 1.4 – Exemple d’une matrice inférieure par bloc

Matrices non régulières

Par contre une matrice possède une structure non régulière ou bienairrégulière
si les éléments sont distribués de manière non uniforme dans la matrice.

• Matrice quelconque Une matrice est dite de structureaquelconque si ses

élémentsanon nuls sont distribués d’une manière quelconque.
La matrice de la figure 1.5 est un exemple d’une matrice quelconque :

Figure 1.5 – Exemple d’une matrice quelconque

• Matrice bande variable La forme xbandexvariablexd’une matrice est défi-

nie par les vecteurs u=(ui) et l=(li). Bien que des éléments nuls puissent apparaître
au sein xde la bande variable, la structure non nulle décrite par la bande variable
peut être plusxprécise que celle décrite par une bande constante. Ainsi, les méthodes
manipulant des matrices à bande variable constituent une bonne approche pour ex-
ploiter les éléments nuls dans une matrice.

7
1.2 Calcul creux

[Link] Formats de compression

Des nombreux problèmes numériques aboutit à manipuler une matrice de très
grande taille mais dont la plupart des coefficients sont nuls. Dans ce cas, on consi-
dère un stockage creux (par abus, on parle d’une matrice creuse) qui permet de ne
pas stocker une grande partie des coefficients nuls et de réduire considérablement la
complexité du problème [1].

Il y a une multitudexde formats diversement utilisés, on distingues deux types,

des formats de compressions spécifiques utilisés pour des matrices ayant une struc-
ture particulière et des formats généralistes pour n’importe quel type de matrice.
Citons quelques exemples des deux types de formats :
Format CSC (Compressed Sparse Column).
Format COO (COOrdinate).
Format MSR (Modified Sparse Row).
Format BND (Banded Linpack Format).
Format VBR (Vriable block row.)
Format BSR (Block comressed sparse row).
Format LNK (LiNKed list).
...
Dans ce travail, nous nous intéressons essentiellement au format CSR (Com-
pressed Sparse Row). En effet, c’est un format qui ne pose aucune condition sur la
structure creuse de la matrice et ne permet de stocker que les informations néces-
saires sur la matrice traitée. Probablement, il est le plus connu et les plus utilisé
pour le stockage des matrices creuses.

Formats de compressions spécifiques

• BND (Banded Linpack Format) C’est le mode dexstockage utilisé pour les
matricesxbande constante. Il s’agit de stocker les élémentsxnon nuls de la matrice
bande A dans un tableauxrectangulaire ABD tel que les éléments de la ième ligne
de Axsoient stockés dans la ième ligne de ABD. On a aussi besoin de connaître le
nombre mL de diagonales de la bande au dessous de laxdiagonale principale ainsi que
le nombre mU de diagonales audessus de la diagonale principale. Ainsi, la largeur de
bande de A qui est δ=mL+mU+1 représente le nombrexminimal de colonnesxdans
ABD. On parle dans ce cas de format de compression BND par colonne parce que
les diagonales constituant la bande sont stockées dans ABD colonne par colonne. Il
existe aussi une version BND par ligne consistant à stocker lesxdiagonales ligne par
ligne dans le tableau ABD[1].

8
1.2 Calcul creux

Figure 1.6 – Format de stockage BND

• MSR (Modified Sparse Row) Utilisé pour le stockage des matricesxtriangulaires.

Ne comporte qu’unxtableau A et un tableau d’entier JA. La première position de
A contient les éléments diagonaux de laxmatrice dans l’ordre. La position n+1
de la matrice A n’est pas utilisée, mais peut être utilisé parfois pour transporter
d’autresxinformations concernant laxmatrice. A partir de la position n+2, les élé-
ments non-nuls de A excluant ses élémentsxdiagonaux, sont stockés par ligne. Pour
chaque élément A(k), le JA entier(k) représente l’indice de colonne de la matrice. Les
premières n+1 positions de JA contiennent les pointeurs des débuts de chaquexligne
A et JA, les deux Tableaux de la figure 1.7 montrent un exemple sur lexformat MSR.

Figure 1.7 – Format de stockage MSR

• BSR (Block Compressed Sparse Row) Une autre variante est lexformat
de compression de ligne parxbloc (Block Compressed Sparse Row) qui est utilisé
lorsque la matrice ciblée peut être décomposée en plusieurs sous-matrices. Prenons
la matrice suivante qui peut se diviser en quatre sous-matrices. Le vecteur A liste
chaquexsous-matrice en ordre de ligne, le vecteur JA indique la colonne à laquelle

9
1.2 Calcul creux

chaque sous-matrice est placée dans la nouvelle matrice C et le vecteur IA indique

les indices de ligne de chaque première sous-matrice qui se trouve sur une nouvelle
ligne. De plus, deux paramètres indiquent le nombre de lignes et de colonnes d’un
bloc. La figure 1.8 traite un exemple sur ce format

Figure 1.8 – Format de stockage BSR

Formats de compressions généralistes

• COO (Coordinate) C’est un format de stockagexparticulièrement simple.
Il permet de représenter une matrice creuse sous forme d’une structure de données
composée de trois tableaux : un tableau de réels A contenant tous les éléments non
nuls de la matrice creuse et deux tableaux d’entiers, JA et IA, contenant les indices
de lignes et les indices de colonnes de ces éléments non nuls, respectivement. Les
trois tableaux ont une taille Nz (nombre d’éléments non nuls de la matrice)[2].
La figure 1.9 décrit le format COO pour une matrice creuse quelconque.

Figure 1.9 – Format de stockage COO

• CSR (Compressed Sparce Row) Le format CSRxstocke les lignes de

manière plus efficace. C’est un format qui ne pose aucune condition sur la struc-
turexcreuse de la matrice et ne permet de stocker que les élémentsxnon nuls. Comme
le COO, il représente la matrice sous forme dextrois tableaux de données. Dans les

10
1.2 Calcul creux

deux premiersxtableaux nommés A et JA il stocke respectivement les Nz éléments

non nuls et leurs indices de colonnesxligne par ligne et dans un troisième tableau IA
de taille n + 1, il stocke la position du premier élément non nul de chaque ligne de
la matrice [2].

L’exemple de la figure 1.10 montre un stockage d’une matrice creuse quelconque

selon le format CSR.

Figure 1.10 – Format de stockage CSR

• ELL (ELLPACK/ITPACK) ELLPACK/ITPACK, ou plus couramment

ELL, est parmi les structures de données les plus génériques pour le stockage des
matrices creuses. De plus, il est plus particulièrement adapté à la représentation
des matrices, plus ou moins structurées. Le stockage en format ELL d’une matrice
creuse, ayant au maximum m éléments non nuls par ligne, utilise deux matrices de
données de taille (n × m) : une matrice de réels Val, et une matrice d’entiers Col.
Une ligne d’indice i de chacune des matrices Val et Col correspond aux éléments non
nuls et leurs indices de colonne respectivement de la ligne d’indice i de la matrice
d’ntrée. Les lignes qui ont moins de m éléments non nuls dans la matrice creuse A
sont complétées par des zéros dans les matrices Val et Col [3]. La figure 1.11 montre
un stockage ELL d’une matrice creuse.

11
1.2 Calcul creux

Figure 1.11 – Format de stockage ELL

1.2.2 Programmes Creux

Les programmesxcreux aboutissent à la résolution de problèmesxmatriciels né-
cessitant l’utilisation d’unexmatrice des matrices dont la plupart des éléments sont
nuls et la distribution ces éléments au sein de la matrice d’entrée définit sa structure
[1]. Ils permettent la résolution des nombreux problèmesxcomplexes dans différents
domaines, tels que la biologie, la finance, la physique ou le traitement d’image/signal.
En outre, vu à travers l’étudexbibliographique effectuée, que plusieursxapplications
scientifiques effectuent des calculs sur des matrices de grandes tailles. Nous avons
constaté à travers cesxapplications que les calculs scientifiquesxcreux se ramènent
souvent à des problèmes d’algèbre linéaire, c’est à dire à la résolution de systèmes
linéaires et au calcul des valeurs (et de vecteurs) propres.

[Link] Produit matrice-vecteur creux : PMVC

L’opération PMVC est un exemple d’un programme polyédriquexcreux. C’est
une opération primordialexdans l’ingénierie et l’informatiquexscientifique et, par
conséquent, a été un sujet de recherchexintense pour longtemps. Elle est représentée
par l’équation y=Ax ; où x et y représentent des vecteurs et A une matricexcreuse.
Pour l’effectuer, il faut diviser le problème sur chaque ligne de la matrice creuse,
créant des équations indépendantes (1.1) .
D’abord, il faut multiplier chaquexvaleur non nul d’une même ligne avec un élément
du vecteur se trouvant au même indice dexcolonne. Puis, il faut accumuler ces ré-
sultats dans le vecteur résultat à l’indice de la ligne en question.
M
X
y[i] = A[i, j]x[j] (1.1)
j=0

La multiplicationxentre une matrice creuse et un vecteur est un problème qui com-

porte une faible proportion de calculs par rapport au nombre d’accès à laxmémoire.
Pour chaque opérationxde multiplication-accumulation, pour des valeurs i et j fixes

12
1.2 Calcul creux

représentant un élément non nul, il faut lire l’élément (i,j) de la matrice A, l’élément
j du vecteur x et écrire à l’élément i du vecteur y (Figure 1.12). Nous avons donc
trois accèsxmémoire pour une opérationxarithmétique.

Figure 1.12 – Exemple d’un PMVC

Remarque 1.2.1. Le travail de ce mémoire est basé sur le programme polyédrique

creux PMVC utilisant le format de stockage CSR.

[Link] Résolution des systèmes d’équation linéaire

La résolution de systèmesxlinéaires a toujours joué un rôleximportant dans la si-
mulation numérique de nombreux problèmesxscientifiques et industriels Un système
de m équations linéaires à n inconnues peut être écrit sous la forme suivante :


 a1,1 x1 + a1,2 x2 + ... + a1,n xn = b1 (1)
 a2,1 x1 + a2,2 x2 + ... + a2,n xn = b2 (2)




. (1.2)

.




m (4)

a x + a x + ... + a x = b
m,m 1 m,2 2 m,n n

Il se définit par la donnée d’une matrice A∈ RN ×N et un vecteur b∈ RN . Il s’agit

de déterminer x∈ RN vérifiant Ax=b.
    
a1,1 a1,2 ... a1,n x1 b1
 a2,1 a2,2 ... a2,n   x2   b2 
    
 .  .  =  . 
    
 .  .   . 
am,m am,2 ... am,n xn bm

Pour résoudre un système d’équationxlinéaire on distingue deuxxclasses de mé-

thodes de résolution : les méthodes directes et les méthodesxitératives, le choix entre
les deux dépend de la structure ainsi que de la taille de la matrice.
En utilisant lesxméthodes directes, on passe par des programmesxcreux. En effet,

13
1.3 Parallélisme

l’idée de base des méthodes directes est de transformer le système d’équations li-
néaires initial Ax = b, en un système équivalent, noté Tx=c, plus facile à résoudre.
Selon la méthode choisie, la matrice T obtenue est soit triangulaire (méthode d’éli-
mination de Gauss soit sous la forme du produit de deux matrices : la première
est triangulaire inférieure et la seconde triangulaire supérieure (factorisation LU) ou
bien factorisation de Cholesky (Figure 1.13). [1].

Figure 1.13 – Méthodes directes de résolution des programmes d’équation linéaire

1.3 Parallélisme
Lexparallélisme est un forme de traitementxinformatique qui permet l’exécu-
tionxsimultané des instructions indépendantes, il existe deux types de parallélisme :
Parallélisationxmanuelle (explicite) : Appliquéexmanuellement et assez pénible, vu
la complexité des transformationsxdes programmes en jeu et peut fiable à cause des
risques d’erreurs qu’elle peut engendre.
Parallélisationxautomatique (implicite) : A travers des méthodesxautomatiques trans-
formant les programmes séquentiels en programmesxparallèles. Dans ce mémoire,
nous nous plaçons dans le cadre précis de la parallélisationxautomatique.

1.3.1 Machines parallèles

Une machine parallèle est essentiellement un ensemble dexprocesseurs qui co-
opèrent etxcommuniquent. Nous désirons uniquement donner une idée brève sur les
différentes types des machines parallèles.

14
1.3 Parallélisme

Commençant par lesxmachines à mémoire partagée (MP), qui utilisent une mé-
moirexglobale commune accédée par tous lesxprocesseurs. Passant ensuite aux ma-
chines à mémoire distribuée (MD), où chaque processeur dispose de sa mémoire
locale et la communication entre les processeurs se fait à travers un réseau d’inter-
connexion [2].
Le troisième type des machinesxparallèles c’est les machines à mémoirexdistribuée-
partagée (MP-D) pour combiner l’avantage de rapidité de communication des MP et
le nombre élevé des processeurs des MD. D’autre part, avec l’évolutionxtechnologique
desxmicroprocesseurs, on voit naître de nouvelles architectures massivementxmulti-
cœurs. L’intérêt essentiel ou la force des solutions multi-cœurs est de permettre l’exé-
cution simultanée d’une tâche par cœur. Certains algorithmes massivementxparallèles
peuvent tirer pleinement profit de ces nouvellesxarchitectures.

1.3.2 Parallélisation automatique

La parallélisationxautomatique décrit une démarche de réordonnancement des
structures itératives permettant dexsélectionner les traitements pouvant êtrexexécutés
dans le même espacextemporelle pour améliorer le tempsxd’exécution ou autre cri-
tères que nous enxpassons certaines en revue dans ce qui suit.
Definition 1.3.1. La parallélisation automatique est la technique permettant de
transformer automatiquement (i.e. à l’aide d’outils appelés compilateurs paralléli-
seurs) un programme séquentiel en un programme à parallélisme explicite équivalent.
Cette parallélisation consiste à faire subir au programme source une série de trans-
formations légales, dans le sens ou elles préservent la sémantique du programmes
[4].
Remarque 1.3.1. On vise particulièrement au type de programmes qui sont les nids
de boucles (polyédrique).

[Link] Programme polyédrique

Le modèle polyédrique a étéxconçu depuis longtemps pour définir un cadrexthéorique
de parallélisationxautomatique basé sur la notion de polyèdre, ce modèle de calcul
fournit desxabstractions pratiques pour raisonner et appliquer desxprogrammes, il
est devenu très populaire en raison de sa richessexthéorique en mathématique et son
interprétationxgéométrique.
Definition 1.3.2. Un programme polyédrique(PP) est un nid de boucles dont les
bornes sont des fonctions affines des indices de boucles englobantes et des constantes
appelées paramètres de structures. Ce modèle permet la représentation des espaces
d’itérations par des polyèdres et permet par calcul polyédrique de calculer un grand
nombre d’information concernant ses programmes comme l’expression de dépendance
de données, les calculs d’ordonnancement et de placement des tâches parallèles, des
optimisations de génération de code, etc.

15
1.3 Parallélisme

Le programme suivant est un exemple d’un programme polyédrique, avec l1 , u1

sont des constantes et lq , uq sont des fonctions affines de i1 , i2 ...iq−1 (2<q ≤ n) :

Algorithm 1 Exemple d’un programme polyédrique

for i1 =l1 ,u1 do
for i2 =l2 ,u2 do
.
.
S(i,k)
.
.
end for
end for

Remarque 1.3.2. Le programme précédent est un nid de boucle parfait où touts les
instructions sont dans la boucle la plus interne. Notons qu’un PP peut aussi être
non parfait.

[Link] Les étapes de parallélisation automatique

Les étapes de parallélisationxautomatique se résument comme suit : Le compila-
teur, dans la première étape, cherche a analyserxles dépendances entre les itérations
dans le programmexsource. La deuxième étape consiste à détecter le parallélisme
dans le programme et déterminer unextransformation à celui-ci. Enfin, la dernière
étape est laxgénération du codexparallèle.

Analyse de dépendance
L’analyse dexdépendance dans un programme est une phase très importante dans
lexprocessus de saxparallélisation, car son résultat influexdirectement sur la réussite
des phases de la parallélisation. Elle consiste à déterminer l’existence possible des
conflits (ou de collisions) lors de l’exécutionxsimultanée de deux opérations, dites
dans ce cas opérations dépendantes.
On distingue entre unexdépendance inter-instancesxd’instructions et dépendance
inter-instructions. En effet, une dépendance entre deux instructions S1 et S2 est
engendrées par l’existence dexdépendance entre une instance de S1 et une instance
S2 .

Transformation
La deuxième étape de la parallélisationxautomatique est la détection du paral-
lélisme et la recherche d’unextransformation valide i.e qui n’en change pas le ré-
sultat d’exécution, l’adaptant à l’architecture parallèlexvisée. Comme exemple dex

16
1.3 Parallélisme

transformation, nous citons : la permutation, laxtorsion, laxfusion, laxdistribution,

l’éclatement de boucles, etc. Le modèlexpolyédrique a été conçu en vue de fournir
un formalisme mathématique adéquat permettant de standardiser le traitement des
différentesxtransformations.

Génération du code parallèle

Nous nous intéressons ici au modèle polyédrique, à la manière de la transfor-
mation du polytope source afin d’aboutir au programmexparallèle requis. Dans le
cas d’un nid parfait, après l’analyse de dépendance, la génération des boucles pa-
rallèles se fait à partir de laxtransformation et de programme original. Cette étape
consiste à construire le programmexparallèle ayant comme espace d’itération le po-
lytopexdestination.

[Link] Outils de parallélisation automatique

La parallélisation automatique consiste à adapter un programme écrit pour une
machine séquentielle (qui n’a qu’un processeur) à une machine parallèle. Plusieurs
outils ont été utilisés. Nous citons dans ce qui suit quelques outils de parallélisation
automatique utilisant les programmes polyédriques.

Cloog
Cloog signifie Chunky Loop Generator, est un générateur de codexpolyédrique,
il a été écrit à l’origine pourxrésoudre le problème dexgénération de code pour op-
timiser les compilateurs basés sur le modèle polytope , il est conçu aussi pour être
le back-end des paralléliseurs automatique.
Le professeurxCedric Bastoul est le créateur de Cloog, sesxintérêts de recherche sont
dans les techniques de compilateur pour l’ optimisation et parallélisation avec un
fort accent sur laxrestructuration du code à l’ aide du modèlexpolyédrique.
CLooG est un logiciel et unexbibliothèque pour générer du code, c’est-à-dire, il
trouve un code (par exemple dans C, FORTRAN...) qui atteint chaque pointxintégral
d’un ou plusieurs polyèdres paramétrés.
CLooG est un logiciel et une bibliothèque, il a été écrit à l’origine pour résoudre le
problème de génération de code pour optimiser lesxcompilateurs basés sur le modèle
polytope. Néanmoins, il est utilisé maintenant dans diverses zones, Pour construire
desxautomates dexcontrôle pour une synthèse de haut niveau ou pour trouver la
meilleure approximation polynomiale d’une fonction. CLooG est conçu pour éviter
les frais généraux de contrôle et de produire un code très efficace.

17
1.3 Parallélisme

PLUTO
PLUTO est un outil de parallélisationxautomatique basé sur le modèle poly-
édrique, il transforme les programmesxC de source en source pour le parallélisme
et la localité à grain grossierxsimultanément. Le cadre de transformation de base
travaille principalement en trouvant desxtransformations affines pour un carrelage
et une fusion efficaces, mais sans s’y limiter.

1.3.3 Métrique de performances

Une fois le programme estxparallélisé, plusieurs travaux de recherche utilisent
des métriques pour mesurer saxperformance par rapport au programmexséquentiel
tel que le tempsxd’exécution, l’efficacité et l’accélération.

[Link] Temps d’exécution

Un algorithme peut être considéré comme une fonction de transfert de don-
nées, à laquelle est associé un retard équivalent au temps de calcul, c’est le temps
d’exécution[5].

[Link] Accélération
Ce terme estxproportionnel au tempsxd’exécution sur des architecturesxparallèles.
Il représente le rapport entre le travail de l’algorithme W(n), Avec n est la taille des
données, et le tempsxd’exécution sur p processeurs T(n,p).
alors l’accélération (Speed - Up) est le rapport tel que indiqués dans l’équation
suivante :

W (n)
S(n) = (1.3)
T (n, p)
Théoriquement le temps d’exécution diminue en fonction du nombre dexprocesseurs,
donc comme nous montre la figure 1.14, l’accélération est une application linéaire
en fonction du nombre de processeur.

Figure 1.14 – Accélération en fonction du nombre de processeur

18
1.4 Conclusion

[Link] Efficacité
C’est un mesure de "rendement" du calculxparallèle, en théorie c’est un nombre
compris entre 0 et 1 : E(p)= S(p)/p , si E=1 alors touts les processeurs ont été
utilisés donc l’efficacité nous indique dans quelle mesure les diversxprocesseurs sont
utilisés ou non.

1.4 Conclusion
Dans ce chapitre, nous avons passé en revue lesxprincipales notions liées au
calcul creux et les notions s’y rapportant. Ensuite, nous avons donnés unxaperçu
et le parallélismexparticulièrement la parallélisationxautomatique dans sa généra-
lité. La notion du modèlexpolyédrique a été aussi définie et expliquées, en vue
de faciliter la compréhension du prochain chapitre, dans lequel nous ferons une
étudexdétaillé du modèle polyédrique de parallélisationxautomatique et de modèle
polyédriquesxcreux.

19
CHAPITRE 2
ÉTAT DE L’ART

2.1 Introduction
Le parallélisme donne des résultats plusxsignificatifs dans le cas où les algo-
rithmes présentent une forme de régularité dans le traitement des étapes dexcalculs
et dans les structures de données (nids de boucles affines). Cette régularité est ex-
ploitée dans les outils dexparallélisation tels que les compilateursxparalléliseurs ou
dans les compilateurs de langages à parallélismeximplicite. Lorsqu’il apparaît des
irrégularités dans le traitement des calculs et dans les rangementsxdes données (non
affinité des bornes des boucles), l’inconvénient est que le parallélisme devient difficile
à exploité. Ceci estxnotamment le cas lorsque on parle des programmes polyédriques
creux (PPC).
Les programmes polyédriquesxcreux, particulièrement le programme PMVC en tant
qu’un ensemble de boucles imbriquées a fait l’objet de nombreuses études.
Ce chapitre situe le contexte de notre travail par rapport aux travaux existants :
la modification ou la transformation du PMVC en programme polyédrique (PP)
pour le parallélisé. Pour ce faire, nous avons étudié d’abord la parallélisation auto-
matique par le modèle polyédrique en donnant un aperçu sur les extensions de ce
modèle. Puis, nous avons présenté quelques solutions réalisés pour l’optimisation ou
la parallélisation de ce programme.

2.2 Parallélisation par le modèle polyédrique

L’exploitation efficace des machines parallèles, i.e. la manière d’écrire les pro-
grammes qu’elles ont appelées à exécuter, représente un problème majeur qui nette-
ment retenu l’attention des chercheurs et la retient encore. L’idéal serait de concevoir
de nouveaux algorithmes dédiés aux systèmes parallèles. Mas il s’avère que cette ap-
proche est complexe et peu pratique du fait que les concepteurs d’algorithmes n’ont

20
2.2 Parallélisation par le modèle polyédrique

pu se débarrasser de la tournure d’esprit "séquentiel" qui les accompagnés depuis

longtemps. Une approche plus réaliste consiste à transformer les algorithmes séquen-
tiels existants en algorithmes exécutables efficacement sur les machines parallèles.

2.2.1 Modèle polyédrique de base

La parallélisation par le modèlexpolyédrique de base [6][7] consiste à déterminer
l’espace d’itération du programmexséquentiel source écrit sous forme d’un système
d’inéquationsxlinéaires. La deuxième étape est l’application d’unextransformation
de parallélisation sur le polytope source donnant lieu au polytope destination. La
troisième étape est la paralllélisation du programme destination. Nous détaillons
ci-dessous les trois étapes qui fontxaboutir au programmedestination à partir du
programme source.
1. Détermination du polytope source
Le polytope sourcexreprésente l’espace d’itération du programme source. Le construire
revient à écrire le système d’inéquation que vérifiant lesxindices de boucles. C’est un
système de 2n inéquations linéaires se notant Ax≤b est construite en deux étapes
comme suit :

— La partiexsupérieure de A déterminée à partir des bornes inférieures des

indice.
— La partiexinférieure de A est déterminée à partir des bornesxsupérieures des
indices.
On notera (A,b) le plytope défini par Ax≤b.
2. Détermination du polytope destination
La détermination du polytope destination est l’étape la plus délicate du modèle
polyédrique. Elle consiste, àxsegmenter le polytope source, dont on dispose, en
des intervalles de temps, i.e. des ensembles d’itérations qui peuvent être exécu-
tésxsimultanément. Cette segmentation peut être formulée comme une transforma-
tion affine du polytope source, préservant les dépendances de données etxvérifiant
un ou plusieurs critères d’efficacité. Un exemple typique est la minimisation du
temps d’exécution. Une fois déterminée, la transformation sera appliquée au poly-
topexsource donnant lieu à un nouveau polytope appelé polytope destination.

Transformation
Le modèle polyédrique en lui-mêmexn’impose pas de transformation particulière. En
effet, il peut être considéré comme une sorte de plate forme sur laquelle peuvent se
freffer plusieurs techniques da parallélisation, à condition que leurs résultats soient
des transformations affines, afin d’être représentées par des matrices.

21
2.2 Parallélisation par le modèle polyédrique

Polytope transformé
La transformation étant déterminée, il ne reste plus qu’a l’appliquer au polytope
source.
Soit y le vecteur des indices transformé : y = Tx.
T étant inversible, on peut écrire x = T−1 y.
Le système d’inéquation linéaires définissant le polytope source Ax ≤ b peut donc
s’écrire (AT−1 ) y ≤ b).
Ainsi, le polytope destination se note (AT−1 , b).
Ce polytope transformé contient les même points que le polytope source, mais il est
défini dans un nouveau système ordonné.
3. Détermination du programme destination
Cette dernière étape consiste à retransformer le polytope destination en un pro-
gramme contenant des boucles.
Le programme destination contient des boucles séquentiels et d’autres parallèles.

2.2.2 Extensions
Le modèle polyédrique de base, comme il a été défini dans la section 2.2.1, exige
des contraintes assez fortes sur les transformations qu’il traite. Celles-ci doivent être
effectivement affines et inversibles. Étendre le modèle polyédrique à une plus grande
classe de transformation a suscité l’intérêt des chercheurs depuis son apparition [7].

[Link] Non inversibilité de la matrice de transformation

Dans [6],[8], sont proposées deux méthodes de traitement des matrices de trans-
formation arbitraires, i.e. non nécessairement carrées ou inversibles. Nous passons
brièvement en revue le principe de la méthode exposée dans [8].
Ayant une matrice de transformation T quelconque, non inversible, on la traite en
passant par les quatre étapes suivantes :
1. Éliminer les lignes linéairement dépendantes :
En parcourantxles lignes de la matrice T de haut en bas, on supprime celles qui
sont linéairement dépendantes des précédentes. La matrice obtenue est notée T’.
Les lignes éliminées sont sauvegardées ainsi que leurs numéros pour un traitement
ultérieur.
2. Étendre la matrice en une matrice carrée inversible :
La matrice T’, résultat de l’étape 1, a un rang non nul, mais elle n’est pas nécessai-
rement carrée : le nombre de sas lignes est inférieur ou égal à celui de ses colonnes.
Pour obtenir une matrice carrée inversible, on ajoute en bas de T’ des valeurs uni-
taires linéairement indépendants chacun une dimension manquante. La matrice car-
rée obtenus est notée T”.

22
2.2 Parallélisation par le modèle polyédrique

2. Générer le code parallèle en utilisant la matrice modifiée :

Étant inversible, la matrice T” obtenue est utilisée pour transformer le polytope
source en un polytope destination et générer le code parallèle comme cela a été
exposé dans la section 2.2.1 dans le cadre de modèle polyédrique de base.
4. Insérer le code correspondant aux lignes éliminées :
Dans le programme destination obtenu, on insère autant de boucles qu’on a éliminé
de lignes à l’étape 1. La boucle Bi d’indice yi , correspondant à la ligne li dans la
matrice originale T, est insérée à la position i du nid destination.

[Link] Traitement par instruction

On appelle transformation affine par instruction une transformation qui associe
une expression affine à chaque instruction du programme source. Vu que telles trans-
formations sont capables, dans la plupart des cas, d’exprimer plus de parallélisme
que les transformation affines, il a été intéressant d’étendre le modèle polyédrique
pour supporter ce traitement par instruction. La méthode adoptée est simple. Cette
extension est représentée dans [9], [8]. Nous la résumons par les étapes suivante :

[Link] le programme source en un ensemble de programmes contenant chacun

une seule instruction. Ces programmes qu’on appelle parties programmes source ont
le même espace d’itération (même nid de boucles) que le programme original.

2. Traiter chaque partie programme source dans le cadre du modèle polyédrique

de base. Ceci est possible puisque la transformation dont on dispose associe une
expression affine à chaque instruction. Les programmes générés sont appelés parties
programmes destination.

3. Fusionner les parties programmes destination en vue d’obtenir le programme

destination final.

[Link] Affinité par morceaux

Le traitement de ces transformationsxest identique au traitement par instruction.
La seule différence consiste en la manière de diviser le programme à paralléliser en
des partiesxprogrammes source. Si la transformation a k expressions différentes sur
l’espace d’itération, le programmexsource sera divisé en k parties programmes, cha-
cune représentant un morceau de l’espace d’itération. Sur chaque partie programme,
on a une transformation affine.
L’élaboration du modèlexpolyédrique présente au apport considérable dans le
domaine de la parallélisation automatique. Son principal point fort est sa théo-
rie mathématique riche, lui permettant de quantifier la préservation de la validité
desxtransformations. Un autre avantage de ce modèle est son interprétation géomé-
trique intuitive facilitant son utilisation et sa manipulation.

23
2.3 Parallélisation des programmes creux

2.3 Parallélisation des programmes creux

Notre objectif dans ce chapitre est d’étudier les programmesxcreux, notam-
ment Les programmes polyédriques creux, ils présentent deux caractéristiques fon-
damentales. D’une part, les objetsxqu’elles manipulent sont des matrices creuses
ou desxvecteurs. D’autre part, le traitement des calculs est mis en œuvre par des
boucles imbriquées dont les bornes ne sont pas affines.
Dans ce travail, on s’intéresse au programme produit matrice-vecteur creux (PMVC).
Cette opération est importante dans plusieurs domaines et à cause de la nature
creuse de la matrice, on utilise des formats de stockages permettant de résoudre
les problèmes d’accès non consécutifs [10]. Parfois, l’utilisation de ces formats in-
troduisent des difficultés supplémentaires sur l’écriture des bornes des boucles (non
affines) et la parallélisation de ces boucles nécessite une réadaptation des programme
originaux.

2.3.1 Optimisation du PMVC

Nous étudions ici quelques versions d’optimisation du programme PMVC in-
dépendamment de la structure de la matrice traitée, du format de stockage, des
structures de données utilisées pour ce format ainsi que de l’architecture cible.

[Link] Optimisation par par restructuration des données

Plusieurs travaux proposent l’optimisation du PMVC de restructurer la matrice
(permutations de lignes et/ ou de colonnes) en utilisant la stratégie la méthode
Glouton pour la structuration en blocs. Il a été montré expérimentalement [11] que
par rapport à la structure quelconque, une structure régulière et/ou par bloc de la
matrice creuse permet de réduire les défauts de cache et améliorer les performances
du PMVC [12].
Plusieurs chercheurs se sont intéressés par la conception des formats appropriés
pour le stockage des matrices creuses. Nous expliquons dans la suite quelques ap-
proches traitant cette solution.

Approche de White et Sadayappan

White et Sadayappan ontxobservé que l’emplacement des données en mémoire
cause des problèmes à l’algorithme de PMVC. Dans leur article [13], ils ont intéressé
par l’accessibilitéxdes éléments du vecteur x qui dépend entièrement de la structure
des éléments non nuls dans la matrice. En effet, les matrices CSR peuvent avoir
d’une part des lignes de longueur variable et cette variabilité rend lexdéroulement
de la bande externe presque impossible et un surcharge sur la boucle intérieure et
d’autre part, ils peuvent aussi avoir des lignesxcontenant un nombre d’éléments non
nuls très petit de tel sorte la boucle intérieure ne s’exécute que sur quelques itéra-
tions, ce petit nombre d’itérations peut marginaliser les avantage de déroulement de

24
2.3 Parallélisation des programmes creux

cette boucle.
Ils ont donc proposé de paralléliserxl’algorithme en augmentant le nombre des ins-
tructions de calcul par déroulement de boucle tout en évitant d’empirer la localité
des éléments en mémoire selon deux étape :
La première étape consiste à réarranger la matrice en fonction de la longueur pour
obtenir une matrice résultante avec des lignes de longueurxégale. La figure 2.1 pré-
sente un exemple d’une matrice réarrangée.

Figure 2.1 – Tri des lignes par longueur

La deuxième étape est le stockage de la matrice réordonnée sous une forme qui
facilite le déroulement des boucles, ce stockage est appélé Column-Mjor CSR (CM-
CSR), ou les lignes sont compressées et le tableau IA qui stocke le début de chaque
ligne dans le CSR d’origine stocke plutôt le début de chaque colonne dans ce format.
La figure 2.2
Les résultats ont démontré que le format BSR performe mieux en termes du nombre

Figure 2.2 – CM-CSR stocke la matrice triée par rangée en forme de colonne-ma
jor

d’opérations à la seconde comparé au format CSC et à une version compressée par

bloc de ce dernier. Le format de compression par bloc du format CSC a toutefois
surpassé les performances du format BSR lorsque les matrices avaient plusieurs lignes
ayant peu d’éléments non nuls.

25
2.3 Parallélisation des programmes creux

[Link] Proposition d’un nouveau format

Dans certains travaux, pour optimiser le PMVC, les auteurs se trouvent obligés
de proposer un nouveau format de stockage (i.e. différent du format original) [14].
Ainsi, dans [15] l’optimisation est effectuée grâce à l’utilisation du format BCSR
(Block CSR), une variante du format CSR, qui assure une certaine localité des
données. L’idée derrière ce format est d’exploiter les éléments non nuls se trouvant
dans des positions contiguës en les empaquetant dans des blocs de tailles différentes.
Connaissant l’indice de colonne du premier élément non nul dans un bloc, on peut
déduire les indices de colonne de tous les autres éléments non nuls du même bloc. En
d’autres termes, un seul accès indirect est nécessaire pour chaque bloc. Le format
BCSR utilise un tableau 1-D (de longueur égale au nombre de blocs) supplémentaire
en plus des trois tableaux utilisés par le format CSR.
Le principe format CSR-VI consiste à compresser le vecteur A qui contient les
éléments non nuls de la matrice en profitant de l’éventuelle redondance des valeurs
non nulles. A la place de A, le format CSR-VI utilise deux vecteurs vals_unique et
val _ind. Le premier contient les valeurs non nulles distinctes de la matrice et le
second contient, pour chaque élément non nul de la matrice, l’indice de sa valeur
dans vals_unique.

Approche de Vazquez et al.

Plusieurs auteurs ont proposé de créer un autre format de compression pour
accélérer l’algorithme de multiplication entre une matrice creuse et un vecteur. C’est
le cas de Vázquez et al [17]. Ils ont proposé le format ELLPACK-R, ce format est
identique au format ELL sauf qu’ils ont ajouté unxvecteur Max pour stocker les
tailles de chaque ligne de la matrice. Ceci permet alors de tirer avantage du format
ELL, qui offre de meilleures performances que le format usuel CSR dans plusieurs
cas, sans perdre de temps sur les éléments nuls qui se trouvent dans les matrices.
La figure 2.3 présente un stockage d’une matrice de structure quelconque selon le
format ELLPACK-R.

Figure 2.3 – Stockage selon le format ELLPACK-R

26
2.3 Parallélisation des programmes creux

L’algorithme présentant ce format est indiqué dans la figure 2.4.

Figure 2.4 – Algorithme ELLPACK-R

[Link] Optimisations spécifiques à des architectures particulières

D’autres optimisations telles que celles proposées dans [18][19] dépendent de l’ar-
chitecture de la machine cible. Ainsi, dans [18] et [20] sont étudiées des optimisations
qui dépendent des tailles de la mémoire cache et du registre mémoire. Les deux tra-
vaux décrivent un système appelé Sparsity qui, étant données les performances d’une
machine et les caractéristiques de la matrice creuse, peut déterminer une estimation
de la taille optimale du bloc pour la décomposition de la matrice creuse. Nous rele-
vons de même dans [19] une étude d’optimisation du PMVC pour des plateformes
multi-coeurs. Il se trouve que sur ce type d’architecture, l’optimisation peut être
assurée par l’utilisation du parallélisme de threads. La matrice creuse est ainsi par-
titionnée en blocs. Chaque bloc est traité par un thread. Les threads sont traités en
parallèle par les différents cœurs de la machine. Un travail d’équilibrage des charges
entre les blocs de la matrice est nécessaire pour avoir de bonnes performances [20]
[18].

[Link] Formats hybrides

Le parallélisme correspond auxdécoupage de la matricexcreuse en sous matrices
par blocs de lignes et les traiter en parallèle. Le découpage se fait à l’aide d’un
algorithmexheuristique, il aide à trouver pour chaque sous matrice son format de
stockage et les combiner. Les combinaisons entre plusieurs format s’appelle l’hybri-
dation [21].
L’hybridation se faitxcomme suit ; si la matrice est petite, on choisit CSR si non, si
les lignes sont à peut près de même taille, on choisit ELL comme format de stockage,
le reste de la matrice est mis sous le format CSR ou COO selon le nombre d’éléments
vides et le nombre d’éléments non nuls restants.
La parallèlisation correspond à envoyer un ensemble indépendant de bloques de vec-
teurs vers différents cœurs et de les appliquer en parallèle[10].

27
2.3 Parallélisation des programmes creux

Les pointsxforts des différents formats de stockages nous entraînent à les combiner
entre eux pour tirer avantage de chacun d’entre eux. Plus précisément ; nous divisons
notre matrice en deux sous matrices, ou plus, les hybrides ELL+COO ou ELL+CSR
donnent alors de bonnes performances.
Quand le format ELL est extrait d’une matrice dont les lignes sont de poids sem-
blables, beaucoup de lignes peuvent être laisséesxvides. Pour éviter lesxrépétitions
correspondant aux lignes vides dans le champ début du format CSR, nous créons
alors un format, nommé COO_S. Pratiquement, c’est un format basé sur CSR mais
avec desxpointeurs seulement sur les lignes vides ; cela permet une bonnexcompression
des informations de lignes, comparé aux formats COO ou CSR tout en gardant une
structure CSR et COO [21].

Le format COO_S possède des champs data, idcol qui correspondent au deux
tableaux A et JA dans les formats COO et CSR, le nombre idlig[k] correspond à la
kème ligne non vide qui commence dans data et idcol à début[k], nous donnons par
exemple la figure 2.5.

Figure 2.5 – COO_S

En plus des optimisations par hybridation, dans [1], l’auteur utilise l’optimisation
de la distribution du PMVC sur un système distribué à grande échelle (SDGE).

2.3.2 Distribution du PMVC sur un SDGE

Des structures de données particulières sont utilisées pour le stockage des ma-
trices creuses dans l’objectif de bien gérer l’espace mémoire. Les problèmes de traite-
ment de ces matrices de grande taille nécessitent un espace de stockage des données
ainsi qu’un volume de calcul importants d’où, une utilisation de superordinateurs
de haute performance qui, souvent, peuvent ne pas être disponibles. Dans le cas de
certaines applications scientifiques, les Systèmes Distribués à Grand Échelle (SDGE)
constitués de réseaux de machines interconnectées peuvent constituer une bonne al-
ternative [1].

28
2.3 Parallélisation des programmes creux

[Link] Fragmentation des matrices creuses

Dans ce qui suit, nous présentons deux approches pour décomposer une matrice
creuse, notée A, en fragments (blocs de lignes) dont le nombre est noté f. La première
NLE (fragmentation avec Nombre Equilibré de Lignes), consiste à décomposer la
matrice en blocs (fragments) de lignes ayant la même taille i.e. contenant le même
nombre de lignes contiguës. La seconde approche, appelée NEZ (fragmentation avec
Nombre Equilibré de non-Zéros) consiste à décomposer la matrice en fragments de
lignes contiguës (ne contenant pas nécessairement le même nombre de lignes) ayant
le même nombre d’éléments non nuls.

Fragmentation NLE C’est une approche naïve qui consiste à partitionner A

en f fragments (blocs de lignes) où les p premiers contiennent chacun q+1 lignes
contiguës alors que les (f -p) restants en contiennent q. La décomposition NLE vise
un équilibrage au niveau du nombre de lignes par fragment. Néanmoins, elle peut
présenter un déséquilibrage au niveau du nombre d’éléments non nuls par fragment
ce qui peut engendrer, après compression des fragments, de mauvaises performances
globales pour le PMVC

Fragmentation NEZ L’approche de fragmentation présentée ci-dessus est as-

sez naïve. Elle consiste à fragmenter la matrice A en blocs de lignes tels que chaque
bloc (fragment) contient (autant que possible) le même nombre d’éléments non nuls.
Remarquons que le nombre d’éléments non nuls par fragment doit être autour de la
moyenne NZ/f et ce, dans le but de garantir une fragmentation équilibrée.
Le principe de l’algorithme de fragmentation NEZ revient, en fait, à la résolution
d’un problème d’ordonnancement particulier [22]. Il consiste à ordonnancer N tâches
indépendantes non préemptives T1 ,. . . ,TN (i.e. les N lignes de A) de coûts c1 , ..,cN ,
où ci est le nombre d’éléments non nuls dans la ligne i, sur f processeurs homogènes
sous la contrainte que les tâches (i.e. lignes) affectées à un processeur ([Link])
doivent être successives (i.e. contiguës).
La première phase qui est une phase constructive, permet de construire une frag-
mentation initiale en un. Elle consiste à affecter des lignes contiguës à un fragment
donné jusqu’à ce que sa charge (i.e. le nombre total des éléments non nuls de ses
lignes) soit très proche du seuil Nz/f ou l’excède pour la première fois.
De plus, notons ici que :
(i) une ligne donnée ne peut appartenir qu’à un seul fragment,
(ii) le nombre de lignes n’est pas nécessairement le même pour tous les fragments.
(iii) chaque fragment contient des lignes contiguës. Ainsi, chaque fragment peut être
identifié par l’indice de sa première ligne.

[Link] Produit fragment-vecteur

Soit A une matrice creuse N×N ayant Nz éléments non nuls et x un vecteur de
taille N. L’objectif est de calculer le PMVC sur un système distribué (figure 2.6).

29
2.4 Récapitulations

L’approche utilisée pour la distribution de ce calcul consiste à utiliser une géomé-

trie virtuelle à une dimension pour les nœuds. La matrice A sera décomposée en f
fragments. En se basant sur l’étude de la fragmentation effectuée précédemment. Un
fragment (bloc de lignes), noté Ai (i= 1...f ), est envoyé au nœud virtuel i. Concer-
nant le vecteur x, il est diffusé à tous les nœuds. Par la suite, en parallèle, chaque
nœud multiplie un fragment Ai de la matrice compressée A par le vecteur x. Nous
obtenons ainsi un fragment vecteur yi du vecteur résultat y. Une fois cette phase de
calcul terminée, une phase de communication est alors nécessaire pour rassembler
les fragments du vecteur résultat y sur un nœud unique.

Figure 2.6 – Calcul de PMVC sur un système à grand échelle SDGE

2.4 Récapitulations
Les différentes modifications de la CSR ont des forces et des faiblesses :

— Vazques et al. ont interprété que la simplicité de l’implémentation du PMVC

basée sur ELLPACK-R le rend parfaitement adapté à l’informatique GPU.
L’évaluation comparative avec d’autres formats proposés a montré que la
performance moyenne réalisée par ELLPACK-R est la meilleure après une
étude approfondie sur un ensemble de matrices d’essai représentatives. Par

30
2.5 Conclusion

conséquent, ELLPACK-R s’est révélé être supérieur aux autres approches

utilisées jusqu’à présent, car il combine plusieurs avantages pour exploiter
l’architecture GPU : (1) l’amélioration de la gestion de la mémoire pour lire
la matrice creuse et (2) la réduction du calcul inutile et déséquilibre des
threads, puisque le nombre réel d’entrées non nulles dans chaque rangée de
la matrice est pris en compte.
— La performance obtenue parxl’hybridation est, en général, plusxélevée que
celle de modification des formats, mais il estxremarquable que ses résultats
soient plus bas pour les matrices de petite taille.
— la réorganisation de la matricexoriginale peut avoir des conséquences néga-
tives si elle possède une structure donnant une bonnexlocalité de données, la
réorganisation peut déplacer les lignes voisines (i.e. qui ont le même nombre
d’éléments non nuls) très éloignées.

L’objectif général de de la distribution du PMVC sur un SDGE est dexdéterminer,

pour une grande matrice creuse et un vecteur dense donnés, le meilleurxéquilibrage
des charges pour la distribution du PMVC sur unxtel système. D’après les expéri-
mentations étudiés, nous citons en quelques lignes ce que nous avons interprété :
— Il est clair que l’algorithme NLE peut être effectué en un temps O(f ). No-
tons que NLE peut engendrer un déséquilibrage de chargexprohibitif pour les
nœuds du système distribué quand les éléments non nuls ne sont pasxuniformément
répartis sur les lignes de la matrice.
— La phase 1 de NEZ peut êtrexeffectuée en un temps O(N) et la phase 2 (au
pire) en un temps O(N*nit) où nit est le nombre maximalxd’itérations. Par
conséquent, NEZ peut être effectuée en un temps O(N*nit). Si on choisit
nit=O(1) (resp. O(N)), on atteint une complexité de O(N)(resp. O(N2)).
— Le meilleur des cas axlieu, en particulier, lorsque les lignes de A contiennent
le même nombre d’éléments non nuls.
— Les temps totauxxd’exécution des algorithmes de fragmentation et le temps
nécessaire pour la construction du vecteur y (y = Ax) sont élevés lorsque f
est grand. Cela nous a permis de constater que le traitement de matrices de
grande taille sur un SDGE n’est intéressant que pour des tailles (N) nette-
mentxsupérieures au nombre de nœuds du système (f ) i.e. N  f .

2.5 Conclusion
Ce chapitre a étéxexclusivement consacré à la méthodologie de parallélisation par
le modèlexpolyédrique. Les régularités qu’impose la méthode de parallélisation par
ce modèle fait que celui-ci impose la contrainte l’affinité des bornes de ces boucles.
Ce modèle peut être considéré comme uneaplate forme standard de la parallélisation
automatique sur laquelle se greffent plusieurs méthodes de détection de parallélisme.
Cependant, certains programmes ne peuvent pas entrer dans le cadre de ce modèle

31
2.5 Conclusion

(qui ne suivent pas la règle d’affinité des bornes). Les solutions proposées pour
laaparallélisation de ces programmes sont loin d’être définitives notamment dans
le traitement des programmes dites programmes polyédriques creuxaenchaînant de-
salgorithmes à matrices creuses. Dans ce contexte, le chapitre suivant présente les
détails de nos approches réalisées pour la parallélisation du PMVC.

32
CHAPITRE 3
APPROCHES PROPOSÉES POUR CSR

3.1 Introduction
Dans les chapitres précédents, nous avons étudié le calcul creux selon deux
exemples : le PMVC et la résolution des systèmes d’équation linéaire, nous avons
donné aussi un aperçue sur les matrices creuses et leurs formats de compression,
puis dans le second chapitre, nous avons présenté un état de l’art sur les approches
de parallélisation d’un programme creux en se basant sur l’opération du PMVC.
Le présent chapitre est divisé en deux parties dont la première est consacrée à définir
les deux nouvelles approches de transformation du programme PMVC utilisant le
CSR en un programme polyédrique, et la deuxième se focalise sur l’utilisation du
CSR pour le stockage des matrices particulières.

3.2 Motivation
Le calcul du PMVC, nécessite d’abord un modèle de compression des données
convenable choisie selon le type de la matrice utilisée et l’algorithme calculant cette
opération dépend de ce modèle.
Ce travail se base sur un seul modèle : le CSR (défini dans le chapitre 1). L’algo-
rithme PMVC utilisant ce format est un programme polyédrique creux, ce caractère
creux résulte du fait que les bornes de la boucle interne sont des indices de tableaux
et le parallélisme de cette boucle ne peut pas être exploité, par conséquence, des
efforts supplémentaires doivent être dépensés pour se débarrasser de ces bornes.
Pour se faire nous proposons de reformuler la conception du format de donnée ap-
propriée pour stocker les matrices puisque l’opération PMVC est directement liée
au format utilisé, et de réécrire l’algorithme sous une forme polyédrique. Deux nou-
velles approches sont exploitées, la première est appelée une succession de boucle et
la deuxième est une boucle englobante contenant des gardes (If-Then-Else).

33
3.2 Motivation

Du fait de la diversité des formats de compression, nous nous restreignons qu’on

peut aussi à travers ce format stocker des matrices de structures particulières (par
exemple matrices bandes, matrices triangulaires par bloc, etc.) et d’écrire pour cha-
cune son algorithme PMVC polyédrique.
La figure3.1 résume tout le travail réalisé dans ce mémoire.

Figure 3.1 – Shéma explicatif du travail réalisé

Avant de détailler les nouvelles approches, nous commençons par donner l’algorithme
original du PMVC pour le format CSR.

34
3.3 Algorithme général pour CSR

3.3 Algorithme général pour CSR

Etant donné deux vecteurs x ; y ∈ Rn ; x est un vecteur quelconque, y est le
vecteur résultat et M une matrice creuse quelconque. Apres le stockage de M selon
le format CSR, nous obtiendrons trois tableaux A, JA et IA comme c’est expliqué
dans le chapitre 1.
L’opération PMVC s’écrit mathématiquement comme suit : y= y+Mx et s’exprime
par l’algorithme suivant :

Nous détaillons dans la suite le principe suivi pour se débarrasser des bornes de la
deuxième boucle qui sont des indices du tableau IA.

3.4 Proposition pour le cas des matrices quelconques

Soit l’exemple suivant de la figure 3.2 ou M est une matrice creuse quelconque
d’ordre n a nz(M) éléments non nuls que l’on a rangés dans le tableau A(1 :nz) en
les énumérant par ordre de ligne.
Dans le tableau JA (1 :nz) on range les indices de colonnes de ces éléments dans
le même ordre et dans le tableau IA (1 :n+1) on indique la liste des indices des
démarrages de lignes de la matrice M stockée dans A avec par convention la valeur
nz+1 dans IA(n+1).
Si on déroule la boucle externe sur les lignes, la fusion des différentes boucles internes
qui en résultent n’est pas légale parce que leurs lignes peuvent avoir des longueurs
(nombre d’éléments non nuls) différentes. Puisque le tableau IA de ce format fonc-
tionne comme un pointeur de ligne sur la matrice, il peut nous servir à compter le
nombre d’éléments non nuls dans chaque ligne, nous les rangeons dans un nouveau
vecteur DIFF comme tel que DIFF[k]= IA[k+1]-IA[k]. La figure 3.2 présente un
exemple de matrice compressée par le format CSR en ajoutant le nouveau tableau
DIFF.

35
3.4 Proposition pour le cas des matrices quelconques

Figure 3.2 – Exemple d’une matrice creuse quelconque stockée selon le format CSR

Maintenant selon le nouveau tableau DIFF, nous pouvons rassembler les lignes
portants le même nombre d’élément non nul dans une boucle, c’est à dire, tant que
DIFF[k]=DIFF [k+1], c’est que les lignes k et k+1 ont le même nombre d’éléments
non nuls si non on réorganise la matrice de telle manière que les lignes de même
longueur soient regroupées ensemble et on peut alors appliquer l’algorithme au nid
de boucles du PMVC et structurer les calculs selon les groupes de lignes de même
longueur.
Nous montrons dans la suite avec schéma explicatif le raisonnement de cette ap-
proche : Nous gardons le même exemple précédent pour la suite.

36
3.4 Proposition pour le cas des matrices quelconques

3.4.1 Approche 1 : Succession de boucles

[Link] Principe de base
La première approche consiste à écrire l’algorithme avec une succession de boucles
ou chaque boucle rassemble des lignes portant le même nombre d’éléments non nuls
comme c’est expliqué dans la section précédente. Cette approche est décrite par
l’algorithme 2 ci dessous :
Les nouvelles bornes dépendent de la matrice traitée ; les nombres des lignes portants

Algorithm 2 Algorithme de PMVC selon l’approche 1

for i=x1 ,x2 do
for j=1,y1 do
Y(i) = Y(i) + A(j) * X(JA(j))
end for
end for
for i=x3 ,x4 do
for j=1,y2 do
Y(i) = Y(i) + A(j) * X(JA(j))
end for
end for
.
.
.

for i=xk ,xn do

for j=1,y3 do
Y(i) = Y(i) + A(j) * X(JA(j))
end for
end for

le même nombre d’éléments non nuls et les nombres d’éléments non nuls dans chaque
ligne.

Remarque 3.4.1. Le problème c’est que nous sommes obligé à chaque fois d’écrire
manuellement les bornes des boucles, cela dépend toujours de l’emplacement des
éléments non nuls dans les matrices.

[Link] Exemple
Prenons le cas de la matrice précédente M, si on applique notre première ap-
proche, nous ajoutons le tableau DIFF comme c’est montré dans la figure 3.3. Ce
tableau nous informe qu’on a trois nids de boucles imbriquées successives, chaque
nid contient une boucle d’indice i parcoure les lignes et une autre d’indice j parcoure

37
3.4 Proposition pour le cas des matrices quelconques

les colonnes allant toujours de 1 à nzligne (avec nzligne est le nombre d’éléments dif-
férents de zéro dans chaque ligne) Dans cet exemple la première boucle allant de 1

Figure 3.3 – Nouvelle format CSR

à 1 indique que la première ligne de la matrice contient un nombre d’élément non

nul différent à celui de la deuxième, de même pour la deuxième ligne. Par contre les
lignes 4 et 5 ont le même nombre d’élément non nuls, donc nous admettons trois
boucles successives comme indiqué dans l’algorithme suivant.

Algorithm 3 Exemple de PMVC selon l’approche 1

for i=1,1 do
for j=1,3 do
Y(i) = Y(i) + A(j) * X(JA(j))
end for
end for
for i=2,2 do
for j=1,1 do
Y(i) = Y(i) + A(j) * X(JA(j))
end for
end for
for i=4,5 do
for j=1,2 do
Y(i) = Y(i) + A(j) * X(JA(j))
end for
end for

38
3.4 Proposition pour le cas des matrices quelconques

3.4.2 Approche 2 : Boucle englobante contenant des gardes

[Link] Principe de base
Dans cette approche nous gardons le même principe précédent mais nous ajou-
tons des gardes IF-THEN-ELSE pour minimiser le nombre de boucles successives,
le nouveau programme s’écrit comme suit :

Algorithm 4 Algorithme PMVC selon l’approche 2

for i=1,n do
if x1 ≤ i ≤ x2 then
for j=1,y1 do
Y(i) = Y(i) + A(j) * X(JA(j))
end for
else
if x2 ≤ i ≤ x3 then
for j=1,y2 do
Y(i) = Y(i) + A(j) * X(JA(j))
end for
else
if xk ≤ i ≤ xn then
for j=1,y3 do
Y(i) = Y(i) + A(j) * X(JA(j))
end for
end if
end if
end if
end for

[Link] Exemple
Pour le même exemple précédent, l’algorithme 5 calculant le produit de la matrice
M par un vecteur quelconque selon la deuxième approche s’écrit comme suit :

39
3.5 Matrices creuses particulières

Algorithm 5 Exemple de PMVC selon l’approche 2

for i=1,n do
if i = 1 then
for j=1,3 do
Y(i) = Y(i) + A(j) * X(JA(j))
end for
else
if i = 2 then
for j=1,1 do
Y(i) = Y(i) + A(j) * X(JA(j))
end for
else
if 4 ≤ i ≤ 5 then
for j=1,2 do
Y(i) = Y(i) + A(j) * X(JA(j))
end for
end if
end if
end if
end for

3.5 Matrices creuses particulières

Le CSR est un mode de stockage pour des matrices creuses de structure irrégulière
quelconque. Dans ce travail, nous appliquons ce format sur des matrices particulières,
c’est-à-dire des matrices de structures régulières à savoir des matrices bandes, des
matrices triangulaire par blocs ou des matrices qu’on a noté MTA/MTD.
Nous cherchons toujours à écrire le programme PMVC sous la forme polyédrique et
de le paralléliser par la suite.
Dans ce qui suit, pour chaque type de matrice nous commençons par le stockage
selon le format CSR, puis nous proposons une version polyédrique de l’algorithme
du PMVC correspondant.

3.5.1 Matrices bandes

Nous proposons ici un stockage selon le format CSR d’une matrice bande quel-
conque caractérise par le nombre de diagonaux au dessus mU et de diagonaux au
dessous mL. Le stockage de cette matrice comme pour les matrices quelconques
sauf qu’on peut s’en passer du troisième tableau IA. Nous expliquons le stockage
proposé à travers l’exemple de de la figure 3.4 où mL=2, mU=1 donc la longueur
δ=mL+mU+1=4.

40
3.5 Matrices creuses particulières

Figure 3.4 – Exemple d’une matrice bande stockée selon le format CSR

En utilisant ce stockage, le PMVC pourrait s’écrire sous la forme de trois blocs

successifs où le premier concerne les mL lignes (nombre de diagonaux au dessous), le
deuxième concerne les n-mU-mL lignes ayant chaque une δ éléments non nuls et le
troisième concerne le reste des lignes de la matrice qui est égal à mU lignes (nombre
de diagonaux au dessus).
Pour le premier (respectivement le troisième) bloc, nous avons utilisé un compteur
k exprimant le nombre d’éléments non nuls qui incrémente (respectivement décré-
mente) dans l’algorithme.

Algorithm 6 PMVC selon le CSR pour une matrice bande

k= 1+mU
for i=1,mL do
for j=1,k do
Y(i) = Y(i) + A(j) * X(JA(j))
end for
k = k + 1
end for
for i=mL+1,n-mU do
for j=1,mL+mU+1 do
Y(i) = Y(i) + A(j) * X(JA(j))
end for
end for
k= mU+mL
for i=n-mU+1,n do
for j=1,k do
Y(i) = Y(i) + A(j) * X(JA(j))
end for
k = k - 1
end for

41
3.5 Matrices creuses particulières

3.5.2 Matrices MTA et MTD

Il s’agit d’un type particulier de matrices creuses :
Le premier vérifiant |1≤j≤n et M[i,j]6= 0|=i qu’on notera "matrice de taille ascen-
dante" (MTA).
Le deuxième vérifiant |1≤ j≤n et M[i,j]6= 0|=n-i+1 noté "matrice de taille descen-
dante" (MTD).
Nous détaillons dans la suite ces deux types de matrice.

[Link] Matrices MTA

La ième ligne de la matrice MTA contient i éléments non nuls, le placement de
ces éléments se fait d’une manière aléatoire.
La figure 3.7 suivante est un exemple d’une MTA stocké selon le format CSR.

Figure 3.5 – Exemple d’une MTA stockée selon le CSR

Pour une matrice MTA, le programme PMVC s’écrit sous forme de deux boucles
imbriquées où la première parcoure tout les lignes de la matrice d’entrée et la
deuxième concerne le nombre d’éléments non nuls dans chaque ligne qui sera in-
crémenté après chaque itération.
Pour toutes matrices vérifiant ce type et stockés selon le format CSR, le PMVC est
écrit comme le montre l’algorithme 3.7 suivant.
Algorithm 7 PMVC selon le CSR pour une matrice MTA
for i=1,n do
for j=1,i do
Y(i) = Y(i) + A(j) * X(JA(j))
end for
end for

Remarque 3.5.1. La matrice triangulaire inférieure est un cas particulier de ce

type de matrices

42
3.5 Matrices creuses particulières

[Link] Matrices MTD

La ième ligne de la matrice contient n-i+1 éléments non nuls et comme pour le
cas de MTA, l’emplacement des éléments différents de zéro est aléatoire.
La figure 8 est un exemple illustrant le stockage d’une matrice MTD selon le CSR.

Figure 3.6 – Exemple d’une MTD stockée selon le CSR

Comme pour un MTA le programme PMVC vérifiant le format polyédrique (voir

algorithme 8) pour une MTD s’écrit avec doux boucles imbriquées où la première
concerne les n lignes de la matrice et la deuxième concerne n-i+1 éléments non nuls
dans chaque ligne.

Algorithm 8 PMVC d’une MTD selon le CSR

for i=1,n do
for j=1,n-i+1 do
Y(i) = Y(i) + A(j) * X(JA(j))
end for
end for

Remarque 3.5.2. La matrice triangulaire supérieure est un cas particulier de ce

type de matrices

3.5.3 Matrices triangulaire par blocs

Comme nous avons déjà expliqué dans le premier chapitre, une matrice dite tri-
angulaire par bloc est caractérisée par la taille de son bloc noté "Bloc".
On notera TIB (respectivement TSB) une matrice triangulaire inférieure (respecti-
vement supérieure) par bloc.

43
3.5 Matrices creuses particulières

Figure 3.7 – Exemple d’une matrice TIB stockée selon le CSR

Pour ce type de matrice, le remplissage des lignes se fait selon la taille du bloc
choisi, pour cette raison le nombre d’éléments non nuls (noté Nz dans les algorithmes
9 et 10) dans chaque ligne peut être déterminé par la fonction MOD :
Comme première étape, on fixe Nz de la première ligne à la taille du bloc. Ensuite,
si la position de la ième ligne est divisible par la taille du bloc, alors on a le même
nombre d’élément non nuls que la ligne précédente. Si non, on a un nombre Nz égal
à celui de la ligne précédente plus la taille du bloc.
Pour toute matrice TIB stockée selon le format CSR, l’algorithme 9 permet de
calculer son PMVC.

Algorithm 9 PMVC d’une matrice TIB selon le CSR

Nz=bloc
for i=1,n do
for j=1,Nz do
Y(i) = Y(i) + A(j) * X(JA(j))
end for
if ( i MOD bloc 6= 0) then
Nz= Nz+bloc
end if
end for

Pour toute matrice TSB stockée selon le format CSR, l’algorithme 10 permet de
calculer son PMVC.

44
3.6 Conclusion

Algorithm 10 PMVC d’une matrice TSB selon le CSR

Nz=n
for i=1,n do
for j=1,Nz do
Y(i) = Y(i) + A(j) * X(JA(j))
end for
if ( i mod bloc 6= 0) then
Nz=Nz-bloc
end if
end for

3.6 Conclusion
Le programme PMVC selon le format CSR est considéré comme un PPC se
caractérise par un caractère creux dans l’écriture des bornes de ses boucles. Ainsi,
un programme polyédrique comme un modèle de parallélisation exige l’affinité des
bornes de ses boucles. Pour remédier de ce problème, nous avons présenté deux
nouvelles approches permettant de réécrire le programme pour le transformer à un
programme polyédrique. Donc, nous avons proposé deux versions, la première notée
"une succession de boucles" et la deuxième notée "une boucle englobante contenant
des gardes". Cette étude n’était pas généralisé pour tout types de matrice creuse
quelconque à cause de la diversité de sa structure (les lignes ne sont pas toujours
de même longueur). Mais, nous avons pu constaté qu’un PPC peut être facilement
parallélisé s’il se transforme à un PP en particulier l’opération PMVC.
Par la suite, nous avons présenté une approche permettant d’appliquer le format CSR
pour la compression des matrices particulières. Nous avons écrit leur programmes
PMVC selon le modèle polyédrique et les paralléliser.
Dans le chapitre suivant, nous présenterons les résultats d’expérimentations de ces
nouvelles approches en séquentiel et en parallèle. Les expérimentations concernent
le temps d’exécution par rapport au programme original.

45
CHAPITRE 4
ÉTUDE EXPÉRIMENTALE

4.1 Introduction
Dans le chapitre précédent, nous avons proposé deux nouvelles approches du pro-
gramme PMVC pour le format CSR, ainsi, nous avons fourni quelques algorithmes
en forme polyédrique pour calculer la même opération et en utilisant le même for-
mat pour compresser des matrices creuses particulières. Puis nous avons parallélisé
le code implémenté, ceci est fait à travers l’open-source de OpenMP (omp4j).
Au niveau de ce chapitre, nous allons mener une série d’expérimentations afin de
mesurer les performances de nos algorithmes proposés. Pour ce faire, une compa-
raison va être établie avec l’algorithme original PMVC utilisant le CSR pour les
matrices de structure régulière et irrégulière en séquentiel comme en parallèle.
Le présent chapitre est organisé comme suit. Dans la section 2, nous donnons un
aperçu sur les stratégies d’expérimentation. La section 3 est consacrée à présenter les
résultats des expérimentations et les interprétations retenues. Nous terminons par
une conclusion pour résumer l’étude et les tests réalisés dans ce travail de mémoire.

4.2 Stratégies d’expérimentations

Notre but ici consiste essentiellement en : (i) la validation des approches théo-
riques présentées dans ce mémoire ; et ; (ii) l’évaluation de leurs performances. Pour
cela, nous avons procédé aux cours de nos expérimentations de la manière suivante.

— Vérifier la conformité entre toutes les versions (séquentielle et parallèles) d’un

même programme, c’est à dire s’assurer que les différentes versions fournissent
exactement les mêmes résultats dans les différentes étapes de calcul.
— Refaire une dizaine de passages pour chaque mesure de du temps d’exécution
et garder la valeur minimale. En effet, nous avons constaté que pour une

46
4.2 Stratégies d’expérimentations

expérimentation donnée, les valeurs du temps d’exécution sont très proches,

sauf certains survenus probablement au moment d’interruptions systèmes,
dont la durée est d’un ordre de grandeur nettement supérieur. Ainsi, afin de
ne pas prendre en compte de telles valeurs qui risquent de fausser les résultats,
nous avons opté pour le choix du minimum.
— Dans le but d’évaluer les performances pratiques des différentes approches
de calcul PMVC, nous avons effectué une série d’expérimentations sur l’en-
semble de matrices suivants.
(i) matrices quelconques générées aléatoirement.
(ii) matrices Particulières (matrices bande, matrices par bloc, matrices MTA
et MTD) générées aléatoirement.
Précisons que pour tout les ensembles, nous donnons la taille n de la matrice,
nous avons conçu un générateur qui fournit en sortie une matrice respectant
sa forme (bande, bloc, etc.) où les éléments non nuls sont distribués aléatoi-
rement.
— L’étude consiste à comparer les nouvelles algorithmes PMVC pour CSR par
rapport à l’algorithme original à travers les facteurs suivants :
(i) varier la taille n du matrice étudiée ainsi que la taille des diagonaux mU
et mL pour les matrices bandes et la taille du bloc pour les matrices blocs.
(ii) varier le nombre de morceaux qu’on a noté m selon plusieurs configura-
tions (c1 ,c2 ,...,cn ) pour les matrices quelconques.
(iii) varier le nombre d’éléments non nuls noté Nz dans les matrices quel-
conques.
(iiii) varier le nombre de thread (th) dans le but d’observer le comportement
générale des programmes en fonction du nombre de threads.

4.2.1 Les mesures utilisées

Dans la plupart des programmes scientifiques de calcul numériques, une grande
fraction du temps d’exécution total est passé dans le calcul d’un petit nombre d’ins-
tructions internes à des boucles (c’est à dire boucles imbriqués) comme pour le cas
d’un PMVC.
La parallélisation ne peut réduire le temps d’exécution que si le programme présente
suffisamment de parallélisme. Nous pouvons donc mesurer les performances de nos
approches par le calcul de leurs temps d’exécution noté (Te).

4.2.2 OpenMP
Dans ce travail de mémoire nous avons choisir OpenMP comme outil de pa-
rallélisation. En effet, la simplicité de son interface nous a permis de paralléliser
rapidement notre code, il permet aussi un gain de performance d’un facteur presque
N (ou N est le nombre de cœurs disponibles).

47
4.3 Étude expérimentale sur des matrices quelconques

Definition 4.2.1. L’API Open Multi-Processing (OpenMP) offre un modèle de pro-

grammation parallèle plus haut-niveau que Pthreads. Elle permet la parallélisation
d’un programme C, C++ ou Fortran à travers un ensemble d’instructions données
directement au compilateur par des directives "#pragma" dans le code source. Par
exemple, on peut facilement, à l’aide de cette API de paralléliser l’exécution d’une
boucle, de telle sorte que chaque fil calcule la partie du résultat liée à sa partie du
domaine d’entrées. OpenMP permet aussi de contrôler le partage de données entre
les fils, de facilement unifier les résultats des fils à l’aide d’opérations de réduction,
et d’automatiquement répartir la charge sur les fils en utilisant un ordonnanceur dy-
namique. L’usage d’OpenMP est très utile pour des calculs itératifs qui bénéficieront
grandement de la parallélisation, comme un calcul utilisant la méthode des éléments
finis.

4.2.3 Environnement matériel et logiciel

Les caractéristiques physiques des machines utilisées pour l’implémentation des
algorithmes et la réalisation des tests sont comme suit :
Un PC avec un processeur Intel(R) Pentium(R) CPU 2.16GHz 4 cœurs et 4 Go de
RAM et sur WINDOWS 8.
Les nouvelles approches PMCV polyédriques ont été implémentées en java avec
Eclipse et nous avons choisi omp4j (OpenMP pour Java) pour les paralléliser.
Nous présentons dans ce qui suit les résultats les plus significatifs que nous avons
obtenus en expérimentant nos approches de transformation d’un PPC en PP. Les
résultats décrits dans ce chapitre concerne le code du PMVC utilisant le CSR.

4.3 Étude expérimentale sur des matrices quelconques

Cette section décrit les tests réalisés sur des matrices creuses quelconques de
différentes tailles en séquentiel et en parallèle.
Comme première expérimentation, nous avons d’abord vérifié que les résultats obte-
nus par les nouvelles versions implémentées sont identiques par rapport à la version
originale. Nous avons ainsi mesuré le temps d’exécution du PMVC pour chaque
version.

4.3.1 Versions séquentiels

Afin d’analyser convenablement les résultats de nos expérimentions, nous étu-
dions les variations des Te en fonction du nombre d’éléments non nuls Nz de la
matrice étudiée, ensuite en fonction de sa taille et enfin en fonction de nombre de

48
4.3 Étude expérimentale sur des matrices quelconques

morceaux m. Pour ne pas encombrer les figures, nous n’y présenterons que les résul-
tats les plus significatifs.

Remarque 4.3.1. Le PMV a une complexité de O(n2 ) ou n désigne la taille de la

matrice. Donc si n est multipliée par deux, le temps d’exécution est multiplié par
quatre. Mais dans le cas du PMVC on parle des matrices creuses (c’est à dire, deux
matrices de même taille peuvent ne pas avoir le même nombre d’éléments non nuls
Nz). Dans ce cas, le temps d’exécution dépend de Nz.

La figure 4.1 est un exemple de deux matrices de même taille n, même nombre
de morceau m, même configuration c et un nombre d’éléments non nuls Nz différent.

Figure 4.1 – Exemple de deux matrices M1 et M2 de taille n=5

Suite à cette remarque, les premières expérimentations ont été réalisées comme
suit :
Nous avons fixé n et Nz puis, nous avons varié le nombre de morceaux (m1 ,m2 ,...,mn )
ainsi que la configuration (c1 ,c2 ,...,cn ). Notons que, pour une matrice creuse quel-
conque, le nombre de morceaux désigne le nombre des lignes qui ont le même nombre
d’éléments non nuls (Nz) et la configuration (c) désigne le nombre d’éléments non
nuls dans chaque morceau (m).

Nous avons implémenté une matrice quelconque tel que, les valeurs de ses pa-
ramètres sont les suivants : taille de la matrice n=50, nombre d’éléments non nuls
Nz=1275 et le nombre de morceaux varie entre 2 et 50. Nous avons aussi varié la
configuration c de deux manières comme il est indiqué dans le tableau 4.1 pour voir
si elle influe sur Te ou non. Les valeurs des temps d’exécutions Te obtenus sont
classés comme suit.

49
4.3 Étude expérimentale sur des matrices quelconques

Morceau (m) 2 50 10
Configuration(c) 25/26 1/49 par ligne par 5 lignes 41/1/../1
CSR original 0.050 0.050 0.051 0.051 0.051
Approche 1 0.042 0.042 0.062 0.058 0.059
Approche 2 0.043 0.043 0.065 0.060 0.060

Table 4.1 – Te en fonction de m avec n=50 et Nz=1275

Commentaire 4.3.1. À la lecture des résultats de cette expérimentation, nous re-

marquons que, pour la même taille n, le même Nz et quelque soit m la configuration
n’influe pas sur Te.

Nous avons refaire la même expérimentation avec des matrices et des vecteurs de
tailles 100 et 500 sans tenir compte de leur configuration. Les résultats sont présentés
dans La table 4.2.

Nombre d’éléments
Taille (n) morceau (m) CSR original Approche 1 Approche 2
non nuls (Nz)
2 0.064 0.050 0.052
1275 10 0.065 0.069 0.072
50 0.064 0.073 0.076
100 2 0.114 0.098 0.099
10 0.115 0.132 0.139
5050
50 0.115 0.184 0.189
100 0.115 0.210 0.221
2 0.093 0.062 0.068
1275 10 0.094 0.097 0.104
50 0.092 0.112 0.114
2 0.154 0.103 0.105
5050 10 0.154 0.163 0.165
500
50 0.155 0.275 0.300
2 0.614 0.452 0.456
10 0.613 0.645 0.649
125250
50 0.614 0.956 0.982
500 0.615 1.389 1.401

Table 4.2 – Te (en s) du calcul PMVC

[Link] Variation des Te en fonction de Nz

Dans cette section, nous nous intéressons à comparer les algorithmes des nou-
velles approches avec celui du CSR original, À cet effet, nous varions le nombre

50
4.3 Étude expérimentale sur des matrices quelconques

d’éléments non nuls de la matrice d’entrée en fixant sa taille et le nombre de mor-

ceaux. Les valeurs des paramètres sont les suivants : la taille n=500, le nombre de
morceau m=10. Nous avons obtenu les résultats représentés par la Figure 4.2. Nous
constatons que lorsque nous augmentons le nombre d’éléments non nuls, le temps
d’exécution augmente. En d’autres termes, Te augmente en fonction de Nz pour tous
les versions.

Figure 4.2 – Te en fonction de Nz pour n=500 avec m=10

[Link] Variation des Te en fonction de n

Afin d’analyser convenablement les résultats de nos expérimentations, nous étu-
dions les variations des Te en fonction de n. Pour des matrices de taille variable, si
nous fixons Nz et m (voir Figure 4.3), nous remarquons que la durée totale de temps
d’exécution augmente en fonction de la taille de la matrice d’entrée.

Figure 4.3 – Te en fonction de n pour Nz=1275 avec m=50

La boucle externe de la version du CSR original allant de 1 à n même si Nz

51
4.3 Étude expérimentale sur des matrices quelconques

est très petit, c’est de même pour les deux versions puisque toutes les lignes de la
matrice d’entrée contiennent au moins un élément non nul. Donc pour le même Nz,
si n augmente, Te augmente aussi.

[Link] Variation des Te en fonction de m

Nous avons remarqué dans les expérimentations précédentes que la version du
CSR original donne des résultats meilleurs que les nouvelles approches. Nous avons
donc varié m pour voir le comportement de chaque version sur des matrices de taille
n et Nz fixes.
La figure 4.4 représente les résultats obtenues.

Figure 4.4 – Te en fonction de m

En conséquence, nous concluons que l’augmentation de Te est due à l’augmen-
tation du nombre de boucles de nos versions. Lorsque la version original du CSR
contient deux boucles imbriqués quelque soit la valeur de m (voir chapitre 3), les
deux approche peuvent avoir un nombre de boucle imbriqué parfois égal à n (c’est
à dire chaque ligne de la matrice admet un nombre Nz différent au reste des lignes).
On constate ainsi pour un nombre de morceau égal à 2 (très petit), les nouvelles
approches

[Link] Comparaison entre Approche 1 et Approche 2

Pour l’algorithme du calcul PMVC utilisant le CSR, nous avons arrivé à résoudre
le problème des bornes non affines. En séquentiel, nous n’avons pas trop augmenté
les valeurs des Te.
La question qui se pose maintenant : laquelle parmi ces deux approches la plus
performante ?( La performance du code est évidement caractérisée par son temps
d’exécution).
La repense à cette question est obtenu suite à une comparaison entre les deux (figure
4.5).

52
4.3 Étude expérimentale sur des matrices quelconques

Figure 4.5 – Te en fonction de m

Les temps d’exécution affichés confirment que la meilleure version est celle de
l’approche 1 (des boucles successives), En effet, l’algorithme PMVC utilisant cette
approche présente des temps d’exécution assez réduits par rapport à l’approche 2
(boucle englobante contenant des gardes).
cette conclusion est valide quelque soit n, Nz et m.

Commentaire 4.3.2. Suite à ces interprétations, on opte pour Approche 1 pour le

reste de cette étude.

4.3.2 Versions Parallèles

Nous avons mesuré les variations des temps d’exécutions pour les différentes
versions parallèles du PMVC. Comme pour le cas séquentiel, nous avons utilisé un
échantillon de matrices de tailles (notées n) et de nombre d’éléments non nuls (notées
Nz). Ces matrices ont été générées aléatoirement avec un nombre de morceaux m
variable.

[Link] Version CSR original

Nous avons vu dans le programme de calcul PMVC pour le CSR original (voir
chapitre 3), que la boucle externe est parallélisable, en effet, pour le calcul d’un
produit matrice vecteur dense ou creux, les lignes du vecteur résultat sont indépen-
dantes c’est à dire le calcul ainsi que le remplissage de ces lignes peuvent s’exécuter
en parallèle.
Dans le tableau [Link], nous avons varié la taille de la matrice d’entrée entre 50 et
1000 l’effet de la parallélisation de la boucle externe est clair dans l’histogramme de
la figure4.6.

53
4.3 Étude expérimentale sur des matrices quelconques

Tille (n) 50 100 500 1000

CSR en séquentiel 0.051 0.065 0.092 0.265
th=2 0.026 0.034 0.064 0.141
CSR en parallèle th=3 0.018 0.023 0.040 0.091
th=4 0.013 0.018 0.024 0.068

Table 4.3 – Te en fonction de n avec Nz=1275, m=50

Figure 4.6 – Te en fonction de n obtenues par CSR original avec Nz=1275, m=50,
th=3
la version OpenMP permet quant à elle d’exploiter plus le parallélisme (Figure
4.7).

Figure 4.7 – accélération et efficacité en fonction de n

Il est à noté que la meilleure accélération est atteinte par un nombre de threads
égal à 4 est qui correspond au nombre de processeurs.

54
4.3 Étude expérimentale sur des matrices quelconques

Concernant l’efficacité, nous remarquons qu’elle est proche de 1 pour quelque soit
le nombre de threads ce qui est prévisible puisque nous avons quatre processeurs.

[Link] Approche proposée (Approche 1)

Dans cette section nous nous intéressons à comparer l’approche 1 séquentiel à
celle en parallèle. Nous avons fait varier le nombre de threads (th) de 2 à 4 en utili-
sant 4 processeurs de la machine et ce, dans le but d’observer le comportement de la
nouvelle approche en fonction du nombre de threads. D’après le tableau [Link], les
résultats obtenues sont plus au moins encourageantes, nous pouvons dire qu’avec la
nouvelle approche parallèle, nous avons arrivé à réduire le temps d’exécution beau-
coup plus mieux que la version originale.

Tille (n) 50 100 500

Approche 1 séquentiel 0.062 0.073 0.112
th=2 0.032 0.037 0.057
Approche 1 en
th=3 0.021 0.025 0.039
parallèle
th=4 0.016 0.020 0.030

Table 4.4 – Te en fonction de n obtenues par approche 1 avec Nz=1275, m=50

L’effet de la parallélisation sur les Te est clair sur la figure 4.8 où nous avons fixé
Nz à 1275 ainsi que m à 50 et varié la taille n de matrice d’entrée.

Figure 4.8 – Te en fonction de n pour Nz=1275 et m=50, th=3

Commentaire 4.3.3. L’utilisation du Opensource Ompj4 a permis le traitement

d’un volume de données avec un temps d’exécution assez réduit.
En utilisant un nombre de thread égal à quatre, nous avons gagné plus de parallélisme
avec une accélération qui atteint 3,73 pour une matrice de taille 500 (figure 4.9) .

55
4.3 Étude expérimentale sur des matrices quelconques

Figure 4.9 – Accélération et efficacité en fonction de n

[Link] Comparaison entre Approche 1 et version CSR original

Nous essayons à travers la figure 4.10 ci-dessous de résumer les résultats des
approches étudiés. Nous avons fixé Nz et m ainsi que le nombre de threads pour les
versions parallèles.

Figure 4.10 – Te en fonction de n pour Nz=1275 , m=50 et th=3

En conclusion, les expérimentations confirment que la nouvelle approche donne

des bonnes résultats en parallèle, en transformant le programme PMVC en un pro-
gramme polyédrique, nous avons gardé les mêmes intervalles des Te obtenus par la
version originale.

56
4.4 Étude expérimentale sur des matrices particulières

4.4 Étude expérimentale sur des matrices particu-

lières
Nous avons déjà vu qu’on peut appliquer le format CSR sur des matrices parti-
culières de manière à respecter son principe de compression des matrices creuses et
d’écrire leurs programmes PMVC avec format polyédrique, dans cette section, nous
allons testé le comportement de ce format sur ces types de matrices.

4.4.1 Matrices Blocs

Le tableau 4.5 représente des valeurs de Te relevées pour des matrices bandes de
taille variante entre 1000 et 6000, avec 2,3 et 4 threads (th).

Taille de la matrice (n) 1000 3000 5000 6000

Bloc 100 50 100 50 300 50 500 50
CSR originale 0.109 0.091 1.639 0.275 1.720 0.457 3.338 1.822
Nouvelle version
0.107 0.091 1.453 0.263 1.334 0.434 2.762 1.748
séquentiel
th=2 0.065 0.047 0.74 0.135 0.68 0.22 1.39 0.87
Nouvelle version
th=3 0.039 0.032 0.51 0.088 0.44 0.15 0.92 0.59
parallèle
th=4 0.029 0.025 0.38 0.067 0.35 0.11 0.70 0.48

Table 4.5 – Te en fonction de n avec variation du taille de Bloc

Dans le but de comparer nos résultats à la version du CSR original, nous nous
sommes restreints à la figure 4.11 qui représente les valeurs des Te en fonction de la
taille de la matrice d’entrée en fixant la taille de bloc à 50.

Figure 4.11 – Te en fonction de n avec Bloc=50, th=4

57
4.4 Étude expérimentale sur des matrices particulières

Commentaire 4.4.1. En conclusion, les expérimentations montrent que les meilleurs

résultats sont obtenus par la nouvelle version en parallèle et même en séquentiel.

4.4.2 Matrices bandes

Le tableau 4.6 représente les valeurs des Te relevées pour des matrices bandes de
taille variant entre 1000 et 6000, avec 2 puis 4 threads (th).

Taille de la matrice (n) 1000 3000 5000 6000

mL 300 20 1000 20 1000 20 1000 20
Diagonaux
mU 200 50 1000 50 1000 50 1000 50
CSR originale 0.109 0.094 0.594 0.294 0.589 0.397 0.720 0.399
Nouvelle version
0.092 0.087 0.520 0.226 0.478 0.380 0.682 0.387
séquentiel
th=2 0.048 0.044 0.271 0.115 0.240 0.120 0.345 0.192
Nouvelle version
th=3 0.034 0.030 0.174 0.075 0.161 0.125 0.228 0.130
parallèle
th=4 0.023 0.023 0.133 0.058 0.120 0.095 0.170 0.097

Table 4.6 – Te en fonction de n, mL et mU

Commentaire 4.4.2. Selon la lecture du tableau 4.6, nous remarquons que la nou-
velle version pour le calcul PMVC utilisant le CSR est meilleure que la version
originale en séquentiel comme en parallèle.

La figure 4.12 présente les valeurs des Te pour des matrices bande de taille entre
1000 et 6000 où nous fixons le nombre des diagonaux au dessous mL=20 et au dessus
mU=50.

Figure 4.12 – Te en fonction de n avec mL=20, mU=50, th=4

58
4.4 Étude expérimentale sur des matrices particulières

Commentaire 4.4.3. Nous remarquons que les meilleures valeurs des Te sont tou-
jours atteintes par la nouvelle version que nous avons proposé dans le chapitre précé-
dent. Nous pouvons aussi noté selon l’histogramme si dessus que Te croit légèrement
en fonction de n.
concernant la version parallèle, Te diminue en fonction de th.

4.4.3 Matrices MTA/MTD

La même expérimentation est faite sur des matrices MTA et MTD et le tableau
4.7 illustre les résultats obtenus.
Taille de la matrice (n) 1000 3000 5000 6000
Type MTD MTA MTD MTA MTD MTA MTD MTA
CSR originale 0.119 0.097 0.422 0.425 1.322 1.334 1.956 1.747
Nouvelle version
0.089 0.087 0.349 0.411 1.122 1.134 1.537 1.345
séquentiel
th=2 0.50 0.045 0.175 0.203 0.614 0.570 0.77 0.674
Nouvelle version
th=3 0.031 0.030 0.118 0.138 0.412 0.381 0.512 0.446
parallèle
th=4 0.024 0.022 0.089 0.102 0.310 0.284 0.389 0.334

Table 4.7 – Te en fonction de n

Les résultats du tableau 4.7 montrent que Te augmente en fonction de n. Nous re-
marquons ainsi que la nouvelle approche fournit toujours des valeurs de Te meilleurs.
Dans ce qui suit, nous présentons un histogramme (voir Figure 4.13) relatif à la
nouvelle approche représentant une variation de n. Le même comportement a été
remarqué pour les deux matrices MTD et MTA.

Figure 4.13 – Te en fonction de n avec th=4

Commentaire 4.4.4. quelque soit n, nous remarquons que les nouvelles versions
sont plus meilleures que la version originale. De plus, la parallélisation a permis

59
4.5 Conclusion

de réduire encore le temps d’exécution. Ceci est décrit dans les histogrammes de la
figure 4.13.

À la lecture des tableaux est des histogrammes précédents, nous pouvons constaté
que pour les matrices creuses régulières le format CSR nous a servi non seulement
dans le stockage des éléments non nuls, mais aussi de réduire le temps de calcul de
ces éléments.

4.5 Conclusion
Au niveau de ce chapitre, nous avons mené une série d’expérimentations : La pre-
mière partie a été consacrée sur des matrices quelconques dont le but de comparer
les nouvelles approches implémentés par rapport la version originale du programme
PMVC utilisant le format de compression CSR. Nous avons remarqué qu’en aug-
mentant le nombre d’éléments non nuls (Nz) dans la matrice (soit en augmentant sa
taille tout en fixant Nz, soit en fixant sa taille et en augmentant Nz), la durée totale
d’exécution augmente. Nous avons également noté que, dans les nouvelles approches,
l’augmentation du nombre de morceaux augmente le temps d’exécution.
La deuxième partie a présentée des expérimentations sur des matrices particulières.
Ceci est fait afin d’étudier et analyser le comportement du CSR sur quelques ma-
trices de structure régulière. A cet égard, les évaluations ont montrées que le temps
d’exécution est réduit par rapport à la version originale du CSR en séquentiel comme
en parallèle.

60
 CONCLUSION GÉNÉRALE

Dans ce mémoire, nous sommes intéressés dans le domaine de programme creux.

En effet, l’étude bibliographiqueapar laquelle nous avons entamé notre travail a per-
mis deaconstater que plusieurs applications scientifiques effectuent des calculs sur
des matrices creuses de grandes tailles, Il s’avère que ces calculs reposent essentiel-
lement sur le noyau produit matrice-vecteur creux (PMVC).
Afin d’avoir une idée précise sur les matrices creuses et leurs différents modes
de stockage, nous avons effectué un passage en revue que nous avons voulu as-
sezaexhaustif sur les différentes structures régulières et irrégulières de matrices creuses.
Pour les deux classes de structures i.e. régulières et irrégulières, nous avons décrit
une série de modes de stockage. Cela a conduit à classer les formats deacompression
en deux catégories : formats généralistes et formats spécifiques. Nous avons ainsi
constaté que la structure la plus fréquente est la structure (irrégulière) quelconque,
pour cette raison, notre échantillon de formats de compression a été limitée essen-
tiellement au format CSR.
Notre problématique étant l’étude de la transformation d’un programme polyédrique
creux (PPC) en programme polyédrique (PP). Il est possible de tireraprofit de l’étude
du PMVC, le travail consiste à éliminer le critère creux (les bornes non affines) du
programme source pour pouvoir le paralléliser.
L’aspect et la méthodologie mathématique riche du modèle polyédrique le distin-
guant des autres méthodes classiques, il traite des nids de boucles, à contrôle sta-
tique, dont les bornes sont des fonctions affines des indices de bouclesaenglobantes
et des paramètres de structure.
Dans ce contexte, nous avons proposé deux nouvelles approches (voir chapitre 3)
pour modifier le programme PMVC utilisant le format CSR et le transformer en
PP. notre contribution s’est basée sur la division de l’algorithmeaoriginal selon le
nombre de morceaux (le nombre des lignes contenant le même nombre d’éléments non
nuls). Ensuite, après avoir étudié l’opération PMVC sur des matrices quelconques,
nous sommes passés à appliqué le même format sur des matrices particulières comme
les matrices bande, les matrices par bloc ou les matrices qu’on a noté MTA/MTD,

61
4.5 Conclusion

puis pour chacune, nous avons implémenté son programme PMVC sous forme poly-
édrique en séquentiel puis en parallèle en utilisant l’outil de parallélisation OpenMP.

Les expérimentations que nous avons réalisées montrent que l’augmentation du

nombre d’éléments non nuls ou de la taille dans la matrice augmente la durée to-
tale d’exécution. Pour le cas des matrices quelconques, la génération du meilleur
algorithme du PMVC étais celle de l’approche 1, mais en augmentant le nombre de
morceaux, la version original devient meilleure. En effet, les expérimentations ont
confirmé les résultats de notre étude théorique qui ont montré que le temps d’exé-
cution augmente en fonction du nombre de boucles successives en séquentiel comme
en parallèle. Ainsi, l’utilisation de ce format sur des matrices particulières a permis
d’accélérer l’opération PMVC en séquentiel et en parallèle.
Les travaux qui sont réalisés tout au long de ce mémoire permettront par la suite
d’ouvrir de nouveaux axes de recherche et même des perspectives d’amélioration.
Nous en citons les suivantes :
• Pour n’importe quelle matrice creuse quelconque compressée selon le format
CSR, transformer automatiquement l’algorithme de calcul PMVC selon les
approches 1 et 2.
• Automatiser la phase de transformation d’un PPC en PP et essayer de réaliser
des compilateurs capable de paralléliser automatiquement les programmes
creux.

62
 BIBLIOGRAPHIE

[1] Olfa Hamdi-Larbi. Etude de la distribution, sur système à grande échelle, de

calcul numérique traitant des matrices creuses compressées. PhD thesis, Uni-
versité de Versailles-Saint Quentin en Yvelines, 2010.
[2] Lilia Ziane Khodja. Resolution de systemes lineaires et non lineaires creux sur
grappes de GPUs. PhD thesis, Université de Franche-Comté, 2013.
[3] Lilia Ziane Khodja. Résolution de systèmes linéaires et non linéaires creux sur
grappes de GPUs. PhD thesis, Besançon, 2013.
[4] Michel Cosnard and Denis Trystram. Algorithmes et architectures paralleles.
Interéd, 1993.
[5] Yaroub Elloumi. Parallélisme des nids de boucles pour l’optimisation du temps
d’exécution et de la taille du code. PhD thesis, Paris Est, 2013.
[6] Wei Li and Keshav Pingali. A singular loop transformation framework based
on non-singular matrices. Languages and Compilers for Parallel Computing,
pages 391–405, 1993.
[7] Yosr Slama and Mohamed Jemni. Improving code generation in the polytope
model. 2000.
[8] Martin Griebl, Christian Lengauer, and Sabine Wetzel. Code generation in the
polytope model. In Parallel Architectures and Compilation Techniques, 1998.
Proceedings. 1998 International Conference on, pages 106–111. IEEE, 1998.
[9] Jean-Fran cois Collard. Automatic parallelization of higher-order languages in
the polytope model.
[10] Rachid Habel. Programmation haute performance pour architectures hybrides.
PhD thesis, Paris, ENMP, 2014.
[11] Sivan Toledo. Improving the memory-system performance of sparse-matrix
vector multiplication. IBM Journal of research and development, 41(6) :711–
725, 1997.

63
BIBLIOGRAPHIE

[12] Juan Carlos Pichel, Dora Blanco Heras, José Carlos Cabaleiro, and Francisco F
Rivera. Performance optimization of irregular codes based on the combination
of reordering and blocking techniques. Parallel Computing, 31(8) :858–876,
2005.
[13] James B White and Ponnuswamy Sadayappan. On improving the performance
of sparse matrix-vector multiplication. In High-Performance Computing, 1997.
Proceedings. Fourth International Conference on, pages 66–71. IEEE, 1997.
[14] Jeremiah Willcock and Andrew Lumsdaine. Accelerating sparse matrix compu-
tations via data compression. In Proceedings of the 20th annual international
conference on Supercomputing, pages 307–316. ACM, 2006.
[15] Ali Pinar and Michael T Heath. Improving performance of sparse matrix-
vector multiplication. In Proceedings of the 1999 ACM/IEEE conference on
Supercomputing, page 30. ACM, 1999.
[16] Richard W Vuduc and Hyun-Jin Moon. Fast sparse matrix-vector multiplication
by exploiting variable block structure. In International Conference on High
Performance Computing and Communications, pages 807–816. Springer, 2005.
[17] Francisco Vázquez, José-Jesús Fernández, and Ester M Garzón. A new ap-
proach for sparse matrix vector product on nvidia gpus. Concurrency and
Computation : Practice and Experience, 23(8) :815–826l, 2011.
[18] E Im and Katherine A Yelick. Optimizing sparse matrix-vector multiplication
for register reuse. In Proceedings of the International Conference on Computa-
tional Science, 2001.
[19] Samuel Williams, Leonid Oliker, Richard Vuduc, John Shalf, Katherine Yelick,
and James Demmel. Optimization of sparse matrix–vector multiplication on
emerging multicore platforms. Parallel Computing, 35(3) :178–194, 2009.
[20] Rich Vuduc, James W Demmel, Katherine A Yelick, Shoaib Kamil, Rajesh Ni-
shtala, and Benjamin Lee. Performance optimizations and bounds for sparse
matrix-vector multiply. In Supercomputing, ACM/IEEE 2002 Conference,
pages 26–26. IEEE, 2002.
[21] Brice Boyer. Multiplication matricielle efficace et conception logicielle pour la
bibliotheque de calcul exact LinBox. PhD thesis, Université de Grenoble, 2012.
[22] Dorit S Hochbaum. Approximation algorithms for NP-hard problems. PWS
Publishing Co., 1996.
[23] Gene M Amdahl. Validity of the single processor approach to achieving large
scale computing capabilities. IEEE Solid-State Circuits Society Newsletter,
12(3) :19–20, 2007.
[24] Joseph L Greathouse and Mayank Daga. Efficient sparse matrix-vector multi-
plication on gpus using the csr storage format. In Proceedings of the Interna-
tional Conference for High Performance Computing, Networking, Storage and
Analysis, pages 769–780. IEEE Press, 2014.

64
BIBLIOGRAPHIE

[25] S Ezouaoui, Z Mahjoub, L Mendili, and S Selmi. Performance evaluation of

algorithms for sparse-dense matrix product. In Proceedings of the International
MultiConference of Engineers and Computer Scientists, volume 1, 2013.
[26] Thalie Léna Keklikian. Modélisation des accès mémoire lors de la multiplication
d’une matrice creuse par un vecteur sur processeur graphique. PhD thesis, École
Polytechnique de Montréal, 2014.
[27] Jérôme Richard. Implémentation et évaluation d’algorithmes parallèles de FFTs
3D à base de modèles de composants logiciels. PhD thesis, LIP-ENS Lyon ;
Orleans-Tours, 2014.
[28] Muthu Manikandan Baskaran and Rajesh Bordawekar. Optimizing sparse
matrix-vector multiplication on gpus using compile-time and run-time stra-
tegies. IBM Reserach Report, RC24704 (W0812-047), 2008.
[29] Ibrahima Gueye. Résolution de grands systemes linéaires issus de la méthode
des éléments finis sur des calculateurs massivement paralleles. PhD thesis, École
Nationale Supérieure des Mines de Paris, 2009.
[30] Gérard Authié, Afonso Ferreira, Jean-Louis Roch, Gilles Villard, Jean Roman,
Catherine Roucairol, and Bernard Virot. Algorithmes parallèles-analyse et
conception. Hermès, 1994.
[31] Pyrrhos Stathis, Stamatis Vassiliadis, and Sorin Cotofana. A hierarchical sparse
matrix storage format for vector processors. In Parallel and Distributed Pro-
cessing Symposium, 2003. Proceedings. International, pages 8–pp. IEEE, 2003.
[32] John Mellor-Crummey and John Garvin. Optimizing sparse matrix-vector pro-
duct computations using unroll and jam. International Journal of High Per-
formance Computing Applications, 18(2) :225–236, 2004.

65