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.

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

Scolarité 2012-2013 (Travail de master)

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

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

Scolarité 2012-2013 (Travail de master)

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

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

Scolarité 2012-2013 (Travail de master)

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

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

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

Scolarité 2012-2013 (Travail de master)

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

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

Scolarité 2012-2013 (Travail de master)

Analyse sémantique d’une plateforme d’apprentissage 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.

Scolarité 2012-2013 (Travail de master)

Analyse sémantique d’une plateforme d’apprentissage 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).

Scolarité 2012-2013 (Travail de master)

Analyse sémantique d’une plateforme d’apprentissage 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.

Scolarité 2012-2013 (Travail de master)

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 ».

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 ».

C’est mon

ordinateur

General matrix-matrix multiplication (GEMM)

Premier algorithme :

Trois boucles.

General matrix-matrix multiplication (GEMM)

Premier algorithme :

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]

General matrix-matrix multiplication (GEMM)

Premier algorithme :

Trois boucles.

General matrix-matrix multiplication (GEMM)

Premier algorithme :

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

General matrix-matrix multiplication (GEMM)

Premier algorithme :

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

Pourquoi ?

General matrix-matrix multiplication (GEMM)

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.

General matrix-matrix multiplication (GEMM)

i

k

j

k

A C

B

CacheTLB

Mémoire

General matrix-matrix multiplication (GEMM)

X

X

X

i

k

j

k

&C00

&A00

&B00

A C

B

CacheTLB

Mémoire

i=0, j=0, k=0

General matrix-matrix multiplication (GEMM)

X

x

x

i

k

j

k

&C00

&A00

&B00

&A01

A C

B

CacheTLB

Mémoire

i=0, j=0, k=1

General matrix-matrix multiplication (GEMM)

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

General matrix-matrix multiplication (GEMM)

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

General matrix-matrix multiplication (GEMM)

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

General matrix-matrix multiplication (GEMM)

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

General matrix-matrix multiplication (GEMM)

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.

General matrix-matrix multiplication (GEMM)

i

k

j

k

A C

B

CacheTLB

Mémoire

General matrix-matrix multiplication (GEMM)

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)

General matrix-matrix multiplication (GEMM)

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)

General matrix-matrix multiplication (GEMM)

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)

General matrix-matrix multiplication (GEMM)

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.