프로그래머가 몰랐던 멀티코어 CPU 원리와 구조

Story 01. 프로그래머가 프로세서도 알아야 해요?

- 병렬 프로그래밍의 중요성이 대두 되면서 하드웨어를 exploit해야 할 필요성이 커짐.
- 소프트웨어 개발에 쓰일 수 있는 다양한 알고리즘 / 아이디어를 습득할 수 있음.

Story 02. 프로세서의 언어 : 명령어 집합 구조 (ISA)

CISC의 탄생
 - 범용 목적 마이크로 프로세서가 처음 나온 1970년대에는 컴파일러의 도움이 크지 못했다. -> 다양한 기능을 제공
 - 그리고 메모리가 비싸고 부족했다. -> 짧은(가변) 길이의 명령어 형태
 - 그래서 최초의 ISA는 CISC형태를 띔.

RISC의 탄생
 - CISC의 명령어들 중 자주 사용되는 것은 일부분에 불과했다.
 - 제한되고 간단한 형태의 명령어들만 제공함으로서 더 저렴하다. 혹은 다른 것에 트랜지스터들을 투자 가능.
 - Make Common Case Fast

RISC vs CISC
 - RISC는 하드웨어의 복잡함을 컴파일러나 프로그래머에 넘겼다. (레지스터 수가 많고 하드웨어 구현이 더 간단, 슈퍼컴퓨터에 적합)
 - CISC는 프로그램의 복잡함을 하드웨어가 도맡아 처리한다.
 - 이제는 RISC와 CISC경계가 모호해졌다. CISC인 x86의 경우 CISC 명령어를 내부적으로 micro-op으로 쪼개서 처리한다. (겉은 CISC, 속은 RISC)

Story 03. 프로세서의 기본 부품과 개념들

마이크로 아키텍처 : 마이크로 프로세서 하나를 만드는 데 필요한 알고리즘 및 회로 수준의 구조를 자세히 정의 한 것.

Story 04. 암달의 법칙과 프로세서의 성능 지표

성능 향상을 위해 해야 할 일
- 명령어 개수 N을 줄이자
   * 컴파일러 최적화 : Common Sub-expression Elimination, Constant Propagation, Dead Store Elimination 등등
   * 적당한 inlining과 loop unrolling은 성능을 향상 시킨다.
   * 프로세서 내부 : macro-op fusion, micro-op funsion
- CPI를 줄이자
   * 파이프라이닝, 슈퍼스케일러, 비순차 실행, 분기 예측, 투기적 실행
- 클록 속도는 빠르게
   * 반도체 미세 공정
   * 한 사이클에 완료되는 일의 양을 줄인다. (파이프라이닝과 관련)

Story 05. 프로그램의 의미를 결정 짓는 의존성

데이터 의존성 : RAW, WAR, WAW
 - RAW (flow dependence) : 진짜 의존성. 순서대로 실행돼야 한다.
 - WAR (anti dependence) : Renaming같은 테크닉을 통해 해결 가능.
 - WAW (output dependence) : 위와 같다.
컨트롤 의존성 : 분기에 의해 생기는 의존성. PC에 의한 RAW라고도 볼 수 있다.
메모리 의존성 : 포인터에 의해 생기는 것. 실행 전까지 데이터 의존성 여부를 알 수 없다.
Story 06. 프로세서 기본 동작

인터럽트 (Interrupt)
 - 하드웨어 인터럽트 : 명령어 흐름과 상관없이 비동기적으로 발생하는 사건.
 - 소프트웨어 인터럽트 : 명령어(INT와 같은)로 인해 발생하는 인터럽트.

예외 (Exception)
 - 프로그램 실행 도중 동기적으로 발생하는 사건. (프로그램 흐름과 관련있다.)
 - Fault : 문제를 일으킨 명령어부터 실행.
 - Trap : 문제를 일으킨 명령어 다음부터 실행.
 - Abort : 프로그램 중단.

Story 07. 고성능 프로세서의 시작 : 명령어 파이프라인

