Image Processing

Кэш с пря­мым отоб­ра­же­ни­ем ад­ре­сов

Не­смот­ря на то, что пол­но­стью ас­со­ци­а­тив­ный кэш об­ла­да­ет са­мы­ми луч­ши­ми свой­ства­ми, он ред­ко ис­поль­зу­ет­ся на прак­ти­ке из-за боль­ших на­клад­ных рас­хо­дов при ап­па­рат­ной реа­ли­за­ции. По­это­му рас­смот­рим на­бо­лее про­стой ва­ри­ант: кэш с пря­мым отоб­ра­же­ни­ем ад­ре­сов. В та­ком кэ­ше каж­дый байт опе­ра­тив­ной па­мя­ти мо­жет по­пасть толь­ко в од­но ме­сто кэш-па­мя­ти.

Как и рань­ше, раз­де­лим кэш на стро́ки, и в каж­дой стро­ке кэ­ша бу­дем хра­нить не­сколь­ко (на­при­мер, 16) байт опе­ра­тив­ной па­мя­ти. Кро­ме то­го, пред­по­ло­жим, что кэш име­ет 65536 строк (та­ким об­ра­зом, объ­ём кэш-па­мя­ти ра­вен 16×65536 = 1 Ме­га­байт).

Что­бы опре­де­лить, в ка­кое ме­сто кэш-па­мя­ти по­па­дёт за­дан­ный байт из опе­ра­тив­ной па­мя­ти, раз­де­лим ад­рес это­го бай­та на не­сколь­ко ча­стей. Пред­по­ло­жим, что ад­рес па­мя­ти со­сто­ит из 32-х бит:

То есть, гру­бо го­во­ря, стар­шие би­ты ад­ре­са от­бра­сы­ва­ют­ся, а млад­шие од­но­знач­но опи­сы­ва­ют ме­сто в кэш-па­мя­ти, в ко­то­рое бу­дет за­пи­сан за­дан­ный байт опе­ра­тив­ной па­мя­ти. Стар­шие би­ты (тег) да­ют нам «но­мер ме­га­бай­та» опе­ра­тив­ной па­мя­ти, а млад­шие — сме­ще­ние внут­ри это­го ме­га­бай­та. По­это­му каж­дый ме­га­байт опе­ра­тив­ной па­мя­ти отоб­ра­зит­ся в кэш (ри­су­нок 2). Тег хра­нит­ся в стро­ке кэш-па­мя­ти для то­го, что­бы опре­де­лить, из ка­ко­го имен­но ме­га­бай­та при­шла эта стро­ка.

Так как каж­дый байт опе­ра­тив­ной па­мя­ти мо­жет на­хо­дить­ся толь­ко в од­ном ме­сте кэш-па­мя­ти, при за­пи­си но­вых дан­ных в кэш нет не­об­хо­ди­мо­сти ре­шать, ка­кие дан­ные бу­дут из кэ­ша вы­тес­не­ны: вы­тес­нять нуж­но ту́ стро­ку, на ме­сто ко­то­рой при­хо­дит но­вый байт. По­это­му нет не­об­хо­ди­мо­сти хра­нить «воз­раст» строки́ кэ­ша.

Кро­ме то­го, нет не­об­хо­ди­мо­сти иметь устрой­ство срав­не­ния тэ­га в каж­дой стро­ке кэш-па­мя­ти. В пол­но­стью ас­со­ци­а­тив­ном кэ­ше эти устрой­ства тре­бо­ва­лись, что­бы про­из­ве­сти срав­не­ние тэ­гов од­но­вре­мен­но во всех стро­ках кэ­ша. В кэ­ше с пря­мым отоб­ра­же­ни­ем мы бу­дем ис­кать на­ши дан­ные лишь в од­ной кон­крет­ной стро­ке, но­мер ко­то­рой опре­де­ля­ет­ся ад­ре­сом бай­та. По­это­му до­ста­точ­но иметь лишь од­но устрой­ство срав­не­ния в кон­т­рол­ле­ре кэш-па­мя­ти.

