CS Week 1 - 컴퓨터 구조 기초

카카오 그룹의 CS(Computer Science) 테스트를 처음 접하고 비전공자의 무지함을 직접 실감하니 따로 공부하지 않고는 버틸 수가 없었다...

그렇게 시작된 비전공자의 8주 짜리 CS 기초 다지기 !

차근차근 달려가다보면 언젠가 끝에 닿으리라 믿으며 첫 주차를 시작한다.

Table of Content

첫 주차는 컴퓨터의 기본 하드웨어적인 요소가 되는 CPU와 이와 상호작용하는 여러 저장소, 레지스터, 캐시, RAM 에 관한 이야기이다.

주제	세부 핵심 내용
1, 프로그램이 돌아간다는 것은 ? - 프로그램 실행 과정	- 저장소의 종류와 역할
2. CPU 는 어떻게 생겼나 ? - CPU 내부 구조	- 레지스터란 ?
	- 캐시 메모리란 ?
3. 최하위 단계에서의 로직 - 고전 5단계 파이프라인	- Instruction Fetch, IF : 명령어 가져오기
	- Instruction Decode, ID : 명령어 해독하기
	- Execute, EX : 명령어 실행하기
	- Memory Access, MEM : 데이터 접근
	- Write-Back, WB : 결과 기록
	- 해저드(Hazard)에 대해
	- 파이프라인 최적화 기법
4. 메모리 계층과 ‘왜 캐시가 필요한가’ - 캐시와 메모리	- 레이턴시 절벽(Latency Cliff) 과 캐시 메모리의 종류
	- 지역성(Locality)
	- 주소 분해 - 데이터의 위치와 위치 핸들링
	- 가상 메모리 - ‘가짜 주소 공간’ 시스템
	- 매핑 정책 - 메모리 블록을 캐시의 어디에 저장할까?
	- 여러가지 캐시 정책 - 캐시 내 데이터 핸들링 정책
5. 캐시 미스와 캐시의 성능 계산 - 3C와 AMAT	- 캐시 미스의 종류 (3C)
	- 캐시의 성능 계산 (AMAT, Average Memory Access Time)

---

1. 프로그램이 돌아간다는 것은 ? - 프로그램 실행 과정

프로그램의 명령어들은 별도의 컴파일 과정을 거쳐 기계어로 번역된다. 파일 실행 시, OS 가 해당 파일을 RAM 으로 올리고 CPU 를 데려와 시간 및 작업을 할당하게 된다.

• 저장소의 종류와 역할

  결국 디스크 / SSD 등은 전체 파일을 저장하는 역할, 메모리 / RAM 는 실행되는 파일을 올려놓는 “실행 공간” 이며 동시에 컴퓨터의 “실행” 역할을 총괄하는 OS 가 조정하는 곳, 레지스터 / 캐시 는 실행되는 “하나하나의 개별 명령”으로 연산을 담당하는 CPU가 조정하는 곳인 셈이다.

---

2. CPU 는 어떻게 생겼나 ? - CPU 내부 구조

• 레지스터란 ?

  레지스터(Registers)란 디스크, 메모리, 캐시보다도 빠른 CPU와 직접적으로 붙어있는 초고속 초소형 저장소이다.

  사실상 RAM 에 실행 파일이 올라간다면 레지스터에서 하나하나의 명령이 처리된다고 볼 수 있다. 이 레지스터는 산술연산을 담당하는 ALU(Arithmetic Logic Unit)과 직접적으로 붙어있어 직접적인 가장 하위 Baseline의 연산을 하기 위한 저장소라고 볼 수 있다. 여기를 극대화하여 활용한다면 메모리 접근 횟수를 줄임으로서 획기적인 성능 개선을 노릴 수 있다.

  레지스터는 하나하나의 명령을 담는 공간이기에 명령의 종류에 따라 그 종류가 크게 나뉜다. 레지스터간의 데이터 연산과 데이터 전달을 통해 전체 명령이 실행된다고 볼 수 있다. 그 예시는 c. 참고
  

