Обработувачки меѓусклад

Обработувачки меѓусклад (англиски: CPU cache) — сметачко памтење која се користи од централната обработувачка единица (CPU) или од контролер на некој периферен уред (нпр. контролер на тврд диск) во сметачот со цел да се скрати времето за пристап кон основната меморија. Кеш меморијата е многу помала од обичната сметачка меморија но е многу побрза и затоа во неа се чуваат најчесто употребуваните сметачки адреси или податоци од главната меморија. Кога на обработувачкката единица ѝ требаат податоци таа најпрво ги бара во сопствените обработувачкки регистри, доколку не ги пронајде ги бара во кеш меморијата и доколку и таму не ги најде ги бара во главната меморија. Што значи, кеш меморијата го скратува времето за пронаоѓање на најчесто употребуваните податоци, па според тоа ја зголемува брзината на сметачот.

Дијаграм на кеш меморијата

На дијаграмот на сликата се прикажани главната и кеш меморијата. Главната меморија се состои од податоци кои се подредени под редоследни броеви уште и наречени адреси. На секој податок му одговара соодветна адреса. Кеш меморијата ги содржи најупотребуваните податоци како и нивните адреси во главната меморија, секако подредени под еден свој редослед кои уште и се нарекуваат кеш линии.

Повеќето модерни обработувачки единици имаат најмалку три независни кеш делови:

• инструкциски кеш - за да ги забрза инструкциските команди
• податочен кеш - да го забрза читањето и запишувањето на податоците
• преведувачки бафер(TLB - Translation Lookaside Buffer) - кој се користи да го забрза преведувањето на виртуелните во физички адреси за податочниот и инструкцискиот кеш.

Голем дел од микрообработувачите во светот немаат вградено кеш меморија поради намалувањето на трошоците и заштеда.

Историја

Приказ на местото на кеш меморијата и хиерархијата на сметачките системи

Почетокот на употребата на кеш меморијата се поврзува со измислувањето и користењето на виртуелното памтење. Поради постојаната недоволност и високата цена на мемориите, првите сметачи користеа сложена хиерархија на физичка меморија проширена и пресликана во виртуелна меморија која ја користеле програмите. Значи при виртуелната меморија најмалку употребуваните податоци се зачувуваат на некој надворешен извор на меморија, како тврд диск и сл. Во тој случај се јавила кеш меморијата како место во кое ќе се чуваат најкористените податоци и обработувачот до нив може да пристапе најбрзо од било која меморија.

Со измислувањето на првите лични сметачи стагнира развитокот на кеш меморијата бидејќи пристапувањето кон меморијата беше само малку побавно од пристапувањето кон обработувачкките регистри. Меѓутоа од почетокот на 1980-тите оваа разлика меѓу регистрите и меморијата постојано се зголемува. Ова се должи на се побрзиот развој на обработувачите во однос на меморијата. Иако е можно да се направи меморија со иста работна честота (брзина) како обработувачот сепак економски поисплатливо е да се направат една поголема но побавна меморија во комбинација со една помала но многу побрза кеш меморија. Денес имаме и пример на опслужувачи кај коишто оваа кеш меморија е многу голема со цел за побрз пристап до тие опслужувачи. Типичен пример за тоа се опслужувачите на гугл (google) кои поголемиот дел од податоците ги чуват на серверска кеш меморија.

Историја на кеш меморијата кај x86 архитектурата

Со достигнувањето на работна честота од 20 и повеќе мегахерци кај 386-ките, започнаа да се употребуваат мали кеш мемории со цел да ја забрзаат работата на системот. Ова решение почна да се применува бидејќи тогашната ДРАМ меморија има време на доцнење од 120ns. Кеш меморијата почна да се прави од побрзата но и поскапа СРАМ меморија која има доцнење од само 10 наносекунди. Тогаш чиповите со кеш мемории се наоѓаа надвор од обработувачот сместени на матичната плоча.

Големината на тогашната кеш меморија се движеше околу 16-64 килобајти.

