Scoreboarding

1. 개요[편집]

---

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

1.1. Scoreboard의 구성[편집]

---

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

• 명령어 상태(Instruction status) : 처리하고 있는 명령어가 파이프라인의 어느 단계에 있는지에 대한 정보.
• 기능 단위 상태(Functional Unit status) : 각 기능 단위가 어떤 상태인지를 나타내는 정보. 주요 정보는 다음과 같다.
  • Busy : 이 기능 단위가 현재 사용 중인지의 여부를 표시하는 플래그.
  • Op : Operation. 현재 기능 단위에서 처리하고 있는 연산.
  • Fi : 이 기능 단위에서 현재 계산을 다 수행하면 값을 써야 할 목적지 레지스터의 번호
  • Fj, Fk, ... : 현재 계산을 처리한 데 필요한 source 레지스터들의 번호.
  • Qj, Qk, ... : 계산에 필요한 값을 받아 올 기능 단위에 대한 정보. 이 정보는 지금 기능 단위가 처리하고 있는 명령어가 읽어야 할 명령어의 처리가 아직 진행 중일 경우에 필요하다.
  • Rj, Rk, ... : 각각 Fj, Fk, ... 의 값이 준비되었으나, 아직 현재 기능 단위가 읽지 않았음을 표시하는 플래그이다. 이는 현재 기능 단위가 읽기도 전에 다른 기능 단위가 레지스터에 있는 값을 덮어쓰지 않도록 하는 역할을 하여 WAR 위험을 해결한다.
• 레지스터 결과 상태(Register result status) : 레지스터마다, 만약 해당 레지스터에 쓰는 명령어가 처리 중이라면 그것이 어떤 기능 단위에서 값을 받아와야 하는지에 대한 정보.

1.2. 파이프라인 단계[편집]

---

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

• 발행(Issue) : 우선, 명령어를 해석하고, 만약 이 명령어를 발행한 후에 앞선 명령어들과의 구조 위험(structural hazard)이 있는지[2]
  예컨대, 이 명령어가 사용해야 하는 기능 단위를 앞선 명령어들이 이미 사용하고 있어서 기다려야 하는지 등
  확인한 후, 있다면 발행하지 않고 그렇지 않을 때까지 기다린다. 이 구조 위험 확인 때문에 명령어가 발행 단계를 거치는 것은 순차적이어야 한다. 또한 WAW 위험을 해결하기 위해, 이 명령어가 쓸 곳에 쓰는 다른 명령어가 아직 처리 중이라면 발행하지 않는다.
  • 명령어를 발행하게 되면, 사용하는 기능 단위에 해당하는 Scoreboard의 Busy를 Yes로 표시하고, Op, Fi, Fj, Fk에 대한 정보를 채운다. 레지스터 결과 상태를 확인하여, 이 명령어가 읽어야 할 각 레지스터의 값이 어떤 다른 기능 단위에서 계산하고 있다면 그에 대한 정보를 대응되는 Qj, Qk, ...에 채우고 대응되는 Rj, Rk, ... 는 No로 설정한다. 아니라면 해당 레지스터에 값이 준비되어 있고 아직 기능 단위가 읽지 않았으므로 대응되는 Rj, Rk, ...는 Yes로 설정한다.
• 피연산자 읽기(Read Operand) : 피연산자들을 읽기 전에 RAW 위험을 해결하기 위해 피연산자들이 모두 준비될 때까지, 즉 모든 Rj, Rk, ... 가 Yes로 설정될 때까지 기다려야 한다.
  • 피연산자들이 모두 준비되었으면, 레지스터들은 피연산자들을 읽고 Rj, Rk, ...는 모두 No로 설정한다.
• 실행(Execute) : 기능 단위가 연산을 수행한다. 이에 소요되는 시간은 연산의 종류에 따라 수 사이클에서 수십 사이클까지도 소요될 수 있다.
• 되쓰기(Write Back) : 결과를 레지스터에 쓰기 전에 혹시 쓰는 동작이 다른 곳에 필요한 결과를 덮어쓰는지를 확인하고, 만약 그렇다면 그렇지 않을 때까지 기다린다. 이로써 WAR 위험이 해결된다.
  • 이 기능 단위의 결과가 필요한 기능 단위마다, 해당하는 Rj, Rk, ...를 Yes로 설정해 줌으로써 결과가 준비되었다는 걸 알려야 한다. 또한 레지스터에 값을 쓰면서 레지스터 결과 상태 역시 비워야 한다. 마지막으로, 이 기능 단위의 Busy를 No로 표시함으로써 다른 명령어들이 이 기능 단위를 사용할 수 있도록 한다.

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가 발행되기 전이다. 명령어 상태에는 다음 완료해야 할 단계를 나타낸다.

2.1. cycle 1[편집]

---

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

2.2. cycle 2[편집]

---

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

2.3. cycle 3[편집]

---

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

2.4. cycle 4[편집]

---

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

2.5. cycle 5[편집]

---

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

2.6. cycle 6[편집]

---

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

2.7. cycle 7[편집]

---

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

2.8. cycle 8[편집]

---

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

2.9. cycle 9[편집]

---

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

2.10. cycle 10[편집]

---

MUL과 SUB가 계산되고 있다.

2.11. cycle 11[편집]

---

SUB의 실행이 완료되었다.

2.12. cycle 12[편집]

---

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

2.13. cycle 13[편집]

---

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

2.14. cycle 14[편집]

---

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

2.15. cycle 15[편집]

---

MUL과 ADD를 계산 중이다.

2.16. cycle 16[편집]

---

ADD의 계산이 완료되었다.

2.17. cycle 17[편집]

---

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

2.18. cycle 18[편집]

---

MUL을 계산하고 있다.

2.19. cycle 19[편집]

---

MUL의 계산이 완료되었다.

2.20. cycle 20[편집]

---

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

2.21. cycle 21[편집]

---

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

2.22. cycle 22[편집]

---

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