Кешпамет

Кешпамет или скрита основна памет^[1](от английски: cache memory, от френското cacher – „скривам“, общо с английското cash – „пари в брой“), често наричана за по-кратко само кеш, е спомагателна компютърна памет за ускоряване обмена на данни между различните нива в йерархията на паметта. Ускоряването се постига чрез поддържане на копия от избрани части от данните върху носител с бързо действие, близко до това на горното ниво на паметта. Степента на ускорение зависи от вида на обменяните данни, от алгоритъма за избор на данни за копиране и от съвместимостта помежду им.

За да са по-ефективни в употребата на данни, кешовете са сравнително малки. Въпреки това, кеш паметта се е доказала в много области на компютърните изчисления, защото моделите за достъп в компютърните приложения проявяват „locality of reference“. Освен това моделите за достъп проявяват „temporal locality“, ако се извикат данни, които са били използвани неотдавна, докато „special locality“ се отнася за заявки за физически съхранявани данни в близост до вече извикани данни.

Кеш паметта бива различни видове в зависимост от положението си в йерархията:

процесорен кеш – ускорява обмена на данни между регистрите на централния процесор и оперативната памет
- кеш от 1-во ниво – работи с тактовата честота на процесора, в процесорите с харвардска архитектура има отделни кешпамети за команди и за данни, разположен е в една и съща интегрална схема (ИС) с процесора;
- кеш от 2-ро ниво – работи на честота, по-ниска от честотата на процесора, най-често в съотношение 1:2 или 1:3, може да бъде в ИС на процесора или като външни модули;
- кеш от 3-то ниво – допълнително ниво, когато е необходим по-голям обем на кешпамет или за съвместна работа на няколко процесора в симетрична многопроцесорна обработка;
- кеш от 4-то ниво – второ допълнително ниво за симетрична обработка, когато кешът от 3-то ниво на отделните процесори не позволява симетрична обработка или има ограничения за броя процесори в нея;
кеш на диска, често наричан дисков кеш – буферна памет в твърдите дискове, която освобождава централния процесор от нуждата да чака записа върху или прочитането на данни от диска;
кеш на контролера – памет в дисковия контролер (най-често в контролери за RAID-масиви), която допълнително буферира обмена при входно-изходна операция към няколко диска;
дисков буфер, също наричан дисков кеш – междинна памет при запис на данни върху магнитна лента.

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

Кеш паметта представлява хардуерно изпълнен блок от памет за временно съхранение на данни с вероятност да бъдат ползвани отново. Централните процесори и твърдите дискове често ползват кеша, както и уеб браузърите и уеб сървърите.

Кеша се състои от общ запас от вписвания/постъпвания. Всяко постъпване идва с присъединени данни, които са копие на данни в някое допълнително хранилище. Всяко постъпване има и маркировка, което уточнява идентичността на данните в допълнителното хранилище, в което се съдържа копието на постъпването.

Когато кеш клиентът (микропроцесор, уеб браузър или операционна система) трябва да осъществи достъп до данните, които се предполага, че съществуват в допълнителното хранилище, първо проверява кеша. Ако там може да бъде открито постъпване със същата маркировка на търсените данни, се използва то. Тази ситуация се нарича „cache hit“. Така например, един уеб браузър може да провери локалния си кеш за копие на съдържанието на уебстраница с определен URL. В този пример, маркировката е URL-ът, а данните са съдържанието на уеб страницата. Процентът на достъпите от „cache hit“ се нарича „хит съотношение“ на кеша.

Алтернативната ситуация, когато след проверка в кеша не са намерени нужните данни със съответната маркировка, се нарича „cache miss“. Некешираните данни, взети от допълнителното хранилище след „cache miss“, се копират в кеша, готови за по-нататъшен достъп.

По време на „cache miss“, процесорът обикновено премахва някое друго постъпване за да създаде място за не кешираните данни.

Една популярна политика на замяна е „най-малко ползвана напоследък“; тя замества най-малко ползването напоследък постъпление (виж cache algorithm). По-ефикасните кешове изчисляват честота на ползване с размера на съхраняваното съдържание, както и времевите интервали и скоростта на изпълнение за кеша и допълнителното хранилище. Това работи добре за по-големи обеми от данни, по-дълги времеви интервали и бавни скорости на изпълнение.

Политики на записване

