Лек­ция № 7: Кэш про­цес­со­ра

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

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

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

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

Раз­де­ле­ние ад­ре­са на ча­сти

Ри­су­нок 1. Раз­де­ле­ние ад­ре­са на ча­сти

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

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

Ри­су­нок 2. Пря­мое отоб­ра­же­ние ад­ре­сов
(на при­ме­ре кэш-па­мя­ти объ­ё­мом 1 МБ)

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

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

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

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

Ри­су­нок 3. Стро­ка кэ­ша с пря­мым отоб­ра­же­ни­ем ад­ре­сов

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

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

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

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

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

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

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

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

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

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

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

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

раз­де­ле­ние ад­ре­са на ча­сти

Ри­су­нок 4. Раз­де­ле­ние ад­ре­са на ча­сти в че­ты­рёх-ас­со­ци­а­тив­ном кэ­ше

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

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

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

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

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

стро­ка че­ты­рёх-ас­со­ци­а­тив­ной кэш-па­мя­ти

Ри­су­нок 5. Стро­ка че­ты­рёх-ас­со­ци­а­тив­ной кэш-па­мя­ти

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

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

Пример поиск данных в четырёх-ассоциативном кэше по адресу

Ри­су­нок 6. При­мер по­ис­ка дан­ных в че­ты­рёх-ас­со­ци­а­тив­ном кэ­ше по ад­ре­су.
Мо­дифи­ка­ция воз­рас­та строки́ не по­ка­за­на.
На­жми­те на ри­су­нок, что­бы уве­ли­чить

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

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

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

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

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

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

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

35 отзывов на запись «Лек­ция № 7: Кэш про­цес­со­ра»