• 캐시 메모리란 ?

  캐시 메모리란 일반적으로 RAM으로 지칭되는 메모리와 CPU 명령 처리에서 RAM 의 접근성 제한으로 발생하는 병목 현상을 해결하기 위해 더 가볍고 빠르도록 상위 계층에 존재하는 저장소이다. 보통 일반적인 메모리는 SRAM, 캐시 메모리는 이보다 더 빠른 DRAM 으로 이루어져 있다.

  메모리가 “실행되는 파일”을 올려놓는 공간이라면 캐시 메모리는 그 중 “가져올 확률이 높은 파일이 모인 공간” 이라고 볼 수 있다.
  같은 비유로 레지스터는 “실제로 가져온 파일” 이라고 볼 수 있겠다.

---

3. 최하위 단계에서의 로직 - 고전 5단계 파이프라인

• Instruction Fetch, IF : 명령어 가져오기

  • 프로그램 카운터(Program Counter, PC) 는 “다음 명령어의 메모리 주소” 를 가지고 있다. 이 메모리 주소를 메모리 주소 레지스터에 ****넘겨준다.

  • 메모리 주소 레지스터(Memory Address Register, MAR) 은 “실행 명령의 메모리 주소” 를 저장하는 공간이다.

  • 이를 통해 제어 장치는 메모리에 접근하여 메모리 버퍼 레지스터(Memory Buffer Register, MBR) 에 “실행 명령의 데이터” 를 저장하여 가져온다.
    이 과정에서 L1 → L2 → L3 → 메모리 순서로 히트 / 미스를 판단하게 된다.
    

  • 명령어 레지스터(Instruction Register, IR) 은 이렇게 가져온 “다음 명령어” 가 저장되는 공간이다.

• Instruction Decode, ID : 명령어 해독하기

  • 제어 장치(CU) 가 IR에 존재하는 명령어를 읽어 “연산 종류”, “저장소(레지스터, 메모리 등) 위치” 를 파악하여 제어 신호를 생성하게 된다.

• Execute, EX : 명령어 실행하기

  • ALU(산술 연산)/AGU(주소 생성) 이 해당 제어 신호에 맞춰 연산을 수행하게 된다.

  • 만일 산술 연산이라면 ALU 가 범용 레지스터(General Purpose Register, GPR) 의 다양한 값들을 참조하여 연산을 수행, 플래그 레지스터(Flags Register) 에 그 연산과 관련된 여러 상태(Zero, Carry, Sign 등) 을 저장하고 결과값을 GPR 에 저장한다.

  • 만일 주소 생성 신호라면 AGU 가 베이스 레지스터(Base Register, BR) 의 베이스 주소를 참조, GPR 의 값들을 참조하여 주소를 계산 후 저장한다.

• Memory Access, MEM : 데이터 접근

  • 위 경우와 동일하게 MAR, MBR, 캐시의 상호작용이 일어난다. 단, 초고계층의 L1은 효율성을 위하여 명령어 전용 L1I 와 데이터 전용 L1D 로 나뉘어져 있다는 사실을 기억하자.

• Write-Back, WB : 결과 기록

  • 결과를 기록하는 단계로 ALU(산술 연산) 혹은 MBR(메모리 데이터)의 결과를 GPR(범용) 혹은 FP(실수 연산용) 에 저장하는 단계이다.
  • 위 기본 단계들을 이용하여 파이프라인은 여러 형태를 띌 수 있다. 예컨대 여러 명령을 통째로 병렬 처리하는 Super Scalar, 각 단계를 촘촘히 이어붙은 Super Pipeline, 이 둘을 합친 SuperPipelined Super Sclar 방식 등이 존재한다.

