Karh09 11

11. Организация и йерархия на кеш паметта. Повишаване на производителността на кеш-памет.


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


Разяснения

Производителността на компютрите се намалява поради голямата разлика в бързодействието на ОП и ЦП. За сравнение на един такт на процесора при изпълнение на дадена инструкция е нужна една наносекунда, докато около 50 наносекунди са нужни за достъп до паметта. Терминът „идеална памет” означава такава памет, която в момента на подаване на адреса на исканата клетка от паметта, да бъде върната информацията от тази клетка. Но това е трудно осъществимо. За да се помогне работата на ЦП и да се намали до някаква степен това време на изчакване което се получава, навлиза идеята за направата на по-малки и по-бързи(RAM) памети с по-малко забавяне наречени кеш памети. Тези памети са реализирани на основата на предположенията, че ако на процесора му е трябвала някаква инструкция, то в скоро време тя отново ще му потрябва в близкото бъдеще и второ, че ако на процесора му е трябвала някоя инструкция, то тези около нея ще му потрябват в близкото бъдеще. Тази нова, малка и бърза памет се вкарва във Фон Ноймановата архитектура между ЦП и ОП.
untitled33.JPG

Кешът се състои от регистрова памет(RF) и/или статична памет(SRAM), а ОП се състои от динамична памет (DRAM). При поискването на информация от ЦП се проверява първо дали тази информация я има в кеш, ако я има то имаме hit. Това означава, че ще имаме достъп до данните с малко закъснение. Ако не може да се намери търсената информация в кеш паметта, то имаме miss. Това означава, че ще трвбва да се обърнем към DRAM и да търсим информацията там, което от своя страна означава, че ще имаме голямо закъснение при получаването на данните.

Структура на кеш паметта

untitled34.JPG
Кеш паметта е съставена от множества. Всяко множество е съставено от равен брой фреймове(line), които пък от своя страна са съставени от идентификатор(address tag), блок(data block) и два бита за състояние. address tag – а е част от адреса в ОП и еднозначно идентифицира разположението на данните в ОП. Фреймовете в кеша са разбъркани от големи и малки адреси.

Ако трябва да сложим копие на някакви данни от ОП (блок) в кеша има три начина това да стане в зависимост от организацията на кеш паметта:
1. При пълно асоциативен кеш (fully associative) – имаме едно множество от всички фреймове и там може да се сложи на произволно място.
2. При двупътно асоциативен кеш (set associative) – тогава имаме няколко индексирани множества с по равен брой фреймове където по индексът на множеството се ориентираме къде трябва да се постави новия блок.
3. Кеш с директно изобразяване (direct map) – тук отново имаме едно множество от индексирани фреймове и блокът се поставя на точно определеното място.
Четенето съответно при трите вида кеш става по следния начин:

Fully Associative

untitled35.JPG

Set Associative

untitled36.JPG

Direct Map

untitled37.JPG

Време за достъп

Средно време за достъп в паметта = времето при hit + Колко средно се получава miss * Глоба (времето необходимо да се извлече информацията от ОП и да се запише в кеш)
Average memory access time = Hit time + Miss rate x Miss penalty
To improve performance:

  • reduce the hit time
  • reduce the miss rate (e.g., larger cache)
  • reduce the miss penalty (e.g., L2 cache)

Причини за miss при кеш паметта

  • задължителен miss при първо обръщение към този адрес – студен старт
  • поради капацитета – капацитета се е запълнил и е изхвърлил данни и тях ги няма, но на нас ни трябват
  • по каква схема се разполагат блоковете и кои линии се изхвърлят при запълване на капацитета

Различните варианти на кеш паметта имат различни преимущества и недостатъци. Ако размерът на кеш паметта е по – голям, това ще намали miss-овете но ще увеличи времето за hit. Ако има по-голяма асоциативност отново може да се увеличи времето за hit. По-големият размер на блока също увеличава miss-овете.

Replacement Policy

Кой фрейм трябва да се извърли?

  • Random
  • Least Recently Used (LRU)
  • LRU cache state must be updated on every access
  • true implementation only feasible for small sets (2-way)
  • pseudo-LRU binary tree often used for 4-8 way
  • First In, First Out (FIFO) a.k.a. Round-Robin
  • used in highly associative caches
  • Not Least Recently Used (NLRU)
  • FIFO with exception for most recently used block or blocks
  • One-bit LRU
  • Each way represented by a bit. Set on use, replace first unused.

Кеш с много нива

untitled38.JPG
Кеш паметта се реализира вече на 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 пъти повече от ОП. Сега се различават до един-два пъти. В ОП реално има дубликати на нещата от диска.

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

Q1: Дали новата стойност ще се разпространи до паметта?
1. Да. Записва се през всички нива на кеша и се записва в основната памет.
write through – проникващо през кешовете

-    бавно стават операциите за запис, независимо от производителността на кеша
-    ще се увеличава честотата на писане
+    при четене всички нива на кеша ще имат новата стойност

2. Не. write back – новата стойност не стига до основната памет, а се записва само в най-близкото ниво на кеша.
Заради възможността от поява на желание за промяна на паметта в бъдеще се налага добавянето на още един бит за състояние в кеша (dirty bit). когато се запише нещо в линията този бит става 1, 0 – чиста линия.

+    наличието на този бит улеснява replacement-а, щом е чист, значи копието му съвпада с копието в другите нива
-    консистентността се нарушава
+    ще се намали трафика от големия кеш до ОП (по голям кеш =повече трафик)

Q2: Какво става когато процесора подаде данни, но адреса го няма в кеша?(имаме miss)

1. алокира се кеш блока – блокът в които трябва да се пише се изтегля от паметта и се слага в L1 кеша . Намества се в кеша без да се чете от него и след това се пише (write back)
2. Пише се директно в ОП. Не се чете в блока, не се губи време в четене.

Кеш паметта е направена за бързо четене. Паралелно със сравняването на тага се изтегля и информацията и при получаването и не се знае от кой фрейм е получена тя. Това не може да се приложи при писането в кеша. При писане първо се намира тага който ни е необходим за писане и после се пише. По този начин записът става много бавен. Решението е създаването на write buffer който се слага на входа на кеша (вътре в него). Там стоят и адреса и данните и процесорът счита, че данните са записани. При постъпване на данни за запис в кеша първо се проверява дали има hit и ако има тогава се записват в буфера и когато им доиде реда се записват в кеша. Обработката на буфера става паралелно с четенето от кеша. Надеждата при създаването на кеш паметите е, че ще има по-често четене отколкото писане. Буферът не може да бъде по-голям за да не се задържа информацията в него и процесорът ще чака докато се освободи място в него. Буферът ускорява производителността на кеша. Ако се сложи и един write-back буфер на края на кеша се ускорява и replacement-а.
untitled39.JPG
Има някви методи за ускоряване които няма да пиша щото стана много цялата глупост и ако успея да напиша и половината евалата!

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License