나무모에 미러 (일반/밝은 화면)
최근 수정 시각 : 2023-04-08 22:59:32

Scoreboarding


1. 개요
1.1. Scoreboard의 구성1.2. 파이프라인 단계
2. 예시
2.1. cycle 12.2. cycle 22.3. cycle 32.4. cycle 42.5. cycle 52.6. cycle 62.7. cycle 72.8. cycle 82.9. cycle 92.10. cycle 102.11. cycle 112.12. cycle 122.13. cycle 132.14. cycle 142.15. cycle 152.16. cycle 162.17. cycle 172.18. cycle 182.19. cycle 192.20. cycle 202.21. cycle 212.22. cycle 22

1. 개요

Scoreboarding은 CDC 6600에서 도입한 비순차적 실행 기법이다. Tomasulo 알고리즘과는 달리, 비순차적 실행에 필요한 정보를 각 기능 단위[1]에 흩어놓지 않고 Scoreboard에 모아서 관리하는 것이 특징이다.

1.1. Scoreboard의 구성

Scoreboard는 다음과 같은 정보를 저장해야 한다.

1.2. 파이프라인 단계

Scoreboarding에서, 가져온(fetched) 명령어는 다음과 같은 파이프라인 단계들을 거치게 된다.Scoreboarding의 pseudocode (위키피디아)

2. 예시

위 설명만으로는 구체적인 동작 방식을 이해하기 쉽지 않으므로, 예시를 들어 한 사이클씩 그 동작을 설명한다. 표에는 각 사이클이 끝난 직후의 상태를 표시한다.
예시 원본 [3]

다음과 같은 명령어들을 처리하는 것을 생각해 보자. F0...F10은 부동소수점 레지스터이고, MUL, SUB, DIV, ADD는 각각 곱셈, 뺄셈, 나눗셈, 덧셈을 처리하는 명령어이다. 피연산자(operand)는 첫 번째가 목적지 레지스터를 지정하고, 나머지 둘은 계산하는 데 필요한 source 레지스터를 지정한다. LOAD의 경우, 해당하는 주소에서 값을 가져온다.
LOAD F6, 34+R2
LOAD F2, 45+R3
MUL F0, F2, F4
SUB F8, F6, F2
DIV F10, F0, F6
ADD F6, F8, F2


다음은 cycle 0일 때의 초기 상태이다. 첫 명령어인 LOAD가 발행되기 전이다. 명령어 상태에는 다음 완료해야 할 단계를 나타낸다.
[clearfix]
명령어 상태
명령어 다음
LOAD F6, 34+R2 Issue
LOAD F2, 45+R3
MUL F0, F2, F4
SUB F8, F6, F2
DIV F10, F0, F6
ADD F6, F8
Register result status
F0 F2 F4 F6 F8 F10
- - - - - -
Functional Unit status
남은 시간 기능 단위 Busy Op Fi Fj Fk Qj Qk Rj Rk
Load/Store No
Multiply No
Add/Sub No
Divide No

2.1. cycle 1

명령어 상태
명령어 다음
LOAD F6, 34+R2 R.O
LOAD F2, 45+R3 Issue
MUL F0, F2, F4
SUB F8, F6, F2
DIV F10, F0, F6
ADD F6, F8
Register result status
F0 F2 F4 F6 F8 F10
- - - Load/Store - -
Functional Unit status
남은 시간 기능 단위 Busy Op Fi Fj Fk Qj Qk Rj Rk
Load/Store Yes Load F6 R2 Yes
Multiply No
Add/Sub No
Divide No
첫 번째 LOAD가 발행되었다. Load/Store FU의 Busy가 Yes로 설정되고, 목적지 레지스터인 F6은 해당 FU에서 값을 가져와야 한다.

2.2. cycle 2

명령어 상태
명령어 다음
LOAD F6, 34+R2 Exec
LOAD F2, 45+R3 Issue
MUL F0, F2, F4
SUB F8, F6, F2
DIV F10, F0, F6
ADD F6, F8
Register result status
F0 F2 F4 F6 F8 F10
- - - Load/Store - -
Functional Unit status
남은 시간 FU Busy Op Fi Fj Fk Qj Qk Rj Rk
Load/Store Yes Load F6 R2 No
Multiply No
Add/Sub No
Divide No
Load/Store FU가 이미 사용 중이므로 구조 위험에 의해 다음 LOAD가 발행되지 않는다. 첫 번째 LOAD는 피연산자 읽기가 완료되었고 Rk가 No로 설정된다.