파이프라인의 효율적인 설계
1. 균등한 파이프라인 단계 : 파이프라인의 각 단계는 균등한 길이로 나뉜다.
 - 파이프라인의 효율은 가장 긴 단계가 결정한다. (pipeline stall)
2. 같은 작업 : 파이프라인은 항상 같은 작업만 수행한다.
 - 어떤 명령어가 특정 단계에서 더 많은 시간을 쓴다면 역시 stall이 생겨 효율이 떨어진다. 따라서 각 단계는 항상 같은 길이를 가지는 것이 좋다.
3. 독립적인 작업 : 파이프라인에 투입되는 작업은 서로 의존 관계가 없다.
 - 명령어들이 서로 파이프라이닝에 있어 의존성이 있다면 stall이 생겨 효율이 떨어진다.
4. 파이프라인 유지 비용의 최소화 : 최적의 파이프라인 깊이를 찾는다.
 - 파이프라인 자체에 대한 비용을 생각해야 한다.
 - 이상적으로는 단계가 많아질수록 효율이 좋아진다. 그러나 실제 구현에서는 파이프라인 깊이를 늘리는 것에 대한 비용을 생각해야한다.

파이프라인 해저드
구조 해저드 : 프로세서의 자원이 부족해서 생기는 stall
컨트롤 해저드 : 분기에 의해서 생기는 stall
 - delayed slot, branch prediction등을 통해 해결
데이터 해저드 : 데이터 의존성과 메모리 의존성에 의해 발생하는 stall
 - bypass등을 통해 해결

소프트웨어에서도 파이프라이닝 기법을 활용할 수 있다.

Story 08. 또 하나의 혁명 : 비순차 실행

순차 프로세서
 - 명령어들을 순서대로 실행하는 프로세서
비순차 프로세서
 - 명령어들을 의존성에 따라 스케쥴링하며 비순차적으로 실행하는 프로세서
 - 특정 명령어가 stall되면 그 동안 다른 명령어를 처리할 수 있다.
 - 뒤에 오는 명령어를 throughput을 위해서 미리 실행 할 수 있다.
 - 보통 슈퍼스칼라 프로세서이다.
슈퍼스칼라 프로세서
 - 두 개 이상의 파이프라인을 가진 프로세서
 - 이상적인 IPC가 1을 초과할 수 있다.

명령어 수준 병렬성 (ILP)
 - 명령어 수준에서 명령어들이 동시에 실행될 수 있는 병렬성.
 - 하드웨어가 아주 이상적이라면 IPC는 ILP와 같을 것이다.

Tomasulo 알고리즘
 - 비순차 실행을 구현하는 알고리즘.
 - 밑의 요소들로 이루어져 있다.

Instruction Window
 - 명령어들 사이에서 ILP를 찾을 때 사용하는 윈도우.
 - 윈도우 내에 가장 오래된 명령어가 완료되면 한 칸 이동한다.
 - 2010년 기준 최신 프로세서들에서 Window 크기는 보통 100여 개. 컴파일러는 그 보다 더 큰 수천 개의 명령어들 사이에서 ILP를 찾는다.

Register Renaming
 - Register Renaming을 통해 가짜 의존성 (WAR, WAW)을 해결한다.
 - 이 과정은 Instruction Decoding과정에서 이루어진다.
 - 논리 레지스터 파일과 물리 레지스터 파일의 mapping을 위해 RAT(Register Alias Table)을 사용한다.

Reservation Station
 - Reservation Station을 이용해 동적으로 명령어를 스케쥴링한다.
 - Wake-Up : 어떤 명령어의 모든 피 연산자가 완료되면 명령어를 깨운다. (즉, 실행 가능한 상태로 표시한다.)
 - Select : 실행 가능한 명령어들 중 선택을 하여 계산 장치를 할당 한다. (즉, 스케쥴링을 한다.)
 - RS의 wake-up과 select 로직은 확장하기가 어렵다. 따라서 파이프라인 구현의 병목 지점이 된다.
 - 2008년 인텔의 네할렘 구조에서 RS의 크기는 36개.

Re-Order Buffer (ROB)
 - ROB는 비 순차적으로 실행된 명령어들이 순서대로 완료되게 한다.
 - 인텔의 네할렘 구조에서 ROB의 개수는 128개.