Когато системата записва данни в кеша, в определен момент трябва да запише данните и в резервното хранилище (backing store). Точният момент на записване се контролира от така наречената „политика на записване“.

Има два основни подхода за записване:

Директен запис (write-through): записът се извършва едновременно в кеша и резервното хранилище (backing store).
Забавено вписване (write-back) (или write behind): Първоначално записа се извършва само в кеша. Записът в резервното хранилище се отлага, докато кеш блоковете с данните бъдат променени или заменени с ново съдържание.

Забавеното вписване (write-back) е по-сложено за имплементация, тъй като трябва да следи кои връзки са били презаписани и да ги маркира като „мръсни“ за по-късни записи в резервното хранилище. Данните в тези връзки се записват обратно в резервното хранилище само когато са премахнати от кеша – ефект, познат още като „мързелив запис“. Поради тази причина, „read miss“ в кеша (което изисква блокът да бъде заменен от друг) често ще изисква два пъти достъп до паметта: веднъж да запише замените данни от кеша обратно в хранилището, и още веднъж, да получи отново нужните данни.

Други политики също могат да задействат забавеното вписване. Клиентът може да направи много промени на данните в кеша и след това изрично да уведоми кеша да запише обратно данните.

Има два подхода за справяне със ситуации на „write-misses“:

Разпределено записване (write allocate) (също известно като fetch on write): данните на „missed-write“ връзките се зареждат в кеша, последван от „write-hit“ операция. При този подход, „write misses“ са сходни с „read misses“.
Не разпределено записване(no-write allocate) (също известно като write-no-allocate или write around): данните в „missed-write“ връзките не се зареждат в кеша, ами се записват директно в допълнителното хранилище. При този подход само пътищата са кеширани. Както „write-through“ така и забавено вписване може да използват тези „write-miss“ подходи, но обикновено те са свързани по следния начин:

Забавеното вписване използва разпределено записване (write allocate), с надеждата за последващи записвания (или дори четения) към същите връзки, които са вече кеширани.

Директен запис (write-trough): използва неразпределено записване (no-write allocate). Тук последващите записи нямат предимство, защото те тепърва трябва да бъдат записани директно в резервното хранилище. Обекти, различни от тези, които кешът може да замени в резервното хранилище, като в този случай копието в кеша може да е излязло от употреба или остаряло. Също така, когато клиентът актуализира данните в кеша, копията им в други кешове ще остареят.

Приложения

Кеш на процесора

Основна статия: Процесорен кеш

Процесорният кеш е памет, по-малка или близка до паметта на процесора, която може да работи по-бързо от значително по-голямата основна памет. От 1980 г. насам повечето процесори използват един или повече кешове, а модерните вградени десктоп и сървърни микропроцесори, могат да имат до 6 различни кеша, като всеки един има специална функция. Примери за кеш със специална функция са D-cache и I-cache.

Кеш на графичния процесор

По-ранните графични процесори не са притежавали хардуерно-управляеми кешове, но с навлизането на графичните процесори в масовите модели компютри, все по-големи размери кеш са били представяни и интегрирани.^[2] Например процесорите от GT-200 архитектурата (GT200), не включваха кеш от 2-ро ниво, докато графичния процесор Fermi притежава 768 KB последно ниво кеш, Kepler има 1536 KB последно ниво кеш и Maxwell^[2] има 2048 KB кеш.

Буфер за преобразуване

Основна статия: Буфер за преобразуване

Единицата за управление на паметта (MMU), която извлича въведените данни от таблица в страница, има специализиран кеш, който се използва за записване на резултатите от транслация между виртуалния и физическия адреси. Този кеш се нарича буфер за преобразуване (TLB).^[3]

Кеш на диск

Основна статия: Кеш на страница

Докато кешът на процесорите се управлява изцяло хардуерно, някои видове кеш се управляват и от софтуер. Кеша на страницата в основната памет е пример за кеш на диск, който се управлява от операционната система kernel.

Въпреки че буфера на диска, който е интегриран в хард диска, понякога е подвеждащо представен като кеш на диск, неговите главни функции са последователно записване и предварително прочитане. Повторни кеш попадения са сравнително редки, поради малкия размер на буфера, в сравнение с капацитета на драйва. Въпреки това, по-високия клас дискови контролери доста често притежават свои собствени кешове на блоковете данни на хард диска (data blocks).

