Reproductibilité numérique pour l'HPC exascale

ChemseddineChohra

Reproductibilité numérique pour l'HPCexascale

Scolarité

2008 : Bacalauréat en mathématiques : Mention : passable. Moyenne : 11,38.

2011 : Licence en informatique : Spécialité : Systèmes d'information. Université : université de Guelma, Algérie. Stage de fin de cycle :

Durée : 4 mois. Sujet : collaboration dans les RS (Réseaux Sociaux). Directeur : Khaled HALIMI (maitre assistant LabSTIC-Univ de

Guelma). Note obtenue : 15,5.

Classement : 3 / 60. Moyenne de cursus : 13,5.

Scolarité

2013 : Master en informatique : Spécialité : master de recherche. Université : université de Guelma, Algérie. Stage de fin de cycle :

Durée : 5 mois. Sujet : outil d'analyse des RS à base de web sémantique

(application sur une plateforme d'apprentissage social). Directeur : Khaled HALIMI (maitre assistant LabSTIC-Univ de

Guelma). Note obtenue : 16.

Moyenne de cursus : 15,00. Classement : 1/30 (Major de promotion).

Scolarité

Concours pour l'obtention de bourse : Centre : université de Constantine, Algérie. Module : BDD, algorithmique, SE, langues (Français et Anglais), culture

générale. Classement : 1/51.

Scolarité 2012-2013 (Travail de master)

Analyse sémantique d’une plateforme d’apprentissage social :

Conception d’une ontologie pour le domaine d’apprentissage.




Définition formelle et explicite d’une

conceptualisation partagée






Conception d’une ontologie pour le domaine d’apprentissage. Représentation des ressources sous forme RDF.




Ensemble de triplets (Sujet, Prédicat, Objet)






Conception d’une ontologie pour le domaine d’apprentissage. Représentation des ressources sous forme RDF. Définir des règles d’inférence sur le graphe représentatif.



Conception d’une ontologie pour le domaine d’apprentissage. Représentation des ressources sous forme RDF. Définir des règles d’inférence sur le graphe représentatif. Appliquer les algorithmes (existants) de l‘analyse des réseaux sociaux

(détection des individus importants et des communautés dans notre réseau social).



Conception d’une ontologie pour le domaine d’apprentissage. Représentation des ressources sous forme RDF. Définir des règles d’inférence sur le graphe représentatif. Appliquer les algorithmes (existants) de l‘analyse des réseaux sociaux

(détection des individus importants et des communautés dans notre réseau social).

Visualiser et exploiter des résultats.


Représentation globale de notre système

Résultats

90% des objectifs initiaux.

Communication orale à la deuxième journée nationale JSTIC 2013 à l’université de Guelma. Titre : outil d‘analyse des RSs à base de web sémantique. Auteurs : Khaled HALIMI, Abdelaziz KHALED, Chemseddine CHOHRA. Présenté par : Abdelaziz KHALED.

Article soumis à SCA’2013.

Thèse

Comité de suivie de thèse :

Directeur : Philippe LANGLOIS (Professeur à DALI-UPVD). Codirecteur : David PARELLO (Maître de conférence à DALI-UPVD). Membre de l’ED : Bernard GOOSSENS (Professeur à DALI-UPVD). Membre extérieur : Fabienne JEZEQUEL (Maître de conférence « HDR »

au laboratoire d’informatique-Paris 6). Référent : Salim HADDADI (Professeur à LabSTIC-Univ de Guelma).

Sujet : Reproductibilité numérique pour l'HPC exascale.

Mots clés : Arithmétique, Précision, Performance, Algèbre linéaire, BLAS.

Problématique

Non-reproductibilité numérique des résultats :

Erreurs d’arrondi (Ǝ x є R, fl(x) ≠ x). Les erreurs de calcul (Ǝ x, y є Fl, x + y ≠ x + y).

