기말

3

나눗셈 : dividend를 divisor로 나눠서 quotient와 remainder를 얻어낸다. 이때 곱셈과 비슷하게 shift와 sub를 통해서 하는데, divisor는 왼쪽에 딱붙여놓고 하위를 0으로 채우고 시작한다. 매 반복마다 몫이 발생하면 자리를 옮겨줘야하므로 quotient는 left shift, divisor는 모든 자리에대해 연산을 시작해야하고 왼쪽에 붙어서 시작했기 때문에 right shift 해주면서 반복한다 ← 사람이 하는 계산이 이렇다는게 아니라 실제 기계에서 하는게 이렇게 작동한다는 의미임..!

division flow char dividend(remainder) 에서 오른쪽을 0으로 채운 divisor값으로 빼고 그 결과를 다시 remainder에 저장한다. 몫값은 왼쪽 shift를 1회 진행해 새로운 값(몫)이 쓰여질 공간을 만드는데, 만약 remainder가 0보다 작아졌다면 remainder를 빼기 전으로 원상복구를 하고 quotient의 새 비트로 0을준다. 그렇지 않다면 뺀 값을 고냥 remainder로 남겨놓고 quotient는 1을 준다. divisor를 right shift 해준다. 이걸 65번 반복해서 모든 비트에 대해 적용한다.

초기 나눗셈 회로 : divisor는 왼쪽에 붙어있는채로 시작(오른쪽은 0으로 채워져있다), 매 반복마다 right shift. quotient는 매 반복마다 left shift. remainder에서 divisor를 빼고 판별해서 몫을 넣어주고 반복. 반복때 shift.

n자리연산이면 연산을 n+1번 한다 0111 / 0010 0000 / 0010 0000 / 1110 0111 → 연산
0000 / 0010 0000 / 0000 0111 → quotient 수정 0000 / 0001 0000 / 0000 0111 → divisor 수정 —————————————- 0000 / 0001 0000 / 1111 0111 0000 / 0001 0000 / 0000 0111 0000 / 0000 1000 / 0000 0111 —————————————- 0000 / 0000 1000 / 1111 1111 0000 / 0000 1000 / 0000 0111 0000 / 0000 0100 / 0000 0111 —————————————- 0000 / 0000 0100 / 0000 0011 0001 / 0000 0100 / 0000 0011 0001 / 0000 0010 / 0000 0011 —————————————- 0001 / 0000 0010 / 0000 0011 0011 / 0000 0010 / 0000 0001 0011 / 0000 0001 / 0000 0001

개선된 버전의 나눗셈 회로 : reaminder는 연산할수록 줄어들것이고 몫은 연산할수록 증가한다. 따라서 remainder 레지스터를 공유함으로써 multiplier회로와 유사한 구조를 만들어낼 수 있다. «어케했누씨발년아;

빠른버젼 : 곱셈처럼 더 빠르게 만들 수 없다 : 각 step결과의 부호를 알아야 뺄지 말지를 처리할 수 있음. adder처럼 그런거 고려할 필요없이 단순하게 다 더해버리면 되는 문제가 아니기때문.

부호 나눗셈 : 산술 나눗셈에서는 나머지를 무조건 양수로 만들어줘야한다. 근데 그걸 그대로 컴퓨터 회로로 옮기면 HW가 너무 복잡해진다. 그니까 그냥 음수 나머지를 허용해서 양수 나눗셈이랑 똑같이 처리해준다.

연산자를 모두 양수로 변환하고 각 부호를 기억해두고 그냥 나눗셈처럼 연산해준다. 몫의 부호는 두 operand의 부호가 같았다면 + 아니라면 -가 되고 나머지의 부호는 dividend의 부호를 따라가게 된다. ex) 7 / -2 = 몫 -3, 나머지 1 -7 / -2 = 몫 3, 나머지 -1 7 / 2 = 몫 3, 나머지 1 -7 / 2 = 몫 -3, 나머지 -1

RISC-V에서의 나누기 instruction : 일반 R-format이다. 곱셈도 그렇고 R-format으로 동일하게 처리하는데서 오는 이점이 많다. div는 몫을, rem은 나머지를 반환해준다. divu와 remu는 각각 div, rem의 unsigned값으로 반환해준다. 비정상적인 이벤트는 무시해버린다. overflow가 발생하거나 0으로 나누는 등의 다루기 어려운 문제가 발생하면 이는 HW적으로 해결하기는 어렵다. 따라서 SW에서 처리를 해준다.

Floating point

시프에서 다 했잖아 다알지?

매우 크거나 작은수는 정수 표현을 할 수 없으니 다른 표현을 사용해야한다. 그래서 나온게 플로팅포인트

1.xxxx * 2^y의 형식으로 표시하여서 매우작은수와 매우 큰수를 표현한다.

(-1)^s * ( 1 + fraction) X 2(exponent - bias)

float에서는 Exponent가 8비트 Fraction이 23비트 (1 + 8 + 23 = 32) bias = 127

double에서는 Exponent가 11비트 Fraction이 52비트 (1 + 11 + 52 = 64) bias = 1023

s : 음수이면 1, 짝수이면 0

fraction : 1.xx로 일단 1은 붙어있다고 가정하고 쓴다.

exp : 지수를 얼마나할건지, 근데 우리는 2의보수를 쓰지는 않을거다 그러니까 항상 양수가될 수 있게 bias를 더해준다. 8비트수는 256개를 표현할 수 있고 일반적으로이는 음수도 포함하니까 음수는 포함 안하게하려고 하는거임

플로팅포인트의 정규표현방식은 exp 000..0과 111..1은 사용하지 않는다. 그니까 기본적으로 0을 표현할 방법이 없다. 또 가장 작은 수랑 큰 수에도 제약이 있다. 00..1 이랑 11..0

대신 좋은점은 그냥 정수표현이랑 동일하게 비교할 수 있음 비트 나열된게 어쨋든 동일한 방식으로 생각해도 되게끔 동작함.

