CPU, Pipeline (OOOE, Branch prediction)

🟣 CPU의 명령어 처리 구조

instrucion cycle (명령 주기) : Fetch → Decode → Execute

하나의 명령어를 인출하여 실행하는 데 필요한 일련의 활동.

 

 

 

 

 

사이클을 세부화 하면 4가지로 나눌 수 있음. 항상 실행 필요할 때만 실행

• 인출 사이클
• 실행 사이클
• 간접 사이클 (주소 지정 방식이 필요할 때)
• 인터럽트 사이클 (인터럽트 요구가 있을 때)

---

 

 

 

제어장치 (Control Unit, CU)

• -명령어 레지스터에 저장된 명령어 해독
• - 컴퓨터 시스템의 모든 동작을 제어하는 제어신호 생성

 

연산기/산술논리연산장치(ALU)

• - 데이터를 처리하는 기능 담당
• - 레지스터 혹은 주기억장치에 저장된 데이터에 대한 산술 연산 혹은 논리 연산 수행
• - 조합 논리회로로 구성(조합 논리회로 빌딩 블록)

조합 논리 회로 : 현재의 입력 신호에 의하여 출력(결과)가 결정되는 논리 회로

 

 

 

 

< Fetch Cycle > : 제어장치에서 실행 (Control Unit, CU)

 

▶ Fetch

• ①-1 프로그램 카운터에 저장된 주소를 MAR로 전달 [ T0 :  MAR <- PC ]

MBR : 메모리 버퍼 레지스터. 메모리로부터 읽은 자료를 넣어두기 위한 일시 기억 회로.

프로그램 카운터(PC) : 다음에 수행할 명령어의 주소를 포함하고 있는 레지스터.

현재의 명령이 실행될 때마다 그 레지스터의 내용에 1이 자동적으로 덧셈됨.

• ② MBR에 저장된 내용을 IR에 전달함. [T2 : IR <- MBR ]

IR : 명령어 레지스터. 현재 실행 중인 명령어를 기억하고 있는 중앙처리장치 내의 레지스터.

중앙 처리 장치의 인출 사이클에서 프로그램 카운터가 지정하는 주기억장치의 주소에 있는 명령어를 명령어 레지스터로 옮기면, 실행 사이클에서 명령어 해독기가 명령어 레지스터에 있는 명령어를 해독한다.

 

< Excute Cycle >

▶ Decode

③-1 명령어 해독기에서 Opcode(연산 코드)를 해석해 무슨 연산을 할지 결정

④ Operand(오퍼랜드)는 MBR을 넘어 주기억장치로 넘어감

 

⑤ 해독된 연산 코드가 ALU(=연산장치)로 넘어감.

 Operand(오퍼랜드) : 연산을 수행하는 데 필요한 데이터나 데이터 주소

 

▶ Execute : 해석된 명령어에 따라 필요한 연산 실행. (주기억장치로 넘어간 오퍼랜드를 연산장치로 가져옴.)

 

• 데이터의 이동 : CPU와 기억장치, I/O장치 간에 데이터를 이동
• 데이터 처리 : 산술, 논리 연산을 통한 데이터의 처리
• 데이터 저장 : 연산 결과 데이터나 입력 장치로부터 읽어 들인 데이터를 기억장치에 저장
• 프로그램 제어 : 프로그램의 실행 순서 결정

---

🟣 Pipelining

: 여러 명령어를 중첩시켜 실행시키는 기술

프로세서에서 성능을 높이기 위해서 명령어 처리를 여러 단계로 나누어 단계별로 동시에 수행하는 기술.

• Pipelining이 없이 명령어 처리

클록 사이클 당 한 단계에서 순차적 처리

 

명령은 5단계를 모두 거쳐 처리를 한 후에 다음 명령을 처리함.
각 단계에 1주기가 걸린다고 가정하면, 3개의 명령을 처리하는데 15주기가 걸림 → 비효율적

---

 

• Pipelining 명령어 처리

각 단계는 하드웨어의 다른 섹션에서 실행되기 때문에 명령을 Pipelining하여 효율성을 향상 시킴.
다양한 하드웨어 섹션이 각기 다른 명령어를 동시에 처리할 수 있도록 함.

3개의 명령을 처리하는데 7주기가 걸림 → 효율적

 

---

pipeline이 가장 효율적이려면 아래 조건을 만족해야 한다

