컴퓨터 구조 및 설계 - Chapter 4. The Processor

Chapter 4. The Processor

ㆍProcessor의 내부 구조를 이해할 수 있다.

4.1 - Introduction

4.2 - Logic Design Conventions

4.3 - Building a Datapath

4.4 - A Simple Implementation Scheme

4.5 - An Overview of Pipelining

4.6 - Pipelined Datapath and Control

4.7 - Data Hazards: Forwarding versus Stalling

4.8 - Control Hazards

4.9 - Exceptions

4.10 - Parallelism via Instructions

4.11 - Real Stuff: The ARM Cortex-A8 and Intel Core i7 Pipelines

4.12 - Going Faster: Instruction-Level Parallelism and Matrix Multuply

4.13 - Advanced Topic: An Introduction to Digital Design Using a Hardware Design Language to Describe and Model a Pipeline and More Pipelining Illustrations

4.14 - Fallacies and Pitfalls

4.15 - Concluding Remarks

(목차를 블록 선택 후, Ctrl+F로 탐색 가능 - 브라우저에 따라 다를 수 있음)

---

<4.1 - Introduction>

 

 

 

Introduction

 

ㆁCPU 성능의 요소(factor)

　＊Instruction count(명령어 수)

　　ㆍISA(Instruction set Architecture)와 컴파일러에 의해 결정

　＊CPI(Cycle Count per Instruction)와 Cycle Time

　　ㆍCPU 하드웨어에 의해 결정

 

ㆁMIPS 구현방식을 2가지의 형태로 배워볼 것

　＊간소화된 버전

　＊그보다는 좀 더 현실적인 pipeline화된 버전

 

ㆁ구현에 실제 MIPS의 모든 명령어를 사용하진 않고, 일부분을 사용할 것임.

　(하지만, 주로 사용되는 명령어들이고, 대부분의 동작을 구현 가능하므로..)

　＊메모리 참조(memory reference): lw, sw

　＊산술/논리(arithmetic/logical): add, sub, and, or, slt

　＊제어 이동(control transfer): beq, j

 

 

 

Instruction Execution

 

ㆁ프로그램에 메모리에 로드되면 instruction들은 instruction memory에 순서대로 주소를 가지며 위치함.

 

ㆁPC(Program Counter, 현재 실행하는 명령어의 메모리 주소를 가짐(정확히는 다음번)) ↔ instruction memory.

　＊PC에 담긴 주소로 instruction memory에서 instruction을 읽어오는 것을, fetch instruction이라고 함.

 

ㆁ레지스터 번호 ↔ 레지스터 뭉치

　＊instruction에서 레지스터 번호($at, $t0, $s0, ...)를 통해 레지스터에 접근하여 값을 읽어오는 것을 read register.

 

ㆁinstruction 종류(class)에 따라..

　＊계산에 ALU를 사용하기도 함.

　　ㆍ산술 계산

　　ㆍload/store를 위한 메모리 주소 계산

　　ㆍbranch 대상 주소 계산(offset)

　＊메모리에 접근하여 데이터를 load/store하는 명령어.

　＊PC ← 대상주소(점프류) / PC+=4(순차적 진행)

 

 

 

CPU Overview

개략도

간략하게 표현함

＊실제로는 여러 선이 함께 만날 수 없음

　ㆍ원래는 Multiplexer(MUX)를 써서 그 중 하나의 신호를 선택함.

＊Control

　ㆍ각각의 하드웨어 모듈(레지스터, 메모리, ...)이 어떻게 동작하는지를 제어해주는 컨트롤을 만들어주는 회로.

　ㆍ명령어를 읽어서 해당하는 제어 신호를 만들어냄.

 

 

 

---

<4.2 - Logic Design Conventions>

일반적인 논리 회로의 디자인을 복습

 

 

 

Logic Design Basics

 

＊정보는 binary(0, 1)로 인코딩됨

　ㆍ저전력 = 0, 고전력 = 1.　_-_-_-_-

　ㆍ하나의 비트 표현마다 한 개의 선(wire)이 필요.

　ㆍ따라서, 멀티비트 데이터는 multi-wire bus들로 인코딩됨

 

＊combinational element(조합 요소)

　ㆍ데이터(목표)에 동작함.

　ㆍoutput은 input의 조합.

 

＊state(sequential) element(상태/순서적 요소)

　ㆍ정보를 저장(store).

 

Combinational Elements

조합 요소

 

＊AND-gate

　ㆍY = A & B

 

＊adder

　ㆍY = A + B

 

＊multiplexer

　ㆍY = S ? |0 : |1

 

＊arithmetic/logic unit

　ㆍY = F(A, B)

 

Sequential Elements

순서적 요소

＊레지스터: 데이터를 회로에 저장(store)

　ㆍclock 신호(signal)를 사용하여 언제 저장된 값이 업데이트 되는지 결정

　ㆍEdge-triggered: clock이 0에서 1로 변할 때(rising-edge) 업데이트

　　(※ falling-edge에서 업데이트시킬 수도 있음. 정하기 나름. 여튼 edge에서.)

 

＊Combinational Elements는 input과 규칙에 의해 output이 결정되었으나,

　Sequential Elements는 현재값과 input, clock 타이밍에 의해 output이 결정.

　ㆍ레지스터, 메모리 등에 사용.

 

 

 

Clocking Methodology

방법론

＊Combinational logic은 clock cycle동안 데이터를 변형(transform)한다.

　ㆍclock edge간에. 그 사이에.

　ㆍstate element들로부터 input이 되고, output은 또 state element가 된다.

　ㆍ가장 지연이 긴 시간(longest delay, 가장 느린 logic)이 clock period(클럭 주기)를 결정한다.

 

 

 

---

<4.3 - Building a Datapath>

 

 

 

Building a Datapath

 

ㆁDatapath

　＊데이터가 흐르는 경로

　＊연산을 위한 데이터든, 그 결과든 흘러서 어디론가 전달되거나 저장되거나 해야함.

　＊CPU에서, 프로세스 데이터와 주소들의 요소가 전달되는 길.

　　ㆍ레지스터, ALU, MUX, 메모리, ... 등의 모듈들이 연결되는 통로

 

ㆁ우리는 MIPS datapath를 순차적으로 만들어 볼 것임.

　＊개략도의 디자인을 좀 더 정제(refine)할 것임.

 

 

 

Instruction Fetch

(여기에는 안나왔지만, 점프를 위한 PC 값 변경 요소도 있어야할텐데..??)

 

 

 

R-Format Instructions

MIPS에서 R-Format은 3개의 레지스터(rs, rt, rd)를 사용했었음.

(좌) 레지스터 뭉치 / (우) ALU

＊레지스터

　ㆍ산술적/논리적 작업을 수행

　ㆍ2개의 read 레지스터

　ㆍ결과를 write 레지스터에 씀.

 

＊ALU(Arithmetic/Logical Unit)

　ㆍ레지스터에서 나온 2개의 Read data input들이 들어감.

　ㆍ결과는 다시 레지스터로 write data로써.

　(레지스터에 쓰는건 write data.

　 레지스터에서 다른 곳으로 데이터가 가는 것=레지스터의 데이터를 다른 곳에서 쓰는 것이 read data.)

 

 

 

Load/Store Instructions

I-Format

＊대상 레지스터에서 읽음(read)

＊16-bit의 offset을 이용하여 주소를 계산

　ㆍ주소 계산에 ALU를 사용.

　ㆍALU는 32-bit이기 때문에, 32-bit로 확장해서 사용.

　　(offset은 -/+가 있으므로, sign-extend로 부호를 유지한 채 확장)

＊Load: 메모리를 읽고, 레지스터를 업데이트. (메모리에서 레지스터로. 메모리 기준 read. 빠르게 쓰려고 불러오기.)

＊Store: 레지스터의 값을 메모리에 기록. (레지스터에서 메모리로. 메모리 기준 write. 영구용으로 저장.)

 

 

 

Branch Instructions

I-Format

ㆁ대상 레지스터에서 읽음(read)

　ㆍ이 두 값을 비교

 

ㆁ피연산자(operand, 위의 두 값)를 비교

　＊ALU를 사용. 두 개를 뺀 결과를 Zero와 검사하여 output 발생.

　　ㆍZero와 같으면 뺀 게 0이니, output은 1(같다).

　　ㆍZero와 다르면 뺀 게 0이 아니니, output은 0(다르다).

 

ㆁ점프한다면 대상 주소(target address)도 계산해야 함.

　＊I-format instruction의 address 부분에 담긴

　　16비트의 정보(displacement. 얼마나 위(-)아래(+)로 움직일지)를

　　32비트로 확장하기 위해 sign-extend로.

　＊그리곤 2번 shift left함(*4). (word(32-bit) displacement)

　　ㆍ원래 PC + offset*4 형태의 PC-relative addressing 방식임.

　　　(주소가 4-byte씩이니.. 즉, 위에서 구한건 몇 "칸"이지, 몇 byte는 아니었던.)

　＊계산된 결과를 PC에 더함(PC-relative addressing)

　　ㆍ참고로, PC에는 이미 현재 명령어의 다음 주소인 PC+4 상태이므로(instruction fetch에서 이미 더해진),

　　　+4를 감안하여 주소를 계산.

　　ㆍPC-relative addressing에 대한 상세한 설명은 Chapter 2 복습.

 

 

 

Composing the Elements

요소들을 구성하기(합치기)

 

＊각 요소들을 통합하여 한 clock cycle에 동작할 수 있도록 한다.

 

＊한 clock cycle에 하나의 instruction만 실행한다.

　ㆍ각 datapath 요소는 한 번에 하나의 기능만을 수행할 수 있다.

　ㆍ그러므로, data memory와 instruction들을 분리해야 한다.

　　(그렇지 않다면 하나의 명령어가 동시에 접근하려고 함)

 

＊data source가 교차하는 곳에서는 multiplexer(MUX)를 사용하여 다른 instruction에 다른 경로로 대응할 수 있도록 한다.

 

 

 

R-Type/Load/Store Datapath

 

Full Datapath

Single-cycle로 돌아가는(간소화된 버전의) MIPS의 구현 회로

 

---

<4.4 - A Simple Implementation Scheme>

간단한 구현 개요

 

 

ALU Control

Arithmetic Logical Unit

 

＊ALU는 다음에 쓰인다.

　ㆍLoad/Store: F = add

　ㆍBranch: F = subtract

