Кеш меморија

Од Википедија — слободната енциклопедија
Прејди на: содржини, барај

Кеш меморија (англ. Cache) е компјутерска меморија која се користи од Централната Процесирачка Единица (CPU) или од контролер на некој периферен уред (нпр. контролер на тврд диск) во компјутерот со цел да се скрати времето за пристап кон основната меморија. Kеш меморијата е многу помала од обичната компјутерска меморија но е многу побрза и затоа во неа се чуваат најчесто употребуваните компјутерски адреси или податоци од главната меморија. Кога на процесорската единица ѝ требаат податоци таа најпрво ги бара во сопствените процесорски регистри, доколку не ги пронајде ги бара во кеш меморијата и доколку и таму не ги најде ги бара во главната меморија. Што значи, кеш меморијата го скратува времето за пронаоѓање на најчесто употребуваните податоци, па според тоа ја зголемува брзината на компјутерот.

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

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

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

  • инструкциски кеш - за да ги забрза инструкциските команди
  • податочен кеш - да го забрза читањето и запишувањето на податоците
  • преведувачки бафер(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). Постојат три видови на мапирање на кеш меморијата:[1]

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

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

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

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

Правила на замена на кеш линии[уреди]

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

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

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

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

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

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


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

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

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

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

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

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

Кеш промашувања[уреди]

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

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

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

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

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

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

Адресно преведување[уреди]

Хиерархија на кеш мемориите[уреди]

Број на кеш нивоа[уреди]

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

  • Процесорот бара бараниот блок во L1.
    • Aко е таму се случува кеш погодок.
    • Ако не, се случува 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

Наводи[уреди]

  1. Fundamentals of Computer Organization and Design, Автор: Sivarama P. Dandamudi, Издавач: Springer-Verlag New York, 22 септември, 2002, Глава 17: Cache Memory стр 700-710
  2. Fundamentals of Computer Organization and Design, Автор: Sivarama P. Dandamudi, Издавач: Springer-Verlag New York, 22 септември, 2002, Глава 17: Cache Memory стр 711-713
  3. Cache Memories, Автор: A.J. Smith, ACM Computing Surveys, Vol. 14, 1982, стр. 473–530
  4. Fundamentals of Computer Organization and Design, Автор: Sivarama P. Dandamudi, Издавач: Springer-Verlag New York, 22 септември, 2002, Глава 17: Cache Memory стр 713-715
  5. Fundamentals of Computer Organization and Design, Автор: Sivarama P. Dandamudi, Издавач: Springer-Verlag New York, 22 септември, 2002, Глава 17: Cache Memory стр 718

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

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