В свя­зи со ска­зан­ным стро­ка кэш-па­мя­ти мо­жет быть устрое­на так, как по­ка­за­но на ри­сун­ке 3. Мы ви­дим, что кэш с пря­мым отоб­ра­же­ни­ем ад­ре­сов устро­ен го­раз­до про­ще, чем пол­но­стью ас­со­ци­а­тив­ный кэш (см. ри­су­нок 6 из пер­вой ча­сти лек­ции).

Ко­гда про­цес­сор вы­да­ёт за­прос на чте­ние бай­та опе­ра­тив­ной па­мя­ти, кэш-кон­т­рол­лер вы­пол­ня­ет сле­дую­щие дей­ствия:

• раз­би­ва­ет ад­рес тре­бу­е­мо­го бай­та на ча­сти (как по­ка­за­но на ри­сун­ке 1), опре­де­ляя тэг, но­мер строки́ кэ­ша, и сме­ще­ние в стро­ке;
• све­ря­ет тэг, за­пи­сан­ный в нуж­ной стро­ке кэ­ша, с тэ­гом, вы­де­лен­ным из ад­ре­са;
• ес­ли тэ­ги не сов­па­ли (дан­ные в кэ­ше от­сут­ству­ют), то вы­пол­ня­ют­ся сле­дую­щие дей­ствия:
  • ес­ли бит мо­дифи­ка­ции строки́ не ра­вен ну­лю, то он об­ну­ля­ет­ся, и со­дер­жи­мое строки́ за­пи­сы­ва­ет­ся в ме­сто опе­ра­тив­ной па­мя­ти, опре­де­ля­е­мое хра­ня­щим­ся в стро­ке тэ­гом и но­ме­ром этой строки́ в кэ­ше;
  • в стро­ку кэ­ша из опе­ра­тив­ной па­мя­ти за­гру­жа­ют­ся 16 байт, сре­ди ко­то­рых на­хо­дит­ся тре­буе­мый про­цес­со­ром байт па­мя­ти (ад­рес этой по­сле­до­ва­тель­но­сти байт ра­вен ад­ре­су тре­бу­е­мо­го бай­та, но с об­ну­лён­ны­ми по­след­ни­ми че­тырь­мя би­та­ми);
  • тэг строки́ за­ме­ня­ет­ся на тэг, вы­де­лен­ный из ад­ре­са тре­бу­е­мо­го бай­та;
• те­перь тре­буе­мые дан­ные точ­но при­сут­ству­ют в кэ­ше, и кон­т­рол­лер вы­да­ёт байт про­цес­со­ру из строки́ кэ­ша в со­от­вет­ствии со сме­ще­ни­ем, вы­де­лен­ным из ад­ре­са.

Ко­гда про­цес­сор вы­да­ёт за­прос на за­пись бай­та в опе­ра­тив­ную па­мять, кэш-кон­т­рол­лер вы­пол­ня­ет сле­дую­щие дей­ствия:

• раз­би­ва­ет ад­рес тре­бу­е­мо­го бай­та на ча­сти (как по­ка­за­но на ри­сун­ке 1), опре­де­ляя тэг, но­мер строки́ кэ­ша, и сме­ще­ние в стро­ке;
• све­ря­ет тэг, за­пи­сан­ный в нуж­ной стро­ке кэ­ша, с тэ­гом, вы­де­лен­ным из ад­ре­са;
• ес­ли тэ­ги не сов­па­ли (пе­ре­за­пи­сы­вае­мые дан­ные не про­кэ­ши­ро­ва­ны), то вы­пол­ня­ют­ся сле­дую­щие дей­ствия:
  • ес­ли бит мо­дифи­ка­ции строки́ не ра­вен ну­лю, то со­дер­жи­мое строки́ за­пи­сы­ва­ет­ся в ме­сто опе­ра­тив­ной па­мя­ти, опре­де­ля­е­мое хра­ня­щим­ся в стро­ке тэ­гом и но­ме­ром этой строки́ в кэ­ше;
  • в стро­ку кэ­ша из опе­ра­тив­ной па­мя­ти за­гру­жа­ют­ся 16 байт, сре­ди ко­то­рых на­хо­дит­ся пе­ре­за­пи­сы­вае­мый про­цес­со­ром байт па­мя­ти (ад­рес этой по­сле­до­ва­тель­но­сти байт ра­вен ад­ре­су тре­бу­е­мо­го бай­та, но с об­ну­лён­ны­ми по­след­ни­ми че­тырь­мя би­та­ми);
  • тэг строки́ за­ме­ня­ет­ся на тэг, вы­де­лен­ный из ад­ре­са тре­бу­е­мо­го бай­та;
