기말 대비용 정리 노트 (Lecture 2)

해당 영상은 추석 보강용으로 촬영된 영상 바탕이다.

 

앞서 디지털 시스템에 대한 일반적인 것을 배웠는데 이제부터는 실제 시스템(아키텍처)을 살펴볼 것이다. 해당 과목을 통해서 하게 될 것은 CPU와 그 인근에 달린 고속 장비들에 대한 보안이다. Audio나 USB 같은 저속 장비들에 대한 보안은 다루지 않을 것이며, 오늘 할 강의는 프로세서 칩에 대한 부분이다.

 

프로세서 칩에는 여러 logic block이 포진해 있으며, 최근부터는 그래픽 관련 부분이 탑재되어 그래픽 블록, CPU core, IO 관련 블록으로 주로 나뉜다. CPU 중에서 핵심은 computational core이기 때문에 처음 시작할 때는 CPU core 내부에서 어떤 일이 벌어지는가를 중점적으로 보게 될 것이다.

복습 : 프로세서 코어의 기능

high level 언어로 프로그램을 짜면 컴파일러가 돌아가면서 각 칩에 맞는 binary code로 변환한다. 이러한 binary code 하나하나는 CPU가 이해, 동작할 수 있는 명령어(instruction)이며, 이렇게 명령어들의 집합이 정해져 동작하는 아키텍처를 Instruction Set Architecture라고 한다. ISA의 제일 기본적인 구성은 메모리에 올려놓은 instruction set으로 구성된 프로그램의 어디를 실행해야 하는지를 알려주는 Program Counter(PC), 데이터와 코드를 들고 있는 메모리, 메모리에 값을 읽거나 쓰면서 연산의 주체가 되는 레지스터이다. Instruction은 일반적으로 다음의 3가지 type으로 나눈다.

 

• Arithmetic & Logical : Input and outputs are registers
• Load & Store : Move data btw registers and memory
• Control flow : Change order of execution within a program, unconditional (jumps) or conditional (branches)

CPU의 Efficiency (Performance)

기본적인 execution은 프로그램의 instruction을 순서대로, 하나씩 수행하게 된다. 더 복잡한 execution도 있지만, 프로그램을 짜게 되는 사람의 mind에서는 sequentially & one at a time이 기본 형태일 것이다. HW가 정말 충실하게 이 order에 따라 실행을 하게 된다면 실행이 느릴 것이다. 이 때문에 HW 개발자들은 이를 개선하기 위해 계속 노력해왔다. 일단 CPU의 퍼포먼스 성능 측정은 어떻게 할 수 있을까? 다음과 같은 요소들을 정의해서

 

• IC : 프로그램 내의 실제 수행되는 instruction 개수 (while 같은 경우는 1개가 아닌 loop 개수 만큼)
• CPI : 한 instruction마다 얼마나 많은 cycle이 소모되는지 (= 1/IPC)
• CCT : 하나의 cycle이 차지하는 시간 (= 1/Frequency)

Execution Time = IC * CPI * CCT를 계산할 수 있다. 왜 굳이 이렇게 3분할을 해서 연산을 하는가하면 각각을 개선하기 위한 요소가 차별화되기 때문이다. IC를 개선하기 위해서 아키텍처가 할 수 있는 일은 많이 없다. 이는 프로그래머 또는 컴파일러가 해 줄 일이다. CCT는 circuitry와 제조 공정에 의해 dominant되는 부분으로서 사이클 수를 높이는 것은 HW인 칩의 문제이며, CPI 또한 아키텍처에 의해 개선될 수 있는 영역이기 때문에 이 둘을 주로 살펴볼 것이다.

 

아무런 문제 없이 instruction이 실행될 경우 예상되는 CPI가 base CPI이다. 그러나 실제로 프로그램이 실행되다보면 앞선 명령어와의 관계로 인한 대기 등 여러가지 원인에 의해 지연이 생기게 된다. 이러한 지연에서 소모되는 cycle을 stall CPI라 하며 총 CPI는 base CPI와 stall CPI의 합이다. Stall이 생기는 원인을 분석하면 크게 다음과 같은 원인이 있으며,

 

