Sujets de recherche - CDA

L'équipe CDA produit des contributions à deux grands défis des domaines du calcul intensif, du calcul parallèle et du calcul distribué :

la quête d’algorithmes parallèles ou distribués efficaces qui passent à l'échelle ;

la facilité d’utilisation des architectures massivement parallèles ou distribuées.

Certains scientifiques comme Rodney Brooks considèrent que ces défis sont parmi les plus importants en informatique et que le futur de cette science et de nombreuses sciences liées au développement des systèmes informatiques dépend grandement des réponses qui seront apportées à ces défis.

A. Défi lié à la quête d’algorithmes parallèles ou distribués efficaces qui passent à l'échelle

A.1. Calcul sur GPU

L'équipe CDA contribue à la conception et à l'analyse d'algorithmes parallèles utilisant des accélérateurs de calcul de type GPU pour la résolution de problèmes NP-complets en optimisation combinatoire. L’introduction du calcul généraliste sur accélérateurs de calcul de type processeur graphique est relativement récente. Avant 2007-2008, les processeurs graphiques qui équipaient les cartes graphiques des machines étaient dédiées à des tâches graphiques. Avec l’introduction de nouveaux outils de programmation comme CUDA ou OpenCL, les GPUs qui possèdent un nombre important de coeurs de calcul ont commencé à être utilisés comme des accélérateurs de calcul en collaboration avec le CPU pour des applications de calcul intensif en science et ingénierie. Il y a eu notamment de très nombreuses applications du calcul parallèle sur GPU en traitement du signal et en algèbre linéaire. A titre d’exemple, le GPU Tesla K40 basé sur l'architecture NVIDIA Kepler de l'équipe CDA possède 2880 cœurs de calcul et à une performance maximale simple précision en virgule flottante de 4,29 Tera Flops. Aussi, la majorité des constructeurs ont adopté ces architectures parallèles à des fins d’accélération pour certaines de leurs machines. De part le monde, certains constructeurs de supercalculateurs ont aussi conçu des machines massivement parallèles à base de GPUs qui ont intégré le Top 10 des supercalculateurs comme la machine Titan à Oak Ridge National Laboratory, USA en 2012 ou la machine Tianhe-1A à Tianjin Chine. L’attractivité du calcul sur GPU est donc très récente. Elle est par ailleurs très importante et touche maintenant tous les domaines d’application en science et ingénierie. Parmi les domaines les plus importants on citera l’astrophysique, la séismique, le pétrole, le nucléaire. L’utilisation de GPUs à des fins d’accélération de calculs généralistes présente de nombreux intérêts :
- les GPUs sont des accélérateurs de calcul puissants du fait de leur nombre important de coeurs,
- les GPUs sont largement répandus ; ils constituent donc des accélérateurs relativement bon marché,
- les GPUs consomment moins d’énergie que d’autres solutions disponibles sur le marché.

L'équipe CDA a obtenu des résultats  importants pour des problèmes de la famille du sac à dos dans un contexte du GPU computing. Nous avons proposé en particulier divers algorithmes parallèles  de Programmation Dynamique, de Branch and Bound et du Simplexe dans des contextes de GPU computing ou multi-GPUs. Ces algorithmes parallèles ont permis de réduire le temps de calcul par un facteur 50. Ces travaux ont été cités plus de cent fois en un an et demi. Les travaux de recherche de CDA ont reçu le soutien de NVIDIA Corporation qui est l'un des l'un des plus grands fournisseur de cartes graphiques. Didier El Baz a été récipiendaire d'un  NVIDIA Academic Partnership au mois d'Octobre 2010 qui était accompagné du don de deux accélérateurs de calcul C2050 possédant chacun 448 cœurs de calcul (cf. NVIDIA Academic Partnership). Le soutien de NVIDIA aux recherches de Didier El Baz a été renouvelé au mois de Juillet 2014 avec la donnation d' un GPU Tesla K40.

A.2 Algorithmique itérative parallèle ou distribuée asynchrone

Le défi du passage à l'échelle en algorithmique parallèle ou distribuée repose principalement sur le maintien de l'efficacité des algorithmes. Les périodes d'inactivités des processeurs ou des machines peuvent nuire grandement au parallélisme massif ou à la distribution massive des calcul ; ceci est particulièrement notable pour les problèmes dont la résolution nécessite l'utilisation de méthodes itératives parallèles ou distribuées comme en simulation numérique ou en optimisation. L'équipe CDA poursuit des recherches sur les algorithmes itératifs asynchrones. En effet, il semble peu réaliste de synchroniser des processeurs ou des machines dans un contexte de parallélisme massif ou de distribution massive des calculs. Les itérations asynchrones sont particulièrement adaptées au contexte du calcul sur réseau et du calcul pair à pair ainsi qu'à des contextes pour lesquel les charges de calcul sont naturellement déséquilibrées.  Nous effectuons des études pour des applications distribuées temps réel sur architectures dédiées (projet ANR PSIROB Smart Surface, ANR-06-ROBO-0009-03 et projet ANR Smart Blocks, ANR-2011-BS03-005) ou pour des applications de calcul intensif sur architecture généraliste. Nous étudions la convergence, la détection de la convergence, la mise en œuvre et la terminaison des algorithmes itératifs asynchrones pour diverses applications en optimisation ou en simulation numérique (cf. Publications récentes). Ces travaux mèlent des aspects traditionnels de cette discipline, comme la conception d’algorithmes distribués pour la détermination de l’état global d’un système à des fins de terminaison par exemple, à des aspects plus récents liés à la résolution de problèmes complexes ou de grande dimension en optimisation combinatoire, en commande optimale ou en simulation numérique via des techniques comme le calcul pair à pair ou le calcul sur réseau dans des contextes massivement distribués.

B. Défi lié à la facilité d’utilisation des architectures massivement parallèles ou distribuées.

L'équipe CDA a étudié plus particulièrement un environnement décentralisé qui facilite la mise en œuvre de calculs distribués pair à pair (c'est-à-dire pour lequels chaque nœud de calcul participant à une application peut être tour à tour client et serveur de cette application) et qui permettent la communication directe entre les pairs. Nous nous sommes intéressés aux applications issues de la simulation numérique ou de l'optimisation qui présentent un parallélisme de tâche et requièrent une résolution au moyen de méthodes itératives distribuées. L'environnement décentralisé P2PSAP que nous avons conçu et développé repose sur le protocole de communication auto adaptatif P2PSAP que nous avons conçu comme une extension de CTP (Configurable Transport Protocol). Le protocole P2PSAP s'adapte à un contexte multi réseau : Ethernet, Infiniband et Myrinet. Il s'adapte aussi en fonction d'éléments de la couche application comme le type de schéma itératif sélectionné et d'éléments de contexte de la couche réseau comme la topologie du réseau. Ces études ont été effectuées dans le cadre du projet ANR CIS  Calcul Intensif Pair à pair, CIP (ANR-07-CIS7-011) dont Didier El Baz été le porteur et le coordonnateur (cf. Projet ANR CIP).

 

Algorithmes itératifs asynchrones          Facilité d'utilisation des architectures massivement parallèles          Publications récentes          Mémoires          Benchmarks