Fully Symbolic Analysis of Loop Locality: Using Imaginary Reuse to Infer Real Performance

Dit artikel introduceert een volledig symbolische theorie voor lokaalheidsanalyse die cache-prestaties als polynomen afleidt en binnen een milliseconde een voorspelling van cache-misses levert met 99,6% nauwkeurigheid voor diverse wetenschappelijke kernels.

De kern

De "Voorspellende Krystal" voor Computergeheugen: Een Simpele Uitleg

Stel je voor dat je een enorme bibliotheek hebt (dat is de computerprocessor) en een klein, handig bureau waar je je meest gebruikte boeken direct bij je hand hebt (dat is het cache-geheugen). Als je een boek nodig hebt dat op je bureau ligt, is het supersnel. Als je het niet hebt, moet je rennen naar de grote bibliotheek, wat veel tijd kost. Dit noemen we een "miss" (een gemiste kans op snelheid).

De vraag die deze wetenschappers zich stellen is: "Hoe vaak moet ik rennen naar de bibliotheek, en hoeveel boeken kan ik op mijn bureau houden om dat te minimaliseren?"

Tot nu toe hadden programmeurs twee opties:

1. Gokken: "Ik denk dat het ongeveer zo werkt..." (vaak fout).
2. Testen: "Laten we het programma een miljoen keer draaien en tellen..." (duur en traag, werkt niet voor elke nieuwe situatie).

Deze paper introduceert een nieuwe manier: Algebraïsche Locality. Laten we dit uitleggen met een paar creatieve analogieën.

1. Het Probleem: De "Eerste Kijk" Dilemma

Stel je voor dat je een nieuwe film kijkt. De eerste keer dat je een scène ziet, is dat nieuw (een "first-touch"). In de wereld van computers is dit een "koude start": het boek moet uit de bibliotheek gehaald worden.

• Het oude probleem: Als je probeert te voorspellen hoe vaak je een boek nodig hebt, is de eerste keer dat je het ziet een raadsel. Het lijkt alsof je het nooit eerder hebt gezien. In wiskundige termen is de "hergebruikstijd" oneindig lang. Dat maakt het onmogelijk om een nette formule te maken.

2. De Oplossing: "Imaginaire Hergebruik" (De Tijdreis-Analogie)

De auteurs hebben een slimme truc bedacht: Stel je voor dat je de film oneindig vaak herhaalt.

• De eerste keer dat je de film ziet, is de eerste scène nog nieuw.
• Maar als je de film twee keer achter elkaar afspeelt (oneindige herhaling), is de eerste scène van de tweede keer eigenlijk een herhaling van de eerste keer.

Ze noemen dit "Imaginary Reuses" (Imaginaire Hergebruik).

• De Analogie: Het is alsof je een tijdreis maakt. De "eerste keer" dat je iets ziet in de echte wereld, wordt in hun formule behandeld alsof het de "laatste keer" was van de vorige tijdreis.
• Het resultaat: Plotseling is er geen enkele "oneindige" tijd meer. Alles heeft een eindige tijd. Hierdoor kunnen ze een perfecte wiskundige formule (een polynoom) schrijven die precies beschrijft hoe het geheugen zich gedraagt.

3. De Resultaten: Een Voorspellende Formule

In plaats van te zeggen "Het werkt ongeveer zo", geven ze je nu een formule (een recept).

• Voorbeeld: Als je de grootte van je gegevens verdubbelt, hoe groot moet je bureau dan zijn om even snel te blijven?
  • De oude regel (de $\sqrt{2}$-regel) zegt: "Verdubbel de grootte, en vergroot je bureau met 1,41 keer."
  • De nieuwe formule zegt: "Het hangt af van de exacte vorm van je gegevens. Soms moet je bureau 1,41 keer groter, soms 1,5 keer, en de foutkans is verwaarloosbaar."

Ze hebben dit getest op 41 verschillende wetenschappelijke taken (zoals het simuleren van sterrenstelsels of het trainen van AI).

• Snelheid: Het kost de computer gemiddeld 41 seconden om deze formule te "berekenen" (de formule te vinden).
• Gebruik: Zodra de formule er is, duurt het minder dan een milliseconde om te voorspellen wat er gebeurt, zelfs als je de grootte van de gegevens of de grootte van het geheugen verandert.
• Nauwkeurigheid: Ze voorspellen 99,6% van de bewegingen in het geheugen correct. Dat is alsof je een weersvoorspelling doet en het de hele week perfect regent of droog blijft, precies zoals voorspeld.