2.3. cycle 3

명령어 상태
명령어 다음
LOAD F6, 34+R2 W.B
LOAD F2, 45+R3 Issue
MUL F0, F2, F4
SUB F8, F6, F2
DIV F10, F0, F6
ADD F6, F8
Register result status
F0 F2 F4 F6 F8 F10
- - - Load/Store - -
Functional Unit status
남은 시간 FU Busy Op Fi Fj Fk Qj Qk Rj Rk
Load/Store Yes Load F6 R2 No
Multiply No
Add/Sub No
Divide No
첫 번째 LOAD의 실행이 완료되었다.

2.4. cycle 4

명령어 상태
명령어 다음
LOAD F6, 34+R2 -
LOAD F2, 45+R3 Issue
MUL F0, F2, F4
SUB F8, F6, F2
DIV F10, F0, F6
ADD F6, F8
Register result status
F0 F2 F4 F6 F8 F10
- - - - - -
Functional Unit status
남은 시간 FU Busy Op Fi Fj Fk Qj Qk Rj Rk
Load/Store No
Multiply No
Add/Sub No
Divide No
첫 번째 LOAD의 되쓰기까지 완료되었다. 레지스터에는 34+R2의 주소에 있던 값이 쓰였고, FU status와 Register result status는 다시 비워진다.

2.5. cycle 5

명령어 상태
명령어 다음
LOAD F6, 34+R2 -
LOAD F2, 45+R3 R.O
MUL F0, F2, F4 Issue
SUB F8, F6, F2
DIV F10, F0, F6
ADD F6, F8
Register result status
F0 F2 F4 F6 F8 F10
- Load/Store - - - -
Functional Unit status
남은 시간 FU Busy Op Fi Fj Fk Qj Qk Rj Rk
Load/Store Yes Load F2 R3 Yes
Multiply No
Add/Sub No
Divide No
앞에서 구조 위험이 해소되어, 두 번째 LOAD가 발행되었다. 첫 LOAD때와 동일하다.

2.6. cycle 6

명령어 상태
명령어 다음
LOAD F6, 34+R2 -
LOAD F2, 45+R3 Exec
MUL F0, F2, F4 R.O
SUB F8, F6, F2 Issue
DIV F10, F0, F6
ADD F6, F8
Register result status
F0 F2 F4 F6 F8 F10
Multiply Load/Store - - - -
Functional Unit status
남은 시간 FU Busy Op Fi Fj Fk Qj Qk Rj Rk
Load/Store Yes Load F2 R3 No
Multiply Yes Mult F0 F2 F4 Load/Store No Yes
Add/Sub No
Divide No
Multiply 기능 단위는 Busy하지 않으니, 구조 위험이 없어 MUL이 발행되었다. 첫 LOAD는 피연산자 읽기가 완료되었다.

2.7. cycle 7

명령어 상태
명령어 다음
LOAD F6, 34+R2 -
LOAD F2, 45+R3 W.B
MUL F0, F2, F4 R.O
SUB F8, F6, F2 R.O
DIV F10, F0, F6 Issue
ADD F6, F8
Register result status
F0 F2 F4 F6 F8 F10
Multiply Load/Store - - Add/Sub -
Functional Unit status
남은 시간 FU Busy Op Fi Fj Fk Qj Qk Rj Rk
Load/Store Yes Load F2 R3 No
Multiply Yes Mult F0 F2 F4 Load/Store No Yes
Add/Sub Yes Sub F8 F6 F2 Load/Store Yes No
Divide No
아직 MUL의 피연산자가 준비되지 않아, 피연산자 읽기 단계를 완료할 수 없다. LOAD가 실행되었고, SUB가 발행된다.

2.8. cycle 8

