컴퓨터구조 다시 공부해보기

컴퓨터구조 학점이 D-다. 이번 학기에 재수강하게 돼서 미리 한 바퀴 돌렸다. 강의가 14주고 평가는 중간과 기말이 거의 전부라, 시험에 나올 계산 위주로 다섯 덩어리를 잘랐다.

정리하고 보니 이 과목은 명령어 하나가 컴퓨터 안에서 어떻게 처리되는지를 앞에서 뒤로 따라간다. 그리고 뒤로 갈수록 질문이 느린 것을 어떻게 견디느냐로 바뀐다.

1. 성능 평가

프로그램이 얼마나 걸리는지 재는 방법부터 시작한다. 생각해보면 답은 뻔하다. 명령어를 몇 개 실행하는지, 명령어 하나에 클럭이 몇 번 드는지, 클럭 한 번이 몇 초인지. 이 셋을 곱하면 시간이 나오는데, 시험은 셋을 따로따로 흔들어서 묻는다.

CPU 시간 = 명령어 수(IC) × CPI × 클럭 주기
         = 명령어 수(IC) × CPI ÷ 클럭 주파수

CPI는 명령어 하나당 클럭 수인데, 명령어마다 다르다. 곱셈은 오래 걸리고 덧셈은 금방 끝난다. 그래서 종류별 비율을 알고 있으면 평균을 내서 쓴다.

평균 CPI = Σ(종류별 CPI × 종류별 비율)

Σ는 종류마다 곱해서 전부 더하라는 뜻이다. 명령어 100개짜리 프로그램으로 세어보면 바로 보인다. ALU가 50%에 CPI 1이면 50개가 50클럭을 쓰고, load가 20%에 CPI 5면 20개가 100클럭을 쓴다. 이렇게 다 더한 뒤 명령어 100개로 나눈 값이 평균 CPI다.

종류	CPI	비율	곱하면
ALU	1	0.5	0.5
load	5	0.2	1.0
store	3	0.1	0.3
branch	2	0.2	0.4
		합	2.2

여기서 두 가지를 조심해야 한다. 하나는 클럭 주기와 주파수가 서로 역수라는 점이다. 2GHz면 주기가 0.5ns인데, 문제가 어느 쪽으로 줬는지부터 봐야 한다.

다른 하나는 클럭이 빠르다고 무조건 빠른 게 아니라는 점이다. 2GHz에 CPI 1.5인 컴퓨터와 3GHz에 CPI 2.5인 컴퓨터를 비교하면, 클럭이 느린 쪽이 오히려 약 1.11배 빠르다. 클럭만 보고 고르면 틀리게 돼 있다.

마지막은 암달의 법칙이다.

속도 향상 = 1 ÷ ((1−f) + f/s)
            f = 개선되는 부분의 비율, s = 그 부분이 빨라지는 배수

프로그램의 60%가 곱셈인데 곱셈기를 4배 빠르게 만들면 전체는 1.82배밖에 안 빨라진다. 곱셈을 아예 공짜로 만들어도 2.5배가 한계다. 나머지 40%는 그대로 남아 있기 때문이다. 일부만 개선해서는 전체가 그만큼 빨라지지 않는다는 얘기다.

2. 명령어 형식

명령어 한 줄은 결국 32비트짜리 숫자 하나다. 그 안에 무슨 연산인지, 어떤 값을 쓸 건지, 결과를 어디에 넣을 건지를 다 담아야 한다.

레지스터를 가리키는 자리가 5비트인 이유가 여기서 나온다. MIPS 레지스터가 32개인데, 32개 중 하나를 고르려면 5자리가 필요하다. 2를 다섯 번 곱하면 32니까 그렇다. 외울 숫자가 아니라 세면 나오는 숫자다.

형식	배치	쓰임
R	op(6) rs(5) rt(5) rd(5) shamt(5) funct(6)	add, sub 같은 계산
I	op(6) rs(5) rt(5) immediate(16)	lw, sw, addi, beq
J	op(6) address(26)	j, jal

형식이 셋인 건 담아야 할 게 다르기 때문이다. 계산 명령어는 재료 둘과 결과 하나가 필요해서 레지스터 자리가 세 개다. addi처럼 숫자를 직접 쓰는 명령어는 그 숫자를 넣을 자리가 통으로 필요해서 레지스터 자리 하나를 포기하고 16비트를 확보한다. 멀리 점프하는 명령어는 아예 주소에 26비트를 다 쓴다.

분기 명령어가 재미있다. beq가 쓸 수 있는 자리는 16비트뿐인데 주소는 32비트다. 담을 수가 없다. 그래서 주소 대신 여기서 몇 칸 건너뛸지를 적는다.

분기 목적지 = (PC + 4) + (offset × 4)

