Vahemälu lokaalsus: miks lugemisjärjekord loeb

Mälus paikneb 8 × 8 maatriks int-tüüpi täisarve, rida rea järel. Mälu ja protsessori vahel on vahemälu, milles on kaheksa 16-baidist rida. Liida maatriksi elemendid kokku ridade või veergude kaupa ja jälgi lugemisi sammhaaval. Igas lahtris on kirjas ainus vahemälurida, kuhu selle aadress saab kuuluda. Merevaigukollane tähistab möödalasku, roheline tabamust ja hele toon naaberlahtreid, mis möödalasu korral kaasa laaditi.

Näidisarvutus — Vahemälu lokaalsus: miks lugemisjärjekord loeb

Lugemisi kummaski järjekorras	64
Maatriksi loetavad 16-baidised plokid	16
Suurim võimalik tabamuste arv	48 / 64 (75,0%)
Tabamusi ridade kaupa	48 / 64 (75,0%)
Tabamusi veergude kaupa	0 / 64 (0,0%)
Veeru 0 kasutatavad vahemäluread	4 / 8

Need on väärtused, mida kalkulaator lehe avamisel näitab. Muuda ülal mõnda sisendit, et need ümber arvutada.

Interaktiivse simulatsiooni laadimine...

Õppetund

Teooria — Vahemälu lokaalsus: miks lugemisjärjekord loeb

Vahemälu on väike ja kiire mälu, mis hoiab põhimälu andmete koopiaid vahemäluridades. Iga rida mahutab ühe joondatud L-baidise ploki. Kui loetava aadressi plokk on juba vahemälus, on lugemise tulemus tabamus. Muidu on tulemuseks möödalask ja vahemällu laaditakse kogu plokk. S reaga otsevastendusega vahemälus saab aadressi a sisaldav plokk paikneda ainult real ⌊a / L⌋ mod S. Kui tsükkel loeb naaberaadresse järjest, saab ta igast laaditud plokist teha mitu lugemist. Seda nimetatakse ruumiliseks lokaalsuseks.

Mida iga sümbol tähendab

L: vahemälurea suurus baitides: siin 16, enamikul laua- ja serveriarvutite protsessoritel 64
S: vahemäluridade arv: siin 8

Eeldab: Eeldame algul tühja otsevastendusega vahemälu, 4-baidiseid int-tüüpi täisarve ja ridade kaupa mällu paigutatud maatriksit, nagu teeb C. Fortran paigutab maatriksi mällu veergude kaupa ja seal on kiirem teine lugemisjärjekord. Loendame ainult maatriksi lugemisi. Tegelikud esimese taseme andmevahemälud on suuremad ja hulgassotsiatiivsed, tavaliselt 8-kordselt assotsiatiivsed: plokk võib paikneda oma hulga mis tahes 8 real. See kõrvaldab enamiku siin nähtavatest konfliktidest, kuid ei lahenda ruumipuudust. Riistvaralist eellaadimist, mis toob järgmise ploki vahemällu juba enne selle küsimist, siin ei arvestata.

Samad 64 liitmist võivad anda 48 tabamust või mitte ühtegi 🖖

Vajuta 8 × 8 ridade kaupa ja seejärel 8 × 8 veergude kaupa. Mõlemal juhul loetakse samu 64 täisarvu samalt 64 aadressilt. Muutub ainult järjekord. Ridade kaupa lugedes annab iga 16-baidise ploki esimene lugemine möödalasu ja laadib vahemällu neli täisarvu. Järgmised kolm on seega juba kohal: kokku 48 tabamust. Veergude kaupa lugedes asub järgmine element järgmises maatriksireas, 32 baiti eemal, ja kuulub teisele vahemälureale. Siin on maatriksi rida täpselt kahe vahemälurea pikkune. Seetõttu satub veerg 0 ainult vahemäluridadele 0, 2, 4 ja 6 ning a[4][0] tõrjub välja ploki, mille a[0][0] sisse tõi. Kui tsükkel jõuab elemendini a[0][1], on selle plokk juba eemaldatud. Kõik 64 lugemist annavad möödalasu. Ulrich Drepper mõõtis sama mõju suuremas mõõtkavas 2007. aastal. Kui seni veergude kaupa loetud maatriks enne transponeeriti, nii et mõlemat sai lugeda ridade kaupa, kulus Intel Core 2 protsessoril 1000 × 1000 maatriksite korrutamiseks vaid 23,4% varasemast taktsüklite arvust.

Kuni maatriks mahub vahemällu, ei mõjuta lugemisjärjekord tabamuste arvu 🖖

Vali suuruseks 5 ja proovi mõlemat lugemisjärjekorda: kummalgi juhul saad 25 lugemise kohta 18 tabamust. Maatriks võtab 100 baiti, vahemälu mahutab 128 baiti. Maatriksi seitse plokki satuvad seitsmele eri vahemälureale. Kui plokk on kord laaditud, ei tõrju miski seda välja. Iga plokk annab ainult ühe möödalasu, esimesel lugemisel, olenemata järjekorrast. Suurusega 6 × 6 võtab maatriks 144 baiti ja kaks plokki peavad jagama sama vahemälurida. Nüüd lähevad tulemused lahku: ridade kaupa saad 27 tabamust, veergude kaupa 25. Ilma täidiseta jääb veergude kaupa lugemine alla kõigi järgnevate suuruste juures kuni 16 × 16-ni.