명령어 상태
명령어 다음
LOAD F6, 34+R2 -
LOAD F2, 45+R3 -
MUL F0, F2, F4 R.O
SUB F8, F6, F2 R.O
DIV F10, F0, F6 R.O
ADD F6, F8 Issue
Register result status
F0 F2 F4 F6 F8 F10
Multiply - - - Add/Sub Divide
Functional Unit status
남은 시간 FU Busy Op Fi Fj Fk Qj Qk Rj Rk
Load/Store No
Multiply Yes Mult F0 F2 F4 Load/Store Yes Yes
Add/Sub Yes Sub F8 F6 F2 Load/Store Yes Yes
Divide Yes Div F10 F0 F6 Multiply No Yes
LOAD는 되쓰기까지 완료하면서, 레지스터에 불러온 값을 다른 기능단위들이 필요로 하는지 보고 값이 준비되었다는 표시로 Rj, Rk를 Yes로 설정한다. DIV가 발행된다.

2.9. cycle 9

명령어 상태
명령어 다음
LOAD F6, 34+R2 -
LOAD F2, 45+R3 -
MUL F0, F2, F4 Exec
SUB F8, F6, F2 Exec
DIV F10, F0, F6 R.O
ADD F6, F8 Issue
Register result status
F0 F2 F4 F6 F8 F10
Multiply - - - Add/Sub Divide
Functional Unit status
남은 시간 FU Busy Op Fi Fj Fk Qj Qk Rj Rk
Load/Store No
10 Multiply Yes Mult F0 F2 F4 Load/Store No No
2 Add/Sub Yes Sub F8 F6 F2 Load/Store No No
Divide Yes Div F10 F0 F6 Multiply No Yes
MUL과 SUB의 피연산자 읽기가 완료되며, Rj와 Rk를 No로 설정한다. 필요한 값을 Multiply FU에서 받아 와야 하기 때문에 DIV는 피연산자 읽기 단계를 완료할 수 없다. SUB가 Add/Sub 기능단위를 사용 중이기 때문에 구조 위험이 해결될 때까지 ADD를 발행할 수 없다.

2.10. cycle 10

명령어 상태
명령어 다음
LOAD F6, 34+R2 -
LOAD F2, 45+R3 -
MUL F0, F2, F4 Exec
SUB F8, F6, F2 Exec
DIV F10, F0, F6 R.O
ADD F6, F8 Issue
Register result status
F0 F2 F4 F6 F8 F10
Multiply - - - Add/Sub Divide
Functional Unit status
남은 시간 FU Busy Op Fi Fj Fk Qj Qk Rj Rk
Load/Store No
9 Multiply Yes Mult F0 F2 F4 Load/Store No No
1 Add/Sub Yes Sub F8 F6 F2 Load/Store No No
Divide Yes Div F10 F0 F6 Multiply No Yes
MUL과 SUB가 계산되고 있다.

2.11. cycle 11

명령어 상태
명령어 다음
LOAD F6, 34+R2 -
LOAD F2, 45+R3 -
MUL F0, F2, F4 Exec
SUB F8, F6, F2 W.B
DIV F10, F0, F6 R.O
ADD F6, F8 Issue
Register result status
F0 F2 F4 F6 F8 F10
Multiply - - - Add/Sub Divide
Functional Unit status
남은 시간 FU Busy Op Fi Fj Fk Qj Qk Rj Rk
Load/Store No
8 Multiply Yes Mult F0 F2 F4 Load/Store No No
0 Add/Sub Yes Sub F8 F6 F2 Load/Store No No
Divide Yes Div F10 F0 F6 Multiply No Yes
SUB의 실행이 완료되었다.

2.12. cycle 12

명령어 상태
명령어 다음
LOAD F6, 34+R2 -
LOAD F2, 45+R3 -
MUL F0, F2, F4 Exec
SUB F8, F6, F2 -
DIV F10, F0, F6 R.O
ADD F6, F8 Issue
Register result status
F0 F2 F4 F6 F8 F10
Multiply - - - - Divide
Functional Unit status
남은 시간 FU Busy Op Fi Fj Fk Qj Qk Rj Rk
Load/Store No
7 Multiply Yes Mult F0 F2 F4 Load/Store No No
Add/Sub No
Divide Yes Div F10 F0 F6 Multiply No Yes
SUB는 되쓰기까지 완료되었다. 해당하는 부분을 비운다.