× 4가 붙는 건 명령어 하나가 4바이트라서다. 칸 단위로 세면 같은 16비트로 네 배 멀리 갈 수 있다.

3. 파이프라이닝

명령어 하나를 처리하는 일은 다섯 토막으로 나뉜다.

단계	하는 일
IF	메모리에서 명령어를 꺼낸다
ID	명령어를 쪼개고 레지스터 값을 읽는다
EX	계산한다
MEM	메모리를 읽거나 쓴다
WB	결과를 레지스터에 적는다

빨래로 생각하면 쉽다. 세탁기를 돌리고 건조기에 넣고 개서 서랍에 넣는 일을 한 사람씩 다 끝내고 다음 사람으로 넘어가면, 첫 사람이 서랍에 넣을 때까지 세탁기는 논다. 첫 사람 빨래가 건조기로 넘어갈 때 세탁기에 둘째 사람 빨래를 넣으면 아무도 안 논다. 기계를 놀리지 않고 겹쳐서 흘리는 것, 그게 파이프라인이다.

여기서 클럭을 어디서 끊느냐가 갈린다. 단일 사이클은 명령어 하나를 클럭 한 번에 끝내니까, 클럭 한 번이 다섯 단계를 전부 통과할 만큼 길어야 한다. 파이프라인은 클럭 한 번에 단계 하나만 하면 되니까 제일 느린 단계만 버티면 된다.

방식	클럭 주기	CPI
단일 사이클	모든 단계의 합 (800ps)	1
다중 사이클	제일 느린 단계 하나 (200ps)	명령어마다 다름
파이프라인	제일 느린 단계 하나 (200ps)	이상적으로 1

단계 시간이 각각 200, 100, 200, 200, 100ps일 때의 숫자다. 합이냐 최댓값이냐를 바꿔 쓰면 그 문제는 통째로 틀린다.

시간 공식은 그림을 그려보면 안 외워진다. 명령어 세 개를 다섯 단계에 흘리면 첫 명령어가 끝나는 데 5클럭이 걸리고, 그 뒤로는 매 클럭 하나씩 나오니까 남은 두 개에 2클럭이 더 든다. 합쳐서 7클럭이고, 이걸 일반화한 게 아래 공식이다.

파이프라인 총 클럭 = 단계 수 + (명령어 수 − 1)
총 시간 = 총 클럭 × 클럭 주기

명령어가 백만 개면 5 + 999,999라서 앞의 5는 있으나 마나 해진다. 그래서 CPI가 1에 가까워진다. 다만 파이프라인은 명령어 하나를 빨리 끝내주지는 않는다. 오히려 조금 늘어난다. 빨라지는 건 명령어 하나가 아니라 전체 처리량이다.

4. 해저드

겹쳐서 돌리니까 생기는 문제다. 앞 명령어가 아직 결과를 안 적었는데 다음 명령어가 그 값을 읽으려 들면 곤란해진다.

종류	언제	해결
구조적	같은 부품을 동시에 쓸 때	부품을 늘린다
데이터	앞 결과를 뒤에서 바로 쓸 때	포워딩, 안 되면 스톨
제어	분기 결과가 나오기 전에 다음 걸 가져와야 할 때	예측한다

데이터 해저드는 값이 언제 나오고 언제 필요한지만 비교하면 풀린다. 원래 값은 WB에서 레지스터에 적히고 다음 명령어가 ID에서 읽어 가는데, 이러면 시간이 안 맞는다. 그래서 계산이 끝난 곳에서 필요한 곳으로 값을 직접 질러 보낸다. 레지스터에 넣었다 빼는 왕복을 생략하는 것이고, 이걸 포워딩이라고 부른다.

문제는 메모리에서 값을 읽어 오는 명령어다. 계산 명령어는 EX에서 값이 완성되는데 lw는 MEM에 가서 읽어야 값이 나온다. 한 단계 늦다. 다음 명령어가 EX를 시작할 때 lw는 아직 손에 값을 못 쥐고 있어서, 없는 값을 넘겨줄 수가 없다. 그래서 한 클럭을 그냥 흘려보낸다.

상황	스톨
바로 윗줄이 lw이고 그 값을 씀	1
바로 윗줄이 계산 명령	0
lw인데 두 줄 이상 떨어져 있음	0
포워딩이 없는 파이프라인	2 또는 3

세 번째 줄이 함정이다. lw 두 개가 붙어 있고 그 아래에서 둘 다 쓰면 스톨을 두 번 세기 쉬운데, 멀리 있는 쪽은 이미 값이 나와 있어서 세면 안 된다. 마지막 줄은 문제에 단서가 있어야 정해진다. 레지스터 파일이 같은 클럭에 쓰고 읽을 수 있다는 조건이 있으면 2, 없으면 3이다.