single precision : 대강 소수점 아래 6자리까지 표현 가능

double : precision : 대강 소수점 아래 16자리 까지 표현 가능

ex) -0.75 → 음수이므로 s = 1, 이진수로 0.11이므로 1.1 * 2^-1로 표현 가능하다. 즉 frac = 1.1, exp = -1

single precision : E = exp + bias이므로 -1 + 127 = 126 = 0111 1110 , M = 100…0(23bit) ⇒ 1(S) 0111 1110(E) 1000 0000 000(M) = 1011 1111 0100 0000 …. 0000

**double precision : E = -1 + 1023 = 1022 = 0111 1111 110, M = 100..0(52bit) ⇒ 1(S) 0111 1111 110(E) 100..0(M) = 1011 1111 1110 1000 0000 0000 …. 0000

비교의 우선순위가 되는 부호비트, 지수비트, 유효수비트 순으로 배치가된다. 앞서말했듯 비교에 큰 이득이된다.

역으로 바꿔보자면 (single precision) 1100 0000 1010 00…00

single precision : S = 1, E = 1000 0001, M = 0100 0000 …. 0000 → S = 1, E = 129 ⇒ exp = 2, frac = 1.01 ⇒ (-1)^1 * 1.01 * 2^2 = -101 = -5

오버플로우 : 지수부가 너무 커서 exponent field를 벗어나는 경우

언더플로우 : 0이 아닌 실수부가 너무작아서 표현이 불가능한 경우, 지수부의 값이 음수로 너무큰 경우

비정규화

exponent가 0인경우엔 frac의 거저주는 비트도 0으로 친다. 그럼 더 작은값을 표현하게된다. 만약 frac도 0이라면 기존엔 표현할 수 없던 0을 뜻하게된다. 이 값은 s에 따라 음 혹은 양의 0이된다.

exponent가 11…11인 경우엔 frac에 따라 값이 달라진다. frac이 0인경우 s에 따라 음 혹은 양의 무한대가 되고, frac이 0이 아닌경우엔 NaN즉, 숫자가 아니라는 표현이 된다.

실수표현의 연산은 곱셈이 오히려 덧셈보다 쉽다. 더할 때 지수가 큰 애한테 작은애를 allign해주어야한다. 어떻게하던 손실은 발생하는데 작은놈한테 맞추는거보단 큰놈한테 맞추는게 손실이 적다.

ex) (1.000 * 2^-1) + (-1.110 * 2^-2)

• 큰놈한테 정렬시킨다 ⇒ (1.000 * 2^-1) + (-0.111 * 2^-1)
• significand끼리 더한다 ⇒ 1.000 + (-0.111) = 0.001 ⇒ 0.001 * 2^-1
• 다시 정규화시킨다. 오버플로나 언더플로 생겼는지도 체크함 ⇒ 1.000 * 2^-4
• 필요하다면 값을 수정한다.

이런 더하기하드웨어를 만들기는 존나 복잡하다. 한클락안에는 못함

오히려 곱셈은 쉽다.

ex) 1.000 * 2^-1 * -1.110 * 2^-2

• 지수끼리 더한다 ⇒ -1 + -2 = -3 지수끼리 더한후에 biase는 한번만 더해줍시다.
• significand끼리 곱한다 ⇒ 1.000 * 1.110 = 1.110 * 2^-3
• 다시 정규화시킨다. 오버플로나 언더플로 생겼는지도 체크함
• 필요하다면 값을 수정한다.
• 부호를 결정한다 ⇒ 같은거끼리곱했으면 양, 다른거끼리곱했으면 음, 여기선 다른거니까 음 ⇒ -1.110 * 2^-3

플로팅 포인트 연산을 위해서는 그를 위해 분리된 32개의 레지스터가 존재한다. 기본적으로 더블 프레시전을 가지는데, 만약 싱글을 사용하면 하위 32비트만 사용하는 방식임.

따라서 로드와 스토어도 별도로 존재한다. fld, fsd, flw , fsw 로 나뉜다. 오직 실수를 위한 레지스터이고 실수를 위한 instruction임

따라서 실수 연산을 위한 instruction들도 따로있다. fadd.s, fsub.s, fmul.s, fdiv.s, fsqrt.s 등등..

얘네들은 무조건 f레지스터에서만 값을 가져올수있다구~

비교연산같은경우에는 위에서 언급했든 표현법은 달라도 1대1비교에 있어서 앞의 비트부터 뒤비트까지 동일한방식으로 훑어도됨. 따라서 회로는 동일하게 작동함. 그치만 instruction을 따로 둔 이유는 소스와 데스티네이션이 다른 레지스터이기때문임. 하드웨어적으론 동일하게 작동하게하고 instruction단에서 분리해놓은 것

4

7개의 인스트럭션을 다룬다. sd, ld, add, sub, and, or, beq

모든 인스트럭션의 공통점은 일단 PC에가서 다음 instruction주소를 읽어야 한다는거랑, 버리던 어쩌던 일단 소스레지스터 두개를 읽어온다는것이다. ← 쓰든 안쓰든 일단 읽어오도록 설계되어있다.

이렇게 공통적인 작업이 끝나면 opcode를 기반으로 뭘해야할지를 분석하고 ALU가 그에알맞게 연산작업을 하는거.

기본적으로 PC는 수행뒤 다음 작업을 수행하게 되어있다. 우리의 instruction은 4바이트이므로 매번 PC에 4씩 더해지는 구성이다.

모든 연산은 ALU에서. ALU는 따라서 아주 다양한 연산을 한다. 그런 다양한 연산을 하기위해 control이 필요

회로상에 보면 꺾이는 부분이 많다. 이런 꺾이는부분은 맘대로 꺾이는게아니라 각 상황에 알맞은걸 선택하고 돌고 해야함. 즉 이걸 선택해줄 신호도 있어야하고 실제 선택이 일어나도록 mux도 있어야하겠지

mux도 달고 컨트롤도 달아주면 아래처럼된다.