• те­перь пе­ре­за­пи­сы­вае­мые дан­ные точ­но при­сут­ству­ют в кэ­ше, и кон­т­рол­лер мо­дифи­ци­ру­ет байт строки́ кэ­ша в со­от­вет­ствии со сме­ще­ни­ем, вы­де­лен­ным из ад­ре­са;
• бит мо­дифи­ка­ции строки́ уста­нав­ли­ва­ет­ся в 1.

Кэш с пря­мым отоб­ра­же­ни­ем ад­ре­сов яв­ля­ет­ся ча­ст­ным слу­ча­ем пол­но­стью ас­со­ци­а­тив­но­го кэ­ша, ес­ли стра­те­гию вы­тес­не­ния дан­ных за­ме­нить с «вы­тес­не­ния са­мой ста­рой строки́» на «вы­тес­не­ние строки́, имею­щей то же са­мое сме­ще­ние в сво­ём ме­га­бай­те дан­ных, что и тре­бу­е­мая/за­пи­сы­ва­е­мая стро­ка». Ино­гда это при­во­дит к си­ту­а­ци­ям, при ко­то­рых кэш во­об­ще не ра­бо­та­ет. На­при­мер, пред­ста­вим, что мы скла­ды­ва­ем со­от­вет­ствую­щие эле­мен­ты двух мас­си­вов A и B, и так ока­за­лось, что рас­стоя­ние меж­ду эти­ми эле­мен­та­ми крат­но раз­ме­ру кэ­ша. То­гда при по­оче­рёд­ном об­ра­ще­нии к эле­мен­там мас­си­вов A и B, они бу­дут вы­тес­нять друг дру­га из кэ­ша, так как отоб­ра­жа­ют­ся в од­но и то же ме­сто кэш-па­мя­ти.

Из-за при­ми­тив­ной «стра­те­гии за­ме­ще­ния» кэш с пря­мым отоб­ра­же­ни­ем ад­ре­сов в сред­нем про­иг­ры­ва­ет по ско­ро­сти пол­но­стью ас­со­ци­а­тив­но­му кэ­шу то­го же объ­ё­ма, вы­тес­няю­ще­му са­мую ста­рую стро­ку. Для то­го, что­бы срав­нять ско­ро­сти, объ­ём кэ­ша с пря­мым отоб­ра­же­ни­ем дол­жен быть уве­ли­чен в 4–8 раз.

Кэш с пря­мым отоб­ра­же­ни­ем ад­ре­сов, бу­дучи са­мым про­стым с точ­ки зре­ния ап­па­рат­ной реа­ли­за­ции, ис­то­ри­че­ски был пер­вым рас­про­стра­нён­ным ви­дом кэ­шей. Од­на­ко из-за сво­ей низ­кой эф­фек­тив­но­сти он был быст­ро вы­тес­нен го­раз­до бо­лее со­вер­шен­ным N-ас­со­ци­а­тив­ным кэ­шом.

N-ас­со­ци­а­тив­ный кэш

Эта ар­хи­тек­ту­ра кэш-па­мя­ти со­че­та­ет в се­бе низ­кие на­клад­ные рас­хо­ды при ап­па­рат­ной реа­ли­за­ции (по­чти как у кэ­ша с пря­мым отоб­ра­же­ни­ем ад­ре­сов) и вы­со­кое быст­ро­дей­ствие (по­чти как у пол­но­стью ас­со­ци­а­тив­но­го кэ­ша).

В N-ас­со­ци­а­тив­ном кэ­ше каж­дый байт опе­ра­тив­ной па­мя­ти мо­жет хра­нить­ся не в од­ном ме­сте кэш-па­мя­ти (как в кэ­ше с пря­мым отоб­ра­же­ни­ем ад­ре­сов), и не во всех стро­ках кэ­ша (как в пол­но­стью ас­со­ци­а­тив­ном кэ­ше), а в N раз­лич­ных стро­ках кэ­ша, где N яв­ля­ет­ся сте­пе­нью двой­ки.

