[ACA] Instruction-level Parallelism (2)

Instruction-level Parallelism (2)

Dynamic Scheduling

Limitations of simple techniques

• A major limitation issue and execution
  • in-order instruction issue and execution
    • 명령어가 프로그램 순서에 따라 issue되고 명령어가 파이프라인에서 stall되면 이후 명령어를 처리할 수 없다.
    • 명령어 j가 long-running 명령어 i에 종속성을 가지면, 명령어 j 이후에 실행될 모든 명령어들은 i가 끝나가 j가 실행될 때까지 stall돼있어야 한다.
• Simple techniques은 약간의 data dependence stalls만 제거할 수 있다.
  • 몇몇 dependence는 런타임까지 알 수 없다.
  • 컴파일러는 micro-architecture의 디테일을 알 지 못할 수 있다.
  • 예측하지 못한 딜레이가 있을 수 있다: multi-level caches

Idea

• 다이나믹 스케쥴링은 'in order' execution을 깼다.
  • Out-of-order execution
    • data operands가 사용가능 하면 즉시 명령어를 실행한다.
• Out-of-order execution을 사용하기 위해, ID pipe stage는 두 stage로 나뉜다.
  • Issue
    • 명령어들은 instruction queue에 저장된다.
    • 명령어들을 decode하고 structure hazards를 확인한다.
  • Read Operands
    • Data hazards가 없을 때까지 기다렸다가 피연산자를 읽는다.

New hazards

• 다뤄야할 새로운 hazards가 있다.
  • WAR
    • Possibility of overwriting a value that has not been read yet
  • WAW
    • Writing twice to the same location
• Idea
  • WAW, WAR hazards를 최소화하기 위해 hw에서 레지스터를 rename해준다.

Register Renaming

Tomasulo's Algorithm

• Tomasulo's Algorithm은 다음을 허용한다.
  • Out-of-order execution
  • anti-, output dependence를 register renaming을 통해 다룰 수 있다.
• Tomasulo's Algorithm에서 각 명령어는 세 스텝을 거친다.
  1. Issue
     • 명령어들을 Instruction Queue에 넣는다.
     • 가능하다면 명령어를 RS(Reservation station)에 보낸다.
     • WAR, WAW를 제거하기 위해 register renaming을 한다.
  2. Execute
     • 새로운 데이터에 대해 버스를 모니터링하고 데이터를 기다리는 명령어에 나눠준다.
     • 피연산자가 사용가능할 때 functional units에 대해 명령어를 실행한다.
  3. Write result

Tomasulo's Approach: Reservation Station

• Register renaming은 RS가 제공한다.

• RS의 각 엔트리는 다음을 포함한다.

  1. Instruction
  2. Buffered operand values (when avaliable)
  3. References to instructions in RS that will provide values

• Operation

  • RS는 사용 가능한 경우 피연산자를 fetch해오고 일시적으로 저장한다.

  • 보류중인 명령어는 그들의 출력을 보내는 RS를 가리킨다.

    • 결과값은 result bus에서 브로드캐스트된다. (Common Data Bus, CDB)

  • 마지막 출력값만 레지스터 파일을 업데이트한다.

  • 명령어를 issue하면 레지스터는 RS를 참조하여 renaming된다.

• 레지스터보다 RS가 더 많을 수도 있다.