Élimination des circuits nuls dans les graphes cycliques pour l'ordonnancement périodique de tâches

Résumé : Ce résultat s'inscrit dans la continuité de nos efforts précédents concernant l'ordonnancement périodique de tâches sous contraintes de stockage. Notre contexte est l'optimisation de programmes embarqués. Nos tâches représentent les instructions répétitives d'une boucle POUR d'un programme. Certaines instructions écrivent des résultats dans des registres. Un registre ne peut être libéré (et par conséquent pouvant contenir le résultat d'une autre instruction) que lorsque tous les consommateurs (i.e. lecteurs) de la donnée ont été exécutés. Le but est de trouver un ordonnancement périodique de ces instructions tel que le besoin en registres soit minimisé ou borné. Nous avons déjà apporté une étude théorique au problème [1] et mis en place une heuristique performante [2].

Cet exposé apporte une réponse à un problème ouvert pour l'optimisation de codes embarqués pour une famille spécifique de processeurs, appelés VLIW ou DSP. Dans cette famille de processeurs, les latences d'écriture et de lecture dans les registres sont visibles au niveau du programme. En d'autres termes, lorsqu'une instruction lit ou écrit dans un registre, le programme doit faire en sorte de garantir la latence d'accès en registres. Cette spécificité des processeurs VLIW ou DSP rend l'optimisation des registres plus délicate mais simplifie la conception architecturale de ces processeurs. Jusqu'à présent, il n'y a pas eu de réponse satisfaisante dans la communauté d'optimisation de codes concernant l'optimisation des registres dans ce type de processeurs. Notre modèle théorique [1] définit bien le problème mais n'a apporté qu'une solution partielle jusqu'à présent. Dans cet exposé, nous vous présentons notre dernier développement sur ce sujet en apportant une heuristique itérative se basant sur la programmation linéaire.

Type de document :
Communication dans un congrès
11e Congrès annuel de la société française de Recherche Opérationnelle et d'Aide à la Décision - ROADEF 2010, Feb 2010, Toulouse, France. 2010, 〈http://www.roadef2010.fr/〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00647687
Contributeur : Sid Touati <>
Soumis le : vendredi 2 décembre 2011 - 15:04:47
Dernière modification le : jeudi 15 février 2018 - 08:48:05
Document(s) archivé(s) le : vendredi 16 novembre 2012 - 14:11:22

Fichier

A_limination_des_circuits_nuls...
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00647687, version 1

Citation

Sébastien Briais, Karine Deschinkel, Sid Touati. Élimination des circuits nuls dans les graphes cycliques pour l'ordonnancement périodique de tâches. 11e Congrès annuel de la société française de Recherche Opérationnelle et d'Aide à la Décision - ROADEF 2010, Feb 2010, Toulouse, France. 2010, 〈http://www.roadef2010.fr/〉. 〈hal-00647687〉

Partager

Métriques

Consultations de la notice

158

Téléchargements de fichiers

124