(교수님께서 챕터5를 보고 챕터4를 하자고 하셔서 그 순서로 정리)
programmers는 용량 제한없는 빠른 메모리를 원한다. 이 챕터를 통해 그 환상을 최대한 실현하는 법을 알아본다.
물론 계속 큰 메모리를 계속 빠르게 접근하는 것은 불가능하다.
자 그럼 그 기저에 깔린 원리를 알아보자.
> Principle of locality
1. Temporal locality (locality in time)
: 특정 item이 한번 referenced되면, 해당 item은 짧은 시간 내에 다시 referenced 된다는 것
2. Spatial locality (locality in space)
: 특정 item이 한번 referenced되면, 해당 item의 주변 item들이 짧은 시간 내에 다시 referenced 된다는 것
위 원리는 컴퓨터 메모리에서든, 도서관에서 책을 빼내와 자료조사를 하든, 둘 다에서 적용되는 기본 원리이다.
프로그램에선 loop나 array이 그 예시이다. instructions도 연속적으로 접근한다. 즉 프로그램은 spatial locality가 높다.
> Memory Hierarchy
그러니 Principle of locality를 활용해 메모리 접근 효율성을 높일 수 있다.
Memory hierarchy를 통해 위 원리의 이점을 활용한다..
높은 level로 갈 수록 processor과 가까이 위치하며, 접근이 빠르고, 용량이 작고, (용량당 가격이) 비싸다.
낮은 level로 갈 수록 processor와 멀리 위치하며, 접근이 느리고, 용량이 크고, (용량당 가격이) 싸다.
낮은 level로 갈 수록 모든 data를 포함한다. 즉 특정 level memory의 data는 본인보다 높은 level의 data를 모두 포함한다.
모든 프로그램은 memory에 접근하는데 상당한 시간을 할애하므로 memory system은 performance를 결정하는 주요 요소이다. -> Make common case fast / Amdahl's law
Memory hierarchy는 (1)가장 최근 접근한 데이터를 processor와 가까이 둬서 temporal locality의 이점을 활용하고, (2)block채로 데이터를 upper level에 넣음으로써 spatial locality의 이점을 활용한다.
> 용어 정리
메모리들이 정보를 다루는 최소 기본 단위가 있는데, 이를 block 혹은 line이라 한다.(메모리 종류마다 block 크기가 다른가 모르겠네) (교수님께선 cache로만 설명하셨음, 즉 캐시의 기본 데이터 단위가 block이다.. 라고)
processor가 memory에 특정 주소의 data를 요청한다. 이때 가장 높은 level의 memory에서 제일 먼저 찾는다. 여기에 processor가 요청한 데이터가 있다면 이를 hit이라고 하고, upper level의 메모리에 원하는 값이 없으면 miss라고 한다.
miss가 발생하면 해당 level의 메모리는 더 낮은 level로 가서 값을 찾아 해당 block을 읽어온다.
읽기 시도 중 hit이 발생한 비율을 hit rate(hit ratio)라고 하고, 반대로 miss 발생 비율을 miss rate라고 한다.
즉, hit rate가 높을수록 속도와 모두 챙기는데 가까워진다.
우리가 memory hierarchy를 사용하는 주요 이유는 퍼포먼스 때문이므로 아래 시간 정보는 중요하다.
Hit time : upper level(cache 말하는거임)에 접근하는데 걸린 시간 + hit/miss 판단 시간(즉, upper level에 값이 있는지 탐색하는 시간) -> (hit 판단+처리 시간 다 말하는듯?? 다른데서도 hit time 말하는거 보면 그런 맥락임)
miss penalty : upper level에 lower level의 block을 올리는데 걸리는 시간 + 해당 block이 다시 processor까지 가는데 시간
(책에선 메모리로 말하긴하는데, 교수님께서 cache 기준으로 설명하셔서 그냥 cache에 접근하고 한다고 보면 될듯)
miss penalty를 processor 올리는 시간도 포함은 하는데, 뭐 계산하거나할때 굳이 그렇게까지 나누진 않는 것 같다.
→ Hit time은 그냥 Processor랑 Cache 사이에서 일어나는 시간들(hit/miss 판단시간 포함), Miss penalty는 miss가 생겨서 Cache랑 MM 사이에서 추가로 일어나는 시간들.. 문제풀땐 이렇게 단순하게 알아도 ㄱㅊ을듯
밑에 문제들도 보면 이 개념으로 전부 풀린다. miss penalty에 processor 올리는 시간 포함됐다고 일일이 따지지 않는다.
The Basics of Caches
(ch4에서 볼 datapath 내의 메모리가 캐시라고 보면 된다.)
CPU가 메인 메모리까지 가는건 꽤 소모가 있는 작업이다.
위에서 말했듯 우리는 locality 원리에 의해 메모리를 계층 구조로 나눴다.
Cache 메모리는 그 중 가장 CPU와 가까운 메모리이다. 메인메모리에 접근하는 시간이 비교적 길기때문에, 중간에 CPU와 가까운 작은 메모리 공간을 하나 두고 locality 원리를 이용해 훨씬 더 빠르게 메모리에 접근하는 것이다. locality 원리에의해, "접근 했던 값과 그 근처의 값들"을 저장해두면 상당히 편리할 것이다.
아래 Multi-level cache는 그런 중간 저장소 level을 더 늘린 것이다. cache가 추가된 이유(원리)를 생각해보면, 그 사이에 cache가 더 있으면 당연히 miss penalty도 줄어들고 더 빠를 것이다.
참고로, CPU는 cache의 존재를 모른다. multi-level cahce에서도 마찬가지로 서로의 존재를 모른다. 그냥 메모리의 주소를 사용해서 main 메모리에 접근하듯이 접근하면 중간에 cache가 끼여서 알아서 처리해주는 것이다.
즉, 프로세서는 cache에서 데이터를 load/store하는지 memory에서 데이터를 load/store하는지 전혀 모른다. 또 cache가 갑자기 없어져도 correctness엔 문제가 없다. 속도에 좀 문제가 생길뿐...
Caching은 prediction의 한 예이다.
거의 최신 컴퓨터의 Cache의 hit rate는 95퍼센트를 넘는다.
(교수님께서 요즘에 실제 메인 메모리까지 가지 않고 cache에서 모두 해결되는 경우가 99.99... 퍼센트라고 하셨음. 99프로인건 확실하고 소숫점 뒤에 9가 몇개가 들어가냐로 얘기하는 수준이 됐다고 하심)
> Direct-mapped Cache
Cache내에서 메모리의 data를 어떻게 배치할까?
miss가 나서 특정 block을 low level 메모리에서 불러오는 순서대로 막 넣어도 되긴 하겠지만, 그렇게 하면 Cache내에 프로세서가 요청한 값이 있는지를 찾는데 너무 오래 걸린다.(이 방법을 fully associative cache라 한다.)
그래서 hit/miss 판단 속도를 높이기 위해 direct-mapped cache라는 기법을 이용하기도 한다. hit/miss 판단도 시간이 걸리는 문제이다.
즉, Direct-mapped Cache는 메모리 data를 더 높은 레벨인 cache로 올릴때 어떻게 data를 배치할지에 대해 정한 방법 중 하나인 것이다.
: cache에서의 위치는 메모리에서의 위치를 기반으로 할당한다.
: Cache내에서 위치 = (Block address) modulo (Number of blocks in the cache)
: 특정 메모리 location은 정확히 cache의 한 위치에만 대응된다.(당연히 cache가 메모리보다 더 작으니 1대1로 대응되진 않음)
식만 봐선 이해가 안 될 수 있으니 위 그림을 같이 보자.
그림에서 메모리는 실제 5비트지만, cache는 3비트 주소를 사용한다.
direct-mapped cache는 캐시의 특정 공간을 메모리의 특정 공간만 들어올 수 있도록 하는 것이다.
여기선 메모리 주소의 하위 3비트가 캐시로 올라갈때 캐시에서의 주소가 된다. 즉, 그림에서 빨간 박스들에서의 같은 index가 cache에서 같은 위치를 가진다.
이렇게 해싱? 비슷하게 함으로써 Cache 내에서의 hit/miss 판단을 빠르게 한다.
(하지만 공간 활용이 잘 안된다는 단점이 있다.)
tags
: tags 라는 추가 저장 공간을 활용해 indexing할때 활용되지 않는 상위 주소를 마저 저장한다. 이 경우엔 주소의 상위 2비트를 tags에 저장한다. 뭐 당연히 이 값이 있어야 processor가 요청한 data가 맞는지, 즉 hit 인지를 최종적으로 확인할 수 있다. 프로세서는 보통 메인 메모리의 주소를 통해 값을 요청할 것이므로 지금 저장된 값의 메인 메모리 풀 주소를 당연히 cache에서도 알고 있어야한다.
Valid bit
: Cache에서의 특정 entry가 유효한 값인지 확인해주는 bit이다. HW에는 garbage 값이더라도 일단 값은 들어있다. 그것만 보고선 그 위치에 유효한 값이 있는건지 없는건지 알 수 없으니, 이 비트로 유효한 값이 들어있는지를 체크한다.
Cache read 간단 과정
1) CPU에서 특정 memory 주소의 값을 읽어오도록 요청한다.
2) index를 이용해 cache에서 해당 위치를 찾아간다.
3) valid한지 + tag 값이 일치하는지 확인한다.
4-1) hit이라면, 그대로 hit판단하고 processor에 값을 보낸다.
4-2) miss라면, memory에서 값을 가져와 기존 값을 덮어쓰고(valid bit가 N이었다면 Y로 바꾸고), processor에 값을 보낸다.
(마지막에 덮어쓰는 과정은 사실상 temporal locality 이점을 활용하는 것)
(1way direct-mapped cache에선 각 메모리 값이 올 수 있는 자리가 하나 뿐이라 그냥 그 자리가 바로 덮어씌워진다.)
Address 분석
위에선 간단하게 Memory 주소의 하위 비트들이 cache 주소(index)로 들어간다고 했는데, 그건 cache에 1바이트씩 데이터를 저장할때 얘기였다.
하지만 보통 cache는 n개 word(4bytes) 단위로 데이터를 처리한다.
cache가 n개 words를 처리한다고 가정하고 아래를 보자. 아래 그림은 Memory의 풀 주소를 나타낸다.
Cache는 word 단위로 주소를 저장하므로 주솟값 뒷쪽 2비트는 index로 사용할 필요가 없다.
아래 그림을 보자.
Data 영역에 1 word 크기의 data가 들어간다고 해보자. 그럼 address의 뒷쪽 2비트에 어떤 값이 오든 모두 cache에서 같은 index를 가리킬 수 밖에 없고, 이를 굳이 구분해 저장할 필요는 없다. 이 cache 주소로 사용되지 않는 2비트를 우리는 byte offset이라고 한다.
예를들어 보자. 1번~30번까지 30명의 학생이 수학여행을 갔다고 해보자. 3개 방(1~3번방)에 각각 1~10번, 11~20번, 21~30번 학생을 배정한다. 학생 번호로 방을 찾고자 할때 끝자리는 필요없다. 15번학생이든 16번이든 12번이든 앞자리 1만보고 1번방에 있다는걸 알 수 있다. 이때 무시되는 끝자리가 byte offset인 셈이다.
같은 논리로 Cache가 2개 이상의 word를 기준으로 처리할때도 생각해볼 수 있다. 이때는 뒷쪽 2비트 바로 왼쪽의 비트들도 index로 사용할 필요가 없을 수 있다. 예를들어 Data에 2개 word가 저장된다면, 하위 3비트가 어떻든 모두 같은 index를 가리킬 것이기 때문이다. 이 1비트를 우리는 block offset(word offset이라고 했으면 더 좋을거같긴한데)라고 한다.
이렇게 Cache의 Data가 저장하는 크기에 따라 index로 사용되는 비트가 무엇인지는 달라진다.
결국 CPU는 byte 단위로 주소를 사용하니, cache의 한 index로 안에서 offset으로 특정 위치를 지정한다.
참고로 이런 offset들이 Cache 내에서 위치를 찾아가거나, hit/miss 판단하는데는 쓸모가 없지만,
값을 읽거나 쓸때 cache 안에서 위치를 찾아야하니 아예 쓸모없는건 아님.
(cache miss로 인해서 Main memory와 cache가 소통해야할때는 cache의 block 단위로 읽어오고 써버리니까, 그때도 offset은 쓸모없다.)
Cache의 총 bits 수는 cache size(block(line) 총 크기)와 address size로 결정된다. (바로 아래 예시에선 Data 공간 크기도 같이 주긴 함)
ex) Cache size가 2^n개의 blocks이고, block size가 2^m개의 words라고 해보자. address는 32-bit이다.
이때 tag field의 크기는 (32 - 2 - n - m)이다. n은 index로 쓰이는 비트 개수고, m은 block offset 크기이므로 빼주면 된다.
Cache내 "총" bit 개수는 2^n x ((32-2-n-m) + 1 + 32*2^m) 이다.
★★★
간단하게 생각하면 굳이 byte offset과 block offset을 나눌 필요도 없다. 그냥 Data 영역에 저장되는 데이터 크기가 얼마인지 보고 그 부분은 빼고 index로 쓰면 된다. 무슨 말이냐면, 우리가 1 word씩 cache에 저장한다면 ...100, ...101, ...110, ...111 주소의 데이터들은 모두 cache의 한 entity(line, index)의 data에 모두 쭉 저장되므로, 뒷쪽 비트는 index로 사용할 필요가 없단 소리다.
다른 예시를 보자면, Data 영역에 64바이트(16워드)씩 저장하면, memory address에서 하위 6비트는 index로 사용되지 않는다. 그래서 우리는 Data 영역의 크기에 따라 index 비트를 누구부터 쓸지 정하는 것이다.
이후 index 크기는 cache가 저장하는 entities 개수에 따라 다르다. cache가 저장하는 entity가 256개 있다면, address의 offset을 제외하고 남은 부분의 하위 "8비트"가 cache에서 index 위치를 찾기위해 사용된다.
이렇게 index까지 빼고 남은 부분은 tag field로 들어간다.
어렵게 생각할 필요 없이, 그냥 메모리 address가 어떻게 cache에서 값을 찾기위해 파싱되는지, 실제 cache 구조는 어떤지, 그리고 아래에 나오는 hit 판단 하고 data 뽑아내는 회로 같은걸 각각 이해하고 있으면 문제 나와도 조건대로 분석해서 풀면 됨.
책 p.~ 문제 풀어보기
★★★
> Cache Size
Cache의 전체 size를 구하고 싶다면, index개수x(valid bit 너비 + tag 너비 + data 영역 bit 수) 를 하면 된다.
하지만 보통 cache size라고 말하면 ""tag나 valid 영역은 제외하고 Data 부분에서 저장할 수 있는 크기만"" 말하는게 관습이니 주의
> 예시
간단한 실제 cache 회로를 하나씩 살펴보자.
Address는 32비트이다. 이 Cache는 16word 단위로 데이터를 주고 받는다.
저장할 수 있는 blocks(entries) 개수는 총 256개이다.
Address 비트들을 보면, 우선 byte offset으로 2비트를 사용하고, block offset으로 4비트(16워드씩 저장하기때문)를 사용한다.
entries는 256개이니 offset 윗부분 8비트를 index로 사용하고, 남은 비트는 tag로 간다.
이제 CPU가 특정 주소의 값을 요청하면, 바로 위에서 말한대로 주소를 파싱해서 cache에서 값을 찾아본다.
회로를 보면, index를 우선 보고, valid와 tag 값을 비교해 둘 다 성공한다면 Hit으로 판단한다.
Hit이라면, offset까지 조합해 Mux로 Data 중 한 word만 골라서 내보낸다.
> Cache 기본 특성
> Block Size와 Miss Rate
block 크기는 얼마가 적당할까? entry 개수는 얼마가 적당할까? → 위 표를 보면 어느정도 알 수 있다.
우선 우측 Y축을 기준으로 보면, Cache size가 늘 수록 miss rate는 계속 줄어든 다는 것을 볼 수 있다. 이는 당연한 현상이다. cache에 많은 값을 저장할 수 있을수록 CPU가 요청한 값이 있을 확률은 올라간다.
cache size가 커질수록 miss rate가 개선은 되지만, 개선되는 폭이 작아진다는 것을 주목하자.(nonlinear)
즉, 어느 시점이 되면 설계자들은 자원(돈)을 더 투입해서 조금의 이득을 볼 지, 아니면 이대로 만족할지를 결정해야한다.
이런 것은 컴퓨터 분야 뿐 아니라 다양한 곳에서도 일어나는 현상이다.
이제 특정 cache size로 고정했을때 Block size 변화에 따른 Miss rate를 보자. block size가 늘어난다고 miss rate가 무조건 작아지진 않는다.
특정 값까지는 miss rate가 작아지지만, 그걸 넘어서면 miss rate가 다시 상승한다.
왜 그럴까?
1. Block size가 너무 작을때는 Spatial locality가 제대로 작동하지 않는다. 주변의 값을 곧 참조하는데, block size가 작으니 충분한 주변 값을 가져오지 못해서 spatial locality를 반영하지 못한다. 그래서 block size를 늘려주면 miss rate가 감소하는 것이다.
2. Block size가 너무 클때는 Temporal locality가 제대로 작동하지 않는다. 한번 참조한 값을 다시 참조해야하는데, block size가 크면 cache에 저장할 수 있는 entity 개수가 작아지므로 해당 값이 금방 overwrite 될 수 있다. 따라서 block size를 줄여주면 miss rate가 감소하는 것이다.
물론 프로그램마다 어떤 locality를 근거로 한 현상이 자주 등장하는지는 다르다.(교수님께서 위 그래프는 아마 여러개 프로그램 돌려서 평균 낸 것일 거라고 하심)
block size가 커지면 또 다른 문제가 생기는데, miss의 cost(==miss penalty)가 증가한다는 것이다. miss 횟수가 비슷하더라도, miss가 나서 다시 memory에 접근해서 값을 가져올때 block size가 클 수록 더 시간이 오래 걸린다. 따라서 당연히 다른 경우보다 miss cost가 크다.
(그래서 위 그래프에서도 block size가 큰 경우가 block size가 작은 경우보다 miss rate가 작긴 하지만, 실제 cost를 따져보면 모를 일이다...)
block size 증가로 인한 miss penalty를 줄이려면 Main Memory의 bandwidth를 늘려야한다.
> Miss Penalty
Miss Penalty를 어떻게 개선할까? Miss penalty는 위에서도 봤지만, lower level의 block을 high level memory로 옮기고, 그걸 또 processor에 주는 시간까지 합한 것이다.(miss가 뜨면 생기는 "패널티"인 셈) 이걸 좀 더 자세히(?) 보자.
Miss Penalty = Set-up time + transfer time
여기서 set-up time은 MM 내부에서 값을 찾고 하는 등의 시간이라 MM을 바꾸지 않는 이상 개선하기 쉽지 않다.
즉, 우리는 transfer time을 개선해야하는데, 사실 이것도 고정된 값이라 실제로 줄이진 못하고 특정 기법을 사용해 소모 시간을 줄일 수 있다.(hiding the transfer time)
1) early-restart : Instruction data 같은 순차적으로 접근해야 하는 data에 적용하면 빠르다. miss가 났을때 MM에서 값을 가져오는데 이때 process는 값을 다 가져오기 전까지 잠시 멈춘다. early-restart를 이용하면 MM에서 첫번째 data를 가져오고 바로 process를 계속 실행시킨다. 그렇게 실행되는 동안 동안 뒷부분 나머지 값들을 가져온다.
2) critical word first : instruction 말고 일반 data들은 순차적으로 접근하지 않는 경우가 많아 중간의 값을 요구할 수도 있다. 이럴때 요구하는 값을 가장 먼저 주고 'early-restart`와 같은 방식으로 멈춰있던 프로세스를 재시작 하는 것이 critical word first라는 방법이다.
그냥 이 개념 볼때만 processor로 값을 올리고 처리하는 시간도 miss penalty에 포함된다고 보자.
(엄밀히 하자면 할 수 있을 것 같긴한데, 교수님께서 내주시는 과제나 이런거보면 굳이 안그래도 될듯.
> Intel core i7 예시
실제 Cache들은 이렇게 multiLevel로 구성된다. (miss penalty가 줄어듦)
L3는 shared cache이고, L1과 L2는 한 core가 전용으로 사용한다.
바로 위에서 miss penalty를 줄이기 위해 두 종류의 데이터를 다르게 처리한다고 배웠다.
그래서 L1을 보면 instruction data와 일반 data를 구분하여 cache에 올리는 것을 볼 수 있다.
(CPU 밖에서 보면 L3까지 모두 CPU로 보임)
> Cache Miss Handling in Processor
instruction을 읽을때 miss가 발생했을때 어떤 일이 발생하는지 보자.(일반 data miss도 비슷함)
1. PC-4를 memory unit에 보냄 (다시 miss가 난 주소를 읽어야하는데 PC는 바로바로 업데이트 되기때문에 PC-4 이용)
2. MM에서 data를 읽어오도록 지시
3. data가 준비될때까지 대기
4. cache에 data 작성 (tag, valid도 작성)
5. 다시 그 inst(data)를 읽어오도록 하는 instruction을 Re-send -> 이번엔 hit!
(miss가 나면 작업 완료될때까지 잠시 중지된다.)
> Write Handling in Cache
Cache가 Write를 다루는 두가지 방법이 있다.
1. Write-Through Cache
: Write를 Cache와 MM(Main Memory)에 둘 다 반영하는 방식이다.
data의 일관성(consistency)이 보장된다는 장점이 있다. 하지만 Write 명령때마다 MM에 접근하므로 Cache를 사용하는 이점이 없어진다는 단점이 있다(read 할때 이득이 있긴하지만).
그래서 write buffer라는 것을 이용한다. write 명령에서 write buffer에 값을 올려두기만하고 다음 작업을 계속 진행하여 작업 속도를 높인다. 그러면 write buffer는 asyncronous하게 MM에 해당 값을 천천히 올린다.
하지만 write buffer을 이용하면, write buffer가 값을 다 쓰기 전에 MM에는 과거 값이 들어가있어서 그 사이에 다른 core에서 해당 값을 조회하면 문제가 생긴다. 즉, data consistency를 잃는 순간이 발생해버린다.
(책: write buffer를 쓰더라도 결국 write buffer가 꽉차면 멈춰야하니, stall이 발생할 수도 있다.)
2. Write-Back Cache
: (Cache의 이점을 이용해) write를 우선 cache에만 반영하는 방식이다. 그리고 나~중에 Cache의 바뀐 값이 MM의 다른 값이 올라와서 자리를 내줘야할때(?), MM 또한 update 시켜준다.(바뀐 값임을 체크하기위해 dirty bit라는 것 사용)
매번 MM에 접근하지 않으므로 처리 속도가 빠르다는 장점이 있다. 하지만 이번에는 data consistency가 보장되지 않는다. 따라서 correctness 문제가 발생할 수 있다. 실제 update된 값이 특정 core의 cache에만 있다면, 다른 core에선 다른 값을 사용하게 될 것이다.
그래서 이 경우에는 write로 인해 특정 cache의 값이 바뀌면, 다른 cache에 해당 memory 주소의 값이 invalidate 하다는 신호를 보내준다.
그럼 그 신호가 발생한 뒤로는 해당 메모리 주소의 값을 사용하지 못하게 하거나, 그 값을 이용하려면 MM으로 가지않고 update 된 값을 가진 cache로 가서 읽어오도록 하겠지? 정확히 어떻게 되는진 모르겠으나 대충 이렇게 처리할 수 있다고 설명하심.
뭐 어쨌든 이런 방식들을 더 동원해서 cache의 consistency를 유지해야한다. 따라서 cache간 소통 같은 추가 작업이 필요하므로 write-through 보다 구현이 어렵다.
write할때도 miss가 나기도 하는데 이건 어떤 경우냐면,
read에서 miss와 마찬가지로 cache에 해당 주소의 값이 올라와있지 않은 경우이다.
write miss가 발생한다면, read miss 일때와 마찬가지로 locality 원리에 의해 해당 값을 memory에서 cache로 올려야한다.
> Cache Performance
chap1에서 봤듯이 CPU time은 다음과 같다.
CPUtime = total clock cycles x clock cycle time
하지만 여기서 Cache가 추가되면 Cache에서의 작업을 처리하기위한 추가 cycle을 고려해야한다.
즉 (1)total clock cycles = CPU execution clock cycles + Memory stall clock cycles 로 봐야한다.
이 Memory stall cycles = Read stall cycles + Write stall cycles 로 나눠지는데, Write에서의 cycle 계산은 쉽지 않다.
write buffer를 예측하기는 쉽지 않고, write-back 방식에서도 모두 고려하기는 어렵다.
그래서 복잡한 부분은 다 쳐내고 read와 write miss penalty를 같다고 가정해서 간단하게 아래 식으로 계산한다.
(2)Memory Stall Cycles = IC x (Mem Access/IC) x miss rate x miss penalty
("전체 IC 중에서 메모리 엑세스 하는 놈들 중에서 미스나는 놈들" 곱하기 miss penalty)
식을 하나씩 자세히 보자.
우선 1번식에서 cpu cycles는 그냥 program을 실행하며 소모되는 cycle 개수이고, Memory stall clock cycles는 memory system을 기다리며 소모되는 cycle 개수이다. memory에 대해 작업하는 경우는 hit인 경우와 miss인 경우 두가지로 나뉜다.
hit을 처리하는 cycle은 보통 cpu execution cycles에 포함된다고 본다. 그래서 Memory stall clock cycles은 miss일때를 중점으로 본다. (2)번 식을 보면 miss에 대해서만 고려한다.
하지만 hit time도 확실히 cache performance에 영향을 주는 요소이긴하므로, 위처럼 하지 않고 AMAT이라는 식을 사용해 hit도 따로 빼서 계산하기도 한다.(hit time으로 인한 효과를 뭉뚱그려서 보지 않고 아예 따로 확실하게 보기위해 빼서 본다는 말인듯?)
문제풀때...
Cache가 구분 돼있다면, 위 식을 Cache별로 구분해서 각각에 따로 적용해야한다.(L1_i에대해 위 식으로 penalty 계산하고, L1_d에 대해서는 또 따로 위 식으로 penalty 계산하라는 말)
예를들어 ppt p.17에 문제를 보면 instruction data와 일반 data에 대해 cache를 따로 정의한다.
이 경우 i Cache에 접근할때는 위 식의 Mem Access 횟수를 IC로 보고 계산해야하고, d Cache에 접근할때는 Mem Access 횟수를 IC 중에서 ld나 sd 같은 애들이 나오는 횟수로 보고 계산해야한다. (miss rate도 따로 정의돼있으니 당연히 따로 적용하면 됨)
따라서 instruction data는 instruction 개수에서 곧바로 miss rate와 miss penalty를 곱하면 되고,
일반 data는 instruction 개수에 data에 접근을 하는 퍼센트(경우)를 곱한 후, miss rate와 miss penalty를 곱해야한다. 왜냐하면 일반 data에 접근하는 경우엔, 메모리에 접근하는 instruction들을 뽑아와야 하기 때문이다.
마지막으로 위 둘과 idel cycle을 더해주면 된다.
(instruction도 일단은 메모리에서 읽어와야하는 데이터일 뿐이라는 것도 잊지말자.)
(책 p.415에는 위 예제에서 그냥 CPI만 증가했을때 어떻게 되는지 간단하게 보여준다.)
※ 그리고 miss penalty라는 것은 정상적으로 진행되다가 miss가 발생했을때, MM까지 갔다오고 다시 그걸 processor에 올려야하는, "추가로 소모되는 비용"이다.
그러니 memory stall cycle 같은거를 합쳐서 계산할때 miss가 나는 intructions 개수와 나지않는 instructions 개수를 따로 생각하거나 할 필요가 없다.
miss가 나든 안나든 전체 instructions에 대해서 계산하고, 그 중 miss가 발생하는 경우에 대해서 단순하게 추가해주기만 하면 된다. memory stall cycle같은 miss penalty는 miss로 인해서 발생하는 추가 비용이니까...
> Set associative Cache
지금까지 direct-mapped cache를 기준으로 알아봤는데, 얘는 사실 Set associative Cache의 한 종류이다.
Set associative Cache란, 쉽게 생각해서 direct-mapped cache를 옆으로 n개 이어붙였다고 생각하면 된다.
기존에 배운 direct-mapped cache는 MM의 특정 주소의 값이 cache에 올라갈 수 있는 자리가 하나 뿐이었다면,
Set associative cache에선 본인 자리가 n개만큼 더 늘어난다. (hash table에서 slot을 늘려준 셈)
이름에서 볼 수 있듯이 direct-mapped cache는 cache의 지정 공간과 곧바로 연결되지만, set associative cache는 지정 set과 연결된다. 그 set 내부라면 어디든 저장될 수 있는 것이다. direct-mapped cache에 비해 좀 널널해진 셈.
direct-mapped cahce는 그 set의 크기가 1이어서 특정 index를 가지는 주소의 값을 하나밖에 담지 못했지만, n-way set associative cache는 특정 index를 가지는 주소의 값을 n개 담을 수 있다.
index로 8비트가 사용된다. direct-mapped cache였다면 index 값이 같은 경우 둘 다 저장될 수 없었지만, 여기선 4개까지 수용할 수 있다.
모든 block은 어떤 주소인지 알아야하므로 당연히 tag와 valid도 모두 각각 가진다. direct-mapped cache를 이어붙인 것에 밑에 H/W가 더 추가된 꼴이다.
miss가 나서 MM의 값을 올려야하는데 해당 set이 이미 꽉차있다면,
LRU(least recently used)라는 방법에 근거해 후보 중 오래된 데이터를 replace시킨다.
한 Set의 크기를 n이라고 할때 이를 associativity라고 한다. 그리고 그 cache를 n-way associative cache라고 한다.
즉, direct-mapped cache는 사실 1-way associative cache인 것이다.
MM의 데이터가 들어갈 수 있는 cache의 영역에 딱히 제한을 두지 않기도 하는데, 그런 cache를 full associative cache라고 한다.
full associative cache는 n-way associative cache이다. 여기서 n은 block 개수와 같다. 즉 index에 따라 값이 들어갈 자리가 정해지는게 아니라 어떤 값이든 어느 위치라도 올 수 있다는 의미이다.
아래 그림은 cache size가 고정된 경우 Set 크기에 따라 associative cache가 어떻게 생겼는지 간단하게 도식화한 것이다.
Cache size(data size)를 고정하고 way를 2배로 늘리면 index bit가 하나 줄고 tag bit가 하나씩 늘어난다.
관련 계산해보는 예제는 책 p.423 참고
<Set 크기 증감에 따른 장단점>
Direct-mapped Cache의 단점은 공간 활용이 안된다는 것이다.
같은 크기의 공간에서 Set 크기를 더 늘려준다면(대신 index 크기가 줄어들겠지), hit이 더 잘된다.
Set 크기를 1에서 2로 늘리면 index 개수가 반토막이 난다. 그럼 한 index에 들어갈 수 있는 데이터 개수도 2개가 되지만, index가 1-bit 줄어들기때문에 거기에 들어갈 수 있는 후보도 2배로 늘어난다는 소리다. 공간이 두배로 늘더라도 들어올 수 있는 놈들도 두배로 늘어버리면 miss rate와는 관계 없어보이는데 왜 hit이 더 잘될까?(miss rate가 줄어들까?)
→ 쉽게 극단적인 두 놈(Direct-mapped와 full-associative)을 비교해보자. 각 cache가 data를 총 4개 담을 수 있다고해보자, 그럼 full-associative의 경우 data를 4개 이상 진행하기 전까진 기존 data를 쫓아내지 않고 꽉꽉 채워넣는다.
하지만 Direct-mapped의 경우 data가 2개만 진행됐을때도 기존 data를 쫓아내고 그 위에 덮어써야 할 수도 있다. 물론 잘 넣어주면 4개 다 채울 수도 있겠지만, 확률상 full-associative에 비해 빈 공간을 안쓰고 놔둘 확률이 높다.
표면상 같은 용량의 Cache여도 full-associative가 더 많은 데이터를 수용하고 있을 확률이 높으니, 그리고 temporal locality를 더 잘 지키게되니 당연히 Miss rate도 더 작다.
하지만 Set의 크기를 늘리면 단점이 있다. 위 그림을 보면 알겠지만, 1-way(direct-mapped) 일때와 비교하면 빨간색과 초록색 부분이 추가된다.
Hit 판단을 할때 1-way라면 더 찾아볼 필요가 없지만, k-way라면 k개를 모두 비교해보고 hit 여부를 판단해야한다.
그래서 associativity가 늘어날 수록 Hit time이 증가하고, H/W cost 또한 증가한다.
(참고로 위 회로에서 빨간색으로 표시되지 않은 tag와 비교하는 부분은 병렬로 처리되므로 hit-time을 늘리는데 기여하지 않는다.)
정리하자면
모든 cache는 set associative cache라는 큰 범주에 들어간다. associativity(set의 크기)를 어떻게 잡느냐에 따라 direct-mapped가 될 수도 있고, full associative가 될 수도 있다.
Set의 크기를 줄여서 direct-mapped 쪽으로 갈 수록, miss rate가 높아지지만 HW/cost와 hit time이 감소하고,
Set의 크기를 늘려서 full associative 쪽으로 갈 수록, miss rate가 낮아지지만 H/w cost와 hit time은 증가한다.
지금까지본 각 Cache 성능 측정 요소에 영향을 주는 원인 간단하게 정리 (원인 외 나머지 요소는 같다고 가정)
hit time : associativity
miss rate : associativity, block size
miss penalty : block size, bandwidth, using multiLevel cache
Multilevel Caches
여러 level의 caches를 사용하면 Miss penalty가 줄어든다. Cache의 Level을 추가하면 전체 Cache 크기를 봤을때 그 전체 크기가 증가한 것이다. 그러니 miss가 났을때 하위 level의 memory로 가야한다고할때 멀리있는 MM이 아니라 가까이있는 cache에서 처리될 확률이 더 높기 때문에 miss penalty 자체가 줄어든다. 멀리있는 MM으로 가야하는 penalty보다는 Cache들 사이에서 처리되는 penalty가 당연히 더 작다는 말이다.
프로세서뿐만 아니라, cache 입장에서도 가까운 거리에 locality 원리를 활용한 공간이 생기는 것이니 전체적으로 더 빨라진다.(cache가 하나만 추가됐을때 빨라지는 원리도 locality 때문이었음/processor가 locality 원리를 이용해서 더 빨라졌으니, cache도 locality 원리를 이용하면 당연히 더 빨라진다.)
(요약하자면, locality의 이점을 중간에 한번 더 취하고 + 추가된 cache 기준 안쪽 cache들의 miss penalty도 줄일 수 있음)
L1이 CPU에 가장 가까운 Cache이고, L3는 Main Memory와 가장 가까운 Cache이다.
(L4는 교수님께서 본적 없다고 하심. 성능이 늘긴 하지만 H/W cost 등까지 고려해서 득실따졌을때 애매하나봄.)
L1~L3(shared) 모두 Cache이므로 SRAM을 기반으로하는건 맞지만, 종류에 따라 특성이 다르다.
L1 : processor와 가장 가까우니 작고 빠른게 좋다. hit time도 좋아야한다. direct-mapped cache가 적합하다.
L3 : MM과 가장 가까우니 큰게 좋다. 속도의 중요성은 L1보다 좀 떨어진다. MM으로 넘어가지 않게 하는게 중요하기때문에 좀 느려도 miss rate를 줄이는 편이 좋기때문에 full associative cache가 적합하다.
(아마 Cache 크기 자체도 L3로 갈수록 좀 더 크게 만들거임)
Cache의 장점을 살려 최적화를 하는 기법도 있다. 이를 책에서 blocked algorithms이라고 소개한다.(p.425)
목표는 cache에 한번 올려둔 data들을 replace되기전에 최대한 활용하는 것이다. 그렇게함으로써 temporal locality를 증가시켜 cache miss를 개선한다.
아무 생각없이 캐시 올라와있는거 쓰고 다시 다른거 쓰다가 다시 불러오면 일을 두배로 하게되니, 캐시에 올라와있을때에 최대한 활용하는 것을 목표로 하는 방법이다.
> Multilevel Cache 성능 계산 예제
Cache 성능은 보통 총 소모되는 clock cycles 개수 혹은 CPI로 계산한다.(어차피 나머지는 고정/위의 계산문제에서도 그랬음)
(근데 CPI로 문제 나오더라도 IC를 N으로 잡고 그냥 clock cycles 개수로 생각하는게 좀 더 직관적이긴 한듯)
(아래 문제는, 위에서 봤던 문제 처럼 instruction이랑 일반 data 나누지 않고 그냥 같이 보는듯. 이렇게까지 파고들 필욘 없지만,,, 아래 문제에서 inst.가져오는거랑 data.가져오는거랑 두번에 걸쳐서 miss rate를 2%씩 적용하는게 아니라, "instruction 당 miss rate"라고 했으니, 그 miss rate에 inst 가져오는거랑 data (가져와야한다면) 가져오는거랑 다 포함된다는 의미인듯,, miss rate라는게 코드에 따라 달라질 수 있는 것인데, 여기선 해당 코드를 썼을때 miss rate를 친절하게 알려주니까 그냥 그렇게 하면 된다. 위 문제에선 세부적으로 알려줘서 우리가 계산을 했지만, 여기선 그냥 inst.당 내부적으로 처리하는거 다 고려한 miss rate를 general하게 알려준 셈. 근데 이렇게까지 알 필욘 없고 그냥 문제유형 두개뿐인데 그거에 맞게 잘 풀자)
차근차근보자. IC는 N이라고 가정한다.
L1밖에 없는 경우)
L1에서 모두 hit이라면 CPI는 1이다. 즉 miss가 없다면 총 소모 cycle 개수는 N이다.
miss penalty는 100ns이다. 이를 clock cycle 개수로 바꿔보면, clock rate가 4GHz이므로 400cycle이 miss penalty임을 알 수 있다.
miss penalty가 발생할 확률은 2%이니, miss로 인해 추가로 소모되는 cycle 수는 Nx0.02x400 개이다. 따라서 Cache가 하나뿐일때 총 소모 cycles은 N+8N = 9N이다.
위에서도 말했지만, miss penalty는 "추가로" 발생하는 비용이다.(애초에 문제에서 그런 "추가 비용"을 miss penalty로 골라야한다.) hit인줄 알고 cache에 접근해보고, 그 중에 2%가 miss가 나는 것이니까 N개의 instructions을 98퍼센트는 hit으로 생각하고 2퍼센트는 miss penalty로 계산하는게 아니라, 일반적으로 진행된다고 가정하고 거기에 miss penalty를 더해주기만 하면 된다.
L2가 추가된 경우)
마찬가지로 L1에서 모두 hit이라면 CPI는 1이다. 즉, miss가 없다면 총 소모 cycle 개수는 N이다.
이번엔 L2가 추가됐는데, L2까지 접근하는데 5ns가 걸린다고한다. 즉, L2까지 가야하는 총 miss penalty는 20cycles이다.(4GHz이니까)
그리고 L2까지 가야할 확률은 위와 같이 총 2%이다.
이번엔 MM으로 가는 경우를 생각해보자. L2에서도 miss가 나서 MM으로 가는 miss penalty(추가비용)는 그대로 400 cycles이고, MM까지 갈 확률은 0.5%이다.
그럼 이제, 위에서 말했듯이 miss penalty는 기존 cycles 수에 "누적"되는 것이므로, 단순하게 더하면 된다.
instructions N개의 2% "중에서" 0.5%(즉, 0.02x0.005)를 봐야하지않나 생각할 수도 있는데, 아니다. 문제를 보면 L2가 추가됨으로써 MM으로 가는 miss rate가 0.5%로 줄었다고 했다. "L2에서의 miss rate"라고 했다면 Nx0.02x0.005가 맞겠지만, 여기서 L2에서의 miss rate는 따로 말해주지 않는다.
즉 문제를 좀 자세하게 해석해보면,,, L2 추가전을 보면 L1 miss rate가 2%라고 했으니 MM 접근하는 것도 2%라는 말이었다. 그런데 L2가 추가되며 MM 접근 miss rate가 2%로 줄어든다고 한다. 이는 CPU<->L1 에서 발생하는 miss 중 2%가 MM로 가는 경우였는데, "바로 그 둘"사이의 miss 중"에서 MM 접근하는 경우가 0.5%로 줄었다는 의미로 보는게 맞는 것 같다.("원래는 IC N개중에 MM까지 가는 miss rate가 2%였는데 그게 0.5%로 줄었어.", 딱 요정도만 생각하고 뭐 너무 고민안해도될듯)
그리고 처음부터 보면, 총 N개의 inst 중에서 2%가 L1에서 miss가 나는 것이니, "일단은 무조건" L2로 가는 확률이 2%라는 말이다. 여기서 L2를 거쳐서 또 miss가 나서 MM으로 가는 경우도 같이 계산된다. ppt 보면 따로 계산할 수도 있다.
그리고 다시 전체 N개 instructions에서 0.5%가 MM으로 간다고 한다. 하지만 우리는 MM까지 가야하는 miss 중에서 L2까지 가야하는 penalty는 이미 위에서 계산을 했다.
그러니 0.5%에 대해서 MM으로 가는 경우만 penalty를 계산해서 단순하게 추가해주기만 하면 된다.
★결국 핵심은, miss penalty를 잘 잡고, access time이 (processor에서 접근하는게아니라) 이전 단계에서 접근하는 시간이라는 것을 알고, miss rate를 잘 파악하는 것이다.
기본은 결국 단계별로 추가비용을 확인해서 그런 추가비용이 발생할 확률을 곱해 누적시켜주는 것이다.(ppt 그림 보면서 생각해보면 이해 잘 됨)
그래서 N + 20x0.02xN + 400x0.005xN = 3.4N이다.
따라서 L2가 추가됨으로써 9N/3.4N = 약 2.6배(소숫점아래 둘째자리에서 반올림) 성능이 향상됐다.
근데 ppt 두번째 식이 이해가 훨씬 잘되는거 같음
"해당 memory까지 가는데 걸리는 cycles" x "해당 memory까지만 갈 확률"을 각 memory(cache) 별로 구해줘서 누적합을 구함.
첫번째 식들은 잘 보면, 앞쪽 level에서 뒤로 넘어가는 경우도 모두 포함시켜서 계산할 뿐이다.
<용어 주의>
block과 line은 같은 의미이다.
: 즉, line size라고 하면 한 entity에서 저장하는 데이터 크기를 말한다.
보통은 cache size라고하면 data 영역들의 크기만을 말한다. 문맥에 따라 모든 bit수 다 합친 전체 cache size를 말하기도한다.
ex) "The cache size is 2^n blocks"
: data 영역만의 크기가 2^n blocks란 뜻이다. 윗쪽에서도 말했지만, block은 cache가 처리하는 기본 데이터 단위이다. 즉, block(line)은 cache가 읽고 쓰는 기본 단위이므로, 시각화해서 생각해보자면 아래 그림에서 파란색으로 색칠한 부분의 크기를 말한다. block이라고는 말하지만 결국은 n-byte나 n-word 형식이다.
즉, cache size가 2^n blocks란 것은, direct-mapped cache라면, 간단하게 index가 2^n개(==index 표현비트가 n개)라고 말하는 것이다. direct-mapped cache로 보지 않고 제너럴하게 생각한다면 그냥 [V-Tag-Data]로 구성된 entity가 총 2^n개 있다는 말이다.
'수업 > Computer Architecture' 카테고리의 다른 글
| [Computer Architecture] Processor - 2 (0) | 2022.12.15 |
|---|---|
| [Computer Architecture] Processor - 1 (0) | 2022.11.08 |
| [Computer Architecture] Arithmetic for Computers(2) (2) | 2022.10.18 |
| [Computer Architecture] Arithmetic for Computers(1) (0) | 2022.10.13 |
| Language of the Computer (5) | 2022.09.14 |