[컴퓨터구조] ILP & superscalar processor(2)

현재 글은 이 글에서 이어진다.

---

Superscalar Implementation

 슈퍼스칼라를 구현하는데 필요한 요소들은 다음과 같다.

• 여러개의 instruction을 병렬적으로 다룰 수 있어야 한다.
  • 동시에 여러개의 instruction을 fetch하기 위한 전략을 가진다
  • 여러개의 instruction을 병렬적으로 initiate, issue할 수 있다.
• 프로세스를 올바른 순서로 commit(complete) 할 수 있어야 한다.
• 레지스터의 값과 관련하여 true dependency을 다룰 수 있는 로직, 실행 중 해당 값을 필요한 위치에 전달하기 위한 매커니즘이 필요하다.

Tomasulo algorithm

https://en.wikipedia.org/wiki/Tomasulo%27s_algorithm

 tomasulo 알고리즘은 instruction에 대한 동적 스케줄링에 대한 컴퓨터 하드웨어에 대한 알고리즘으로, 저번 글에서 설명한 여러가지 기법 및 구조를 사용하는 superscalar 머신의 동작을 설명할 수 있다.

Tomasulo 알고리즘의 구조

구조

reservation station

 일종의 instruction window로, 각 functional unit에 대해 각각 존재한다. 레지스터 또는 reorder buffer로부터 데이터가 전달되어 한 instruction에 대응되는 데이터가 모두 준비되면 functional unit에 전달하여 연산을 수행할 수 있는 구조로 되어 있어 out-of-order issue을 지원한다.

 register renaming 기능을 지원하는 역할도 한다. reservation station의 각 라인에는 관련된 instruction의 데이터들이 저장된다. 구체적으로 한 라인의 각 칸에는 instruction의 operand 값들이 저장된다. operand에는 register의 값이 바로 올 수도 있고, 순서를 맞추기 위해 reorder buffer에 저장된 값이 올 수도 있다. 만약 operand가 아직 올 수 없는 경우 그 이유 ( 관련된 연산 ) 를 해당 칸에 저장하게 된다. 

instruction status

reservation stations. 데이터가 준비된 경우 주소를, 준비되지 않은 경우 이유(대응되는 instruction)를 명시.

각 레지스터의 상태 정보. 데이터가 준비되지 않은 경우 일종의 이유를 명시.

register renaming 기능 지원

 위 그림에서 ADD는 R2 레지스터 때문에 MUL에 대한 anti dependency을 가진다. 이때 reservation station을 사용하는 경우 각 레지스터(operand)에 대응되는 칸이 존재하며, 각 instruction은 해당 라인의 모든 칸에 적절한 주소가 전달되었을 때 실행된다. 실행 결과는 일차적으로 reorder buffer에 저장되며 precise exception이 보장될 때 레지스터로 이동된다.

각 instruction이 대응되는 reservation station에 전달되는 구조

reorder buffer

 imprecise exception을 방지하고 speculation에 대한 rollback 기능을 지원함으로써 out-of-order completion을 보장하기 위한 목적으로 사용되는 버퍼이다. 임시적으로 결과 값을 저장하고, 해당 값을 쓸 수 있을 때 WRITE 동작을 수행한다.

 

tomasulo 알고리즘에 의한 instruction 실행 예시

특징

• Reservation Station
  • true dependency interlocking
    • 내부적으로 레지스터 관련 정보가 존재하여 true dependency 발생 시 interlocking할 수 있다고 한다.
  • register renaming
    •  instruction에 명시된 레지스터에서 값을 가져오는게 아니라, station 에 전달된 값을 이용하여 연산을 진행하므로 true dependency가 아닌 경우 레지스터의 이름은 의미가 없다.
    • 값이 준비된 경우 데이터가 바로 들어가나, 아직 준비되지 않은 경우 해당 데이터와 관련된 연산 및 주소 값이 들어간다. 
  • out-of-order issue: 데이터가 먼저 준비되는 순서대로 Functional Unit에 전달되어 연산이 진행될 수 있다.
• Internal forwarding bus
  • internal forwarding 위한 버스가 존재한다. 해당 버스를 이용하여 연산 결과를 바로 전달하여 dependency 문제를 해결할 수 있다.
• Reorder Buffer
  • precise exception 및 speculation을 위한 back up이 가능하게 되어 out-of-order completion이 가능해진다.

단점

 데이터를 전달할 때 버스를 사용한다. 버스는 구조가 간단하다는 장점이 있지만, 해당 버스에 연결된 자원이 많아질수록 버스 이용을 위한 경쟁이 심해지므로 성능이 떨어지는 문제점을 가지고 있다.

 성능을 높이기 위해서는 더 많은 functional unit과 더 큰 reservation station이 필요하다. 이때 reservation station이 커짐에 따라 station이 잠시 보관하고 있는 데이터들을 구분하거나 검색하기 위한 방법이 필요하게 된다. 이때 해당 데이터들을 충분히 빠르게 찾기 위해서는 데이터의 내용 기반으로 검색이 가능한 CAM(Content Addressable Memory) 구조를 가질 필요가 있는데, 이 경우 reservation station의 구조가 매우 복잡해지는 단점이 있다.