the Next Step ?

Un programme parallèle est un programme qui a été conçu pour être exécuté simultanément par plusieurs processeurs. L’intérêt d’un programme parallèle est qu’il est beaucoup plus rapide que son équivalent non parallèle (gain pouvant aller jusqu’à un facteur de 1000 [ref]). R++ s’intéresse à trois sources de parallélisme, exploitables sur les ordinateurs de bureaux modernes : le multi cœur, la carte graphique et le cloud.

Le multi-cœur est le fait d’utiliser en parallèle tous les cœurs (CPU) d’un ordinateur (la plupart des ordinateurs de bureau modernes sont maintenant dotés d’au moins 2, voir 4 ou 8 cœurs). Les cartes graphiques (GPU) sont des unités de calculs massivement parallèles (milliers de processeurs). Ces processeurs sont dotés d’une mémoire de très petite taille, ce qui peut être un handicap dans un cadre général, mais qui ne gêne pas dans le cas spécifique de calculs mathématiques comme la résolution de systèmes linéaires. Enfin, le cloud est un réseau d’ordinateurs connectés.

Premiers tests : bootstrap parallèle

Dans le cadre de son stage de Master 2, Chai Anchen a comparé l’efficacité du bootstrap en utilisant différents langages et architectures.

Méthode

Le bootstrap est une technique statistique de ré-échantillonnage. On dispose d’une population sur laquelle on souhaite calculer une certaine statistique S, potentiellement compliquée. On souhaite obtenir un intervalle de confiance autour de S mais les techniques statistiques classiques ne nous permettent pas d’obtenir un tel intervalle. On va l’obtenir via un boot strap. Le boot strap fonctionne de la manière suivante :

  1. On échantillonne (avec remise) la population. On obtient un echantillon i
  2. Sur l’échantillon i, on calcule l’indice statistiques S(i)
  3. On itère 1 et 2 un grand nombre de fois.

L’ensemble de tous les S(i) suit une distribution qui nous permet ensuite de définir l’intervalle de confiance. Cette méthode est à la fois coûteuse en temps (si les données sont de grande taille ou si S est compliqué à calculer) et facilement parallélisable.

Logiciels et matériel

Les langages et architectures testés sont : R, R avec le package Boot multi-cœur, C mono-cœur, C via la carte graphique et C multi-cœur (6, 8, 10 et 12). Les processeurs utilisés sont :

  • CPU : Intel Xeon E5645@2.4Ghz
  • GPU : Tesla C2050, 3GB, 1.15GHz
  • Multi-cœur : 12 cœurs Intel Xeon E5645@2.4Ghz

Pour notre test, la statistique S est simplement la moyenne d’un vecteur de n flottants générés aléatoirement entre 0 et 100. La taille du vecteur n varie de 100 à 1 000 000.

Résultats

Pour chaque taille de vecteur nous avons calculé le temps d’exécution brut, puis relativement à un temps de référence (C en utilisant CPU). Les résultats sont les suivant :

resultBoot

Analyse

Sans surprise, on constate que C est plus rapide que R (CPU > R et MC > Boot)

Concernant les performances de la GPU et du Multi-cœur, elles sont meilleures que celle de la CPU pure mais seulement à partir d’un certain volume de données. En deçà, les temps de communication avec la carte graphique ou de fusion des résultats présentent un coût plus important que celui du temps de calcul (!) et ralentissent l’ensemble de l’opération. A noter, cela n’enlève rien à l’intérêt du parallélisme qui de manière générale est efficace sur des grandes données, justement là où les méthodes classiques montrent leur limites.

 

Deuxième test : Imputations multiples

Méthode

L’imputation multiple est une méthode permettant de pratiquer des analyses statistiques sur des jeux de données incomplets sans provoquer une sous-estimation de la variance. Le principe est le suivant :

  1. Initialiser toutes les valeurs manquantes. Si une valeur est manquantes, nous la remplaçons aléatoirement par une des valeurs possibles. Cela conduit a un jeu de données complet.
  2. « Prédire » (via une régression linéaire) la première variable à qui il manque des valeurs par toutes les autres. Les valeurs manquantes initiales de la première variable sont remplacées par les valeurs prédites par la régression.
  3. Itérer le processus à toutes les variables. A chaque fois, remplacer les valeurs manquantes par les valeurs prédites par le modèle.
  4. Répéter 1), 2), 3) plusieurs fois

Ensuite, l’analyse est conduite sur le jeu de données ainsi complété.

Il est possible d’effectuer l’ensemble de l’opération plusieurs fois et d’obtenir « plusieurs » jeux de données ainsi complété. Les résultats sont ensuite « poolés », ce qui permet d’avoir un contrôle sur leur stabilité.

Logiciels et matériel

Les langages et architectures testés sont: R avec le package MICE, C mono-cœur, C via la carte graphique(CUDA) et C multi-cœur(6,8,10 et 12). Les processeurs utilisés sont :

  • CPU : Intel Xeon E5645@2.4Ghz
  • GPU : Tesla C2050, 3GB, 1.15GHz
  • Multi-cœur : 12 cœurs Intel Xeon E5645@2.4Ghz

Pour notre test, des matrices de différentes tailles ont été étudiées: le nombre de variables varie de 100 à 1 000 et le nombre d’observations de chaque variable varie de 1 000 à 1 000 000. Pour chaque taille de matrice, nous avons généré 10% de valeurs manquantes et le nombre d’imputations M a été fixé à 5.

Résultats

Pour chaque taille de problème nous avons calculé le temps d’exécution brut, puis relativement à un temps de référence (C en utilisant CPU). Les résultats sont les suivants :

resultImputations

Analyse

Comme nous avons prévu, R (mice) est assez coûteuse, surtout quand on travaille sur des matrices de grandes tailles (plus 100h pour 1 000 x 10 000 contre 200s avec une GPU).

Concernant la performance GPU, elle n’est pas très bonne pour les matrices de petite taille (10 variables), mais quand la taille augmente, ses performances s’améliorent. Cela s’explique par le fait qu’il existe des calculs très intensifs dans cette méthode, comme la multiplication matricielle, la résolution de système linéaire…

Documents téléchargeables

Le mémoire de Chai Anchen, détaillant l’intégralité des méthodes et résultats présentés ci-dessus, est téléchargeable ici.

A suivre : axe Big Data