플립플롭 : 조합회로에서는 입력에의해 결과가 바로나타나지만 순차회로에서는 이전의 입력이 결과에 영향을 끼친다. 플립플롭은 상승모서리에서 정보를 기록해둔다. 회로상에서 경쟁이 발생하는걸 막기위해 , 즉 같은 상승모서리에 정보를 전달하도록 하기위해 플립플롭은 사용된다.

이렇게 해줌으로써 동기화가 가능하다. cpu에 클락이 필요한 이유

모든 회로에 데이터는 상승모서리에 들어가도록 한다. 연산이 이뤄질 때 제대로 된 값이 들어갈 수 있도록 경쟁을 제거해주는거임. 너무빨라도 느려도안되니까 클락을 잘 맞춰주어야함. 너무 빠르게맞추면 있으나마나니까 늦는거에 맞춰줘야함. 그러다보니 클락은 가장 오래걸리는 놈에 맞춰줘야함.

데이터패스 상에는 여러가지 요소들이 배치된다. 이런 데이터패스를 통해 데이터는 처리된다.

ALU, mux, memory이런것들이 datapath에 포함되는것

대이터패스가 데이터의 처리를 달리할 수 있는 이유가 경로를 어떻게 하는가가 어떤 요소를 쓸 것인가 어떤 정보를 어디에 저장할것인가를 결정하기 때문임. 예를들어서 BEQ같은경우는 연산의 결과가 저장이되는게 아니라 PC에들어가는거임.

fetch 구현 : instruction을 메모리에서 가져와서 pc를 증가시킨다

R구현 : 레지스터 두개를 읽어다가 연산하고 그걸 레지스터에 쓴다. regwrite이랑 aluoperation 필요

ls구현 : 레지스터읽고 immediate처리해서 연산하고 메모리에서가져오거나 메모리에접근해서 쓴다. memwrite, memread, immediate generator가 필요함. immediate은 12비트일수도, 32비트일수도있는데 실제 연산에선 64비트가쓰이니까 이걸 64비트 수로 만드는 일을 한다.

b구현 : 레지스터를 읽어서 빼기해서 0인지확인한다. 같으면 점프하는거니까. immediate으로 받은 offset으로 타겟도 계산한다. 계산된값은 짝수보장값이었으니까 왼쪽으로 1번 쉬프트해준다

주소계산이나 조건계산이나 둘다 한 ALU로 못하는건아닌데 굳이 안하는건 시간적인 이득이 있기 때문이다.

여기까지 본 걸로 만들어낸 datapath. 그러나 이건 모든게 한 사이클안에 끝나는 그림이다.

ALU Control

ALU는 다양한 연산을 모두 해낼 수 있어야하는데 그 연산을 누가정해줄것인가..! Alu를 제어할 신호가 있어야한다.

ld , sd, add 모두 add로 해결됨. offset구할 때 add가 수행된다.

branch도 마찬가지로 sub로 해결된다. 빼서 같은건지 판별하니까

그럼 이제 이 ALU control을 어떻게 만들어내느냐

opcode로부터 나온 ALUOP과 func로 판별한다. 앞서말했뜻 ld, sd, add 모두 덧셈, beq, sub뺄셈인거 인증했쬬? 인증했쬬?

여기서보면알겠지만 ALUOP 2비트랑 func7 7비트, func3 3비트로 ALU가 무슨일을 할지 정한다.

Main Control

ALU가 연산하는거 말고도 결정되어야하는건 많다. 연산의 소스는 어디서올건지, 메모리에서 레지스터로 가져올건지, 레지스터에 쓸건지.. 등등 그리고 ALU control에 쓰였던 Aluop도 만들어줘야함. 사실 Alu도 opcode보고 해야하는건 마찬가진데, 그럼 너무복잡해지니까 main이 수고를 덜어주는거임

결과적으로 저렇게 옵코드 인풋 7비트가 주어지면

이로부터 각 포맷에 알맞는 main control이 주어진다. R포맷같은경우는 데이터 경로는 다 똑같은데 연산만 달라지니까..!

• ALUSrc : 소스가 immediate이야?
• MemtoReg : 메모리에서 레지스터로 뭐 가져와?
• RegWrite : 레지스터에 뭘 써?
• MemRead : 메모리에서 뭘 읽어?
• MemWrite : 메모리에 뭘 써?
• Branch : 브랜치해야해?

앞서 datapath가 중요한건 그 path상의 요소들을 어떤걸 통과시키느냐, 그리고 어디로 들어가게 하느냐에따라서 결과가 달라지기 때문이라고 했었는데 그 말 그대로다. control이 어떤 datapath를 열고 닫느냐에 따라 작업이달라짐

Q: 정의되지 않은 연산은 어떻게됨 ? A : datapath에 문제가 있을수도 있고, 무엇보다 정의되지 않은 연산이면 control을 만들어내질 못하니까 정상작동할 수 없음. addi처럼 datapath는 다 갖춰진경우도 있을 수 있음. 이런경우엔 decode만 잘 해주면 충분히 작동하겟쬬

각 포맷에 대한 datapath의 활성/비활성은 pdf 4-28부터 보도록합시다.

퍼포먼스 이슈 : 지금까지 한건 한 사이클 안에서 모든 instruction들이 수행되어야하는 구조였다. 근데 이런식으로 회로를 짜버리면 instruction들 중 가장 오래걸리는게 주기를 결정해버리니까 쓸데없이 시간이 느려진다. 이를 해결하기위해 각 instruction을 작은 부분으로 쪼개고 pipeline을 통해 분할처리하도록한다. 쪼개진 부분의 시간들의 최대공약수로 클락사이클을 정해주면 된다.

한 과정을 자잘한 과정으로 나누어 동시에 실행되도록 하면 시간이 절약된다. 어짜피 한사이클에 다할라고들어도 순차적으로 연산이 진행될텐데 노는공간이생기니까

겹치는 구간이 많아질수록 시간 절약도 많이된다. 즉 speedup은 n이 커질수록 늘어난다.

구획나누기

