RSS

Jak działa cache

Liczba odsłon: 1528

W daw­nych, daw­nych cza­sach ukła­dy dyna­micz­nej pa­mię­ci opera­cyj­nej by­ły tak szyb­kie, że pro­du­cen­ci pro­ce­so­rów po­waż­nie za­sta­na­wia­li się nad sen­sem umiesz­cza­nia we­wnątrz pro­ce­so­ra wię­cej niż kil­ku re­jest­rów. Od te­go cza­su wszyst­ko się zmie­ni­ło: obec­ne pro­ce­so­ry w cza­sie po­trzeb­nym do od­czy­ta­nia z pa­mię­ci opera­cyj­nej kil­ku baj­tów da­nych są w sta­nie wy­ko­nać kil­ka­dzie­siąt roz­ka­zów, z bra­ku da­nych mu­szą jed­nak cze­kać we wstrzy­ma­niu na in­for­mac­je na­pły­wa­ją­ce po­wo­li z pa­mię­ci RAM.

Nowo­czes­ne roz­wią­za­nia – sze­ro­ka ścież­ka da­nych, dwu­ka­na­ło­wa pra­ca pa­mię­ci, tech­ni­ka DDR – zwięk­sza­ją mak­sy­mal­ną prze­pus­to­wość pa­mię­ci, częs­to prze­kra­cza­jąc na­wet teo­re­tycz­ną szczy­to­wą prze­pus­to­wość ma­gi­stra­li pro­ce­so­ra. Procesor jed­nak od­czy­tu­je z pa­mię­ci po­je­dyn­cze baj­ty lub sło­wa, co zmar­no­wa­ło­by ca­ły po­ten­cjał wy­daj­noś­ci, głów­nym prob­le­mem pa­mię­ci dyna­micz­nej jest bo­wiem czas do­stę­pu, któ­ry – choć przez kil­ka ostat­nich lat spadł z po­zio­mu 70 ns do oko­lic 30 ns – jest wie­lo­krot­nie dłuż­szy od cza­su trwa­nia cyk­lu ma­gi­stra­li pro­ce­so­ra.

Rozwią­za­niem sta­ła się pa­mięć pod­ręcz­na — ca­che.

Czym jest ca­che

Idea pa­mię­ci pod­ręcz­nej jest pros­ta: na dro­dze z pro­ce­so­ra do pa­mię­ci opera­cyj­nej na­le­ży umieś­cić do­dat­ko­wy mo­duł bar­dzo szyb­kiej pa­mię­ci o nie­wiel­kiej po­jem­noś­ci, któ­re­go za­da­niem bę­dzie bu­fo­ro­wa­nie naj­częś­ciej uży­wa­nych da­nych w na­dziei, że zo­sta­ną one uży­te po­now­nie. Jednocześ­nie bu­fo­ro­wa­nie po­win­no wy­ko­rzys­ty­wać wy­so­ką szczy­to­wą prze­pus­to­wość pa­mię­ci opera­cyj­nej, in­for­mac­je od­czy­tu­jąc z niej „z za­pa­sem”, dzię­ki cze­mu na­raz prze­sy­ła­nych jest wię­cej da­nych.

Umiejscowienie pamięci podręcznej

W ro­li pa­mię­ci pod­ręcz­nej do­sko­na­le spraw­dza się pa­mięć sta­tycz­na (SRAM). Choć jest ona dro­ga w pro­duk­cji i nie­opła­cal­ne jest bu­do­wa­nie z niej mo­du­łów o po­jem­noś­ci więk­szej niż kil­ka me­ga­baj­tów, jest nie­sa­mo­wi­cie szyb­ka, nie wy­ma­ga od­świe­ża­nia za­war­toś­ci i zwra­ca war­tość spod do­wol­ne­go adre­su w prze­wi­dy­wal­nym, zaw­sze ta­kim sa­mym cza­sie. Niewielka po­jem­ność nie jest tu w ogó­le wa­dą, gdyż pa­mięć pod­ręcz­na o roz­mia­rze prze­kra­cza­ją­cym kil­ka me­ga­baj­tów za­czę­ła­by tra­cić ce­chy bu­fo­ra, sta­jąc się… pa­mię­cią właś­ci­wą.

Jak so­bie z tym ra­dzo­no kie­dyś

Pamięć pod­ręcz­na nie jest wy­mys­łem „ery Pentium”. Pewne jej pros­te for­my sto­so­wa­no już w tak archa­icz­nych obec­nie mik­ro­pro­ce­so­rach, jak na przy­kład MOS 6502 czy Intel 8086. W oby­dwu przy­pad­kach nie­wiel­ki, kil­ku­baj­to­wy ob­szar szyb­kiej pa­mię­ci prze­cho­wy­wał po­bra­ny z wy­prze­dze­niem kod ko­lej­ne­go roz­ka­zu. Pozwala­ło to mi­kro­pro­ce­so­ro­wi roz­po­cząć wy­ko­ny­wa­nie ko­lej­nej ope­rac­ji bez mar­no­wa­nia cza­su na po­bie­ra­nie roz­ka­zu i pa­ra­met­rów na­tych­mias­to­wych — do­stęp do pa­mię­ci prze­ry­wa­ją­cy wy­ko­na­nie dzia­ła­nia na­stę­po­wał je­dy­nie, jeś­li nie­zbęd­ne by­ło sięg­nię­cie do ja­kiejś dal­szej ko­mór­ki pa­mię­ci.

Choć zysk wy­ni­ka­ją­cy z za­sto­so­wa­nia ta­kie­go me­cha­niz­mu był nie­sa­mo­wi­ty, moż­na by­ło wal­czyć o wię­cej. Taka pros­ta pa­mięć pod­ręcz­na by­ła cał­ko­wi­cie nie­sku­tecz­na w przy­pad­ku wy­ko­na­nia roz­ka­zu sko­ku, nie bu­fo­ro­wa­ła też w ogó­le od­wo­łań do da­nych nie wy­stę­pu­ją­cych bez­po­śred­nio w ko­dzie roz­ka­zu. W efek­cie źle na­pi­sa­ny pro­gram mógł ugrzęz­nąć bez­na­dziej­nie w ope­rac­jach wy­ko­ny­wa­nych z udzia­łem pa­mię­ci opera­cyj­nej.

