[Paper Review] Freeway: Maximizing MLP for Slice-Out-of-Order Execution
Motivation
CPU 성능을 높이기 위해, long latency memory access를 hiding 하여 Memory Level Parallelism (MLP) 를 활용하는 연구가 많이 진행됐다. 본 논문은 그 중 Slice-out-or-order (sOoO) 를 revisit 한다.
sOoO에선 에너지 효율성을 높일 수 있는 out-of-order execution 구조를 제안한다. 기존 out-of-order execution 구조에서 사용하는 CAM like structure는 power hungry 하기 때문에, 이를 막고자 independent memory access들에 대해서 memory access와 address-generating instruction을 slice라는 단위로 묶어서 효과적으로 처리한다. (사실 in-order core와 out-of-order core의 hybrid 형이라 생각하면 편하다.)
허나 sOoO에선 slice 간 dependency로 인해 MLP를 maximizing 하지 못하고 block 한다. 따라서 inter-slice dependencies는 MLP 추출 기회를 낮춘다. 좀 더 상세한 구현으로 말하자면, 내부 FIFO가 subsequent independent slice들을 delay 시킨다.
A-IQ: main queue
B-IQ: bypass queue
(1) ld r1 = M[r7] // Slice 1 (2) add r2 = r1 + 1 (3) add r3 = r1 + 1 // Slice 2 (4) ld r4 = M[r3] (5) ld r6 = M[r5] // Slice 3
위 예시 코드를 보면 Slice 1의 r1 (1) 의 결과를 Slice 2 (3)에서 사용하는 것을 볼 수 있다. 이처럼 slice 간 dependency가 문제가 발생해 performance degradation으로 자리잡고 있다. 실험 결과 전체 bypass queue의 stall 요인 중 20% 이상을 차지하는 것으로 나타났다.
Dependent slice 중 65%는 L1 cache hit이 되는 memory operation 연산이 많기 때문에, 만약 이러한 instruction들이 수행 될 수 있다면 전체 성능 향상에 크게 기여할 것이다.
본 논문에선 성능 평가를 위한 기준으로 두 가지를 사용한다.
LSC (Load Slice Core): in-order core에 bypass queue를 통해 stalled instruction을 bypass하여 load instruction을 overlap
Ideal-sOoO: slice 간 full out-of-order execution을 지원하는 구조
Goal
따라서 본 논문은 최신 sOoO core의 능력인 MLP를 추출하는데 발생하는 slice 간 dependency로 인한 delay 문제를 다룬다. 이를 위해 slice 간 dependency를 tracking하여 independent slice를 stall 없이 수행시킨다.
Hardware cost로는 다음과 같이 구성된다.
Register Dependence Table (1 bit per entry): dependent slice를 filter out 하기 위해
Yielding Queue (Y-IQ): filtered slice들이 기다리는 queue로 producer들이 마칠 때까지 기다린다.
본 논문의 contribution을 정리하자면 다음과 같다.
- Slice-dependency는 MLP의 major bottleneck이기 때문에, 해당 slice들의 producer의 latency가 짧더라도 MLP에는 큰 영향을 미친다.
- Independent slice를 수행시킬 수 있는 dependence-aware slice execution policy를 제안한다.
- Dependence-aware slice execution 구현을 위한 최소한의 hardware cost를 사용한다.
- sOoO core 대비 12% 성능 향상 및 full OoO core의 7% MLP 제한이 있다.
본 논문에선 dependent slice를 저장할 FIFO buffer에 대해 실험을 진행했는데, 먼저 FIFO queue를 사용할지, out-of-order queue를 사용할지 논의했다. Out-of-order execution이 가능한 queue는 알다시키 CAM like 구조이기 때문에 hardware cost가 크다.
FIFO queue는 순차적으로 head부터 수행이 될텐데, 이는 dependence graph와 연관이 있을 것이다. 실제 dependence graph의 depth에 따라서 bottleneck이 될 수 있는데, 사전 실험에서 평균적으로 78%의 slice가 independent (depth 0)였고, 나머지 22% 중 72%가 depth 1의 slice 였다고 한다. 즉 대부분 independent slice였기 때문에 FIFO queue로 대부분의 MLP를 노출 시킬 수 있다고 판단했다.
Implementation
Freeway 구조에선 MLP를 향상시키기 위해 LSC의 FIFO slice execution을 버리고 independent slice들에 대해 out-of-order execution 을 수행한다. 이를 위해 dependent slice를 independent slice들과 분리한다.
Y-IQ에 dependent slice들이 ready 상태가 될 때까지 기다리며 independent slice들이 B-IQ에 삽입된다. 대부분 dependent slice는 program order로 ready 되기 때문에 거의 stall 되지 않는다.
이를 위해 최소한의 hardware cost를 사용하는데, 기존 RDT에서 각 entry 별 1-bit이 추가되는데, 이는 해당 instruction이 dependent slice에 포함되는지를 나타낸다. 그리고 entry 별 7 bits씩 확장된 store buffer와 Y-IQ, 그리고 instruction issue logic이 추가된다.
Dependent slice인지 아닌지 tracking하기 위해 Register Rename stage에서 RDT를 look-up 하여 확인 가능하다. Dependent slice (memory slice)의 첫 번째 instruction은 실제 load instruction의 destination 값을 operand로 사용하기 때문에 쉽게 확인 가능하다.
- Tracking: 먼저 load instruction이 발견되면 해당 destination register의 dependency bit을 1로 set한다. 만약 해당 register를 reading하는 instruction가 있으면 dependence slice로 확인 가능하기 때문에 이 instruction의 destination register의 dependency bit 또한 1로 set하여 propagation 한다.
- Dispatch: IST look-up을 통해 해당 instruction이 independence slice에 포함되는 load / store / AGI 라면 B-QI로 insertion 한다. 반대로 만약 dependence slice에 포함되는 instruction이라면 Y-IQ로 dispatch 하여 기다린다. 그리고 나머지 instruction들은 A-IQ로 dispatch 된다.
- Selection (Back-end): Instruction scheduler는 각기 다른 FIFO head에서 최대 2 instruction을 선택한다. 또는 한 queue에서 age-based policy로 selection을 수행하는데, 이는 younger instruction이 stalled older instruction을 bypass 할 수 있도록 하는데, 대신 in-order commit을 위해서 scoreboard (reorder buffer 유사)를 사용한다.
- Memory ordering: store – load 순으로 instruction order가 있을 때, store operation이 수행되고 난 뒤에 load가 수행되어야 한다. 그러나 LSC 구조에선 load가 store를 bypass 할 우려가 있기 떄문에, store buffer에 store address를 저장한다. 따라서 load instruction의 address와 match가 되는 store가 없을 때 issue 한다.
그러나 Freeway 구조에선 store address generation instruction이 Y-IQ에 머물로 있어서 load instruction이 issue 될 때 아직 확인이 안될수 있다. 따라서 모든 store / load instruction의 sequence number를 명시해준다. 그리고 store는 dispatch 될 때 store buffer에 할당되며, store address가 available 할 때 update 된다. 따라서 load가 issue 될 때 이전 store들이 compute 됐는지 확인 할 수 있다.
Evaluation
성능은 LSC 대비 평균 12% 향상을 보이며, 몇몇 application [hmmer, leslie3d, mcf, gemsFDTD] 에서 2배 이상 성능 향상을 보였다 (이런 경우 dependence slice의 portion이 클 것이다). 반면 몇몇 application [calculix, lbm, milc]에선 거의 성능 향상이 없었고 dependence slice가 거의 없었을 것이다.
실제 Ideal sOoO core 대비 7% 정도 성능이 낮았다. 최종적으로 fully OoO core 대비 33%의 성능 차이를 보였다.
Area overhead 경우 LSC 대비 1.5%가 추가되었다. (RDT에 각 entry당 1 bit, Y-IQ 추가, Store Buffer에 entry당 7 bits)
Power overhead는 32nm 기준으로 in-order core 대비 1.24 배 증가했다.
Reference
- Kumar, Rakesh, Mehdi Alipour, and David Black-Schaffer. “Freeway: Maximizing MLP for Slice-Out-of-Order Execution.” 2019 IEEE International Symposium on High Performance Computer Architecture (HPCA). IEEE, 2019.
- Carlson, Trevor E., et al. “The load slice core microarchitecture.” 2015 ACM/IEEE 42nd Annual International Symposium on Computer Architecture (ISCA). IEEE, 2015.