La non-associativité des opérations :(Ǝ x, y, z є Fl, x + (y + z) ≠ (x + y) + z.

Problématique

Non-reproductibilité numérique des résultats :

Erreurs d’arrondi (Ǝ x є R, fl(x) ≠ x). Les erreurs de calcul (Ǝ x, y є Fl, x + y ≠ x + y).

La non-associativité des opérations :(Ǝ x, y, z є Fl, x + (y + z) ≠ (x + y) + z.

HPC exascale :

1018 Opération par seconde. Milliers de processeurs.

Solutions disponibles

Algorithmes de sommation précise :

Plus de 20 algorithmes depuis 1965. Moyenne d’un algorithme chaque 2 ans.

Solutions disponibles

Algorithmes de sommation précise :

Plus de 20 algorithmes depuis 1965. Moyenne d’un algorithme chaque 2 ans.

Objectifs :

x1 + x2 + … + xn = fl(x1 + x2 + … + xn). Minimum des opérations.

Solution proposée

Développent des BLAS Précises sans perte considérable des performances.

BLAS (Basic Linear Algebra Subroutines). Niveau 1 O(N) : ex - opérations sur les vecteurs. Niveau 2 O(N²) : ex - produit vecteur-matrice. Niveau 3 O(N3) : ex - produit matrice-matrice.

Principale difficulté : rapport Performance / Précision.

General matrix-matrix multiplication (GEMM)

Environnement :

Processeur I7 avec fréquence de 3.0 Ghz. Jeux d’instructions AVX (des registres vectoriels de taille 256 bits). Le type de données utilisé est « Binary64 (flottant double

précision ». Peak performance de 24 Gflop/s avec les flottants en double

précision « 24 milliards d’opérations sur des flottants avec double précision dans une seconde ».


Environnement :

Processeur I7 avec fréquence de 3.0 Ghz. Jeux d’instructions AVX (des registres vectoriels de taille 256 bits). Le type de données utilisé est « Binary64 (flottant double

précision ». Peak performance de 24 Gflop/s avec les flottants en double

précision « 24 milliards d’opérations sur des flottants avec double précision dans une seconde ».

C’est mon

ordinateur


Premier algorithme :

Trois boucles.



Trois boucles.

for (int i = 0; i <= M; i++)

for (int j = 0; j <= N; j++)

for (int k = 0; k <= K; k++)

C[i][j] += A[i][k] * B[k][j]



Trois boucles.



Trois boucles. Résultat : 0,32 Gflop/s (1% de peak performance).



Trois boucles. Résultat : 0,32 Gflop/s (1% de peak performance).

Pourquoi ?


Considérons cet exemple :

Matrices A, B, C de taille (8 * 8). Taille de cache 256 octets. Taille de ligne de cache 32 octets. Politique de remplacement des lignes de cache (LRU). Le cache est (fully associative). Nombre des entrées de TLB 8. Taille de page mémoire 32 octets.


i

k

j

k

A C

B

CacheTLB

Mémoire


X

X

X

i

k

j

k

&C00

&A00

&B00

A C

B

CacheTLB

Mémoire

i=0, j=0, k=0


X

x

x

i

k

j

k

&C00

&A00

&B00

&A01

A C

B

CacheTLB

Mémoire

i=0, j=0, k=1


x

x

x

i

k

j

k

&C00

&A00

&B00

&A01

&A02

&A03

&A04

&B40

A C

B

CacheTLB

Mémoire

i=0, j=0, k=4


x

x

x

i

k

j

k

&C00

&A05

&B00

&A06

&A07

&A03

&A04

&B40

A C

B

CacheTLB

Mémoire

i=0, j=0, k=7


x

x

x

i

k

j

k

&C00

&A05

&B00

&A06

&A07

&A03

&A04

&B40

A C

B

CacheTLB

Mémoire

i=0, j=1, k=0

Cache

miss


x

x

x

i

k

j

k

&C00

&A05

&B00

&A06

&A07

&A03

&A04

&B40

A C

B

CacheTLB

Mémoire

i=0, j=1, k=0

Cache

miss

TLB

miss


Solution proposée :

La solution est proposée par Kazushige GOTO (voir Goto K et al. Dans les références) et de décomposer la matrice en suivant les ressources disponibles.


i

k

j

k

A C

B

CacheTLB

Mémoire


i

k

j

k

A C

B

CacheTLB

Mémoire

A(00)

A(10)

A(01)

A(11) C(1)

C(0)

B(1)

B(0)


i

k

j

k

A C

B

CacheTLB

Mémoire

A(00)

A(10)

A(01)

A(11) C(1)

C(0)

B(1)

B(0)

C(0) += A(00) * B(0) + A(01) * B(1)


i

k

j

k

A C

B

CacheTLB

Mémoire

A(00)

A(10)

A(01)

A(11) C(1)

C(0)

B(1)

B(0)


i

k

j

k

A C

B

CacheTLB

Mémoire

A(00)

A(10)

A(01)

A(11) C(1)

C(0)

B(1)

B(0)

C(1) += A(10) * B(0) + A(11) * B(1)

Inner-kernels

i

k

j

k

A C

B

CacheTLB

Mémoire

Inner-kernels

i

k

j

k

A C

B

CacheTLB

Mémoire

Inner-kernels

x

x

x

i

k

j

k

&C00

&A00

&B00

A C

B

CacheTLB

Mémoire

j=0, k=0, i=0

Inner-kernels

x

x

x

i

k

j

k

&C00

&A00

&B00

A C

B

CacheTLB

Mémoire

j=0, k=0, i=3

Inner-kernels

x

x

x

i

k

j

k

&C00

&A00

&B00

&A01

&A02

&A03

A C

B

CacheTLB

Mémoire

j=0, k=3, i=3

Inner-kernels

x

X

x

i

k

j

k

&C00

&A00

&B00

&A01

&A02

&A03

&C01

&B01

A C

B

CacheTLB

Mémoire

j=1, k=0, i=0

Inner-kernels

x

x

x

i

k

j

k

&C00

&A00

&B00

&A01

&A02

&A03

&C01

&B01

A C

B

CacheTLB

Mémoire

j=1, k=3, i=3

Inner-kernels

X

x

x

i

k

j

k

&C02

&A00

&B02

&A01

&A02

&A03

&C01

&B01

A C

B

CacheTLB

Mémoire

j=2, k=0, i=0

Inner-kernels

x

x

x

i

k

j

k

&C02

&A00

&B02

&A01

&A02

&A03

&C01

&B01

A C

B

CacheTLB

Mémoire

j=2, k=3, i=3

Comparaison

Algorithme 1 Algorithme 2

Cache misses 704 (24) 80 (24)

Flop / Caches misses 1024 / 704 = 1,45 1024 / 80 = 12,8

Opérations vectorielles

+=

*

+=

*

+=

*

+=

*

Opérations vectorielles

+=

*

Comparaison avec Intel MKL 11.0

Objectifs de première année

Choisir un bon algorithme de sommation. Développement des BLAS précises et performants. SCAN 2014 (Université de Würzburg, Allemagne).

Bibliographie

Goto, K. & van de Geijn, R. A. Anatomy of high-performance matrix multiplication. ACM Trans. Math. Softw. 34, 3, Article 12. 2008.

Muller, J. M. & al. Handbook of floating-point arithmetic. 2010. Robert A. VAN DE GEIJN & Field G. VAN ZEE. BLIS : a modern alternative to

the BLAS.

Education

Reproductibilité numérique pour l'HPC exascale