Krok pierw­szy: bez­po­śred­nio od­wzo­ro­wu­ją­ca pa­mięć pod­ręcz­na

Najprostszą for­mą pa­mię­ci pod­ręcz­nej nie po­sia­da­ją­cej wy­mie­nio­nych wad jest bez­po­śred­nio od­wzo­ro­wu­ją­ca pa­mięć pod­ręcz­na (ang. direct mapped ca­che me­mo­ry). Buforuje ona da­ne w pacz­kach o jed­na­ko­wej wiel­koś­ci zwa­nych li­nia­mi (ang. ca­che line) — na ty­le du­żych, by moż­li­we by­ło wy­ko­rzys­ta­nie ol­brzy­miej prze­pu­sto­wo­ści pa­mię­ci opera­cyj­nej i wczy­ty­wa­nie da­nych „na za­pas”, na ty­le nie­wiel­kich jed­nak, by w ra­zie po­trze­by od­czy­ta­nia z pa­mię­ci jed­ne­go tyl­ko baj­tu da­nych nie od­czy­ty­wać bez sen­su wie­lu­dzie­się­ciu do­dat­ko­wych baj­tów, któ­rych pro­ce­sor mo­że nig­dy nie po­trze­bo­wać. Najczęściej li­nia ca­che ma roz­miar od 16 do 64 baj­tów, choć zda­rza­ją się roz­wią­za­nia, w któ­rych jest ona więk­sza.

Z roz­mia­ru linii pa­mię­ci pod­ręcz­nej wy­ni­ka też ziar­ni­stość po­dzia­łu pa­mię­ci opera­cyj­nej. Jeśli li­nia ma roz­miar 32 baj­tów, na za­pi­sa­nie adre­su baj­tu w niej za­war­te­go (tak zwa­ne­go prze­miesz­cze­nia) po­trzeb­nych jest 5 bi­tów. Pamięć opera­cyj­na jest za­tem dzie­lo­na na pacz­ki o wiel­koś­ci 32 baj­tów, by te 5 bi­tów adre­su sta­no­wi­ło 5 naj­mniej zna­czą­cych bi­tów adre­su fi­zycz­ne­go baj­tu w pa­mię­ci.

Każda li­nia pa­mię­ci pod­ręcz­nej ma też swój włas­ny adres. W pa­mię­ci pod­ręcz­nej o roz­mia­rze 32 KiB zmiesz­czą się 1 024 li­nie o po­jem­noś­ci 32 B, a więc na za­pi­sa­nie adre­su linii po­trze­ba 10 bi­tów. Te 10 bi­tów sta­no­wi bar­dziej zna­czą­cą część adre­su fi­zycz­ne­go baj­tu w pa­mię­ci.

Gdyby zsu­mo­wać po­da­ne w tym przy­kła­dzie roz­mia­ry adre­sów linii pa­mię­ci pod­ręcz­nej oraz prze­miesz­cze­nia (10 bi­tów i 5 bi­tów) uzys­ka­ło­by się wiel­kość 15 bi­tów, adre­su­ją­cą do­wol­ny frag­ment ciąg­łe­go, jed­no­li­te­go ob­sza­ru pa­mię­ci pod­ręcz­nej, któ­re­go po­dział na li­nie jest dla Cie­bie na ra­zie pew­nie – cze­mu się w ogó­le nie zdzi­wię – cał­ko­wi­cie nie­zro­zu­mia­ły. 15 bi­tów adre­su to jed­nak tyl­ko 32 KiB moż­li­wej do za­adre­so­wa­nia pa­mię­ci (i ta­ki jest właś­nie roz­miar na­szej przy­kła­do­wej pa­mię­ci pod­ręcz­nej) — a współ­czes­ne kom­pu­te­ry są wy­po­sa­żo­ne w pa­mięć opera­cyj­ną o po­jem­noś­ci idą­cej w me­ga­baj­ty lub wręcz gi­ga­baj­ty. Gdyby za­ło­żyć, że pa­mięć ma roz­miar tyl­ko 1 MiB, na za­pi­sa­nie do­wol­ne­go adre­su fi­zycz­ne­go po­trzeb­nych jest 20 bi­tów, a więc o 5 wię­cej, niż po­zwa­la za­adre­so­wać pa­mięć pod­ręcz­na.

Rozwiąza­nie jest pros­te: do­dat­ko­wą, naj­bar­dziej zna­czą­cą część adre­su (tu­taj 5 bi­tów) na­le­ży za­pi­sać wraz z każ­dą li­nią pa­mię­ci pod­ręcz­nej, by moż­na by­ło stwier­dzić, któ­re­mu wy­cin­ko­wi pa­mię­ci opera­cyj­nej ona od­po­wia­da. Tu ujaw­nia się sens po­dzia­łu pa­mię­ci pod­ręcz­nej na li­nie: po­nie­waż naj­mniej zna­czą­ca część adre­su fi­zycz­ne­go ko­mór­ki pa­mię­ci sta­no­wi wy­łącz­nie prze­miesz­cze­nie we­wnątrz linii, zaś środ­ko­wa część adre­su tra­fia zaw­sze w kon­kret­ną li­nię pa­mię­ci pod­ręcz­nej, o tym, czy ta li­nia za­wie­ra da­ne z po­cząt­ku, czy z koń­ca pa­mię­ci opera­cyj­nej mu­si de­cy­do­wać za­pi­sa­na wraz z nią naj­bar­dziej zna­czą­ca część adre­su — tak zwa­ny znacz­nik (ang. tag).