　ㆍR-type: F는 funct field에 따라 다르다.

ALU Control	기능
0000	AND
0001	OR
0010	add
0110	subtract
0111	set-on-less-than
1100	NOR

 

＊opcode로부터 2-bit 부분(전체X)을 가져와서 ALUOp로 도출한다.

　ㆍcombinational logic을 사용해서 ALU control을 만들어낸다.

opcode	ALUOp	Operation	funct	ALU function	ALU control
lw	00	load word	xxxxxx	add	0010
sw	00	store word	xxxxxx	add	0010
beq	01	branch equal	xxxxxx	subtract	0110
R-type	10	add	100000	add	0010
		subtract	100010	subtract	0110
		AND	100100	AND	0000
		OR	100101	OR	0001
		set-on-less-than	101010	set-on-less-than	0111

 

 

 

The Main Control Unit

 

＊control 신호는 instruction으로부터 얻어진다(instruction에 의해 도출된다).

 

 

 

Datapath with Control

 

 

 

R-Type Instruction

 

R-Type Instruction의 Data 및 Control 흐름

 

 

 

Load Instruction

 

Load word Instruction의 Data 및 Control 흐름

 

 

 

Branch-on-Equal Instruction

 

Branch Instruction의 Data 및 Control 흐름

 

 

 

Implementing Jumps

＊word address(직접 주소)를 사용한 점프

＊concatenation(이어붙이기) 방식으로 PC(Program Counter)를 업데이트

　ㆍ26-bit의 address

　ㆍ위에 left shift를 두 번하여 *4의 결과(28-bit)

　ㆍ현재 PC(Program Counter)의 상위 4비트 뒤에 위를 합쳐서("old PC" & "address*4"), 총 32-bit.

＊opcode로부터 해석된(decode) 추가적인 control 신호(signal)이 필요하다.

 

 

 

Datapath with Jumps Added

점프가 추가된 데이터경로

 

Adding the Jump Operation

 

 

 

Performance Issues

 

＊가장 지연시간이 긴 부분(longest delay)가 전체 클럭 주기(clock period)를 결정한다.

　ㆍ특히 치명적인 경로(경로가 길어서 delay가 클 확률이 높은): load instruction

　ㆍinstruction memory → register → ALU → data memory → register

 

＊다른 instruction에 다른 주기로 실행할 수 없다.

　ㆍ모든 instruction은 한 clock cycle에 실행되어야 하며, 모두 같은 clock cycle time이어야 한다.

 

＊설계 원칙(design principle)을 위배한다.

　ㆍmaking the common case fast(가장 일반적인, 자주 사용되는 경로를 빠르게 하라)를 위배.

　ㆍ가장 느린 것에 맞춰지니까.

　ㆍ자주 사용되는 경로를 빠르게 하려고 해봤자, 가장 느린 것에 맞춰짐. 50을 10으로 줄여봤자, 100이 존재하면 헛수고.

 

＊우리는 pipelining을 통해 성능을 향상시킬 것이다.

 

---

<4.5 - An Overview of Pipelining>

 

 

 

Pipelining Analogy

유추

 

＊pipeline화된 빨래: 겹치는 실행.

　ㆍ병렬처리(Parallelism)은 성능을 향상시켜준다.

병렬화의 예시

 

＊4번의 연속된 작업

　ㆍ속도향상

　　= 8 / 3.5 = 2.3배의 성능향상

＊계속(continuous):

　ㆍ속도향상

　　= 2n / 0.5n +1.5(pipeline이 꽉 찰 때까지 걸리는 시간) ≒ 4

　　= stage(pipe)의 수. "stage의 수"배 만큼 성능향상

 

 

 

MIPS Pipeline

 

＊5개의 stage. stage마다 다음 중 하나의 단계를 수행함.

　1. IF: 메모리로부터 Instruction Fetch (메모리로부터 명령어 불러옴)

　2. ID: Instruction Decode & register read (명령어 해석, 레지스터 read)

　3. EX: EXcute operation(작업 실행) 혹은 calculate address(주소 계산)

　4. MEM: access MEMory operand (메모리에 접근)

　5. WB: Write result Back to register (레지스터에 결과를 다시 기록)

 

 

 

Pipeline 성능

 

＊각 stage별 시간을 측정해보면,

　ㆍ레지스터 read나 write에는 각각 100 pico(10^(-12)) second 가 소요됨.

　ㆍ다른 stage들은 200ps.

Instruction	Instr fetch	register read	ALU operation	memory access	register write	총 시간
lw	200ps	100ps	200ps	200ps	100ps	800ps
sw	200ps	100ps	200ps	200ps		700ps
R-Format	200ps	100ps	200ps		100ps	600ps
beq	200ps	100ps	200ps			500ps

＊pipeline화된 데이터경로와 sinle-cycle의 데이터경로를 비교해보면,

　ㆍsingle-cycle에서는 총 소요시간인 800ps 그대로.

　ㆍpipelined에서는 가장 소요시간이 긴 200ps.

 

 

 

Pipeline Speedup

 

＊만약, 모든 stage들이 비슷한 처리시간을 갖는다면,

　ㆍ즉, 모두 같은 시간이라면 "stage의 수"배의 성능향상 효과.

총 instruction의 모든 시간 기준. 단일X.

＊모든 stage가 균등하지 않다면, 속도향상의 효과는 더 적을 것이다.

　ㆍ가장 느린 stage에 맞춰지므로.

　ㆍ총 시간이 800ps이지만, 한 stage가 700ps라면, 다른 stage는 대기해야하고 결국 700ps..

 

＊속도향상은 throughput을 늘려서 얻은 결과이다.

　ㆍ병렬식으로 동시에 여러 instruction을 실행시킴으로써.

　ㆍ지연시간(latency, 각 instruction 하나 실행에 걸리는 시간) 자체는 줄어들지 않음.

 

 

 

Pipelining and ISA Design

 

ㆁMIPS ISA는 pipelining에 적합한 구조임.

　＊모든 instruction은 32-bit임.

　　ㆍ한 cycle 안에 fetch하고 decode하기 쉬움.

　　ㆍc.f. x86: 1~17-byte(8~136-bit)의 다양한 길이

　＊적은 종류의, 규격화된(regular) instruction format.

　　ㆍ한 번에 decode하고 레지스터를 read 가능

　＊Load/Store addressing

　　ㆍ주소 계산은 3번째 stage에서, 메모리 접근은 4번째 stage에서 이루어짐.

　　ㆍ즉, stage별로 다른 작업을 수행할 수 있음.

　＊memory operand의 정렬(alignment. 주소가 4byte씩 되어있다.)

　　ㆍmemory access는 한 싸이클 안에 이뤄진다.

 

 

 

Hazards

위험

 

＊다음 싸이클에서, 다음 instruction이 실행되는 것을 막아버리는 상황이 발생할 수 있다.

　즉, 매 cycle마다 instruction을 실행해야 할텐데, 그렇지 못하는 상황이 발생할 수 있다.

 

＊Structure Hazard(구조적 위험)

　ㆍinstruction을 수행하기 위해 필요한 하드웨어 자원이 사용중(busy)일 수 있다.

 

＊Data Hazard(데이터 위험)

　ㆍinstruction을 수행하기 위해 필요한 데이터가 있는데,

　　다른 instruction이 데이터를 read/write 하고 있다면(그 데이터가 busy 상태라면),

　　완료하기까지 기다려야 한다.

 

＊Control Hazard(제어 위험)

　ㆍ어떤 instruction을 수행하기 위해 다른 instruction의 결과에 의존하는 경우.

　　제어 행동을 결정하는 것이 이전의 instruction에 의존하는 경우.

 

 

 

Structure Hazards

구조적 위험(하드웨어)

 

ㆁ하드웨어 자원을 이용하는 것에서의 충돌

 

ㆁ단일(single) 메모리를 사용하는 MIPS pipeline에서

　＊Load/Store 명령은 data 접근을 위해 memory에 접근한다.

　＊instruction fetch도 instruction을 가져오기 위해 memory에 접근한다.

　＊서로 동시에 진행될 순 없으므로, 한 쪽은 대기를 해야하고, 해당 cycle을 지연(느리게 하다, stall)시킬 수 있다.

　　ㆍpipeline에 "bubble"을 야기할 수 있다.

　　　(아무 것도 하지 않는.)

 

ㆁ그러므로, pipeline화된 datapath는 instruction memory와 data memory가 분리되어야 한다.

　(메모리에서 instruction 영역과 데이터 영역의 분리)

　＊혹은 instruction과 data cache를 분리시키든가

 

대부분의 Structure Hazard는 resource의 부족으로 인해 발생하며,

resource를 추가하면 해결되는 경우가 많음.

 

 

 

Data Hazards

데이터 위험(데이터)

 

＊instruction은 다른 instruction이 데이터에 접근하는 것이 완전히 끝나는 것에 의존적이다.

　(해당 데이터가 사용 중이면, 대기해야 한다.)

　ㆍadd　$s0, $t0, $t1

　　sub　$t2, $s0, $t3

 

2stalls. 2-cycle 공백 발생.

 

 

 

Data Hazards --- Forwarding (aka Bypassing)

 

＊계산된 직후의 결과를 바로 사용(레지스터에 저장되기 전에 곧바로)

　ㆍ레지스터에 write back되는 것을 기다리지 않음(store까지 기다리지 않음).

　ㆍdatapath에 추가적인 연결이 필요하다.

 

 

 

Data Hazards --- Fowarding --- Load-Use Data Hazard

 

＊항상 forwarding(aka bypassing)으로 모든 stall을 피할 수는 없을 수도 있다.

　ㆍ결과가 필요한 순간에 아직 계산이 완료되지 않았다면.

　ㆍ제 때에 값을 끌어올 수도 없이 "존재하지도 않는다면" 활용도 불가능.

결국 1cycle의 stall을 피하지 못한 경우

lw　$s0, 20($t1) 명령어에는,

...,

20($t1)의 주소를 ALU에서 계산,(이건 수행했음)

그 주소를 토대로 MEM에 접근,(이제 접근 중이라 값을 다 못 가져옴)

그 곳의 값을 $s0에 load.

 

어쨌든 최대한 줄이려고 해도(레지스터에 write back 전에 빼오려고 해도),

MEM에 접근 이후에나 원하는 값을 알 수 있음.

최대한 줄여도 1cycle의 stall이 발생.

 

 

 

Data Hazards --- Code Scheduling to Avoid Stalls

