Image Processing

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

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

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

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

Обыч­но кэш про­зра­чен для при­клад­ных про­грамм. Это озна­ча­ет, что про­грам­мы ра­бо­та­ют с па­мя­тью, не за­бо­тясь о су­ще­ство­ва­нии кэ­ша: кэш «пе­ре­хва­ты­ват» за­про­сы к опе­ра­тив­ной па­мя­ти, предо­став­ляя про­грам­ме тре­буе­мые дан­ные. Од­на­ко, со­вре­мен­ные си­сте­мы поз­во­ля­ют при­ло­же­нию «под­ска­зать» кэ­шу пра­виль­ное по­ве­де­ние. Это мо­жет быть сде­ла­но, на­при­мер, при по­мо­щи ко­манд пред­ва­ри­тель­ной за­груз­ки дан­ных в кэш и за­пи­си дан­ных в па­мять, ми­нуя кэш. Бы­ва­ют так­же вы­чис­ли­тель­ные си­сте­мы, в ко­то­рых кэш пол­но­стью управ­ля­ет­ся про­грам­мой: про­грам­ма мо­жет не­за­ви­си­мо ра­бо­тать с кэш-па­мя­тью и опе­ра­тив­ной па­мя­тью, и са­ма ре­ша­ет, ка­кие имен­но дан­ные хра­нить в кэ­ше.

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

Эф­фек­тив­но­стью кэ­ша на­зы­ва­ет­ся от­но­ше­ние чис­ла по­па­да­ний кэ­ша к об­ще­му ко­ли­че­ству об­ра­ще­ний про­цес­со­ра. Эф­фек­тив­ность, та­ким об­ра­зом, — это чис­ло от 0 до 1. Ну­ле­вая эф­фек­тив­ность озна­ча­ет, что кэш ни­сколь­ко не уско­рил ра­бо­ту си­сте­мы; эф­фек­тив­ность, рав­ная еди­ни­це, озна­ча­ет, что уско­ре­ние мак­си­маль­но, и вре­мя об­ра­ще­ния к па­мя­ти опре­де­ля­ет­ся ско­ро­стью ра­бо­ты кэ­ша, а не ско­ро­стью ра­бо­ты опе­ра­тив­ной па­мя­ти. Эф­фек­тив­ность кэ­ша за­ви­сит от сле­дую­щих фак­то­ров:

• Объ­ём кэ­ша. Чем боль­ше объ­ём кэ­ша, тем бо́льшую часть тре­буе­мых про­грам­ме дан­ных он мо­жет в се­бе со­дер­жать, тем ре­же бу­дут про­ис­хо­дить об­ра­ще­ния к опе­ра­тив­ной па­мя­ти, и тем вы­ше бу­дет об­щее быст­ро­дей­ствие си­сте­мы.
• Ал­го­ритм функ­цио­ни­ро­ва­ния кэ­ша. К со­жа­ле­нию, за­ча­стую объ­ё­ма кэш-па­мя­ти не­до­ста­точ­но для то­го, что­бы вме­стить все не­об­хо­ди­мые для вы­чис­ле­ний дан­ные. В этом слу­чае кэш-кон­т­рол­лер дол­жен «ре­шить», ка­кие имен­но дан­ные сле­ду­ет дер­жать в кэ­ше. По­это­му кро­ме объ­ё­ма кэ­ша важ­ным яв­ля­ет­ся ал­го­ритм его функ­цио­ни­ро­ва­ния: кэш, осна­щён­ный хо­ро­шим ал­го­рит­мом, бу­дет го­раз­до эф­фек­тив­нее ис­поль­зо­вать свой объ­ём, хра­ня мень­ше не­нуж­ных дан­ных.
• Вы­пол­ня­е­мая про­цес­со­ром про­грам­ма. Кэш ока­зы­ва­ет­ся эф­фек­тив­ным по­то­му, что боль­шин­ство ком­пью­тер­ных про­грамм об­ра­ща­ют­ся к па­мя­ти не слу­чай­ным об­ра­зом, а за­ко­но­мер­но. Чем луч­ше кэш-кон­т­рол­лер мо­жет «пред­ска­зать» об­ра­ще­ния при­ло­же­ния к па­мя­ти, тем вы­ше эф­фек­тив­ность.

За­ко­но­мер­ность об­ра­ще­ний про­грам­мы к опе­ра­тив­ной па­мя­ти обыч­но вы­ра­жа­ет­ся в том, что об­ра­ще­ния к па­мя­ти об­ла­да­ют временно́й и про­стран­ствен­ной ло­каль­но­стью:

• Временна́я ло­каль­ность: ес­ли про­изо­шло об­ра­ще­ние к ячей­ке опе­ра­тив­ной па­мя­ти, то с боль­шой ве­ро­ят­но­стью эта ячей­ка па­мя­ти вско­ре по­на­до­бит­ся сно­ва.
• Про­стран­ствен­ная ло­каль­ность: ес­ли про­изо­шло об­ра­ще­ние к ячей­ке опе­ра­тив­ной па­мя­ти, то с боль­шой ве­ро­ят­но­стью бу­дет про­из­ве­де­но об­ра­ще­ние к со­сед­ним ячей­кам па­мя­ти.

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

Пол­но­стью ас­со­ци­а­тив­ный кэш

Пусть ад­рес бай­та опе­ра­тив­ной па­мя­ти со­сто­ит из 32-х бит (4-х байт). Со­ста­вим кэш из строк: пусть каж­дая стро­ка со­дер­жит (хра­нит) ад­рес и байт, ко­то­рый со­от­вет­ству­ет это­му ад­ре­су в опе­ра­тив­ной па­мя­ти. Хра­ни­мый ад­рес при­ня­то на­зы­вать те­гом (tag), что­бы не пу­тать его с ад­ре­сом (но­ме­ром) строки́ кэ­ша.

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

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

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

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

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

Пусть про­изо­шло по­па­да­ние в кэш, и со­от­вет­ствую­щая стро­ка име­ла воз­раст N. При­сво­им ей воз­раст 0, а воз­рас­ты всех осталь­ных строк, ко­то­рые бы­ли мень­ше N, уве­ли­чим на еди­ни­цу. Не­труд­но ви­деть, что по­сле та­кой опе­ра­ции все эле­мен­ты кэ­ша вновь име­ют пра­виль­ный воз­раст, со­от­вет­ствую­щий по­ряд­ку их ис­поль­зо­ва­ния. Что­бы уско­рить эту про­це­ду­ру, нуж­но снаб­дить все стро́ки кэ­ша устрой­ства­ми, од­но­вре­мен­но до­бав­ляю­щи­ми еди­ни­цу к воз­рас­ту сво­их строк. В слу­чае про­ма­ха кэ­ша из не­го вы­бра­сы­ва­ет­ся эле­мент с мак­си­маль­ным (65535) воз­рас­том, все воз­рас­ты уве­ли­чи­ва­ют­ся на еди­ни­цу, а но­вый эле­мент по­лу­ча­ет воз­раст 0.

Те­перь рас­смот­рим про­цесс за­пи­си. Пусть про­цес­сор хо­чет за­пи­сать дан­ные в па­мять. Ско­рее все­го, эти дан­ные вско­ре по­на­до­бят­ся вновь, по­это­му они долж­ны быть за­пи­са­ны в кэш. Но нуж­но ли пи­сать их при этом ещё и в опе­ра­тив­ную па­мять? Ес­ли дан­ные в опе­ра­тив­ную па­мять за­пи­сы­ва­ют­ся од­но­вре­мен­но с за­пи­сью в кэш, то он на­зы­ва­ет­ся кэ­шом со сквоз­ной за­пи­сью.

Од­на­ко, ес­ли за­пись в каж­дую стро­ку кэ­ша про­ис­хо­дит в сред­нем бо­лее од­но­го ра­за до сме­ны этой строки́, то вы­год­на дру­гая стра­те­гия. Очень ча­стый сце­на­рий ра­бо­ты с кон­крет­ным эле­мен­том па­мя­ти — «за­пись, чте­ние, за­пись, чте­ние, ...». Здра­вый смысл под­ска­зы­ва­ет, что за­пись в опе­ра­тив­ную па­мять нуж­но про­из­ве­сти лишь в са­мом кон­це по­доб­ной це­поч­ки. А ко­гда у це­поч­ки опе­ра­ций со стро­кой кэ­ша на­сту­па­ет ко­нец? То­гда, ко­гда эта стро­ка вы­бра­сы­ва­ет­ся из кэ­ша.

Та­ким об­ра­зом, ко­гда стро­ка вы­бра­сы­ва­ет­ся из кэ­ша, она долж­на быть за­пи­са­на в опе­ра­тив­ную па­мять. Но что, ес­ли она не бы­ла из­ме­не­на? То­гда её не нуж­но за­пи­сы­вать. Для то­го, что­бы от­сле­жи­вать из­ме­не­ния строк кэ­ша, снаб­дим каж­дую стро­ку до­пол­ни­тель­ным би­том (ри­су­нок 5), ко­то­рый бу­дет уста­нав­ли­вать­ся в еди­ни­цу при мо­дифи­ка­ции дан­ных в стро­ке. То­гда при вы­тес­не­нии строки́ нуж­но бу­дет про­ве­рить этот бит, и, ес­ли он ра­вен еди­ни­це, про­из­ве­сти за­пись в опе­ра­тив­ную па­мять.

