Structure of Cache Memory

 

storage service at level k serves as "cache" to level k+1, lower storage servicies.

 

Cache Hits

Cache Miss - Replacement Policy : LRU(less recently used), random replacement policy

 

cold cache : empty cache -compulsory miss, cold miss 

placement policy : 6.22(singleton) -> result in conflict miss(0,8,0,8 loop) 

Increasing Gap between CPU and main memory, SRAM cache memory are insert in the cpu chip.

CPU register : 0 clock cycle

L1 cache : 4 clock cycle

L2 cache : 10 clock cycle

L3 cache : 50 clock cycle

Main Memory: 200 clock cycle

 

 

Associative Cache orginazation -> (S,E,B,m)

 

 

 

캐시 크기 C = 캐시집합 S * 캐시라인 E * 데이터 블록 B (bytes)

 

캐시 집합 S= E개의 캐시라인(들)으로 구성

 

캐시 라인 = 유효비트(1)+태그비트(t)+데이터 블록(B)

 

캐시 주소 : 태그비트 t+Set index(집합 index)s+Block Offset b

 

S=2^s

B=2^b

 

1. with Addres m, Set index로 집합을 찾는다

2. Set 내의 캐시 라인 중 태그비트가 일치하는 것이 없으면 캐시 미스, 있으면 캐시 적중

3. Block Offset (b)를 보고 어떤 index부터 캐시(워드)를 가져와야하는지 확인

 

if m=32, C=1024, B=4, E=1

->S=256(C/B)

->s=8(2^8=256)

->b=2(2^2=4)

->t=22(m-t-b)

 

Dircted map cache 직접매핑캐시(E=1)

 

Thrashing in Directed map cache

-2 Sets, 4 byte block(B=16), C=32,E=1

float dotprod(float x[8],float y[8]){
    float sum=0.0;
    int i;
    for(i=0;i<8;i++) sum+= x[i]*y[i];
    return sum;
}

Address in binary(Tag/Set/Block)

x[0] - > 0x0/0/0000 -> set 0    y[0] - > 0x1/0/0000 - > set 0

x[4] - > 0x0/1/0000 -> set 1    y[4] - > 0x1/1/0000 - > set 1

first hit - > x[0] miss , set 1 filled with x[0] - x[3]

second hit - > y[0] miss , set 1 filled with y[0] - y[3]

third hit - > x[0] miss, set 1 filled with x[0] - x[3]

 

13비트 주소에서 ,4바이트 블록 크기를 가지고 집합이 8개라고 일때

주소 0x0A31의 워드를 참조한다고 하자

0000 1010 0011 0001

tag bit 0101 0001/set index100/block offset 01

4번 집합을 보고, valid bit가 1이며 태그비트가 51과 일치하는 라인이 있으면 캐시 적중이다

캐시적중이면 첫번째 블록부터 워드를 가져온다

 

 

Fully Associative Cache 완전결합성캐시(S=1)

no set index in Addres m, Addres only divide in Tag bit and Block offeset

-> Fully Associative Cache is used in small cache, TLB(translation look-aside buffers), because is hard to make parellelly searching tag bits

 

Issue about write

write through : write immediately to next hierarchy

-> cause lot of bus traffic in every write

write back : when replacement algorithm update block, write to next hierarchy

-> need to set dirty bit

 

write miss

1) write-allocate : get cache from next level, then write

-> matched with write back

2) no-write-allocate : write directly to next level

-> matched with write through

lower hierarchy, need more transfer time, probably use write back.

 

Unified Cache : 통합 캐시 - save data,instruction

i-cache : 인스트럭션 캐시 - save only instruction

d-cache:데이터 캐시 - save only data

 

미스 비율 miss rate = #misses/#references

적중 비율 hit rate = 1-miss rate

적중 시간 hit time

 

Block Size

블록 크기가 크면 공간 지역성이 좋아지지만,

캐시 라인 수가 적어지기때문에(전의 위치의 메모리 4개를 참조한다고 캐시 라인 수가 2개면 자주 교체가 일어남) 시간 지역성이 안좋아진다

또한 전송시간이 길어져 미스 비용에도 안좋은 영향

 

Assoiciativity 결합도 : 집합당 캐시 라인의 수

More Associativity, less possibility of thrasing

but need more tag bit, additional LRU state bit per line

 

 

if 2.1GHz(2100Mhz) Computer's L1 cache Read Throughput is 12,000MB/s,

CPU clock cycle to access 16 byte word is

2100/12000 * 16 = 2.8 -> 3 Clock Cycle