code scheduling으로 stall을 피하기

 

＊forwarding은 극한적으로 값의 생성 시점에 집중하여 값을 당겨온 것이었고,

　(하드웨어적으로 추가적인 연결로를 만들어서라도 값을 미리 쓰겠다는)

　이 방법은 "값 때문에 대기할거면 다른 일을 미리 해두면 되지"라는 방식.

　코드의 효율성을 높이는 것 뿐. (당연히 다른 방식이니 forwarding과 혼합 가능.)

 

＊코드의 순서를 바꿈으로써, 다음 instruction에 필요한 결과값 load 과정에서 발생할 stall을 회피.

　ㆍData Dependent한 순서를, Independent한 순서로 변경.

　　(물론, 명령어에 필요한 값들이 변하지 않았어서 순서를 바꿀 수 있는 경우에. 즉, 당겨서 해도 상관없는 명령어를.)

 

＊C code:

A[3] = A[0] + A[1];
A[4] = A[0] + A[2];

A의 기본 주소는 $t0에.

＊Data Dependency로 stall이 발생하는 순서에서, Independent한 명령어끼리 연속되도록 해서 stall을 없앰.

　ㆍ원래의 코드에서, add...,$t2에서, $t2의 값을 알려면, 4($t0) 때문에(MEM 직후까지) forwarding을 해도, 1개의 stall.

　ㆍ원래의 코드에서, add...,$t4에서, $t4의 값을 알려면, 8($t0) 때문에(MEM 직후까지) forwarding을 해도, 1개의 stall.

　ㆍ원래의 코드는, RAW(Read After Write, write 후에 read)로 Data Dependency가 발생.

　ㆍ첫 stall 부분에 차라리 lw $t4, 8($t0)를 당겨와서(그동안 이 명령어에 이용되는 값은 변하지 않았으니)

　　미리 해 둠(할 수 있는 다른 작업을 해 둠. 바로 위의 명령어와는 independent하니 바로 가능.).

　ㆍ$t4를 미리 준비해놔서, 두번째 stall도 같이 사라짐. 일석이조. 개이득..

　ㆍ코드의 양이 줄어드는 것이 아님. pipeline에서 발생하는 지연현상을 줄이는 것.

 

※Data Dependency는 RAW, WAW, WAR의 3가지 경우가 있음(RAR는 X. 읽고 읽는건 뭐..).

　ㆍ직전의 결과와 상관이 있을 때.

　ㆍ여기서 stall이 발생하는 Data Hazard는 RAW(Read After Write)에서 발생.

　ㆍWAW와 WAR은 멀티쓰레드에서 동기화를 제대로 해주지 않아 값이 틀어질 수 있는 것 처럼,

　　병렬구조에서 쓰기 결과 순서가 확실하게 되지 않을 수 있는 Data Hazard.

　ㆍhttps://en.wikipedia.org/wiki/Data_dependency

　ㆍhttps://en.wikipedia.org/wiki/Hazard_(computer_architecture)

 

 

 

Control Hazards

제어 위험

 

ㆁData Hazard는 데이터가 아직 준비되지 않아서.

　Control Hazard는 제어 신호로 인해 프로그램의 flow가 바뀔 수 있는 상황.

　＊그래서 flow가 바뀔지도 모르기 때문에 직후 명령어들이 바로 실행되지 못하는 hazard.

 

ㆁ분기(branch)는 control의 흐름을 결정한다.

　＊다음 명령어를 가져오는 것(intruction fetch)은, 분기의 결과(branch outcome)에 의존적이다.

　　ㆍ순차적으로 PC+4가 될지, beq 최종신호로 1이 와서 다음 주소 결과를 PC에 담을지.

　＊pipeline은 항상 올바른 instruction을 fetch하지 않을 수도 있다.

　　ㆍbranch의 ID(Instruction Decode & register read) stage가 여전히 작업 중(working)이라 결과를 못 내고 있을 때.

 

ㆁMIPS pipeline에서,

　＊branch 명령어의 비교대상(레지스터 값)을 비교하는 것과 점프 대상 주소 계산을 미리 해야 한다.

　＊그럴 수 있도록 ID stage에 하드웨어를 추가한다.

 

 

 

Control Hazards --- Stall on Branch

branch에서의 stall

 

＊다음 instruction을 fetch하기 전에, branch 결과가 결정되는 동안 기다리게 되는 상황.

　ㆍID stage에 하드웨어를 추가하여 미리 비교를 하고 주소를 계산했더라도,

　　ID stage가 끝나야 알 수 있으므로, 1 cycle stall.

 

 

 

Control Hazards --- Branch Prediction

branch 결과를 예측

 

＊긴 pipeline(stage 수가 아주 많은, 아주 긴.)에서는 이전의 branch 결과가 결정되는 것을 기다릴 수 없다(일찍 알기 어렵다).

　ㆍstall로 인한 불이익은 엄청 커질 수 있다. 결과를 최대한 당겨도 여러 cycle의 stall이 발생할 수 있다(stage 수가 많아서).

 

＊branch 결과를 예측

　ㆍ만약 예측이 틀렸을 경우에만 stall이 발생

 

＊MIPS pipeline에서,

　ㆍbranch 결과를 "일어나지 않은 것"으로 예측(가정)할 수 있다.

　ㆍ이렇게 해서 branch 명령어 이후에 intruction fetch를, 지연없이(no delay) 바로 가능하다.

 

 

 

Control Hazards --- Branch Prediction --- MIPS with Predict Not Taken

MIPS에서, 일어나지 않은(같은→같지않은/같지않은→같은. 즉, 순차적인(PC+4) 흐름)으로 예측

 

 

 

Control Hazards --- Branch Prediction --- 좀 더 현실적인 Branch Prediction

실제로 사용하는 것에 더 가까운 방식(위에서는 무조건 아닐 것으로 예측)

 

ㆁStatic branch prediction

　＊전형적인(typical) branch 동작(behavior)에 기인한다(based on).

　＊예시: loop와 if문 branch

　　ㆍ되돌아가는(backward, 위로 -~) branch는 일어날 것으로 예상(가정)한다. 해당 주소의 IF.

　　ㆍ진행하는(forward, 아래로 +~) branch는 일어나지 않을 것으로 예상(가정)한다. PC+4의 IF.

　＊정확도는 떨어질 수 있음.

 

ㆁDynamic branch prediction

　＊하드웨어가 실제의(actual) branch 동작(behavior)을 측정한다(measure).

　　ㆍe.g., 각 branch의 최근 history를 기록한다(record). 

　＊미래의(future) 동작은 그동안의 경향(trend)을 따를 것으로 가정한다.

　　ㆍ그게 틀린다면, 당연히 그 때는 stall이 발생하고 re-fetcing이 일어날 것임.

　　ㆍhistory는 잘되는 못되든 항상 기록될 것이고, stall이 발생하면 점차 수정되어 trend도 변할 것임.

　＊정확도는 높아지지만, history 기록과 trend 측정에 자원과 시간 소요.

　　ㆍ최신 프로세서는 이 방식 사용. 뭐 하드웨어도 더 쓸 수 있고 성능도 되서 그런가..?? 여기에 성능 조금 써도 전체적으로 성능 더 좋아지면 뭐..

 

 

 

Pipeline Summary

 

＊Pipelining은 instruction의 througput(처리량)을 늘림으로써 성능을 향상시키는 방법이다.

　ㆍ한 명령어의 실행 속도가 아님. 동시에(병렬적으로) 여러 명령을 가능케하는 양을 늘린 것.

　ㆍ병렬적(parallel)으로 여러 명령(multiple instruction)을 실행한다.

　ㆍ각 instruction은 같은 latency(지연, 한 명령어의 총 실행속도)을 갖는다.

 

＊hazard(위험)에 주의한다.

　ㆍstructure, data, control

 

＊Instruction Set의 설계방식(Instruction set architecture)은 pipeline 구현의 복잡도에 영향을 미친다.

　ㆍISA가 간단할 수록 pipeline 구현도 쉬워진다.

 

 

 

잠깐 복습,

Hazard의 정의는?

다음 cycle에 다음 명령어가 시작되는 것을 막는 상황.

Situations that prevent starting the next instruction in the next cycle.

 

---

<4.6 - Pipelined Datapath and Control>

 

 

 

MIPS Pipelined Datapath

예전에 본 개략도는 single-cycle이고, 이제는 muilti(pipelined).

 

 

 

Pipeline registers

 

＊각 stage 사이에 레지스터들이 필요하다.(stage 수 - 1)

　ㆍ이전 cycle에서 만들어진 정보를 가지고 있어야 하기 때문

 

 

 

Pipeline Operation

 

ㆁpipeline datapath를 통한 instruction의 cycle-by-cycle(cycle에서 cycle로) 흐름

　＊"Single-clock-cycle" pipeline diagram(도표)

　　ㆍsingle-cycle을 사용하는 pipeline을 보여줌.

　　ㆍ사용되고 있는 하드웨어 자원을 강조표시

　＊c.f., "multi-clock-cycle" diagram은..

　　ㆍ시간 경과에 따라 어떻게 실행되는지(operation) 보여주는 그래프

 

ㆁ이제 load & store 명령어를 수행하는 "single-clock-cycle" diagram을 살펴보자.

 

 

 

Single-clock-cycle pipeline diagram --- IF for Load, Store, ...

 

 

 

Single-clock-cycle pipeline diagram --- ID for Load, Store, ...

 

 

 

Single-clock-cycle pipeline diagram --- EX for Load, Store, ...

 

 

 

Single-clock-cycle pipeline diagram --- MEM for Load, Store, ...

＊MEM for Load

 

＊MEM for Store

 

 

 

Single-clock-cycle pipeline diagram --- WB for Load

＊SW에서는 WB stage에서 강조되는 영역이 없다.

　ㆍ메모리에서 오른편으로 흐르는 두 개의 흐름(I-format의 LW용 값/R-format의 결과값)이 없음.

　ㆍ그래서 SW의 WB stage는 아무 작업도 없다.

 

＊pipeline에서, WB은 5번째 stage이며,

　이만큼 이미 다른 cycle이 진행되어, 레지스터에는 이미 다른 명령어를 해석하고 있을 것.

　ㆍ기존 명령어의 $rt가 아니므로, WB을 위해 기존 명령어의 $rt를 보존해야 한다.

 

 

 

Single-clock-cycle pipeline diagram --- Corrected Datapath for Load