Пусть, как и рань­ше, ад­рес со­сто­ит из 4-х байт, объ­ём кэ­ша ра­вен од­но­му ме­га­бай­ту, дли­на строки́ — 16 байт. Для опре­де­лён­но­сти рас­смот­рим при­мер ра­бо­ты че­ты­рёх-ас­со­ци­а­тив­но­го кэ­ша.

Ко­гда про­цес­сор про­из­во­дит об­ра­ще­ние к опе­ра­тив­ной па­мя­ти, ад­рес раз­де­ля­ет­ся на ком­по­нен­ты, как по­ка­за­но на ри­сун­ке:

От­ли­чие от кэ­ша с пря­мым отоб­ра­же­ни­ем здесь в том, что кон­т­рол­лер кэш-па­мя­ти впра­ве вы­би­рать два стар­ших би­та но­ме­ра строки́ (hint) по сво­е­му усмот­ре­нию, тем са­мым за­пи­сы­вая дан­ные из опе­ра­тив­ной па­мя­ти в од­но из че­ты­рёх воз­мож­ных для дан­но­го ад­ре­са мест кэш-па­мя­ти. В об­щем слу­чае чис­ло бит в по­ле hint рав­но .

Важ­но по­ни­мать, что сна­ча­ла ад­рес раз­би­ва­ет­ся на ком­по­нен­ты (тег, но­мер строки́, сме­ще­ние), а за­тем про­из­во­дит­ся вы­бор двух стар­ших би­тов но́мера строки́. Та­ким об­ра­зом, тег со­дер­жит не­из­ме­нён­ные стар­шие би­ты ад­ре­са, тем са­мым поз­во­ляя опре­де­лять, ка­кие же на са­мом де­ле дан­ные на­хо­дят­ся в дан­ной стро­ке. На­при­мер, в стро­ку кэш-па­мя­ти №1 (стро́ки ну­ме­ру­ют­ся с ну­ля) мо­гут по­пасть бай­ты из опе­ра­тив­ной па­мя­ти, где N — лю­бое чис­ло. При этом тэг как раз и хра­нит это N.

Но как вы­брать эти два про­из­воль­ных би­та? Са­мое луч­шее, что мож­но сде­лать — это за­ме­стить ту́ стро­ку (из че­ты­рёх воз­мож­ных), к ко­то­рой наи­бо­лее дол­го не бы­ло об­ра­ще­ний. Это опять при­во­дит нас к не­об­хо­ди­мо­сти хра­нить «воз­раст» каж­дой строки́ кэ­ша. Од­на­ко в дан­ном слу­чае воз­раст мо­жет быть реа­ли­зо­ван го­раз­до про­ще, чем в пол­но­стью ас­со­ци­а­тив­ном кэ­ше. Посмот­рим, как это мож­но сде­лать.

Мыс­лен­но разо­бьём кэш-па­мять на не­пе­ре­се­каю­щие­ся под­мно­же­ства из че­ты­рёх строк та­ким об­ра­зом, что­бы но­ме­ра строк каж­до­го под­мно­же­ства име­ли оди­на­ко­вые млад­шие би­ты, но от­ли­ча­лись дву­мя стар­ши­ми би­та­ми. На­при­мер, в пер­вое под­мно­же­ство вой­дут стро́ки но­мер 0, 16384, 32768 и 49152; во вто­рое под­мно­же­ство вой­дут стро́ки с но­ме­ра­ми 1, 16385, 32769, 49153 и так да­лее.

Ко­гда стро­ка дан­ных долж­на быть за­пи­са­на из опе­ра­тив­ной па­мя­ти в кэш, од­но­знач­но опре­де­ле­но под­мно­же­ство строк, в ко­то­рое она по­па­да­ет, а кон­крет­ный эле­мент под­мно­же­ства дол­жен быть вы­бран кон­т­рол­ле­ром. В этом слу­чае 4 строки́ под­мно­же­ства «со­рев­ну­ют­ся» друг с дру­гом за вы­тес­не­ние, при­чём стро́ки од­но­го под­мно­же­ства ни­ко­гда не мо­гут со­рев­но­вать­ся со стро­ка­ми дру­го­го под­мно­же­ства. По­это­му кон­т­рол­ле­ру нуж­но уметь опре­де­лять, ка­кая стро­ка в пре­де­лах дан­но­го под­мно­же­ства са­мая «ста­рая». Так как в каж­дом под­мно­же­стве все­го 4 эле­мен­та, до­ста­точ­но все­го двух бит для хра­не­ния воз­рас­та строки́ (ри­су­нок 5).

