폰 노이만 구조

현대 컴퓨터 구조들은 폰 노이만 구조를 바탕으로 하고 있다. 해당 컴퓨터의 구조는 위의 그림과 같다. 입력 장치와 출력 장치는 존재하지만 크게 신경을 쓸 것은 없다. 왜냐하면 폰 노이만 구조에 있어 딱히 핵심적인 내용은 아니기 때문이다.

눈여겨 볼 부분은 중앙처리장치(CPU)와 주 기억장치(메인 메모리)다. 그리고 이 두 장치는 버스로 연결이 된다. 메인 메모리는 주소의 집합들이며, 명령어와 데이터들이 저장된다. 그래서 메인 메모리에 접근 할 때에 주소를 통하여 해당 명령어 및 데이터를 가져 올 수가 있다. 이것을 페치(Fetch)라고 일컫는다.

CPU는 제어 유닛(Control Unit)과 연산/논리 유닛(ALU)으로 구성이 되어 있는데, 그 역할은 다음과 같다.

• 제어 유닛 : 어떤 명령어가 실행 될지를 결정한다.
• 연산/논리 유닛 : 실제 명령어를 실행하는 역할을 수행한다.

그림에 묘사되어 있지 않지만, CPU에는 레지스터(register)라고 하는 특별한 기억 장치가 있다. 레지스터에는 CPU가 사용중인 데이터 및 실행중인 프로그램의 정보가 저장된다. 이 레지스터는 여러 종류가 있는데, 그 중에서 프로그램 카운터(program counter)라는 것이 존재한다. 이 프로그램 카운터에 다음에 실행 할 명령어와 해당 명령어의 주소가 저장된다.

폰 노이만 병목

폰 노이만 구조는 본질적인 문제를 안고 있는데, 발로 병목 현상이다. 이는 CPU와 메인 메모리의 분리로 인해서 발생하는 문제다. 왜냐하면 CPU가 처리 할 수 있는 명령어 숫자와 메인 메모리에서 가져 올 수 있는 명령어 수의 차이가 있기 때문이다.

예를 들어서, CPU가 1초에 10000개의 명령어를 처리한다고 가정해보자. 그런데 버스를 통해 메인 메모리에서 가져 올 수 있는 명령어는 1초에 1000개에 불과하다고 가정해보자. 그러면 단순 계산으로 CPU는 0.1초 동안 명령어를 수행하고, 0.9초 동안은 작업이 없어 놀게 되는 셈이다.

슬프게도 CPU의 처리 속도가 발전하고, 메인 메모리의 용량이 커질 수록 이러한 간극은 더더욱 커져가는 추세이다. 때문에 이러한 문제를 해결하고자 하는 여러 노력들이 존재했고, 지금도 이러한 문제를 해결하고자 한다.

캐시(Cache)

캐시는 폰 노이만 병목을 해결하기 위해 자주 사용되는 방법들 중의 하나이다. 캐시의 기본 골자는 CPU안에 또 다른 작은 저장 장치를 두는 것이다. 그리고 CPU가 사용한 데이터 혹은 명령어들의 일부는 캐시에 저장이 된다. 이 캐시의 의의는 메인 메모리에 접근하는 것 보다 훨신 빠르다는 장점이 있다. 때문에 캐시를 통해서 CPU의 작업 효율을 늘릴 수가 있다. 하지만 1가지 문제가 있다. 바로 어떤 데이터를 캐시에 저장해야 하는 것이다.

캐시의 용량은 메인 메모리와 비교하면 상당히 작다. 때문에 저장 할 수 있는 용량이 제한되어 있다. 그래서 저장 할 데이터와 명령어를 선별 할 필요가 있는데, 보편적으로는 직전에 사용한 데이터 및 명령어와 물리적으로 가까운 것을 사용한다. 일반적으로 프로그램은 명령어를 실행한 후에 다음 명령어를 수행하기 때문이다. 다른 지역으로 넘어가는 분기는 상대적으로 빈도가 적다.

int arr[1000];

/*
	Do something
*/

int total = 0;

for(int i = 0; i < 1000; i++)
	total += arr[i];

위의 코드를 한번 살펴보자. 배열은 메모리에 연속 된 블록으로 할당된다. 그래서 arr[0] 바로 다음에 arr[1]이 오게된다. 이렇게 한위에 대한 다음 위치를 접근한다는 원칙을 지역성(Locality)이라고 한다.

이러한 지역성이라는 특징을 활용하기 위해서 개별적인 데이터 및 명령어에 접근하기 보다는 덩어리로 가져와서 처리한다. 이러한 덩어리(혹은 블록)를 캐시 블록(Cache block) 혹은 캐시 라인(Cache line)이라고 한다.

이 캐시가 저장할 수 있는 크기는 레벨에 따라 상이하다. 위의 그림에서 보이듯 캐시의 레벨이 명기되어 있는데, 레벨이 낮을수록 빠르고 저장 할 수 있는 크기가 작아진다는 특징이 있다.

때문에 CPU는 데이터나 명령어에 접근 할려고 할 때에 순차적으로 살펴본다. 처음에는 레벨 1 캐시는 체크하고, 그 다음으로 레벨 2 캐시를 체크한다. 그리고 마지막엔 메인 메모리에 접근한다. 만약에 캐시에서 해당하는 정보를 있을 경우에 이를 캐시 히트(Cache hit)라고 한다. 거꾸로 찾지 못하였을 경우엔 Cache miss(Cache miss)라고 한다.

캐시 매핑(Cache mapping)

메모리 인덱스	완전 연관	직접 매핑	2-way
0	0, 1, 2, 3	0	0, 1
1	0, 1, 2, 3	1	2, 3
2	0, 1, 2, 3	2	0, 1
3	0, 1, 2, 3	3	2, 3
4	0, 1, 2, 3	0	0, 1
5	0, 1, 2, 3	1	2, 3
6	0, 1, 2, 3	2	2, 3
. .	. . .	.	. . .
15	0, 1, 2, 3	1	2, 3

그렇다면 메인 메모리에서 읽은 데이터 및 명령어를 캐시에 어떻게 배치해야 할까? 이러한 문제에 대한 접근법으로 완전 연관 캐시(Fully associate cache), 직접 매핑 캐시(Direct mapped cache)가 있다. 그리고 중간자 적인 접근법으로 n-way 집합 연관(n-way set associative)가 있다.

위의 표에서 보이듯이 메모리 인덱스가 0 ~ 15까지 있는 16라인의 메모리를 가정하자. 그리고 캐시의 사이즈는 4 라인이다. 이 경우에 대한 각자의 접근 방법은 다음과 같다.

• 직접 매핑 캐시 : 4로 나눈 후 나머지에 따라 라인을 할당한다. 그래서 표에 보이는 것 처럼 0에는 0, 1에는 1 순서로 저장되는 걸 확인 할 수가 있다.
• 완전 연관 캐시 : 이 경우에는 모든 메모리 라인에 캐시가 할당 되어 있는 것을 볼 수 있다. 이는 메모리의 인덱스와 무관하게 캐시의 어디든 적재 될 수 있음을 의미한다.
• 2-way 집합 연관 : 이 접근법은 위에서 언급한 기법을 절충한 방법이라고 볼 수도 있는데, 각 캐시 라인마다 n 개의 캐시 라인을 할당한다. 그래서 위의 표와 같은 모습이 된다.