＊$rt 보존을 위해, 레지스터 이후의 stage간 레지스터(pipeline register)마다 $rt를 넘겨줌으로써,

　WB에서 다시 레지스터에 전달하여 활용.

 

 

 

Multi-Cycle Pipeline Diagram

 

＊시간과 명령어에 따른 resource(하드웨어 자원)의 사용을 보여줌.

 

＊전통적인, 보통의 형태(Traditional form)

 

 

 

Single-Cycle Pipeline Diagram

 

＊주어진 cycle(특정한 cycle)에서 pipeline의 상태

　ㆍ특정한 cycle에서 각 stage들이 어떤 명령어를 수행하고 있는지. 내부 상태가 어떤지.

　※ 위의 Multi-Cycle Pipeline Diagram을 참조하면, CC5에 해당하는 시간임.

 

 

 

Pipelined Control (간결화된)

 

Pipelined Control

 

＊Control signal(제어신호)는 instruction으로부터 파생된다(derived).

　ㆍsingle-cycle에서처럼

＊각 stage에 control들이 전달되기 위해, pipeline register(각 stage간 레지스터)에 함께 전달되어 보존되어야 한다.

　ㆍsingle-cycle과는 달리, ID에서 해석되어 생성된 제어신호들이 각 stage에 쓰이기 위해 보존되어야 하므로.

　ㆍpipeline에서는 ID에서 또 새로운 명령어로 다른 제어신호들을 생성할테니..

　ㆍ역시 pipeline이 sigle-cycle보다 더 복잡해지는 것.

 

pipeline register에 각 제어신호들이 넘겨지면서 보존되고, 각 stage에서 알맞게 쓰임.

 

 

 

잠깐 복습,

Pipeline processor에서 Forwarding의 정의는?

값이 계산되자마자 곧장 끌어다 쓰는 것.

Use result when it is computed.

 

Forwarding은 대부분의 Data hazards를 해결할 수 있으나,

Load-Use Data Hazard는 해결할 수 없음.

 

---

<4.7 - Data Hazards: Forwarding versus Stalling>

 

 

 

Data Hazards in ALU Instructions

 

＊다음의 순서를 생각해보자. (RAW. Read After Write. 쓰기 후에 읽기)

　sub　$2, $1, $3

　and　$12, $2, $5

　or 　 $13, $6, $2

　add　$14, $2, $2

　sw 　 $15, 100($2)

 

＊우리는 forwarding(bypassing)으로 hazard를 해결할 수 있다.

　ㆍ그러면 forward가 필요한 때는 어떻게 알 수 있는가(detect)?

 

 

 

Dependencies & Forwarding

 

＊지금 우리가 관심있는 Dependency는 RAW에 의한 의존성.

　ㆍForwarding으로 해결가능한 Data Dependency는 RAW에 의한 것이므로.

　(※ WAW와 WAR은 병렬식으로 누가 먼저 써버리느냐에 따라 결과가 달라질 수 있던..)

녹색 선을 위에서 아래로 표현했지만,

실제로 장치는 하나이니, 오른쪽에서 왼쪽으로 표현해야 한다.

다음 cycle 기준으로는 EX/MEM 레지스터가 생성된 값을 가지고 있고(해당 명령어는 MEM단계로 들어갔으니),

다다음 cycle 기준으로는 EX/MEM 레지스터에는 이미 다른 값으로 덮혔지만,

MEM/WB 레지스터에 해당 값을 가지고 있다(해당 명령어는 WB단계로 들어갔으니).

 

 

 

Detecting the Need to Forward

Forwarding이 필요한 순간을 감지해내기

 

＊pipeline을 통해 레지스터 번호를 넘겨준다(pass).

　ㆍe.g., ID/EX.RegisterRs = ID/EX pipeline register의 Rs(SourceRegister)를 위한 레지스터 번호

 

＊EX stage에서의 ALU 피연산자 레지스터 번호는 다음과 같다. (R-format의 ALU)

　ㆍID/EX.RegisterRs, ID/EX.RegisterRt

 

＊Data hazard가 발생하는 경우는 아래의 4가지 경우.

　ㆍ1a/b는,

　　(다음 cycle의 instruction)EX의 Rs/Rt(피연산자들)가

　　(이전 cycle의 instruction)MEM의 Rd가 같을 때.

　　즉, WB을 위한 대상 레지스터에 값이 쓰이고, 다른 명령어가 그걸 읽어야 하는데,

　　아직 값이 쓰이지 않아서.

　　1cycle 전의 instruction에서, EX직후에서 "계산된 Rd에 쓰일 값"을 끌어와서 사용.

　ㆍ2a/b는,

　　(다음 cycle의 instruction)EX의 Rs/Rt(피연산자들)가

　　(이전 cycle의 instruction)WB의 Rd가 같을 때.

　　마찬가지로, WB을 위한 대상 레지스터에 값이 쓰이고, 다른 명령어가 그걸 읽어야 하는데,

　　아직 값이 쓰이지 않아서.

　　2cycle 전의 instruction에서, "Rd에 쓰일 값이 흐르던 것"을 MEM이후에서 끌어와서 사용.

 

※ R-format Instruction

op	rs	rt	rd	shamt	funct
6 bits	5 bits	5 bits	5 bits	5 bits	6 bits

 

＊forwarding은 이전의 instruction에서 레지스터에 늦게 쓰여지는 것들을 해결하는 것이라(아직 그 값이 안 쓰여져서 문제였던),

　pipeline register에 함께 전해지는 제어 신호를 살펴보면,

　RegWrite 신호(마지막 WB에서 register에 쓰이라는 신호)를 찾아볼 수 있을 것이다.

　ㆍEX/MEM.RegWrite, MEM/WB.RegWrite

 

＊그리고 쓰이는 것이니, 쓰일 대상 레지스터 번호를 나타낼 Rd도 $zero가 아닐 것이다.

　ㆍEX/MEM.RegisterRd≠0

　ㆍMEM/WB.RegisterRd≠0

　(※ 0번 레지스터는 쓰기가 불가능한 $zero 고정이니까..)

 

 

 

Forwarding Paths

Forwarding을 위해 경로와 장치를 추가한 모습

＊Forwarding 감지를 위해, 현재 cycle의 Rs, Rt(파란색)를 Forwarding Unit(보라색)에 보낸다.

　※ 현재 피연산자 Rs, Rt가 제대로 준비 되었는지가 Data Hazard와 forwarding으로 해결의 핵심이므로,

　　현재 cycle은 피연산자가 필요한 실행단계인 EX stage이다.

＊1cycle 전의 instruction과, 2cycle 전의 instruction에서(둘 다 아직 덜 끝난)

　쓰여질 목표 레지스터(Rd)가 현재 Rs나 Rt와 같다면, 레지스터에는 값이 아직 제대로 쓰이지 않았을 것이다.

＊이전 cycle의 Rd를 보존하기 위해, Rd를 pipeline register에 넘겨지도록 한다.(빨간색)

　ㆍ1cycle 전의 Rd는 EX/MEM.RegisterRd에.

　ㆍ2cycle 전의 Rd는 MEM/WB.RegisterRd에.

＊Forwarding Unit(보라색)에서는,

　현재 cycle의 Rs나 Rt와, EX/MEM.RegisterRd 혹은 MEM/WB.RegisterRd가 같은 번호를 가지는지 비교한다.

　ㆍEX/MEM.RegisterRd, MEM/WB.RegisterRd 모두 Rs, Rt와 일치하지 않으면 상관없다.

　ㆍEX/MEM.RegisterRd가 Rs나 Rt와 일치한다면, EX직후인 ALU의 결과값(녹색)을 가져와서 사용한다.

　ㆍMEM/WB.RegisterRd가 Rs나 Rt와 일치한다면, WB로 쓰려는 값(녹색)을 가져와서 사용한다.

　ㆍForwarding Unit(보라색)은 제어신호를 3x1의 MUX(주황색)들로 보내,

　　ALU의 피연산자로

　　ID stage의 레지스터의 값(일반적인 경우)를 사용할지, forwarding으로 가져온 값을 사용할지 제어한다.

 

 

 

Datapath with Forwarding

전체 Datapath.

Forwarding Unit에서는 이전 cycle들의 Rd 뿐만 아니라,

EX/MEM.RegWrite, MEM/WB.RegWrite의 제어 신호도 forwarding 판별에 필요하므로,

이들 역시 pipelien register에서 함께 전달되는 것을 볼 수 있다.

 

 

 

Forwarding Conditions

forwarding 조건

 

＊EX hazard

　ㆍ(EX/MEM.RegWrite & EX/MEM.RegisterRd≠0) & (EX/MEM.RegisterRd == ID/EX.RegisterRs)

　　→ ForwardA = 10

　ㆍ(EX/MEM.RegWrite & EX/MEM.RegisterRd≠0) & (EX/MEM.RegisterRd == ID/EX.RegisterRt)

　　→ ForwardB = 10

 

＊MEM hazard

　ㆍ(MEM/WB.RegWrite & MEM/WB.RegisterRd≠0) & (MEM/WB.RegisterRd == ID/EX.RegisterRs)

　　→ ForwardA = 01

　ㆍ(MEM/WB.RegWrite & MEM/WB.RegisterRd≠0) & (MEM/WB.RegisterRd == ID/EX.RegisterRt)

　　→ ForwardB = 01

 

※ no hazard or double??

　ㆍForwardA = 00 / ForwardB = 00

　ㆍ즉, 앞 비트는 EX hazard, 뒤 비트는 MEM hazard.

　ㆍ11이라면 더 나중에 레지스터에 쓰일(현재와 가까운) 1cycle 전인 EX hazard의 값을 고를 것(MUX는 1개만 결과로).

　　(근데 아래를 보면 11이 가능한가는 모르겠음. 수정된 조건으로 00,10,01로 못을 박아서..)

 

 

Double Data Hazard

 

＊다음의 순서를 생각해보자. (RAW. Read After Write. 쓰기 후에 읽기)

　(병렬식으로 순서가 얽히지 않고(WAW or WAR의 Data hazard가 아니라도), 반드시 순서대로 진행된다고 하더라도.)

　add　$1, $1, $2

　add　$1, $1, $3

　add　$1, $1, $4 → 위의 어느걸 가져오지??

 

＊양 쪽 hazard가 모두 일어난다면,

　ㆍ좀 더 최근(현재에 가까운) 것을 사용

 