Tutaj też wi­dać skąd wzięła się naz­wa „bez­po­śred­nio od­wzo­ro­wu­ją­ca pa­mięć pod­ręcz­na”. Ponie­waż każ­da li­nia pa­mię­ci pod­ręcz­nej mo­że od­po­wia­dać jed­ne­mu z wie­lu wy­cin­ków pa­mię­ci opera­cyj­nej o ta­kiej sa­mej mniej zna­czą­cej częś­ci adre­su, w da­nym mo­men­cie zbu­fo­ro­wa­ny jest tyl­ko je­den z moż­li­wych wy­cin­ków. Jeśli pro­ce­sor spró­bu­je od­wo­łać się do in­ne­go wy­cin­ka o ta­kiej sa­mej mniej zna­czą­cej częś­ci adre­su, lecz le­żą­ce­go w in­nym ob­sza­rze pa­mię­ci opera­cyj­nej, za­war­tość linii pa­mię­ci pod­ręcz­nej bę­dzie mu­sia­ła się zmie­nić, aby od­wzo­ro­wy­wać te­raz in­ny ob­szar pa­mię­ci. W skraj­nym przy­pad­ku – gdy pro­ce­sor na zmia­nę bę­dzie od­wo­ły­wał się do tej sa­mej linii, ocze­ku­jąc jed­nak da­nych z dwóch róż­nych ob­sza­rów pa­mię­ci – wy­daj­ność kom­pu­te­ra dra­ma­tycz­nie się po­gor­szy, gdyż nie tyl­ko pa­mięć pod­ręcz­na nie speł­ni swo­je­go za­da­nia (gdyż za każ­dym ra­zem za­wie­rać bę­dzie ona „nie te da­ne”), ale wręcz spo­wol­ni ma­szy­nę, gdyż w do­brej wie­rze bę­dzie na za­pas od­czy­ty­wać z pa­mię­ci opera­cyj­nej wszyst­kie baj­ty linii — na­wet, jeś­li po­trzeb­ny jest tyl­ko je­den.

Przykład

Powyższy opis mo­że wie­lu prze­ra­zić. Choć sta­ra­łem się opi­sać spo­sób dzia­ła­nia bez­po­śred­nio od­wzo­ro­wu­ją­cej pa­mię­ci pod­ręcz­nej w moż­li­we naj­prost­szy spo­sób, jest to tak skom­pli­ko­wa­ne, że do­pie­ro po głęb­szym prze­my­śle­niu sta­je się jaś­niej­sze. Może na­stę­pu­ją­cy przy­kład po­mo­że Ci zro­zu­mieć dzia­ła­nie pa­mię­ci pod­ręcz­nej ty­pu direct mapped.

Dla pros­to­ty za­łóż­my, że pa­mięć pod­ręcz­na skła­da się tyl­ko z 16 linii (adres 4-bi­to­wy) o roz­mia­rze 32 B każ­da (prze­miesz­cze­nie 5-bi­to­we), a więc ma su­ma­rycz­ny roz­miar 512 B. Podłączmy ją do pro­ce­so­ra o 12-bi­to­wej ma­gi­stra­li adre­so­wej (ob­szar adre­so­wa­nia fi­zycz­ne­go: 4 KiB) i wy­ko­naj­my krok po kro­ku uprosz­czo­ny pro­gram od­wo­łu­ją­cy się do róż­nych ko­mó­rek pa­mię­ci (wszyst­kie po­niż­sze adre­sy za­pi­sa­ne są bi­nar­nie!):

  1. Procesor od­wo­łu­je się do ko­mór­ki pa­mię­ci o ad­re­sie 000 0001 11011. Pamięć pod­ręcz­na spraw­dza za­war­tość linii o ad­re­sie 0001 i stwier­dza, że nie za­wie­ra ona w ogó­le po­praw­nych da­nych, w związ­ku z tym po­bie­ra 32 B da­nych spod adre­sów 000 0001 xxxxx pa­mię­ci opera­cyj­nej i zwra­ca bajt o prze­miesz­cze­niu 11011 z od­czy­ta­nej linii. Wraz z li­nią pa­mię­ci pod­ręcz­nej za­pi­sy­wa­ny jest znacz­nik o war­toś­ci 000.
  2. Procesor od­wo­łu­je się do ko­mór­ki pa­mię­ci o ad­re­sie 000 0001 00011. Pamięć pod­ręcz­na spraw­dza za­war­tość linii o ad­re­sie 0001 i stwier­dza, że za­wie­ra ona po­praw­ne da­ne właś­nie ze znacz­ni­kiem 000 (a więc spod adre­sów fi­zycz­nych 000 0001 xxxxx), zwra­ca za­tem bajt o prze­miesz­cze­niu 00011 z wnęt­rza tej linii. Jest to tak zwa­ne tra­fie­nie (ang. ca­che hit).
  3. Procesor od­wo­łu­je się do ko­mór­ki pa­mię­ci o ad­re­sie 110 0001 10001. Pamięć pod­ręcz­na spraw­dza za­war­tość linii o ad­re­sie 0001 i stwier­dza, że za­wie­ra ona po­praw­ne da­ne ze znacz­ni­kiem 000 (a więc spod adre­sów fi­zycz­nych 000 0001 xxxxx), nie mo­że za­tem zwró­cić po­trzeb­nych pro­ce­so­ro­wi da­nych. Zawartość linii jest ka­so­wa­na, a w miej­sce po­przed­nio prze­cho­wy­wa­nych da­nych wczy­ty­wa­na jest za­war­tość pa­mię­ci opera­cyj­nej spod adre­sów 110 0001 xxxxx wraz ze znacz­ni­kiem 110. Po wczy­ta­niu linii zwra­ca­ny jest bajt o prze­miesz­cze­niu 10001 z wnęt­rza tej linii. Jest to tak zwa­ne pud­ło (ang. ca­che miss).

Jeśli spró­bu­jesz te­raz na zmia­nę wy­ko­ny­wać ope­rac­je 2. i 3. po­wyż­sze­go pro­gra­mu zo­ba­czysz, że pa­mięć pod­ręcz­na bę­dzie bez przer­wy „pud­ło­wać”, bez­na­dziej­nie za­peł­nia­jąc tę sa­mą li­nię da­ny­mi z dwóch róż­nych ob­sza­rów pa­mię­ci opera­cyj­nej o tej sa­mej środ­ko­wej częś­ci adre­su fi­zycz­ne­go. Jest to efekt właś­nie bez­po­śred­nie­go od­wzo­ro­wa­nia każ­dej z linii na wie­le ma­łych ob­sza­rów pa­mię­ci opera­cyj­nej o tym sa­mym środ­ku adre­su.