Кро­ме то­го, в стро­ках кэ­ша те­перь не тре­бу­ют­ся устрой­ства для од­но­вре­мен­но­го срав­не­ния тэ­гов и для од­но­вре­мен­но­го уве­ли­че­ния воз­рас­та, так как эти опе­ра­ции нуж­но де­лать не со все­ми стро­ка­ми кэш-па­мя­ти, а толь­ко с че­тырь­мя стро­ка­ми за один раз. Эти 4 строки́ мо­гут быть, на­при­мер, пр­осмот­ре­ны/об­ра­бо­та­ны кон­т­рол­ле­ром по оче­ре­ди, не силь­но сни­жая быст­ро­дей­ствие кэ­ша.

Од­на­ко, мож­но до­бить­ся од­но­вре­мен­ной об­ра­бот­ки че­ты­рёх строк кэ­ша. Для это­го раз­де­лим кэш-па­мять на 4 рав­ных ча­сти («бан­ка»), и свя­жем с каж­дым бан­ком своё устрой­ство управ­ле­ния (ри­су­нок 6). При та­ком под­хо­де каж­дое под­мно­же­ство из че­ты­рёх од­но­вре­мен­но об­ра­ба­ты­вае­мых строк ока­жет­ся рас­пре­де­лён­ным по че­ты­рём бан­кам, каж­дый из ко­то­рых мо­жет ра­бо­тать па­ра­л­лель­но с осталь­ны­ми. При за­пи­си дан­ных в кэш hint, вы­би­рае­мый кон­т­рол­ле­ром, фак­ти­че­ски бу­дет пред­став­лять со­бой но­мер бан­ка, в ко­то­рый дан­ные бу­дут за­пи­са­ны.

Ко­гда про­цес­сор вы­да­ёт за­прос на чте­ние бай­та опе­ра­тив­ной па­мя­ти, кэш-кон­т­рол­лер вы­пол­ня­ет сле­дую­щие дей­ствия:

• раз­би­ва­ет ад­рес тре­бу­е­мо­го бай­та на ча­сти (как по­ка­за­но на ри­сун­ке 4), опре­де­ляя тэг, но­мер строки́ кэ­ша, и сме­ще­ние в стро­ке;
• так как кон­т­рол­лер не зна­ет, ка­кое зна­че­ние hint (но­мер бан­ка) бы­ло вы­бра­но им для этих дан­ных, ко­гда они за­пи­сы­ва­лись в кэш в про­шлый раз (и за­пи­сы­ва­лись ли они во­об­ще), кон­т­рол­лер, зная но­мер строки́ в бан­ке, чи­та­ет стро­ки с этим но­ме­ром од­но­вре­мен­но со всех бан­ков (см. ри­су­нок 6), ли­бо, ес­ли кэш не раз­бит на бан­ки, чи­та­ет че­ты­ре строки́ по оче­ре­ди из кэш-па­мя­ти, под­став­ляя в но­мер строки́ все воз­мож­ные зна­че­ния hint (см. ри­су­нок 4);
• кон­т­рол­лер све­ря­ет тэ­ги про­чи­тан­ных из кэш-па­мя­ти строк с тэ­гом, вы­де­лен­ным из ад­ре­са;
• ес­ли тэ­ги не сов­па­ли (дан­ные в кэ­ше от­сут­ству­ют), вы­пол­ня­ют­ся сле­дую­щие дей­ствия:
  • сре­ди че­ты­рёх про­чи­тан­ных строк вы­би­ра­ет­ся для за­ме­ще­ния стро­ка с мак­си­маль­ным воз­рас­том (ес­ли кэш не раз­бит на бан­ки, а име­ет сквоз­ную ну­ме­ра­цию строк, то это дей­ствие как раз и озна­ча­ет вы­бор зна­че­ния hint кон­т­рол­ле­ром); воз­раст этой строки́ об­ну­ля­ет­ся, воз­рас­ты осталь­ных трёх строк уве­ли­чи­ва­ют­ся на еди­ни­цу;
  • ес­ли бит мо­дифи­ка­ции вы­бран­ной для за­ме­ще­ния строки́ не ра­вен ну­лю, то он об­ну­ля­ет­ся, и со­дер­жи­мое строки́ за­пи­сы­ва­ет­ся в ме­сто опе­ра­тив­ной па­мя­ти, опре­де­ля­е­мое хра­ня­щим­ся в стро­ке тэ­гом и но­ме­ром этой строки́ в бан­ке;
  • в вы­бран­ную для за­ме­ще­ния стро­ку кэ­ша из опе­ра­тив­ной па­мя­ти за­гру­жа­ют­ся 16 байт, сре­ди ко­то­рых на­хо­дит­ся тре­буе­мый про­цес­со­ром байт па­мя­ти (ад­рес этой по­сле­до­ва­тель­но­сти байт ра­вен ад­ре­су тре­бу­е­мо­го бай­та, но с об­ну­лён­ны­ми по­след­ни­ми че­тырь­мя би­та­ми);
  • тэг строки́ за­ме­ня­ет­ся на тэг, вы­де­лен­ный из ад­ре­са тре­бу­е­мо­го бай­та;