＊double일 경우에는 MEM hazard의 조건이 변경됨

　ㆍEX hazard가 아닐 경우에만 MEM hazard forwarding.

　ㆍ즉, double이라면, 항상 EX hazard로 보고 EX 직후의 값(1cycle 이전의, 최근의)을 가져오면 됨.

 

 

 

Revised Forwarding Conditions

수정된 forwarding 조건

 

＊EX hazard (그대로)

　ㆍ(EX/MEM.RegWrite & EX/MEM.RegisterRd≠0) & (EX/MEM.RegisterRd == ID/EX.RegisterRs)

　　→ ForwardA = 10

　ㆍ(EX/MEM.RegWrite & EX/MEM.RegisterRd≠0) & (EX/MEM.RegisterRd == ID/EX.RegisterRt)

　　→ ForwardB = 10

 

＊MEM hazard

　ㆍ(MEM/WB.RegWrite & MEM/WB.RegisterRd≠0)

　　& not ((EX/MEM.RegWrite & EX/MEM.RegisterRd≠0) & (EX/MEM.RegisterRd == ID/EX.RegisterRs))

　　& (MEM/WB.RegisterRd == ID/EX.RegisterRs)

　　→ ForwardA = 01

　ㆍ(MEM/WB.RegWrite & MEM/WB.RegisterRd≠0)

　　& not ((EX/MEM.RegWrite & EX/MEM.RegisterRd≠0) & (EX/MEM.RegisterRd == ID/EX.RegisterRt))

　　& (MEM/WB.RegisterRd == ID/EX.RegisterRt)

　　→ ForwardB = 01

 

 

 

Load-Use Data Hazard

이전에 forwarding으로 줄여도 stall을 완전히 없앨 순 없어서 code scheduling 했던.

(당연하지만 미리 해둘 작업이 없으면 code scheduling 같은 방식도 불가능이니 그냥 받아들여야함..ㅎ)

---

＊항상 forwarding(aka bypassing)으로 모든 stall을 피할 수는 없을 수도 있다.

　ㆍ결과가 필요한 순간에 아직 계산이 완료되지 않았다면.

　ㆍ제 때에 값을 끌어올 수도 없이 "존재하지도 않는다면" 활용도 불가능.

결국 1cycle의 stall을 피하지 못한 경우

lw　$s0, 20($t1) 명령어에는,

...,

20($t1)의 주소를 ALU에서 계산,(이건 수행했음)

그 주소를 토대로 MEM에 접근,(이제 접근 중이라 값을 다 못 가져옴)

그 곳의 값을 $s0에 load.

 

어쨌든 최대한 줄이려고 해도(레지스터에 write back 전에 빼오려고 해도),

MEM에 접근 이후에나 원하는 값을 알 수 있음.

최대한 줄여도 1cycle의 stall이 발생.

---

현재 cycle은 EX stage이고,

이전 cycle의 값들이라봐야 EX/MEM에 있는 값들이 고작인데,

MEM 이후의 값은 아직이라 가져올(forwarding) 수 없음.

stall이 발생.

 

 

 

Load-Use Hazard Detection

감지

 

＊현재 cycle의 ID stage에서, 향후 instruction에 필요한 부분이 아직 준비되지 않았는지 검사한다.

　※ EX stage에서는 지금 당장 필요한데 부랴부랴 검사하기에는 만약 안돼서 bubble을 삽입하기에 늦다.

　※ forwarding은 EX stage에서도 충분히 어떻게든 끌어올 수 있기 때문에 그 때 판별해도 상관없었음.

 

＊ID stage에서 ALU 피연산자 레지스터 번호는 다음과 같다.

　ㆍIF/ID.RegisterRs

　ㆍIF/ID.RegisterRt

 

＊Load-use hazard는 다음일 때 발생한다.

　ㆍID/EX.MemRead & [ (ID/EX.RegisterRt == IF/ID.RegisterRs) || (ID/EX.RegisterRt == IF/ID.RegisterRt) ]

　ㆍ이전 cycle의 명령어가 MemRead 종류라서, MemRead 신호가 있었고,

　　현재 cycle의 명령어의 피연산자(Rs나 Rt)의 번호가

　　이전 cycle의 Rt의 번호(메모리에서 읽은 값을 넣을 레지스터 번호)와 같을 경우.

 

※ 아마 이전 cycle은 I-format일 것.

op	rs	rt	constant or address
6 bits	5 bits	5 bits	16 bits

　ㆍrs인 레지스터 값에 address를 ALU로 더한 주소의 메모리에 접근하여, rt인 레지스터에 값을 가져올 것.

 

＊만약 Load-use hazard가 감지된다면, stall이 발생할 것이고, 해당 부분에 bubble을 삽입시킨다.

 

 

 

How to Stall the Pipeline

 

ㆁ강제로 ID/EX 레지스터의 제어 신호 값들을 모두 0으로 한다(ID 이후 아무것도 동작하지 않도록 한다).

　＊EX, MEM, WB는 NOP(no-operation)

　＊EX/MEM 포함, 그 이후의 신호들은 그대로이기 때문에, 이전 cycle의 명령어는 계속 진행됨.

　　ㆍ한 단계의 bubble이 필요할 뿐.

 

ㆁ쉰 다음에(제대로 다 준비되면) 명령어를 수행해야 하므로,

　PC와 IF/ID 레지스터의 갱신을 방지한다.

　＊현재 명령어가 ID stage에서 다시 decode되도록 한다.

　＊직후 명령어(PC+4+4가 아닌 PC+4)가 IF stage에서 다시 fetch되도록 한다.

　＊1-cycle의 stall은 이전의 명령어(lw)가 충분히 MEM에서 데이터를 읽어올 수 있도록 해주었다.

　　ㆍ이제 현재 명령어가 EX stage로 진행해도 된다.

 

 

 

Stall/Bubble in the Pipeline

 

 

 

Datapath with Hazard Detection

Load-Use Datahazard Detection이 추가됨

＊ID stage에서 Hazard detection unit이 추가된 것이 보임.

　ㆍ여기에 ID/EX.MemRead 제어 신호가 전달됨.(1-cycle 전)

　ㆍ그리고 ID/EX 레지스터에의 Rt가,(1-cycle 전)

　ㆍIF/ID 레지스터의 Rs, Rt가 전달됨.(현재)

 

＊이것을 토대로 Load-Use Data hazard를 감지하면,

　ㆍID/EX 레지스터에 제어신호를 모두 0으로 하여,

　　1번 bubble이 생기도록(한 층만 건드리니까) 해 줌.

　ㆍPC에는 PCWrite 제어신호를 0으로 하여,

　　PC가 업데이트 되는 것을 방지(직후 명령어는 그대로 다시 fetch).

　ㆍIF/IDWrite 제어신호를 보내 현재 명령어가 다시 decode 될 수 있도록.

 

 

 

Stalls and Performance

 

＊stall은 성능을 저하시킨다.

　ㆍ하지만, 정확한 결과를 얻기 위해서는 꼭 필요하다.

　　(당연히 정확성이 더 중요. 꼬이면 그 후 다 위험해짐)

 

＊컴파일러는 코드를 재배치해서 hazard를 피하고 stall을 방지할 수 있다.

　ㆍ이를 위해서 컴파일러는 해당 프로세서의 pipeline 구조를 정확히 파악해야 한다.

 

---

<4.8 - Control Hazards>

 

 

 

Branch Hazards

 

＊branch의 결과가 MEM 단계에서 결정된다면??(원래 ALU에서 zero인지 아니까 EX아닌가?? 말 그대로 가정인가??)

＊Control hazard 파트에서,

　branch 결과를 알기 위해 기다리는 것 대신 "아닌 것으로 가정"하여 연속된 명령어를 수행하다가

　아니면 그대로, 맞으면 제대로 명령어 가져와서 수행하기로 했었음.

　ㆍ만약 결과가 맞으면 그동안 미리 예측하여 수행해둔 명령어는 버려야 함.

　ㆍ제어 신호를 0으로 하여 비워야(flush) 함.

 

 

 

Reducing Branch Delay

예측에 실패하더라도 버려지는 단계를 줄여보자

 

＊branch 결과를 구하는 걸 ID stage에서 할 수 있도록 하드웨어를 옮긴다.

　ㆍtarget address adder (대상 주소를 PC+4+offset(address*4)해주던 ALU 및 left shift, sign extend)

　ㆍregister comparator (ALU로 비교해서(빼서) zero인지 봤던)

 

＊예시: branch

　36:　sub　$10, $4, $8

　40:　beq　$1,　$3, 7

　44:　and　$12, $2, $5

　48:　or　　$13, $2, $6

　52:　add　$14, $4, $2

　56:　slt　　$15, $6, $7

　...

　72:　lw　　$4, 50($7)　　# (40+4)+7*4 = 72

ID stage에 값비교와 주소계산이 모두 가능하도록 장치를 옮기거나 추가함.

　ㆍbeq는 다음 stage들도 넘어가도 딱히 할 일은 없음.

　ㆍ예측이 맞다면 상관없이 다음 명령어 계속 수행.

　ㆍ예측이 틀리고 정말 분기로 이동해야한다면,

　　분기 대상 주소를 PC에 넣어 해당하는 명령어를 IF할 수 있도록 하고,

　　직후 명령어(IF였던)는 파기(이제서야 ID로 들어오지만)한다.

　ㆍ기존 모델에서는 예측으로 실행해둔 여러 instruction을 버리면서 여러 cycle의 bubble이 발생하지만,

　　ID stage에서 분기 결과값을 구함으로써, 단 1번(IF 단계였던 직후 명령어)의 bubble만으로 줄일 수 있음.

 

 

 

잠깐 복습,

Data Hazard의 정의는?

이전 명령어가 데이터를 읽거나 쓰는 것이 완료될 때까지 기다려야 하는 상황.

Need to wait for previous instruction to complete its data read/write.

 

 

 

Data Hazards for Branches

 

＊만약 branch에서 비교하려는 레지스터가

　2-cycle 전이나 3-cycle 전의 ALU instruction 결과(Rd)라면(아직 레지스터에 값이 쓰여지지 않았다면).

　(즉, RAW(Read After Write, 쓴 뒤에 읽기))

＊forwarding을 사용하여 해결할 수 있음

　ㆍ이전에 본 forwarding은 현재 cycle이 EX stage였다(ALU에 필요한 피연산자).

　ㆍ이제 branch의 비교 ALU는 ID stage에 있기 때문에,