• IF : Instruction Fetch ⇒ 메모리로부터 인스트럭션을 가져온다.
• ID : Instruction Decode ⇒ 가져온 인스트럭션을 디코드해서 Main, ALU Control을 만들어낸다.
• EX : Execute operation ⇒ ALU control에 따라 ALU에서 연산을한다.
• MEM : Access Memory ⇒ datapath에 따라 메모리에 접근할일있으면 접근해서 쓰거나 읽는다
• WB : Write Back ⇒ 레지스터에 써줘야하면 써준다.

파이프라인의 성능은 최대공약수로 만들어서 하므로 손해보는 부분이 생기지만 그래도 오버랩되는부분생각하면 이게 낫다.. 그니까 개별 instruction의 성능은 더 떨어질 수 있어도, 병렬처리부분에서는 이게 깡패지

이렇게 손해가 생기지만 그래도 훨씬 빨리 끝난다는거 인정?유휴 작업이 생겨서 손해보는것

이경우 스피드업은 pipeline을 안쓸때가 쓸때보다 얼마나 오래걸리는가를 측정한거라고 보면된다. 안쓰면 한사이클에 800인데 쓰고서 한사이클에1000이 됐다.

걸리는시간은 n번의 instruction이 수행될때 안썼으면 800n, 썻다면 1000 + 200(n - 1)이므로 speedup은 4가된다. overwrap되는부분이 빈틈없었다면 5가 됐을 것. 스피드업의이상적인 수치는 스테이지의 수와 동일함.

RISCV는 파이프라인에 특화돼있다. 모든 인스트럭션이 32비트로 동일하고(fetch decode가 고정과정이라 유리) 포맷의종류가 적다 (mul이랑 div도 r인것처럼) ld/sd도 뭐 3번째에 계산 4번째에 접근이 장점이라는데 이건 잘 모르겟읍니다. 아마 메모리를 따로둿다는걸 어필하고싶은건가?

파이프라인은 순차적으로 작동한다. 왼쪽에서 오른쪽으로. 근데 오른쪽에서 왼쪽으로 갈 일이 생긴다.. 해저드가 발생한것이지..뭐근데 beq가 돌아가기전까진 문제가 안되니까 일단은 beq를 할지안할지모르니까 그냥 4더해서 계속 다음 instruction으로 넘어가는 전략을 취한다. ,똑같은문제가 ld나 r포맷같이 register에 쓰는 instruction에서도 발생한다. 뒤로가서 레지스터에 써줘야하니까..

pdf40쪽부터 참고하시오

컨트롤도 함께 따라가줘야한다 그래서

파이프라인상에는 한가지 인스트럭션만 주구장창올라가지 않는다. 다양한 인스트럭션들이 올라간다.

파이프라인엔 5단계가있다 그니까 한번에 최대 5개의 instruction이 공존할 수 있음.

CC5에는 이런모습이다.

WB의 ld가 write-back하면 ID의 ld자리로온다. 이걸 막기위해 전반부와 후반부 각각 따로컨트롤되게한다. 그리고 컨트롤도 datapath와 함께 이동해줘야한다. ID단계에서 디코드는 동일하게되지만 이를 사용하는부분은 데이터와 함께가야함

ID에서 만들어진 컨트롤은 ID 이후로 EX, MEM, WB에서 사용이되는데 이렇게 사용되기 위해선 뒤로 넘겨져야한다 . 파이프라인을 하나 안하나 컨트롤은 똑같음. 그냥 보내는과정이 수반된다는점만 달라진다.

해저드

structural : fetch중일 때 mem에 접근할 수없다. 자원에 여러곳에서 접근을 못하니까 근데 이건 해결임. instruction메모리와 data메모리를 따로 두어서 해결

data : 다음 인스트럭션에서 앞 인스트럭션의 결과를 사용해야하면 난처해진다. 앞에있다고해서 다 끝난게아님

WB시점에 쓰기가 끝나고 ID시점에 읽어야하니까 WB랑 ID까지는 겹칠 수 있다

이렇게 두번의 손해가생긴다.. 그치만 사실 값은 EX에서 이미 결정이 난거니까 레지스터가기전에 EX끝난시점에서 datapath만 새로 만들어주면 된다.

그래서 이렇게 만들어준다. 이러면 EX에서 계산된값이 레지스터를 거치지않고 바로 다음 인스트럭션의 소스가 된다. 대신 이러면 하드웨어도복잡하고 여러가지 오버헤드가생긴다.

로드후 사용하는것도 문제가된다. 이건 load-use data hazard라고 부른다. load된걸 쓰려면 MEM이후에 datapath를 새로 놔야되는데 이건 아무리빨라도 한사이클은 손해볼 수밖에 없다.

대신 코드를 잘 스케쥴링하면 해결할 수 있지..

control : branch가 결정되기까지 시간이 걸림. 그럼 그동안 다른 instruction을 수행한다. 희망을걸어보는거

아니면 ID단계에서부터 branch 주소를 계산하고 branch여부를 판단해서 바로 다음에 branch하도록 하는방법도있긴함 근데 이러면 엄청 오버헤드가 커진다. 그리고이렇게 아무리줄여봤자 하나는 손해보게 돼있다. ID가 끝나야 실행할수있는거니까

이럴바엔 예측을해보자 이말이지 근데 가장좋은예측은 “실패한다” 로 예측하는거임. 애초에 실패할 확률이 존나게 큼 그래서 걍 RISC-V에서는 항상 실패한다는 가정하에 다음 instruction을 수행하도록 4더해서하고 만약에 확인해보니까 엥 branch였네 하면 그간 수행한거 싹버리고 branch해서 다시이어감 이렇게하면 한번에 생기는 버블은 커도 생길 확률이 적으니까 어느정도 방어가된다.

ID에서 브랜치주소 계산해놓고 했다가 틀리면 수정하는경우인건가..?

예외

예측하지 못했던 이벤트가 발생.

예외 : 정의되지않은 ofcode, 산술연산오버플로우, 시스템 콜 등 내부적으로 발생한다.