Додека со развојот на 486-ката започнува вградување на кеш меморија во обработувачот. Оваа меморија е уште позната како Ниво 1 (Level 1 или L1) меморија за да се разликува од другата побавна кеш меморија која се вградуваше на матичната плоча и е позната како Ниво 2 (Level 2 или L2) меморија. Големината на оваа меморија се движеше околу 256 килобајти.

Денес L2 меморијата е далеку поголема и поразвиена и се вградува во самиот обработувач. А кај некои започна да се користи и Ниво 3 (Level 3 или L3) кеш меморија.

Начин на работа

Кога микрообработувачот треба да запише или да прочита некоја локација од меморијата тој прво проверува дали се наоѓа во кеш меморијата. Кеш меморијата ги запаметува локациите на податоците во главната меморија па според тоа се проверува дали ја содржи локацијата што ја бара обработувачот. Доколку обработувачот ја пронајде локацијата во кеш меморијата велиме дека имаме кеш погодок, а обратно имаме кеш промашување. Во случај на кеш погодок обработувачот чита или запишува податоци во соодветната кеш линија. Односот на кеш погодоците со промашувањата се нарекува стапка на ефикасност и е мерка за ефикасноста на кеш меморијата.

Во случај на кеш промашување се обезбедува нова кеш линија на која се копираат соодветната локација и податоците на таа локација во меморијата. Потоа обработувачот може да продолжи со работа со таа локација во кеш меморијата. Меѓутоа овие промашувања релативно го забавуваат системот бидејќи е потребно време податоците да се ископираат од главната во кеш меморијата, па дополнително да се пренесат до обработувачот.

Пресликување (Мапирање)

Мапирачката функција е функција која покажува на кој начин мемориските блокови ќе се пресликаат(мапираат) во кеш линиите (блоковите во кеш меморијата често се нарекуваат кеш линии). Оваа функција се нарекува и функција на хеширање (hashing function). Постојат три видови на мапирање на кеш меморијата:

• Директно мапирање - Секој мемориски блок си има специфицирано една кеш линија која се користи секогаш кога се става тој блок во кешот.
• Асоцијативно мапирање - Без рестрикции, дозволува било која кеш линија да биде користена за преместување на било кој мемориски блок.
• Асоцијативно мапирање по групи - Секој мемориски блок си има специфицирано една група од неколку кеш линии каде што ќе се стави тој блок, а во рамките на групата се користи асоцијативно мапирање.

Директното мапирање се постигнува со модуло функцијата. На пример, ако кешот има C линии секој мемориски блок i ќе биде директно врзан со кеш линијата c = i mod C. При директно мапирање адресата се дели на три компоненти: бајт офсет, идентификационен број за кеш линијата и кеш ознака (tag). Директното мапирање има релативно едноставна имплементација, но затоа има помала флексибилност и може да предизвика проблеми со перформансите.

Асоцијативното мапирање, уште познато како целосно асоцијативно мапирање, не налага рестрикции при поставувањето на блокови во кеш меморијата. Ова мапирање нуди најголема флексибилност. Тука адресата се дели само на два дела : бајт офсет и кеш озната (tag). Најголемиот недостаток е што блокот може да се наоѓа во било која кеш линија, па треба да се проверат сите последователно што налага хардверска имплементација на онолку сопредби колку што има кеш линии. Ова мапирање скоро и да не се користи во практика.

Асоцијативното мапирање по групи е на некој начин хибрид или компромис од претходните две мапирања. Секој мемориски блок директно се мапира на одредена група на кеш линии. Типично овие групи имаат мал број на линии - 2,4 или 8 - се користат. Повторно адресите се делат на три дела но овој пат на: бајт офсет, идентификационен број за групата и кеш ознака.

Правила на замена на кеш линии

Кога нема да има слободна кеш линија, меморијата мора да избрише односно жртвува некоја полна кеш линија. Кај директното мапирање веднаш се знае која линија ќе биде „жртвената“ бидејќи секој мемориски блок е поврзан со точно определена линија. Но за асоцијативното определување мора да се одбере некоја непозната линија. Правилото по кое се одредува која линија ќе се избрише се нарекува правило на замена. Основниот проблем кај ова правило е да се процени која линија има најмала веројатност да се употреби во иднина. Ова е многу тешко за предвидување и затоа има повеќе такви правила и нивната прецизност им варира.