•   각 단계별 처리 시간이 일정해야 한다. 
•   각 명령어의 처리 단계는 균일해야 한다. 그러나 실제로는 처리 시간일 일정하지도 않고 처리 단계가 균등하지 않아서 문제가 발생한다.

그러나 실제로는 처리 시간이 일정하지 않고, 처리 단계가 균등하지 않아 문제가 발생한다. ≪Hazard≫

 

---

🟣 Out-of-order-Execution (비순차적 실행)

(데이터 해저드 해결 방법)

명령어 수준에서 병렬성(Instruction Level Parallelism)을 찾아서 이를 비순차적, 즉 병렬 처리할 수 있도록 한 기술.

-Pipeline 내의 빈 공간이 생기는 것 방지, CPU가 최고 성능을 내도록 함.

 

명령을 비순차적으로 병렬 처리하기 위해서는 다음의 기술들이 필요하다

병렬 처리(parallel processing) : 다수의 프로세서들이 여러 개의 프로그램 혹은 한 프로그램에 분할된 부분들을 분담하여 동시에 처리하는 기술.

• Instruction Window (명령어 윈도우)
• Register Renaming (가짜 의존성 제거)
• Reservation Station (동적 명령어 스케줄링)
• Reorder Buffer (순차적 완료)

 

🔵Instruction Window (명령어 윈도우)

prossecer Pipeline에서는 명령어들이 스트림으로 처리됨.

명령어의 스트림에서 각 명령어들의 의존 관계 분석이 필요한데, 하나하나의 명령어를 순차적으로 분석하면 비효율적

▶ 명령어 윈도우(Instruction Window)가 필요함

명령어 스트림 속에서 일정한 숫자의 범위 내에서 ILP(병렬성)를 검사하여 비순차적으로 처리

 

명령어 스트림(Instruction stream) : 프로세서에 의해 실행되기 위해 순서대로 나열된 데이터들의 집합

 

 

① 명령어 하나가 명령어 윈도우 속으로 들어옴과 동시에 처리가 완료된 가장 오래된 명령어 하나는 빠져나감.

② 윈도우 내에서 명령어들을 처리함 (의존성 체크, 스케줄링 후 병렬실행, 이전 명령어 완료 기다림... 등)

③ 명령어 윈도우 내에서 가장 오래된 명령어가 빠져나가고, 동시에 다른 명령어가 들어옴.

 

 

🔵 Refister Renaming (가짜 의존성 제거)

 

가짜 의존성이라는 것은 코드에 사용된 레지스터를 보면 상하 코드가 의존적인 것처럼 보이지만, 의미적으로 따져 보면 실제로는 의존성이 존재하지 않는 경우를 말함

의존성 체크 과정에서 가짜 의존성이 발견되어 레지스터의 이름을 살짝 바꾸어주는 과정을 Rester Renaming이라고 부른다

 

🔵 Reservation Station(동적 명령어 스케줄링)

operand가 준비되면 명령어는 수행 가능.
operand가 준비되지 않은 명령어가 대기하는 곳이 Reservation Station이라는 Queue임.

 

Queue : 컴퓨터의 기본적인 자료 구조의 한 가지로, 먼저 집어넣은 데이터가 먼저 나오는 FIFO(First In First Out)로 지정하는 형식

Reservation Station에서 대기하는 명령어는 두 가지 핵심 작업을 함.

 

● Wake-up : Reservation Station 에서 대기하고 있는 어떤 명령어가  어떤 operand 를 기다리고 있었나 찾는 것을 말함. 매번 Reservation Station Queue에 있는 명령어들이 필요로 하는 Operand 들을 모두 체크한다. (Bottle neck point)

 

● Select : operand 가 준비되어 실행 가능한 상태의 명령어보다 사용 가능한 실행 장치의 숫자가 적은 상황이 있을 때, 실행 장치의 할당을 효과적으로 수행할 수 있도록 스케줄링하는 것을 말함 (Bottle neck point)

 

Bottle neck(병목 현상) : 시스템 전체의 성능이나 용량이 하나 혹은 적은 개수의 구성 요소나 자원에 의해 제한을 받는 현상

▶ 병목 현상과 복잡성 때문에 Reservation Station Queue의 크기를 무작정 늘려서 병렬성을 높이는 작업에 한계가 있음