• 해저드(Hazard) 에 대해

  이러한 파이프라인은 병렬적인 처리로 인해 중간 중간에 막히기도 하는데 이를 해저드(Hazard) 라고 한다.

  1. 대표적인 해저드로 구조적 해저드(Structural Hazard) 는 병렬 처리 과정에서 여러 명령이 하나의 주소에 존재하는 경우 발생하며 이는 버블 스톨(Bubble Stall) 을 통해 파이프라인의 쉬어가는 시간을 만들어주어 해결한다.

     버블 스톨이란 아무것도 없는 "버블"을 만들어주어 다른 작업이 진행되는 동안 특정 파이프라인이 작업을 쉬도록 만들어주는 기법이다.

  2. 데이터 해저드(Data Hazard) 는 이전 명령의 WB 과정 이전에 후속 명령이 값을 쓰거나 읽는 경우로 RAW(Read After Write), WAW(Write After Write), WAR(Write After Read) 로 나뉘며 이는 포워딩(By-Pass), 다른 하나는 버블 스톨을 이용하여 해결한다.

     포워딩이란 결과값이 저장되는 WB 과정 이전 EX / MEM 과정에서 GPR / MBR / FP 등에 저장된 값을 다음 연산의 ALU 로 미리 전달하는 방법 이다.

  3. 마지막으로 제어 해저드(Control Hazard) 는 이전 명령의 분기 / 점프 / 함수복귀 등으로 인해 PC 값이 바뀌는 경우 발생하며 이를 예측하는 분기 예측(Backward-Taken, Forward-Taken , BHT(Branch History Table) 등) / 주소 값을 캐싱하는 BTB(Branch Target Buffer), 주소 값을 스택에 넣는 RAS(Return Address Stack) 등의 방법으로 해결한다.
     

• 파이프라인 최적화 기법

  1. 이러한 파이프라인의 성능을 개선시키기 위한 방법으로 레지스터 리네이밍(Register Renaming)이 존재한다. 이는 데이터 해저드 - WAR / WAW - 가짜 의존성을 제거하기 위한 방법으로 실제로 값이 저장되기 이전에 읽으려는 실제 해저드, RAW 과 달리 동일한 레지스터명 사용으로 발생하는 충돌을 제거한다. 이를 통해 불필요한 버블 등을 제거하여 CPU의 성능을 높일 수 있다.

  2. 잇따라, OoO(Out of Order), 버블로 밀리는 시간동안 준비된 명령부터 실행하여 처리량을 높이는 방법이 존재한다. Renaming 이 진행된 상황에서 각각의 명령 오퍼랜드를 유닛(ALU, AGU) 등에 예약시켜놓고 버블이 발생하는 순간 이를 실행시키는 방법이다. 당연하게도 전체 처리 순서는 변하면 안되기에 ROB(Reorder Buffer) 를 통해 그 순서를 다시 찾아간다.
     

---

4. 메모리 계층과 ‘왜 캐시가 필요한가’ - 캐시와 메모리

• 레이턴시 절벽(Latency Cliff) 과 캐시 메모리의 종류

  레이턴시 절벽(Latency Cliff) 이란 저장장치 간의 속도 차이가 계단식으로 급격히 커지는 현상을 말한다. 그러나 속도와 비용의 트레이드오프 관계로 인해 모든 저장소를 L1 수준으로 만들 수 없기에 “계층적인 저장소 구조”를 이용해 이를 해결한다.

  CPU와 가장 근접한 순서로 연산중인 데이터나 주소를 직접적으로 가지고 있는 레지스터, 자주 쓰는 명령어(L1I)나 데이터(L1D) 등을 가지고 레지스터 바로 옆에 존재하는 L1 Cache(약 32kB*2), CPU 내부 하나하나의 코어에 붙어있는 L2 Cache(약 1MB), 여러 코어가 공유하는 L3 Cache(약 수십 MB), CPU 밖에서 실행중인 프로그램 전체를 담고 있는 SRAM, 모든 정보를 가지고 있는 SSD / HDD로 나누어진다.
  