• те­перь тре­буе­мые дан­ные точ­но при­сут­ству­ют в кэ­ше (тэг од­ной из че­ты­рёх строк сов­па­да­ет с тэ­гом, вы­де­лен­ным из ад­ре­са); кон­т­рол­лер уве­ли­чи­ва­ет на еди­ни­цу воз­раст тех строк (сре­ди че­ты­рёх про­чи­тан­ных), воз­раст ко­то­рых мень­ше воз­рас­та строки́ с нуж­ны­ми дан­ны­ми, а воз­раст строки́ с нуж­ны­ми дан­ны­ми об­ну­ля­ет;
• кон­т­рол­лер вы­да­ёт байт про­цес­со­ру из строки́ кэ­ша в со­от­вет­ствии со сме­ще­ни­ем, вы­де­лен­ным из ад­ре­са

Ко­гда про­цес­сор вы­да­ёт за­прос на за­пись бай­та в опе­ра­тив­ную па­мять, кэш-кон­т­рол­лер вы­пол­ня­ет сле­дую­щие дей­ствия:

• раз­би­ва­ет ад­рес тре­бу­е­мо­го бай­та на ча­сти (как по­ка­за­но на ри­сун­ке 4), опре­де­ляя тэг, но­мер строки́ кэ­ша, и сме­ще­ние в стро­ке;
• кон­т­рол­лер, зная но­мер строки́ в бан­ке, чи­та­ет стро­ки с этим но­ме­ром од­но­вре­мен­но со всех бан­ков (см. ри­су­нок 6).
• кон­т­рол­лер све­ря­ет тэ­ги про­чи­тан­ных из кэш-па­мя­ти строк с тэ­гом, вы­де­лен­ным из ад­ре­са;
• ес­ли тэ­ги не сов­па­ли (пе­ре­за­пи­сы­вае­мые дан­ные не про­кэ­ши­ро­ва­ны), то вы­пол­ня­ют­ся сле­дую­щие дей­ствия:
  • сре­ди че­ты­рёх про­чи­тан­ных строк вы­би­ра­ет­ся для за­ме­ще­ния стро­ка с мак­си­маль­ным воз­рас­том; её воз­раст об­ну­ля­ет­ся, воз­рас­ты осталь­ных трёх строк уве­ли­чи­ва­ют­ся на еди­ни­цу;
  • ес­ли бит мо­дифи­ка­ции вы­бран­ной для за­ме­ще­ния строки́ не ра­вен ну­лю, то он об­ну­ля­ет­ся, и со­дер­жи­мое строки́ за­пи­сы­ва­ет­ся в ме­сто опе­ра­тив­ной па­мя­ти, опре­де­ля­е­мое хра­ня­щим­ся в стро­ке тэ­гом и но­ме­ром этой строки́ в бан­ке;
  • в вы­бран­ную для за­ме­ще­ния стро­ку кэ­ша из опе­ра­тив­ной па­мя­ти за­гру­жа­ют­ся 16 байт, сре­ди ко­то­рых на­хо­дит­ся пе­ре­за­пи­сы­вае­мый про­цес­со­ром байт па­мя­ти (ад­рес этой по­сле­до­ва­тель­но­сти байт ра­вен ад­ре­су тре­бу­е­мо­го бай­та, но с об­ну­лён­ны­ми по­след­ни­ми че­тырь­мя би­та­ми);
  • тэг строки́ за­ме­ня­ет­ся на тэг, вы­де­лен­ный из ад­ре­са тре­бу­е­мо­го бай­та;
