Real-time scheduling for media processing using conditionally guaranteed budgets

Abstract

In dit proefschrift behandelen we een planningsprobleem dat haar oorsprong vindt in het kosteneffectief verwerken van verschillende media door software in consumentenapparaten, zoals digitale televisies. De laatste jaren zijn er trends gaande van analoge naar digitale systemen, en van verwerking van digitale signalen door speci??eke, toepassingsgerichte hardware naar verwerking door software. Voor de verwerking van digitale media door software wordt gebruik gemaakt van krachtige programmeerbare processoren. Om te kunnen wedijveren met bestaande oplossingen is het van belang dat deze programeerbare hardware zeer kosteneffectief wordt gebruikt. Daarnaast dienen de bestaande eigenschappen van deze consumenten apparaten, zoals robuustheid, stabiliteit, en voorspelbaarheid, behouden te blijven als er software wordt gebruikt. Verder geldt dat er gelijktijdig meerdere media stromen door een consumenten apparaat verwerkt moeten kunnen worden. Deze uitdaging is binnen de onderzoekslaboratoria van Philips aangegaan in het zogenoemde Video-Quality-of-Service programma, en het werk dat in dit proefschrift beschreven wordt is binnen dat programma ontstaan. De binnen dat programma gekozen aanpak is gebaseerd op schaalbare algoritmen voor de verwerking van media, budgetten voor die algoritmen, en software dat de instelling van die algoritmen en de grootte van de budgetten aanpast tijdens de verwerking van de media. Ten behoeve van het kosteneffectief gebruik van de programmeerbare processoren zijn de budgetten krap bemeten. Dit proefschrift geeft een uitvoerige beschrijving van die aanpak, en van een model van een apparaat dat de haalbaarheid van die aanpak aantoont. Vervolgens laten we zien dat die aanpak leidt tot een probleem wanneer er gelijktijdig meerdere stromen worden verwerkt die verschillende relatieve relevanties hebben voor de gebruiker van het apparaat. Om dit probleem op te lossen stellen we het nieuwe concept van voorwaardelijk gegarandeerde budgetten voor, en beschrijven we hoe dat concept kan worden gerealiseerd. De technieken voor het analyseren van het planningprobleem voor budgetten zijn gebaseerd op bestaande technieken voor slechtste-gevals-analyse voor periodieke real-time taken. We breiden die bestaande technieken uit met technieken voor beste-gevals-analyse zodat we apparaten die gebruik maken van dit nieuwe type budget kunnen analyseren.