4. Waarom is dit belangrijk?

Stel je voor dat je een stad bouwt (een computerprogramma).

• Vroeger: Je bouwde wegen (cache) op basis van ervaring. "Hier moet een weg zijn, want dat is handig." Soms was het verkeerd, en stonden er files (trage computer).
• Nu: Je hebt een perfecte simulatie die je kunt draaien voordat je ook maar één asfalt legt. Je kunt zeggen: "Als we de stad 10% groter maken, moeten we 2 nieuwe bruggen bouwen, anders stopt het verkeer."

Dit helpt programmeurs om software te schrijven die van nature sneller is, zonder dat ze handmatig alles hoeven te optimaliseren. Het maakt het mogelijk om te zien hoe een programma zich gedraagt op een supercomputer, een laptop of een mobiele telefoon, puur door naar de wiskunde te kijken.

Kortom: Ze hebben een manier gevonden om het gedrag van computergeheugen om te zetten in een strakke wiskundige formule, door slimme "tijdreizen" (imaginaire herhalingen) te gebruiken om de eerste, verwarrende momenten op te lossen. Het is alsof ze een kristallen bol hebben die niet alleen ziet wat er gebeurt, maar precies weet wat er zal gebeuren, hoe groot de gegevens ook zijn.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het paper "Fully Symbolic Analysis of Loop Locality: Using Imaginary Reuse to Infer Real Performance", vertaald en samengevat in het Nederlands.

Probleemstelling

Locality (de neiging van geheugentoegangen om in kleine gebieden van het adresruimte te clusteren) is een fundamentele eigenschap die de prestaties van data-intensieve toepassingen bepaalt. Bestaande methoden voor het analyseren van cache-prestaties hebben echter beperkingen:

1. Empirische regels: Regels zoals de $\sqrt{2}$-regel zijn nuttig voor schaalbaarheid, maar bieden geen exacte voorspellingen en missen nuance (bijv. verschillende miss-ratio's bij dezelfde schaalregels).
2. Symbolische beperkingen: Bestaande symbolische technieken voor affiene lussen (zoals het oplossen van geheeltallige vergelijkingen) kunnen vaak geen kwadratische of reciproke termen genereren. Ze zijn vaak beperkt tot constante cache-blokgroottes en hebben in het slechtste geval een exponentiële rekentijd.
3. Het "Cold-Start" Dilemma: Traditionele modellen behandelen de eerste toegang tot een gegeven (first-touch) als een oneindige hergebruiksinterval (Reuse Interval - RI). Dit maakt symbolische analyse onmogelijk omdat het leidt tot divergerende werksetgroottes.

Methodologie

De auteurs introduceren een volledig symbolische theorie genaamd Algebraic Locality, die cache-prestaties uitdrukt als polynomen afhankelijk van programmeer- en cache-parameteren. De kern van de methode bestaat uit de volgende stappen:

1. Oneindige Herhaling en Imaginaire Hergebruik (Imaginary Reuses):

   • Om het probleem van oneindige RIs bij eerste toegang op te lossen, wordt het concept van "Oneindige Herhaling" geïntroduceerd. Het programma wordt verondersteld oneindig vaak te herhalen.
   • Een "first-touch" in de eerste iteratie wordt in de tweede iteratie een "hergebruik". Deze worden Imaginary Reuses genoemd.
   • Dit zorgt ervoor dat elke toegang een eindige RI heeft, waardoor Denning's Recursie (een stochastisch model) correct kan worden toegepast op deterministische sequenties.

2. Afgeleide van Polynomen:

   • De theorie gebruikt de Reuse Interval (RI) verdeling.
   • Door Denning's Recursie toe te passen op de RI-verdeling (inclusief de imaginaire reuses), worden twee soorten polynomen afgeleid:
     1. Een polynoom voor de cache-grootte (werksetgrootte).
     2. Een polynoom voor het aantal missen of de miss-ratio.
   • Deze polynomen kunnen kwadratische en reciproke termen bevatten, wat ze nauwkeuriger maakt dan lineaire modellen.

3. Compiler Implementatie:

   • De analyse is geïmplementeerd als een compiler-pass die werkt op de MLIR Affine dialect.
   • Het proces omvat het vertalen van lusnests naar parametrische polytoepen.
   • Met behulp van Integer Set Programming (ISL) en Barvinok-decompositie worden de RI-verdelingen en hun tellingen berekend als stuksgewijze quasi-polynomen.
   • Een RI Som Invariantie test (waarbij het puntproduct van RI-waarden en hun verhoudingen gelijk moet zijn aan de data-grootte) wordt gebruikt om de correctheid van de symbolische berekeningen te verifiëren.

4. Correctie voor Cold Misses:

   • Omdat de analyse gebaseerd is op oneindige herhaling (waarbij first-touches hits worden), moet het resultaat worden aangepast voor een enkele uitvoering. De bijdrage van de imaginaire reuses aan de "hits" wordt omgezet in "cold misses" om de werkelijke miss-ratio te krijgen.

Belangrijkste Bijdragen

• Algebraic Locality Theory: Een nieuwe theorie die cache-polynomen in lineaire tijd afleidt met behulp van imaginaire reuses. Het bewijst formele eigenschappen zoals "Working-set Correctness" en "RI Sum Invariance".
• Affine Loop Compiler Analyse: Een implementatie die MLIR-affiene lussen omzet in parametrische polytoepen en symbolische RI-verdelingen berekent, inclusief de behandeling van complexe lussen en variabele grenzen.
• Schaalbaarheidsanalyse: De mogelijkheid om exacte schaalregels af te leiden (bijv. hoe de miss-ratio verandert bij het vergroten van de probleemgrootte $n$), wat nauwkeuriger is dan empirische regels zoals de $\sqrt{2}$-regel.

Resultaten

De methode is geëvalueerd op een benchmarksuite van 41 wetenschappelijke kernels (30 uit Polybench en 11 Einsum/tensor-operaties).

• Analyse Snelheid: Het afleiden van de locality-polynomen kost gemiddeld 41 seconden (voor niet-gefuseerde lussen) en maximaal enkele honderden seconden voor zeer diep geneste lussen.
• Voorspellingssnelheid: Eenmaal de polynomen zijn afgeleid, duurt het voorspellen van cache-misses voor willekeurige invoergroottes en cache-configuraties minder dan 1 milliseconde.
• Nauwkeurigheid:
  • De voorspelling van het aantal data-moves (hits + misses) heeft een nauwkeurigheid van 99,6% vergeleken met gesimuleerde set-associatieve L1 caches.
  • De gemiddelde fout in de miss-ratio is 1,1% voor volledig associatieve caches en 1,3% voor 12-weg set-associatieve caches.
  • Zonder het gebruik van "Imaginary Reuses" zou de fout oplopen tot gemiddeld 2,15% en maximaal 19,88%.
• Hardware Validatie: De resultaten komen sterk overeen met hardware performance counters op een Nvidia GB10 (Cortex-X925) processor.

Betekenis en Impact

Dit paper biedt een doorbraak in de statische analyse van cache-prestaties:

1. Van Empirisch naar Exact: Het vervangt empirische schaalregels door wiskundig exacte polynomen. Dit stelt ontwikkelaars in staat om de exacte impact van cache-grootte en probleemgrootte te begrijpen, inclusief subtiele verschillen (bijv. twee programma's die dezelfde $\sqrt{2}$-regel volgen maar een twee keer zo grote miss-ratio hebben).
2. Efficiëntie: Het combineert de nauwkeurigheid van simulatie met de snelheid van symbolische analyse, waardoor het mogelijk is om prestaties te voorspellen voor nog niet bestaande hardwareconfiguraties of invoergroottes.
3. Compiler Integratie: De integratie in MLIR maakt het toepasbaar op moderne compilatie-workflows en ondersteunt geavanceerde optimalisaties zoals lusfusie (loop fusion), waarbij de analyse aantoont dat fusie de voorspelde nauwkeurigheid zelfs kan verbeteren door het "moving-cliff" probleem (een type voorspellingsfout bij meervoudige lussen) op te lossen.

Kortom, deze techniek biedt een fundamenteel nieuw perspectief op het modelleren van geheugentoegangspatronen, waardoor het mogelijk wordt om cache-prestaties volledig symbolisch en met hoge precisie te analyseren en te optimaliseren.