Dynamical ILP

ILP(Instruction Level Parallelism)

• Moore's Law가 붕괴되면서 필연적으로 나올 수 밖에 없는 개념
• Pipelining, Superscalar, VLIW and EPIC

Pipelining

• Simple Pipelining
  • 기본적인 파이프라이닝.
  • Control Hazard와 Data Hazard 존재
    • Forwarding / Stalling
  • Rigid Sequencing. WB만 하고싶어도 MEM 사이클에 있긴 해야함
• 더 발전하기 위해 Dynamic Scheduling 도입
  • Out of Order로 처리하자!

Dynamically Scheduled Processor

• 해결해야 할 문제들
  • Structural Hazards : 아직 처리할 곳이 비지 않았을 수도
  • RAW Data Hazard : 아직 Operand들의 값이 계산 중인 RAW
  • WAR WAW Hazard
• Reservation Station
  • Structural Hazard 해결 가능 (준비 안 되었으면 대기!)
  • RAW 해결 가능 (마찬가지!)
• WAR and WAW
  • In order일 때는 고민할 필요가 없었음. (당연하니깐!)
  • Out of Order에서는 고민해야함
    • Register Renaming으로 해결
• Exception
  • Exception이 생기면 정확히 생긴 위치로 이동해야 함
  • 하지만 우리는 Exception이 생긴 Inst가 언제 계산되었는지 알 수가 없음
    • 그 전 Instruction이 처리되지 않았을 수도, 아니면 반대일 수도
    • 그래서 Reordering Buffer가 필요. Commit 대기하다가 순서 맞추면 Commit
• Reordering Buffer (ROB)
  • Register value을 Forwarding 하는 기능도
  • 값이 이미 구해졌는지 확인하게 해 줌
• Dependence Through Memory
  • Load 할 때 ROB 먼저 확인
    • 있음 가져오기
    • store하는 게 없으면 메모리 액세스
    • 근데 만약 아직 정해지지 않은 주소로 store를 하려고 하면 ? 기다려야 함
  • Load / Store Queue
    • 그래서 이 검사를 빠르게 하기 위해 Load/Store Queue 사용
    • Load Queue는 Queue(FIFO) 일 필요는 없음.
      • 모든 Load에 대해 필요한 값이 나왔는지 동시에 체크
    • Store Queue는 FIFO
      • Store 할 수 있을 때 store
    • RS와 하는 건 비슷
• Superscalar Execution
  • 한 번에 여러 개의 IF

Register Renaming

• Register Renaming을 어디서 할 것인가?
• Rename Register 개수
  • in flight = RS + EX + LD + ST
  • rename = RS + EX + LD
  • ROB <= In flight

Prediction and Speculation

• Branch Prediction 같은 것들
• OoO Speculation도 Prediction의 일종
• ROB가 다 해줌. 일단 계산 후 ROB에 저장하고, 필요하면 쓰고, 필요없어지면 Squash
• Branch Target Buffer & Branch History Table
  • 들로 Target address와 taken/not taken 여부 계산
• Return address stack
  • return ( 어디로 리턴일지 모름) 을 위해 backtrace같이 주소 저장
• Memory data speculation
  • 필요한 걸 예상해서 미리 가져오자
• Prefetching
  • Coverage와 Accuracy 사이에서 타협해야함
    • Coverage가 높으면 쓸데없는 것 많이 가져옴
    • accuracy가 높으면 안 가져온 애들도 많음
  • next value, next n value, stride 등 다양한 policy
• Speculation은 꼭 Dynamic할 때만 할 수 있는 것이 아님
  • Compile할 때 비싼 operation들은 먼저 처리하고, 값을 따로 저장해서 branch 이후에 사용할 수도?

Simultaneous Multithreading

• Thread Scheduling Policies
  • Coarse block scheduling
    • coarse하면 작은 틈을 활용하긴 어렵지만, 큰 틈을 더 효과적으로 사용 가능
    • Context Switch 할 틈도 주고.
  • Fine grained block scheduling
    • Fine grained하면 작은 틈 활용 가능
    • 하지만 Context Switch 매우 어려움
  • Simultaneous MT
    • 그냥 막 써!
    • Policies:
      • Fair vs Prioritized
    • Multiple PC, RF 필요
      • 그 외 Thread Aware한 Branch Predictor 등등도
      • Reservation Station은 고려 필요 없음
• Superscalar와의 비교
  • What to Fetch
    • Superscalar에서는 가장 오래된 게 최고
      • Speculation 많이 안 해도 되고, 필요한 값들 준비도 많이 되었을 것이고
    • SMT에선 안 그럼
      • Cache hit spec, branch spec 등등 다양한 policy 있음
      • 그래서 크게 안 다름 ㅋㅋ
• Branch Prediction의 Cost와 Benefit 모두 다운~
• Rename register의 수, writeback port의 수 등이 대표적 병목