lundi 17 juin 2013

Programmation parallèle sous R

Les ordinateurs personnels sont de plus en plus performants. Ils sont maintenant pour la plupart dotés de processeurs multi-cœurs. Dans le même temps, les logiciels grands publics de Data Mining, libres ou non, restent souvent monothread. Un seul cœur est sollicité durant les calculs, tandis que les autres restent inactifs. Ca fait un peu gaspillage.

Récemment, nous avons introduit deux variantes multithread de l’analyse discriminante linéaire dans Sipina 3.10 et 3.11. Après une analyse succincte de l’algorithme, nous nous sommes concentrés sur la construction de la matrice de variance covariance intra-classes qui semblait constituer le principal goulot d’étranglement du processus. Deux types  de décomposition des calculs ont été proposés, que nous avons exploité en nous appuyant sur la programmation multithread sous Delphi (langage de développement de Sipina). Nous avons constaté que l’amélioration des performances par rapport à la version séquentielle est spectaculaire lorsque l’ensemble des cœurs disponibles sur la machine sont pleinement utilisés.

Durant le travail d’analyse qui m’a permis de mettre au point les solutions introduites dans Sipina, j’avais beaucoup étudié les mécanismes de parallélisation disponibles dans d’autres outils de Data Mining. Ils sont plutôt rares en réalité. J’avais quand même noté que des stratégies très perfectionnées sont proposées pour le logiciel R. Il s’agit souvent d’environnements qui permettent d’élaborer des programmes tirant parti des capacités étendues des machines à processeurs multi-cœurs, multiprocesseurs, et même d’un cluster de machines. Je me suis intéressé en particulier au package « parallel »  qui est lui-même une émanation des package « snow »  et « multicore » . Entendons-nous bien, la librairie ne permet pas d’accélérer miraculeusement une procédure existante. En revanche, elle nous donne l’opportunité d’exploiter efficacement les ressources machines à condition de reprogrammer la procédure en réorganisant judicieusement les calculs. L’idée maîtresse est de pouvoir décomposer le processus en tâches que l’on peut exécuter en parallèle, charge à nous par la suite d’effectuer la consolidation.

Dans ce tutoriel, nous détaillons la parallélisation d’un algorithme de calcul d’une matrice de variance covariance intra-classes sous R 3.0.0. Dans un premier temps, nous décrivons un programme séquentiel, mais facilement transformable. Dans un deuxième temps, nous utilisons les outils des packages « parallel » et « doParallel » pour lancer les tâches élémentaires sur les cœurs disponibles. Nous comparerons alors les temps de traitement. Disons-le d’emblée, contrairement aux exemples jouets que l’on peut consulter ici ou là sur le web, le bilan est passablement mitigé quand il s’agit de traiter des bases volumineuses réalistes. Les solutions achoppent sur la gestion des données.

Mots-clés :  analyse discriminante linéaire, logiciel R, package parallel, package doparallel, parLapply, mclapply, foreach
Didacticiel : fr_Tanagra_Parallel_Programming_R.pdf
Fichiersparallel.R, multithreaded_lda.zip
Références :
R-core, Package 'parallel', April 18, 2013.

mardi 4 juin 2013

Multithreading équilibré pour la discriminante

Dans le document « Multithreading pour l’analyse discriminante », nous présentions une implémentation multithread de l’analyse discriminante à destination des machines à processeurs multi-coeurs ou multiprocesseurs. A occupation mémoire égale par rapport à la version séquentielle, elle permettait de réduire les temps de calculs dans des proportions considérables en fonction des caractéristiques des données. La solution présentait néanmoins deux faiblesses : le nombre de coeurs utilisé était tributaire du nombre de classes K dans la base à traiter ; l’équilibrage des charges entre les cœurs dépendait de leur fréquence. Ainsi, sur une des bases d’expérimentation avec K = 2 classes très fortement déséquilibrées, le gain était quasi-nul par rapport à la version monothread.

Dans ce tutoriel nous présentons une nouvelle solution implémentée dans Sipina 3.11. Au prix d’une occupation mémoire accrue, que nous préciserons, elle permet de surmonter les deux goulots d’étranglement pointés sur la version précédente. Les capacités de la machine sont pleinement utilisées. Plus intéressant même, le nombre de threads devient paramétrable, permettant à l’utilisateur d’adapter les ressources machines à exploiter pour le traitement des données.

Pour mieux situer les améliorations induites par notre stratégie, nous comparons nos temps d’exécution avec la version multithread parcimonieuse en mémoire développée précédemment, la version séquentielle, et la référence SAS 9.3 (proc discrim).

Mots-clés : sipina, multithreading, thread, multithreaded data mining, multithread processing, analyse discriminante prédictive, analyse discriminante linéaire, sas, proc discrim
Didacticiel : fr_Tanagra_Sipina_LDA_Threads_Bis.pdf
Données : multithreaded_lda.zip
Références :
Tanagra, "Multithreading pour les arbres de décision".
Tanagra, "Analyse discriminante linéaire - Comparaisons".
Wikipédia, "Analyse discriminante linéaire".