순차 vs 비순차
 - 인텔의 Itanium, Atom, IBM의 POWER6, GPU는 순차 방식.
 - Itanium은 ILP를 하드웨어가 아닌 컴파일러가 찾는 구조이다.

Story 09. 하이퍼스레딩 : 병렬성의 극대화

ILP의 한계
수평 방향의 낭비 : ILP의 제한등의 문제로 파이프라인에 명령들을 꽉 넣을 수 없을 때.
수직 방향의 낭비 : cache miss등으로 인해 파이프라인에 명령어를 하나도 넣을 수 없을 때.

Hardware Multi-threading
 - TLP (Thread Level Parallelism)를 활용하는 기술
 - Fine-Grained Multi-threading : 일정 사이클 동안 번갈아가며 명령어를 쓰레드에서 가져와 파이프라인에 넣는다. 수직 방향의 낭비를 어느 정도 해결.
 - Coarse-Grained Multi-threading (Switch-On-Event Multi-threading) : 명령어를 하나도 투입할 수 없을 때 문맥을 다른 쓰레드로 전환한다. 수직 방향의 낭비를 효과적으로 해결.
 - Simultaneous Multi-threading : 매 사이클마다 여러 쓰레드에서 동시에 명령어를 가져와 파이프라인에 투입한다. 수평/수직 방향의 낭비를 효과적으로 해결.

Hyper-threading : 인텔이 구현한 2-way SMT
SMT는 보통 높은 효율을 가져다주지만, 공유하는 자원이 많기에(cache, reservation station등) 불균형을 초래할 수 도 있다.

Story 10. 멀티코어 혁명 : 칩 멀티프로세서

싱글 코어의 한계 : 에너지 장벽, ILP의 한계
병렬 컴퓨터 구조 : SISD, SIDM, MISD, MIMD

공유 메모리 구조
칩 멀티프로세서(CMP) : 멀티코어를 의미 (cpu 1개에 여러 개의 core가 있는 것)
대칭형 멀티프로세서(SMP) : 프로세서를 대칭적으로 여러 개 연결하는 것. (mainboard에 여러 개의 cpu를 꼽는 것) 프로세서 수가 증가하면 메모리에 병목 현상이 많아짐으로 scalability가 떨어진다.
NUMA(Non-Uniform Memory Access) : 시스템 전체적으로 메모리 주소는 공유하지만, 물리적인 메모리 위치를 서로 떨어져있다. 메모리 접근 속도가 비균일하다. SMP에 비해 scalability가 좋다.

멀티코어의 구성 방식
homogeneous 멀티코어 : 같은 (종류) 의 코어들로 구성한다.
heterogeneous 멀티코어 : 서로 다른 종류의 코어들로 구성한다. (직렬적인 부분은 속도가 빠른 코어에 맡기고, 병렬적인 부분은 속도가 느리나 많은 수의 코어에 맡기는 식의 응용이 가능하다.)

멀티코어의 한계 : 메모리 장벽 (코어 수가 많아져도 메모리 대역폭에 한계가 있어 성능이 오히려 떨어질 수 있다.)
병렬 프로그래밍의 중요성 : The free lunch is over.

Story 11. 데이터 병렬성 : SIMD와 GPU

주목할 만한 내용 없었음. (GPGPU와 CUDA에 대한 일반적인 개론이었다.)

Story 12. 고성능 프로세서의 필수 조건 : 똑똑한 캐시

Cache의 검색 정책
 - 주소를 Tag, Index, Offset 세 부분으로 나누어 cache line에 접근한다.

Cache의 배치 정책
 - Directed-Mapped : 한 인덱스가 캐시 라인 하나에 할당된다.
 - Set-Associative : 한 인덱스가 N개의 캐시 라인 내에서 할당될 수 있다. (N-way) 캐시 충돌을 줄일 수 있다. 그러나 N개의 tag검사를 동시에 실행해야 함으로 하드웨어 구현이 어렵고 비용이 증가한다.
 - Fully-Associative : 한 인덱스가 캐시 어디에도 할당될 수 있다.