• 지역성(Locality) 이란 ?

  이러한 계층 구조에서 효율적인 “캐시 히트” 를 위해 캐시 구조는 기본적으로 “지역성” 이라는 특성을 가진다.

  이는 최근에 쓴 데이터는 곧 다시 쓴다는 “시간적 지역성” 과 근처에 존재하는 데이터는 곧 다시 쓴다는 “공간적 지역성”으로 나뉘게 된다.

  예를 들어 루프를 도는 sum 함수의 경우 시간적 지역성이, 리스트와 같은 배열 순회 시 공간적 지역성이 크게 작용하게 된다.

  이러한 지역성을 충족시키기 위해 캐시는 요구 데이터를 읽어올 때 근처 데이터를 함께 읽어오게 되며 이때 한 번에 읽어오는 데이터 크기를 캐시 라인이라고 한다. 이에 따라 각각의 캐시는 전체 캐시 크기 (ex. 4096 bytes) 에서 캐시 라인의 크기 (ex. 64 bytes) 를 나눈 수 만큼의 세트 (64 세트), 구역 분획을 가지게 된다.

  이러한 지역성을 반영하여 미리 RAM 의 데이터를 캐시 메모리에 올리는 프리페처 (Prefetcher) 도 존재한다.
  

• 주소 분해 - 데이터의 위치와 위치 핸들링

  명령어가 가지는 주소는 32 bit 의 크기로 메모리 블록의 정체성을 나타내는 tag (20 bit), 캐시 내 세트 번호 index (6 bit), 해당 메모리 블록 내 비트 시작 순서인 offset (6 bit)로 이루어진다.

  tag 주소 는 RAM 상에 존재하는 데이터 블록의 위치이며 캐시 내 저장된 데이터의 캐시 히트 판단을 위해서도 쓰이기에 캐시의 메타 데이터로도 저장되는 값이다.

  index 주소는 캐시 내 몇 번 세트에 데이터를 저장할 것이냐 혹은 몇 번 세트에 데이터가 저장되어 있느냐를 나타내는 값이다. 하나의 캐시 메모리가 총 64개의 세트, 구역 분획을 가지기에 이를 나타내기 위해 index 주소는 세트 수 만큼의 6 bit의 길이를 가진다.

  offset 주소의 경우 접근한 캐시 라인, 메모리 블록 하나는 결국 지역성과 캐시 라인 크기에 따라 64 bytes 로 이루어져 있고 이 중 실제 필요한 데이터의 시작 위치를 나타내는 값이다. 하나의 세트는 총 64 bytes 로 이루어져 있기에 이 중 시작 바이트를 나타내기 위해 offset 주소는 6 bit 의 길이를 가진다. 4-way 의 경우 세트 당 4개의 라인이 존재하고 tag 주소 히트로 라인이 자동 선택되므로 offset 주소는 세트 크기가 아니라 캐시 라인 크기에 맞추게 된다.

  이러한 데이터의 주소는 매우 빠르고 예측 가능해야 하므로 RAM의 메모리 주소 → 캐시 세트 번호는 하드웨어적으로 이미 정해진 1:1 대응 규칙을 따르게 된다.

  1. CPU → 캐시 접근 시 (Cache Lookup)

     L1 → L2 → L3 순서로 명령어에 존재하는 index 주소를 기준으로 해당 캐시 메모리의 세트에 접근, tag 주소를 기반으로 캐시 히트 / 캐시 미스 여부를 판단한다. 만일 히트할 경우 offset 주소를 기반으로 하나의 세트의 64 bytes 내 읽기 시작점을 정해 데이터를 읽어온다.
     

  2. 캐시 → RAM 접근 시 (Cache Miss / Memory Fetch)

     이 경우 해당하는 tag 주소의 메모리 블록 (64 bytes) 를 불러와 index 주소의 캐시 메모리에 이를 저장, 데이터를 가져다 쓰게 된다. 이 경우 offset 주소는 0번으로 초기화되어 캐시 세트의 첫 부분부터 데이터를 저장하게 된다.
     

