Arhitektura predmemorije.
Ovisno o načinu na koji su linija predmemorije i područje glavne memorije usklađeni, razlikuju se tri arhitekture predmemorije: izravno preslikana predmemorija, potpuno asocijativna predmemorija i djelomična ili postavljena asocijativna predmemorija.
Izravno preslikana predmemorija.
U izravno mapiranoj predmemoriji, adresa memorije kojoj se pristupa jedinstveno određuje liniju predmemorije u kojoj se može nalaziti traženi blok. Objasnit ćemo princip rada takve predmemorije na primjeru 256 KB nesektorske predmemorije s veličinom retka od 32 bajta i predmemoriranom glavnom memorijom od 64 MB - tipičnom predmemorijom matične ploče za Pentium. Struktura predmemorije u takvom sustavu ilustrirana je na sl. 1. Predmemorirana glavna memorija je uvjetno paginirana (u ovom slučaju 256 KB), čija je veličina jednaka veličini predmemorije (256 KB). Cache-memorija (i uvjetno - glavne memorijske stranice) podijeljena je u retke (256 KB / 32 bajta - 8 K redaka). Arhitektura izravnog preslikavanja implicira da svaki redak predmemorije može preslikati samo odgovarajući redak iz bilo koje predmemorirane memorijske stranice. Budući da je glavna memorija puno veća od predmemorije, svaki redak predmemorije može biti tražen od strane mnogih memorijskih blokova s istim niskim dijelom adrese, što se naziva pomak unutar stranice (0 - set, 1-set, 2-set ... N-skup od 32-bajtnih blokova ). Jedan redak u određenom trenutku može sadržavati kopiju samo jednog od ovih blokova. Broj linije je adresa linije u cache memoriji, a oznaka nosi informaciju o tome koji blok zauzima tu liniju (oznaka je gornji dio adrese koju postavlja procesor prilikom pristupa memoriji, odnosno, drugim riječima, broj stranice). Memorija oznaka mora imati broj ćelija jednak broju redaka predmemorije, a njezina širina mora biti dovoljna da primi bitove višeg reda adrese predmemorije koje nisu na adresnoj sabirnici predmemorije. Uz adresni dio oznake, svaki red predmemorije povezan je s bitovima znakova valjanosti i izmjene podataka. Na početku svakog pristupa RAM-u, kontroler cache memorije prije svega čita ćeliju tag memorije s adresom retka određenom bitovima A17-A5, uspoređuje sadržaj ovog retka tag memorije s bitovima A25-A18 iz memorijsku adresu koju postavlja procesor i analizira znak stvarnosti.
Riža. 1. Predmemorija s izravnim preslikavanjem.
Ova se analiza izvodi u posebnoj petlji praćenja, koja se ponekad naziva i petlja upita. Ako se kao rezultat analize pokaže da traženi blok nije u cacheu, generira se (ili nastavlja) ciklus pristupa glavnoj memoriji (cache miss). Ako pogodi, zahtjev servisira predmemorija. U slučaju promašaja nakon čitanja iz glavne memorije od strane primatelja informacija, novi podatak se stavlja u red predmemorije (ako je čist) , a u njen tag se stavljaju gornji bitovi adrese i postavlja predznak valjanosti podataka. Bez obzira na količinu traženih podataka, cijeli se redak prepisuje u predmemoriju iz glavne memorije (budući da se znak valjanosti odnosi na sve njegove bajtove). Ako kontroler predmemorije implementira čitanje unaprijed, tada se u sljedećim ciklusima slobodne sabirnice ažurira i sljedeći redak (ako je bio čist ). Čitanje "u rezervi" omogućuje, ako je potrebno, izvođenje ciklusa skupnog čitanja iz predmemorije preko granice retka. Takav cache ima najjednostavniju hardversku implementaciju i koristi se u sekundarnom cacheu većine matičnih ploča. Međutim, ima ozbiljan nedostatak. Ako tijekom izvođenja programa procesor naizmjenično pristupa istoj adresi linije, ali s različitim ili ciklički promjenjivim brojevima oznaka, tada će se promašaji predmemorije stalno popravljati, a predmemorija će, umjesto da ubrza, usporiti razmjenu s memorija. Prebacivanje stranica u multitasking operativnim sustavima (OS) također smanjuje broj pogodaka predmemorije, što utječe na performanse sustava. Povećanje veličine predmemorije uz zadržavanje arhitekture izravnog mapiranja neće imati značajan učinak, budući da će različiti zadaci zahtijevati iste linije predmemorije. Bez povećanja veličine predmemorije, moguće je povećati učinkovitost predmemoriranja promjenom njegove strukture, o čemu će biti riječi u nastavku.
Ponekad unaprijed mapirana predmemorija koristi koncept skupa umjesto retka u sektoriziranoj unaprijed mapiranoj predmemorije, a sektor se tada naziva redom. Skup (kao i linija predmemorije koja nije sektor) ima informacije o oznakama povezane sa svim elementima skupa (linijama ili sektorima). Osim toga, svaki element skupa (redak ili sektor) ima svoj bit valjanosti (slika 2).
Riža. 2. Predmemorija usmjerena prema naprijed
Vrsta-asocijativna (djelomično-asocijativna) predmemorija.
Skup-asocijativna arhitektura predmemorije (slika 3) dopušta svakom bloku predmemorirane memorije da zatraži jednu od nekoliko linija predmemorije kombiniranih u skup. U ovoj arhitekturi postoji, takoreći, nekoliko paralelnih i koordiniranih izravnih kanala preslikavanja, gdje kontroler predmemorije mora odlučiti u koji od redaka skupa smjestiti sljedeći blok podataka. Na primjer, u najjednostavnijem slučaju, svaki memorijski blok može stati u jednu od četiri postavljene linije (četverokanalni set-asocijativna predmemorija). Skupni broj u kojem se traženi blok podataka može mapirati jedinstveno je identificiran srednjim dijelom adrese (poput broja retka u predmemorije mapiranja prema naprijed). Linija skupa koja se preslikava na traženi blok određena je usporedbom oznaka (kao u asocijativnoj predmemoriji) izvedenom paralelno za sve linije memorije oznaka danog skupa (kanali predmemorije). Osim toga, svaki skup mora imati pridruženu zastavicu koja definira skupni niz koji će se zamijeniti novim blokom podataka u slučaju promašaja predmemorije (strelica pokazuje u svom smjeru na slici).
Riža. 3. Četverokanalni set-asocijativni cache
Datum kandidata za zamjenu obično je niz kojemu se nije pristupalo najdulje vrijeme (LRU algoritam - najmanje nedavno korišten). S relativno velikim brojem kanala (linija u skupu), pribjegava se određenom pojednostavljenju - Pseudo-LRU algoritam za četiri linije omogućuje donošenje odluka korištenjem samo 3 bita.
Također je moguće koristiti FIFO (prvi ušao, prvi izašao) algoritam zamjene ili čak nasumične zamjene, što je jednostavnije, ali manje učinkovito. Set-asocijativna arhitektura naširoko se koristi za primarnu predmemoriju modernih procesora.
Asocijativna predmemorija.
Za razliku od prethodnih, za potpuno asocijativni cache, bilo koji od njegovih redaka može mapirati bilo koji blok memorije, što značajno povećava učinkovitost korištenja ograničene količine predmemorije. Međutim, svi bitovi
Riža. 4. Potpuno asocijativna predmemorija.
Adrese predmemoriranog bloka, minus bitovi koji određuju položaj (pomak) podataka u retku, pohranjuju se u memoriju oznaka. U takvoj arhitekturi (sl. 4), da bi se utvrdilo prisustvo traženih podataka u predmemorijskoj memoriji, usporedba s gornjim dijelom adrese oznake svih redaka memorije oznaka, a ne jedne ili nekoliko, kao kod izravnog mapiranja ili potrebna je skup-asocijativna arhitektura. Eliminira se sekvencijalno nabrajanje memorijskih ćelija oznaka. (ovo oduzima previše vremena), pa ostaje paralelna usporedba oznaka svih ćelija, a to je složen hardverski zadatak koji je prihvatljiv samo za male količine primarne predmemorije (M2 Cyrix procesor).
Programeri cache memorije susreli su se s problemom da bilo koja ćelija ogromne glavne memorije potencijalno može biti u cache memoriji. Ako je radni skup podataka koji se koristi u programu dovoljno velik, to znači da će se mnogi fragmenti glavne memorije natjecati za svako mjesto u cache memoriji. Kao što je ranije objavljeno, nije neuobičajeno da omjer između predmemorije i glavne memorije bude 1 prema 1000.
3.3.1 Asocijativnost
Bilo bi moguće implementirati predmemoriju u kojoj svaki red predmemorije može pohraniti kopiju bilo koje memorijske lokacije. To se zove potpuno asocijativna predmemorija (potpuno asocijativna predmemorija). Za pristup liniji predmemorije, jezgra procesora bi morala usporediti oznake svake pojedine linije predmemorije s oznakom tražene adrese. Oznaka će morati pohraniti cijelu adresu, koja neće biti specificirana pomakom u retku predmemorije (što znači da će vrijednost S prikazana na slici u odjeljku 3.2 biti nula).
Postoje predmemorije koje su implementirane na ovaj način, ali gledajući veličinu L2 predmemorije koja se trenutno koristi, to je nepraktično. Imajte na umu da bi predmemorija od 4 MB sa 64 B linija predmemorije trebala imati 65 536 unosa. Kako bi se postigla odgovarajuća izvedba, logika predmemorije mora moći, unutar nekoliko ciklusa, odabrati od svih ovih unosa onaj koji odgovara danoj oznaci. Troškovi provedbe takve sheme bili bi ogromni.
Slika 3.5: Shematski prikaz potpuno asocijativne predmemorije
Svaki redak predmemorije zahtijeva od komparatora da izvrši veliku usporedbu oznaka (imajte na umu da je S nula). Slovo pored svake veze označava širinu veze u bitovima. Ako ništa nije navedeno, tada je širina veze jedan bit. Svaki komparator mora usporediti dvije vrijednosti, od kojih je svaka široka T bitova. Zatim, na temelju rezultata, sadržaj odgovarajućeg retka predmemorije treba odabrati i učiniti dostupnim. Da biste to učinili, trebate kombinirati onoliko skupova podatkovnih linija O koliko ima segmenata predmemorije (kaširanja). Broj tranzistora potrebnih za implementaciju jednog komparatora bit će velik, dijelom zato što komparator mora biti vrlo brz. Ne može se koristiti iterativni komparator. Jedini način da se uštedi na broju komparatora je smanjiti njihov broj iterativnom usporedbom oznaka. Ovo ne radi iz istog razloga iz kojeg ne rade iterativni komparatori: trajalo bi predugo.
Potpuno asocijativna predmemorija praktična je za malu predmemoriju (na primjer, TLB predmemorija na nekim Intelovim procesorima je potpuno asocijativna), ali predmemorija mora biti mala - stvarno mala. Riječ je o maksimalno nekoliko desetaka zapisa.
L1i, L1d i predmemorije više razine zahtijevaju drugačiji pristup. Sve što možete učiniti je ograničiti svoju pretragu. U najekstremnijem slučaju, svaka oznaka se preslikava na točno jedan unos u predmemoriju. Izračun je jednostavan: za predmemoriju od 4MB/64B sa 65.536 unosa, svakom unosu možemo pristupiti izravno i za to koristiti bitove 6 do 21 adrese (16 bitova). Donjih 6 bitova je indeks retka predmemorije.
Slika 3.6: Shematski prikaz izravno mapirane predmemorije
Kao što se može vidjeti na slici 3.6, implementacija takvog izravno preslikana predmemorija (izravno preslikana predmemorija) može biti brzo i jednostavno. Zahtijeva samo jedan komparator, jedan multiplekser (dva su prikazana na ovom dijagramu jer su oznaka i podaci odvojeni, ali to nije strogi zahtjev dizajna) i neku logiku za odabir sadržaja koji sadrži valjane retke predmemorije. Komparator je složen zbog zahtjeva u pogledu brzine, ali sada postoji samo jedan; kao rezultat toga, može se uložiti više truda da bi se ubrzao. Prava složenost ovog pristupa leži u multiplekserima. Broj tranzistora u jednostavnom multiplekseru raste za O(log N), gdje je N broj linija predmemorije. To je prihvatljivo, ali može rezultirati sporim multiplekserom, u kojem slučaju se brzina može povećati trošenjem novca na tranzistore u multipleksorima i paraleliziranjem dijela rada za povećanje brzine. Ukupan broj tranzistora će sporo rasti u usporedbi s veličinom predmemorije, što ovo čini vrlo atraktivnim rješenjem. Ali ovaj pristup ima nedostatak: funkcionira samo ako su adrese korištene u programu ravnomjerno raspoređene u odnosu na bitove koji se koriste za izravno mapiranje. Ako to nije slučaj, a obično jest, neki se unosi predmemorije aktivno koriste i stoga se više puta poništavaju, dok se drugi gotovo uopće ne koriste ili ostaju prazni.
Slika 3.7: Shematski prikaz predmemorije s višestrukom asocijativnošću
Ovaj se problem može riješiti korištenjem predmemorije s višestruka asocijativnost (set pridružen). Predmemorije s više asocijativnosti kombiniraju značajke potpuno asocijativnih predmemorija i izravno mapiranih predmemorija, uvelike izbjegavajući nedostatke ovih rješenja. Slika 3.7 prikazuje izgled predmemorije s višestrukom asocijativnošću. Memorija za oznake i za podatke podijeljena je u skupove, čiji se odabir provodi u skladu s adresom. Ovo je slično izravnom mapiranom predmemoriju. No umjesto korištenja zasebnog elementa za svaku vrijednost u skupu, isti se skup koristi za predmemoriju malog broja vrijednosti. Paralelno se uspoređuju oznake za sve elemente skupa, što je slično radu potpuno asocijativne predmemorije.
Rezultat je predmemorija koja je relativno otporna na promašaje zbog lošeg ili namjernog odabira adresa s istim postavljenim brojevima u isto vrijeme, a veličina predmemorije nije ograničena brojem komparatora koji mogu raditi paralelno. Ako se predmemorija poveća (vidi sliku), povećat će se samo broj stupaca, ne i broj redaka. Broj redaka se povećava samo ako se povećava asocijativnost predmemorije. Danas procesori L2 predmemorije koriste razine asocijativnosti do 16 i više. L1 predmemorija obično je postavljena na razinu 8.
Tablica 3.1: Učinci veličine predmemorije, asocijativnosti i veličine retka predmemorije
| Veličina cache memorija L2 |
Asocijativnost | |||||||
|---|---|---|---|---|---|---|---|---|
| izravni prikaz | 2 | 4 | 8 | |||||
| CL=32 | CL=64 | CL=32 | CL=64 | CL=32 | CL=64 | CL=32 | CL=64 | |
| 512k | 27 794 595 | 20 422 527 | 25 222 611 | 18 303 581 | 24 096 510 | 17 356 121 | 23 666 929 | 17 029 334 |
| 1M | 19 007 315 | 13 903 854 | 16 566 738 | 12 127 174 | 15 537 500 | 11 436 705 | 15 162 895 | 11 233 896 |
| 2M | 12 230 962 | 8 801 403 | 9 081 881 | 6 491 011 | 7 878 601 | 5 675 181 | 7 391 389 | 5 382 064 |
| 4M | 7 749 986 | 5 427 836 | 4 736 187 | 3 159 507 | 3 788 122 | 2 418 898 | 3 430 713 | 2 125 103 |
| 8M | 4 731 904 | 3 209 693 | 2 690 498 | 1 602 957 | 2 207 655 | 1 228 190 | 2 111 075 | 1 155 847 |
| 16M | 2 620 587 | 1 528 592 | 1 958 293 | 1 089 580 | 1 704 878 | 883 530 | 1 671 541 | 862 324 |
Ako imamo 4MB/64B predmemoriju i 8-kanalnu asocijativnost, tada ćemo imati 8192 seta u predmemoriju i samo 13 bitova oznake bit će potrebno za adresiranje skupova predmemorije. Da bi se odredilo koji od unosa (ako ih ima) u skupu predmemorije sadrži adresirani redak predmemorije, potrebno je usporediti 8 oznaka. To se može učiniti u vrlo kratkom vremenu. Kao što vidite iz prakse, ovo ima smisla.
Tablica 3.1 prikazuje broj promašaja L2 predmemorije za neki program (u ovom slučaju, gcc kompajler, koji programeri Linux kernela smatraju najvažnijim mjerilom) pri promjeni veličine predmemorije, veličine retka predmemorije i višestruke asocijativnosti vrijednosti. U odjeljku 7.2 predstavit ćemo alat za simulaciju predmemorije potreban za ovaj test.
Jednostavno, ako već nije očito, odnos svih ovih vrijednosti je veličina predmemorije
veličina retka predmemorije x asocijativnost x broj skupova
Preslikavanje adrese u predmemoriju izračunava se kao
O = veličina retka predmemorije log2
S = log2 broja skupova
prema slici u odjeljku 3.2.
Slika 3.8: Veličina predmemorije i razina asocijativnosti (CL=32)
Riža. 3.8 čini tablične podatke razumljivijim. Slika prikazuje podatke za liniju predmemorije fiksne veličine od 32 bajta. Gledajući brojke za određenu veličinu predmemorije, možete vidjeti da asocijativnost može stvarno pomoći u značajnom smanjenju promašaja predmemorije. Za predmemoriju od 8 MB, prijelaz s izravno mapirane na dvosmjernu asocijativnost štedi gotovo 44% predmemorije. Ako se koristi predmemorija s više asocijativnosti, tada procesor može pohraniti veći radni skup u predmemoriju nego u slučaju izravno mapirane predmemorije.
Ponekad možete pročitati u literaturi da uvođenje asocijativnosti ima isti učinak kao udvostručenje veličine predmemorije. Ovo, kao što se vidi u slučaju prelaska s predmemorije od 4 MB na predmemoriju od 8 MB, vrijedi u nekim ekstremnim slučajevima. Ali to, naravno, nije točno s naknadnim povećanjem asocijativnosti. Kao što je vidljivo iz podataka, naknadno povećanje asocijativnosti daje znatno manji dobitak. Međutim, ne bismo trebali potpuno zanemariti ovu činjenicu. U našem primjeru programa, maksimalna upotreba memorije je 5,6 MB. Dakle, s veličinom predmemorije od 8 MB, isti skupovi predmemorije koristit će se više puta (više od dva puta). Kako se radni skup povećava, ušteda se može povećati, jer, kao što vidimo, s manjim veličinama predmemorije prednost korištenja asocijativnosti bit će veća.
Općenito, čini se da povećanje asocijativnosti predmemorije iznad 8 ima mali učinak na jednu nit radnog opterećenja. Dolaskom višejezgrenih procesora koji koriste zajedničku L2 predmemoriju, situacija se mijenja. Sada u osnovi imate dva programa koji pristupaju istoj predmemoriji, što bi u praksi trebalo udvostručiti učinak korištenja asocijativnosti (ili učetverostručiti za procesore s četiri jezgre). Stoga se može očekivati da bi se s povećanjem broja jezgri trebala povećavati asocijativnost zajedničke predmemorije. Kako to postaje nemoguće (16-kanalnu asocijativnost već je teško implementirati), dizajneri procesora počet će koristiti zajedničku L3 predmemoriju i šire, dok će L2 predmemoriju potencijalno dijeliti neki podskup jezgri.
Drugi učinak koji možemo vidjeti na slici 3.8 je kako povećanje veličine predmemorije poboljšava performanse. Ovi se podaci ne mogu interpretirati bez poznavanja veličine radnog skupa. Očito, predmemorija velika poput glavne memorije trebala bi dovesti do boljih rezultata od manje predmemorije, tako da općenito nema ograničenja za povećanje veličine predmemorije i stjecanje mjerljivih prednosti.
Kao što je gore spomenuto, veličina radnog skupa na vrhuncu je 5,6 MB. Ova nam vrijednost ne omogućuje izračunavanje količine memorije koja bi donijela maksimalnu korist, ali nam omogućuje procjenu ove veličine. Problem je u tome što se sva memorija ne koristi neprekidno i stoga imamo sukobe čak i sa 16M predmemorije i 5,6M radnim skupom (sjetite se prednosti dvosmjerne 16MB asocijativne predmemorije u odnosu na verziju s izravnim prikazom). Ali slobodno se može reći da pod takvim opterećenjem prednost predmemorije od 32 MB neće biti značajna. Međutim, tko je rekao da radni set treba ostati nepromijenjen? Kako radno opterećenje s vremenom raste, tako bi trebala rasti i veličina predmemorije. Kada kupujete strojeve i odlučujete koliko ćete predmemorije platiti, vrijedi izmjeriti veličinu radnog skupa. Zašto je ovo važno može se vidjeti na sl. 3.10.
Slika 3.9: Raspored memorije korišten u testiranju
Provode se dvije vrste testova. U prvom testu elementi se obrađuju sekvencijalno. Testni program koristi pokazivač n, ali elementi niza su međusobno povezani tako da se obilaze redoslijedom kojim su u memoriji. Ova je opcija prikazana na dnu slike 3.9. Postoji jedna povratna referenca koja dolazi iz posljednjeg elementa. U drugom testu (gornji dio slike) elementi niza se obilaze slučajnim redoslijedom. U oba slučaja, elementi niza tvore cikličku jednostruko povezanu listu.
Poznate opcije za mapiranje glavne memorije u predmemoriju mogu se svesti na tri vrste: direktno, potpuno asocijativno I djelomično asocijativno.
Na izravni prikaz adresa linije ja predmemorija u koju se blok može mapirati j iz OP-a, jednoznačno je određena izrazom: ja = j mod m, Gdje m je ukupan broj redaka u cacheu, tj. po retku cachea s brojem ja prikazan svaki m-ti blok OP-a, ako odbrojavanje počinje od bloka čiji je broj jednak ja.
Izravno preslikavanje jednostavna je i jeftina metoda preslikavanja. Njegov glavni nedostatak je rigidna dodjela jednog retka u predmemoriji određenim OP blokovima. Stoga, ako program naizmjenično pristupa riječima iz dva različita bloka mapirana u isti red predmemorije, ovaj red će se stalno ažurirati i vjerojatnost pogotka bit će mala.
Potpuno asocijativni prikaz nadilazi nedostatak izravnog dopuštajući učitavanje bilo kojeg RAM bloka u bilo koju liniju predmemorije. Asocijativno mapiranje pruža fleksibilnost u odabiru retka za novo snimljeni blok. Temeljni nedostatak ove metode je potreba za izvođenjem provjere za sve redove predmemorije.
Djelomično asocijativno preslikavanje jedan je od mogućih kompromisa, kombinirajući prednosti izravnih i asocijativnih metoda preslikavanja i, u određenoj mjeri, lišeno njihovih nedostataka. Keš memorija se dijeli na v podskupovi (skupovi), od kojih svaki sadrži k redaka (uobičajeno je reći da skup ima k ulazi). Ovisnost između skupa i OP blokova ista je kao kod izravnog preslikavanja: na linije uključene u skup ja, mogu se prikazati samo dobro definirani blokovi glavne memorije, u skladu s relacijom ja = j mod v, Gdje j– adresa OP bloka. Istodobno, postavljanje blokova duž linija modula je proizvoljno, a asocijativni princip se koristi za traženje željene linije unutar modula.
U ekstremnim slučajevima, kada v = m, k= 1, višestruko asocijativno preslikavanje svodi se na izravno, a kada v = 1,k = m- na asocijativ.
Ovisno o načinu određivanja međusobne korespondencije linije predmemorije i glavnog memorijskog bloka, razlikuju se tri arhitekture predmemorije:
Potpuno asocijativna predmemorija
Izravna predmemorija preslikavanja (izravno preslikana predmemorija);
set- (djelomično ili višestruko-) asocijativni cache (set-associative cache).
U potpuno asocijativna predmemorija bilo koji blok glavne memorije može se nalaziti u bilo kojoj liniji predmemorije ili se bilo koja linija predmemorije može mapirati u bilo koji blok glavne memorije. U ovom slučaju, gornji bitovi predmemorirane adrese podataka, minus bitovi koji određuju položaj (pomak) podataka u retku (bloku), unose se u katalog i koriste kao oznaka. U takvoj arhitekturi, da bi se utvrdilo ima li podataka u predmemorij na određenoj adresi, potrebno je usporediti gornje bitove ove adrese s oznakama svih redaka u direktoriju predmemorije. Ako se takva usporedba radi uzastopno, tada će trajati predugo, a cache memorija postaje besmislena zbog niskih performansi. Stoga se takva usporedba mora izvoditi paralelno za sve oznake. Ovaj zahtjev najbolje ispunjava asocijativna memorija, to jest, oznaka mora biti pohranjena u asocijativnoj memoriji oznake predmemorije.
Ovakva organizacija cache memorije složen je hardverski problem koji se može riješiti samo za male volumene, tj. potpuno asocijativni cache zbog svoje složenosti ne može imati veliki volumen i koristi se u pravilu u pomoćne svrhe. Na primjer, u Intel procesorima, potpuno asocijativna predmemorija koristi se u straničnom bloku za izgradnju međuspremnik za prevođenje asocijacije TLB (Translation Look aside Buffer), dizajniran za ubrzavanje pristupa često korištenim stranicama.
Suprotna arhitektura je predmemorija izravnog mapiranja. U izravno mapiranoj predmemoriji, određeni blok glavne memorije može se nalaziti samo u dobro definiranoj liniji predmemorije. Glavna memorija je uvjetno podijeljena na stranice, čija veličina odgovara veličini predmemorije. Arhitektura izravnog mapiranja znači da svaki redak predmemorije može mapirati samo odgovarajući blok s bilo koje stranice u glavnoj memoriji. Blokovi s istim brojem svih stranica spadaju u isti red predmemorije. Stoga, svaki redak predmemorije preuzimaju mnogi blokovi glavne memorije s istim brojevima unutar stranice. Jedan po redak može sadržavati samo kopiju jednog od ovih blokova. Oznaka je broj stranice čiji blok zauzima odgovarajuću liniju predmemorije. U takvoj arhitekturi, da bi se utvrdilo postoje li podaci u predmemoriji s određenom adresom, potrebno je usporediti broj stranice kojoj ta adresa pripada s oznakom retka u direktoriju predmemorije koji odgovara bloku na stranici koja sadrži zadanu adresu, odnosno potrebno je izvršiti samo jednu usporedbu.
Izravno preslikana predmemorija ima najjednostavniju hardversku implementaciju, budući da predmemorija ima strukturu konvencionalne memorije koja se izravno adresira i potreban je samo jedan komparator. Stoga takav cache može biti velik.
Intermedijar između potpuno asocijativne predmemorije i izravno mapirane predmemorije je set-asocijativna predmemorija, koji se uglavnom koristi u modernim mikroprocesorima. U set-asocijativnom cacheu, za razliku od izravno mapiranog cachea, svaki blok glavne memorije može zatražiti jednu od nekoliko linija predmemorije kombiniranih u skupu. To povećava vjerojatnost uspješne konverzije. Pojednostavljeno, možemo pretpostaviti da je set-asocijativna predmemorija nekoliko paralelnih i koordiniranih izravnih kanala preslikavanja u kojima redovi s istim brojevima tvore odgovarajući skup. Niz za biranje koji predstavlja potrebni blok glavne memorije određen je usporedbom oznaka (kao u asocijativnoj predmemoriji) izvedenom paralelno za sve kanale predmemorije. Svaki skup ima pridruženu oznaku koja određuje red skupa koji treba zamijeniti novim blokom u slučaju promašaja predmemorije. Kandidat za zamjenu obično je string kojemu se nije pristupalo najduže vrijeme (LRU algoritam - Retko nedavno korišten). Također je moguće koristiti FIFO ili čak algoritam nasumične zamjene, što je jednostavnije, ali manje učinkovito.
Zašto opažamo konstantan porast performansi jednonitnih programa? Trenutno smo u onom stupnju razvoja mikroprocesorskih tehnologija, kada povećanje brzine jednonitnih aplikacija ovisi samo o memoriji. Broj jezgri raste, ali je frekvencija fiksna unutar 4 GHz i ne daje povećanje performansi.
Brzina i učestalost rada memorije glavni je razlog zašto dobivamo "svoj dio besplatnog kolača" (link). Zato je važno koristiti memoriju što učinkovitije, a još više što brže kao cache. Za optimizaciju programa za određeno računalo korisno je znati karakteristike predmemorije procesora: broj razina, veličinu, duljinu linije. Ovo je posebno važno u kodu visokih performansi - jezgri sustava, matematičke biblioteke.
Kako odrediti karakteristike automatske predmemorije? (naravno, cpuinfo se ne smatra raščlanjenim, barem zato što bismo na kraju željeli dobiti algoritam koji se može lako implementirati u druge operativne sustave. Zgodno, zar ne?) To je ono što ćemo sada učiniti .
Malo teorije
Trenutačno postoje i široko se koriste tri vrste predmemorije: izravno mapirana predmemorija, asocijativna predmemorija i višestruka asocijativna predmemorija.Predmemorija izravnog mapiranja
- dana linija RAM-a može se mapirati u jednu liniju predmemorije, ali mnoge moguće linije RAM-a mogu se mapirati u svaku liniju predmemorije.Asocijativna predmemorija (potpuno asocijativna predmemorija)
- bilo koja linija RAM-a može se preslikati na bilo koju liniju predmemorije.Višestruka asocijativna predmemorija
- predmemorija je podijeljena u nekoliko "banki", od kojih svaka funkcionira kao izravno mapirana predmemorija, tako da linija RAM-a ne može biti mapirana na jedan mogući unos u predmemoriju (kao što bi bilo u slučaju izravnog mapiranja), ali jednoj od nekoliko banaka; Odabir banke temelji se na LRU ili drugom mehanizmu za svaku predmemoriranu liniju.LRU - pomicanje same "dugo neiskorištene" linije, predmemorija memorije.
Ideja
Da biste odredili broj razina predmemorije, morate uzeti u obzir redoslijed pristupa memoriji, u kojem će prijelaz biti jasno vidljiv. Različite razine predmemorije prvenstveno se razlikuju u brzini odziva memorije. U slučaju "promašaja predmemorije" za L1 predmemoriju, podaci će se pretraživati u sljedećim razinama memorije, a ako je veličina podataka veća od L1 i manja od L2, tada će brzina odziva memorije biti brzina odziva L2. Prethodna tvrdnja vrijedi iu općem slučaju.Jasno je da moramo odabrati test na kojem ćemo jasno vidjeti promašaje predmemorije i testirati ga na različitim veličinama podataka.
Poznavajući logiku višestruko asocijativnih predmemorija koje rade prema LRU algoritmu, nije teško smisliti algoritam na koji predmemorija "pada", ništa lukavo - prolazak kroz liniju. Kriterij učinkovitosti je vrijeme jednog pristupa memoriji. Naravno, morate sekvencijalno pristupati svim elementima niza, ponavljajući mnogo puta da biste izračunali prosjek rezultata. Na primjer, mogu postojati slučajevi kada linija stane u predmemoriju, ali za prvi prolaz učitavamo liniju iz RAM-a i stoga dobivamo potpuno neadekvatno vrijeme.
Želio bih vidjeti nešto poput koraka, koji prolaze duž linija različitih duljina. Da biste odredili prirodu koraka, razmotrite primjer prolaza linije za izravni i asocijativni cache, slučaj višestruko asocijativnog cachea bit će prosjek između izravno mapiranog cachea i asocijativnog cachea.
Asocijativna predmemorija
Čim veličina podataka premaši veličinu predmemorije,
potpuno asocijativna predmemorija "promaši" pri svakom pristupu memoriji.
Izravna predmemorija
Razmotrite različite veličine redova. - pokazuje maksimalni broj promašaja koje će procesor potrošiti za pristup elementima niza tijekom sljedećeg prolaska kroz liniju.
Kao što vidite, vrijeme pristupa memoriji ne povećava se dramatično, već s povećanjem količine podataka. Čim veličina podataka premaši veličinu predmemorije, doći će do promašaja pri svakom pristupu memoriji.
Stoga će za asocijativni cache korak biti okomit, dok će se za izravni cache postupno povećavati do dvostruke veličine predmemorije. Multi-asocijativna predmemorija bila bi prosječan slučaj, "nalet", barem zato što vrijeme pristupa ne može biti bolje od izravnog.
Ako govorimo o memoriji, onda je najbrža cache, zatim operativna, najsporija je swap, o tome nećemo ubuduće. S druge strane, različite razine predmemorije (u pravilu, današnji procesori imaju 2-3 razine predmemorije) imaju različite brzine odziva memorije: što je viša razina, to je sporija brzina odziva. I stoga, ako je linija smještena u prvu razinu predmemorije (koja je, usput rečeno, potpuno asocijativna), vrijeme odziva bit će kraće od vremena retka koji je znatno veći od veličine predmemorije prve razine. . Stoga će biti nekoliko platoa na grafikonu vremena odziva memorije u odnosu na veličinu retka - plato * odziva memorije i platoi uzrokovani različitim razinama predmemorije.
*Plato funkcije - ( i:x, f(xi) - f(xi+1)< eps: eps → 0 }
Počnimo s implementacijom
Za implementaciju ćemo koristiti C (ANSI C99).Kod je napisan brzo, uobičajenim prolazom kroz linije različitih duljina, manje od 10mb, koji se ponavljaju. (Dat ćemo male dijelove programa koji nose semantičko opterećenje).
Za (i = 0; i< 16; i++) { for (j = 0; j < L_STR; j++) A[j]++; }
Pogledamo grafikon – i vidimo jedan veliki korak. Ali u teoriji sve ispada sasvim u redu. Postalo je potrebno razumjeti: zašto se to događa? I kako to popraviti?
Očito, to se može dogoditi iz dva razloga: ili procesor nema predmemoriju ili je procesor tako dobar u pogađanju pristupa memoriji. Budući da je prva opcija bliža fikciji, razlog svemu je dobra prognoza pogodaka.
Činjenica je da danas daleko od vrhunskih procesora, osim principa prostorne lokalnosti, predviđaju i aritmetičku progresiju u redoslijedu pristupa memoriji. Stoga pristupi memoriji moraju biti nasumični.
Duljina randomiziranog niza trebala bi biti usporediva s duljinom glavnog niza kako bi se riješili velike granularnosti pristupa, kao i da duljina niza ne bi trebala biti potencija broja dva, zbog toga „prekrivanja ” - što može dovesti do odstupanja. Najbolje je postaviti konstantu granularnosti, uključujući ako je granularnost prost broj, tada se mogu izbjeći preklapajući učinci. A duljina randomiziranog niza je funkcija duljine niza.
za (i = 0; i< j; i++) {
for (m = 0; m < L; m++) {
for (x = 0; x < M; x++){
v = A[ random[x] + m ];
}
}
}
Nakon toga nas je iznenadila dugo očekivana "slika", o kojoj smo govorili na početku.
Program je podijeljen u 2 dijela - test i obrada podataka. Napišite skriptu u 3 retka za pokretanje ili je pokrenite 2 puta ručno, odlučite sami.
Veličina unosa za Linux.
#uključi
Windows listing size.c
#uključi
Općenito, mislim da je sve jasno, ali želio bih navesti nekoliko točaka.
Niz A deklariran je kao nepostojan - ova nam direktiva jamči da će uvijek biti poziva nizu A, odnosno neće ih "izrezati" ni optimizator ni kompajler. Također je vrijedno spomenuti da se cijelo računsko opterećenje izvodi prije mjerenja vremena, što nam omogućuje smanjenje utjecaja pozadine.
Datoteka je prevedena u asembler na Ubuntu 12.04 i kompajler gcc 4.6 - ciklusi su sačuvani.
Obrada podataka
Logično je koristiti izvedenice za obradu podataka. I unatoč činjenici da se s povećanjem reda diferencijacije povećava i šum, koristit će se drugi izvod i njegova svojstva. Koliko god druga derivacija bila bučna, zanima nas samo predznak druge derivacije.Pronalazimo sve točke u kojima je druga derivacija veća od nule (s određenom greškom jer je druga derivacija, osim što se brojčano razmatra, vrlo bučna). Postavljamo funkciju ovisnosti predznaka druge derivacije funkcije o veličini cache memorije. Funkcija poprima vrijednost 1 u točkama gdje je predznak druge derivacije veći od nule, odnosno nulu ako je predznak druge derivacije manji ili jednak nuli.
Poletišta su početak svakog koraka. Također, prije obrade podataka potrebno je ukloniti pojedinačne outliere koji ne mijenjaju semantičko opterećenje podataka, ali stvaraju zamjetan šum.
Ispis datoteke data_pr.c
#uključi
Testovi
CPU/OS/verzija kernela/prevodilac/ključevi prevođenja - bit će navedeni za svaki test.
Intel Pentium CPU P6100 @2,00 GHz / Ubuntu 12.04 / 3.2.0-27-generic / gcc -Wall -O3 size.c -lrtL1 = 0,05 Mb
L2 = 0,2 Mb
L3 = 2,7 Mb- Neću dati sve dobre testove, razgovarajmo o "Grabljama"
Razgovarajmo o "grabljama"
Rake je otkriven tijekom obrade podataka na poslužiteljskom procesoru Intel Xeon 2.4/L2 = 512 kb/Windows Server 2008Problem je u malom broju točaka koje ulaze u interval postizanja platoa - prema tome, skok u drugoj derivaciji je neprimjetan i uzima se kao šum.
Ovaj problem možete riješiti metodom najmanjih kvadrata ili provesti testove tijekom određivanja zona platoa.
Volio bih čuti vaše prijedloge kako riješiti ovaj problem.
Bibliografija
- Makarov A.V. Arhitektura računala i programiranje niske razine.
- Ulrich Drepper
Predmemorija s izravnim preslikavanjem (postavljanjem);
potpuno asocijativna predmemorija;
· višestruki asocijativni cache ili djelomično asocijativni.
Izravno preslikana predmemorija(smještaj) je najviše
jednostavan tip međuspremnika. Memorijska adresa jedinstveno identificira niz
cache u koji će biti smješten blok informacija. U isto vrijeme, pre-
Pretpostavlja se da je RAM podijeljen na blokove i svaki
kojem bloku u međuspremniku je dana samo jedna linija. Ovo je jednostavna i jeftina metoda prikaza za implementaciju. Njegov glavni nedostatak je rigidna dodjela jednog retka u predmemoriji određenim OP blokovima. Stoga, ako program naizmjenično pristupa riječima iz dva različita bloka mapirana u isti red predmemorije, taj će se red stalno ažurirati i vjerojatnost pogotka bit će mala.
Potpuno asocijativna predmemorija nadilazi nedostatak izravnog dopuštajući učitavanje bilo kojeg RAM bloka u bilo koju liniju predmemorije. Upravljačka logika razlikuje dva polja u UE adresi: polje oznake i polje riječi. Polje oznake odgovara adresi OP bloka. Kako bi provjerila postoji li kopija bloka u predmemoriji, logika kontrole predmemorije mora istovremeno provjeriti podudaranje oznaka svih redaka s poljem oznake adrese. Asocijativno mapiranje pruža fleksibilnost u odabiru retka za novo snimljeni blok. Temeljni nedostatak ove metode je potreba za korištenjem skupe asocijativne memorije.
Višestruki asocijativni tip ili djelomično asocijativni tip prikaza − ovo je jedan od mogućih kompromisa, kombinirajući prednosti izravne i asocijativne metode. Priručna memorija (i oznake i podaci) podijeljena je na nekoliko modula. Ovisnost između modula i OP blokova je čvrsta kao u izravnom preslikavanju. Ali postavljanje blokova duž linija modula je proizvoljno, a asocijativni princip se koristi za traženje željene linije unutar modula. Ova metoda prikaza je najčešće korištena u modernim mikroprocesorima.
Mapiranje OP sektora u predmemoriju.
Ova vrsta prikaza koristi se u svim modernim računalima i sastoji se u činjenici da je cijeli OP podijeljen na sektore koji se sastoje od fiksnog broja uzastopnih blokova. Priručna memorija također je podijeljena na sektore koji sadrže isti broj redaka. Položaj blokova u OP sektoru i sektoru predmemorije potpuno je isti. Preslikavanje sektora u predmemoriju izvodi se asocijativno, tako da se bilo koji sektor iz RAM-a može smjestiti u bilo koji sektor predmemorije. Dakle, u procesu rada, ALU se okreće OP-u u potrazi za sljedećom naredbom, kao rezultat toga, u predmemoriju (u nedostatku bloka koji sadrži ovu naredbu), čitav sektor informacija iz OP-a učitava se u predmemoriju, štoviše, prema načelu lokalnosti, zbog toga se značajno povećava brzina sustava.
Hijerarhijski model predmemorije
U pravilu, cache memorija ima višerazinsku arhitekturu. Na primjer, u računalu s 32 KB interne (u CPU jezgri) i 1 MB vanjske (u CPU kućištu ili na matičnoj ploči) predmemorije, prva bi se smatrala predmemorijom razine 1 (L1), a potonja bi bila predmemorija 2 -ta razina (L2). U modernim poslužiteljskim sustavima broj razina predmemorije može biti do četiri, iako se najčešće koriste dvije ili tri razine.
U nekim procesorskim arhitekturama, L1 predmemorija je podijeljena u predmemoriju instrukcija (InstructionCache, I-cache) i podatkovnu predmemoriju (DataCache, D-cache), ne nužno iste veličine. Sa stajališta sklopova, lakše je i jeftinije dizajnirati odvojene I-cache i D-cache: dohvaćanje naredbi provodi I-box, a podatke dohvaćaju E-box i F-box , iako su u oba slučaja uključeni A-box i C-box. Svi su ti blokovi veliki i problematično im je omogućiti simultani i brzi pristup istoj predmemoriji. Osim toga, to bi neizbježno zahtijevalo povećanje broja pristupnih priključaka, što također komplicira zadatak projektiranja.
Budući da I-cache i D-cache moraju osigurati vrlo nisku latenciju pristupa (ovo vrijedi za bilo koji L1 cache), moraju žrtvovati svoju veličinu - obično je to od 16 do 32 KB. Uostalom, što je manja veličina predmemorije, to je lakše postići pristup s niskom latencijom.
Priručna memorija 2. razine u pravilu je unificirana, odnosno može sadržavati i naredbe i podatke. Ako je ugrađen u jezgru procesora, onda se govori o S-cache (SecondaryCache, sekundarna predmemorija), inače - o B-cache (BackupCache, backup cache). U modernim poslužiteljskim procesorima, volumen S-cache-a je od jednog do nekoliko megabajta, aB-cache-a - do 64 MB. Ako dizajn CPU-a predviđa prisutnost ugrađene predmemorije treće razine, tada se naziva T-cache (TernaryCache, tercijarna predmemorija). U pravilu, svaka sljedeća razina predmemorije je sporija, ali veća od prethodne. Ako je B-cache prisutan u sustavu (kao posljednja razina modela cache memorije), tada ga mogu kontrolirati i CPU i sistemska logika.
Ako u trenutku izvođenja određene instrukcije u registrima nema podataka za nju, tada će se oni tražiti od najbliže cache razine, odnosno od D-cache-a. Ako nisu u D-Cacheu, zahtjev se šalje S-cacheu, itd. U najgorem slučaju, podaci će biti isporučeni izravno iz memorije. Međutim, moguća je još tužnija opcija, kada ih podsustav upravljanja virtualnom memorijom operativnog sustava (OS) uspije natjerati u straničnu datoteku na tvrdom disku. U slučaju isporuke iz RAM-a, gubitak vremena za primanje potrebnih podataka može iznositi od desetaka do stotina CPU ciklusa, a u slučaju podataka na tvrdom disku već se može govoriti o milijunima ciklusa.
Asocijativnost predmemorije
Jedna od temeljnih karakteristika cache memorije - razina asocijativnosti - odražava njezinu logičku segmentaciju. Činjenica je da bi sekvencijalno nabrajanje svih redova predmemorije u potrazi za potrebnim podacima zahtijevalo desetke ciklusa i poništilo bi sav dobitak od korištenja memorije ugrađene u CPU. Stoga su RAM ćelije čvrsto povezane za predmemoriranje redaka (svaki red može sadržavati podatke iz fiksnog skupa adresa), što značajno smanjuje vrijeme pretraživanja. Više od jedne linije predmemorije može biti povezano sa svakom RAM ćelijom: na primjer, n-smjerna asocijativnost znači da se informacije na određenoj RAM adresi mogu pohraniti u n lokacija predmemorije.
Odabir mjesta može se provesti prema različitim algoritmima, među kojima se najčešće koriste principi zamjene LRU (LeastRecentlyUsed, zadnji traženi unos se zamjenjuje) i LFU (LeastFrequentlyUsed, najmanje često tražen), iako postoje modifikacije ovih principa. Na primjer, potpuno asocijativna predmemorija (fullyassociative), u kojoj se informacije smještene na proizvoljnoj adresi u RAM-u mogu smjestiti u proizvoljan redak. Druga mogućnost je izravno mapiranje, u kojem se informacije koje se nalaze na proizvoljnoj adresi u RAM-u mogu smjestiti na samo jedno mjesto u predmemoriju. Naravno, ova opcija pruža najveće performanse, budući da će kontroler morati "pogledati" samo u jednu cache liniju prilikom provjere informacija, ali je i najmanje učinkovita, jer kontroler neće odabrati "optimalno" mjesto prilikom pisanja. Za istu količinu predmemorije, shema pune asocijativnosti bit će najmanje brza, ali najučinkovitija.
U praksi se susreće potpuno asocijativna predmemorija, ali u pravilu ima vrlo malu količinu. Na primjer, CPU Cyrix 6x86 koristio je 256 bajtova ove predmemorije instrukcija ispred objedinjene predmemorije L1 od 16 ili 64 KB. Često se potpuno asocijativna shema koristi pri projektiranju TLB-ova (o čemu će biti riječi u nastavku), predmemorija adresa skokova, međuspremnika za čitanje i pisanje, itd. U pravilu, razine asocijativnosti I-cache-a i D-cache-a su prilično niske (do na četiri kanala) - njihovo povećanje Neprikladno je jer dovodi do povećanja kašnjenja pristupa i, kao rezultat toga, negativno utječe na performanse. Kao neka kompenzacija, asocijativnost S-cachea je povećana (obično do 16 kanala), budući da su kašnjenja u pristupu ovom cacheu nevažna. Na primjer, prema studiji o često korištenim cjelobrojnim zadacima, Intel Pentium III je imao 16K bajtova četverostruke D-cache memorije koja je pokrivala oko 93% zahtjeva, a 16K bajtova četverostruke I-cache memorije pokrivala je 99% zahtjeva.
Veličina retka i oznake predmemorije
Važna karakteristika predmemorije je veličina retka. U pravilu se po liniji koristi jedan adresni zapis (tzv. tag) koji označava kojoj adresi u RAM-u odgovara dati red. Očito je da je numeriranje pojedinačnih bajtova neprikladno, budući da će u ovom slučaju količina nadzemnih informacija u predmemoriji nekoliko puta premašiti količinu samih podataka. Stoga se jedna oznaka obično oslanja na jedan redak, koji je obično veličine 32 ili 64 bajta (stvarni maksimum je 1024 bajta), i ekvivalentan je četiri (ponekad osam) bita sabirnice podataka sustava. Osim toga, svaki red predmemorije popraćen je nekim informacijama kako bi se osigurala tolerancija na pogreške: jedan ili više bitova parnosti (parity) ili osam ili više bajtova otkrivanja i ispravljanja pogrešaka (ECC, ErrorCheckingandCorrecting), iako u masovnim rješenjima često ne koriste niti jedno ili drugo.
Veličina oznake predmemorije ovisi o tri glavna čimbenika: veličini predmemorije, maksimalnoj količini RAM-a koja se može predmemorirati i asocijativnosti predmemorije. Matematički se ta veličina izračunava formulom:
Stag=log2(Smem*A/Scache),
gdje je Stag veličina jedne oznake predmemorije, u bitovima; Smem - maksimalna količina RAM-a koja se može predmemorirati, u bajtovima; Scache - količina cache memorije, u bajtovima; A - asocijativnost predmemorije, u kanalima.
Iz toga slijedi da bi sustav s 1 GB RAM-a i 1 MB predmemorije s dvokanalnom asocijativnošću zahtijevao 11 bitova za svaku oznaku. Važno je napomenuti da sama veličina retka predmemorije ni na koji način ne utječe na veličinu oznake, ali obrnuto utječe na broj oznaka. Treba razumjeti da veličina retka predmemorije nema smisla činiti je manjom od širine bita sabirnice podataka sustava, ali višestruko povećanje veličine dovest će do pretjeranog začepljenja predmemorije nepotrebnim informacijama i pretjeranog opterećenja na sistemsku sabirnicu i memorijsku sabirnicu. Osim toga, maksimalna količina predmemorije koja se može predmemorirati ne mora odgovarati maksimalnoj količini RAM-a koja se može instalirati na sustav. Ako dođe do situacije da ima više RAM-a nego što se može predmemorirati, tada će predmemorija sadržavati informacije samo iz nižeg segmenta RAM-a. Upravo je to bila situacija sa Socket7/Super7 platformom. Čipseti za ovu platformu dopuštali su velike količine RAM-a (od 256 MB do 1 GB), dok je količina predmemorije često bila ograničena na prvih 64 MB (govorimo o B-cacheu koji se nalazi na matičnoj ploči) zbog upotrebe jeftinih 8-bitnih tag SRAM čipova (od kojih su 2 bita bila rezervirana za indikatore valjanosti i promjenu linije). To je rezultiralo primjetnim padom performansi.
