SHPC 05 - Dependences and Pipelining

Techniques to Improve Single-Core Performance

• Two major techniques
  • Instruction pipelines : 컨베이어 밸트처럼 한 사이클에 여러 명령어의 서로 다른 단계를 동시에 수행하는 것
  • On-chip caches : 메인 메모리 - CPU 데이터 전송 시간을 줄여주는 기법

Dependences

• 서로 다른 연산간의 순서 관계
  • 의존성을 지키는 순서는 원래 프로그램과 동일한 결과를 아웃풋으로 내뱉을 것
  • 의존성을 위반하면 다른 결과를 내놓을 것 - 이를 기준으로 의존성인지 아닌지 판단 가능
• 종류
  1. Data dependences
     • Data와 관련된 dependence
     • Flow(true) dependence
     • Anti dependence
     • Output dependence
     • Input dependence (실제로 의존성이라 볼 수는 없지만 코드 분석에 있어서 categorization을 위해 만든 개념)
  2. Control dependences
     • Branch와 관련된 dependence

Dependence vs Dependency

뜻은 똑같지만 전자를 쓰는 게 맞다. 그 이유는 맨 처음 이 단어를 사용한 논문에서 dependency가 아닌 dependence를 사용했기 떄문.

Flow Dependence

• True dependence
• Instruction P가 메모리에 쓰기연산을 한 후, 다음 Instruction Q가 해당 부분을 읽는 것
• Read-After-Write (RAW)
• 이 그림에서 파란 노드의 그래프 그림을 Dependence Graph 라고 부른다.

Anti Dependence

• False dependence
• 순서를 바꾸면 결과값이 달라지기 때문에 dependence이다
• Instruction P가 메모리를 읽은 후, 다음 Instruction Q가 해당 부분을 쓰는 것
• Write-After-Read

Output Dependence

• False dependence
• Instruction P가 메모리를 쓴 후 Q가 해당 부분을 쓰는 것
• Write-After-Write

Input Dependence

• 캐시의 동작을 분석하기 위해 만들어둔 개념
• Instruction P가 메모리 영역을 읽은 후 다음 instruction Q가 해당 부분을 읽는 것

True dependence	False dependence
명령어 결과가 이전 명령어의 결과에 따라 달라질 때 사용	변수의 이름을 재사용해서 발생하는 name dependence
포워딩이나 stall 등으로 해결	변수의 이름을 수정하는 컴파일러 최적화 옵션을 통해 해결
e.g. Flow dependence(Data dependence)	e.g. Anti dependence, Output dependence

Basic Block

• 코드가 주어지면 control 의 이동을 그래프로 분석한다
• 이 Control flow graph의 노드가 basic block
• Basic block
  • 컨트롤은 basic block 코드의 시작부에만 들어올 수 있음
  • 컨트롤은 마찬가지로 코드의 마지막 부분에서만 나갈 수 있음
  • 즉 시작부에서부터 끝가지 중단이나 브랜치로 인한 jump가 발생하지 않는 명령어 집합
  • Basic block 내의 instruction들은 앞선 instruction의 실행이 바로 다음 Instruction의 실행을 반드시 보장함
• 찾는 방법 : Leader를 찾는다
  • 아래의 명령어들이 모두 leader라고 볼 수 있음
    1. Function의 첫번째 instruction
    2. conditional/unconditional jump의 target이 되는 Instruction
    3. conditional/unconditional jump의 바로 다음에 있는 Instruction
  • 이 Leader부터 해서 leader에 달린 모든 inst를 포함하나 다음 leader나 end 를 포함하지 않는 inst set을 basic block이라 하는 것

Control-Flow Graph (CFG)

• Directed graph이며 실행 동안 프로그램이 traverse할 수 있는 모든 가능한 경로를 나타냄
  • Node: basic block
    • entry, exit node를 dummy node로 도입(컴파일러의 분석을 편하게 하기 위해)
  • Edge: 가능한 flow of control

Control Dependences

• Q의 실행이 P의 실행에 종속적인 경우를 의미
  • 즉 P의 결과에 따라 Q가 실행되거나 실행되지 않는 경우
  • 
  • 이 그림에서 P에 대해 R은 종속성이 없는데 Q는 있음