• Data Hazard : Data dependancy가 있는 명령어 사이에서 발생하며, RAW, WAW, WAR dependancy가 여기에 해당
• Control Hazard :  jump와 branch의 방향성을 결정하기까지 다음 수행될 명령이 대기하게 된다. (Control dependancy)
• Memory Latency : 메모리에서 값을 받아오는 속도가 느려서 발생하는 현상
• Structural Dependancy : 한정된 자원에 일이 몰려서 발생

성능을 올린다는 것은 stall 발생으로 생기는 stall CPI를 줄이는 것이다.

 

이번 강의에서 주로 다룰 내용은 아니지만 CPU의 평가 척도에는 power efficiency도 있다. 데이터 센터와 모바일에서 중요하게 여기는 요소 중 하나로, 3% performance improvement per 1% power increment라는 룰이 있듯, 성능이 올라가더라도 power를 너무 많이 잡아먹으면 비효율적이게 된다.

 

---

 

아래 구조는 프로세서에서 명령을 처리하기 위한 가장 기본적인 구조이다. 한 번에 하나의 instruction이 실행된다.

해당 구조에서는 한 cycle clock time(CCT)을 하나의 instruction이 전 단계를 통과할만큼 길게 만들어야 했으며, 하나의 instruction이 특정 단계를 사용하지 않고 있음에도 다음 instruction이 대기해야 했다.

 

이를 가속하기 위해 전 과정을 latch를 사용하여 작은 단계로 분리하고, 한 cycle clock time마다 하나의 단계가 실행되도록 만들며, 각 instruction의 실행을 중첩시킨다. 이것이 첫 강의에서 배운 Pipelining이다. 해당 관점에서 볼 때, CPI는 여전히 1이지만, CCT는 단계를 쪼갠 만큼 줄어들게 된다. Pipelining은 Dependancy가 없는 작업들의 경우, 굳이 한 작업이 완료가 될 때까지 기다리지 않고 실행시킬 수 있다는 Instruction level parallelism의 원칙을 따라간다.

 

1985년 개발된 5단계 파이프라인 MIPS는 Fetch, Decode, ALU, Memory, Write Register로 단계를 분류하며, 간단하고 elegant하면서도 WAW와 WAR hazard가 없이 base CPI를 1로 둘 수 있어 지금도 널리 쓰인다. 그러나 정말 모든 것이 잘 풀려서 stall이 없다 할지라도 IPC가 1이라는 것은 다른 관점에서 볼 때는 단점일 수 있다. 또한 memory instruction 같이 high latency instruction에 대해서 처리가 미숙하며, 하나의 instruction에 지연이 걸리면 pipeline에 올라와있는 다른  instruction에도 영향이 갈 수 밖에 없다는 특징이 있다. 이러한 기본 형태의 MIPS를 개선하기 위한 많은 아이디어가 나왔다.

 

• 단계를 더 많이 쪼갠다. (deeper pipeline, lower CCT)
• 한 번에 여러 instruction을 fetch해서 처리한다. (wider pipeline) IPC가 증가할 여지가 있다.
• 앞의 명령어가 stall하더라도 뒤에 명령어의 stall을 줄이기 위한 Diversified pipeline, OOO
• Control dependency를 줄이기 위한 branch prediction (speculation)

우선 Deeper pipeline을 살펴보자. 단순히 생각하면 단계를 더 많이 쪼갤수록 CCT를 더 많이 낮출 수 있을 것이라 생각할 수 있다. 그러나 특정 작업은 중간 결과를 내기 위해 일정 사이클을 반드시 소모할 수 밖에 없으며, 이를 무리하게 나눌 경우, 후처리 때문에 더 많은 사이클을 소모하게 된다. 거기다가 이러한 작업이 모두 균일하게 나눠지지 않기 때문에 일률적으로 모든 작업을 나누는 것이 어렵다. 더욱 큰 문제로는 단계를 분할하면, 다음 단계에 이전 단계의 결과를 보내기 위해 임시적으로 저장하는 pipeline register에서 delay가 발생하면서 추가적인 작업 시간이 발생한다. 따라서 전체를 N단계의 pipelining으로 쪼갠다고 하면 overhead 시간 O가 더해지며, CCT는 기본 T에서 T/N + O로만 떨어진다. 성능 개선율은 N이 무한으로 갈수록 T/O로 수렴하기 때문에 너무 많이 단계를 쪼개는 것은 의미가 없으며, 실제로는 많아봐야 25단계를 넘지 않는다.

 