Najgorsze jest to, że bar­dzo trud­no jest unik­nąć spad­ku wy­daj­noś­ci zwią­za­ne­go z ciąg­ły­mi ko­liz­ja­mi za­war­toś­ci pa­mię­ci pod­ręcz­nej. W trak­cie pi­sa­nia pro­gra­mu, któ­ry bez­po­śred­nio ad­re­su­je pa­mięć, moż­na pró­bo­wać tak roz­miesz­czać uży­wa­ne na­prze­mien­nie blo­ki pa­mię­ci, by do opi­sy­wa­nej sytu­acji nig­dy nie do­szło. Co ma jed­nak po­cząć pro­gra­mis­ta wy­ko­rzy­stu­ją­cy w swo­im pro­gra­mie usłu­gi sys­te­mu opera­cyj­ne­go, któ­ry mo­że przy­dzie­lić apli­kac­ji blo­ki pa­mię­ci tak nie­for­tun­nie umiej­sco­wio­ne w pa­mię­ci, że pro­gram bę­dzie wlókł się jak żółw, prze­no­sząc tak na­praw­dę kil­ka ra­zy wię­cej da­nych, niż prze­wi­dział autor?

Rozwiąza­nie: asoc­ja­cyj­na pa­mięć pod­ręcz­na

Rozwiąza­nie prob­le­mu ciąg­łych ko­li­zji przy do­stę­pie do tej sa­mej linii pa­mię­ci pod­ręcz­nej, od­wzo­ro­wu­ją­cej jed­no­cześ­nie kil­ka róż­nych ob­sza­rów pa­mię­ci, jest tyl­ko jed­no: na­le­ży do­puś­cić sytu­ację, w któ­rej nie ist­nie­je sztyw­ne od­wzo­ro­wa­nie linii na blok pa­mię­ci opera­cyj­nej, a więc nie­istot­ny sta­je się adres linii pa­mię­ci pod­ręcz­nej, bę­dą­cy w bez­po­śred­nio od­wzo­ro­wu­ją­cej pa­mię­ci pod­ręcz­nej jed­no­cześ­nie środ­ko­wą częś­cią adre­su fi­zycz­ne­go.

Pamięć te­go ty­pu na­zy­wa się w peł­ni aso­cja­cyj­ną pa­mię­cią pod­ręcz­ną (ang. fully asso­cia­ti­ve ca­che me­mo­ry). W przy­pad­ku ta­kiej pa­mię­ci pod­ręcz­nej adres fi­zycz­ny dzie­lo­ny jest na dwie tyl­ko częś­ci: mniej zna­czą­cą, okre­śla­ją­cą prze­miesz­cze­nie baj­tu w ra­mach jed­nej linii, oraz bar­dziej zna­czą­cą, bę­dą­cą znacz­ni­kiem umoż­li­wia­ją­cym od­szu­ka­nie linii bu­fo­ru­ją­cej po­trzeb­ny frag­ment pa­mię­ci opera­cyj­nej. Rozwiąza­nie – wy­da­wa­ło­by się – ideal­ne. Niestety, rze­czy­wi­stość nie jest tak we­so­ła. By pa­mięć pod­ręcz­na by­ła od­po­wied­nio szyb­ka, od­szu­ka­nie właś­ci­wej linii mu­si być jak naj­szyb­sze. W przy­pad­ku bez­po­śred­nio od­wzo­ro­wu­ją­cej pa­mię­ci pod­ręcz­nej tę szyb­kość za­pew­nia­ło sztyw­ne po­wią­za­nie adre­su linii z adre­sem fi­zycz­nym — aby od­szu­kać właś­ci­wą li­nię pa­mię­ci pod­ręcz­nej wy­star­czy­ło od­czy­tać znacz­nik ściś­le okreś­lo­nej linii i spraw­dzić, czy od­po­wia­da on szu­ka­ne­mu adre­so­wi fi­zycz­ne­mu.

W peł­ni asoc­ja­cyj­na pa­mięć pod­ręcz­na nie ofe­ru­je ta­kie­go ułat­wie­nia. Do wy­bo­ru są dwie me­to­dy od­szu­ki­wa­nia linii: ite­ra­cyj­na, bar­dzo po­wol­na, pod­da­ją­ca w wątp­li­wość sens uży­wa­nia pa­mię­ci pod­ręcz­nej w ogó­le, oraz na­tych­mias­to­wa (rów­no­leg­ła), któ­ra wy­ma­ga osob­ne­go kom­pa­ra­to­ra znacz­ni­ków dla każ­dej z linii — a ich licz­ba idzie w set­ki ty­się­cy. W tym przy­pad­ku wy­daj­ność by­ła­by fas­cy­nu­ją­ca, jed­nak oku­pio­ne zo­sta­ło­by to nie­sa­mo­wi­tym kosz­tem: kil­ka­set tran­zy­sto­rów two­rzą­cych kil­ka­dzie­siąt baj­tów linii pa­mię­ci pod­ręcz­nej wy­ma­ga­ło­by do­dat­ko­wo kil­ku ty­się­cy tran­zy­sto­rów two­rzą­cych kom­pa­ra­tor!

Co by się jed­nak sta­ło, gdy­by spró­bo­wać po­łą­czyć sztyw­ne przy­po­rząd­ko­wa­nie linii pa­mię­ci pod­ręcz­nej do wie­lu ob­sza­rów pa­mię­ci (da­ją­ce szyb­kość wy­szu­ki­wa­nia) z za­ło­że­niem, że środ­ko­wa część adre­su fi­zycz­ne­go nie od­po­wia­da jed­nej tyl­ko linii? Powstanie wte­dy ścież­ko­wo asoc­ja­cyj­na pa­mięć pod­ręcz­na (ang. n-way set asso­cia­ti­ve ca­che me­mo­ry). W ol­brzy­mim uprosz­cze­niu pa­mięć te­go ty­pu jest zbu­do­wa­na z kil­ku nie­za­leż­nych blo­ków bez­po­śred­nio od­wzo­ro­wu­ją­cej pa­mię­ci pod­ręcz­nej, dzię­ki cze­mu środ­ko­wa część adre­su kie­ru­je ste­row­nik pa­mię­ci pod­ręcz­nej nie do jed­nej je­dy­nej linii, ale do dwóch, czte­rech, oś­miu lub na­wet więk­szej licz­by. I choć da­lej moż­na wy­ob­ra­zić so­bie sytu­ację, w któ­rej czte­ro­ścież­ko­wa asoc­ja­cyj­na pa­mięć pod­ręcz­na zo­sta­je wy­pro­wa­dzo­na w po­le przez pro­gram od­wo­łu­ją­cy się na zmia­nę do pię­ciu blo­ków pa­mię­ci o tej sa­mej środ­ko­wej częś­ci adre­su fi­zycz­ne­go, praw­do­po­do­bień­stwo ta­kie­go przy­pad­ku jest na ty­le nis­kie, że moż­na się nim zu­peł­nie nie przej­mo­wać.