　　1, 2 전 단계가 아닌, 2, 3 전 단계에 대해 forwarding할 수 있다.

　　(1 전 명령어는 이제 막 EX를 수행하는 중이고, 2 전 명령어는 EX/MEM, 3 전 명령어가 MEM/WB)

 

 

＊만약 비교하려는 레지스터가

　ㆍ1 cycle 전(바로 직전)의 ALU instruction의 결과(ID/EX.RegisterRd)이거나,

　ㆍ2 cycle 전의 load로 불러온 값을 쓸 레지스터(EX/MEM.RegisterRt)라면,

　forwarding할 수 없고, stall이 발생할 수 밖에 없다.

　※ 직전 명령어가 산술일 때, 이제 EX 들어가려는데 값이 있을리가..

　　(branch 피연산자로서 ALU 결과는 한 칸의 여유 필요)

　※ 2-cycle 전 명령어가 load일 때, 이제 MEM 들어가려는데 값이 있을리가..

　　(branch 피연산자로서 MEM read는 두 칸의 여유 필요)

 

 

 

Dynamic Branch Prediction

 

ㆁ초대형(deeper and superscalar(stage 아주 많음)) pipeline일수록,

　branch 패널티(stall 발생)는 더 중요하게 여겨진다(크다).

　＊stage 수가 많으면 나눠서 일을 하니 속도가 올라가지만,

　　그만큼 stall도 한꺼번에 여러 cycle이 발생할 수 있다(여러 stage가 쉬어야 하니까).

　＊또한 복잡하기 때문에, branch의 결과도 ID stage가 아닌, 좀 더 진행이 된 상태에서 알 수 있게 된다.

　　ㆍ그러면 예상이 틀렸을 때, 미리 진행한 명령어들을 flush하면서 stall도 더 많이 발생함.

 

ㆁdynamic prediction(동적 예측)을 사용하자

　＊branch prediction buffer(aka. branch history table)를 둔다.

　＊거쳐온 branch instruction의 주소들을 색인화(index)한다.

　＊분기 결과(outcome)를 저장해둔다(store). taken/not taken(조건맞음/조건틀림)

　＊branch를 수행하려면

　　ㆍ테이블을 살펴보고 추론한 예상을 바탕으로, 이러하길 바라면서 진행하기로 한다.

　　ㆍ분기 대상이든, 아니라서 연속으로 진행하든, 예상한 대로의 명령어를 가져와서 진행한다.

　　ㆍ만약 틀렸다면, 예상대로 했던 명령어를 비우고(flush pipeline) 예측을 뒤엎는다(반대의 명령어를 가져온다).

 

 

 

1-Bit Predictor: Shortcoming(결점, 단점)

1-Bit. 바로 전의 결과만 사용하는 경우.

 

ㆁ다중 loop에서, 안쪽 loop branch는 예측실패(mispredict)를 두 번 한다(처음, 마지막)!

　＊안쪽 loop의 반복 중 마지막에서,

　　예측실패(mispredict)는 일어날 것(taken)으로 나타난다.

　　ㆍ안쪽 loop는 항상 일어나서(taken) 내부가 반복되었기 때문에, 이번에도 그럴 것으로 예측해서

　＊안쪽 loop의 반복 중 첫번째에서,

　　예측실패(mispredict)는 일어나지 않을 것(not taken)으로 나타난다.

　　ㆍ안쪽 loop의 가장 최근은 일어나지 않고(not taken),

　　　밖으로 나가서 바깥 loop가 다시 안쪽을 시작시킨 것이라,

　　　이번에도 안쪽은 최근대로 일어나지 않을 것으로 예측해서.

 

 

 

2-Bit Predictor

 

＊두번의 연속된 예측실패(misprediction)이 일어나야만 예측기준의 결과(predictor가 판단할)를 역전한다.

State Transition Diagram

　ㆍ11↔10↔01↔00

 

 

 

Calculation the Branch Target(address)

 

ㆁbranch 명령어를 위해 기존의 EX stage에서였든, ID stage로 옮겼든,

　대상 주소를 계산(rs(PC+4) + address*4)해야 함.

 

ㆁpredictor를 사용하더라도, 여전히 대상 주소는 계산해야한다(당연하지..).

　＊branch마다 1-cycle의 패널티

 

ㆁbranch target buffer

　＊반복될 branch라면 아예 대상 주소(바뀌지 않고 고정된 메모리주소)를 기억해두고 재활용하자.

　＊대상 주소의 캐시(cache)

　＊instruction fetch 때 PC에 의해 색인화(index)됨

　　ㆍ만약 예측이 적중하면, 대상 주소의 명령어를 즉시 fetch할 수 있다.

　　　(이미 buffer에 있는 주소라면, 주소 계산의 오버헤드가 사라짐.)

 

---

<4.9 - Exceptions>

 

 

 

Exceptions and Interrupts

예외와 인터럽트(중단)

 

ㆁ제어의 흐름 중에(프로그램이 실행 중에),

　"예상치 못한" 상황 발생으로, 변동(예상치 못한 상태 제거)이 필요한 때

　＊다른 ISA마다 기간(term)을 다르게 사용한다.

 

ㆁException(예외)

　＊CPU 내부에서 발생한다.

　　ㆍe.g, undefined opcode, overflow, syscall, ...

 

ㆁInterrupt(중단)

　＊외부 I/O controller(CPU가 아닌 외부장치. OS 등..)로부터 발생한다.

 

※ Trap

　＊(=Software Interrupt)

　　ㆍsyscall 활용. 명령어가 인터럽트를 발생.

　　ㆍ원래 인터럽트는 하드웨어에서 발생시키지만, 소프트웨어적으로 호출해서 발생시키는 경우.

 

ㆁ성능을 희생하지 않고서 이 문제들을 다루는 것은 어렵다.

　＊이 문제를 다루기 위해서는 어느정도 성능 저하가 발생한다.

 

 

 

Handling Exceptions

예외 처리

 

ㆁMIPS에서, exception은 System Control Coprecessor(CP0)에 의해 관리된다.

 

ㆁ문제가 생긴(offending, interrupted) instruction의 PC(지금 exception이니 지금 PC. 즉, instruction 주소)를 저장한다.

　＊MIPS에서는: Exception Program Counter(EPC)

 

ㆁ문제의 종류(indication. 표시,원인)를 저장한다.

　＊MIPS에서는: Cause Register에 저장.

　＊1-bit로 가정한다면,

　　ㆍundefined opcode는 0, overflow는 1 처럼.

　　(※ 원래는 더 많은 종류가 있음)

 

ㆁ8000 00180(미리 정해진)의 메모리 주소에 위치한 handler로 jump

　※ 여기서 EPC와 Cause Register의 값 등을 이용하여 처리.

 

 

 

An Alternate Mechanism

다른 방식(좀 더 발전된)

 

＊Vectored Interrupts

　ㆍ원인에 따른 handler 주소가 다르게 정해져있다.

 

＊예시:

　ㆍundefined opcode:　C000 0000

　ㆍoverflow:　　　　　 C000 0020

　ㆍ...:　　　　　　　 　 C000 0040

 

＊문제가 발생한 Instruction은 다음 중 하나로 진행된다.

　ㆍ해당 handler에서 처리하거나(드물게)

　ㆍreal handler(문제를 제대로 처리할 수 있는)로 jump하여 처리하거나

 

 

 

Handler Actions

handler 동작

 

＊원인을 읽고, 관련된 handler로 넘겨준다(handler로 jump).

 

＊필요한 동작을 결정한다.

 

＊만약 해당 명령어를 재시작 가능하다면,

　ㆍ적절한 동작으로 시정하여 동작시킨다.

　ㆍEPC를 이용하여 원래의 PC로 돌아갈 수 있도록 한다.

 

＊그렇지 않다면,

　ㆍ프로그램을 중단한다(terminate).

　ㆍEPC, cause, ... 등을 이용하여 error를 보고한다(Report error).

 

 

 

Exceptions in a Pipeline

 

＊control hazard의 또 다른 형태로 볼 수 있다.

　ㆍcontrol hazard는 프로그램의 flow가 바뀔지도 몰라서 직후 명령어가 바로 실행될 수 없는 hazard.

　ㆍexception도 발생하면, 다음의 명령어들이 실행되지 못하고 exception을 처리해야 함.

 

＊add명령어의 EX stage에서 overflow가 발생했다고 생각해보자.

　add　$1, $2, $1

　ㆍ$1에 잘못된 값이 쓰여지는 것을 막는다.

　ㆍ이전 명령들은 제대로 완수될 수 있도록 한다.

　ㆍadd 명령어와 이후 명령어들을 비운다(flush).

　ㆍEPC와 Cause Register의 값을 세팅한다.

　ㆍhandler로 제어권을 넘긴다(handler가 처리할 수 있도록 jump).

 

＊예측실패한 branch와 유사하다.

　ㆍ동일한 하드웨어 자원을 많은 부분 함께 사용한다.

 

 

 

Pipeline with Exceptions

추가된 부분을 강조 표시.

추가된 장치 외에도, 기존의 장치를 많은 부분 함께 활용하여 exception을 처리한다.

 

 

 

Exception Properties

특성

 

ㆁ재실행 가능한 명령어에 대한 exception

　＊pipeline은 명령어를 비운다(flush).

　＊handler가 처리 후, 원래의 instruction으로 돌아감.

　　ㆍ이번엔 시정된 instruction을 실행한다.

 

ㆁEPC 레지스터에 PC가 저장됨

　＊문제가 발생한 instruction을 식별가능.

　＊당연히 실제론 PC+4가 저장될 것임.

　　ㆍhandler가 반드시 조정해야 함(-4를 PC에 넣어줘야 해당 instruction으로 돌아감).

 

 

 

Exception 예제

 

＊add 명령어에서 exception 발생

　40　　sub　$11, $2, $4

　44　　and　$12, $2, $5

　48　　or 　 $13, $2, $6

　4C　　add　$1,  $2, $1

　50　　slt 　 $15, $6, $7

　54　　lw 　 $16, 50($7)

　...

 

＊Handler

　8000 0180　　sw　$25, 1000($0)

　8000 0184　　sw　$26, 1004($0)

　...

 

＊EX stage에서 exception 발생

　ㆍ현재 instruction과 이후 instruction들 모두 flush

 

＊nop으로 flush(bubble), 그리고 handler로 jump

 

 

 

Multiple Exceptions

