본 게시글은
서울대학교 데이터사이언스대학원 정형수 교수님의
데이터사이언스 응용을 위한 컴퓨팅 시스템 강의를
학습을 목적으로 재구성하였습니다
중간고사가 끝나서 뒤늦게 허겁지겁 정리해보는
이전에 배운 수업내용
이번 수업 내용은 메모리 계층 구조에 관한 내용인데
굉장히 굉장히 중요한 내용이고
시스템 프로그래밍의 꽃과도 같은 내용이라고 한다
오늘 배울 내용은 다음과 같다고 한다
이전 시간에 배운 내용을 간단하게 복습해보자
메모리에 접근해서 데이터를 다루는 명령어는
read와 write가 있었다
위와 같은 어셈블리 명령어의 경우
(%rsp)라고 하면
rsp가 가리키고 있는 것을
메모리 address로 해석해서 그곳에 접근했다
CPU에서 메인 로직을 담당하는 부분은 ALU이다
register set 전체가 register file이고
여기에 필요한 데이터가 올라가있어야하기 때문에
데이터를 읽고 쓰고 하려면
main memory로 가야하는데 이를
memory controller를 통해서 수행해준다
cpu가 필요로 하는 데이터를 read하거나 write할 때
이걸 메모리 쪽에다가 보내줘야하는데
memory controller는 이때
주소(address line), 데이터(data line), 연산자(op)
딱 이렇게 3개를 다룬다
memory controller와 main memory는
memory bus에 연결되어있다
main memory부터 memory bus를 통해서
memory controller가 받아서
register file까지 올려주게 된다
c++에 atomic이라는 선언자가 있는데
이를 선언하면 변수가 atomic으로 받아들여진다
이게 뭘 해주는거냐하면
뭔갈 하나 작업할 때 작업하고 남겨진 데이터를
나 혼자만 control할 수 있게 해주는 것이다
중간에 다른 누군가가 read나 write할 수 없게
그걸 하드웨어에게 부탁하게하는 선언자이다
그래서 이걸 사용하게 되면
assembly code에 lock이라는 op가 하나 더 붙는다
main memory에 써야할때는 거꾸로 간다
컴퓨터를 하다보면 정말 많이 들어보는
RAM에 대해서 정말 간단하게 한 번 알아보자
register file은 SRAM을 사용하고
main memory는 DRAM을 사용한다
SRAM이 가장 빠른 메모리이며
가장 비싼 메모리이기도 하다
SRAM과 DRAM의 구조이다
DRAM은 정보를 저장하기 위해서
트랜지스터 1개와 capacitor 1개가 필요하다
그런데 계속해서 clock을 refresh 시켜줘야해서
전력을 많이 소모한다
SRAM은 6개의 트랜지스터를 필요로 하는데
refresh 해줄 필요가 없고 전력을 계속 hold할 수 있다는 장점이 있다
하지만 circuit 자체가 복잡하다
SRAM과 DRAM의 차이는 이렇다
cost가 무려 100배 차이가 나서
SRAM의 성능이 좋다고 마음대로 가져다 쓸 수가 없다
ALU에 가까이 있는게 가장 작고 가장 빠르고 가장 비싸다
그리고 ALU로부터 멀어질수록 싸고 용량이 많아진다
그래서 메모리 계층구조는 피라미드 형태로 생겨있다
이제 Locality에 대해서 알아보자
CPU와 다른 저장장치의 gap에 대해서 알아보자
이 자료가 2015년 자료라 좀 옛날 자료인데
이 trend가 크게 변하지는 않았다고 한다
하지만 SSD는 이후로 열심히 내려오고 있고
DRAM과 CPU는 계속해서 제자리를 유지하고있다고 한다
이렇게 CPU와 다른 저장장치간의 간극이 매우 큰데
이걸 줄여줄 수 있게 하는 중요한 원칙이 바로
Locality이다
사실 이 Locality는 굉장히 중요하고 유명한 개념이며
메모리 구조에서 반드시 알아야하는 개념이다
아무튼 우리나라말로는 지역성이라고 하는
locality는 2가지 원칙이 있다
1) temporal locality
- 한 번 접근한 데이터는 빠른 시간 내에
또 접근하는 경향이 있다
- 시간 지역성
2) spatial locality
- 한 번 접근한 데이터는 그 주변의 데이터에도
계속 접근하는 경향이 있다
- 공간 지역성
이는 데이터가 내포한 성질과도 같은 것이다
따라서 우리가 미래는 알 수 없으니
past history를 보고 앞으로 어떻게 접근할지를
잘 예측하는 것이 cache 성능의 가장 큰 핵심이 된다
위 코드 예시를 한 번 살펴보자
array에서 한 칸씩 건너뛰면서 access하는 구조이다
one word size로 stride하는 아주 간단한 코드인데
위 경우 spatial locality를 만족시키는 사례이다
왜냐하면 a라는 array에
0부터 순차적으로 접근하고 있기 때문이다
또한 sum의 입장에서는 temporal locality도 만족시킨다
왜나하면 sum은 이번에도 다음번에도
계속 방문하기 때문이다
우리가 c나 c++ 실행을 위해 컴파일을 하면
gcc -os라는 옵션을 줄 수 있는데
이걸 하면 코드 사이즈가 굉장히 minimize된다
그러면 이걸 왜 하냐?
사이즈가 작으면 코드가 icache에 올라갈 확률이 높아지기 때문이다
데이터와 Instruction마다 패턴이 다르고
Working set 사이즈가 다르다
이전만 하더라도 이걸 어떻게하면
효율적으로 나눠서 저장하지에 대한
연구가 굉장히 활발하게 진행되었으나
지금은 그냥 아예 분리해서 fix해 버렸다
따라서 instruction은 icache에
data는 dcache에 무조건 저장하게 되어있다
하지만 일부는 소프트웨어가 이걸 관리할 수 있도록
제어권을 넘긴 아키텍처 회사들도 존재한다고 한다
locality를 만족시키는게 얼마나 중요한지
위 예시를 통해서 한 번 살펴보자
사실 이건 이번 수업 가장 첫 강의에서 다뤘던 내용인데
위 코드에서 for문의 i와 j의 순서를 바꿨을 때
결과값은 똑같지만 성능 차이가 어느 수준으로 나는지와
그래서 locality와 cache의 성능이
프로그래밍에서 얼마나 중요한지 단적으로 알려주는 사례이다
여기서 a는 2차원 배열의 형태이고
i와 j의 순서대로 차례차례 a[i][j]와 같은 형태로
배열에 접근하고 있다
여기서 a[j][i]와 같이 변경해도
logical한 코드의 답은 전혀 바뀌지 않는다
하지만 Locality로 인해서 수행속도에는
어마어마한 차이가 있다
a[i][j]와 같은 순서로 접근하면
위 slide의 배열처럼 i에 묶인 j를 순서대로 쭈욱 가져오게 된다
그럼 spatial locality를 충족시키게 되고
이렇게 되면 cache에 데이터가 자연스럽게 올라가고
memory controller가 미리 near by 데이터를 캐시에 올려놓는다
그럼 메모리 access를 할 필요가 없이
바로 cache로 access하고 cache hit이 된다
그럼 아까 말했듯이 여기서
j를 먼저 돌리고 그 다음 i를 돌린다고 해보자
i가 먼저 바뀌면
stride가 n씩되어서 계속 n만큼 건너서 뛰게 된다
이렇게 되면 spatial locality와
정반대로 수행하게 되고
cache miss가 계속해서 발생하기 때문에
속도가 굉장히 많이 차이나게 된다
그렇다면 이렇게 3차원을 다 더하는 코드에서는
접근 순서를 어떻게 해주면 좋을까?
k를 가장 밖으로 빼고
그 다음 i, j의 순서로 해주는것이 가장 좋다
이제 메모리 계층구조에 대해서 살펴보자
앞에서도 계속 강조됐던 내용이지만
메모리는 속도와 비용 용량에 각각 차이가 있다
이것이 메모리 계층구조를 단적으로 나타내는
피라미드 형태이다
아래로 내려갈수록 Linear가 아니고
exponential하게 내려온다고 한다
따라서 이러한 성능 차이가 최대한 안났으면
좋겠다는 욕망에서 cache라는 것을 두었다
큰 메모리로 접근할수록 시간이 오래 걸리기 때문에
큰 메모리에 접근할 일을 최소화 시키자는 것이다
따라서 cache에는 한 번 접근한 데이터가 있으면
계속 cache 시켜놓아
프로그램의 성능을 향상시키자는 것이다
cache는 보통 read의 용도로만 쓴다고 알고있지만
사실 read, write 2가지의 용도로 사용한다
read는 우리가 아는대로
데이터 혹은 instruction을 메인메모리 접근없이
읽고싶을 때 사용하고
write의 경우 실제 메모리에 write하지 않았지만
일단 메인메모리에 쓴 것처럼(?) 한 다음
cache에 모아놨다가 나중에 일괄 write를 하게 되는데
이걸 write buffer라고 부른다
우리가 앞에서 배웠듯이
CPU는 instruction을 실행할 때
out of order(ooo)로 수행을 시킨다
이를 위해서 store buffer에 모든 것을 저장해놓고
순서에 관계없이 저장 시키다가
나중에 이걸 가장 마지막에 in order로 다시 복원시키면서
store buffer에 저장된 데이터를 다 날려버린다
그래서 cache는 이런 buffer의 역할도 함께 하기 때문에
buffer cache라고도 불린다
하지만 CPU에게는 buffer의 역할보다는
cache의 역할이 매우 중요하며
CPU가 필요로 하는 데이터가 그때 그때 찾을 수 있도록
만들어주는 것이 cache의 가장 중요한 목적이다
이러한 cache 메모리의 특징을 잘 살펴보자
우리가 메인 메모리는 얼만큼 쓰고있는지
컴퓨터 내부에서 확인할 수 있지만
cache는 확인이 불가능하다
그리고 캐시는 주로 하드웨어가 관리한다
이게 cache memory의 기본 컨셉이다
아래에 있는 메모리에 있는 데이터 중에서
locality잘 보이는 것들을
cache에 담아둬서 필요로 할 때
memory까지 가지않고도 access할 수 있게 해주는 것이다
cache memory의 가장 중요한 성능 matrix는
hiteration이라고 부르는데
내가 필요로한 데이터가 cache 메모리에 제대로 담겨있는 정도를
정량적으로 측정한 것이다
따라서 Locality를 잘 보이는 데이터를 담는 것이 중요하다
필요로 하는 데이터가 cache에 있는 것을
Hit이라고 부른다
CPU에서 address line 14번을 요청했다
위 경우 cache에 14가 있으므로
이런 경우 hit!이 된 것이다
그 다음에 만약 CPU가
address line 12를 달라고 했다 가정해보자
그런데 cache에 12가 없어서
main memory에서 가져왔다
이렇게 되는 경우를 cache miss라고 부른다
cache miss는 cache를 사용안하는 것보다 못하다
왜냐하면 cache를 방문하지 않고
그냥 바로 main memory로 갔어도 되는데
cache에 방문했다가 검사하고 없어서
다시 main memory까지 접근하면서
필요없는 시간을 또 낭비하게 된 것이기 때문이다
이것이 바로 miss penalty이고
이것이 우리가 작성한 프로그램에서
cache를 잘 hit하는게 중요한 이유이다
따라서 뛰어난 연구자들이
보통 어떤 경우에 cache miss가 나는지 살펴보았는데
보통 위의 3가지 경우로 정리된다고 한다
3가지 경우가 전부 C로 시작해서
이를 3C라고 하는데
3 types of cache misses라고 한다
1) cold miss
- 한 번도 부른 적이 없는 데이터를 불렀을 때
2) capacity miss
- cache 용량 부족으로 어쩔 수 없이
부르지 못한 데이터일 때
3) conflict
- 원래는 저장되어 있었지만 캐시 매핑 정책으로
덮어써져서 해당 데이터가 날라갔을 때
1, 2번은 그렇다치자
3번은 대체 무슨 말일까?
이걸 알아보기위해서 다음시간부터는
cache mapping 정책에 대해서 본격적으로 살펴본다
CPU와 cache가 실제 어떻게 구성되어있는지 살펴보자
각 아키텍처마다 저런식으로 구성이 되어있는데
L3를 모든 core에서 공평하게 접근할 수 있도록
보통 설계한다
core i7의 경우를 살펴보면
L1, L2를 우선적으로 갔는데 필요한 데이터가 없다
그럼 L3를 검사하는데 그런데도 없으면
memory controller를 통해서 wire를 타고
main memory로 접근해서 해당 데이터를 가져오게 된다
그럼 아까전에 conflict miss가 캐시 데이터의
매핑 정책때문에 생긴다고 했는데
캐시 데이터 매핑 정책에는 어떤 것들이 있는지 살펴보자
이번 시간에는 여기까지만 살짝 배우고
다음시간에 더 본격적으로 알아본다
우선 캐시데이터 매핑 정책에는
direct-mapped cache가 있고
set-associative cache가 있는데
지금 살펴볼건 set-associative cache이다
cache는 hit되는 것도 중요하지만
cache가 hit되도록 데이터를 잘 담는 것도 중요하다
캐시 매핑 정책은 cache에 데이터를
어떻게 잘 담을까에 대한 내용이다
위 ppt에서 용어에 대해 간단하게 살펴보자
위 도식은 cache 메모리의 구조인데
한 block을 line이라고 부르고
그 line들이 모이면 하나의 set이 된다
line의 수를 E로 표현하는데
E=4이면 한개의 set에 4개의 line이 있는 것이다
그런데 만약 line이 1개인 경우가 있는데
이게 direct-mapped cache이다
S는 이러한 E개의 line이 모인 set의 개수인데
set이 많아지면 conflict miss의 확률이 훨씬 줄지만
비용이 많이 들기 때문에
적당한 조율이 필요해진다
그렇다면 위와 같은 구조를 바탕으로
CPU가 address line을 던지면
cache는 어떻게 데이터를 찾을까?
CPU의 address는 tag, set index, data offset
이렇게 3개의 정보를 담아온다
이렇게 CPU에서 address line이 날라오면
우선 set index로 몇 번째 set인지를 검색한다
그럼 해당 set에서 line들을 대상으로
가장 처음의 valid bit을 통해 해당 line이 유효한지 확인하고,
그 후에는 line의 tag와 CPU address line의 tag와 동일한지 확인한다
그럼 만약 set이 64개이면
set index는 2의 8제곱이 64이므로
8비트만 있으면 된다
이런식으로 어떤 set인지를 표기한다
그런데 여기서 set이라는 개념이 아예 없고
모든 line을 전체 돌면서 tag를 비교하면서
데이터를 찾게되면 이건
full associative cache가 된다
이런 방식으로 캐시를 매핑하면
자유롭게 저장이 가능하므로
conflict miss가 굉장히 적어지지만
하드웨어적으로 구현이 굉장히 복잡하고 느려질 수 있다
이번 시간에 배운 내용은 여기까지..!
다음도 cache memory 구조에 대해
더 자세하게 배운다