Лек­ция № 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 ра­за эф­фек­тив­ней, чем двух-ас­со­ци­а­тив­ный. С даль­ней­шим уве­ли­че­ни­ем ас­со­ци­а­тив­но­сти уве­ли­че­ние эф­фек­тив­но­сти не так зна­чи­тель­но.

109 отзывов на запись «Лек­ция № 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!
I enjoy what you guys are usually up too. Such clever work and coverage!
Keep up the wonderful works guys I’ve you guys to my blogroll.
This page certainly has all of the info I wanted about this
subject and didn’t know who to ask.
This text is priceless. Where can I find out more?
Ahaa, its fastidious conversation on the topic of this article here at this web site, I have read all that, so now me also commenting at this place.
I want to to thank you for this very good read!! I absolutely enjoyed
every little bit of it. I have got you book-marked to
look at new things you post…
Hey There. I found your blog using msn. This is a very neatly written article.
I’ll be sure to bookmark it and come back to learn more of your helpful information. Thanks for the post.
I will certainly comeback.
What’s up to every body, it’s my first visit of this website;
this blog carries remarkable and actually fine material in favor of visitors.
Definitely consider that which you stated. Your favorite justification appeared to be on the web the
easiest thing to have in mind of. I say to you, I certainly get irked while other folks think about issues that they just do not realize
about. You controlled to hit the nail upon the
highest and also outlined out the entire thing with no need side effect , people could take a signal.
Will probably be back to get more. Thanks
Informative article, totally what I needed.
Very good information. Lucky me I came across your site by
accident (stumbleupon). I’ve saved as a favorite for later!
I’m gone to convey my little brother, that he should also pay a
quick visit this blog on regular basis to take updated from most up-to-date gossip.
Wonderful beat ! I wish to apprentice even as you amend your
web site, how can i subscribe for a blog web site?
The account helped me a applicable deal. I were a little bit
acquainted of this your broadcast offered vibrant clear idea
We’re a group of volunteers and starting a new scheme in our
community. Your web site provided us with helpful info
to work on. You’ve done an impressive task and our entire group will be grateful
to you.
My partner and I stumbled over here different page and thought I may as well check things out.
I like what I see so now i am following you.
Look forward to looking into your web page for a second time.
I enjoy what you guys are usually up too. Such clever
work and coverage! Keep up the great works guys I’ve incorporated you guys
to my blogroll.
Hi there, i read your blog occasionally and
i own a similar one and i was just wondering if you get
a lot of spam feedback? If so how do you prevent it,
any plugin or anything you can advise? I get so much lately it’s
driving me crazy so any help is very much appreciated.
With havin so much content do you ever run into
any problems of plagorism or copyright violation? My blog has a lot of completely unique content I’ve either created myself or outsourced but it
appears a lot of it is popping it up all over the web without my authorization. Do you know any solutions
to help protect against content from being ripped off? I’d
certainly appreciate it.
Great blog here! Additionally your web site rather a lot
up very fast! What web host are you the use of?
Can I get your associate hyperlink in your
host? I want my site loaded up as quickly as yours lol
Thanks for the auspicious writeup. It in fact was a leisure account it.
Glance advanced to far brought agreeable from you!
However, how could we communicate?
I like the valuable information you provide in your articles.
I’ll bookmark your weblog and check again here frequently.
I’m quite certain I will learn many new stuff right here!
Good luck for the next!
In fact no matter if someone doesn’t know afterward its up to other people that they will help, so here
it takes place.
Good post. I learn something totally new
and challenging on sites I stumbleupon everyday. It will always be useful to read articles from
other authors and use something from other sites.
I every time emailed this blog post page to all my associates,
since if like to read it next my friends will too. Have a look at my website silk lash extensions wholesale (cogpartners.com)
I’m amazed, I have to admit. Rarely do I come across a blog that’s both equally educative and amusing, and let me tell you,
you’ve hit the nail on the head. The problem is something which not enough folks are speaking intelligently about.
I’m very happy I came across this in my search for something regarding this.
It’s very trouble-free to find out any matter on web as compared to books, as I found this paragraph
at this site.
Good info. Lucky me I recently found your
blog by accident (stumbleupon). I have book-marked it for later! Feel free to visit my blog silk lash extensions perth
I’m gone to convey my little brother, that he should also pay a visit this website on regular basis to
obtain updated from latest information.
I’m not sure exactly why but this weblog is loading very slow for me.
Is anyone else having this issue or is it a issue on my end?
I’ll check back later on and see if the problem still exists.
Awesome blog! Is your theme custom made or did you download it from somewhere? A theme like yours with a few simple tweeks would really make my
blog jump out. Please let me know where you got your design. Kudos Visit my web-site latest game trade (Brayden)
Hi superb website! Does running a blog such as this require a large amount of work? I have absolutely no knowledge of coding however I was hoping to start my own blog in the near future.
Anyways, should you have any suggestions or tips for new blog
owners please share. I understand this is off topic
however I just needed to ask. Thank you! Look into my homepage major water damage (Claudette)
Every weekend i used to visit this web site, as i wish
for enjoyment, as this this web site conations really pleasant funny stuff too. my page :: madden mobile coins buy reddit
What’s up everyone, it’s my first go to see at this website,
and paragraph is in fact fruitful designed for me, keep up posting such articles
or reviews. Also visit my webpage silk lash extensions perth — Denese -
Spot on with this write-up, I actually believe that this website needs a great deal more attention.
I’ll probably be back again to read more, thanks
for the advice! my site — mink strip lashes review
Howdy just wanted to give you a quick heads up. The words in your post seem to be running off the screen in Ie.
I’m not sure if this is a formatting issue or something to do with internet
browser compatibility but I thought I’d post to let you know. The style and design look great though! Hope you get the issue solved soon. Kudos Here is my homepage … cs go skins for sale ebay
Thanks very nice blog! My homepage :: madden mobile coin selling
(Kathryn)
Hi there, I would like to subscribe for this webpage to get most up-to-date updates, so where can i do it
please assist. Also visit my site: cs go knife skins for sale
I am now not positive where you are getting your info, but great topic.
I needs to spend some time learning more or understanding more. Thanks for great information I was looking for this information for
my mission. my site — cs go skins steam workshop
Hello! Quick question that’s entirely off topic. Do you know how
to make your site mobile friendly? My weblog looks
weird when viewing from my iphone4. I’m trying to find a theme or plugin that might be able to resolve this issue.
If you have any suggestions, please share. With thanks! Look into my web site; fifa coins 17 pc
Howdy! This is my first visit to your blog! We are a collection of volunteers
and starting a new project in a community in the same niche.
Your blog provided us valuable information to work on. You have
done a wonderful job!
Awesome blog! Is your theme custom made or did you download it from somewhere?
A design like yours with a few simple tweeks would really
make my blog shine. Please let me know where you got
your theme. Cheers Feel free to visit my page: silk lash extensions perth
Hi there, just became aware of your blog through Google,
and found that it’s truly informative. I am gonna watch out
for brussels. I will be grateful if you continue this in future.
Lots of people will be benefited from your writing. Cheers! Review my web-site … fifa 17 coins reddit, http://www.qpcom.net,
Hello are using WordPress for your site platform? I’m new to the blog world
but I’m trying to get started and create my own. Do you require
any html coding expertise to make your own blog? Any help would
be really appreciated! Here is my website: mink lashes cruel
Fastidious answers in return of this issue with firm arguments and explaining all concerning that. my web page — cs go awp skins for sale
Hi there, I wish for to subscribe for this blog
to get most up-to-date updates, thus where can i do it please assist. Here is my web blog fifa 17 coins free xbox 360 (http://www.trasportotorribianche.it/)
Hi there, I want to subscribe for this web site to take latest updates, therefore where can i do it please
help out. My blog post mink lash extensions wholesale
In fact when someone doesn’t know after that its up to other users that they will help,
so here it happens. my web-site :: fifacoinsbuy.com review
I really love your blog.. Pleasant colors & theme. Did you develop this site
yourself? Please reply back as I’m trying to create my very own website and want to know where you got this
from or what the theme is named. Many thanks! My blog post — mink strip lashes uk
As the admin of this site is working, no doubt very rapidly it
will be famous, due to its feature contents. Stop by my web page :: fifa coins for sale
These are in fact impressive ideas in regarding blogging. You have touched some pleasant things here. Any way keep up wrinting. Here is my web site cs go skin betting websites
Thanks for finally talking about > Лек­ция № 7:
Кэш про­цес­со­ра | Image Processing < Loved it! my web page: faux mink lashes for sale; Leah,
Greetings! Very useful advice in this particular article! It’s the little changes which will make the biggest changes.
Thanks a lot for sharing! My webpage :: cs go weapon skins for sale (mikaelsiebenrock.com)
Good article. I’m going through a few of these issues as well..
all the time i used to read smaller content which also clear their motive, and that is also happening
with this article which I am reading now.
It’s hard to find educated people about this subject, but you
sound like you know what you’re talking about! Thanks
Normally I don’t learn article on blogs, however I would like to say that this write-up very forced me to
check out and do it! Your writing taste has been surprised me.
Thank you, quite great post. my page — fifa coins zone legit
Excellent article. I absolutely appreciate this website.
Stick with it! Here is my web site fifa 17 coins ps4 review (Kelli)
Thank you, I have just been looking for information about this topic for
a long time and yours is the best I’ve discovered till now.
However, what in regards to the conclusion? Are you sure concerning the source? my website; mink lashes sephora — privatelabel.cooperfarms.com,
Hurrah, that’s what I was searching for, what a information! existing here at this web site, thanks admin of this
web site.
Your style is very unique in comparison to other people I have read stuff
from. I appreciate you for posting when you have the opportunity, Guess I will just bookmark this web site.
Howdy! This post could not be written any better! Going through this post reminds me of my previous roommate!
He always kept preaching about this. I am going to forward this
post to him. Pretty sure he’ll have a good read.
Thank you for sharing!
Pretty nice post. I just stumbled upon your blog and wanted to say
that I have really enjoyed browsing your blog posts.
In any case I will be subscribing to your rss feed and I hope you write again soon!
Greetings from Los angeles! I’m bored to tears at
work so I decided to browse your blog on my iphone during lunch break. I love the information you provide here and can’t wait to take a look
when I get home. I’m amazed at how quick your blog loaded on my phone ..
I’m not even using WIFI, just 3G .. Anyways, superb blog!
Hi everybody, here every one is sharing such experience, thus
it’s nice to read this website, and I used to pay a quick
visit this weblog all the time. Feel free to visit my web site … csgo skins price
Hello just wanted to give you a brief heads up and let you know a few of
the images aren’t loading correctly. I’m not sure why but I think its a linking issue. I’ve tried it in two different browsers and both show the same outcome. Here is my web-site; madden mobile coins cheap (qpcom.com)
hello!,I love your writing very so much! proportion we
communicate more approximately your article on AOL? I need a specialist in this house to resolve my problem.
May be that is you! Looking ahead to look you. My weblog — madden mobile coins for sale reddit
Heya i’m for the first time here. I came across this board and I to find It really helpful & it helped me out
much. I am hoping to provide one thing again and aid
others like you helped me. Here is my site: silk lash extensions london
That is really fascinating, You are a very professional blogger.
I have joined your feed and look ahead to seeking more of your great post.
Additionally, I have shared your site in my social networks my site … mink strip lashes uk
Heya i’m for the first time here. I came across this board and
I find It really useful & it helped me out
much. I hope to give something back and help others like you
helped me. Also visit my page: csgo skins free 2017,
Deloris,
I’m gone to inform my little brother, that he should also visit this website
on regular basis to obtain updated from most up-to-date news update.
What i don’t understood is in reality how you are not actually
much more smartly-liked than you might be right now.
You are very intelligent. You know therefore significantly on the subject of this matter,
produced me personally believe it from so many numerous angles.
Its like women and men don’t seem to be interested except it’s something to accomplish with Lady
gaga! Your personal stuffs excellent. Always take care of it up!
Can I just say what a relief to discover somebody who truly understands what they are talking about on the net. You definitely realize how to bring an issue to light and make it
important. More and more people really need to read this and
understand this side of your story. I was surprised that you are
not more popular because you surely have the gift. Feel free to surf to my weblog; siberian mink lashes cruelty — http://www.atek.co.kr,
I’m not that much of a online reader to be honest but your
blogs really nice, keep it up! I’ll go ahead and bookmark your site to come back in the future.
Cheers Review my page :: csgo skins betting sites
I couldn’t resist commenting. Perfectly written! my website … madden mobile coin glitch no survey no download
Howdy! I realize this is somewhat off-topic but I had to ask.
Does managing a well-established website such as
yours require a massive amount work? I am completely new to blogging
but I do write in my journal daily. I’d like to start a blog so I will be able
to share my personal experience and feelings online.
Please let me know if you have any suggestions or tips for new
aspiring blog owners. Appreciate it! my website :: buy cheap nba live coins (art.i.sanj.bhb@payapps.co.kr)

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

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

   

Можете использовать теги <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>