Cache의 교체 정책
 - N-way set-associative cache에서 최대 N개의 cache line 중에 어떤 것을 교체할 것 인지에 대한 정책.
 - 일반적으로 LRU를 사용. (LFU나 FIFO방식을 사용할 수 도 있다.)
 - LRU : 각 cache line마다 log2(N) 비트의 counter를 유지하여 LRU를 구현할 수 있다. (총 N*log2(N) 필요)
 - Pseudo LRU : cache line을 tree구조로 관리하며 가장 최근에 접근된 cache로 가는 경로를 기록하는 방법. (N-1비트만 가지고 가능.)
 - L1은 보통 LRU 혹은 유사 LRU 사용. L2나 L3는 L1에 비해 접근 패턴이 다르기 때문에 다른 교체 정책을 쓰기도 한다. (최근에 사용된 cache line은 대부분 L1에서 보존되기 때문에 L2나 L3으로의 접근 패턴은 L1에 비해 temporal locality가 낮다.)

Cache의 쓰기 정책
- L1 명령어 캐시는 write-through, 그 외에는 대부분 write-back을 사용한다.

Cache Miss의 분류와 줄일 수 있는 방법
1. 콜드 미스 (cold miss, compulsory miss)
 - 데이터를 최초로 읽을 때 발생한다.
 - cache line 크기를 증가함으로서 줄일 수 있다. 그러나 이는 충돌/용량 미스에 악영향을 끼칠 수 있다.
 - Prefetching을 통해 줄일 수 있다.
2. 충돌 미스 (conflict miss)
 - index가 충돌함으로서 발생한다.
 - cache associativity를 높임으로서 줄일 수 있다. 그러나 이것은 tag 일치 검사를 해야 할 cache line이 많아짐으로서 hit latency를 악화 시킬 수 있다.
 - victim cache 기법 (일부 영역의 캐시에서만 연관도가 높아야한다는 점에서 착안한 기법)
3. 용량 미스 (capacity miss)
 - cache의 용량이 부족해 발생한다.
 - cache의 크기를 늘림으로서 줄일 수 있다. 그러나 이는 hit latency의 악화를 가져온다.
4. 코히런스 미스 (coherence miss)
 - 다른 프로세서에 의해 cache line이 무효화되어 발생한다.

Blocking Cache : cache miss가 처리 중이라면 다른 캐시 접근을 봉쇄된다.
Non-Blocking Cache : cache miss가 처리 중이더라도 다른 cache hit나 miss를 처리할 수 있다. (그 수에는 제한이 있다.)
Pipelined Cache : cache를 파이프라인화 한다. 매 cycle마다 cache 요청을 할 수 있다.

멀티코어에서의 캐시
 - Coherence 문제
 - MSI 스누핑 프로토콜 (Invalid, Shared, Modified)
 - MESI 프로토콜 (MSI + Exclusive)
 - cache coherence 작업은 확장성 문제가 있다. Core 개수가 많은 경우 snooping 기반이 아닌 directory 기반으로 구현하기도 한다.

Story 13. if 문은 그냥 실행되는 것이 아니다

조건 분기문 : 조건이 만족할 때만 해당 목적지로 분기한다.
무조건 분기문 : 항상 해당 목적지로 분기한다.

직접 분기문 : 분기 목적지를 바로 얻을 수 있다.
간접 분기문 : 분기 목적지를 얻기 위해 메모리를 참조해야 한다.

분기 방향 예측 : 조건 분기문의 taken or not taken 여부를 예측
분기 목적지 예측 : 분기 목적지를 예측
투기적 실행 (speculative execution) : 불확실한 예측을 기반으로 명령어를 실행하는 것. 예측이 실패할 시 원 상태로 복구해야 한다.

분기 방향 예측
 - 2bit branch predictor
 - 히스토리를 이용한 분기예측 (Global History - BHR, Local History - BHR Table)
 - gShare (PC ^ BHR을 통해 얻은 값으로 엔트리를 고른다.)

