Parallélisation d’algorithmes de fouille de données

Malgré l’amélioration constante des algorithmes d’exploration et d’extraction de caractéristiques des grandes bases de données, les besoins en terme de puissance de calcul et de capacité mémoire sont de plus en plus importants. Les deux principales raisons sont d’une part l’accroissement régulier de la taille des bases à explorer d’autre part la volonté de traiter les données sous forme de flux continus, en temps-réel (ou presque). Une première approche, à moyen terme, repose sur les travaux formels au niveau algorithmique pouvant conduire à des mises en œuvre plus rapides et moins consommatrices de mémoire. Nous nous intéressons à une approche à plus court terme consistant à optimiser et paralléliser l’exécution des algorithmes existants. Dans un premier temps, la démocratisation actuelle des architectures à mémoire partagée (à base de processeurs multi-cœurs) combinée à une parallélisation multi-threads des programmes existants permet d’envisager des solutions d’accélération à coût très faible. Les problématiques principales concernent alors la gestion mémoire, le découpage des tâches et l’équilibrage de la charge sur un grand nombre d’unités de calculs. Dans un second temps, l’exploitation de clusters de stations de calcul (architectures à mémoire partagée) devrait nous permettre d’envisager le traitement de bases beaucoup plus volumineuses grâce à une plus grande extensibilité de l’architecture (d’abord en terme de mémoire mais aussi de puissance de calcul). La principale problématique relève ici de la distribution des données sur les différentes stations et l’équilibrage de la charge.

Travaux actuels et collaborations.

 Nos travaux concernent actuellement la parallélisation en mémoire partagée d’un algorithme de recherche d’itemsets graduels (qui représentent une forme de co-variation) au sein de bases de données numériques. Ils sont réalisés en collaboration avec A. Laurent (équipe TaToo / LIRMM- Montpellier) et A. Termier, (LIG – Grenoble). Les premiers résultats sont très encourageant. Nous envisageons ensuite l’utilisation d’architectures à mémoire distribuée pour le traitement de très grandes bases.