Итак, про­цес­сор за­пи­сы­ва­ет дан­ные в па­мять. Ес­ли эти дан­ные есть в кэ­ше, то они пе­ре­за­пи­сы­ва­ют­ся и по­ме­ча­ют­ся, как из­ме­нён­ные. Ес­ли дан­ных в кэ­ше нет, то са­мая ста­рая стро­ка вы­тес­ня­ет­ся, и на её ме­сто за­пи­сы­ва­ют­ся но­вые дан­ные, опять же по­ме­чен­ные как из­ме­нён­ные. Не­до­ста­ток та­ко­го под­хо­да в том, что при про­ма­хе кэ­ша те­перь ча­сто бу­дут про­ис­хо­дить две опе­ра­ции: за­пись дан­ных ста­рой строки́ из кэ­ша в опе­ра­тив­ную па­мять, и за­груз­ка тре­буе­мых дан­ных из па­мя­ти в кэш. По­это­му ино­гда де­ла­ют так, что кэш в сво­бод­ное вре­мя сам пе­ре­пи­сы­ва­ет мо­дифи­ци­ро­ван­ные дан­ные в опе­ра­тив­ную па­мять, об­ну­ляя со­от­вет­ствую­щие би­ты мо­дифи­ка­ции.

Нам оста­лось ре­шить две про­бле­мы:

1. Наш кэш хо­ро­шо справ­ля­ет­ся с временно́й ло­каль­но­стью об­ра­ще­ния к дан­ным, но он со­вер­шен­но не адап­ти­ро­ван к про­стран­ствен­ной ло­каль­но­сти. Как быть, ес­ли про­цес­сор об­ра­ща­ет­ся к од­но­му бай­ту опе­ра­тив­ной па­мя­ти, за­тем к со­сед­не­му, и так да­лее?
2. Раз­ра­бо­тан­ный кэш бу­дет иметь очень вы­со­кие на­клад­ные рас­хо­ды при ап­па­рат­ной реа­ли­за­ции. Дей­стви­тель­но, каж­дая стро­ка кэ­ша, по­ми­мо един­ствен­но­го бай­та дан­ных, со­дер­жит: че­ты­ре бай­та ад­ре­са, устрой­ство срав­не­ния ад­ре­сов, два бай­та для хра­не­ния воз­рас­та строки́, устрой­ство для на­ра­щи­ва­ния воз­рас­та, и бит, обо­зна­чаю­щий мо­дифи­ка­цию строки́.

Для ре­ше­ния этих про­блем бу­дем хра­нить в каж­дой стро­ке кэ­ша не один байт дан­ных, а не­сколь­ко байт, иду­щих под­ряд в опе­ра­тив­ной па­мя­ти. Те­гом строки́ бу­дем счи­тать ад­рес пер­во­го со­дер­жа­ще­го­ся в ней бай­та. Рас­смот­рим при­мер, ко­гда в стро­ке кэ­ша хра­нят­ся 16 байт. Для то­го, что­бы дан­ные в стро­ках не мог­ли «пе­ре­кры­вать­ся» (пе­ре­кры­тие дан­ных зна­чи­тель­но услож­нит ло­ги­ку ра­бо­ты), по­тре­бу­ем, что­бы те­ги всех строк бы­ли крат­ны 16. То­гда 4 по­след­них би­та те­га бу­дут рав­ны ну­лю, и их не нуж­но хра­нить. Мы ви­дим, что от­но­ше­ние «по­лез­но­го» объ­ё­ма кэ­ша к об­ще­му зна­чи­тель­но улуч­ши­лось (ри­су­нок 6).

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

При по­ис­ке дан­ных в та­ком кэ­ше по ад­ре­су сле­ду­ет взять стар­шие 28 бит ад­ре­са, и по­дать их на срав­не­ние в стро́ки кэ­ша. Ес­ли стро­ка най­де­на, то нуж­но взять из строки́ байт, опре­де­ляе­мый млад­ши­ми че­тырь­мя би­та­ми ад­ре­са. Ес­ли стро­ка не най­де­на, то тре­бу­ет­ся об­ра­ще­ние к опе­ра­тив­ной па­мя­ти.

Те­перь, ес­ли про­цес­сор бу­дет за­пра­ши­вать бай­ты из па­мя­ти под­ряд, то лишь каж­дое 16-е об­ра­ще­ние к па­мя­ти бу­дет при­во­дить к про­ма­ху кэ­ша. Ко­неч­но, есть и не­до­ста­ток: со­сед­ние 15 байт бу­дут за­гру­жать­ся (и за­ни­мать часть кэш-па­мя­ти) да­же то­гда, ко­гда они про­цес­со­ру не по­на­до­бят­ся. Мож­но услож­нить ал­го­ритм, что­бы чте­ние или за­пись дан­ных под­ряд во­об­ще не при­во­ди­ло к про­ма­хам кэ­ша: для это­го нуж­но за­гру­жать в кэш сле­дую­щие 16 байт, ес­ли про­изо­шло об­ра­ще­ние к по­след­не­му бай­ту строки́.