프리디케이션 (Predication)
 - 컨트롤 의존성을 데이터 의존성으로 바꾸는 방법.
 - 분기 예측이 어렵고 분기문의 규모가 작을 때 유용하게 쓰일 수 있다.
 - x86의 CMOV등.. Itanium 명령어 구조인 IA-64는 모든 명령어에 대해 predication을 적용할 수 있다.

Story 14. 가상 함수에 담긴 복잡함

직접 분기문의 분기 목적지 예측
 - BTB (Branch Target Buffer) : 캐시랑 거의 비슷한 구조를 가진다. 보통 directed-mapped 형식으로 만들어진다.

간접 분기문의 분기 목적지 예측
 - iBTB (Indirect BTB), RAS(Return Address Stack)
 - 함수 리턴 : RAS를 이용해 예측한다.
 - 콜백 함수와 가상 함수, jump table : 다른 분기문의 실행 내역 History를 기반으로 하는 iBTB를 통해 예측.

Story 15. 효율적인 메모리 명령 실행 알고리즘

효율적인 메모리 연산의 실행
 - 메모리 의존성은 데이터 의존성과 달리 명령어 해독만으로 파악할 수 없다.
 - 메모리 의존성이 없는 것들에 대해 비순차 실행이 가능하도록 하기.

Load Store Queue (LSQ)
 - 메모리 명확화 (memory disambiguation) 문제를 푸는 장치.
 - Store-to-Load Forwarding : 데이터 Load시 이전에 수행된 Store로 부터 bypass로 값을 가져오는 것. (비록 Store가 아직 메모리에 반영되지 않았더라도)
 - MOB (Memory Order Buffer) 라고도 불린다.

메모리 의존성 예측과 투기적 실행
 - 메모리 의존성을 예측하고 투기적으로 실행한다.

포인터
 - 포인터는 메모리 의존성을 만들어 컴파일러 최적화를 힘들게 한다.
 - C99에서는 포인터에 restrict 키워드를 붙임으로서 포인터가 서로 다른 메모리 영역을 가지고 있음을 컴파일러에게 알려 더 많은 최적화를 하도록 할 수 있다.

Story 16. 메모리 레이턴시 감추기 : 프리펫처

소프트웨어 프리펫칭
 - 프로그래머나 컴파일러가 ISA가 정의하는 명령어를 이용해 직접 프리펫칭을 지시하는 것.
 - 프리펫칭 거리 : 최적의 프리펫칭 거리는 메모리 레이턴시를 감출 수 있을 만큼만 미리 수행되어야 한다.
 - Cache Line의 크기와 프리펫칭 거리, overhead를 고려해서 수행해야 한다.
 - Cache Miss를 예측하기 어렵기 때문에 한계가 있다.

포인터 기반 자료구조의 소프트웨어 프리펫칭
 - 그리디 프리펫칭 : 특정 노드에 인접한 노드만 프리펫칭 하는 것. (1보다 큰 프리펫칭 거리 만큼 프리펫칭하면 load-to-load dependence등으로 인한 overhead가 커서 비효율적이므로)
 - 히스토리 포인터를 이용한 프리펫칭 : 정확하게 프리펫칭 거리만큼 프리펫칭한다. 히스토리 포인터와 FIFO를 이용해 구현한다. 자주 바뀌지 않으며 같은 패턴으로 반복 순회하는 포인터 기반 자료구조에 효과적이다.
 - 데이터 선형화를 이용한 프리펫칭 : 순회하는 순서대로 연속적인 메모리에 노드를 할당하는 것. 매우 제한적으로 사용될 수 있다.

하드웨어 프리펫칭
 - 하드웨어가 자동으로 수행하는 프리펫칭.
 - 순차적 프리펫칭 : 인접한 캐시라인을 프리펫칭하는 것. 캐시 오염을 해결하기 위해 stream buffer를 이용할 수 있다.
 - 스트라이드 프리펫칭 : 접근하는 메모리 주소가 일정 간격으로 차이가 난다는 것을 탐지한다면 그 간격을 바탕으로 프리펫칭할 수 있을 것이다.
 - 마르코프 프리펫칭 알고리즘 : cache miss가 발생하는 메모리 주소의 히스토리를 바탕으로 프리펫칭하는 알고리즘. (특정 주소가 cache miss됐을 때 다음에 cache miss가 될 확률이 높은 메모리 주소들을 얻을 수 있다. 따라서 그 주소들을 프리펫칭하는 알고리즘)
 - 내용 기반의 하드웨어 프리펫처 : 캐시 라인을 읽었을 때 '메모리 주소'로 보이는 값이 있으면, 해당하는 주소를 프리펫칭하는 것. 포인터 기반의 자료구조에 대해서 좋은 성능을 보인다.

