Continued Prefetching Post-Branch Misprediction: Exploring Path Convergence for Performance Enhancement

Abstract

Den eksponentielle veksten av digitale tjenester har gjort Warehouse-Scale Computers (WSCs) essensielle for de nettjenestene vi bruker daglig, levert av selskaper som Google, Amazon og Facebook. WSCs er ryggraden til disse tjenestene, men de står overfor betydelige utfordringer knyttet til deres energiforbruk, kjølebehov og miljøpåvirkning. Ettersom etterspørselen etter digitale tjenester fortsetter å øke, blir det stadig viktigere å optimalisere ytelsen og effektiviteten til WSCs. En stor hindring i å forbedre WSC-effektiviteten er den såkalte front-end flaskehalsen i moderne prosessorer. Denne flaskehalsen oppstår når prosessorens evne til å hente og dekode instruksjoner henger etter dens evne til å eksekvere instruksjoner. Denne flaskehalsen blir spesielt tydelig under serverarbeidsbelastninger som kjennetegnes av store instruksjonsfotavtrykk og komplekse programvarestakker. Historisk sett har fremskritt i prosessorer vært avhengig av økende antall transistorer, men med slutten av Dennard-skaleringen har fokuset skiftet til arkitektoniske optimaliseringer som tar sikte på å forbedre prosessoreffektiviteten. Fetch Directed Instruction Prefetching (FDIP) adresserer front-end flaskehalsen ved å forhåndshente instruksjoner med minimal maskinvarekostnad. Ved å koble front-end fra back-end, muliggjør FDIP kontinuerlige forutsigelse av grener under pipeline-stopp. Dette tillater forhåndshenting av disse grenforutsigelsene for å redusere cache-miss. Imidlertid står FDIP overfor utfordringer fra grenfeilforutsigelser, som krever at pipeline reverseres til riktig sti og midlertidig stopper forutsigelsesaktiviteter, noe som fører til betydelige ytelsesstraffer. Denne oppgaven undersøker de potensielle fordelene ved å fortsette forhåndshenting av cache-blokker på feil sti etter en grenfeilforutsigelse. Teori antyder at utnyttelse av sti-konvergens - hvor de feilaktige og korrekte stiene alignerer etter en grenfeilforutsigelse - kan forbedre den totale ytelsen. Gitt at kode ofte består av korte grener, som if-setninger og små løkker, kan målinstruksjonen være feilforutsagt, men den tilsvarende cache-blokken kan fortsatt være den samme. I slike tilfeller, siden forhåndshenting skjer på cache-blokknivå, kan det å fortsette forhåndshenting i stedet for umiddelbart å gå tilbake til riktig sti, redusere antall cache-miss og forbedre ytelsen. Denne teorien utforskes ved å implementere en versjon av FDIP som tillater fortsatt forhåndshenting langs en feilforutsagt sti samtidig som man sørger for at pipeline går tilbake til riktig sti. Om det oppdages at cache-blokkene langs den feilforutsagte stien har avveket fra riktig sti, vil forhåndshenting også gå tilbake til riktig sti. Undersøkelsen fokuserer først på om det er tilstrekkelig med sykluser til å forhåndshente instruksjoner etter en grenfeilforutsigelse for å avgjøre om å fortsette forhåndshenting på den feilforutsagte stien kan være gunstig. Instruksjoner Per Syklus (IPC) ble deretter målt. Deretter ble nøyaktigheten til forhåndshentingen vurdert, stienes likhet ble sammenlignet, og hyppigheten av grener innen de to stiene ble analysert.

The exponential growth of digital services has made Warehouse-Scale Computers (WSCs) essential for the online services we use daily, provided by companies such as Google, Amazon, and Facebook. WSCs are the backbone of these services, but they face significant challenges related to energy consumption, cooling demands, and environmental impact. As the demand for digital services continues to increase, optimizing the performance and efficiency of WSCs becomes increasingly critical.

A major hurdle in enhancing WSC efficiency is the so called front-end bottleneck in modern processors. This bottleneck occurs when the processor's ability to fetch and decode instructions lags behind its execution capabilities, particularly under server workloads characterized by large instruction footprints and complex software stacks. Historically, advancements in processors relied on increasing transistor counts, but with the end of Dennard scaling, the emphasis has shifted to architectural optimizations aimed at improving processor efficiency.

Fetch Directed Instruction Prefetching (FDIP) addresses the front-end bottleneck by prefetching instructions with minimal hardware overhead. By decoupling the front end from the back end, FDIP enables continuous branch predictions during pipeline stalls. This allows for prefetching of these branch predictions to cache misses. However, FDIP faces challenges from branch mispredictions, which necessitate pipeline flushing and temporarily halt prefetching activities, leading to significant performance penalties.

This thesis investigates the potential benefits of continuing to prefetch on the incorrect path after a branch misprediction. Theory suggests that leveraging path convergence—where the incorrect and correct paths align after a branch misprediction—could enhance overall performance. Given that code often consists of short branches, such as if-statements and small loops, the target instruction may be mispredicted, but the corresponding cache block might remain the same. In such cases, since prefetching occurs at cache block level, continuing to prefetch rather than immediately reverting to the correct path could reduce cache misses and improve performance.

This theory is explored by implementing a version of FDIP that allows for continued prefetching along a mispredicted path while ensuring that the pipeline reverts to the correct path. If it is determined that the cache blocks along the mispredicted path have diverged from the correct path, prefetching will also revert to the correct path.

The investigation first focused on whether there was sufficient cycles to prefetch instructions after a branch misprediction to determine if continued prefetching on the mispredicted path could be beneficial. The Instructions Per Cycle (IPC) were then measured. Subsequently, prefetching accuracy was assessed, the similarity of the paths was compared, and the frequency of branching within the paths was analyzed.