Henting av hurtigbuffer - Cache prefetching

Cache prefetching er en teknikk som brukes av datamaskinprosessorer for å øke utførelsesytelsen ved å hente instruksjoner eller data fra den opprinnelige lagringen i langsommere minne til et raskere lokalt minne før det faktisk er nødvendig (derav begrepet 'prefetch'). De fleste moderne datamaskinprosessorer har raskt og lokalt hurtigbufferminne der forhåndsinnhentede data lagres til det er nødvendig. Kilden for prefetch -operasjonen er vanligvis hovedminnet . På grunn av deres design er tilgang til cacheminner vanligvis mye raskere enn tilgang til hovedminne , så forhåndshenting av data og deretter tilgang til dem fra cacher er vanligvis mange størrelsesordener raskere enn å få tilgang til dem direkte fra hovedminnet . Forhåndshenting kan gjøres med instruksjoner for ikke-blokkering av hurtigbuffer .

Data mot instruksjonsbuffer forhåndshenter

Cache -forhåndshenting kan enten hente data eller instruksjoner i hurtigbufferen.

Data forhåndshenting henter data før det er nødvendig. Fordi datatilgangsmønstre viser mindre regelmessighet enn instruksjonsmønstre, er nøyaktig datainnhenting generelt mer utfordrende enn instruksjonshenting.

Instruksjoner som hentes på forhånd, henter instruksjoner før de må utføres. De første vanlige mikroprosessorene som brukte en eller annen form for instruksjonsforhåndshenting var Intel 8086 (seks byte) og Motorola 68000 (fire byte). I de siste årene bruker alle prosessorer med høy ytelse forhåndsinnhentingsteknikker.

Maskinvare kontra programvare hurtigbuffer

Henting av hurtigbuffer kan utføres enten med maskinvare eller programvare.

Maskinvarebasert forhåndshenting oppnås vanligvis ved å ha en dedikert maskinvaremekanisme i prosessoren som ser på strømmen av instruksjoner eller data som blir forespurt av det utførende programmet, gjenkjenner de neste elementene som programmet kan trenge basert på denne strømmen og hentes på forhånd i prosessorens cache .

Programvarebasert forhåndshenting blir vanligvis oppnådd ved at kompilatoren analyserer koden og setter inn ekstra "forhåndshentings" instruksjoner i programmet under selve kompilering.

Metoder for forhåndshenting av maskinvare

Strømbuffere

Strømbuffere ble utviklet basert på konseptet "one block lookahead (OBL) ordning" foreslått av Alan Jay Smith .
Stream buffere er en av de vanligste maskinvarebasert forhåndshenting teknikker i bruk. Denne teknikken ble opprinnelig foreslått av Norman Jouppi i 1990, og mange varianter av denne metoden har blitt utviklet siden. Den grunnleggende ideen er at cache -missadressen (og påfølgende adresser) hentes inn i en egen dybdebuffer . Denne bufferen kalles en strømbuffer og er atskilt fra hurtigbufferen. Prosessoren bruker deretter data/instruksjoner fra strømbufferen hvis adressen som er knyttet til de forhåndshentede blokkene, samsvarer med den forespurte adressen generert av programmet som kjøres på prosessoren. Figuren nedenfor illustrerer dette oppsettet: ${\ displaystyle k}$ ${\ displaystyle k}$

Et typisk strømbufferoppsett som opprinnelig foreslått av Norman Jouppi i 1990

Når prefetch -mekanismen oppdager en glipp på en minneblokk, si A, tildeler den en strøm for å begynne å hente påfølgende blokker fra den tapte blokken videre. Hvis strømbufferen kan inneholde 4 blokker, ville vi forhåndshentet A+1, A+2, A+3, A+4 og beholdt dem i den tildelte strømbufferen. Hvis prosessoren bruker A+1 neste, skal den flyttes "opp" fra strømbufferen til prosessorens cache. Den første oppføringen av strømbufferen vil nå være A+2 og så videre. Dette mønsteret for forhåndshenting av påfølgende blokker kalles Sekvensiell forhåndshenting . Den brukes hovedsakelig når sammenhengende steder skal hentes på forhånd. For eksempel brukes den når du henter instruksjoner på forhånd.
Denne mekanismen kan skaleres opp ved å legge til flere slike 'strømbuffere' - som hver ville opprettholde en egen forhåndshentningsstrøm. For hver ny miss ville det bli tildelt en ny strømbuffer, og den ville fungere på en lignende måte som beskrevet ovenfor.
Den ideelle dybden på strømbufferen er noe som er eksperimentert med forskjellige referansemål og avhenger av resten av mikroarkitekturen som er involvert.

Et annet mønster for forhåndshenting av instruksjoner er å forhåndshente adresser som er adresser foran i sekvensen. Det brukes hovedsakelig når de påfølgende blokkene som skal hentes på forhånd er adresser fra hverandre. Dette kalles Strided Prefetching. ${\ displaystyle s}$ ${\ displaystyle s}$