Последно един бърз локален хард диск може също да кешира информация, съдържаща се на по-бавни устройства за съхранение на памет, като дустанционни сървъри (web cache) или локални касети и други оптични устройства. Също така бързите флаш-базирани, статични дискови устройства (SSD) могат да бъдат използват за кешове на по-бавните хард дискове (HDD), като могат да бъдат и комбинирани да работят заедно като хибридни хард дискове или статични-хибридни дискове (SSHDs).

Уеб кеш

Основна статия: Уеб кеш

Уеб браузърите и прокси сървърите използват уеб кеша, за да съхраняват предишни отговори от сървъра като уеб страници и снимки. Уеб кешът намалява количеството информация, което трябва да бъде разпространено в мрежата, защото информацията, която преди се е съхранявала в кеша, доста често може да се преизползва. Това намалява честотната лента и критериите за изпълнение на уеб сървъра и спомага подобряването на използваемостта за потребителите.^[4]

Уеб браузърите използват вградени кешове, но някои интернет доставчици или организации използват кеширащ прокси сървър, който представлява уеб кеш, който е споделен между всички потребители в дадената мрежа.

Друга форма на кеширането е P2P кеширането, където файловете, използвани от Р2Р (peer-to-peer) приложенията, са съхранени в ISP кеш, за да се ускори Р2Р трансфера. Подобно съществуват децентрализирани еквиваленти, които позволяват на различни общества да изпълняват еднаква задача, за Р2Р трафик, като например Corelli.^[5]

Мемоизация

Основна статия: Мемоизация

Кешът може да съхранява данни, които са изчислени по нужда, вместо да бъдат извлечени от бекъп. Техниката на мемоизация и оптимизация, която съхранява резултатите от повтаряща се функция в речник като по този начин позволява на последващи заявки да използват съхранените данни и да избегнат повторното им изчисляване. например ccache е програма, която кешира резултатите от компилирането, за да ускори неговото време.

Други типове кеш

DNS сървърът BIND осъществява кеширане на домейни към IP адреси, както някои специализирани библиотеки.

Операциите, при които данни се записват едновременно в кеш паметта и основната памет, са често срещани при използване на нестабилни мрежи (като Ethernet LAN), поради изключителната сложност на кохерентния протокол, изисквана при операции, при които данните се презаписват в кеша при всяка промяна, когато връзката е нестабилна.

Търсачките доста често показват уеб страници, които са били индексирани като активни в техния кеш. Например Гугъл предоставя линк към кеширано копие при всеки резултат от търсенето. Това е полезно, когато дадени уеб страници от уеб сървър са временно или перманентно недостъпни.

Кеширането на бази данни може значително да подобри скоростта на изпълнение на процесите в базата данни, например в обработката на индекси, речници от данни и често използвани подмножества от данни.

Фрагментираният кеш използва мрежови хостове, за да предоставят на процесите скалируемост, надеждност и производителност. Хостовете могат да бъдат разположени на едно и също място или да бъдат разпръснати в различни географски региони.

Сравнение на буферна и кеш памет

Семантиката на буферната и кеш паметта не са задължително взаимно изключващи се. Дори и да са, има фундаментални разлики в изпълнението на процеса на кеширане и буфериране.

Фундаментално кеширането реализира ускоряване на изпълнение при многократна употреба на данни, докато кеш системата може да доведе до ускоряване на изпълнение от първоначалното прехвърляне на данни. Това ускорение се дължи на буферирането, което се наблюдава вътре в кеш системата. При кеширане за четене, данните трябва да бъдат извлечени от тяхната първоначална локация поне веднъж, за да е възможно за повторните четения на данните, да реализират ускорение на изпълнението, чрез възможността да бъдат извлечени от преходната, по-бърза памет на кеша, отколкото от първоначалната локация на данните. При кеширане за писане, реализацията на ускоряване на изпълнението може да бъде осъществена още при първото записване на данните, чрез възможността на данните веднага да бъдат запазени в преходната памет на кеша, различавайки трансфера на данните към първоначалната памет, в по-късен етап или друг паралелен, второстепенен процес. Обратно на стриктното буфериране, кеширането трябва да бъде свързано с (потенциално разпределен) кохерентен кеш протокол, за да бъде запазена връзката между преходната памет на кеша и мястото, където данните биват запазени. От друга стана, буферирането:

намалява броя на трансферите за иначе големи по обем данни между комуникационни процеси, което спестява четенето на много, но малки по обем трансфери като ги обединява в няколко по-големи.
осигурява посредник за комуникационните процеси, при които директния трансфер е неосъществим.
подсигурява наличието на минимален размер или репрезентация на данните, който се изисква поне от един от комуникационните процеси, участващи в трансфера.

При типичните имплементации на кеширането, данните които са били прочетени или записани за първи път, са били ефективно буферирани; в случай на записване, в повечето случаи се осъществява ускорение на изпълнението за приложението, откъдето е произлязло. В допълнение на това, частта от кеширащия протокол, където индивидуалните прочитания са преобразувани в партида от прочитания, също е вид буфериране, въпреки че този вид може да има негативно влияние, най-малкото върху изпълнението на първоначалните записвания (въпреки че може да има позитивно влияние върху изпълнението на сбора на индивидуалните прочитания). В практиката най-често кеширането включва някакъв вид буфериране, но стриктното буфериране не включва кеширане.

Буферът е временно място за съхранение на данни, което традиционно се използва, защото инструкциите на процесорите не могат директно да четат данни, запазени в периферни устройства. По този начин, адресируемата памет се използва като преходна фаза. Освен това такъв буфер може да бъде осъществен, когато голямо количество от данни се монтира или демонтира (според изискването на устройството за съхранение на данни) или когато данните могат да бъдат доставени в различен ред от този, в който са били създадени. Освен това цял буфер от данни най-често се пренася последователно (пример: на хард диск), така че самобуферирането понякога подобрява процеса на трансфер на данни или редуцира вариациите или отклоненията на латентността на трансфера, за разлика от кеширането, където целта е да се намали латентността. Тези предимства се наблюдават дори и буферираните данни да са записани на буфера веднъж и прочетени от буфера веднъж.

Кешът също така подобрява процеса на трансфера. Част от увеличението идва от възможността, че няколко малки трансфера са се комбинирали в един по-голям. Но главното увеличение се получава, защото има голям шанс, еднаквите данни да бъдат прочетени многократно или че записаните данни скоро ще бъдат прочетени. Главната функция на кешът е да ограничава достъпа до по-бавното и скрито съхранение. Кешът също така се използва като ниво на абстракция, което е създадено да бъде невидимо от перспективата на съседните нива.

Източници

↑ Сравни с гръцката калка κρυφή μνήμη - „скрита памет“.
↑ ^а ^б S. Mittal, "A Survey of Techniques for Managing and Leveraging Caches in GPUs", JCSC, 23(8), 2014.
↑ Frank Uyeda. Lecture 7: Memory Management (PDF) // CSE 120: Principles of Operating Systems. UC San Diego, 2009. Посетен на 4 декември 2013.
↑ Multiple (wiki). Web application caching // Docforge. Архивиран от оригинала на 2019-12-12. Посетен на 24 юли 2013.
↑ Gareth Tyson, Andreas Mauthe, Sebastian Kaune, Mu Mu and Thomas Plagemann. Corelli: A Dynamic Replication Service for Supporting Latency-Dependent Content in Community Networks. In Proc. MMCN'09 [1] Архив на оригинала от 2015-06-18 в Wayback Machine.

Допълнителна литература

Тази страница частично или изцяло представлява превод на страницата CPU cache в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс – Признание – Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година – от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите.

ВАЖНО: Този шаблон се отнася единствено до авторските права върху съдържанието на статията. Добавянето му не отменя изискването да се посочват конкретни източници на твърденията, които да бъдат благонадеждни.

[1] Сравни с гръцката калка κρυφή μνήμη - „скрита памет“.

[ReferenceGCS7-2] а ^б S. Mittal, "A Survey of Techniques for Managing and Leveraging Caches in GPUs", JCSC, 23(8), 2014.

[3] Frank Uyeda. Lecture 7: Memory Management (PDF) // CSE 120: Principles of Operating Systems. UC San Diego, 2009. Посетен на 4 декември 2013.

[4] Multiple (wiki). Web application caching // Docforge. Архивиран от оригинала на 2019-12-12. Посетен на 24 юли 2013.

[5] Gareth Tyson, Andreas Mauthe, Sebastian Kaune, Mu Mu and Thomas Plagemann. Corelli: A Dynamic Replication Service for Supporting Latency-Dependent Content in Community Networks. In Proc. MMCN'09 [1] Архив на оригинала от 2015-06-18 в Wayback Machine.

[1]

[2]

[3]

[4]

[5]