Можеби најпознато е правилото да се избрише најмалку употребуваната кеш линија(least recently used - LRU). Во практиката, имплементацијата на LRU е скапа за мемории со поевеќе од 4 групи. Поради тоа се користи парцијална имплементација, што е апроксимација на вистинското LRU. Ова „псевдо LRU“ правило се состои од поделба на групата на две подгрупи и работење со подгрупата која најмалку се употребувала.

Алтернатива на ова правило е правилото на случајна замена (random replacement). Ова правило, како што кажува и името се темели на заменување на случаен блок од меморијата со новиот. Додека за мали кеш мемории LRU има предност во однос на перформансите, за големи мемории тоа не е секогаш точно. Некогаш се случува и случајното заменување да има подобри перформанси од LRU. Други правила од теоретски интерес се најретко употребуваната кеш линија (least frequently used - LFU) и прво-внатре-прво-надвор (FIFO, First In - First Out) шравилата. FIFO го заменува блокот кој бил најдолго време во групата, а LFU го заменува блокот кој бил референциран најмалку пати. Овие методи се посоодветни за управување со виртуелната меморија.

Правила на запишување

Кога податоците се запишуват во кеш меморијата порано или подоцна тие треба да бидат запишани и во меморијата. Одредувањето кога се запишуваат се врши по правилото за запишување. Запишувањето може да се врши на два начини. Првиот начин е со секое запишување на кеш меморијата, да се запишува и во меморијата (write-through). Со овој метод и кеш и мемориската копија ќе бидат доследни.

Вториот и побрз начин е при запишувањето во кеш меморијата локациите на кои се запишува се означуваат како „нечисти“ и да не се пристапува до меморијата, па откако обработувачот ќе заврши со работата се запишуваат нечистите локации на соодветната адреса во меморијата(write-back). Недостатокот на овој начин е што треба подолго време да се смести нова кеш линија која треба да дојде на местото на веќе постоечка и променета (нечиста) линија, како и потребата од екстра „нечист“ бит.

Во поново време со користењето на повеќе кеш мемории, се случува податоците од истата локација во главната меморија да ги обработуваат две или повеќе кеш мемории при што за да не доаѓа до мешање и несовпаѓање на податоци се користат протокол за комуникација на кеш мемориите.

Во случаи кога обработувачот ќе ја заврши својата работа и чека одредени податоци да бидат отчитани од меморијата, бидејќи за тоа треба одредено време, тој покрај извршувањето на други паралелни инструкции, ја средува и сопствената кеш меморија.

Соработливост на кеш меморијата

Според правилото на замена се одредува на која локација во кешот ќе се копираат податоците. Доколку на правилото на замена му е дозволено да одбира на која локација ќе ги копира новите податоци кешот се нарекува целосно соработлив. Во спротивност доколку му се одредува само едно место каде ќе копира се нарекува директно пресликан (мапиран). Повеќето кешови користат комбинација од двата начини, односно се делумно соработливи од N-то ниво. Тоа значи доколку се соработливи од 2-ро ниво значи можат да запишуваат само на две локации, ако се од 4-то можат да запишуваат само на 4 локации итн.

Со зголемувањето на соработливоста на кеш меморијата се зголемува можноста за кеш погодок, но се зголемува и времето за пребарување на локациите. Во практика најмногу се користи правилото на дуплирање на соработливоста од директно пресликана во делумно соработлива од 2-ро ниво, или од делумно соработлива од 2-ро ниво до делумно соработлива од 4-то ниво, што има ефект врз стапката на ефикасност како дуплирање на големината на кеш меморијата. Зголемувањето на соработливоста над 4 ниво има многу помала стапка на ефикасност и се користи за други намени.

Доколку една локација од главната може да биде копирана на две локации во кеш меморијата, се поставува прашањето: како се одредуваат тие локации? Едно од најупотребуваните и најпросто шеми на одредување е на првата локација на меморијата му се доделуваат првите 2 од кешот, на втората вторите две и така кога сите локации ќе се исполнат, на наредната локација од меморијата повторно му се даваат првите две од кешот и така натаму.

Кеш промашувања