Ścieżkowo asoc­ja­cyj­na pa­mięć pod­ręcz­na ma pra­wie sa­me za­le­ty. Sterownik te­go ty­pu pa­mię­ci jest nie­wie­le bar­dziej skom­pli­ko­wa­ny od ste­row­ni­ka bez­po­śred­nio od­wzo­ro­wu­ją­cej pa­mię­ci pod­ręcz­nej — po­trzeb­nych jest tyl­ko kil­ka do­dat­ko­wych kom­pa­ra­to­rów (ty­le, ile jest ście­żek asoc­ja­cji) oraz układ de­cy­zyj­ny wy­bie­ra­ją­cy ścież­kę asoc­ja­cji, w któ­rej w ra­zie ko­li­zji na­stą­pi za­mia­na za­war­toś­ci linii. Najpoważ­niej­szym prob­le­mem jest właś­nie wy­bór stra­tegii za­mia­ny za­war­toś­ci linii: przy­kła­do­we moż­li­woś­ci to wy­bór ścież­ki asoc­ja­cji naj­dłu­żej nie uży­wa­nej lub pros­ty wy­bór ko­lej­nych ście­żek asoc­ja­cji.

Pozosta­ją jesz­cze dwa py­ta­nia: ile ście­żek asoc­ja­cji po­win­na za­wie­rać pa­mięć pod­ręcz­na i czy le­piej jest mieć wię­cej ście­żek o mniej­szym roz­mia­rze, czy mniej o więk­szym. Na pierw­sze z nich od­po­wiedź jest pros­ta: wy­ko­na­ne do­świad­cze­nia do­wiod­ły, że już dwie ścież­ki asoc­ja­cji (ang. 2-way set asso­cia­ti­ve ca­che me­mo­ry) są roz­wią­za­niem bar­dzo do­brym, zaś osiem ście­żek asoc­ja­cji (ang. 8-way set asso­cia­ti­ve) pra­wie do­rów­nu­je wy­daj­noś­cią w peł­ni asoc­ja­cyj­nej pa­mię­ci pod­ręcz­nej i zwięk­sza­nie licz­by ście­żek asoc­ja­cji po­wy­żej oś­miu nie da­je już w za­sa­dzie przy­ro­stu wy­daj­noś­ci.

Gorzej jest z dru­gim py­ta­niem, gdyż od­po­wiedź mu­si brzmieć: to za­le­ży od za­sto­so­wań. Programom mul­ti­me­dial­nym, prze­twa­rza­ją­cym sek­wen­cyj­nie nie­licz­ne, ol­brzy­mie blo­ki da­nych nie­wiel­ka licz­ba ście­żek asoc­ja­cji nie za­szko­dzi, zaś po­więk­sze­nie roz­mia­ru linii pa­mię­ci pod­ręcz­nej mo­że zna­czą­co pod­nieść szyb­kość ich dzia­ła­nia. Z kolei opro­gra­mo­wa­nie biu­ro­we mi­ni­mal­nie le­piej spra­wu­je się z pa­mię­cią pod­ręcz­ną o wie­lu ścież­kach asoc­ja­cji o nie­wiel­kim roz­mia­rze, a zwięk­sza­nie roz­mia­ru linii ra­czej zmniej­sza wy­daj­ność. Nie dzi­wi za­tem fakt, że ol­brzy­mia więk­szość obec­nie pro­du­ko­wa­nych mi­kro­pro­ce­so­rów dys­po­nu­je czte­re­ma lub ośmio­ma ścież­ka­mi asoc­ja­cji pa­mię­ci pod­ręcz­nej (nie­za­leż­nie od jej roz­mia­ru), zaś po­jem­ność linii oscy­lu­je mię­dzy 32 B a 64 B.

Write back? Write through?

Dotych­czas ana­li­zo­wa­łem dzia­ła­nie pa­mię­ci pod­ręcz­nej wy­łącz­nie w ra­mach wspo­ma­ga­nia ope­rac­ji od­czy­tu da­nych. Praktycz­na reali­zac­ja te­go ty­pu pa­mię­ci pod­ręcz­nej, pra­cu­ją­ca w na­zy­wa­nym z an­giel­ska try­bie write-through, nie bie­rze udzia­łu w ope­rac­ji za­pi­su da­nych do pa­mię­ci, po­za ewen­tu­al­nym zaktua­li­zo­wa­niem linii, któ­rej za­war­tość mo­że się w wy­ni­ku te­go za­pi­su zmie­nić. Dane prze­cho­wy­wa­ne w pa­mię­ci pod­ręcz­nej są za­tem bez przer­wy aktu­al­ne, jed­nak za­pis da­nych trwa tak sa­mo dłu­go, co w przy­pad­ku cał­ko­wi­te­go bra­ku pa­mię­ci pod­ręcz­nej.

Pamięć pod­ręcz­na mo­że jed­nak wspie­rać ope­ra­cję za­pi­su da­nych do pa­mię­ci. Pamięć ty­pu write-back po wy­kry­ciu cyk­lu za­pi­su da­nych do pa­mię­ci opera­cyj­nej aktua­li­zu­je za­war­tość od­po­wied­niej linii i usta­wia osob­ny bit (fla­gę) in­for­mu­ją­cy o tym, że jest ona „brud­na”, to zna­czy że za­wie­ra da­ne now­sze, niż za­pi­sa­ne w pa­mię­ci opera­cyj­nej (ang. dirty flag lub mo­di­fied flag). Dzięki te­mu wie­le ope­rac­ji za­pi­su po­je­dyn­czych baj­tów lub słów da­nych mo­że zo­stać sku­mu­lo­wa­nych i rzeczy­wiś­cie wy­ko­na­nych do­pie­ro w mo­men­cie, gdy zmo­dy­fi­ko­wa­na li­nia mu­si zo­stać usu­nię­ta z pa­mię­ci pod­ręcz­nej.

