Direction de recherche : Claire HANEN

Étude du problème RCPSP cyclique

La constante évolution des architectures des processeurs à haute performance, afin de répondre aux exigences des applications embarquées, donnent de plus en plus d'importance à une programmation plus performante, surtout au niveau de la compilation, dans ces systèmes. Notre étude est particulièrement motivée par l'optimisation de l'ordonnancement lors de la compilation des instructions dans les processeurs de type VLIW (Very Large Instruction Word), et sa résolution à l'aide du RCPSP (Resource Constrained Project Scheduling Problem) cyclique. Dans un tel model, on dispose en général d'un petit nombre d'unités fonctionnelles indépendantes et qui peuvent exécuter plusieurs tâches simultanément si les dépendances de données s'y prêtent et si les ressources nécessaires sont disponibles. Aujourd'hui, les études théoriques dans le domaine d'ordonnancement cyclique visent à caractériser les algorithmes d'ordonnancement (analyses du pire cas, résultat d'optimalité, etc) pour des applications réelles aussi bien dans les systèmes embarqués que dans les systèmes de production. Dans le cadre de cette thèse, nous avons travaillé sur la détermination de modèles appropriés, capables de prendre en compte les nouvelles caractéristiques de ces systèmes (la nature des dépendances, l'hétérogénéité des ressources, etc.). Plusieurs algorithmes approchés avec garanties de performance ont été proposés, ainsi qu'une étude expérimentale, afin d'analyser leur efficacité en pratique, a été établie.

Publications 2008-2013

• 2013
  • M. Ayala, A. Benabid, Ch. Artigues, C. Hanen : “The resource-constrained modulo scheduling problem: an experimental study”, Computational Optimization and Applications, vol. 54 (3), pp. 645-673, (Springer Verlag) (2013)
• 2012
  • A. Benabid, C. Hanen, O. Marchetti, A. Munier‑Kordon : “Periodic schedules for bounded timed weighted event graphs”, IEEE Transactions on Automatic Control, vol. 57 (5), pp. 1222-1232, (Institute of Electrical and Electronics Engineers) (2012)
  • Ch. Artigues, M. Ayala, A. Benabid, C. Hanen : “Bornes inférieures et supérieures pour l’ordonnancement modulo sous contraintes de ressources”, ROADEF 2012, Angers, France (2012)
  • Ch. Artigues, M. Ayala, A. Benabid, C. Hanen : “Lower and upper bounds for the resource-constrained modulo scheduling problem”, Project management and Scheduling conference, Louvain, Belgium, pp. 82-85 (2012)
• 2011
  • A. Benabid : “Étude du problème RCPSP cyclique”, soutenance de thèse, soutenance 07/02/2011, direction de recherche Hanen, Claire (2011)
  • A. Benabid, C. Hanen : “Worst case analysis of decomposed software pipelining for cyclic unitary RCPSP with precedence delays”, Journal of Scheduling, vol. 14 (5), pp. 511-522, (Springer Verlag) (2011)
• 2010
  • A. Benabid, C. Hanen : “Performance of Garey Johnson algorithm for pipelined type tasks systems”, International Transactions in Operational Research, vol. 17 (6), pp. 797-808, (Wiley) (2010)
  • A. Benabid, C. Hanen : “Decomposed software pipelining for VLIW with precedence delays and resource constraints”, EURO conference, Lisbon, Portugal (2010)
  • A. Benabid, C. Hanen : “Minimizing lateness for precedence graphs with constant delays on dedicated pipelined processors.”, Electronic Notes in Discrete Mathematics, vol. 36 (1), pp. 791-798, (Elsevier) (2010)
  • A. Benabid, C. Hanen : “Performance of Zinder-Roper algorithm for unitary RCPSP with constant precedence latencies”, 11^e Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2010), Toulouse, France (2010)
• 2009
  • A. Benabid, C. Hanen : “Decomposed software pipelining for cyclic unitary RCPSP with precedence delays”, Multidisciplinary International Conference on Scheduling: Theory and Applications, Dublin, Ireland (2009)
  • A. Benabid, C. Hanen : “Worst case analysis on modulo scheduling for specialized processors systems”, 10^e Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2009), Nancy, France, pp. 1-12 (2009)
• 2008
  • A. Benabid, C. Hanen : “Performance of the Garey-Johnson algorithm for pipelined task systems”, ALIO/EURO conference on combinatorial optimization, Buenos Aires, Argentina (2008)
  • A. Benabid, C. Hanen, O. Marchetti, A. Munier‑Kordon : “Periodic schedules for Unitary Timed Weighted Event Graphs”, 9^e Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2008), Clermont-Ferrand, France, pp. 17-31 (2008)