단일 캐쉬(cache), cache coherency 관련

캐쉬 설계

Risc Processor Cache 설계
http://idec.jnu.ac.kr/data/2001/local/7.18/718h.pdf

Performance of Snoopy Caches for a synthetic N-body application
http://www.cs.bu.edu/faculty/best/crs/cs551/sc.html

Memory Coherence Protocols 논문들
http://www.cs.umd.edu/%7Ekeleher/bib/dsmbiblio/node3.html

Cache memory implementation and design techniques
http://blog.naver.com/silver_birch?Redirect=Log&logNo=60024962492

MESI
http://www.ee.technion.ac.il/courses/044800/lectures/MESI.pdf

Vivio MESI cache coherency description and animation
https://www.cs.tcd.ie/Jeremy.Jones/vivio/caches/MESIHelp.htm


Cache Coherency
---------------------------------------------------------------
SMP같은 multiprocessor 상황에서 processor별 L1 $(캐쉬)들이 있는데
서로간의 데이터 일관성이 지켜져야 한다. 이를 위해서 cache coherency  protocol들이 개발되었다.


04BusBasedSMP.ppt
http://www.lrr.in.tum.de/~gerndt/home/Teaching/SS2006/Hochleistungsarchitekturen/04BusBasedSMP.pdf

Shared Memory Multiprocessors Bus Based Shared Memory Private
http://www.iro.umontreal.ca/~aboulham/F3380/new-l17x4.pdf

High Performance Computing lession 2 Memory Access model
ece.uprm.edu/~wrivera/ICOM6025-2005/lecture2.pdf

http://en.wikipedia.org/wiki/Cache_coherency

Bus snooping
Bus sniffing이라고도 하며, Distributed Memory System이나 multiprocessor시스템에서, cache coherency를 보장하기 위해서 제공됨
캐쉬 컨트롤러는 기다리고 있다가 캐쉬 라인이 invalidate가 되면 이를 버스에 broadcast하는 역활을 한다.
캐쉬 라인은 일반적으로 dirty, invalid, valid, shared 상태를 갖는다.

해당 캐쉬 위치의 상태는 invalid라서 캐쉬 읽기 실패(read miss)시 버스로 읽기 요청을 broadcast된다.
캐쉬들 중 요청한 위치가 dirty 상태인 캐쉬가 복사본을 만들고 valid상태로 변경된 후 복사본을 요청한 노드로 보낸다.
캐쉬 블럭 쓰기가 일어나면 valid 상태에서 dirty상태로 변경되고 이를 broadcast하여 모든 캐쉬 컨트롤러에게 해당 복사본 위치를 invalidate시킨다.


the MESI protocol, MSI protocol, MOSI protocol (more generally: the MOESI protocol), home-based coherence protocols


MSI protocol
------------------------------------------------------
SGI 4D machine에서 사용됨, chache coherency의 필수 3상태만 있음
Modified: The block has been modified by the processor that owns this cache. (아마두 dirty인듯)
Shared: This block is shared by one or more processors, and clean (unmodified) in all of them. (아마두 valid 인듯)
Invalid: This block is invalid, and must be refetched from memory or another cache on a hit to this line. (이건 invalid)

MSI에서는 한Cpu만이 해당 데이터를 갖고 있음에도 불구하고 데이터를 읽고 쓰기 위해서 PrRd/BusRd (I->S)와 PrWr/BusRdX (S->M)의 두번의 버스 transaction이 발생된다.
자신만이 갖고 있는 데이터에 대해서는 Exclusive 상태를 두어 읽을 때
PrRd/BusRd (I->E)로 만들고 쓰기 시 다른 캐쉬는 이 데이터의 복사본을
갖고 있지 않기 때문에 추가의 버스 transaction (BusRdX)를 일으키지 않고 쓸수있다. (PrWr/-- 가 발생됨)


MESI protocol
http://www.wordiq.com/definition/MESI_protocol
캐쉬 라인마다 상태값임
MSI에서는 자기만 사용하는 블럭임에도 불구하고 해당 블럭을
읽고 바로 쓰기를 시도할 경우 처음 PrRd/BusRd 와 쓰기를 위한 PrWr/BusRdX가 발생되어 결국 버스 트랜잭션이 두번 발생되는 불이익이 있다.
어차피 나만 사용하는 데이터 블럭이라면 버스 상에 다른 캐쉬에게 이 사실을 말해줄 필요가 없기 때문에 나만 사용하는 읽기를 요청하면 캐쉬컨트롤러는
PrRd/BusRd(S') 를 발생시켜 E (Exclusive) 상태를 만든다.
E 상태에서 쓰기 시도시 어차피 나만 갖고 있으므로, PrWr/-- 만 읽으켜서
바로 M 상태가 된다. 즉 읽기 시도 후 바로 쓰기 시도 시 하나의 버스 트랜
잭션이 일어나는 이점이 있다.

M - Modified: Indicates that this cache line was modified and therefore the underlying data (e.g. the main memory) is no longer valid.
E - Exclusive: Indicates that this cache line is only stored in this cache and hasn't been changed by a write access yet.  (dirty상태인듯)
S - Shared: Indicates that this cache line may be stored in other caches of the machine.  (valid 인듯)
I - Invalid: Indicates that this cache line is invalid.





MOSI protocol
-----------------------------------------------------
MSI에 Owner 상태가 추가된 형태 현재 프로세서가 소유권을 갖고 있음을 표시, 다른 프로세서가 이 블럭을 요청하면 나중에 서비스 될것이다.



MOESI protocol
-----------------------------------------
full state이다.

기존 MSI나 MESI에서는 다른 캐쉬에서 읽기 요청을 발생시키면 M 상태에
있는 캐쉬는 S로 바뀌면서 BusWB 즉 WriteBack또는 Flush로 메인메모리로
캐쉬 내용을 써버린다. MOESI에서는 이렇게 메모리로 항상 최신값으로
BusWB하지 않고 캐쉬 들간에 서로 주고 받기만하고 메모리는 stale(오래된 값을 갖고 있도록 invalid)되도록 내비둔다. 이렇게 함으로써 SMP 시스템에서
느린 메인 메모리 대역폭시 메인 메모리를 안쓰고 캐쉬끼리 통신하게 함으로써
이익을 줄 수 있다.
만일 캐쉬가 자기만 갖고 있는 블럭을 쓰기를 위해서 M 상태로 변경된 후 다른 캐쉬에서 읽기 요청이 있으면 M 상태에서 O 상태로 변경되고 읽기 요청한 캐쉬는 S 상태가 된다. O 상태는 Owned(Ownership)상태로 자기만 변경할 수 있고 다른 캐쉬에 의해서 공유된 상태를 의미한다. (Shared-Modified)

Modified: This cache has the only valid copy of the cache line, and has made changes to that copy. (혼자만 valid하다, 복사본을 날려줘야함)

Owned: This cache is one of several with a valid copy of the cache line, but has the exclusive right to make changes to it. It must broadcast those changes to all other caches sharing the line.

Exclusive: This cache has the only copy of the line, but the line is clean (unmodified).

Shared: This line is one of several copies in the system. This cache does not have permission to modify the copy.

Invalid: This block is not valid; it must be fetched to satisfy any attempted access.

AMD의 듀얼 시스템 아키텍쳐  - 2) MOESI Cache 일치성
http://www.technoa.co.kr/content/View.asp?pPageID=46319



http://www.cs.auckland.ac.nz/compsci703s1c/lectures/