Vi utvecklar från första principer en exakt modell av beteendet hos loopar som utför i en minneshierarki, genom att använda en icke-traditionell klassificering av missar som har nyckel egenskapen komposabilitet. Vi använder Presburger formler för att uttrycka olika typer av missar samt tillståndet i cache i slutet av loop boet. Vi använder befintliga verktyg för att förenkla dessa formler och räkna cache missar. Modellen är kraftfull nog att hantera imperfekta loop bon och olika smaker av icke-linjära array layouter baserat på bit interleaving av array index. Vi anger också hur man hanterar blygsamma nivåer av associativitet, och hur man utför begränsad symbolisk analys av cache beteende. Komplexiteten i formlerna relaterar till den statiska strukturen i loop boet snarare än till dess dynamiska resa räkna, så att vår modell för att få effektivitet i att räkna cache missar genom att utnyttja repetitiva mönster av cache beteende. Validering mot cachesimulering bekräftar exaktheten i vår formulering. Vår metod kan ligga till grund för en statisk prediktor för att styra program- och dataomvandlingar för att förbättra prestandan.
Chatterjee m.fl. REF använder Presburger formler för att uttrycka olika typer av missar samt tillståndet i cache i början och i slutet av en slinga.
Exact analysis of the cache behavior of nested loops
{'venue': "PLDI '01", 'journal': None, 'mag_field_of_study': ['Computer Science']}