2.13. cycle 13

명령어 상태
명령어 다음
LOAD F6, 34+R2 -
LOAD F2, 45+R3 -
MUL F0, F2, F4 Exec
SUB F8, F6, F2 -
DIV F10, F0, F6 R.O
ADD F6, F8 R.O
Register result status
F0 F2 F4 F6 F8 F10
Multiply - - Add/Sub - Divide
Functional Unit status
남은 시간 FU Busy Op Fi Fj Fk Qj Qk Rj Rk
Load/Store No
6 Multiply Yes Mult F0 F2 F4 Load/Store No No
Add/Sub Yes Add F6 F8 F2 Yes Yes
Divide Yes Div F10 F0 F6 Multiply No Yes
구조 위험이 해결되어 ADD를 발행할 수 있다.

2.14. cycle 14

명령어 상태
명령어 다음
LOAD F6, 34+R2 -
LOAD F2, 45+R3 -
MUL F0, F2, F4 Exec
SUB F8, F6, F2 -
DIV F10, F0, F6 R.O
ADD F6, F8 Exec
Register result status
F0 F2 F4 F6 F8 F10
Multiply - - Add/Sub - Divide
Functional Unit status
남은 시간 FU Busy Op Fi Fj Fk Qj Qk Rj Rk
Load/Store No
5 Multiply Yes Mult F0 F2 F4 Load/Store No No
2 Add/Sub Yes Add F6 F8 F2 No No
Divide Yes Div F10 F0 F6 Multiply No Yes
ADD의 피연산자 읽기가 완료되었다.

2.15. cycle 15

명령어 상태
명령어 다음
LOAD F6, 34+R2 -
LOAD F2, 45+R3 -
MUL F0, F2, F4 Exec
SUB F8, F6, F2 -
DIV F10, F0, F6 R.O
ADD F6, F8 Exec
Register result status
F0 F2 F4 F6 F8 F10
Multiply - - Add/Sub - Divide
Functional Unit status
남은 시간 FU Busy Op Fi Fj Fk Qj Qk Rj Rk
Load/Store No
4 Multiply Yes Mult F0 F2 F4 Load/Store No No
1 Add/Sub Yes Add F6 F8 F2 No No
Divide Yes Div F10 F0 F6 Multiply No Yes
MUL과 ADD를 계산 중이다.

2.16. cycle 16

명령어 상태
명령어 다음
LOAD F6, 34+R2 -
LOAD F2, 45+R3 -
MUL F0, F2, F4 Exec
SUB F8, F6, F2 -
DIV F10, F0, F6 R.O
ADD F6, F8 W.B
Register result status
F0 F2 F4 F6 F8 F10
Multiply - - Add/Sub - Divide
Functional Unit status
남은 시간 FU Busy Op Fi Fj Fk Qj Qk Rj Rk
Load/Store No
3 Multiply Yes Mult F0 F2 F4 Load/Store No No
0 Add/Sub Yes Add F6 F8 F2 No No
Divide Yes Div F10 F0 F6 Multiply No Yes
ADD의 계산이 완료되었다.

2.17. cycle 17

명령어 상태
명령어 다음
LOAD F6, 34+R2 -
LOAD F2, 45+R3 -
MUL F0, F2, F4 Exec
SUB F8, F6, F2 -
DIV F10, F0, F6 R.O
ADD F6, F8 W.B
Register result status
F0 F2 F4 F6 F8 F10
Multiply - - Add/Sub - Divide
Functional Unit status
남은 시간 FU Busy Op Fi Fj Fk Qj Qk Rj Rk
Load/Store No
2 Multiply Yes Mult F0 F2 F4 Load/Store No No
Add/Sub Yes Add F6 F8 F2 No No
Divide Yes Div F10 F0 F6 Multiply No Yes
ADD가 써야 할 F6에 있는 결과를 DIV가 아직 읽지 못했으므로, ADD는 되쓰기 단계를 완료하지 못한다.

2.18. cycle 18