• Instruction Q가 P에 control dependent하다는 말은 iff
  1. P→ end 경로 중 모든 P의 inst가 Q의 inst를 앞서는 P → Q → end 경로가 존재한다.
  2. P→ end 경로 중 Q를 통하지 않는 execution path도 존재한다.
• 이 역시 명령어들의 순서를 반드시 지켜야 한다

Instruction Pipeline

• Throughput을 증가시키기 위한 하드웨어 테크닉
  • 12 사이클 → 6 사이클
  • 백만개의 inst 있다고 가정하면, 3백만 → 백만 + 2
• 최근에는 딥러닝으로 이걸 최적화하기도 한다
• 일반적으로는 5단계 파이프라이닝을 수행

Pipeline Hazards

Data Hazard

• 아직 만들어지지 않은 result를 필요로 하는 경우
• 아래 예시에서 WB 이후 생기는 r1 의 데이터를 두번째, 네번째가 필요로 함

Resolving Data Hazards

Stalling the Pipeline

• Hardware적 해결: 데이터가 생길 때까지 bubble을 넣어서 기다린다
  • Bubble : 파이프라인 딜레이를 의미, 버블동안은 이전 stage의 상태를 그대로 유지하면서 기다린다
• 두 사이클이 낭비됨
• Software적 해결: Instruction 사이에 no-op을 삽입하여 소프트웨어적으로 구현 가능하다

Transparent register file

• Hardware적 해결
• 레지스터 파일이 포워딩을 해주는 방식
  • 동일한 사이클에 동일한 레지스터에 읽기와 쓰기 요청이 들어오는 경우, 쓰기 데이터를 읽기 요청에 대한 응답으로 보내주는 식
  • 첫번째 half cycle : register data가 쓰여짐
  • 다음 halft cycle : register data를 읽음
  • 이거 멀티포트로 structural hazard 극복하는 것과 뭐가 다른지 잘 모르겠다
• 수업시간에는 제대로 보지 않고 넘어감

Question

• 멀티포트로 structural hazard 극복하는 것과 뭐가 다른지 잘 모르겠다
  • Structural hazard는 Register file 전체, 메모리 전체를 대상으로 발생하는 hazard
  • 하나의 레지스터에 대한 것은 Data hazard로 분류한다
• 이 방식을 쓴다고 하더라도 그대로 두번의 stall이 필요하지 않나?
  • 위의 예제가 이 방식을 가정한 것. 이 방식을 사용하지 않으면 3 사이클을 쉬어야 한다

Data Forwarding

• Hardware적 해결
• 파이프라인의 output data를 이전 스테이지(EX, MEM)로 전달해 주는 것

Structural Hazards

• 동일한 하드웨어를 두개 이상의 instruction(stage)가 접근하는 경우
• Resource conflict
  • 동일한 메모리 유닛에 IF와 MEM이 동시 접근
  • 동일한 레지스터 유닛에 ID와 WB가 동시 접근

Control Hazards

• 브랜치에 의해 발생
  • 다음 Fetch할 instruction의 주소가 결정되지 않은 것
• 브랜치 결과는 MEM 단계에서야 알 수 있다.
  • MEM에서 다음 PC를 알 수 있다고 가정

Resolving Control Hazards

• Software적 해결
• Delayed branch
  • Delayed slot에 명령어를 배치하여 스케쥴링
  • Delayed slot에는 브랜치 결과와 관계없이 실행되는 명령어들을 담고 있음

Stalling

• 브랜치 결과를 알 수 있을 때까지 기다리는 것
• 세사이클 쉬어야 함
• 하드웨어적 해결 / 소프트웨어적 해결 ?

Branch prediction

• 복잡함
• 예측해서 파이프라인을 방지
• 하드웨어적 해결

In-order Execution

1. Instruction을 Fetch & Decode
2. 각 오퍼런드가 준비되어 있으면(e.g. 메모리에서 레지스터로 로드) 적절한 실행 유닛에 할당(Dispatch)한다
3. 그렇지 않으면 stall한다
4. 실행 결과를 레지스터 파일에 기록한다

