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

참고: Computer Architecture: A Quantitative Approach (5th edition) - 3. Instruction-Level Parallelism and its Exploitation

지난 글에 이어, 이번 글에서는 Tomasulo 알고리즘에 대해 살펴볼 것이다.

2024.04.14 - [Computer Architecture] - [컴퓨터구조#7-1] ILP (Instruction-Level Parallelism) - dependence, Out-of-Order execution, 동적 스케줄링

---

Tomasulo Alrgorithm

out-of-order execution을 위한 알고리즘으로, 여러 functional unit 간 컨트롤과 로직을 분산시켜 동적 스케줄링을 수행한다. 구성 요소 및 특징은 다음과 같다.

• Reservation stations: 명령어의 피연산자를 저장
  • reservation station name은 명령어의 임시 아웃풋 이름이 된다.
  • register renaming을 제공하며, 피연산자 값을 계속 유지하여 WAR을 예방한다.
• Common Data Bus (CDB)
  • reservation state와 레지스터를 broadcast하고 업데이트한다.
• In-order issue (dispatch)
  • issue: ready된 명령어 중 functional unit으로 보낼 명령어를 고르는 것
• Out-of-order execution (completion)

Tomasulo 알고리즘을 사용한 MIPS fp unit 구조

Example

다음과 같은 상황의 예시 configuration을 생각해보자.

• 정수 ALU 연산은 2 cycle 소요되며 ALU는 파이프라인되어 있다. (즉 연산이 1 cycle 소요될 수도 있다)
• 메모리에서 로드는 5 cycle 걸린다
• 한 cycle에 하나의 명령어를 issue함
• V1, V2 : RF/CDB에서 오는 피연산자 값
• Q1, Q2: RS entry를 가리키는 피연산자
• 모든 필수적 Vx 값들이 ready 일 때만 연산을 실행할 수 있음
• 서로 다른 functional unit들이 CDB에 simultaneous하게 write할 수 있다고 가정.

Example-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

다음과 같이 총 세 개의 table이 있다.

Adder Reservation Station

Name	Time	Busy	Op	V1	V2	Q1	Q2
RS1		N
RS2		N
RS3		N

Load Reservation Station

Name	Time	Busy	Op	V1	V2	Q1	Q2
LD1		N
LD2		N

Register File

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

 

Cycle 1

명령어 I1은 R9+10에서 R1으로 데이터를 로드하는 명령어이다. 즉, Load Reservation Station에 다음과 같이 명령어를 넣어준다. 로드 시간은 4 cycle 걸린다고 가정하자.

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

또한, RF의 R1에는 기존에 갖고 있던 Value를 지우고 Q에 명령어의 이름을 넣어준다(pending 상황).

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

 

Cycle 2

I2는 R1-R2를 R3에 저장하는 명령어이다. Adder RS에 명령어를 저장한다. RF에서 R1과 R2의 상태를 보면 R1은 Value 대신 Q에 LD1이 있으므로 Q1에 LD1을, R2는 X2a가 value로 저장되어 있으므로 V2에 X2a를 복사해 넣는다.

Name	Time	Busy	Op	V1	V2	Q1	Q2
RS1		Y	SUB		X2a	LD1
RS2		N
RS3		N

이 와중, 한 사이클이 지났으므로 LRS의 LW 명령어 Time은 4에서 3으로 줄어든다.

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

또한, 마지막으로 RF에는 R3에 RS1의 값을 저장할 것이므로 다음과 같이 업데이트한다.

	Q	Value
R1	LD1
R2		X2a
R3	RS1
R4		X4a
R5		X5a
R6		X6a
R7		X7a
R8		X8a
R9		X9a

 

Cycle 3

I3은 R4+R5를 R2에 저장하는 명령어이다. 위와 같은 방법으로 V1, V2에 X4a, X5a를 넣어준다. 피연산자가 다 준비되어 있기 때문에 busy를 Y로 바꾸고 연산은 수행한다. 

Name	Time	Busy	Op	V1	V2	Q1	Q2
RS1		Y	SUB		X2a	LD1
RS2	1	Y	ADD	X4a	X5a
RS3		N

한 사이클이 더 지났으므로 LRS의 LW 명령어 Time은 3에서 2로 줄어든다.

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

RF에는 R2에 RS2의 값을 저장할 것이므로 다음과 같이 업데이트한다.

	Q	Value
R1	LD1
R2	RS2
R3	RS1
R4		X4a
R5		X5a
R6		X6a
R7		X7a
R8		X8a
R9		X9a

 

Cycle 4

I4는 R4와 R5를 XOR하여 R3에 저장한다. 두 값은 역시 RF에서 바로 가져올 수 있으므로 다음처럼 업데이트한다. 이때, 이전 ADD 명령어는 실행이 1 cycle 소요되므로 RS2의 시간은 1에서 0으로 줄어든다.

Name	Time	Busy	Op	V1	V2	Q1	Q2
RS1		Y	SUB		X2a	LD1
RS2	0	Y	ADD	X4a	X5a
RS3	1	Y	XOR	X4a	X5a

LRS의 LW 명령어 Time은 2에서 1로 줄어든다.

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

RF에는 R3에 RS3의 값을 저장할 것이므로, 가장 최신 값을 갖도록 하기 위해 기존 RS1에서 다음과 같이 RS3으로 Q를 업데이트한다.

	Q	Value
R1	LD1
R2	RS2
R3	RS3
R4		X4a
R5		X5a
R6		X6a
R7		X7a
R8		X8a
R9		X9a

 

Cycle 5

ADD의 수행이 끝났으므로 RS에서 없애고, XOR 연산 수행 시간도 0으로 줄어든다.

Name	Time	Busy	Op	V1	V2	Q1	Q2
RS1		Y	SUB		X2a	LD1
RS2		N
RS3	0	Y	XOR	X4a	X5a

I5는 R1+20을 R6에 저장하는 load 명령어이다. 아직 R1 값은 LD1을 기다리는 Q이므로 V1이 아닌 Q1에 LD1을 넣어준다. 아직 언제 operand가 ready될지 모르므로 Time은 설정하지 않는다.

Name	Time	Busy	Op	V1	V2	Q1	Q2
LD1	0	Y	LW	X9a+10
LD2		Y	LW			LD1

RF에는, 수행이 끝난 Add의 결과(X2b)를 R2 Value에 업데이트한다. 또한, LW를 통해 R6의 Q 필드에 LD2를 넣어준다.

	Q	Value
R1	LD1
R2		X2b
R3	RS3
R4		X4a
R5		X5a
R6	LD2
R7		X7a
R8		X8a
R9		X9a

 

Cycle 6

I6은 R2+R3을 R7에 저장하는 AND 연산이다. 다음과 같이 반 공간인 RS2에 업데이트한다.

XOR의 수행이 끝났으므로 RS에서 없애고, 이 사이클에서 LD1의 실행이 끝나 RF에 X1b로 업데이트되므로, 해당 값은 즉시 broadcast되어 LD1을 기다리고 있던 RS1도 Q1의 LD1을 V1의 X1b로 바꿔준다.

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

실행이 완료된 LD1(LW)은 삭제하고, LD2의 Q1이었던 LD1을 V1으로 옮겨준다. 이제 execution이 시작되므로 Time도 4부터 시작한다.

Name	Time	Busy	Op	V1	V2	Q1	Q2
LD1		N
LD2	4	N	LW	X1b+20

RF에는, 수행이 끝난 LW의 결과 X1b를 R1에 업데이트한다. 또한, 수행이 끝난 R3(XOR)도 RF에 업데이트한다. I6이 R7에 값을 저장하므로 R7의 Q필드는 RS2로 바꿔준다.

	Q	Value
R1		X1b
R2		X2b
R3		X3b
R4		X4a
R5		X5a
R6	LD2
R7	RS2
R8		X8a
R9		X9a

 

Cycle 7

I7은 R6 OR R7을 R8에 저장하는 연산이다. 다음과 같이 반 공간인 RS3에 업데이트한다.

RS2의 Time은 0으로 줄어들고, 이전 사이클에 operand가 모두 준비된 RS1도 Time이 1로 시작되어 연산이 시작된다.

Name	Time	Busy	Op	V1	V2	Q1	Q2
RS1	1	Y	SUB	X1b	X2a
RS2	0	Y	AND	X2b	X3b
RS3		Y	OR			LD2	RS2

LD2의 Time은 4에서 3으로 줄어든다.

Name	Time	Busy	Op	V1	V2	Q1	Q2
LD1		N
LD2	3	N	LW	X1b+20

RF의 R8은 Q 필드를 RS3으로 바꿔준다.

	Q	Value
R1		X1b
R2		X2b
R3		X3b
R4		X4a
R5		X5a
R6	LD2
R7	RS2
R8	RS3
R9		X9a

 

Cycle 8

실행이 끝난 RS2는 Adder RS에서 빠지고, 계산 결과는 R7에 업데이트되어 RS3에 broadcast된다.

Name	Time	Busy	Op	V1	V2	Q1	Q2
RS1	0	Y	SUB	X1b	X2a
RS2		N
RS3		Y	OR		X7b	LD2

LD2의 Time은 3에서 2로 줄어든다.

Name	Time	Busy	Op	V1	V2	Q1	Q2
LD1		N
LD2	2	N	LW	X1b+20

RF의 R7도 다음과 같이 업데이트된다.

	Q	Value
R1		X1b
R2		X2b
R3		X3b
R4		X4a
R5		X5a
R6	LD2
R7		X7b
R8	RS3
R9		X9a

..

이와 같은 방식으로 계속해서 진행된다.

 

장점과 단점

Tomasulo 알고리즘의 장단점은 다음과 같다.

• 장점
  • hazard 탐지 로직이 분산되어 있다.
  • WAW와 WAR에 대한 stall을 제거한다: reservation station이 not available한 경우 structural hazard(파이프라인 stall)로 바뀐다.
• 단점
  • 같은 레지스터에 대해 여러 개의 값이 reservation station과 RF에 존재할 수 있다.
  • speculative execution을 지원하지 않고, interrupt가 정밀하지 않다. (다음 글에서 관련 내용 다룰 것)