Тема 12

Организация на кеш-памет. SRAM памет. Йерархия на кеш-паметта


страницата се нуждае от дописване/преглеждане


theme12_cache_memory_scheme.PNG

Структура и организация на паметта

Aдресно пространство, като адресите (на данните и инструкциите) се формират от процесора. Паметта е била хомогенна линейна последователност от адреси. С развитието на технологиите се откриват недостатъци - забавяне поради време за достъп ( време за достъп - от задаването на адреса до попадането в клетката, която се задава с този адрес ). Това време се намалява непрекъснато, но намалява и такта на процесора. Следователно отношението на двете времена се запазва и то е в рамките на около 50 (1 наносекунда за такт на процесора и 50 наносекунди за време за достъп)
За премахване на този проблем се преминава към архитектурни подходи - изграждане на йерархия в паметта. Така вече има бърза и нормална памет (cache и оперативна памет).
ОП – основната памет. Тя трябва да съхранява цялото оригинално линейно пространство.
кеш – съхранява само малка част дублирани адреси от адресното пространство.
По-късно се вижда, че този вариант повишава коефициента на производителност и тази идея се развива, като кеш паметта се реализира вече на 3 нива(L1, L2, L3)
L1 – най-малка като обем и най-бърза
L2 - малко по-голяма и по–бавна
L3 – най-голяма и най-бавна
И трите са много по-бързи за достъп от ОП и трите съдържат само дубликати. Ако един адрес е представен в L1, то той е представен по същия начин в L2 и L3 (съответно в ОП), но ако е в L3, например, то не е задължително той да е представен в L1 и L2.
Колкото е по-малка по обем една памет, толкова е по-бърза. Затова кеша се разделя на три нива и L1 се разделя на памет за инструкции (IS – instruction сегмент) и памет за данни (DS – data segment )( при Intel – 8 KB за данни и 8 KB за инструкции). Когато L2 е вътре в процесора (заедно с L1), се повишава скоростта на работа. Идеята е скоростта на работа с данните между регистрите и L1 да е почти същата като тази на процесора ( с % по-малка ). Преди освен с бързината е имало проблем и с обема на паметта – не е стигала. Например в IBM 360 ( адресната решетка е била 24 бита, тоест адресируеми са били 16МВ. На практика обаче размерът на реалната памет е бил 1МВ. Затова е започнала да се използва виртуална памет, като паметта 1МВ е в ОП, а останалите се записват на диск. Там са всички байтове и при 32 разрядна решетка там има 4GB. Реалната оперативна памет днес се прави така, че да достига 4 GB. Преди виртуалното пространство е било около 10 пъти повече от ОП. Сега се различават до един-два пъти. В ОП реално има дубликати на нещата от диска.

Нека Х е структура в йерархията. Тогава означенията са:
X block – X на нивата L1, L2, L3 и в ОП – минималното количество памет, което може да се използва , обикновено за кешовете е 16Вytes
X hit – когато имаме адресация и адресираният блок се намира в Х, имаме попадение
X miss – блокът, който е адресиран, го няма в Х
X hit time – времето, за което имаме достъп до Х при hit
X miss ratio – отношението на непопаденията – опитите за достъп до Х, при които не се попада на адреса, тоест X MISS RATIO = сполучливи/несполучливи.
X miss penalty - блокът го няма в Х и той трябва да се докара от най-близкото място и да се откара после в процесора. (това е времето за справяне със ситуацията, когато адресът го няма в Х). Например, ако го няма в L1, го търси в L2, ако го няма там, го търси в L3, ако не – в ОП и после го слага нагоре по йерархията в процесора ( L3, L2, L1, процесора ).

Tavg = Thit + %miss*Tmiss
Tavg – средно време за достъп
%miss – процент на пропускания
Tmiss – време за донасяне от друго място
Thit – време за взимане когато е намерен
Ако Thit =1 , Тmiss = 20 , %miss = 5% => средното време ще е равно на 2.

Ефективността на кеша зависи от процента на miss-а. Кеширането се оказва ефективно благодарение на особеностите на Ноймановата архитектура и програмите, които се пишат. Инструкциите, които се изпълняват от процесора, са подредени линейно или на групи в линейни участъци, освен това скоковете при преходите имат стремеж да не са много далечни, а в сравнително близки участъци. Така се получава времева локалност – напоследък използвани адреси трябват отново в близко време. (Те са по-често използвани в кратък период от време). Пространствена локалност – съседните адреси на използвания в момента адрес е много вероятно да бъдат скоро използвани. Тоест ако ни е нужен един адрес, то заедно с този адрес докарваме в кеша и съседите му, тъй като най-вероятно те ще потрябват. Тоест в L1 се докарват не само 4 байта за адрес, а цял пакет от 16 байта. Теглят се повече адреси и освен това когато се сложи някакъв блок в кеша, той най–вероятно често ще се използва => програмите са локални по отношение на времевото и пространственото използване на адреси. Адресите, които са активни (използват се в момента) се движат на групи, това води до сравнително добри характеристики на miss ratio. Регистровата памет е най-бърза.

Reg < 2 KB 1 ns 150 GB/s
L1 < 64 KB 4 ns 50 GB/s
L2 < 8 MB 10 ns 25 GB/s
L3 < 64 MB 20 ns 10 GB/s
ОП < 4 GB 50 ns 4 GB/s
Disk >1GB 10 000 000 ns 10 MB/s

Целта на кеша е да е бърза => не може да се управлява от програма или ОС, трябва да е хардуерно управлявана. Кеша не се командва от ОС.
Технологично има 2 типа памет – статична и динамична (SRAM и DRAM). Биполярни транзистори (по-бързи), се използват за SRAM , отделят повече топлина и са необходими 6 транзистора за 1 бит информация.

theme12_triger.PNG

Информацията в тригера се записва само по време на единичната стойност на clock-a ( клокиран тригер ) и се пази неопределено дълго време, не се нуждае от освежаване. Cache паметите се правят на базата на такива тригери, които обаче са големи ( като обем ), затова са с по-малка плътност. По тази причина cache паметите са с малък капацитет.
ABC = Associativity - Block-Capacity

theme12_cache_scheme.PNG

Структура на cache – сх.2 – съставена от множества и във всяко множество има еднакво количество frame-ове( n на брой множества ). Данните във frame-а са един блок и frame-а съдържа tag – идентификатор на блока ( име ) и 2 бита за състоянието на block-a -> valid(v) и dirty(d).
valid = 1=>frame съдържа нещо, ако е 0 – няма нищо. Какво точно се съдържа се определя от tag и data. В началото, когато се зарежда нова стойност във frame-а d е 0. След първото писане на каквото и да е в блока на frame-а d става 1. Когато се подаде адрес към кеш паметта, той се разглежда като съставен от 3 части – offset – отместване спрямо началото на блока, определя размера на блок ( колко байта е блокът в тази кеш памет ). Ако блокът е 16 Bytes, то offset-ът има размер 4 bits. index – свързван е с номер на множеството. При конструирането на cache-a първо се определя колко ще са множествата ( винаги степен на двойката - например 256 => 8 бита поле index ). Остават 20 b за tag (tag присъства във frame-a ). В зависимост от приетата асоциативност се определя бройката ( плътността ) вътре в множеството. При 4 frame-a във всяко множество има четирипътна асоциативност. При подаване на адрес автоматично се определя index , активира се 1 от 256 множества. Фреймовете се подават на асоциативното устройство и в него се търси едновременно match-ване в tag-а от адреса. Ако някой tag съвпадне с този от адреса hit става 1 и се подават на изхода всички фреймове ( още не се знае кой е номерът на фрейма ). При cache паметта не трябва да има последователно проверяване за match на tag-а, защото това забавя. Едновременно се пускат всички tag-ове за проверка. Ако имаме match излиза hit = 1 и самите данни от блока на frame-а, но не знаем кой frame ни е свършил работа. Тази схема не дава номера на фрейма вътре в множеството. Това върши работа при четене, но при писане ще се изисква да претърсим всички фреймове в множеството, последователно да ги обходим и да работим с този, който ни трябва. Чрез асоциативната схема бързо вадим, каквото ни трябва, но нямаме позициониране.

Имаме 2 крайни случая при реализация на кеш памет: директно изобразяване ( direct-mapped ) – тук нямаме асоциативност; всяко множество се състои само от 1 frame. Тогава по index директно се отива на множество и се проверява дали tag-ът е същият. Друг граничен случай е set-associative. При него полето index = 0 като дължина, т.е. кеш паметта има само 1 множество и в него са всички фреймове ( в случая 1024 ). tag-ът нараства и става 28 бита, докато при direct-mapped полето за tag намалява по размер.
L1 cache в Pentium е двупътно асоциативен, 8KB капацитет, 16 Bytes block => по 2 frame-a в множество, 256 множества, index – 8 bits, offset – 4 bits, tag – 20 bits.
В L2 cache – 64 KB капацитет, 32 B block, двупътна асоциативност ( 2 frames в множество ) => 1024 множества => 5b offset, 10b index, 17 bits tag ( или може 256 множества при 4 frames в множество – 4-пътна асоциативност ).

Има 4 аспекта, по които се определя как работи един кеш:

  1. Къде може да бъде поставен 1 блок ( пласиране на блок ) – при напълно асоциативен кеш се слага в един от малкото фреймове в множество ( в кой да е фрейм ). При direct-mapped в единствения frame на множество
  2. Идентификацията на блока – първо се намира множеството, на което е блокът, в паралелно търсене се търси съвпадение на tag-a и се взима по offset-а конкретната стойност на блока
  3. Replacement – замяна на блокове във frame-овете. Frame-овете се пълнят бързо и когато вече няма място, а трябва да се постави нов => replacement. Първо трябва да се избере в кой фрейм на дадено множество ще слагаме блока. Това става като се използва ефективен алгоритъм по времева локалност ( Least Recently Used = LRU ). Изхвърля се най-рядко използваният напоследък блок и се слага на негово място новият => всяка операция на четене, запис, трябва да се брои, като тези броячи се нулират периодично. По тях се определя кой да се изхвърли. Това е най-добрият алгоритъм, но тук говорим за hardware-на реализация, това изисква много хардуерни ресурси => ще е тежък. Затова се използва и random –изхвърля се случаен ( това не е хубав начин, но е прост и не утежнява допълнително работата ). Затова в cache-a се прави подобрение на random, което е not most recently used (NMRU ) – следи се най-използваният напоследък блок и се гарантира, че няма да се изхвърли той, а върху останалите се генерира случайно число, което определя кой да се махне.
  4. Стратегията на запис ( write strategy ) – когато се получи резултат, той да се запише до последното ниво на паметта ( в L1,L2,L3,ОП,ДИСК ) – нарича се write-through – това намалява производителността на кеш-а т.к. се отнема повече време са се копират данните навсякъде. Но се поддържа консистентност на адресите. Другата стратегия е write-back – процесорът пише само в едно ниво и край. Така може да се получи, че един tag в L1 не отговаря на L2,L3,… т.е. това не е консистентност на данните, но е по-бързо.

При replacement – ако d = 0 => блокът е идентичен на оригинала, т.е. не е писано и можем направо да запишем върху него. Ако d = 1, значи той е променян и трябва да го запишем първо на долното/долните нива и после да пишем върху него. Ако се работи често с една данна, тя се променя в кеша ( например L1 ) и когато вече не е нужна се записва надолу по йерархията ( когато тръгнем да махаме блока ) – това се прави и write-back. По-бързо е отколкото да се сменя 10 пъти навсякъде, но се губи консистентност.
Локация – какво се прави, когато искаме да запишем, а блокът го няма в L1? Опитваме се да запишем в несъществуващ в кеша блок => има 2 стратегии – write-allocate ( върви в комбинация с write-back ) – ако го няма в блока, го докарваме в кеша и правим запис по адреса, който трябва да се запише; блокът остава в кеша; no-write-allocate – блокът го няма в кеша и не се докарва – направо се отива в паметта и се пише там ( разумно е да се ползва с write-through ). Нормално кеша работи с write-back и write-allocate.
ABC:
A – Associativity ( Асоциативност ) – 1,2,4,5,8,16 – по колко frame-a в множество; по-голяма асоциативност – по-нисък miss rate, но кешът поскъпва.
B – Block ( Блок ) – 16,32,64 при кеша се работи с целия блок, независимо каква част от него ни трябва, затова не е нито много голям, нито много малък.
C – Capacity ( Капацитет ) – ако е много малък – голям miss rate, ако е много голям – бавен => затова са на нива

POLICY HIT/MISS to
back + alloc Both Cache
back + noalloc Hit Cache
back + noalloc Miss Mem
thru + alloc Both Both
thru + noalloc Hit Both
thru + noalloc Miss Mem
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License