Neli kasutamata täisarvu rea kohta kasvatavad tabamuste arvu 0-st 48-ni 🖖

Vajuta Täidisega read. Sama 8 × 8 maatriksit loetakse endiselt veergude kaupa, kuid iga rea lõpus on neli täisarvu, mida ei loeta. Nii võtab rida 48 baiti ehk kahe vahemälurea asemel kolm. Arvud 3 ja 8 on ühistegurita, seega satub veerg 0 nüüd kõigile kaheksale vahemälureale. Veeru kaheksa plokki mahuvad korraga vahemällu ning järgmise kolme veeru lugemisel on need juba kohal: 64 lugemise kohta 48 tabamust, sama palju kui ridade kaupa. Selle eest kulub 128 lisabaiti, mida kordagi ei loeta. Täidis kõrvaldab konfliktist tingitud möödalasud: kaks plokki võistlevad sama vahemälurea pärast, kuigi teised read seisavad tühjana. Vahemälu mahtu täidis ei suurenda. Läbitöötatud ülesande lõpus kohtad maatriksit, mille puhul saabki määravaks ruumipuudus.

Ülesanne täielikult lahendatud

Kui palju mälu liiklust põhjustab ebasoodne lugemisjärjekord? 4 sammu
Vajuta 8 × 8 veergude kaupa ja selgita, miks on tabamusi 0. Seejärel võta 1024 × 1024 maatriks 4-baidiseid int-tüüpi täisarve ning otsevastendusega 32 KiB vahemälu, mille read on 64-baidised. Mitu baiti tuuakse mälust, kui liita maatriksi elemendid kokku ridade kaupa? Aga veergude kaupa? Kas iga rea lõppu ühe vahemälurea jagu täidist aitaks?

Ava see ülesanne tööriistas
1. Siinses näites võtab maatriksi rida 8 × 4 = 32 baiti ehk kaks vahemälurida. Seega algab rida i vahemälureal 2i mod 8 ja veerg 0 kasutab ainult vahemäluridu 0, 2, 4 ja 6. a[4][0] võtab üle rea, kus paiknes a[0][0]. Kui tsükkel jõuab elemendini a[0][1], on selle plokk juba eemaldatud: 64 lugemise kohta 0 tabamust. Ridade kaupa lugedes annab iga 16-baidine plokk ühe möödalasu. Plokke on 16, seega tabamusi 48 ja nende osakaal 1 − 4/16 = 75%.
  
  $8 \times 4 = 32 bytes = 2 lines : 2 i mod 8 \in {0, 2, 4, 6}, 64 - 16 = 48 hits by rows$
2. Suures vahemälus on 32 768 / 64 = 512 rida. Ridade kaupa lugedes mahutab iga 64-baidine vahemälurida 16 täisarvu ja ainult esimene lugemine annab möödalasu. Möödalaske on 1 048 576 / 16 = 65 536, tabamuste osakaal 1 − 4/64 = 93,75% ning mälust tuuakse 65 536 × 64 = 4 194 304 baiti. Kogu maatriks loetakse mälust täpselt ühe korra.
  
  $\frac{32 768}{64} = 512 lines, \frac{1 048 576}{16} = 65536 misses, 65536 \times 64 = 4194304$
3. Veergude kaupa lugedes võtab maatriksi rida 4 096 baiti ehk 64 vahemälurida. Rida i algab vahemälureal 64i mod 512 ja iga veerg kasutab 512 vahemälureast ainult 8. a[8][0] tõrjub välja a[0][0] ploki. See on ammu eemaldatud, kui tsükkel jõuab elemendini a[0][1]. Kõik 1 048 576 lugemist annavad möödalasu: mälust tuuakse 67 108 864 baiti ehk 16 korda rohkem.
  
  $\frac{4 096}{64} = 64 : 64 i mod 512 takes 8 values, 1048576 \times 64 = 67108864$
4. Kui lisada iga rea lõppu 16 täisarvu, võtab rida 4 160 baiti ehk 65 vahemälurida. Arvud 65 ja 512 on ühistegurita, seega jaotub veerg nüüd kõigi 512 vahemälurea vahel. Tabamusi siiski ei tule. Üks veerg kasutab 1 024 plokki, kuid vahemälu mahutab 512. Iga plokk on eemaldatud enne, kui järgmine veerg seda vajab.
  
  $\frac{4 160}{64} = 65, g cd (65, 512) = 1, 1024 blocks > 512 lines$
Vastus

Ridade kaupa 4 MiB, veergude kaupa 64 MiB. Täidis jaotab veeru plokid kogu vahemälu peale, kuid tabamusi ei teki. Konfliktid saavad lahendatud, ent selle maatriksi iga veeru plokid vajavad rohkem ruumi, kui kogu vahemälus on.

$4 MiB by rows, 64 MiB by columns (16 \times)$

Õpitee

Kuidas arvuti programmi täidab

Allikad (1)

The first insight's measured case, the line size in the definition, and the 8-way first-level caches in `assumes`: Ulrich Drepper, "What Every Programmer Should Know About Memory," Red Hat, Inc., version 1.0, 21 November 2007. §3.2 (p. 15), §3.3.1 (pp. 17–18), §6.2.1 (pp. 49–50).

42Mathi meeskond · Kontrollitud avaldatud allikate põhjal. Parandused on teretulnud.