다음으로 폭을 넓히는 wide pipeline(혹은 superscalar pipeline)을 생각해보자. 해당 방식의 문제는 general purpose에서는 4개까지가 한계라는 것이다. 주요한 문제는 control dependency 때문인데, 일반적인 프로그램의 경우 8개의 instruction마다 branch 문이 첨가되어 있기에 아무리 많이 끌고 오려고 해봤자 dependency에 걸려 stall될 수 밖에 없기 때문이다. 또한 fetch한 instruction간 data dependency 문제도 있는데, 기존에는 pipeline 위 앞선 instruction과만 dependency 문제가 있었지만, wide pipeline의 경우 옆 pipeline 까지의 관계성을 고려해야 하기 때문에 더 dependency가 있을 가능성이 높아진다. 따라서 이 또한 무작정 늘린다고 성능이 계속 좋아지지는 않는다. 

 

Diversified Pipeline의 경우, 단순하게 단계를 나누거나 한번에 실행되는 instruction의 개수를 늘리는 것이 아닌 instruction의 특성을 분석해서 맞춤형으로 만드는 것에 가깝다. 그림과 같이 서로 다른 연산에 대해 다른 파이프라인 단계를 잡아서 실행을 시킬 수 있다.

느린 FP instruction이 독립적인 정수 연산과는 무관하게 움직이는 등 불필요한 stall을 방지할 수 있는 특성이 있으나, WAW hazard가 발생할 가능성이 있고, OOO exception이 생길 여지가 있다. 

 

최근 프로세서 코어의 fundamental한 구조는 위 요소들을 합쳐서 만들어졌으며, Out of Order Execution을 도입하여 아래와 같은 구조로 만들어진다. 다만 훨씬 더 많은 유닛과 함께 더 깊은 단계가 있을 뿐이다.

해당되는 execution unit에 fetch하고 decode한 instruction을 dispatch한다. 읽어와서 분석이 끝나고 dependency가 없다고 판별되면 Out of Order로 명령이 수행되고, 최종적으로 이들을 취합해서 내보내기 전에 순서를 잡기 위해 reorder buffer가 존재한다. Retirement logic은 buffer의 맨 앞, 즉 가장 우선적으로 들어온 명령의 결과가 나오기를 대기하다가 만약 맨 앞이 채워지면 후발 명령이 수행되었는지를 보고 결과를 반영한다. 이는 만약 첫 번째 명령이 invalid할 경우 뒤 명령어의 결과는 반영하지 않고 reorder buffer 단에서 삭제하기 위해서이다.

 

Out of Order 코어에서 가장 타격이 큰 것은 Control Dependency와 Branch penalty이다. Wide pipeline 방식으로 4개씩 명령어를 들고 와서 dispatch하고, 실행 사이클이 긴 작업이 이미 스케줄이 된 상태이지만 실제로는 fetch한 명령으로 분기하는 경우가 아닌 때는 들고 온 작업은 모두 무용지물이 된다. 앞서 언급한대로 일반적인 프로그램은 4~8개의 instruction 마다 분기가 이루어지기 때문에 이는 critical한 issue이다. 핵심은 decode하여 들어온 instruction이 분기였다는 것을 알아차리더라도 그 시점에서는 이미 늦었다는 것이다. 이미 여러 명령이 같이 fetch되어 dispatch 직전일테니 말이다. 따라서 fetch가 되는 순간에 branch가 있는지 여부를 판단할 수 있어야 하며, 점프할지의 여부와, 점프한다면 어디로 할 것인지를 알 수 있어야 한다.

 