Metoder for forhåndshenting av programvare

Kompilatorstyrt forhåndshenting

Kompilatorstyrt forhåndshenting er mye brukt i sløyfer med et stort antall iterasjoner. I denne teknikken forutsier kompilatoren fremtidige cachemiss og legger inn en forhåndshentingsinstruksjon basert på savningsstraffen og utførelsestiden for instruksjonene.

Disse forhåndshentingene er ikke-blokkerende minneoperasjoner, dvs. at disse minnetilgangene ikke forstyrrer faktisk minnetilgang. De endrer ikke prosessorens tilstand eller forårsaker sidefeil.

En hovedfordel med forhåndsinnhenting av programvare er at det reduserer antall obligatoriske cachemiss.

Følgende eksempel viser hvordan en forhåndshentingsinstruksjon vil bli lagt til i en kode for å forbedre hurtigbufferytelsen .

Vurder en for loop som vist nedenfor:

for (int i=0; i<1024; i++) {
    array1[i] = 2 * array1[i];
}

Ved hver iterasjon får du tilgang til det ^første elementet i matrisen "array1". Derfor kan vi forhåndshente elementene som skal nås i fremtidige iterasjoner ved å sette inn en "forhåndshenting" -instruksjon som vist nedenfor:

for (int i=0; i<1024; i++) {
    prefetch (array1 [i + k]);
    array1[i] = 2 * array1[i];
}

Her, prefetch -steget, avhenger av to faktorer, cache -miss -straffen og tiden det tar å utføre en enkelt iterasjon av for -løkken. For eksempel, hvis en iterasjon av sløyfen tar 7 sykluser å utføre, og straffen for cache -savning er 49 sykluser, bør vi ha - noe som betyr at vi forhåndshenter 7 elementer fremover. Med den første iterasjonen vil jeg være 0, så vi henter det 7. elementet på forhånd. Nå, med dette arrangementet, vil de første 7 tilgangene (i = 0-> 6) fortsatt være feil (under den forenklede antagelsen at hvert element i array1 er i en egen cache-linje for seg). ${\ displaystyle k}$ ${\ displaystyle k = 49/7 = 7}$

Sammenligning av forhåndshenting av maskinvare og programvare

Mens forhåndsinnhenting av programvare krever inngrep fra programmerere eller kompilatorer , krever forhåndsinnhenting av maskinvare spesielle maskinvaremekanismer.
Forhåndshenting av programvare fungerer bare godt med sløyfer der det er vanlig matrisetilgang, ettersom programmereren må håndkode forhåndshentingsinstruksjonene. Mens maskinvare prefetchere jobber dynamisk basert på programmets oppførsel ved kjøretid .
Forhåndshenting av maskinvare har også mindre CPU -overhead sammenlignet med forhåndsinnhenting av programvare.

Beregninger for hurtigbufferhenting

Det er tre hovedberegninger for å bedømme forhåndshenting av cache

Dekning

Dekning er brøkdelen av totale savner som elimineres på grunn av forhåndshenting, dvs.

${\ displaystyle Coverage = {\ frac {\ text {Cache Misses eliminated by Prefetching}} {\ text {Total Cache Misses}}}}}$ ,

hvor, ${\ displaystyle {\ text {Total Cache Misses}} = ({\ text {Cache -misser eliminert ved forhåndshenting}})+({\ text {Cache -savner ikke eliminert ved forhåndshenting}})}}$

Nøyaktighet

Nøyaktighet er brøkdelen av totale forhåndsinnhentinger som var nyttige - dvs. forholdet mellom antall forhåndsinnhentede minneadresser ble faktisk referert av programmet til de totale forhåndsinnhentningene.

${\ displaystyle {\ text {Prefetch Accuracy}} = {\ frac {\ text {Cache Misses eliminated by prefetching}} {({\ text {Useless Cache Prefetches}})+({\ text {Cache Misses elimined by prefetching} })}}}}$

Selv om det ser ut til at det å ha perfekt nøyaktighet kan bety at det ikke er noen glipp, er dette ikke tilfelle. Selve forhåndshentingene kan resultere i nye feil hvis de forhåndshentede blokkene plasseres direkte i hurtigbufferen. Selv om disse kan utgjøre en liten brøkdel av det totale antallet savner vi kan se uten forhåndshenting, er dette et antall feil som ikke er null.

Aktualitet

Den kvalitative definisjonen av aktualitet er hvor tidlig en blokk blir hentet på forhånd mot når den faktisk refereres til. Et eksempel for å forklare aktualiteten ytterligere er som følger:

Tenk på en for -sløyfe der hver iterasjon tar 3 sykluser å utføre og "prefetch" -operasjonen tar 12 sykluser. Dette innebærer at for at de forhåndsinnhentede dataene skal være nyttige, må vi starte gjentakelsene på forhåndshentingen før de brukes for å opprettholde aktualitet. ${\ displaystyle 12/3 = 4}$

Languages

In other projects