Story 17. VLIW로 살펴보는 두 변수 교환 방법

VILW (Very Long Instruction Word)
 - ILP를 하드웨어가 아닌 컴파일러가 찾아 명시적으로 명령어들의 순서를 배치해놓는 것에 기반을 둔다.
 - VILW 프로세서는 비순차가 아닌 순차 프로세서로서 구현이 된다.
 - 비순차를 구현하는 데 드는 하드웨어 자원들을 다른 곳에 활용할 수 있는 장점이 있다. 그리고 컴파일러가 ILP를 찾으므로 명령어 윈도우의 크기가 커서 일반적으로 더 높은 ILP를 찾을 수 있는 장점이 있다.
 - 하위 호환성이 부족한 단점이 있다. 실시간 정보를 알 수 없어 ILP를 찾는게 오히려 힘들어질 수 있다.

Story 18. 프로그래머의 새로운 과제 : 병렬 프로그래밍

주목할 만한 내용이 별로 없었다. (대부분 일반적인 병렬 프로그래밍의 개론적인 내용들 + WIN32 API, pthread, OpenMP, TBB, Ct에 대한 간단한 설명 및 예제였다.)
Work Stealing : 쉬는 스레드가 있으면 바쁘게 일하는 스레드가 일을 훔쳐와 처리하는 기법.
Ct (C for Throughput Computing) : 스루풋 컴퓨팅을 위한 C언어 확장. 데이터 병렬성을 쉽게 표현하여 작업을 병렬화할 수 있다.

Story 19. 골치 아픈 멀티스레드 버그 : 하이젠 버그

데이터 레이스 : 어떤 공유 데이터가 두 스레드 이상에게서 동시에 접근되는데 이 때 적어도 하나의 접근이 쓰기일 때를 말한다. 데이터 레이스가 무조건 버그라고는 할 수 없다. (탐지 툴의 예시 : 인텔 Parallel Studio의 Parallel Inspector)

대표적인 병행성 버그
 - 원자성 위반
 - 순서 위반

Story 20. 어려운 병렬 프로그래밍, 그리고 그 미래는?

가짜 공유 문제 (false sharing)
 - 실제로는 공유되지 않는 데이터이지만, 같은 cache line에 위치하게 되어 성능 저하 문제를 유발하는 것.
 - 데이터를 cache line 크기에 맞춰 align하여 해결할 수 있다.
 - 데이터 동적 할당 시에도 발생할 수 있다. 멀티스레딩에 적합한 메모리 할당자를 사용해야 한다.

Transactional Memory (TM)
 - 원자적으로 실행하고 싶은 부분을 키워드로 선언하면 된다.
 - 락과 달리 일단 실행시켜보고, 충돌이 발생했을 경우에는  rollback후 재 실행한다.
 - 재 실행이 힘든 (IO연산등) 작업들에 대해서는 주의해야 한다.
 - 원자성 위반의 경우 TM으로 인해 큰 효과를 볼 수 있다.
 - Software TM (STM) / Hardware TM (HTM)

스레드 수준 투기 (Thread-Level Speculation, TLS)
 - 일단 여러 스레드로 강제로 실행을 한 후, 충돌이 있다면 rollback 후 재 실행한다.
 -  TM과 흡사하나 TLS는 프로그래머가 코드를 작성하기 보단, 컴파일러가 적절하게 TLS를 활용한 멀티스레드 생성 코드를 넣는다.
 - 실제 하드웨어가 구현되지 않아 이론 상으로만 존재한다. (2010년 기준)