• 가상 메모리 - ‘가짜 주소 공간’ 시스템

  CPU와 운영체제는 각각의 프로그램을 독립된 저장소에서 운영하기 위해 “가상 주소(Virtual Address)” 를 운영한다. 이를 통해 각각의 프로그램은 여러 개로 분할된 RAM 메모리더라도 연속된 메모리처럼 접근하고 사용할 수 있으며 운영체제는 가상 주소를 실제 RAM 주소, 물리 주소로 바꾸어주는 페이지 테이블(Page Table) 을 통해 이를 관리한다.

  그러나 이러한 페이지 테이블은 RAM 상에 존재하기에 매번 주소를 변환하기 위해 RAM 에 접근하는 병목 현상이 발생한다. 이를 해결하기 위해 최근 사용한 페이지 테이블 내용을 저장하는 별도의 캐시 메모리인 TLB(Translation Lookaside Buffer)가 존재하기도 한다.
  

• 매핑 정책 - 메모리 블록을 캐시의 어디에 저장할까?

  1. Direct-mapped cache (직접 매핑)

     해당하는 그대로 저장
     

  2. N-way Set-associative cache (집합 연관 매핑)

     하나의 세트 (64 bytes) 를 N-way, 예를 들어 4개의 하위 라인으로 나누어 데이터를 관리한다. 이 경우 라인 캐시의 크기가 64 bytes 보다 작은 16 bytes 단위로 작동할 수 있게 되어 캐시 히트 확률을 높일 수 있지만 복잡하다는 단점이 존재한다. 이에 더해 하나의 캐시 세트에 여러 단위의 데이터를 동시에 저장할 수 있어 충돌 캐시 미스(Conflict Cache Miss) 를 줄일 수 있다는 장점을 가지고 있다.
     

  3. Fully-associative cache (완전 연관 매핑)

     index 주소를 삭제한 버전이다. 어떤 데이터든 캐시 메모리 내 어느 위치에든 들어갈 수 있어 유연성을 가지지만 캐시 히트 판단 시 모든 tag 주소를 비교해야 한다는 단점이 존재한다.
     

• 여러가지 캐시 정책 - 캐시 내 데이터 핸들링 정책

  • 쓰기 정책 (Write Policy)

    데이터 수정 시 캐시 메모리 / RAM 간의 순서에 관한 정책이다.

    1. Write-through (즉시 쓰기)

       캐시 수정 시 즉시 RAM 에 반영하는 정책으로 메모리 트래픽이 크게 발생하지만 데이터의 실시간 반영, 즉 캐시 일관성을 유지할 수 있다. 실시간 반영이 중요한 L1 캐시에서 주로 사용된다.
       

    2. Write-back (지연 쓰기)

       별도의 dirty-bit 을 붙여 나중에 데이터가 교체될 때 RAM 에 반영하는 방식으로 메모리 트래픽이 적지만 실시간 반영이 안되고 복잡하다는 단점이 존재한다.
       

    3. Write-allocate / No-write-allocate (미스 처리 정책)

       새로운 변수 작성 시 해당 변수가 캐시 메모리에 없는 경우 write-miss 가 발생, Write-allocate 의 경우 RAM 에서 데이터를 캐시로 다시 가져와 수정하는 정책이다. No-write-allocate 의 경우 바로 RAM 에 수정하는 정책이다.
       

  • 교체 정책 (Replacement Policy)

    캐시 메모리 내 데이터 교체 시 “어떤 라인을 내보낼까?”

    1. LRU (Least Recently Used)

       가장 오래된 데이터를 교체하는 방식이다. 모든 데이터의 사용 순서 갱신 및 추적이 필요해 구현이 복잡하지만 캐시 효율성이 올라간다. 각 데이터 블록은 이미 들어갈 캐시 세트 번호가 정해져 있으므로 그 중 어느 오프셋을 지울 지를 결정하는 정책이다.
       

    2. PLRU (Pseudo-LRU)

       간소화된 버전으로 트리 비트 구조 등으로 간단한 순서만을 기억한다.
       

    3. Random

       랜덤 순서로 생각보다 성능이 나쁘지 않다.
       

  • 포함성 정책(Inclusivity Policy)

    캐시 계층(L1, L2, L3) 간 데이터를 어떻게 나눠 저장할 것인가 ?

    1. Inclusive (포함형) 캐시

       L1 → L2 → L3 순서로 상위 집합 역할을 하도록 만든 정책으로 구현과 관리가 굉장히 단순하지만 데이터가 중복 저장된다는 단점이 존재한다. 데이터가 캐시 전체에 존재하지 않음, 캐시 무효화(Invalidate) 를 L3 캐시만으로 확인할 수 있으며 캐시 동기화 기법도 굉장히 간단하다. Intel 이 그 예시.
       

    2. Exclusive (배타형) 캐시

       캐시 메모리들이 전부 다른 정보만을 저장하도록 만든 정책으로 캐시 용량 효율성이 100%지만 그 구현이 복잡하고 데이터 이동이 잦다는 단점이 존재한다. 예를 들어 L1 cache miss, L2 cache hit 시 L2의 데이터를 L1으로 옮기고 L2의 데이터를 지우는 과정이 요구된다.
       

    3. Non-inclusive (비포함형, 유연형)

       포함해도 되고 안해도 되는 정책으로 가장 유연하지만 구현 난이도가 높고 관리가 어렵다는 단점이 존재한다.