중지 (interrupt) : IO로부터 들어온 이벤트 외부에서들어온 비동기형

• 예외가 발생하면 문제가 발생한 PC를 저장해두고 (Supervisor Exception Program Counter)
• 문제의 사유를 저장하고 (SCAUSE)
• SCAUSE에 따른 핸들러로 이동해서 처리한다.
• 처리가 끝나면 SEPC로 돌아가거나 종료시킨다.

벡터인터럽트 vectored interrupt

cause register에 의해 핸들러가 결정된다. 예외번호가 벡터테이블 베이스 레지스터 앞에 추가된다?

근데 이 공간은 32바이트 공간이라 여기서 해결못할수도있다 그럼 또 다른데로 점프시키는 코드가 이 32바이트 공간안에 들어간다.

5

메모리는 크고빠르다고 인식되지만 실제로 그렇지 못하다. 빠를수록 작고 느릴수록 크다. 따라서 빠르고 크게만들기위해서는 뭔가필요하다. 거기에 이용되는게 지역성

시간적 지역성 : 최근에 방문했떤 메모리주소에 또 방문할가능성이크다 loop같은거.

공간적 지역성 : 방문했던 메모리 근처에 또 방문할 가능성이크다. 배열도 순차적이고 pc도 순차적이듯

이렇게 공간성이라는게 있기 때문에 메모리가 어디에 접근할지 우리는 약간의 아이디어를 가질 수 있다.

이런 지역성을 활용하는 방법이있따

disk는 크고느리고 dram은 적당히빠르고 적당히크고 sram은 굉장히빠르고 굉장히 작다

이런친구들을 조합해서 메모리 계층을 만들면 도움이된다

일단 CPU는 발빠른친구를원하니까 SRam이랑 연결시켜서 빠르게작동하도록한다. 앞서 언급한 지역성떄문에 어짜피 넓은범위를 당장 필요로하지는 않을것이다. 그러무로 작은 애들을 sram에 올리는데는 큰 문제가 없다.

대신 dram이랑 disk 가 그를 보조하는것

여기서 sram에서 알맞은걸 찾는걸 hit이라고한다. miss는 당연히 놓친거겠지?

hit 수 / 접근시도 or miss 수 / 접근시도 이렇게 구할 수 있다.

SRAM : 한비트에 6~8트랜지스터, 읽기를 해도 비트가 변하지 않는다. 정보를 유지하는데 별다른 전력이 들지 않는다. 시간도빠르고 전력도 덜먹지만 트랜지스터가 많이필요해서 집적도랑 가격면에서 손해다

DRAM : 한비트에 한트랜지스터, 읽으면 값이 변해서 읽은다음에 다시써주는 부수적인과정이 필요하다. 정보를 유지하는데 전력이 또 필요함. 집적도도높고 속도도준수함 그래서 메인메모리로 사용된다

DRAM 은 2차원 배열구조로 되어있음 한줄읽고 다시 써주는 작업의 연속이다. DDR과 QDR도있음. 하강모서리에도 작동한다던지, 상승하강때 쓰기도한다던지 등

FlashMemory : 기본적으로 ROM이다 (EEPROM : Electrically Erasable Programable ROM) 쉽게말하면 지우기가 가능한 롬임. 지우고 다시쓰는방식. 근데 여러번 지우면 내구도에 문제가생겨서 컨트롤러가 유동적으로 지울장소를 바꿔가면서해야함. NOR과 NAND방식이 있는데 집적도와 속도의차이임. 결론은 집적도의 승

Disk Memory : 플래터디스크. 물리적으로 도는걸 헤더가 읽는거라 속도가 많이 느리다. 블럭단위를 오가기가 오래걸리니까 한번읽을때 많이읽는다.

seek time : 원하는 트랙으로 헤더가 움직이는시간

rotational latency : 헤더 밑에서 디스크가 도는데 걸리는시간

transfer time : 읽은 비트의 블럭을 전송하는데 걸리는시간. transfer time은 오래걸리지 않는다. 그니까 차라리 한번에 많이읽는게 낫다는거지

캐시

캐시는 지역성에 의존하는 메모리다. 원래는 메인메모리속도가 빠른편이고 CPU는 느린편이었으니 필요가 없었는데 CPU가 많이 빨라지고 memory는 그속도에 못미치게되니까 필요하게된거.

direct mapped cache

메모리의 구획을 나누어 캐시로 올려보낸다. 예를들어 캐시에는 8개의 블럭이 올라올수있고 메모리는 32개의 블럭이 있다면 메모리블럭중 지역성이 있는친구 8블럭을 캐시에 올리는거임. 메모리가 32자리이므로 6비트 주소체계를 가지고있다면 캐시에올라가면 3비트 주소체계를 갖게되겠지. 캐시의 3비트를 그래서 메모리의 하위3비트로해준다. 그렇게되면 메모리의 32개 블럭중 8개씩 잘라서 생각할 수 있음 캐시의 한 블럭은 메모리의 32개 블럭 중 4개의 후보중 하나가된다. 앞의 2개는 태그로 이름표라고 생각하면됨. 얘는 누구의 어느위치에서왔따 를 표시해주는거

TAG : 메모리주소의 상위비트, index가 정해지고 남은부분이라고 볼 수 있다. 이게 누구꺼야? 같은 이름표같은존재

cache index : 캐시의 인덱스, 캐시의 주소같은개념. 그치만 주소는아님!

위의 예로 들자면 32개의 메모리 블럭이 8개의 캐시에 매핑되어야한다. 따라서 캐시 인덱스는 하위 3비트가 될거고 나머지 상위 2비트는 태그가되는거

valid bit : 만약에 시스템이 막 켜진상태에서 캐시를봣는데 거기에 00번째 인덱스의 메모리값들이 있다고 쳐보자 그럼 만약에 시스템이 00xxx의 메모리에 접근하려고들면 메모리가아니라 캐시에 접근할거다. 거기안에는 원하는 데이터가 있지도 않아도..! 그러니까 이런걸방지하려면 이 정보들이 유효한지를 나타낼 valid bit가 필요한것. 초기엔 0으로 되어있다.