Спа­си­бо боль­шое за ма­те­ри­ал.
Спа­си­бо ав­то­ру, ста­тья от­лич­ная!
>Ес­ли дан­ных в кэ­ше нет, то са­мая ста­рая стро­ка вы­тес­ня­ет­ся, и на её ме­сто за­пи­сы­ва­ют­ся но­вые дан­ные, опять же по­ме­чен­ные как из­ме­нён­ные Не по­нят­но — ес­ли ли­ния счи­та­на и уже по­ме­че­на как из­ме­нён­ная — то­гда её на­до бу­дет сбро­сить в па­мять да­же ес­ли про­цес­сор в неё ни­че­го не пи­сал.
А, в смыс­ле, име­лось в ви­ду что не за­гру­же­на из па­мя­ти, а что про­цес­сор в неё за­пи­сал, спа­си­бо, те­перь по­нят­но.
Спа­си­бо за ста­тью, на­пи­са­на яс­но и до­ход­чи­во!
ка­жет­ся опе­чат­ка
в N-ас­со­ци­а­тив­ном кэ­ше под боль­шой кар­тин­кой
«ес­ли тэ­ги не сов­па­ли, …уве­ли­чить воз­рас­та…
за­тем сно­ва уве­ли­чить воз­рас­та «
до­слов­но
ес­ли тэ­ги не сов­па­ли (пе­ре­за­пи­сы­вае­мые дан­ные не про­кэ­ши­ро­ва­ны), то вы­пол­ня­ют­ся сле­дую­щие дей­ствия:
сре­ди че­ты­рёх про­чи­тан­ных строк вы­би­ра­ет­ся для за­ме­ще­ния стро­ка с мак­си­маль­ным воз­рас­том; её воз­раст об­ну­ля­ет­ся, воз­рас­ты осталь­ных трёх строк уве­ли­чи­ва­ют­ся на еди­ни­цу;
….
те­перь тре­буе­мые дан­ные точ­но при­сут­ству­ют в кэ­ше (тэг од­ной из че­ты­рёх строк сов­па­да­ет с тэ­гом, вы­де­лен­ным из ад­ре­са); кон­т­рол­лер уве­ли­чи­ва­ет на еди­ни­цу воз­раст тех строк (сре­ди че­ты­рёх про­чи­тан­ных), воз­раст ко­то­рых мень­ше воз­рас­та строки́ с нуж­ны­ми дан­ны­ми, а воз­раст строки́ с нуж­ны­ми дан­ны­ми об­ну­ля­ет; P.S. хо­ро­шая стать­ся
P.P.S. ес­ли на­ве­сти кур­сор на боль­шую кар­тин­ку, то пи­шет «При-мер по-ис-ка дан-ных…»
Спа­си­бо. Ис­пра­вил. Не ду­мал, что кто-ни­будь бу­дет так вни­ма­тель­но вчи­ты­вать­ся.
Огром­ное спа­си­бо Ав­то­ру, очень по­лез­ная ста­тья.
top cash advance in 27410 payday loans
unsecured personal loan options
Take a look at my zooppa buy cialis online without a prescription.
http://canadianrxpharmacyonline.com/ online pharmacy no prescription
http://doxycyclinebrandname.accountant/#738 doryx 200 mg is doxycycline strong malaria doxycycline doxycycline shelf life doxycycline minocycline
http://generic-name-for-keflex.accountant/#448 what is cephalexin used to treat cephalexin for humans cephalexin pregnancy
http://lisinoprilhydrochlorothiazide2016.accountant/#407 drug lisinopril lisinopril 20 mg lisinopril and potassium prinivil medication lisinopril hctz side effects
http://cephalexin-cost.accountant doxycycline calcium doryx price
Вы­воз му­со­ра в СПб http://s-musor.ru/page-165749.html Му­сор пух­то
Вы­воз ме­бе­ли из квар­ти­ры на ути­ли­за­цию http://kudamusor.ru/page-429333.html Разо­брать ста­рый дом
Де­мон­таж до­ма сто­и­мость http://nanomusor.ru/page-42532.html Стро­и­тель­ные ра­бо­ты де­мон­таж
Сто­и­мость вы­но­са стро­и­тель­но­го му­со­ра из квар­ти­ры http://nanomusor.ru/page-753414.html Сколь­ко сто­ит вы­нос му­со­ра
Вы­воз тон­ны му­со­ра http://nanomusor.ru/page-592475.html Пла­сти­ко­вые кон­тей­не­ры для му­со­ра
Вы­воз ме­бе­ли де­ше­во http://nanomusor.ru/page-853681.html Вы­воз не­га­ба­рит­но­го му­со­ра
Арен­да вы­воз му­со­ра http://mega-musor.ru/page-202109.html Арен­да пух­то 27
Сло­мать ста­рый дом и вы­вез­ти му­сор http://nanomusor.ru/page-945105.html Снос зда­ний СПб
Слом и вы­воз му­со­ра http://s-musor.ru/page-132237.html Слом до­ма и вы­воз му­со­ра це­на
Вы­воз бы­то­во­го му­со­ра це­на http://s-musor.ru/page-510341.html Вы­воз му­со­ра це­на за м3
I don’t usually comment but I gotta admit thanks for the post on this great one
Rattling great visual appeal on this web site, I’d value it 10.
I really like your blog.. very nice colors & theme. Did you create this website yourself or did you hire
someone to do it for you? Plz answer back as I’m
looking to create my own blog and would like to find out where u got this from.
appreciate it
Generally I do not learn article on blogs, but I would like to say that this write-up very compelled me to try and do it!
Your writing style has been surprised me. Thank you, quite great post.
I absolutely love your blog and find a lot of your post’s to be exactly
I’m looking for. can you offer guest writers to
write content for yourself? I wouldn’t mind publishing a post or
elaborating on most of the subjects you write concerning here.
Again, awesome website!
I’m no longer certain the place you’re getting your information,
but good topic. I needs to spend a while studying more or understanding more.
Thanks for great info I was searching for this information for my mission.
Fabulous, what a website it is! This website provides useful data to us, keep it up.
As the admin of this site is working, no doubt very
quickly it will be famous, due to its feature contents.
Do you have a spam problem on this website; I also am a
blogger, and I was wondering your situation; we have developed some nice methods and we are
looking to swap methods with other folks, please shoot me an e-mail if interested.
I enjoy reading through a post that can make people think. Also, thanks for allowing me to comment!

Оставить отзыв

Жёлтые поля обязательны к заполнению

   

Можете использовать теги <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre lang=""> <div class=""> <span class=""> <br>