---

5. 캐시 미스와 캐시의 성능 계산 - 3C 와 AMAT

• 캐시 미스의 종류 (3C)

  1. Compulsory Miss (필수 미스)

     해당 데이터에 처음 접근 시 발생하는 캐시 미스로 계층적인 메모리 구조상의 문제로 어쩔 수 없이 발생하는 문제이다. 이른바 “Cold Start(콜드 스타트)”.

     완화 방법이 없는 것은 아니고 프리페쳐(Prefetcher) 를 통해 미리 데이터를 캐시에 올림으로써 어느정도 해결할 수 있다.
     

  2. Capacity Miss (용량 미스)

     프로그램이 한 번에 사용하는 데이터가 캐시의 전체 용량보다 커서 발생하는 캐시 미스이다. 이 경우 관련 데이터를 모두 캐시에 올리지 못해 LRU에 의해 캐시 내 데이터가 순차적으로 밀려나게 된다.

     프로그램 구조상에서 한 번에 너무 큰 데이터를 통한 연산을 진행하지 않도록 데이터를 작은 부분으로 쪼개는 Tiling(타일링)을 통해 해결할 수 있다.
     

  3. Conflict Miss (충돌 미스)

     데이터가 들어갈 캐시의 세트 번호를 정할 때 빈 캐시 세트나 더 오래된 캐시 세트를 찾는 것이 아니라 이미 하드웨어적으로 정해진 캐시 세트 번호로 들어가기 때문에 사용하는 주 데이터들이 같은 캐시 세트 번호를 공유하게 될 때 발생하는 캐시 미스이다.

     이를 해결하기 위해 구역 분획을 더 나누는 N-way associated 매핑 정책 을 사용하거나 배열의 시작 주소를 임의의 캐시 라인 크기의 패딩을 통해 stride, 데이터 접근 간격을 살짝 어긋나게 만드는 Data Padding(데이터 패딩) 을 사용하거나 열 순회 등의 데이터 순서 재배치를 통해 이를 해결할 수 있다. 각각의 경우에 대해 구현 복잡, 캐시 메모리 효율 하락, 공간 지역성 하락 등의 문제가 추가적으로 발생한다.
     

• 캐시의 성능 계산 (AMAT, Average Memory Access Time)

  캐시의 성능은 결국 CPU 가 “데이터에 한 번 접근하는데 걸리는 평균 시간”을 줄이는 것이 목표이므로 AMAT 가 곧 캐시의 성능 지표가 된다.

  단일 캐시 구조에서 AMAT = Hit Time + Miss Rate * Miss Penalty 로 계산되며 각각 캐시 히트 시 데이터를 바로 읽는 시간, 캐시 미스 확률, 캐시 미스 시 하위 계층에서 데이터를 읽는 시간이다.다단 캐시 구조에서는
  AMAT_L1 = Hit Time_L1 + Miss Rate_L1 * AMAT_L2
  AMAT_L2 = Hit Time_L2 + Miss Rate_L2 * AMAT_L3
  AMAT_L3 = Hit Time_L3 + Miss Rate_L3 * Miss Penalty_RAM
  의 구조로 이루어진다.