Scoreboarding

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

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

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

위 설명만으로는 구체적인 동작 방식을 이해하기 쉽지 않으므로, 예시를 들어 한 사이클씩 그 동작을 설명한다. 표에는 각 사이클이 끝난 직후의 상태를 표시한다.
예시 원본 [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가 발행되기 전이다. 명령어 상태에는 다음 완료해야 할 단계를 나타낸다.

첫 번째 LOAD가 발행되었다. Load/Store FU의 Busy가 Yes로 설정되고, 목적지 레지스터인 F6은 해당 FU에서 값을 가져와야 한다.

Load/Store FU가 이미 사용 중이므로 구조 위험에 의해 다음 LOAD가 발행되지 않는다. 첫 번째 LOAD는 피연산자 읽기가 완료되었고 Rk가 No로 설정된다.

첫 번째 LOAD의 실행이 완료되었다.

첫 번째 LOAD의 되쓰기까지 완료되었다. 레지스터에는 34+R2의 주소에 있던 값이 쓰였고, FU status와 Register result status는 다시 비워진다.

앞에서 구조 위험이 해소되어, 두 번째 LOAD가 발행되었다. 첫 LOAD때와 동일하다.

Multiply 기능 단위는 Busy하지 않으니, 구조 위험이 없어 MUL이 발행되었다. 첫 LOAD는 피연산자 읽기가 완료되었다.

아직 MUL의 피연산자가 준비되지 않아, 피연산자 읽기 단계를 완료할 수 없다. LOAD가 실행되었고, SUB가 발행된다.

LOAD는 되쓰기까지 완료하면서, 레지스터에 불러온 값을 다른 기능단위들이 필요로 하는지 보고 값이 준비되었다는 표시로 Rj, Rk를 Yes로 설정한다. DIV가 발행된다.

MUL과 SUB의 피연산자 읽기가 완료되며, Rj와 Rk를 No로 설정한다. 필요한 값을 Multiply FU에서 받아 와야 하기 때문에 DIV는 피연산자 읽기 단계를 완료할 수 없다. SUB가 Add/Sub 기능단위를 사용 중이기 때문에 구조 위험이 해결될 때까지 ADD를 발행할 수 없다.

MUL과 SUB가 계산되고 있다.

SUB의 실행이 완료되었다.

SUB는 되쓰기까지 완료되었다. 해당하는 부분을 비운다.

구조 위험이 해결되어 ADD를 발행할 수 있다.

ADD의 피연산자 읽기가 완료되었다.

MUL과 ADD를 계산 중이다.

ADD의 계산이 완료되었다.

ADD가 써야 할 F6에 있는 결과를 DIV가 아직 읽지 못했으므로, ADD는 되쓰기 단계를 완료하지 못한다.

MUL을 계산하고 있다.

MUL의 계산이 완료되었다.

MUL은 되쓰기까지 완료되면서, DIV에 필요한 다른 결과가 준비된다.

이제 DIV는 피연산자 읽기 단계를 완료할 수 있다. 이로써 WAR 위험이 해결되게 된다.

ADD의 되쓰기까지 완료된다.