-
-
-
-
-
-
-
HomeSite map
SoC/Offres d'emplois/Stages/2015-2016/ALSOC/Conception d'algorithmes parallèles pour architectures manycore Print page

Conception d'algorithmes parallèles pour architectures manycore

Equipe d’accueil : Alsoc, département SoC

Durée du stage : 6 mois

Contexte architectural

Aujourd'hui, la quasi-totalité des processeurs produits sont multi-cœurs. Depuis l'arrêt de l'augmentation de la fréquence des processeurs, le seul moyen d'augmenter leur puissance de calcul est d'augmenter leur parallélisme interne en concevant des processeurs multi-cœurs avec des extensions SIMD. Demain pour cette même raison, les processeurs seront manycore avec des registres SIMD encore plus larges.

Contexte algorithmique

Paralléliser des algorithmes sur de tels processeurs est nécessaire pour exécuter en temps réel des applications complètes afin d'avoir des systèmes en interaction avec le monde extérieur. Les algorithmes d'étiquetage en composantes connexes sont des algorithmes qui consistent à associer à chaque groupe de pixels connexes un numéro unique, l'étiquette de leur composante connexe. Ces algorithmes sont représentatifs de toute une classe d'algorithmes en traitement d'images et servent dans de nombreuses applications comme la détection de mouvement, la reconnaissance de caractères, et l'imagerie médicale. L'expertise acquise lors de leur conception serviront à faire progresser les connaissances de cette classe d'algorithmes et aideront à en concevoir d'autres.

Objectifs du stage

Le premier objectif du stage est de concevoir de nouveaux algorithmes d'étiquetage en composantes connexes pour des architectures manycore. Un certain nombre de ces algorithmes a déjà été développé pour des architectures multi-coeurs. Ces algorithmes existant serviront de base de réflexion pour la conception de ces nouveaux algorithmes. Comme ces algorithmes sont irréguliers et dépendent des données, une méthodologie
de benchmarking (déjà développée) sera mise en place pour analyser leurs performances, comme leur vitesse effective, mais aussi leur scalabilité (capacité à s'exécuter efficacement sur des machines plus parallèles). Deux architectures ont été retenues : la plateforme TSAR du LIP6 (256 cœurs) et le Xeon-Phi d'Intel (57 cœurs pour le KNC, plus de 70 pour le KNL). L'étudiant(e) sera intégré(e) à une équipe de 4 personnes qui travaille déjà sur ces différents aspects. Le dernier objectif du stage est de publier ces nouveaux algorithmes à une conférence internationale (objectif déjà réalisé précédemment).

Connaissances requises

Connaissances en informatiques : langage C, architecture des ordinateurs et système. Connaissances en traitement d'images : aucune, les algorithmes sont simples (une dizaine de ligne), c'est leur parallélisation et les problèmes intrinsèques de concurrence qu'il faudra résoudre efficacement en fonction de l'architecture.

Connaissances acquises par l'étudiant lors du stage

Techniques d'optimisations de code (transformation de haut niveau, optimisation du memory layout). Middleware et API de programmation parallèle comme OpenMP et Pthread. Connaissances architecturales poussées combinant architecture matérielle d'un processeur (cache, pipeline), architecture logicielle d'un algorithme (optimisation du memory layout pour placement de données distribuée sur chaque cœur) et utilisation des
réseaux de communication sur puce (network on chip).


Ce stage nécessite un étudiant motivé, mais en contrepartie les connaissances acquises lui permettront de pouvoir candidater à de nombreuses
thèses traitant de l'un des aspects du stage ou de postuler à des offres d'emploi de type d'ingénieur de recherche en architectures parallèles
auprès de nombreuses sociétés car celles-ci ont un manque récurrent de ce genre de profil.

Réalisation

Le stage comportera entre autres les étapes suivantes :

  • Etude et compréhension de l'architecture TSAR et des extensions du jeu d’instructions intel KNC et AVX-512
  • Prise en main du prototype virtuel SystemC de l'architecture
  • Etude et compréhension des algorithmes de traitement d’image fournis
  • Conception des algorithmes adaptés aux deux architectures parallèles
  • Validation fonctionnelle systématique des algorithmes, par l'écriture de tests appropriés
  • Evaluation des performances et de la scalabilité des algorithmes sur chacune des architectures

Poursuite en thèse Possible en fonction des résultats

Contacts

LIP6/SoC Lionel Lacassagne, Quentin Meunier, Franck Wajsburt, Alain Greiner (prénom.nom@lip6.fr)

Bibliographie

[ICIP2015] "Parallel Light Speed Labeling: an Efficient Connected Component Labeling Algorithm for Multi-Core Processors". International Conference on Imape Processing (ICIP), Laurent Cabaret, Lionel Lacassagne, Daniel Etiemble
[DASIP2012] "On the scalability of omega and signal processing parallel application on emerging CC-NUMA many-cores". Ghassan Almaless and Franck Wajsburt. International Conference on Design and Architectures for Signal and Image Processing

LIP6 LIP6-SoC LIP6 CNRS UPMC