Takie uspraw­nie­nie dzia­ła­nia pa­mię­ci pod­ręcz­nej da­je za­uwa­żal­ny przy­rost wy­daj­noś­ci, spra­wia jed­nak kons­truk­to­rom pro­ce­so­rów i kom­pu­te­rów do­dat­ko­we kło­po­ty. Wszystkie od­wo­ła­nia do pa­mię­ci opera­cyj­nej – rów­nież te nie po­cho­dzą­ce od pro­ce­so­ra – mu­szą zo­stać prze­ana­li­zo­wa­ne i ob­słu­żo­ne przez ste­row­nik pa­mię­ci pod­ręcz­nej. Wyobraź so­bie sytu­ację, w któ­rej pro­ce­sor za­pi­su­je w pa­mię­ci da­ne prze­zna­czo­ne dla dys­ku twar­de­go, po czym ste­row­nik dys­ku, się­ga­jąc bez­po­śred­nio do pa­mię­ci opera­cyj­nej, znaj­du­je pod po­da­nym adre­sem zu­peł­nie przy­pad­ko­we da­ne, gdyż właś­ci­we za­pi­sa­ne zo­sta­ły tyl­ko w pa­mię­ci pod­ręcz­nej! Z te­go po­wo­du na­wet od­wo­ła­nia do za­war­toś­ci pa­mię­ci opera­cyj­nej rea­li­zo­wa­ne przez me­cha­nizm DMA mu­szą al­bo być rea­li­zo­wa­ne za po­śred­nic­twem ste­row­ni­ka pa­mię­ci pod­ręcz­nej, al­bo też wstrzy­my­wa­ne do cza­su zaktua­li­zo­wa­nia da­nych prze­cho­wy­wa­nych w pa­mię­ci opera­cyj­nej.

Architektura write-back cache

Jeszcze więk­szy kło­pot spra­wia­ją kom­pu­te­ry wie­lo­pro­ce­so­ro­we, w któ­rych każ­dy pro­ce­sor dys­po­nu­je włas­ną pa­mię­cią pod­ręcz­ną. Operacja za­pi­su wy­ko­na­na przez je­den z pro­ce­so­rów mu­si zo­stać roz­gło­szo­na na ma­gi­stra­li, by po­zo­sta­łe jed­nost­ki obli­cze­nio­we (i ewen­tu­al­nie ste­row­ni­ki po­zo­sta­łych po­zio­mów pa­mię­ci pod­ręcz­nej) mog­ły usu­nąć ze swo­ich bu­fo­rów nie­pra­wid­ło­we już da­ne. W bar­dziej wy­ra­fi­no­wa­nych roz­wią­za­niach sto­su­je się osob­ny pro­to­kół uzgad­nia­nia spój­no­ści za­war­toś­ci pa­mię­ci pod­ręcz­nej (ang. ca­che cohe­ren­cy), by da­ne zmo­dy­fi­ko­wa­ne przez je­den z pro­ce­so­rów by­ły na­tych­miast mo­dy­fi­ko­wa­ne rów­nież w pa­mię­ci pod­ręcz­nej po­zo­sta­łych jed­nos­tek bu­fo­ru­ją­cych tę sa­mą li­nię da­nych.

Wielopo­zio­mo­wa pa­mięć pod­ręcz­na

Już przed chwi­lą wspom­nia­łem o tym, że w jed­nym sys­te­mie mik­ro­pro­ce­so­ro­wym wy­stę­po­wać mo­że kil­ka po­zio­mów pa­mię­ci pod­ręcz­nej. Powodem sto­so­wa­nia wie­lu po­zio­mów jest brak moż­li­woś­ci po­go­dze­nia szyb­koś­ci pra­cy pa­mię­ci sta­tycz­nej z jej po­jem­noś­cią i licz­bą nie­zbęd­nych do pra­cy tran­zy­sto­rów. Gdy w świe­cie archi­tek­tu­ry x86 naj­pierw po­ja­wi­ła się ze­wnętrz­na pa­mięć pod­ręcz­na za­mon­to­wa­na na pły­cie głów­nej kom­pu­te­ra (ang. exter­nal ca­che, za­sto­so­wa­na po raz pierw­szy w sys­te­mach opar­tych na pro­ce­so­rze Intel 80386 w roz­mia­rze od 64 KiB do 256 KiB), a na­stęp­nie pra­wie tak sa­mo efek­tyw­na we­wnętrz­na pa­mięć pod­ręcz­na umiesz­czo­na w sa­mym pro­ce­so­rze (ang. inter­nal ca­che, za­sto­so­wa­na po raz pierw­szy w pro­ce­so­rze Intel 80486 w roz­mia­rze 8 KiB), na­tu­ral­na sta­ła się chęć po­łą­cze­nia za­let ma­łej, ale nie­zwyk­le szyb­kiej we­wnętrz­nej i wol­niej­szej, ale bar­dzo po­jem­nej ze­wnętrz­nej pa­mię­ci pod­ręcz­nej.

