50.7. CACHE

  



Память очень медленное устройство по сравнению с процессором.
Современные процессоры работают на частоте 3GHz, а внешняя шина на
частоте 800Mhz т.е. в несколько раз медленнее.

Из памяти надо выбирать команды надо читать и писать данные,
а медленная память тормозит всю производительность процессора.

Что делать?
Идея: держать некоторую часть памяти к которой обращались последнее
      время внутри процессора (оттуда мы сможем ее взять быстрее если надо).
      Это место (где держат часть) называется cache (тайник).
	
Принцип:
	подальше положишь, поближе возмешь

Особенно cache актуален для фон-Неймановской архитектуры, т.к. паралельно
с обращениями комманд к памяти идет выборка команд.




  
  Как работает cache 
 

На чтение:
  

Процессор просит cache прочитать данные.
Если данные есть в cache то cache их быстро возвращает
Если же данных нету то cache выбирает их из памяти,
записывает их в себя и возврощает процессору.

	Tef = p * Tcache + (1-p) * Tmem

	Tef    - эффективное время
	Tcache - время доступа к cache
	Tmem   - время доступа к памяти
	p      - вероятность поподания в cache (0..1)

  

  

  



  

  




На запись:

		Cache
	       (на запись)
	       /    \
      Write-through  Write-back
    Сквозная запись  Отложенная запись


Сквозная запись:
  

Данные пишутся в cache и одновременно уходят на шину.

Отложенная запись:
  

Данные пишутся только в cache. Cache сам решает когда и какие
данные переписать из cache в память.






  
  Организация cache 
 

 
  THIS SECTION IS UNDER CONSTRUCTION  
 


	о Direct Mapped
	o Full associative
	o Set associative 
	o Sectored



  
  Direct Mapped 
 
Direct Mapped (прямое отображение):

	Адресс строки i
	Адресс памяти j

	i = j MOD m 	(m - общее число строк в памяти).


	+------------+ +------+ +--------+
	|    TAG     | | LINE | |  BYTE  |	Адресс
	+------------+ +------+ +--------+
		       |                 |
		       +-----------------+
			не хранится в cache


		  Cache
		+-----------+             +---------------------------+
		|           | ----------->| только блок ADDR % M = i  |
		+-----------+		  +---------------------------+
		|	    |
		+-----------+
		|	    |
		+-----------+

  

  





  
  Full Associative 
 
Full Associative (полноассоциативное отображение):
	
	+-------------------++-----------+
	|      TAG	    ||  BYTE     |	Адресс
	+-------------------++-----------+
		             |           |
		             +-----------+
				не хранится в cache


		  Cache
		+-----------+             +---------------------------+
		|           | ----------->|     любые блоки           |
		+-----------+		  +---------------------------+
		|	    |
		+-----------+
		|	    |
		+-----------+

  

  




  
  Set Associative 
 
Set associative (множественно-ассоциативное отображение):
	
	Разбита на подмножества (в строке несколько ways)
	
	+------------+ +------+ +--------+
	|    TAG     | | LINE | |  BYTE  |	Адресс
	+------------+ +------+ +--------+
		       |                 |
		       +-----------------+
			не хранится в cache

	Адресс строки i
	Адресс памяти j

	i = j MOD m 	(m - общее число строк в памяти).
	но в каждой строке несколько ways.


		   Cache
		   2 way
		+-----+-----+             +---------------------------+
		|     |     | ----------->| только блок ADDR % M = i  |
		+-----+-----+		  +---------------------------+
		|     |	    |		    но для них 2 входа
		+-----+-----+		    т.е. может хранить 2 блока
		|     |	    |		    одновременно
		+-----------+

Пример 2 way:
  

  

  


  

  




Почему берут средние биты для индекса LINE?

  


  


  


  


  


  





  
  Протоколы состояния cache 
 


		   Архитектура cache
		(протокол сотояния линии)
		    /          	   \
		однопроцессорно   многопроцессорно
		ориентированный	  ориентированный
		SI		



  
  SI 
 
В однопроцессорно ориентированном cache только процессор в вычислительной
системе имеет cache - все остальные не имеют.

Поэтому элементы в cache имеют сосотояния:
	I - Invalid	 недействительный
	S - Shared       разделяемый

  




  
  MESI 
 
В многопроцессорной системе cache имеет на только процессор но и другие
процессоры и необходимо осуществлять когерентность cache (т.е. соответствие
тому что должно быть в системе.

Существует много дисциплин для многопроцессорно-ориентированного cache,
несомненно самая популярная из них MESI протокол:

  


В MESI протоколе элемент может принимать одно из 4 состояний:
	M 	Modified	Измененный
	E	Exclusive	Измененный только в текущем процессоре
			        и не выведенный еще на шину
	S	Shared		разделяемый
	I	Invalid		недествительный


Другие многопроцессорно ориентированные дисциплины:



  
  MOESI 
 

  




  
  Write-once 
 
  

	Write-once protocol
	Synapse protocol



  
  Berkeley 
 
  

		Berkeley protocol



  
  Illinois 
 
  

		Illinois protocol


  
  Firefly 
 
  

		Firefly protocol


  
  Dragon 
 
  

		Dragon protocol



		Архитектура cache
	    Дисциплина замены блоков
	    /  	     |             \
	 FIFO       LRU            RAND
     (First in   (Last Recently    (Random)
     First out)      Used)
		   /	  \
		точный    приблеженный
		LRU	  LRU


FIFO - заменяется тот элемент в линии которая была выбрана первой.
RAND - заменяется случайный элемент в линии
       (как это сделать - есть счетчик который прибавляет по 1 каждый
	такт процессора, независимо от доступа к памяти,
	его содержимое - это индекс элемента)
LRU  -  Наиболее долго не используемый
	заменяется тот элемент к которому обращались раньше всего.

  




  
  Архитектура Cache 
 

	Cache
	|
	+-- Виртуальный
	|
	+-- Виртуальный с физическими tags
	|
	+-- Физический


 
Виртуальный cache 

 
Виртуальный cache с физическими тэгами 

 
Физический cache 


  




  
  Эксклюзивность 
 

	Cache
	|
	+--- эксклюзивный
	|
	+--- неэксклюзивный
	|
	+--- инклюзивный

Эксклюзивный cache - если информация есть на каком-то уровне cache,
то она отсутствует на других уровнях.
Плюсы:	можно хранить больше информации
Минусы: дополнительное оборудование для поддержки экслюзивности
	Info = SUM(Li)


Инклюзивный cache - в Li всегда содержится все то что есть в Lj, если i > j.
	Info = Lmax

Неэксклюзивный cache - в Li может содержаться, а может не содержаться
информация из Lj.




  
  Иерархия памяти 
 

Уровней cache может быть много, они отличаются размером и быстродействием.
Младшие уровни имеют небольшой размер но высокое быстродействие,
старшии большой размер но медленный доступ (в любом случае быстрее чем
основная память).
  




Могут быть раздельные cache для кода и данных.
Раздельный cache повышает быстродействие т.к. короткие циклы целиком
помещаются в него.
  




Cache занимает много места на кристалле, поэтому возможны варианты когда
на чипе хранятся только tags, а данные хранятся во внешнем cache.
Пример Sun UltraSPARC IV (двухядерный процессор, в котором L2 tags внутри,
а данные снаружи на особой шине).
  




  
  Особенности кэширования для MultiCore 
 

  


  


  


  


Сейчас идут уже и обратные тенденции - типа запрятить одно из ядер, а его
cache передать другому.