명령어 상태
명령어 다음
LOAD F6, 34+R2 -
LOAD F2, 45+R3 -
MUL F0, F2, F4 Exec
SUB F8, F6, F2 -
DIV F10, F0, F6 R.O
ADD F6, F8 W.B
Register result status
F0 F2 F4 F6 F8 F10
Multiply - - Add/Sub - Divide
Functional Unit status
남은 시간 FU Busy Op Fi Fj Fk Qj Qk Rj Rk
Load/Store No
1 Multiply Yes Mult F0 F2 F4 Load/Store No No
Add/Sub Yes Add F6 F8 F2 No No
Divide Yes Div F10 F0 F6 Multiply No Yes
MUL을 계산하고 있다.

2.19. cycle 19

명령어 상태
명령어 다음
LOAD F6, 34+R2 -
LOAD F2, 45+R3 -
MUL F0, F2, F4 W.B
SUB F8, F6, F2 -
DIV F10, F0, F6 R.O
ADD F6, F8 W.B
Register result status
F0 F2 F4 F6 F8 F10
Multiply - - Add/Sub - Divide
Functional Unit status
남은 시간 FU Busy Op Fi Fj Fk Qj Qk Rj Rk
Load/Store No
0 Multiply Yes Mult F0 F2 F4 Load/Store No No
Add/Sub Yes Add F6 F8 F2 No No
Divide Yes Div F10 F0 F6 Multiply No Yes
MUL의 계산이 완료되었다.

2.20. cycle 20

명령어 상태
명령어 다음
LOAD F6, 34+R2 -
LOAD F2, 45+R3 -
MUL F0, F2, F4 -
SUB F8, F6, F2 -
DIV F10, F0, F6 R.O
ADD F6, F8 W.B
Register result status
F0 F2 F4 F6 F8 F10
- - - Add/Sub - Divide
Functional Unit status
남은 시간 FU Busy Op Fi Fj Fk Qj Qk Rj Rk
Load/Store No
Multiply No
Add/Sub Yes Add F6 F8 F2 No No
Divide Yes Div F10 F0 F6 Multiply Yes Yes
MUL은 되쓰기까지 완료되면서, DIV에 필요한 다른 결과가 준비된다.

2.21. cycle 21

명령어 상태
명령어 다음
LOAD F6, 34+R2 -
LOAD F2, 45+R3 -
MUL F0, F2, F4 -
SUB F8, F6, F2 -
DIV F10, F0, F6 Exec
ADD F6, F8 W.B
Register result status
F0 F2 F4 F6 F8 F10
- - - Add/Sub - Divide
Functional Unit status
남은 시간 FU Busy Op Fi Fj Fk Qj Qk Rj Rk
Load/Store No
Multiply No
Add/Sub Yes Add F6 F8 F2 No No
40 Divide Yes Div F10 F0 F6 Multiply No No
이제 DIV는 피연산자 읽기 단계를 완료할 수 있다. 이로써 WAR 위험이 해결되게 된다.

2.22. cycle 22

명령어 상태
명령어 다음
LOAD F6, 34+R2 -
LOAD F2, 45+R3 -
MUL F0, F2, F4 -
SUB F8, F6, F2 -
DIV F10, F0, F6 Exec
ADD F6, F8 -
Register result status
F0 F2 F4 F6 F8 F10
- - - - - Divide
Functional Unit status
남은 시간 FU Busy Op Fi Fj Fk Qj Qk Rj Rk
Load/Store No
Multiply No
Add/Sub No
39 Divide Yes Div F10 F0 F6 Multiply No No
ADD의 되쓰기까지 완료된다.
[1] Functional Unit; FU. CPU에서 명령어를 처리할 때 실제로 연산(사칙연산, 논리연산 등)을 수행하는 요소. 현대 CPU에서는 처리 속도 향상을 위해 같은 기능 단위가 여러 개 존재하기도 해서 여러 명령어를 동시에 처리한다.[2] 예컨대, 이 명령어가 사용해야 하는 기능 단위를 앞선 명령어들이 이미 사용하고 있어서 기다려야 하는지 등[3] 여기 있는 그림은 본 문서에 서술된 것과 약간의 차이가 있는데, 이는 본 문서에서는 일관적으로 각 사이클이 끝난 직후를 묘사한 반면, 그림에서는 실행 중인 과정을 묘사하였기 때문이다.