Wszystkie po­zio­my pa­mię­ci pod­ręcz­nej (bo cza­sem jest ich wię­cej niż dwa) są wzglę­dem sie­bie cał­ko­wi­cie nie­za­leż­ne, mu­szą jed­nak ze so­bą współ­pra­co­wać, aby za­cho­wać spój­ność prze­cho­wy­wa­nych da­nych. Wewnętrz­na pa­mięć pod­ręcz­na dzię­ki umiesz­cze­niu w bez­po­śred­niej bli­sko­ści rdze­nia pro­ce­so­ra dys­po­nu­je ol­brzy­mią prze­pu­sto­wo­ścią, a jej archi­tek­tu­ra po­zwa­la na mak­sy­mal­ne skró­ce­nie cza­su do­stę­pu (oku­pio­ne względ­nie du­żą licz­bą tran­zy­sto­rów przy­pa­da­ją­cych na je­den bajt po­jem­noś­ci pa­mię­ci), bu­fo­ru­je za­tem da­ne naj­częś­ciej wy­ko­rzys­ty­wa­ne. Zewnętrz­na pa­mięć pod­ręcz­na, umiesz­czo­na po­cząt­ko­wo z da­la od pro­ce­so­ra, jest znacz­nie wol­niej­sza (a szcze­gól­nie pod wzglę­dem cza­su do­stę­pu), nad­ra­bia to jed­nak po­jem­noś­cią.

O ile na po­cząt­ku je­dy­nie we­wnętrz­na pa­mięć pod­ręcz­na by­ła sil­nie asoc­ja­cyj­na (czte­ry lub osiem ście­żek asoc­ja­cji), a zew­nętrz­ną pa­mięć pod­ręcz­ną rea­li­zo­wa­no naj­częś­ciej ja­ko bez­po­śred­nio od­wzo­ro­wu­ją­cą, po­stęp w elek­tro­ni­ce spo­wo­do­wał, że wy­po­sa­że­nie ze­wnętrz­nej pa­mię­ci pod­ręcz­nej w ste­row­nik ścież­ko­wo aso­cja­cyj­ny prze­sta­ło być prob­le­mem. Następ­nym kro­kiem by­ło już tyl­ko wbu­do­wa­nie pa­mię­ci pod­ręcz­nej dru­gie­go po­zio­mu (tyl­ko z przy­zwy­cza­je­nia na­zy­wa­nej da­lej „zew­nętrz­ną”) w sam pro­ce­sor (Intel Pentium II, AMD K6-III) — zwięk­sza­ła się dzię­ki te­mu szyb­kość jej dzia­ła­nia (tak pod wzglę­dem cza­su do­stę­pu, jak i szczy­to­wej prze­pu­sto­wo­ści), co cał­ko­wi­cie neu­tra­li­zo­wa­ło nie­wiel­ki spa­dek po­jem­noś­ci.

Obsługiwa­na po­jem­ność pa­mię­ci opera­cyj­nej

Właścicie­le star­szych płyt głów­nych (na przy­kład wy­po­sa­żo­nych w ze­staw ukła­dów Intel 430VX lub 430TX) zna­ją ten ból: po roz­sze­rze­niu pa­mię­ci po­wy­żej 64 MiB wy­daj­ność sys­te­mu przy nie­któ­rych ope­rac­jach wy­raź­nie spa­da mi­mo, iż teore­tycz­nie po­win­na przy­naj­mniej po­zo­stać bez zmian. Odpowie­dzial­ny za ta­ką sytu­ację jest ste­row­nik pa­mię­ci pod­ręcz­nej, a do­kład­niej zbyt ma­ła po­jem­ność ukła­du sca­lo­ne­go Tag SRAM, prze­cho­wu­ją­ce­go znacz­ni­ki po­szcze­gól­nych linii pa­mię­ci pod­ręcz­nej.

W przy­pad­ku wy­mie­nio­nych ze­sta­wów, układ Tag SRAM po­zwa­la prze­cho­wy­wać znacz­ni­ki o roz­mia­rze 7 bi­tów. Ponie­waż wbu­do­wa­ny w nie ste­row­nik pa­mię­ci pod­ręcz­nej ob­słu­gu­je do 16 Ki linii (adres 14-bi­to­wy) o roz­mia­rze 32 B (prze­miesz­cze­nie 5-bi­to­we), adres fi­zycz­ny mo­że mieć naj­wy­żej 26 bi­tów, co po­zwa­la za­adre­so­wać nie wię­cej niż 64 MiB pa­mię­ci opera­cyj­nej. Dostęp do po­zo­sta­łe­go ob­sza­ru rea­li­zo­wa­ny jest bez­po­śred­nio, a przed cał­ko­wi­tą klęs­ką wy­daj­no­ścio­wą kom­pu­ter chro­ni tyl­ko we­wnętrz­na pa­mięć pod­ręcz­na pro­ce­so­ra, któ­ra nie po­sia­da ta­kie­go ogra­ni­cze­nia.

Jako cie­ka­wo­stkę po­dam jesz­cze fakt, że na­wet względ­nie no­wo­czes­ny ze­staw ukła­dów, ja­kim jest Intel 430TX, reali­zu­je dru­gi po­ziom pa­mię­ci pod­ręcz­nej w try­bie direct mapped write-back, czy­li bez­po­śred­nio od­wzo­ro­wu­ją­cą z bu­fo­ro­wa­niem ope­rac­ji za­pi­su.

Von Neumann versus Harvard

Klasyczna archi­tek­tu­ra kom­pu­te­ra – naz­wa­na archi­tek­tu­rą von Neumanna – za­kła­da, że jed­nost­ka cen­tral­na wy­ko­nu­je sek­wen­cyj­nie ko­lej­ne roz­ka­zy po­bie­ra­ne z pa­mię­ci opera­cyj­nej, ope­ru­jąc na da­nych i wy­ni­kach prze­cho­wy­wa­nych rów­nież w tym sa­mym blo­ku pa­mię­ci. Choć da­je to nie­sa­mo­wi­tą elas­tycz­ność, zwal­nia­jąc kon­struk­to­ra kom­pu­te­ra z na­rzu­ca­nia sche­ma­tu po­dzia­łu pa­mię­ci i da­jąc twór­com opro­gra­mo­wa­nia wol­ność wy­bo­ru roz­mia­ru ko­du oraz blo­ku da­nych, bar­dziej efek­tyw­ne jest prze­zna­cze­nie osob­ne­go blo­ku pa­mię­ci na wy­ko­ny­wa­ny kod i osob­ne­go — na da­ne i wy­ni­ki. Architek­tu­ra opie­ra­ją­ca się o ta­ki po­dział na­zy­wa­na jest z kolei archi­tek­tu­rą har­wardz­ką.

