Ordonnancement : solution exacte vs approximée, que gagne-t-on réellement ?

Encadrants : 

Occurrences : 

2018

Nombre d'étudiants minimum: 

2

Nombre d'étudiants maximum: 

3

Nombre d'instances : 

1

Le but de ce  projet est d'implémenter deux logiques de calcul d'ordonnancement (c'est un travail théorique), l'une exacte, l'autre approximée (via optimisation par algorithme génétique). 

Le principe du problème se rapproche d'un problème de remplissage de sac à dos en plus compliqué et contraint. L'application de ces résultats est de permettre de déployer plus de logiciel sur des plateformes embarquées tout en garantissant des temps de réponses stricts. 

Le déploiement de logiciel sur système embarqué est très contraint. Il faut souvent s'assurer à priori que les calculs désirés puissent se terminer dans des délais stricts même dans les pires situations (données plus complexes, forte demande de ressources matérielles...). Pour arriver à ce genre de garanties (temps de réponse borné) le logiciel est structuré en tâches ayant des périodicités et des échéances connues à l'avance. De plus, on évalue le pire temps d'exécution de ces tâches en fonction du processeur choisi pour le déploiement. Ceci donne naissance à des problèmes théoriques dit d'ordonnancement ou allocation.  Dans ce genre de systèmes, il possible et souvent nécessaire de déterminer à l'avance combien de cœurs d'exécution seront requis pour garantir le respect des échéances pour chaque calcul mené. Cette estimation sert usuellement à vérifier que le matériel peut héberger le logiciel conçu. 

Le déroulement du projet sera le suivant : 

  • Acquisition des connaissances élémentaires en ordonnancement et appropriation des concepts clés : utilization, demand bound and supply bound functions, criticality levels/modes  (notez  que nous vous demanderons de respecter un vocabulaire anglophone dans ce projet ce qui évitera les ambigüités de traduction. 
  • Mise au propre de la version exacte de l'algorithme d'allocation dit "des serveurs modaux" permettant de déterminer l'ordonnancement optimisé d'un ensemble de tâches. (Rédaction d'un document).
  • Implémentation de la version exacte 
  • En fonction du temps restant implémentation de la version heuristique de l'algorithme d'allocation optimisant le nombre de processeurs requis. (nous en possédons une déjà mais il y a surement des améliorations possibles). 
  • Comparaison des solutions exactes et heuristiques (qualité du résultat, temps d'exécution, empreinte mémoire).
  • Rédaction d'un document + vous serez formé à la construction d'expériences répétables automatiquement -- via l'usage de scripts essentiellement.