Home > Research > Stages/emplois > [Master 2 Recherche] Ordonnancement de processus sous contrainte de (...)

[Master 2 Recherche] Ordonnancement de processus sous contrainte de pipeline

Wednesday 18 October 2017

Résumé

Les opérateurs arithmétiques à virgule flottante utilisés dans les accélérateurs matériels sont pipelinés pour ne pas limiter la fréquence du circuit. Une opération i produit son résultat à la date i+k, avec k le nombre d’étages du pipeline. Si le résultat de i est utilisé par une opération j, j devra attendre que le résultat soit disponible: j>i+k (contrainte de pipeline). Dans le cas contraire, le pipeline de j sera bloqué jusqu’à ce que la donnée soit disponible. L’ordonnancement sous contrainte de pipeline consiste à réorganiser les opérations pour réduire le temps total d’exécution tout en respectant les contraintes de pipeline. Ce problème est connu pour être NP-complet sur les codes sans tests ni boucles bien que la solution exacte par programmation entière ait un temps d’exécution acceptable en pratique.

Dans ce stage, on se propose d’étudier l’ordonnancement sous contrainte de pipeline d’un réseau de processus régulier: un ensemble de processus communicants par des canaux, chaque processus exécutant un opérateur arithmétique avec un contrôle prédictible à la compilation. Plus précisément, on cherchera à:

- Prédire/borner la marge d’optimisation en supposant une utilisation optimale des pipelines.
- Construire un algorithme qui trouve un ``bon’’ ordonnancement pour chaque processus.

Les résultats seront validés sur les applications de Polybench/C.

Détails: Voir la pièce-jointe.

Attached documents

  • 18 October 2017
    info document : PDF
    79.6 kb

Valid XHTML 1.0 Transitional
SPIP | | Site Map | Follow site activity RSS 2.0
Graphic design (c) styleshout under License Creative Commons Attribution 2.5 License