branch 여부와 점프 여부 판단을 위해 할 수 있는 가장 간단한 방법은 Branch History Table이다. 다음 branch의 결과는 이전과 비슷할 것이라는 아이디어를 채택한 것으로, instruction을 가져올 때의 주소중 하위 m 비트에 따라 2^m bit만큼의 테이블에서의 위치를 찾아 그 값이 0이면 이전에 점프하지 않은 것이며, 1이면 점프한 것이다. 만약 이번에 예측이 틀렸다고 한다면 해당 엔트리를 업데이트한다. 문제는 테이블과 주소의 크기는 제한되어 있기 때문에 상위 비트가 다르더라도 하위 비트가 같으면 동일한 엔트리로 연결되어 aliasing 문제가 발생한다는 것이다.

 

현실에서 가장 많이 쓰이는 것은 Branch Target Buffer이다. BHT와 마찬가지로 하위 비트로 엔트리를 찾는것은 동일하지만 상위 비트들을 tag 값으로 씀으로 상위 비트가 상이하면 해당 정보를 무시하는 식으로 완전히 잘못된 주소로 인한 aliasing 문제를 방지한다. 또한 이 구조는 단순히 점프 여부만을 나타내지 않고, 어디로 뛰었는지를 저장함으로서 더 많은 정보를 포함한다. 만약 주어진 주소에 해당한 엔트리로 찾아가봤더니 invalid하다면, 이는 애초에 branch가 아니거나, branch가 맞지만 뛰지 않아 단순히 PC가 increment 되었다고 해석할 수 있다. Branch Prediction을 활용하여 한 쪽 방향으로 prediction을 편향시켜서 잘못된 주소로 점프시키는 공격 기법이 있다. 이는 나중에 다시 언급될 것이다. 

 

---

Precise exception & Re-order buffer

Pipeline이 있더라도 exception은 single-cycle 프로세서에서 pipeline이 없을 때와 마찬가지로 일어나야 하며, exception이 발생한 지점을 기준으로 그 이전의 코드는 모두 문제없이 수행되며, 그 이후의 코드는 실행이 되지 않은 것처럼 되어야 한다. 이를 precise exception이라고 하며, 앞서 언급했듯이 OOO는 imprecise exception의 문제를 내포한다. 이를 해결하기 위해  re-order buffer가 있는 것이며, OOO에 의해 순서가 뒤바뀌어 실행된 것들을 정렬하는 역할을 한다.

 

---

 

모든 최근 프로세서의 근본은 위 형태를 따라가며, 문제 또한 공유한다. 

 

• Power consumption : 높은 클럭수와 OOO 로직이 심화될수록 더 많은 파워를 소모한다
• Complexity : 너무 복잡한 구조는 디자인과 디버깅하기 난해하다.
• Limited ILP : 프로그램 자체가 instruction 간 dependency가 너무 높은 경우 마땅히 최적화할 방법이 없다. high level에서 low level로 내려오면 dependency가 더해지기 때문에 근본적인 한계가 있다.
• Clock frequency : 클럭 수를 높이는데에 한계가 있다.
• Branch prediction & memory latency : prediction은 틀릴 때가 항상 있고, 최소한의 latency는 없앨 수 없다.

이러한 여러 한계점에 부딪혀 싱글 프로세어 아키텍처에서 멀티 코어로의 변화를 꾀하며 parallel 프로그래밍이 확산되었다. 이 중 가장 간단한 것은 SIMD (Single Instruction Multiple Data)로, 한 사이클에 같은 여러 연산을 동시에 수행하는 명령으로, data parallel processing을 통해 compute throughput을 개선한다.

 

예전 칩(2008)과 비교적 최근 칩(2015)을 비교하면 핵심적인 아키텍처 면으로는 크게 달라진 것은 없으며, Cache 사이즈가 늘어나고, 가상화, 그래픽, SGX 등의 보안 유닛이 추가되는 등 feature 중심의 변화가 일어나는 것을 확인할 수 있다. 따라서 코어의 기본적인 아키텍처는 이 정도로만 이해해도 현재와 큰 차이가 없기 때문에 이 정도 선에서 설명을 마칠 것이다. 

요약

Modern processor cores rely on a handful of techniques

 

• Pipelining & parallelism
• Speculation & OOO execution (For branches, memory dependencies, etc; Reordering used to get precise exception)
• Caching (Instruction, data, page table)
• Indirection (Renaming, page tables)

From the system point of view the processor is

 

• A high frequency, high power consumption device
• That requires high memory bandwidth
• And often needs low memory latency