다중(동시) 예외

 

＊pipeline은 여러 명령어를 동시에 수행한다.

　ㆍ그러므로 동시에 여러 exception이 발생할 수도 있다.

 

＊간단한 접근법: 더 일찍인 instruction(가장 실행 진척도가 높은. 가장 후의 stage인.)의 예외부터 처리한다.

　ㆍ뒤이어 오던 instruction들은 함께 flush.

　ㆍ첫 단추부터 잘 수정해보자는.

　ㆍ"precise" exceptions

 

＊복잡한(complex) pipeline에서는,

　ㆍcycle마다 여러 명령어를 실행할 수 있다.

　ㆍ명령어의 결과 순서가 실행 순서와 같지는 않다(out-of-order).

　ㆍ규칙(명령어 순서대로, precise exceptions)을 지키기가 어렵다(어려워도 불가능은 아닌듯??)!

 

 

 

Imprecise Exceptions

 

ㆁpipeline 동작을 멈추고, 현 상태를 저장한다.

　＊exception의 원인(하나 혹은 여럿)도 함께 저장한다.

 

ㆁ이제 handler가 동작하도록 한다.

　＊어느 instruction(하나 혹은 여럿)이 exception을 일으켰는지 파악하고,

　＊어떤 것을 처리할지, 어떤 것을 flush할지 결정한다.

　　ㆍ"manual" completion(수동 종료??)가 필요할지도 모른다.

 

ㆁ하드웨어는 간결화(단순화, simplify)하되, handler 소프트웨어는 더욱 정교하게(복잡하게, complex).

　＊소프트웨어적으로 해결

 

ㆁ명령어를 다중 수행할 수 있는 out-of-order pipeline인 복잡한 최신 CPU에서는 사용할 수 없는 방법.

　＊위에서 말한 것과 다르게 하드웨어가 간단하지 않으니까.

 

 

 

잠깐 복습,

Exception의 정의는?

CPU 내부에서 발생한, 예기치 못한 상황.

Unexpected events that arise within the CPU.

 

---

<4.10 - Parallelism via Instructions>

 

 

 

Instruction-Level Parallelism (ILP)

 

ㆁPipelining: 여러 instruction들을 병렬적으로(in parallel) 수행.

 

ㆁILP를 향상시키기 위한 두 가지 방법.

　1. Deeper pipeline(더 여러 stage로 더 깊게)

　　ㆍstage마다 적은 일을 하면 → clock cycle은 짧아진다.

　　ㆍ한 stage에 같은 clock cycle이므로,

　　　stage를 좀 더 세분화해서 한 단계가 적은 일을 하면,

　　　속도는 더 빨라진다.

　　　한 명령어가 거칠 총 stage 수는 많아지겠지만(더 병렬적으로 처리).

　2. Multiple issue

　　(※ issue = Instruction Fetch)

　　ㆍpipeline stage들을 복제 → multiple pipelines

　　ㆍclock cycle마다 여러 instruction들을 동시에 시작(말그대로 동시에)

　　ㆍ최근에는, CPI(Cycles Per Instruction) < 1 이 되므로, 대신 Instructions Per Cycle(IPC)를 사용.

　　ㆍe.g., 4GHz 4-way multiple-issue에서는,

　　　16 BIPS(160억 IPS), peak CPI = 0.25, peak IPC = 4.

　　　(하지만 실제로는 instruction의 의존성 때문에 병렬성이 감소됨(peak IPC인 4까지 성능을 내기는 힘듦).)

 

 

 

Multiple Issue

 

＊Static multiple issue

　ㆍ어떤 명령어가 어느 cycle에서 실행할지 이미 결정이 되어 있는 것(runtime 전에 결정. 컴파일러가.).

　ㆍ컴파일러가 instruction들이 함께 issue될 수 있도록 묶어줌(group).

　ㆍ"issue slots"으로 패키지화함(packages them into "issue slots").

　ㆍ컴파일러가 hazards를 감지하고 회피시켜 줌.

 

＊Dynamic multiple issue

　ㆍCPU가 insturction stream을 시험해보고, 각 cycle에 issue할 instruction들을 고름.

　ㆍ컴파일러가 instruction의 순서를 재배치함으로써 도와줄 수는 있음.

　ㆍruntime 동안에 CPU는 고급 기술(advanced techniques)로 hazard를 해결함.

 

 

 

Speculation

추측

 

ㆁ어떤 instruction을 할 것인지 "예상"하는 것

　＊우선 할 수 있기만하면 가능한 빨리 operation을 시작해본다.

　＊예상이 맞았는지 확인한다.

　　ㆍ맞았다면, operation을 그대로 진행하여 완수한다.

　　ㆍ틀렸다면, roll-back하고 올바른 작업을 한다.

 

ㆁstatic과 dynamic multiple issue 모두에서 공통적으로 사용하는 형태.

 

ㆁ예시

　＊branch의 결과를 추측하는 것

　　ㆍ만약 틀렸다면 Roll back하고 제대로.

　＊load 명령어에서

　　ㆍ특정한 메모리 주소에서 값을 읽어오는 것인데,

　　　값이 변하지 않을 경우가 많아서 미리 읽어둔 값을 그대로 사용하려고 함.

　　　그런데 해당 주소의 값이 변했다면 Roll back하고 제대로.

 

 

 

Compiler/Hardware Speculation

컴파일러에서 추측/하드웨어에서 추측

 

＊컴파일러는 instruction들의 순서를 재배치할 수 있다.

　ㆍe.g., branch 직전의 load(두 칸 여유 필요)를 옮긴다든가..

　ㆍ예상이 실패하면, "fix-up" instruction을 끼워넣어서 복구시킬 수 있다.

 

＊하드웨어는 실행할 instruction들을 내다볼 수 있다(앞서볼 수 있다. look ahead).

　ㆍinstruction들이 실제로 수행되어야 하는 게 맞았는지 알기 전까지

　　buffer가 instruction들을 수행하여 결과를 갖고있다가,

　ㆍ추측이 맞았으면 그대로 가져다가 쓰고,

　ㆍ추측이 실패하면 buffer를 비운다(flush).

 

 

 

Speculation and Exceptions

추측과 예외

 

＊만약 추측으로 미리 실행하는 instruction에서 exception이 발생한다면 어떻게 될 것인가?

　ㆍ미리 실행하는게 도중일 수도, 완료되었을 수도 있고, flush될 수도 있는건데..

　ㆍe.g., null-pointer 체크 전에 추측성(sepculative) load 명령어나..

 

＊Static speculation

　ㆍISA의 도움(support)을 받아, exception들을 지연시킬 수 있다.

 

＊Dynamic speculation

　ㆍinstruction이 완수(completion)될 때까지

　　exception들을 buffer해둘 수 있다(마치 일어나지 않은 것처럼).

 

 

 

Static Multiple Issue

 

＊컴파일러가 instruction들을 "issue packets"("issue slots")로 그룹화함(함께 issue될 수 있도록).

　ㆍinstruction 그룹은 single cycle에(한 cycle에, 즉, 동시에) issue될 수 있다.

　ㆍ해당 명령어들이 필요로 하는 pipeline 자원에 의해 결정된다(묶여진다).

　　(명령어의 의존성을 고려하고, 각 stage별로 수행되면서도(pipeline 자원) 동시에 수행 가능한 명령어들)

 

＊하나의 issue packet을, 하나의 아주 긴 instruction처럼(64bytes, 128bytes처럼..) 생각해라.

　ㆍ여러개의 동시 작업들(multiple concurrent operations)로 지정한다.

　ㆍ→ Very Long Instruction Word(VLIW)

 

 

 

Scheduling Static Multiple Issue

 

ㆁ컴파일러는 반드시 모든/몇몇 hazard를 제거해야 한다.

　＊instruction들의 순서를 재배치하고, issue packet들로 묶는다.

　＊한 packet은 의존성(dependency)이 없도록 묶여진 것들이다(그러니 동시에 실행 가능).

　＊다른 packet들 사이에는 좀 의존성이 있을 수도 있다.

　　ㆍISA에 따라 다르다; 컴파일러는 반드시 알아야 한다!

　＊만약 필요하다면, NOP(stall, bubble)을 삽입한다.

 

 

 

MIPS with Static Dual Issue

2개씩 동시실행

 

ㆁ2-issue packets

　＊1 ALU/branch instruction

　＊1 load/store instruction

　＊64-bit 정렬(aligned)

　　ㆍ32-bit*2 = 64-bit

　　ㆍALU/branch, 그 후 load/store

주소	instruction type	pipeline stages
n	ALU/branch	IF	ID	EX	MEM	WB
n+4	load/store	IF	ID	EX	MEM	WB
n+8	ALU/branch		IF	ID	EX	MEM	WB
n+12	load/store		IF	ID	EX	MEM	WB
n+16	ALU/branch			IF	ID	EX	MEM	WB
n+20	load/store			IF	ID	EX	MEM	WB

　　ㆍ8*4=32. 32-bit씩 2개가 동시에. 주소의 앞뒤 정렬순서는 ALU/branch 이후 load/store.

　　ㆍ사용되지 않는 instruction은 nop으로 충진(packet으로 잘 나눠도 bubble이 발생할 수는 있으니).

 

 

 

MIPS with Static Dual Issue

＊ALU/branch는 기존 장치를 이용한다고 하면,

　load/store를 위한 장치와 datapath 등이 추가되었다.

　(여기서는 branch를 ID stage로 당긴 모델이 아닌, 예전 모델 기준인듯.)

　ㆍ레지스터는 함께 사용. 새로운 경로가 복제되듯이 추가됨.

　ㆍ그리고, ALU/branch는 메모리에서 가져오거나 쓰지 않으므로,

　　바로 통과하여 레지스터로 WB 하는 경로로 수정되어 있음.

 

 

 

Hazards in the Dual-Issue MIPS

 

ㆁ병렬적으로(in parallel) 많은 instruction을 동시에 실행하는(execute) 형태.

 

ㆁEX data hazard

　＊single-issue에서도 stall을 피하기 위해 forwarding 기법을 사용했었음.

　＊이제는 같은 packet에서 ALU 결과값을 load/store에 이용하지는 않을 것임.

　　ㆍadd 　$t0, $s0, $s1

　　　load　$s2, 0($t0)

　　ㆍ종속성이 있으므로, 다른 packet으로 나누었을 것임(같은 타이밍은 아예 불가능).

