List Scheduling in Embedded Systems under Memory Constraints

Abstract

Le décodage vidéo et le traitement d'image dans les systèmes embarqués sont sujets à de fortes contraintes de ressources, particulièrement en termes de mémoire. Les heuristiques d'ordonnancement de liste à priorités statiques (HEFT, SDC,...) étant les solutions les plus souvent citées en raison à la fois de leurs bonnes performances et de leur faible complexité, nous proposons une méthode visant à y introduire la notion de mémoire. De plus, nous montrons que par le biais d'un ajustement adapté des priorités des tâches et d'un recours judicieux à l'insertion, des accélérations jusqu'à 20% peuvent être obtenues. Enfin, nous montrons que notre technique permet d'empêcher les interblocages et de réduire significativement l'empreinte mémoire requise comparé à des heuristiques d'ordonnancement de liste classiques.