Kompute­ry kla­sy PC zbu­do­wa­ne są zgod­nie z po­mys­łem von Neumanna, co ogra­ni­cza po­tenc­jal­ną wy­daj­ność obli­cze­nio­wą sto­so­wa­nych w nich pro­ce­so­rów. Inny jest prze­cież sche­mat wy­ko­rzys­ta­nia pa­mię­ci pro­gra­mu – czy­ta­nej sek­wen­cyj­nie z drob­ny­mi od­stępst­wa­mi po­wo­do­wa­ny­mi przez roz­ka­zy sko­ku oraz reali­zac­ję przer­wań – a in­ny — pa­mię­ci da­nych, któ­ra czy­ta­na mo­że być al­bo sek­wen­cyj­nie, al­bo w spo­sób cał­ko­wi­cie lo­so­wy.

Tutaj do ak­cji wkra­cza pierw­szy, naj­bliż­szy rdze­nio­wi pro­ce­so­ra po­ziom pa­mię­ci pod­ręcz­nej. Może on być prze­cież po­dzie­lo­ny na dwa nie­za­leż­ne blo­ki, z któ­rych je­den bu­fo­ru­je wy­łącz­nie kod pro­gra­mu (i umoż­li­wia je­dy­nie od­czy­ty­wa­nie po­szcze­gól­nych ko­mó­rek pa­mię­ci wraz z opty­ma­li­zac­ją od­czy­tu sek­wen­cyj­ne­go), a dru­gi — wszyst­kie da­ne. W ten spo­sób „od zew­nątrz” ma­my do czy­nie­nia z pro­ce­so­rem pra­cu­ją­cym wed­le za­sad okreś­lo­nych przez von Neumanna, „od środ­ka” ko­rzy­sta­jąc ze zwięk­szo­nej wy­daj­noś­ci da­wa­nej przez archi­tek­tu­rę har­wardz­ką.

Jeszcze cie­kaw­szy po­mysł za­sto­so­wa­ny zo­stał w pro­ce­so­rze Intel Pentium 4, któ­re­go pierw­szy po­ziom pa­mię­ci pod­ręcz­nej nie bu­fo­ru­je za­war­toś­ci pa­mię­ci opera­cyj­nej, a zde­ko­do­wa­ne już ko­dy mik­ro­ope­ra­cji. Dzięki ta­kie­mu roz­wią­za­niu (na­zy­wa­ją­ce­go się trace ca­che) w ra­zie po­now­ne­go wy­ko­ny­wa­nia te­go sa­me­go frag­men­tu ko­du po­mi­nię­ty mo­że zo­stać etap po­to­ku od­po­wie­dzial­ny za de­ko­do­wa­nie in­struk­cji x86, a więc skró­co­ny czas reali­zac­ji roz­ka­zu i zwięk­szo­na licz­ba jed­no­cześ­nie rea­li­zo­wa­nych roz­ka­zów. Oczywiś­cie frag­ment pa­mię­ci pod­ręcz­nej pierw­sze­go po­zio­mu bu­fo­ru­ją­cy da­ne dzia­ła w naj­zu­peł­niej kla­sycz­ny spo­sób.

Pod­su­mo­wa­nie

O za­le­tach pły­ną­cych z dzia­ła­nia pa­mię­ci pod­ręcz­nej prze­ko­nać się mo­że każ­dy: wy­star­czy w pro­gra­mie kon­fi­gu­ra­cyj­nym pły­ty głów­nej wy­łą­czyć na chwi­lę je­den z po­zio­mów pa­mię­ci pod­ręcz­nej, by otrzy­mać kom­pu­ter o wy­daj­noś­ci nie­wie­le więk­szej, niż pierw­sze ma­szy­ny wy­po­sa­żo­ne w pro­ce­sor 80486. Proste dwu­krot­ne roz­sze­rze­nie po­jem­noś­ci dru­gie­go po­zio­mu pa­mię­ci pod­ręcz­nej (zwią­za­ne obec­nie z wy­mia­ną pro­ce­so­ra na in­ny) mo­że rów­nież nie­wy­obra­żal­nie przy­spie­szyć kom­pu­ter mi­mo, iż pro­ce­sor na­dal pra­cu­je z ta­ką sa­mą częs­to­tli­woś­cią.

Pamiętać na­le­ży jed­nak, że pa­mięć pod­ręcz­na nie jest pa­na­ceum na prob­le­my z wy­daj­noś­cią kom­pu­te­ra. W nie­któ­rych za­sto­so­wa­niach pro­ce­sor z moc­no okro­jo­ną pa­mię­cią pod­ręcz­ną mo­że cha­rak­te­ry­zo­wać się do­sko­na­łą wy­daj­noś­cią (cze­go przy­kła­dem mo­że być świet­ne dzia­ła­nie pro­ce­so­rów Intel Celeron 266/300 czy AMD Duron w grach i nie­któ­rych za­sto­so­wa­niach mul­ti­me­dial­nych). Niektóre pro­ce­so­ry po roz­bu­do­wa­niu pa­mię­ci pod­ręcz­nej do­sta­ją skrzy­deł (vide Intel Pentium 4, któ­re­go dłu­gi po­tok i 64-baj­to­we li­nie pa­mię­ci pod­ręcz­nej czy­nią nie­zwyk­le za­leż­nym od szyb­kie­go do­stę­pu do pa­mię­ci), in­ne zaś rów­nie łat­wo moż­na przy­spie­szyć zwięk­sza­jąc ich tak­to­wa­nie o za­led­wie 100 MHz (przy­kła­dem mo­że być AMD Athlon XP). Dobre prze­ana­li­zo­wa­nie wy­daj­noś­ci pro­ce­so­ra i stop­nia, w ja­kim mo­że speł­nić Twoje ocze­ki­wa­nia wy­ma­ga przy­gląd­nię­cia się ca­łej je­go archi­tek­tu­rze, a nie tyl­ko pa­ra­met­rom wbu­do­wa­nej w nie­go pa­mię­ci pod­ręcz­nej.

Podziękowa­nia dla MiWa za dys­kus­ję
na gru­pie dys­ku­syj­nej pl.comp.pe­cet na te­mat
szcze­gółów funkcjo­no­wa­nia pa­mię­ci pod­ręcz­nej.