　　ㆍ다른 타이밍(다른 packet)에도 여전히 stall은 발생.

　　　(single-cycle도 한 단계 늦은 타이밍에도 stall이 발생해서 forwarding했음.)

 

ㆁload-use data hazard

　＊여전히 1-cycle의 지연(latency)을 필요로하지만, 이번에는 2 instruction들이 동시진행된다는 점.

 

ㆁ더욱 적극적인 scheduling이 필요해진다.

 

 

 

Scheduling 예제

 

＊dual-issue MIPS를 위한 Scheduling

　ㆍIPC = 5/4 = 1.25 (c.f., peak IPC = 2)

 

 

 

심화: Loop Unrolling

반복문을 풀어헤치기

 

ㆁloop body를 복제하여 더 병렬적인 형태로 풀어버리는 것.

　＊loop-control overhead를 줄여준다.(한 번에 여러번의 내용을 실행해서, branch가 줄어듦)

 

ㆁ복제(loop 내용)마다 다른 레지스터를 사용하도록 한다.

　＊"register renaming"이라고 한다.

　＊loop에서 유발되는 "반의존성(anti-dependency)"를 방지한다??

　　ㆍ같은 레지스터를 load한 후 다시 store할 때.

　　ㆍaka. "name dependence". 레지스터 이름을 재사용.

 

ㆁ위의 동일한 예제(Loop)를 풀어헤친것

　＊IPC = 14/8 = 1.75

　　ㆍ기존의 1.25보다 상승하여 더 2(peak IPC)에 근접해짐.

　　ㆍ하지만 code 길이(instruction memory size)와 레지스터의 비용은 증가함.

 

 

 

Dynamic Multiple Issue

 

＊"Superscalar" processors

 

＊CPU가 각각의 cycle에 어떤 instruction이 issue될지 결정하는 것.

　ㆍruntime에 동적으로(컴파일러가 아닌 CPU가 하니 runtime).

　ㆍCPU가 향후 instruction들을 미리 내다보고, 시험해본 후, 순서를 정하여 실제로 실행.

　ㆍstructure hazards, data hazards를 방지해줌.

 

＊컴파일러의 scheduling의 필요성을 줄임(필요에 따라 보조적으로 할 수는 있음).

　ㆍ그러나 여전히 도움이 될 수는 있음(필요에 따라 보조적으로 할 수는 있음).

　ㆍ전체적으로 code의 제어권은 CPU가 가짐.

 

 

 

Dynamic Multiple Scheduling

 

＊CPU가 stall을 방지하기 위해 instruction들을 순서에 상관없이(out-of-order) 실행하도록 허용하는 것.

　ㆍ하지만 레지스터에 결과를 반영(commit)하는 것은 순서대로 해야한다.

 

＊예시

　lw　 　$t0, 20($s2)

　addu　$t1, $t0, $t2

　sub 　 $s4, $s4, $t3

　slti　　$t5, $s4, 20

　ㆍaddu가 lw 때문에 기다리는 동안 sub을 시작할 수 있게 해줌.

 

 

 

Dynamically Scheduled CPU

(데이터 종속적이지 않아서 순서 상관없이 실행될 수 있는 애들을 말하는 것 같음.

어차피 CPU가 issue 순서는 미리 시험해본 후 한거니까.. hazard 방지해서)

 

 

 

Register Renaming

superscalar processors의 중요한 특징 중 하나

 

ㆁ어떤 instruction이 어떤 레지스터를 사용하는 경우,

　원래는 해당 레지스터를 사용해야 하고, 그걸 위해 기다리거나 했지만,

　다른 레지스터를 이용가능하도록 하여 그 레지스터를 사용.

　instruction의(code의) 표기된 레지스터와, 실제 수행의 레지스터가 다를 수 있다는 것.

 

ㆁreservation station들과 reorder buffer(commit unit)은 효과적으로 register renaming을 제공한다.

 

ㆁreservation station에 instruction issue가 진행될 때,

　＊만약 피연산자가 당장 레지스터 뭉치(일반적인 경우)나 reorder buffer에서 값을 사용할 수 있다면,

　　ㆍreservation station으로 복사된다.

　　ㆍ이제 레지스터는 필요없으므로, 여기에 값이 다시 쓰여져도 된다.

　＊아직 피연산자가 준비되지 않았다면,

　　ㆍfunction unit에서 값을 가져와 reservation station으로 제공한다.

　　ㆍ값을 끌어왔으므로, 다른 곳에서 필요하지 않다면 레지스터에 값을 쓰지 않아도 된다.

　　　(아마 다른 곳도 비슷한 타이밍이면 끌어와서 해결했을 듯. 먼 타이밍이면 쓰긴 해둬야할 듯..??)

 

 

 

Speculation

 

ㆁbranch를 예측해서 막힘없이 계속 issue하는 것

　＊제대로 branch 결과가 결정되기 전까지는 commit하진 않는다.

 

ㆁLoad speculation

　＊load와 cache miss의 delay를 방지한다.

　　ㆍ유효주소를 예측한다.

　　ㆍload 값을 예측한다.

　　ㆍ다른(단계적으로 이전) store가 완료되기 전에 값을 load한다.

　　ㆍ원래 load에서 레지스터에 값이 쓰일 단계는 생략한다.

　＊추측이 확실시 되기 전까지는 load를 commit하진 않는다.

 

 

 

Why Do Dynamic Scheduling?

 

※ 우리가 사용하는 대부분의 CPU은 superscalar processor. 즉, dynamic 방식을 사용함.

 

＊왜 그 전대로 컴파일러가 code를 scheduleing(static)하도록 하지 않고??

 

＊컴파일러가(실행 전에) 모든 stall들을 예측가능한 것이 아니다.

　ㆍe.g., cache miss는 runtime에서나..

＊branch 주변은 항상 schedule할 수 있는 것이 아니다.

　ㆍbranch 결과는 동적으로 결정되기 때문에.

＊ISA별로 다른 구현방식은 각자 다른 latency(지연)과 hazard를 낳는다.

　ㆍ컴파일러가 모든 프로세서의 내부구조를 파악하고, 다른 구현방식별로 모두 대처하기 힘듦.

 

 

 

Does Multiple Issue Work?

다중 issue는 동작하는가?

 

＊그렇다. 하지만, 우리의 기대에는 덜 미친다.

＊프로그램은 ILP(Instruction-Level Parallelism)을 제한시키는

　의존성(dependency)을 갖고있기 때문.

＊몇몇 의존성은 제거하기 힘들다(hard to eliminate).

　ㆍe.g., pointer aliasing(다른 포인터가 실은 같은 곳을 가리키고 있는)

＊몇몇 parallelism은 활용하기 힘들다(hard to expose).

　ㆍinstruction issue가 진행 중일 때 창 크기를 제한하는 것??

＊메모리의 delay와 제한된 bandwith

　ㆍpipeline이 full인 상태로(peak) 유지하기 힘들다(우리의 기대보다 덜 하게 된다).

＊speculation이 잘 들어맞으면 도움을 줄 수 있다.

 

 

 

Power Efficiency

전력 효율

 

＊dynamic scheduling와 speculation의 복잡성은 전력을 더 필요하게 만든다.

＊전력면에서는 superscalar보다 "여러개의 간단한 프로세서"가 더 나을 수도 있다.

Microprocessor	출시	Clock Rate	Pipeline Stages	Issue width	out-of-order Speculation	Cores	Power
i486	1989	25MHz	5	1	no	1	5W
Pentium	1993	66MHz	5	2	no	1	10W
Pentium Pro	1997	200MHz	10	3	YES	1	29W
P4 Willamette	2001	2000MHz	22	3	YES	1	75W
P4 Prescott	2004	3600MHz	31	3	YES	1	103W
Core	2006	2930MHz	14	4	YES	2	75W
UltraSparc III	2003	1950MHz	14	4	no	1	90W
UltraSparc T1	2005	1200MHz	6	1	no	8	70W

 

---

<4.11 - Real Stuff: The ARM Cortex-A8 and Intel Core i7 Pipelines>

 

 

 

---

<4.12 - Going Faster: Instruction-Level Parallelism and Matrix Multuply>

 

 

 

---

<4.14 - Fallacies and Pitfalls>

 

 

 

Fallacies

착오

 

ㆁpipelining은 쉽다??

　＊기본적인 생각(basic idea)는 쉬움.

　＊하지만 실제로 상세하게 파고들면 아주 어려움.

　　ㆍe.g., hazard 감지해내기

 

ㆁpipelining은 기술에 의존적이지 않다(independent of technology)??

　＊그러면 왜 처음부터 동일한 pipelining이 아니었겠나..

　＊더 많은 transister(트랜지스터, 반도체소자)는 더 발전된 기술을 가능하도록 한다.

　＊pipeline과 관련된 ISA 설계는 기술 양상(technology trend)를 고려해야 한다.

　　ㆍe.g., predicted instructions

 

 

 

Pitfalls

함정

 

ㆁ안 좋은(poor) ISA 설계는, pipelining하기 더 힘들어지게 한다.

　＊e.g., 복잡한 ISA (VAX, IA-32)

　　ㆍpipeline 동작을 만들기 위해 큰(significant) overhead가 발생한다.

　　ㆍIA-32의 micro-op 방식.

　＊e.g., 복잡한 adressing 모델

　　ㆍ레지스터 발전의 부작용, 메모리 우회법

　＊e.g., delayed branch(branch의 결과를 기다려야 하는 것)

　　ㆍ발전된 pipeline은 long delay slot을 사용하여 해결한다??

 

---

<4.15 - Concluding Remarks>

 

 

 

Concluding Remarks

끝맺으며

 

＊ISA는 datapath와 control 설계에 영향을 준다.

＊datapath와 control은 ISA 설계에 영향을 준다.

　(서로에게 영향을 준다.)

＊pipelining은 parallelism을 이용하여 instruction의 throughput(처리량)을 늘리는 것이다.

　ㆍ같은 시간당 더 많은 instruction을 완수할 수 있게 한다.

　ㆍ하지만 한 instruction의 시간(latency)이 줄어드는 것은 아니다.

＊Hazards: structural, data, control

＊ILP(Instruction-Level Parallelism)에서 multiple issue와 dynamic scheduling

　ㆍ의존성(dependency)은 parallelism을 방해한다(peak 성능보다 실제로 낮게 동작한다).

　ㆍ복잡성(complexity)는 power wall로 향하게한다(전력소모가 늘어난다).