일단 index 찾아가는건 맞는데 찾아가서 tag확인하고 valid한지도 검증해야한다. 예시가 워드어드레스라서 쉬운거야 바이트어드레스면 오프셋도 고려햐야한다

64개의 블락이있고 한 블럭에 16바이트가 들어간다고 하자. 1204는 어떤 블럭에 들어가야할까?

1204 / 16 = 75 → 75번째 메모리블럭이다.

캐시에는 64개의 블럭이 있으므로 캐시의 11번째 블럭(인덱스)에 올라갈것 → cache index = 11

그러고도 4바이트이후니까 해당 인덱스에서는 4번째 바이트가되어야함 → block offset = 4

75/64 ~= 1 이므로 75번째블럭은 두번째 태그다 → block tag = 1

태그-인덱스-오프셋에서 인덱스를 찾아가서 태그가 같은지보고 valid한지 확인해서 데이터를 가져온 후에 오프셋을보고 데이터를 뽑아낸다. hit판정은 tag랑 valid로 한다. 한캐시에 한 워드가 들어간다고 잡으면 일이 간단한데, 실제론 그렇지않다. 한 블럭에 여러 워드가 들어가니까 블럭에 해당하는 모든 데이터를 mux로 선택해야함. 이 때 선택하는건 block offset이 되겠지. 가져와서 그 하위단에서 뽑아내는건 동일한방식임.

정리하자면 direct mapped chache에서 주소는 tag, index, block offset, byte offset으로 구성되고 validbit은 추가적으로 캐시에있는거니까 사실 주소랑은 무관한거다.

캐시사이즈가 2^n블럭이라면 n비트가 인덱스로 쓰인다(n이면 log2n만큼의 인덱스비트가 필요)

블럭에 2^m개의 워드가들어간다면 m비트가 오프셋으로 쓰인다.

추가로 블럭에는 2^(m+2)개의 바이트, 2^(m+5)개의 비트가 들어갈 수 있다.

또 각 워드는 2개의 바이트오프셋이 필요하다. 4바이트중 선택을 해야함.

태그비트는 인덱스와 오프셋을 제외한 나머지. 64비트 중 캐시인덱스 n개, 블럭오프셋m, 바이트오프셋2개를 제외해주면 태그비트가됨

