[컴퓨터구조#8] Speculative Execution - commit, ROB, FF, PRF

지난 글의 ILP에 이어, 이번에는 out of order execution에 더해 speculative execution을 구현하는 방법에 대해 살펴볼 것이다.

2024.04.14 - [Computer Architecture] - [컴퓨터구조#7-2] ILP (Instruction-Level Parallelism) - Tomasulo Algorithm

목차

1. Speculation
2. Reorder Buffer (ROB)
3. Example
4. Future File
5. Physical Register File

---

1. Speculation

이전 Tomasulo 알고리즘에서 사용된 Reservaton Station을 잠깐 살펴보자. RS entry는 각 명령어가 완료되는 시점까지 할당된다. 연속적인 data-dependent 명령어들은 RS id를 참조한다. 즉, output register는 RS id로 rename된다.

예를 들면, 다음과 같이 두 명령어가 R3을 사용하는 경우,

RS1: SUB R3, R1, R2
RS2: ADD R4, R4, R3

 아래와 같이 RS1으로 rename된다.

RS1: SUB RS1, R1, R2
RS2: ADD RS2, R4, RS1

명령어가 완료되면, 결과는 RF로 써진다. 이후 완료된 명령에 대해서는 RS 이름이 더 이상 사용되지 않는다.

또한, RS는 피연산자를 유지하고 있어 WAR hazard를 제거한다. 다음과 같이 R1에 대한 WAR hazard가 있는 경우, RS1이 old R1 값을 가지고 있기 때문에, RS2는 RS1이 실행되기 전에 R1에 덮어쓸 수 있다.

RS1: SUB R3, R1, R2
RS2: ADD R1, R4, R5

 

일반 out-of-order execution과 달리 Speculation Execution에서는 잘못된 명령어를 실행하는 경우 회복 메커니즘이 필요하다. Control을 추측해야 하는 경우, 명령어들이 프로그램 실행 상 올바른 경로에 있다는 것을 모르는 경우에도 fetch 및 execution을 수행해야 한다. 다른 추측의 경우, 모르는 주소의 store 명령어가 있을 때도 load를 수행해야 할 수도 있고, dependent한 명령어들의 결과를 예측해서 수행해야 할 수도 있다. 빠른 speculation execution을 위해서는 정확하게 예측하고 빠르게 회복하는 것이 중요하다.

이를 지원하기 위해서, 명령어 완료와 별개의 명령어 commit 단계를 생각해야 한다. commit이란, 명령어가 exception-free하고 non-speculative 상태가 되어 RF를 업데이트하고 캐시를 통해 메모리에 store하는 작업을 완료하게 되는 것을 뜻한다. 즉, 실행이 완료되고 그 이후에 CPU를 떠나 system state를 영구적으로 바꾸는 경우 commit되었다고 한다.

• commit은 반드시 in-order로 수행되어야 하며, 
• commit 전까지는 결과값들은 reorder buffer에 버퍼링되어야 한다.

 

2. Reorder Buffer

Tomasulo에서는 명령어가 완료되는 순간 RF를 업데이트했지만, ROB를 사용하는 speculative execution에서는 명령어 완료부터 commit까지 ROB가 결과를 저장하고 있는다.

ROB는 다음과 같은 특징을 바탕으로 동작한다.

• 각 명령어는 하나의 ROB entry와 RS etnry를 갖는다.
• RS entry는 명령어 완료 시점에 de-allocate된다.
• ROB는 out-of-order로 업데이트될 수 있으며, in-order로 retire한다(FIFO).
• ROB에서 명령어가 빠져나가는 순간이 해당 명령어가 commit되는 순간이다.
• ROB entry는 명령어 종류, 값(pending instr/value), 목적지(dest register/store queue pointer), status(completed/exception) 의 정보를 갖고 있다.
• ROB id (tag)를 통해 register renaming을 수행할 수 있다.

본격적인 예시로 들어가기 전 Register Alias Table(RAT)에 대해서 살펴보자. RAT는 Tomasulo의 RF에서 Q 필드를 분리한 것이라고 생각하면 된다. 아키텍처상 레지스터 이름을 바탕으로, 가장 최신의 값을 가지고 있는 ROB entry number 혹은 RF를 맵핑한다. (ROB entry #, RF valid) 두 개의 필드를 갖고 있는데, 

• RF가 가장 최신 값인 경우 RF valid = true이다.
• 만약 값이 생성되었지만 아직 retire되지 않은 경우 ROB가 결과를 갖고 있어 피연산자를 ROB에서 가져오게 된다.
• 만약 값이 생성되기 전이라면 ROB number를 renamed tag로 사용한다.

 

3. Example: ROB+RS

ROB와 RS를 사용하는 경우 예시를 통해 어떻게 speculative execution이 실행되는지 살펴보자. 

configuration은 Tomasulo에서와 동일하며, 한 사이클에 하나의 명령어만 issue 및 commit한다는 조건이 추가되었다.

Cycle 0

예시 명령어는 다음과 같다. (이전과 동일)

I1: LW R1, 10(R9)
I2: SUB R3, R1, R2
I3: ADD R2, R4, R5
I4: XOR R3, R4, R5
I5: LW R6, 20(R1)
I6: AND R7, R2, R3
I7: OR R8, R6, R7

총 5개의 table이 존재한다.

ROB : FIFO

Name	Op	Value	Dest	Status
RB0
RB1
RB2
RB3
RB4
RB5

 RAT

	Q	RF Valid
R1		T
R2		T
R3		T
R4		T
R5		T
R6		T
R7		T
R8		T
R9		T

Adder Reservation Station : 이제 renaming은 ROB를 통해서 하므로 RS의 name field는 삭제

Time	Busy	Op	V1	V2	Q1	Q2
	N
	N
	N

Load Reservation Station: 이제 renaming은 ROB를 통해서 하므로 RS의 name field는 삭제

Time	Busy	Op	V1	V2	Q1	Q2
	N
	N

RF: commit 이후 non-speculatively correct value만 저장

	R1	R2	R3	R4	R5	R6	R7	R8	R9
Value	X1a	X2a	X3a	X4a	X5a	X6a	X7a	X8a	X9a

 

Cycle 1

I1: LW R1, 10(R9)

먼저, ROB의 첫 번째 위치 RB0에 I1을 삽입한다. (status는 pending)

Name	Op	Value	Dest	Status
RB0	LW		R1	P
RB1
RB2
RB3
RB4
RB5

업데이트 대상인 R1은 RAT에 RB0으로 업데이트해주고 RF는 valid하지 않으므로 F로 업데이트한다.

RAT	Q	RF Valid
R1	RB0	F
R2		T
R3		T
R4		T
R5		T
R6		T
R7		T
R8		T
R9		T

LW 명령어이므로 LRS에 다음과 같이 업데이트한다.

Time	Busy	Op	V1	V2	Q1	Q2
4	Y	LW	X9a+10
	N

 

Cycle 2

I2: SUB R3, R1, R2

ROB에 I2를 삽입한다.

Name	Op	Value	Dest	Status
RB0	LW		R1	P
RB1	SUB		R3	P
RB2
RB3
RB4
RB5

업데이트 대상인 R3은 RAT에 RB1으로 업데이트해주고 RF는 valid하지 않으므로 F로 업데이트한다.

RAT	Q	RF Valid
R1	RB0	F
R2		T
R3	RB1	F
R4		T
R5		T
R6		T
R7		T
R8		T
R9		T

Adder RS에 다음과 같이 명령어를 업데이트한다. 두 번째 피연산자는 RF에서 가져온 값 그대로, 첫 번째 피연산자는 RB0으로 Q 필드를 업데이트한다.

Time	Busy	Op	V1	V2	Q1	Q2
	Y	SUB		X2a	RB0
	N
	N

이전 LW 명령어의 시간도 1 줄여준다.

Time	Busy	Op	V1	V2	Q1	Q2
3	Y	LW	X9a+10
	N

 

Cycle 3

I3: ADD R2, R4, R5

ROB에 I3을 삽입한다. 

Name	Op	Value	Dest	Status
RB0	LW		R1	P
RB1	SUB		R3	P
RB2	ADD		R2	P
RB3
RB4
RB5

업데이트 대상인 R2은 RAT에 RB2으로 업데이트해주고 RF는 valid하지 않으므로 F로 업데이트한다.

RAT	Q	RF Valid
R1	RB0	F
R2	RB2	F
R3	RB1	F
R4		T
R5		T
R6		T
R7		T
R8		T
R9		T

Adder RS에 다음과 같이 명령어를 업데이트한다. 두 피연산자 모두 RAT 참조 시 RF valid true이므로 그대로 값을 가져온다.

Time	Busy	Op	V1	V2	Q1	Q2
	Y	SUB		X2a	RB0
1	Y	ADD	X4a	X5a
	N

이전 LW 명령어의 시간도 1 줄여준다.

Time	Busy	Op	V1	V2	Q1	Q2
2	Y	LW	X9a+10
	N

 

Cycle 4

I4: XOR R3, R4, R5

ROB에 I4를 삽입한다. 

Name	Op	Value	Dest	Status
RB0	LW		R1	P
RB1	SUB		R3	P
RB2	ADD		R2	P
RB3	XOR		R3	P
RB4
RB5

업데이트 대상인 R3은 최신 값 유지를 위해 RAT에서 기존 RB1에서 RB3으로 바꿔준다.

RAT	Q	RF Valid
R1	RB0	F
R2	RB2	F
R3	RB3	F
R4		T
R5		T
R6		T
R7		T
R8		T
R9		T

Adder RS에 다음과 같이 명령어를 업데이트한다. 두 피연산자 모두 RAT 참조 시 RF valid true이므로 마찬가지로 그대로 값을 가져온다. 이전 ADD 명령어 시간도 1 줄여준다.

Time	Busy	Op	V1	V2	Q1	Q2
	Y	SUB		X2a	RB0
0	Y	ADD	X4a	X5a
1	Y	XOR	X4a	X5a

이전 LW 명령어의 시간도 1 줄여준다.

Time	Busy	Op	V1	V2	Q1	Q2
1	Y	LW	X9a+10
	N

 

Cycle 5

I5: LW R6, 20(R1)

ROB에 I5를 삽입한다. 또한, ADD 명령어가 수행이 끝났으므로 ROB의 ADD 명령어(RB2)에 결과값을 저장하고 status를 C로 바꿔준다

Name	Op	Value	Dest	Status
RB0	LW		R1	P
RB1	SUB		R3	P
RB2	ADD	X2b	R2	C
RB3	XOR		R3	P
RB4	LW		R6	P
RB5

업데이트 대상인 R6은 RAT에서 RB4로 업데이트한다.

*주의: 아직 RB2가 complete되었을 뿐, commit된 것은 아니므로 RF에는 업데이트되지 않았다.

RAT	Q	RF Valid
R1	RB0	F
R2	RB2	F
R3	RB3	F
R4		T
R5		T
R6	RB4	F
R7		T
R8		T
R9		T

수행이 끝난 ADD를 삭제하고 XOR의 Time도 1 줄여준다.

Time	Busy	Op	V1	V2	Q1	Q2
	Y	SUB		X2a	RB0
	N
0	Y	XOR	X4a	X5a

이전 LW 명령어의 시간도 1 줄여준다. I5를 삽입한다.

Time	Busy	Op	V1	V2	Q1	Q2
0	Y	LW	X9a+10
	Y	LW			RB0

 

Cycle 6

I6: AND R7, R2, R3

ROB에 I6을 삽입한다. 또한, 이 단계에서 XOR(RB3)과 LW(RB0)이 완료되었으므로 업데이트해준다.

Name	Op	Value	Dest	Status
RB0	LW	X1b	R1	C
RB1	SUB		R3	P
RB2	ADD	X2b	R2	C
RB3	XOR	X3b	R3	C
RB4	LW		R6	P
RB5	AND		R7	P

I6의 업데이트 대상인 R7은 RAT에서 RB5로 업데이트한다.

RAT	Q	RF Valid
R1	RB0	F
R2	RB2	F
R3	RB3	F
R4		T
R5		T
R6	RB4	F
R7	RB5	F
R8		T
R9		T

수행이 끝난 XOR를 삭제하고, SUB의 Q1인 RB0를 V1으로 이동한다. (다음 사이클부터 계산이 시작된다. -> 한 사이클당 하나의 명령어만 각 RS에서 issue된다고 가정했기 때문! 이번 사이클에서는 AND가 issue된다. 즉, AND의 Time이 1로 새로 업데이트된다. 하지만 이 부분은 speculative execution과는 orthogonal한 문제이므로 가정에 따라서 SUB가 먼저 issue되고 다음 사이클에 AND가 시작될 수도 있다)

I6 AND를 추가한다. RAT에서 R2, R3 참조 시 RF valid가 false이므로 ROB에서 RB2, RB3를 lookup한다. 두 명령어 모두 상태가 Completion이므로 ROB value를 가져온다.

Time	Busy	Op	V1	V2	Q1	Q2
	Y	SUB	X1b	X2a
1	Y	AND	X2b	X3b
	N

수행이 끝난 이전 LW를 지우고, younger LW의 Q1 RB0를 V1으로 옮겨온다. (한 사이클당 하나의 명령어만 LW RS에서 issue되므로 operand가 준비되고 바로 Time을 4로 set해준다.)

Time	Busy	Op	V1	V2	Q1	Q2
	N
4	Y	LW	X1b+20

 

Cycle 7

I7: OR R8, R6, R7

ROB가 다 찼으므로, FIFO 정책에 따라 complete된 RB0을 evict하고 RB0 이름을 재사용하여 새로 I7을 삽입한다.

Name	Op	Value	Dest	Status
RB1	SUB		R3	P
RB2	ADD	X2b	R2	C
RB3	XOR	X3b	R3	C
RB4	LW		R6	P
RB5	AND		R7	P
RB0	OR		R8	P

I7의 업데이트 대상인 R8은 RAT에서 RB0으로 업데이트한다. 이때, 기존 RB0 (LW)는 커밋되었으므로 RF의 R1은 X1b로 바뀌기 때문에 RAT에서 RF VAlid를 T로 바꿔준다.

RAT	Q	RF Valid
R1		T
R2	RB2	F
R3	RB3	F
R4		T
R5		T
R6	RB4	F
R7	RB5	F
R8	RB0	F
R9		T

SUB의 execution이 시작되고, AND 의 time도 한 사이클 줄어든다. I7의 두 피연산자인 R4와 R5는 아직 모두 계산이 완료되기 전 상황이므로 Q 필드에 넣어준다.

Time	Busy	Op	V1	V2	Q1	Q2
1	Y	SUB	X1b	X2a
0	Y	AND	X2b	X3b
	N	OR			RB4	RB5

LW의 time은 1 줄어든다.

Time	Busy	Op	V1	V2	Q1	Q2
	N
3	Y	LW	X1b+20

RF는 다음과 같이 바뀐다. 

	R1	R2	R3	R4	R5	R6	R7	R8	R9
Value	X1b	X2a	X3a	X4a	X5a	X6a	X7a	X8a	X9a

 

...

이후 다음 사이클에서 AND의 연산이 완료되고, ROB를 업데이트하고, 바뀐 값을 broadcast하고, ... 의 식으로 알고리즘이 진행된다.

 

Mis-speculatioin 시 recovery

만약 ROB에 대해 잘못된 추측을 한다면 어떻게 될까?

in-order retire 시, 만약 mis-speculation bit이 set되었다면, 우선 ROB와 pipeline을 flush하고, PC를 misspeculated 명령어를 가리키도록 바꾼다. 또한, RAT의 모든 entry를 RF로 만든다. RS와 RAT를 모두 리셋하려면 빠른 회복은 힘들다.

즉 retire point까지 기다리는 것ㅇ느 매우 느릴 수 있다. 잘못된 브랜치 예측이 발견되었을 때 곧바로 고쳐야 한다.

 

Store 처리하기

Store 명령어는 시스템 상태를 영구적으로 바꾼다. 따라서 모든 store는 프로그램 순서대로 진행되어야 하며, ROB에서 retire된 이후에만 메모리 시스템으로 보내진다. 이와 관련된 memory dependence를 풀기란 쉽지 않다.

로드의 경우, 피연산자가 준비되자마자 바로 실행하는 것이 성능에 좋다. 로드는 다음 경우에만 실행될 수 있다.

• 피연산자가 준비되고 주소가 계산될 수 있을 때
• ROB 내 같은 주소에 대한 이전 store가 존재하지 않을 때
• ROB 내 모르는 주소에 대한 이전 store가 존재하지 않을 때

 

4. Future File

ROB는 새로운 결과들을 저장한다. out-of-order로 명령어들이 완료되지만, FIFO를 통해 head만 retire시킴으로써 프로세서 상태는 in-order로 업데이트한다. 하지만 사이클당 매우 많은 read와 write을 수행해야 한다(read: 커밋 시 결과 read, invalidate, 피연산자 fetch / write: 명령어 fetch, 업데이트). 이는 ROB를 복잡하고 비싸게 만든다. 이를 해결하기 위해 Future File을 사용할 수 있다.

Future File은 가장 최신의 값만을 갖는 추가적인 RF이다. 즉 RF와 동일한 크기를 갖는다.

• RF가 명령어가 commit될 때만 업데이트되는 것과 달리,
• FF는 명령어가 완료되는 시점에 업데이트된다. (out-of-order일 수 있다.)

Exception이 발생하면, ROB와 pipeline을 flush하고, FF는 RF로 덮어쓴다.

이전에 operand를 가져오는 방법이 ROB, RF, pending에서, FF를 사용한느 경우 선택지는 FF, pending 두 가지로 줄어들게 된다. 즉 FF는 더 많은 speculativity를 제공하기 위한 것이 아니라 복잡성을 줄이기 위한 장치이다.

 

5. Physical Register File

Reservation Station의 대안으로 활용할 수 있다. 중앙화된 PRF를 사용하여, 모든 레지스터 값을 PRF에만 존재하게 함으로써 renaming을 수행할 수 있다.

다음 예시를 통해 살펴보자. I1과 I2 간 RAW/WAR, I2와 I3 간 WAR hazard가 존재한다.

I1: SUB R3, R1, R2
I2: ADD R2, R3, R5
I3: XOR R3, R4, R5

각 명령어가 수행되는 사이클마다 다음과 같이 PRF를 업데이트할 수 있다. renaming을 통해 WAR hazard를 없앨 수 있다.

cycle	1		2		3		4
		PRF		PRF		PRF		PRF
	R1	P1	R1	P1	R1	P1	R1	P1
	R2	P2	R2	P2	R2	P7	R2	P7
	R3	P3	R3	P6	R3	P6	R3	P8
	R4	P4	R4	P4	R4	P4	R4	P4
	R5	P5	R5	P5	R5	P5	R5	P5
실행 중인 명령어	SUB R3, R1, R2		SUB P6, P1, P2 ADD R2, R3, R5		SUB P6, P1, P2 ADD P7, P6, P5 XOR R3, R4, R5		SUB P6, P1, P2 ADD P7, P6, P5 XOR P8, P4, P5

이렇게 PRF를 사용하면, 피연산자 값을 갖는 RS가 필요 없어지고 Issue queue가 대신 필요하게 된다. 즉 Issue queue에서 PRF를 통해 FU에 피연산자를 넘겨주게 된다. 또한 ROB에는 결과 값을 저장하지 않게 된다. Issue queue에 들어가기 전 Register Map Table이라는 구성 요소가 추가로 필요하다.

Register Map Table

architectural register name을 physical register name으로 맵핑해주는 역할을 한다.

별도의 architectural RF가 필요 없어지며, architectural register에 대한 레지스터 맵만 있으면 된다. 다음과 같이 최소 2개의 맵만 필요하다.

• Architectural register map: 기존 architectural RF와 비슷한 역할
• Active register map: Future File과 비슷한 역할

명령어가 커밋될 때는 Architectural RM을 새로운 결과를 갖는 PRF entry를 가리키도록 바꿔주면 된다.

Recovery 시에는, Architectural RM을 Active RM으로 복사하며(기존 RF를 FF로 복사하는 것과 동일), 빠른 회복을 위해서 여러 개의 맵을 저장할 수 있다.

 

기존처럼 RS를 사용하는 방법과 RPF를 사용하는 방법은 각각 장단점이 존재한다.

RS + ROB	PRF
- 레지스터 값은 RS, ROB, Architectural RF, (FF)에 저장된다 - 영역적으로 효율적이지 않을 수 있다 - 값을 여러 곳으로 broadcast해야 함	- 모든 레지스터 값을 한 공간에 저장한다. - 여러 개의 읽기/쓰기 포트를 갖는 ARF보다 훨씬 큰 physical RF가 필요하다. - 명령어가 준비된 후에 PRF를 읽어야 한다 - 결과를 PRF에만 쓴다

 

결국 요약해보면, speculative execution을 위해서는 명령어를 in-order로 커밋하는 것이 핵심이며, ROB와 RS를 합쳐 ROB entry를 바탕으로 register renaming을 수행할 수 있다. 혹은 PRF와 Register map을 활용하여 다른 방법으로 register renaming을 수행할 수도 있다.