Periodic scheduling for cache-miss minimisation

R.A.W. Clout

Research output: ThesisPhd Thesis 2 (Research NOT TU/e / Graduation TU/e)

94 Downloads (Pure)

Abstract

In dit proefschrift behandelen we een meerdimensionaal periodiek planningsprobleem.Dit probleem vindt zijn oorsprong in de videosignaalbewerking. Algoritmen voor de bewerking van videosignalen beschouwen we als verzamelingenoperaties die periodiek uitgevoerd moeten worden met zeer hoge frequentie. Daartoe moeten snelle processoren gebruikt worden. De verwerkingssnelheid van deze processoren is in de afgelopen jaren toegenomen met meer dan 50% op jaarbasis.De geheugens waarvan deze processoren gebruik maken zijn jaarlijks slechts 7%sneller geworden, waardoor beide uit de pas gaan lopen. Een standaard oplossing om dit verschil in snelheid te overbruggen is het toevoegen van cachegeheugen tussen de processor en het geheugen. Een cachegeheugen is een snel maar klein buffer dat tussenresultaten van een berekening kan opslaan. De vraag hoe een cachegeheugen optimaal benut wordt kan gezien worden als een planningsprobleem.Het effectief oplossen van dit probleem is echter nog een open vraagstuk.Het planningsprobleem bestaat eruit om twee toekenningen te vinden, te weten een tijdstoekenning en een geheugentoekenning. De tijdstoekenning representeert de volgorde waarin de operaties uitgevoerd moeten worden. Van deze toekenningeisen we dat operaties in een zodanige volgorde plaatsvinden dat tussenresultaten berekend worden voordat ze worden gebruikt. De geheugentoekenning legt voor ieder tussenresultaat in de berekening een geheugenplaats vast. Van deze toekenningeisen we dat een geheugenplaats waar een tussenresultaat opgeslagen is niet overschreven wordt voordat dit tussenresultaat voor de laatste maal gebruikt is.Verder eisen we van de toekenningen dat het cachegeheugen optimaal gebruikt wordt, hetgeen we vertalen in een minimalisatie van het aantal cache misses.We hebben aangetoond dat dit planningsprobleem formeel lastig is. De lastigheid wordt enerzijds veroorzaakt door de beperkingen die opgelegd worden aan de tijdstoekenning en geheugentoekenning. Anderzijds blijkt het lastig om voor een gegeven tijdstoekenning, geheugentoekenning en cachegeheugen, het aantal cache misses uit te rekenen.Elke tijdstoekenning bepaalt een volgorde waarin de operaties uitgevoerd moeten worden. Helaas kunnen niet alle tijdstoekenningen op een efficiente wijze uitgevoerd worden worden door een processor. Om de verzameling tijdstoekenningen in te perken tot toekenningen die een efficiente afbeelding toestaan, leggen we aanvullende beperkingen op.De kern van het proefschrift wordt gevormd door een discussie over het berekenen van het aantal cache misses voor een gegeven tijdstoekenning en geheugentoekenning.Deze berekening doet later dienst als een middel om verschillende toekenningen met elkaar te kunnen vergelijken. Aangezien het bepalen van het aantal cache misses een formeel lastig probleem is, beschouwen we hiervoor een benaderingsalgoritme. Daartoe hebben we het probleem in twee delen gesplitst. In het eerste deel proberen we zo goed mogelijk het hergebruik van tussenresultaten te bepalen, hetgeen gemeten wordt in de tijd die verstrijkt tussen twee opeenvolgende momenten waarop een tussenresultaat gebruikt wordt. In het tweede deel benaderen we de vulling van het cachegeheugen. De vulling geeft een tijdspanne aan waarin alle tussenresultaten zich nog in het cachegeheugen bevinden. We laten zien dat op basis van het hergebruik en de vulling het aantal cache misses berekend kan worden. Gebaseerd op deze opsplitsing hebben we een benaderingsalgoritme ontworpen.Het resulterende algoritme voor het benaderen van het aantal cache misses hebben we geimplementeerd en gebruikt voor een aantal experimenten. We hebben laten zien dat we het aantal cache misses goed kunnen benaderen in rekentijden die veel kleiner zijn dan de tijden die nodig zijn voor een zogenaamde cachesimulatie.Tenslotte hebben we een eerste stap gedaan in de richting van een lokaalzoekalgoritme voor het planningsprobleem. De basis voor het algoritme wordt gevormd door het benaderingsalgoritme voor het aantal cache misses. De zoekruimte, die nodig is voor lokaal zoeken, wordt opgespannen door veranderingen n de tijdstoekenning en geheugentoekenning. Voor deze veranderingen stellen wij technieken voor die bekend zijn uit de literatuur.
Original languageEnglish
QualificationDoctor of Philosophy
Awarding Institution
  • Mathematics and Computer Science
Supervisors/Advisors
  • Aarts, Emile H.L., Promotor
  • Rem, Martin, Promotor
  • Verhaegh, W.F.J., Copromotor
Award date27 Aug 2001
Place of PublicationEindhoven
Publisher
Print ISBNs90-74445-49-7
DOIs
Publication statusPublished - 2001

Fingerprint

Dive into the research topics of 'Periodic scheduling for cache-miss minimisation'. Together they form a unique fingerprint.

Cite this