캐시에 2^n개의 블럭이있고, 이는 각각 2^(m+5)개의 비트가 들어가고, 태그비트 (64 - (n + m + 2), 추가로 valid bit 1비트가 들어간다. 따라서 캐시에있는 총 비트의 수는

2^n블럭 * (2^(m + 32)블럭당비트 + (64-(n + m + 2))태그비트 + 1(발리드비트))

캐시미스를 처리하는방법 : hit시에는 문제가 안되지만 만약에 miss가 발생하면 캐시 내에서 해결할 수 없게된다 따라서 메모리에가서 읽어와야함. 그 메모리에서 읽어오는 과정 자체가 손해다. 읽는걸로 끝날게아니라 지역성을 유지하기위해 또 블럭을 가져오기도 해야함. 다 가져와서 못했던 작업을 처리해주면 끝난다. (가상메모리에선 page fault에 해당하는부분)

캐시의 문제점 : 캐시를 읽는건 문제가없는데 만약에 캐시를 쓰는건? 캐시에 쓰는건 메인메모리에는 기록이 안된다. 그럼 캐시랑 메모리가 서로 달라지게되는데..

해결방법 1 write through : 캐시에 쓸 때는 메모리에도 즉각 써주자 → 그럼 뭐하러 캐시씀 존나오래걸릴텐데

해결방법 2 write back : 메모리에 안써줘도 어짜피 지역성때문에 캐시 내부에서만 놀테니까 당장은 문제가안된다. 특정시점에 메모리에도 적용을해주자. → 그나마 이게 합리적이다

write buffer : 메모리에 쓰여져야할 데이터를 write buffer에 임시저장해 순차적으로 메모리에도 써준다. 그럼 멈춤없이 계속 작동할 수 있다. 버퍼가 꽉차지만 않으면.. 필요한걸 찾을 때 버퍼도 한번 확인해주는 식으로 하면 된다.

write back : 일단 캐시에서만 놀고 변경되야할거는 별도로 표시해주고 (dirty bit) 캐시가 변경되는 시점에 메모리에 새로 한번에 써주자 → 그래도 그나마 괜찮은방법

캐시 블락은 클수록 좋은편이다. 지역성이 극대화돼서 miss rate가 줄어드니까. 근데 그렇다고 막 키울수도없는게 블락이 커지면 커질수록 miss시의 페널티가 커진다. 결국엔 어느정도 절충해서 괜찮은 지점을 찾는것이 중요함.

캐시퍼포먼스 : 우리가썻던 CPUT = IC * CPI * CCT는 사실 miss가 전혀 안날때의 아주 이상적인 경우임 실제론 miss가 발생한다

RISC-V의 특성상 모든 instruction은 fetch한번은 보장이고, ld나 sd의 경우만 데이터 메모리에 추가로 접근한다. 즉 ld나 sd는 2번의 메모리접근, 이외의 모든 인스트럭션은 한번 접근한다는거

러프하게 계산해봅시다

miss rate가 2%인데 miss penalty가 100cycle인 경우 2%확률로 100증가이므로 평균적으로 miss 발생시 2사이클이 추가로 필요하게된다.

예제 I는 2%의 미스확률, D는 4%의 확률을 갖고, 각 미스는 100사이클의 손해가 생긴다. 완벽한 캐시동작에서 CPI는 2이며 load와 store는 전체 36%의 비중을 가질 때 어떻게될까요? 일단 모든 인스트럭션에대해 평균 2사이클이 증가하고 ld랑 sd에대해서는 4가 더 증가한다. 그런데 ld와 sd는 36%를 차지하므로 0.36 * 4 만큼 더 증가시킬것 즉 아주 평균적으로 miss가나면 3.44만큼의 패널티가 발생한다고 볼 수있다. 원래 CPI가 2였으니까 패널티 계산된 CPI는 5.44가된다.

존나 개손해처럼보이지만 캐시를 안쓰는거보단 훨 낫다. 캐시가 없을때발생하는 시간은 miss와 동일하다고 볼 수있으니 그렇게 계산을하면 200 + 0.36 * 400으로 평균 344사이클이 증가하게된다. 이게나라냐?

CPU의 성능이 좋아지면 미스 페널티의 중요도가 커지게된다. CPU는 빠르게동작하는데 메모리는 그대로면 메모리를 가지러가는 오버헤드동안에 CPU가 손해보는게 상대적으로 많아지니까 패널티가 상대적으로 커진다.

CPI를 줄이면 stall로 발생하는 시간의 비중이 커진다. 패널티가 상대적으로 커진다.

clock을 올린다 → 메모리는 그대로니까 패널티가 커짐

캐시성능을 올리기 : 미스율줄이기 (어소셔티브), 미스패널티줄이기(멀티레벨), 히트타임줄이기

associative cache

캐시는 사실 경쟁에서 안전하지 못하다. 아무리 지역성이 있더라도 경쟁의 가능성은 있다. 메모리 구조도 워낙 떨어져있고 하다보니 아다리안맞으면 골로가는거임 소프트웨어가 처리할 수 있긴하다고함.

각 구획이 경쟁하지 않도록 하는 방법이, 한 index에 여러 블럭이 올라가도록 하면 된다는거임 (한 set에 여러 entry)

n개 블럭을 한인덱스에 묶으면 n-way associative

모두다 묶어버리면 fully associative가 된다.

associative하게 캐시를 관리하게되면 같은 인덱스에서도 어떤 블럭을 고를지가 결정되어야한다. 그니까원랜 인덱스주면 찾아가서 tag같고 valid하면 hit이었지만

이재는 index타고가서 tag들로 어떤블럭쓸지 고르고 valid한지도 확인해야하니 n이 늘어날수록 그 과정이 복잡해지는것.

fully associative는 애초에 인덱스가 의미없어지는 상황이되어버림.

위에서 보듯이 associative를 쓰면 미스확률을 줄일 수 있다. 근데 막 0으로 수렴하는건아니고 어느정도 한계는 있음. 이것도 적당히해야지 야발..

이렇게 한 인덱스에 여러개의 블럭을 두려면 여러 블럭마다 valid와 tag가 따로붙어야하니 캐시 사이즈도 더 커야함. 또 태그를 다 비교해야하니까 하드웨어적으로도 많이 복잡해짐

direct map : 인덱스선택 태그 valid 확인

associative map : 셋 선택 태그비교하며 알맞은것 검색 valid 확인

교체 : 만약 미스가 발생하면 메모리에서 가져와서 캐시를 교체해주어야하는데 그 규칙은 어떻게 할 것인가?

Direct mapped에서는 선택권이 없다. 그치만 associative에서는 valid하지 않은 친구만 교체해주면 된다.

LRU : least recently used 제일 최근에 사용하지 않은것을 바꾼다. 지역성을 생각하면 이게 잘먹힐거 근데 이 시점같은걸 기록하는 오버헤드가 생각보다 크다

random : 걍 그런거 따지지말고 아무거나버려 → 생각보다 효율 나쁘지않음 LRU 에 비벼볼만하다.

멀티레벨 캐시 : 캐시에서도 어떻게든 계층을 나눠보면 이득이 있지 않을까? → 조금이라도 미스율을 낮추기위해서, 캐시도 빠른것과 느린것을나눠서 계층으로 구성하자. 당연히 윗단은 속도가 최곡 밑으로갈수록 크기가 중요해진다.

level 1에서는 시간을 최소화 하고 (minimal hit time, smaller cache size, block size), level-2에서는 l1보다 사이즈도크고 associative하게 해서 미스패널티와 미스율을 최대한으로 줄인다.

가상메모리

메모리를 캐시처럼, 디스크를 메모리처럼 대해보자. 프로그램은 메모리를 공유한다. 각각의 메모리 영역이 겹쳐질수도있고 복잡함. 프로그램간의 메모리 보호도 필요하다. cpu랑 OS는 가상의 주소를 물리주소로 매개해준다. 블락관리하듯 page라는 단위를 관리함.

여러 프로그램이 동시 실행될 때 각 메모리의 충돌도 막는다. 디스크의 가상메모리 페이지들은 실제 메모리에 매핑되어 동작한다. 메모리에 없을때 pagefault가 발생헤서 디스크에서 찾도록한다.

페이지안의 정보들은그대로있다. 어떤 페이지가 올지만 변한다.

페이지는 4kb이다. 즉 2^12만큼이 페이지로 떨어져 나가고 나머지가 페이지 번호가된다. (인덱스와 태그 정하듯) 그럼 실제 메모리에는 페이지와 페이지 번호가 올라가게된다..?

페이지폴트 : 페이지를 찾지못하는 경우. cache와 메모리사이에서는 시간이 많이 소요되지않아서 그냥 기다리지만 디스크는 존나느리다. 그거 기다리다가는 날밤 새기때문에 안기달리고 다른일을하다가 돌아온다. 우리가 예외처리중하나

---

페이지테이블 : 배치정보가 기록된다. 가상 페이지 수의 배열.

페이지테이블레지스터는 물리적인 메모리상의 페이지테이블의 시작점을 가리킨다.

페이지테이블에는 물리적인 페이지번호와 다른 상태비트들 (레퍼런스, 더티비트 Valid bit 등)이 들어간다.

디스크에서는 스왑공간이라고 불린다.

페이지테이블에서 오프셋은 그대로가고 가상 메모리주소가 물리메모리주소로 번역이된다. 그래서 가상메모리 주소가 주어지면 페이지테이블에서 실제 메모리에 있는지 확인하고 없으면 디스크로 가는것?

review

캐시에서 블락 → 페이지

캐시에서 미스 → 페이지폴트

가상주소를 물리주소로 변경 주소변환과정은 가상페이지를 물리페이지로 바꾸는게 다다

페이지교체

캐시에서는 associative에서는 결정의 문제가 생겼었다.

LRU : 페이지폴트확률을 줄인다. reference bit를 활용해 확인한다. 운영체제가 주기적으로 0으로 만들고, 그 페이지를 사용하면 1으로바꾸게해서 1인게 최근에 사용된거니까 살리고 아니면 죽이는거. 나름 쉽게 구현한방법이다. reference bit가 0인걸 제거해준다. 즉 페이지 엔트리마다 하나씩있어야함.

디스크에 쓰기문제 : write-buffer을 하는건 현실적이지 못하다. 거의 write back을 사용한다. 그러니까 더티비트도 있어야함. write의 단위도 page이다.

페이지테이블을 참조 ← 페이지테이블은 메모리에있다.

ld인스트럭션의 주소는 가상주소이다… 진짜접근하려면 물리주소를가지고 캐시를가야함.. 그럼 페이지테이블을 참조해야하고 페이지테이블은 메모리에있다..그럼 ld과정에서

페이지테이블보러 메모리가고

메모리주소를갖고 메모리에 다시접근해야함

ld는 사실 최악의경우 메모리에 4번을가야한다.

인스트럭션fetch 페이지테이블참조→인스트럭션fetch→메모리접근 페이지테이블참조→메모리접근

캐시는 90몇퍼확률로 방어가되니까 메인메모리를 안가는확률이 더 컸다.

페이지테이블로 가는것도 최대한 줄일수있따

모든메모리 엑세스는 두배가 유발될수도있다. 페이지테이블때문에.. (주소를얻기위해, 실제접근을위해)

한페이지가 4kb니까 한 페이지에는 k개의 인스트럭션이있다.. → 여러번 페이지테이블 가봤자 똑같은 페이지로 갈가능성이크다. 우리가 계속말했던 지역성이 있으니까.

지역성이 생각보다 존나게 커진다 4kb나 되니까.

TLB (Translation Lookaside Buffer): 페이지테이블의 지역성이 존나크다. 페이지테이블도 특별한 캐시를 만들어서 어떤 가상메모리가 물리메모리인지를 표시해둔다. 그럼 변환과정이 존나 짧아진다.

페이지테이블을 메모리에둬도좋지만 어짜피 지역성이크니까 다양한 페이지를 보지는 않을거다. 그니까 일부 페이지만이라도 테이블정보를 특별한 캐시에 두면 좀 성능의 향상을 기대할 수 있다는거지. TLB를 통해 페이지검색을 빨리할수있다.

TLB 사이즈는 생각보다 작다. page간의공간지역성은 크지 않다. 굳이 블락의사이즈를 키울필요도 없다. 1~2개의 페이지만 가지고있어도된다.

캐시니까 어짜피 hit이면 짧고, fault면 메모리에 가야하니까 10~100정도

미스날확률은거의없다 0.01~1%정도

가상주소를 물리주소로 바꿀 때 가상주소를 나누어서 페이지번호와 페이지 오프셋으로 바꾼다. 페이지넘버만 가상→물리변환을 한다. 인덱스만가지고 일단 찾아가듯 일단 페이지넘버만 가지고 페이지테이블을간다. 그럼 거기엔 물리 페이지 넘버가 있다→ 그걸로 진짜 물리메모리에 접근한다. 물리메모리에가서 페이지오프셋으로 어디에 접근할지가 정해진다.

물리메모리에 없는건 디스크에있다는거. 페이지가 물리메모리에없다

TLB에서는 가상페이지와 물리페이지주소를 표로 가지고있음

여기서는 엔트리 7개, 즉 7개의 페이지정보를 가지고있음. 단순 가상메모리주소만가져오는게아니라 물리메모리주소도 같이들고와서 매핑해놓은다. 찾을때는 모든 엔트리를 동시접근해서 가상메모리로 매칭되는걸 찾아서 바로 물리메모리로 실제메모리에 접근한다. → fully associative

TLB는 일종의 fully associative cache처럼 작동한다!!!

fully는 캐시에서 실용적으로 잘 안쓰이는데도 다뤘던이유는 TLB처럼 특수한 캐시에서 사용되기 때문이다

바로 물리적인 메모리를 찾을수있게 만든것!

특수한캐시에서 쓰인다고했던이유가 이거였다.

ADD는 원래 한번, 근데 가상메모리사용하면 최악의 경우 두번.. 근데 TLB가 있다. 아니면 cache도 있고

최초로 주어지는건 가상주소다. (instruction에 주어지는게 가상주소임)

페이지오프셋은 두고, 페이지넘버를 변환시켜서 TLB에서 일괄 탐색한다(fully associative)

매치가 됐다면 바로 짝지어진 물리메모리주소에 페이지오프셋을 더해주면 물리주소가된다.

인스트럭션의 가상주소가 물리주소로 바뀌는 과정에서 TLB가 필요한것.

그럼 이렇게 만들어진 물리주소로 cache를 확인해봐야한다. 이번엔 주소의 캐시인덱스로 캐시에가서 해당 인덱스의 tag와 valid를 확인한다.

상응한다면 가져와서 쓴다.

가상메모리까지 고려한게 이렇게 해결된다!

족보

캐시의 성능향상

associative cache의 사용 → 한 인덱스에 여러 블럭을 가지게되므로 miss rate를 줄일 수 있다.

multi leve로 cache를 구성 → miss가 발생하더라도 메모리에서 찾는게아니라 아랫 레벨의 캐시에서 해결할 수 있는 가능성이 있다. miss penalty가 줄어든다.

더 큰 캐시 block을 사용 → 공간지역성이 증가해 miss rate는 줄어들게된다. 그러나 miss시 발생하는 오버헤드는 증가해 miss penalty는 커지게된다.