분기는 성격이 다르다. 어디로 갈지 아직 모르는데 다음 명령어를 가져와야 하니 일단 찍는다. 맞으면 그냥 흘러가고, 틀리면 잘못 가져온 걸 버리는데 그때 버리는 클럭이 벌점이다.

분기 벌점이 있을 때   CPI = 1 + (분기 비율 × 벌점 사이클)
예측이 있으면        CPI = 1 + (분기 비율 × 틀리는 비율 × 벌점)

기본 CPI 1에 더해지는 것이지 곱하는 게 아니다. 그리고 예측이 80% 맞는다고 하면 0.8이 아니라 틀리는 비율 0.2를 곱해야 한다. 벌점은 틀렸을 때만 받는다.

5. 캐시

메모리는 크지만 느리다. 명령어 하나에 백 클럭씩 기다릴 수는 없으니 자주 쓸 것만 가까운 곳에 작게 얹어둔다. 그런데 작으니까 어디에 놓을지 규칙이 필요해진다.

주차장으로 생각하면 편하다. 칸이 네 개인데 차가 여덟 대라고 해보자. 차 번호를 4로 나눈 나머지 칸에 대기로 정하면 규칙은 간단해지지만, 0번 차와 4번 차가 같은 칸을 쓰게 된다. 0번 칸에 서 있는 차가 둘 중 누구인지 알 수 없으니 앞유리에 번호표를 붙여둔다.

캐시가 주소를 세 조각으로 자르는 게 정확히 이 일이다. 어느 칸에 댈지가 인덱스, 그 칸에 든 게 정말 찾던 것인지가 태그다. 그리고 메모리에 한 번 다녀올 때 여러 개를 통째로 끌고 오기 때문에 그중 몇 번째인지도 알아야 하는데, 그게 오프셋이다.

주소 = [ 태그 | 인덱스 | 오프셋 ]

오프셋 = log₂(블록 크기)
집합 수 = (캐시 크기 ÷ 블록 크기) ÷ 연관도
인덱스 = log₂(집합 수)
태그   = 주소 비트 − 인덱스 − 오프셋

32비트 주소에 캐시 16KB, 블록 16바이트, 직접 사상이면 오프셋 4, 인덱스 10, 태그 18이 된다. 셋을 더해 32가 나오는지가 검산이다. 태그는 계산해서 나오는 게 아니라 쓰고 남은 것이다.

인덱스는 집합 수로 센다. 블록 수가 아니다. 직접 사상만 연습하면 둘이 같아서 구분이 안 되는데, 연관도를 4배 올리면 인덱스가 2비트 줄고 태그가 2비트 는다.

여기서 제일 억울한 상황이 나온다. 빈 칸이 세 개나 남아 있는데도 하필 같은 칸을 원해서 쫓겨나는 경우다. 이걸 막으려고 칸 몇 개를 묶어서 그 안에서는 아무 데나 대게 해주는 게 집합 연관이다. 대신 찾을 때 번호표를 여러 개 확인해야 해서 조금 느려진다.

AMAT = 적중 시간 + (실패율 × 실패 손실)

캐시에는 항상 먼저 들르고, 없을 때만 추가로 메모리에 다녀온다. 그래서 곱하기가 아니라 더하기다. 적중 시간 1, 실패율 5%, 실패 손실 100이면 AMAT는 6이 된다. 실패율을 2%로 줄이면 3이 되는데, 3%포인트 차이로 절반이 되는 건 실패 손실이 적중 시간의 백 배라서다.

실패 종류	줄이는 법	대신 나빠지는 것
강제	블록 크기를 키운다	실패 손실이 커진다
용량	캐시를 키운다	느려지고 비싸진다
충돌	연관도를 올린다	적중 시간이 늘어난다

한 바퀴 돌고 나서

다섯 덩어리가 따로 노는 것 같았는데 다 하고 보니 한 줄이었다. 명령어를 32비트에 어떻게 담을지 정하고, 처리를 단계로 쪼개 겹치고, 겹쳐서 생긴 문제를 포워딩과 스톨로 손보고, 느린 메모리를 캐시로 가린다. 그리고 첫 덩어리의 공식이 그게 실제로 빨라졌는지 재는 자다.

공짜가 없다는 것도 계속 나온다. 파이프라인은 명령어 하나를 빨리 끝내주지 않고 전체를 빨리 끝낸다. 연관도를 올리면 충돌은 줄지만 적중 시간이 는다. 블록을 키우면 강제 실패는 줄지만 실패 손실이 커진다. 어느 쪽을 택할지가 이 과목이 계속 던지는 질문이다.

남은 네 과목도 이렇게 한 바퀴씩 돌려볼 생각이다.