Под кеш промашување се подразбира пропаднат обид за читање или запишување од кеш меморијата, што резултира со читање или запишување на податоците од главната меморија при што се губи повеќе време. Постојат 3 вида на кеш промашувања и тоа: при читање на инструкциите, при читање на податоците и при запишување на податоците.

Најмногу време се губи при промашувањето при читање на инструкции, бидејќи обработувачот (или барем процесот) треба да чека дадената инструкција да биде проследена од главната меморија.

Помалку време пак се губи при промашувањето при читање на податоци бидејќи во меѓувреме можат да се извршат инструкциите кои не зависат од тие податоци, па кога податоците ќе бидат проследени од главната меморија да бидат обработени.

А најмалото губење на време е при промашувањето при запишување на податоците бидејќи постои список на запишување каде се чуваат податоците сè додека не се обезбедат услови за нивно запишување. Ова запишување може да почека сè додека не се исполни листата.

Во анализата на кеш промашувањата, генерално се користат три поделби:

• Задолжителни промашувања: Промашувања кои се појавуваат поради пристапување до некој блок за првпат. Бидејќи овие блокови пред тоа не ни биле ставени во кешот, сите дизајни на кеш меморија ќе искусат вакви промашувања. Оттаму и името задолжителни (Compulsory Misses, се користат и имињата Cold-Start Misses и Compulsory Line Fills)
• Капацитивни промашувања(Capacity Misses): Промашувања кои се појавуваат поради достигнување на границата на капацитетот на кеш меморијата. Бидејќи кешот нема можност да ги чува сите блокови после одредено време ќе се наполни и ќе мора да се употребува некое правило на замена на кеш линија. Кога би имало доволно место, вакви промашувања не би се случувале.
• Конфликтни промашувања(Conflict Misses, уште и Collision Misses): Промашувња кои се случуваат поради некој конфликт причинет од мапирачката функција. Овие промашувања се случуваат при директнно или асоцијативно мапирање по групи, поради фактот што повеќе блокови се директно поврзани со една кеш линија. Целосно асоцијативното мапирање ги елиминира овие промашувања.

Хиерархија на кеш мемориите

Број на кеш нивоа

Повеќето тековни обработувачи користат кеш со две нивоа. Овие системи имаат примарен кеш (ниво 1, Level 1 - L1) и секундарен кеш (L2). Примарниот кеш најчесто е на самиот чип а секундарниот надвор од обработувачккиот чип. Во ваков систем типично:

• Обработувачот бара бараниот блок во L1.
  • Ако е таму се случува кеш погодок.
  • Ако не, се случува L1 кеш промашување и блокот се наоѓа во L2 или во главната меморија.
• При L1 промашување, се пребарува L2 кешот.
  • Ако се пронајде блокот, се случува L2 кеш погодок и блокот му се овозможува на обработувачот при што попат тој се запишува во L1.
  • Ако не се најде, се случува L2 кеш промашување и блокот мора да се земе од главната меморија. При тоа тој се запишува во двете кеш нивоа.

Иако повеќето обработувачи користат ваква хиереархиска поставеност (како Pentium, PowerPC итн) постојат и кеш со три нивоа. Конкретен пример е Compaq Alpha (порано DEC Alpha) кој користи три нивоа. Првите две се вградени во чипот, а третото, L3 е вон чипот. Начинот на функционирање е сличен.

Користена литература

• Fundamentals of Computer Organization and Design, Sivarama P. Dandamudi - School of Computer Science, Carleton University 22 септември, 2002

Надворешни врски

• Memory part 2: CPU caches - Добра статија во која детално е обработена кеш меморијата
• Evaluating Associativity in CPU Caches - Го разгледува вградувањето на кеш меморијата, потребата од кеш меморија како и проблемите кои се јавуваат.
• Cache Performance for SPEC CPU2000 Benchmarks - Детално се обработени симулациони резултати на поединечните кеш мемории од повеќе производители
• Memory Hierarchy in Cache-Based Systems Архивирано на 15 септември 2009 г. - ја разгледува и објасунва хиерархијата во кеш мемориите
• A Cache Primer Архивирано на 25 јули 2008 г. - Детално ја објаснува кеш меморијата вклучувајќи и цртежи и споредби