Reservation Station이 존재함으로 해서 명령어들의 실행이 반드시 순차적이지 않고, operand 가 준비된 대로 비순차적으로 스케줄링되어 실행이 가능한 것.

 

Reservation Station에 명령어가 투입되는 순간부터 실행결과가 나오는 때까지는 비순차적일 수 있음

→ operand의 준비상태에 따라 동적으로 스케줄링하는 알고리즘이 바로 토마슐로(Tomasulo) 알고리즘

 

 

🔵 Reorder Buffer(순차적완료)

명령어 순서가 뒤섞여서 끝났더라도 프로그래머가 원하는 순서대로 결과를 보이는 과정이 필요함. 이때 Reorder Buffer 사용

Reorder Buffer에 실행이 끝난 명령어들을 모아뒀다가 원래의 프로그램 순서대로 차례차례 데이터를 저장해 줌

Reorder Buffer에는 당연히 원래 명령어의 순서대로 쌓아두어야 한다.

 

① Reorder Buffer 에 명령어를 넣어두는 시점 =  초기에 Reservation Station으로 명령어를 넣는 시점

② Reorder Buffer에 넣어두고 실행(연산)이 끝난 것들만 표시

③ 처리가 종료되면 표시가 된 명령들을 Reorder Buffer에서 원래 프로그램 순서대로 그 결과를 레지스터 등에 저장해 줌

 

 

---

Out-of-oder-Excution (비순차적 실행)으로 아래 명령어를 처리한다고 예를 들어보자

A=5
B=3
C=A+B
D=4

 

사진 1

사진 2

 

 

▶out-of-order-execution은 Meltdown 취약점 유발.

---

🟣 branch prediction(분기 예측)

(제어 해저드 해결 방법)

dynamic prediction : 프로그램 실행 중 history 기반으로 분기를 예측하는 것

 

a = e + f;
if (a == 0)
	b = 0;
else
	b = 1;

CPU는 독립적으로 실행할 수 있는 명령어들을 찾지만, 2번째 줄에 if문이 있어서 3번을 읽을지 5번을 읽을지 알 수 없음.

▶ 그래서 주어진 분기문이 참이냐 거짓이냐 하는 질문의 답을 예측함. =Branch prediction(분기 예측)

 

예를 들어,

분기 예측기가 a == 0일 확률이 높다고 예측했다면 → CPU는 그것을 믿고 3번째 줄의 명령어를 가져와 처리함.

이후 2번째 줄 명령이 완료되어

• a == 0이 맞다고 판명되면 다음 명령을 수행함.
• a == 0이 아니라고 판명되면 다시 되돌아가(Undo) 5번째 줄 명령이 수행되도록 함. 

---

분기 예측 기술의 두 가지 방법

● 분기 방향 예측

실행될 Pipeline 조건 분기문의 분기 여부(teken or not taken)를 예측하는 기법

 

정적 분기 방향 예측 : 정해진 규칙에 따라 사전에 분기를 지정

동적 분기 방향 예측 : 프로그램 실행 중 계산 이력에 따라 분기를 동적으로 예측

 

● 분기 목적지 예측

분기문이 어디로 분기할지 목적지 PC(Program Counter) 값을 예측하는 기법

 

▶Branch prediction은 Spectre 취약점 유발.

---

🟣 speculation execution (예측 실행)

불확실한 예측 기반, 더 나은 성능을 가져오는 방향으로 명령어를 처리하는 기법

예측에 기반하여 확실하지 않은 명령어를 미리 수행 → 결과 값이 예측 값과 다르면 이미 처리한 명령어 삭제

 

● 예측에 필요한 장치

미래 예측 장치 : 예측에 기반하여 확실하지 않은 명령을 미리 수행하는 장치

- 동적/정적 분기 예측, 이력 기반 분기 예측

 

ROB(Reorder Buffer)

결과가 확실하지 않아도 실행을 계속 진행시킬 수 있는 장치

 

Undo

예측이 틀렸을 때 원상태로 복구하는 장치

 

● 예측 실행 동작 원리

분기문 예측 실행 : 동적/정적 분기 방향과, 분기 목적지를 예측하여 명령어 실행

예측 성공 시 : 실행된 명령어의 결과를 저장하고 다음 명령어 수행

예측 실패 시 : 실행된 명령어의 결과를 취소하고 원상태로 복구(Undo)