• 위 그림에서 Stage의 개수가 더 많은 것들은 시간이 더 많이 걸린다는 것을 의미

Out of Order Execution

Execution이 끝나면 IF를 하는 대신에, Reservation station에 다 넣어놓고 빈자리가 생기면 EX로 넣는다 (이 부분이 Dispatch)

1. Instruction을 fetch 후 decode
2. 적절한 reservation station에 해당 instruction을 issue한다
3. 각 오퍼런드가 준비될 때까지 reservation station에서 기다린다
   • In-order와 다르게 순서 관계 없이 Dispatch가 가능하다
   • 예를 들어 데이터 의존성 때문에 대기중인 명렁어가 있다면, In-order 방식에서는 stall을 하지만 out-of-order 방식에서는 다른 바로 실행 가능한 명령어를 실행 가능하다
   • 이후 나올 Reorder buffer 덕분에 가능하다
4. 적절한 실행 유닛으로 dispatch
5. 실행 결과는 Reorder Buffer에 쓴다.
   • Reorder buffer는 커밋 순서를 보장하기 위해 필요하다.
   • Reorder buffer에서 자신이 가장 오래된 명령어라면 자신의 연산 결과를 커밋(반영)할 수 있다

• 대부분 사용하는 방식

Issue and Dispatching an Instruction

• Issue: Instruction이 ID → Reservation store
• Dispatch: Reservation station → EX

Tomasulo’s Algorithm

• IBM 360/91 에서 구현한 out-of-order scheduling을 위한 알고리즘
  • Backward compatibility
  • OoO를 지원
  • Single Issue로 한번에 하나의 명령어만 파이프라인에 넣음 (←> Superscalar)
    • 그래도 out of order는 가능하다. dependency 이유로 operand 가 준비되지 않았을 때 다른 연산을 먼저 실행 가능함
  • In-order issue → Out of order dispatch → Out of order execution → In-order commit
    • Issue는 순차적으로 하고, dispatch는 순서를 무시하고 수행하고

Retirement (Graduation)

• Reorder buffer slot에서 빠져나오게 되는 것을 의미하며, 다음 경우에 발생
  • Instruction이 커밋되었거나 (permanent change 있음)
  • 삭제된 경우 (permanent change 없음)
• 횟수를 계산해서 리소스를 관리하고 파이프라인 상태를 추적하기도 함

Superscalar Processors

• Dynamic issue multiple instructions in each clock cycle
  • 일반적으로 여러 instruction을 fetch하고 decode함
  • In-order / out-of-order로 issue가 가능하다
• 여러 개의 functional unit을 사용하여 병렬처리한다
• 한번에 fetch하는 instruction의 갯수는 가능한 **Instruction Level Parallelism(ILP)**를 고려한다.
  • 평균적으로 2.8개였다고 함
  • ILP가 제한되어 있기 때문에 한계가 있다.
    • ILP란 명령어 병렬성을 이용해 많은 명령어를 실행하는 것. 파이프라이닝과 슈퍼스칼라 등이 있으며, 여기서는 슈퍼스칼라 상황이니 동시에 실행 가능한 명령어의 수를 고려한다는 뜻
• 현대 프로세서는 Superscalar & pipelined processor
  • EX쪽이 pipeline되어 있다고. 여러모로 복잡하다

VLIW(Very Long Instruction Word) Processors

• 하드웨어가 아니라 컴파일러가 동시에 issue 가능한 instruction을 묶어준다. (소프트웨어적)
• 묶인 instruction은 하나의 long instruction word 가 됨
• Compiler에 의한 static instruction scheduling
• 오 대박 프린터에 이게 들어가 있다고 한다.
  • 내부 인터프리터가 PDF를 인쇄 가능한 형태로 바꿔 주는데 이 과정에서 VLIW를 사용한다고 함

Superscalar vs OoO execution

Superscalar는 여러개의 연산유닛으로 동시에 명령어를 실행하는 반면, Out of order execution은 stall 등 의존성으로 쉬고있는 명령어 대신에 먼저 처리되는게 장점. Superscalar에서 OoO execution을 할 수도 있음