• те­перь пе­ре­за­пи­сы­вае­мые дан­ные точ­но при­сут­ству­ют в кэ­ше; кон­т­рол­лер уве­ли­чи­ва­ет на еди­ни­цу воз­раст тех строк (сре­ди че­ты­рёх про­чи­тан­ных), воз­раст ко­то­рых мень­ше воз­рас­та строки́ с нуж­ны­ми дан­ны­ми, а воз­раст строки́ с нуж­ны­ми дан­ны­ми об­ну­ля­ет;
• кон­т­рол­лер мо­дифи­ци­ру­ет байт строки́ кэ­ша в со­от­вет­ствии со сме­ще­ни­ем, вы­де­лен­ным из ад­ре­са;
• бит мо­дифи­ка­ции строки́ уста­нав­ли­ва­ет­ся в 1.

Мы ви­дим, что N-ас­со­ци­а­тив­ный кэш мож­но по­ни­мать, как N кэ­шей с пря­мым отоб­ра­же­ни­ем ад­ре­сов, ко­то­рые, в свою оче­редь, яв­ля­ют­ся эле­мен­та­ми пол­но­стью ас­со­ци­а­тив­но­го кэ­ша. Кон­т­рол­лер, раз­ме­щая дан­ные в кэш-па­мя­ти, оп­ти­маль­но вы­би­ра­ет один из N эле­мен­тов пол­но­стью ас­со­ци­а­тив­но­го кэ­ша. А в вы­бран­ном кэ­ше он по­ме­ща­ет дан­ные в стро­ку, но­мер ко­то­рой жёст­ко опре­де­ля­ет­ся ад­ре­сом этих дан­ных в опе­ра­тив­ной па­мя­ти.

Кэш с пря­мым отоб­ра­же­ни­ем ад­ре­сов и пол­но­стью ас­со­ци­а­тив­ный кэш яв­ля­ют­ся ча­ст­ны­ми слу­ча­я­ми (край­но­стя­ми) N-ас­со­ци­а­тив­но­го кэ­ша. Ес­ли , мы по­лу­ча­ем кэш с пря­мым отоб­ра­же­ни­ем ад­ре­сов, ес­ли же N рав­но об­ще­му чис­лу строк кэш-па­мя­ти, то по­лу­ча­ет­ся пол­но­стью ас­со­ци­а­тив­ный кэш.

N-ас­со­ци­а­тив­ный кэш яв­ля­ет­ся са­мым рас­про­стра­нён­ным ви­дом кэ­ша в со­вре­мен­ных ком­пьютре­рах, так как он го­раз­до эф­фек­тив­нее кэ­ша с пря­мым отоб­ра­же­ни­ем. В сред­нем, эф­фек­тив­ность (от­но­ше­ние чис­ла по­па­да­ний в кэш к об­ще­му чис­лу об­ра­ще­ний к па­мя­ти) ра­бо­ты двух-ас­со­ци­а­тив­но­го кэ­ша объ­ё­мом V байт при­мер­но рав­на эф­фек­тив­но­сти ра­бо­ты кэ­ша с пря­мым отоб­ра­же­ни­ем объ­ё­мом байт. Ана­ло­гич­но, че­ты­рёх-ас­со­ци­а­тив­ный кэш в 1.5–2 ра­за эф­фек­тив­ней, чем двух-ас­со­ци­а­тив­ный. С даль­ней­шим уве­ли­че­ни­ем ас­со­ци­а­тив­но­сти уве­ли­че­ние эф­фек­тив­но­сти не так зна­чи­тель­но.