(논문) The FastLanes Compression Layout - Decoding 100 Billion Integers per Second with Scalar Code, VLDB 2023 (3. Evaluation)

본 글은 논문 The FastLanes Compression Layout: Decoding > 100 Billion Integers per Second with Scalar Code (VLDB '23) 를 읽고 정리한 글입니다.

별도의 명시가 없는 한, 본 글의 모든 그림은 위 논문에서 가져왔습니다.

목차

• 1. Introduction
• 2. FastLanes
• 3. Evaluation (현재 글)
• 4. Related Work
• 5. Conclusion and Future Work

3. Evaluation §

3.0. Overview §

• FastLanes 는 C++ 라이브러리로 제작되어, MIT license 로 오픈소스화 되었다. (링크)
• Evaluation 을 통해 저자가 답하려고 하는 질문들은 다음과 같다:
  1. Interleaving BP 에서의 unpacking 의 실제 속도는 어느정도일까?
  2. Decoding performance 가 SIMD reg bit-width 에 따라 실제로 얼마나 달라질까? 그리고 같은 reg bit-width 에 대해, 다양한 SIMD ISA 간의 성능은 얼마나 차이날까?
  3. Interleaving BP 와 UTL 의 디자인이 SIMD 를 사용하지 않는 scalar code 에서도 성능 향상을 가져다 줄까?
  4. 순수한 scalar code 의 performance 는 어느정도일까? 그리고 compiler 에 의한 auto-vectorization 은 explicit SIMD intrinsic version 과 비교할 때 어느 정도의 성능일까?
  5. UTL 의 decoding performance 은 어느정도일까?
  6. FastLanes 를 도입했을 때의 query execution 은 얼마나 향상될까? 즉, 모든 것이 종합된 E2E 성능 향상은 어느정도일까?
• 또한 unpacking 와 decoding kernel 을 fusing ¹ 했을 때의 성능 향상은 어느정도일지도 실험했다고 한다.
• 선행연구과의 비교도 당연히 수행했는데, 이건 section 4 에서 설명한다고 한다.

3.1. Micro-benchmarks §

3.1.0. Basic setup §

• 제안한 Interleaving BP 및 여러 decoding 방법은 모든 lane bit-width 경우의 수 ($T\in \{8,16,32,64\}$) 에 대해 구현이 되었고,
• 또한 이들을 다음의 4가지 버전에 대해서도 모두 구현했다고 한다. 진짜 미친 노가다네
  1. Scalar: 순수한 scalar code 이다. 어떠한 vectorization 도 들어가지 않은
     • 즉, compiler 에서 vectorization 관련 option 이 꺼져있는 상태다.
  2. Scalar_T64: 이건 vectorization 은 하지 않았지만, uint64 자료형을 $S=64/T$ 의 SIMD 로 가정하는 구현체이다.
     • 즉, 그렇게 “가정” 하는 것이고 machine code 관점에서 보아도 vectorization 은 적용되어있지 않은 것.
     • “가상의” software-implemented SIMD 라고 이해하면 될듯; 논문상에서도 quasi-SIMD, 즉 유사-SIMD 라고 표현한다.
  3. SIMD: 이건 명시적으로 ISA-specific SIMD intrinsic 을 사용한 버전이다.
  4. Auto-vectorized: 이건 암묵적인 SIMD 라고 생각하면 된다. 즉, compiler 에 의해 SIMD ISA 로 변환되는 버전이다.
     • 이건 Scalar 에서 vectorization compiler option 만 켜서 컴파일 한 것이다.
• 정리하면 다음과 같다고 할 수 있다.

NAME	VECTORIZATION AWARE	SIMD INSTRUCTION	SIMD INTRINSIC
Scalar	X	X	X
Scalar_T64	O	X	X
SIMD	O	O	O
Auto-vectorized	O	O	X

• Compiler 는 LLVM (clang++) 를 사용했고, Scalar (및 Scalar_T64) 에서는 다음의 옵션으로 vectorization 을 비활성화했다고 한다:

-O3 -mno-sse -fno-slp-vectorize -fno-vectorize

• 비교한 CPU 정보는 다음과 같다:

• 여기서 ARM64 에 대해 NEON 만을 사용한 것은 AWS Graviton 에서 실험했을 때 SVE 가 NEON 보다 더 느렸기 때문이라고 한다.
• 이 Micro-benchmark 에서는 순수한 CPU cost 를 확인하고자 했었고 ², 하나의 vector 를 3000만번 (30M) decoding 하였다고 한다.
  • 그래서 데이터들이 L1 cache 에서만 놀 수 있게 하였다고 한다 ³.
• Value 하나 당 소모하는 CPU cycle (즉, 낮을수록 좋다) 을 측정했다고 한다.
  • 다만, $T=8$ 에서의 unpacking 과정만 반대로 CPU cycle 당 value 를 측정했는데,
  • 이건 해당 지표가 CPU platform 간의 차이를 더 명확하게 보여주기 때문이라고 한다.
  • 즉, 소모 시간 (= CPU cycle) 로 platform 간 비교를 하기에는 각 CPU 들의 타겟층 (PC vs server) 와 CPU freq. 등이 차이가 있기 때문이다.
• 마지막으로, 모든 CPU 는 “Turbo scaling feature” 를 비활성화해 CPU freq. 를 일정하게 유지되게 했다고 한다 ⁴.

3.1.1. Bit-unpacking §

• 위 그래프는 interleaved-bp unpacking 를 사용했을 때와 안했을 때를 비교한 것이다.
  • 보면 이것을 사용하는 것 (초록색) 이 사용하지 않는 것 (빨간색) 보다 대체로 유사하거나 빠른 것을 볼 수 있다.
  • 하지만, 사용하는 것에는 parallel 의 기회가 더 많다는 장점이 있다; 보면 Scalar_T64 (파란색) 은 SIMD ISA 를 사용하지는 않지만, 8bit value 8 개를 64bit 자료형 (uint64) 으로 처리하는 데에서 오는 parallelism 덕분에 비교군 중에 제일 빠른 것을 볼 수 있다.
    • 그리고 보라색 글자를 보면, Scalar_T64 와 다른애들과의 차이가 약 $64/T$ 정도 나는 것을 알 수 있다.
    • 이건 Q3 에 대한 답변이 된다; Interleaving BP 를 사용하는 것이 단순 scalar code (Scalar_T64) 에서도 성능 향상을 가져왔기 때문.

• 다음은 interleaved-bp unpacking 의 performance 에 대해 여러 CPU architecture, lane bit-width ($T$), value bit-width ($W$), 에 걸쳐 실험을 한 것이다.
  • 일단 이 그래프 자체가 Q1 에 대한 답변이 된다: 단위가 normalized 되지 않은 순수 cycle per value 이기 때문.
    • 수치적으로 보면, Ice Lake 에서 $T=8$ 일 때 최대값이 거의 70에 달한다는 것을 알 수 있다.
    • 즉, interleaved-bp unpacking 을 사용하면 1cycle 당 최대 70개의 값을 decoding 할 수 있는 것.
  • 그리고 보면 SIMD 를 사용하는 것 (빨간색, 초록색) 이 그렇지 않은 것 (파란색, 노란색) 보다 항상 빠르다는 것을 확인할 수 있다.
  • 또한 Q2 에서의 CPU architecture 간의 비교를 해보면:
    • 일단 AWS Graviton 은 (특히 $T=64$ 에서) 대체로 구린 성능을 보였다.
    • 하지만 동일한 ARM64 기반인 Apple M1 의 경우에는 AWS Graviton 보다는 더 좋은 성능을 보여줬다.
      • 이건 Apple M1 의 경우에 더 나은 ILP 가 되어 있기 때문으로 보인다고 한다.
  • Q2 에서 추가적으로 제시한 SIMD reg 사이즈와 성능간의 연관성에 대해서는:
    • 별로 그런 것처럼 보이지는 않았다.
    • 왜냐면 AMD Zen4 에서는 AVX512 를 사용하며 AMD Zen3 의 AVX2 (256bit) 보다 더 register 의 사이즈가 커졌지만 눈에 띄는 성능 향상은 없었기 때문이다.
    • 다만 이것은 충분히 예상되던 일이었다: AVX512 는 512bit-register 가 아니라 256bit-regitster 2개를 사용하는 것으로 구현되어있기 때문.
  • Q4 에서의 Auto-vectorization 과 SIMD 의 유사도는 아주 높은 것으로 보인다.
    • 보면 거의 모든 실험 결과에서 이 둘이 거의 일치하는 것을 볼 수 있다.
    • 이 상황을 보면 굳이 SIMD intrinsic 을 사용할 필요가 없다는 것을 알 수 있다; 성능이 유사하기에 그냥 compiler 에게 맡기는 것이 code portability 측면에서 더 좋기 때문.
  • 마지막으로 $T=64$ 에서 Scalar 와 Scalar_T64 가 거의 동일하게 나오는 것에 주목하자.
    • 당연히 $T=64$ 에서는 uint64 자료형이 어떤 parallelism 도 제공하지 않기 때문에, 성능이 동일하게 나오는 것이 정상이다.
• 이를 통해 FastLanes 가 제공하는 reduced dependency 와 parallelism opportunity 덕분에 CPU 의 역량을 최대로 활용할 수 있음을 알 수 있다 ⁵.

3.1.2. Unified Transposed Layout §

• Q5 와 관련하여 실험한 결과는 다음과 같다:

• 일단 여기서도 Scalar_T64 가 그냥 Scalar 보다 훨씬 좋은 것을 알 수 있다.
• Scalar 버전을 보자면,
  • 일단 Apple M1 와 Intel Ice Lake 가 가장 뛰어났고
  • AWS Graviton 과 AMD Zen3 은 $W$ 가 작을때 더 성능이 안좋아지는 기현상이 일어났다.
• 그리고 SIMD 를 사용한 버전 (SIMD 와 Auto-vectorized) 을 보면,
  • AWS Graviton 이 매우 구린 것을 다시 한번 확인할 수 있다.
  • Best performance 의 관점에서 보면 $W=8$ 일때 대부분의 platform 에서 성능이 최대로 나타났고 이때의 성능은 cycle 당 40개 이상의 tuple 을 처리할 수 있었다고 한다.
• FastLanes 에서 사용하는 instruction 들은 dependency 가 없기 때문에 column 의 데이터가 어떤것이든지 성능에서는 크게 영향이 없었다고 한다. 오직 $W$ 만이 유의미했고, 따라서 모든 $W$ 에 대해 실험한 것 ⁶.

3.1.3. Fusing Bit-packing and Decoding §

• Fusing 은 연이은 두 작업을 하나의 작업으로 합치는 것이라고 생각하면 된다.
• 따라서 여기서 Fusing BP and Decoding 이라는 것은 BP-unpacking 이후 바로 decoding 을 하는 것을 의미한다.
  • 즉, BP-unpacking 이후 register 에 남아있는 데이터를 그대로 decoding 에 넣는 것이다.
  • 이렇게 하면 BP-unpacking 의 마지막 instruction 인 STORE 와 decoding 의 첫 instruction 인 LOAD 가 절약되는 것.

• 위 결과는 이러한 Fusing 을 사용했을 때의 실험으로 확실히 성능이 좋아지는 것을 볼 수 있다.
  • 낮을수록 좋은거고, 따라서 Fusing (빨간색) 의 경우 non-Fusing (초록색) 보다 더 우수하다.
• BP-unpack 하여 DICT 혹은 FOR 로 compressed 된 vector 로 바꾸는 경우에는 fusing 이 필요 없다고 한다. ⁷
• FOR 이후 DELTA 를 적용시킨 경우 (즉, decompress 시에는 DELTA 처리 후 FOR 처리) 에는 fusing 을 사용할 수 있다. ⁸

3.2. End-to-End Query Performance §

• Q6 와 관련해서, 여기 에 제시된 query processor 에 FastLanes 를 통합해 실질적인 query processing performance 를 측정했다고 한다.
  • 참고로 platform 은 Ice Lake 이며, 모든 데이터는 memory 에 올라와 있다고 한다.
• 일단 schema 는:
  • Table 한개: TAB
  • Column 한개: COL
  • Data type: uint32
  • Data count: $10\times 2^{28}$ (총 10GiB)
• 이때의 결과는 다음과 같다:

• 일단 가로축은 Bit-width ($W$) 이다.
  • 따라서 특정 $W$ 에 대해, 모든 데이터들은 $[0,2^W-1]$ 범위 안에 있고, $W$ 사이즈로 BP 되었다는 것을 의미한다.
  • 이 데이터들은 해당 범위 안에서 일정한 확률 (uniform) 로 랜덤하게 생성된 것들이다.
• 그리고 세로축은 query execution duration 이다.
  • Query 는 간단하게 SELECT SUM(COL) FROM TAB; 즉 그냥 모든 데이터를 다 더하는 것이다.
• 각 선들에 대해서는,
  • 선의 종류는 compression method 이다.
    • 즉, 실선은 FastLanes 가 적용된 것, 긴 점선은 Scalar 버전, 그냥 점선은 compression 하지 않은 것이다.
    • 그래서 보면 compression 하지 않은 것 (그냥 점선) 의 경우에는 모든 $W$ 에 대해 동일한 결과가 나오는 것을 알 수 있다.
  • 선의 색깔은 thread 의 개수이다.
    • 즉, 빨간색은 thread 1개를 사용한 것 (1T), 초록색은 thread 2개를 사용한 것 (2T), 등등인 것.
• 그럼 결과를 보자.
  • 우선 같은 색깔의 선들을 비교해 보면 compression method 들 간의 차이를 확인할 수 있다.
    • 보면 대략 $W=26$ 전까지는 FastLanes 를 사용한 것이 (vectorized execution 덕분에) 제일 빠르다.
    • 제일 극적인 변화는 그림에 보라색 글자로 적혀있는 $4\times$, $7\times$ 이다. 8T (노란색 선) 기준,
      • $W=2$ 언저리에서 FastLanes (실선) 은 uncompressed (점선) 에 비해 $7\times$ 정도의 향상이 있었고,
      • $W=1$ 언저리에서 FastLanes (실선) 은 Scalar (긴 점선) 에 비해 $4\times$ 정도의 향상이 있었다는 것을 의미한다.
  • 그리고 세로로 그어져 있는 저 보라색 긴점선은 uncompressed 보다 느려지는 시점을 의미한다.
    • Compression 의 경우에는 memory-CPU BW 를 적게 먹는다는 장점이 있지만 decompression overhead 가 있다는 단점이 있다.
    • 따라서 저 보라색 긴점선이 이러한 trade-off 를 나타내고 있는 것.
    • 왼쪽의 그것은 모든 thread 개수에 대해, Scalar (긴점선 그래프) 가 uncompressed (점선 그래프) 보다 느려지는 (교차하는) 지점을 나타낸 것이고,
    • 오른쪽의 그것은 모든 thread 개수에 대해, FastLanes (실선 그래프) 가 uncompressed (점선 그래프) 보다 느려지는 (교차하는) 지점을 나타낸 것이다.
    • 즉, FastLanes 가 Scalar 에 비해 더 많은 $W$ 에 대해 성능 이점을 가져올 수 있다고 해석할 수 있다.

Footnotes §

1. 이것도 뭔소린지는 아직까지는 모르겠다. ↩

2. 뭔소리임 ↩

3. 3000만번 실험을 돌린거랑 L1 cache resident 가 뭔상관인지 모르겠다. ↩

4. 내용을 이해하기에 critical 한 것은 아니지만, 이게 뭔지, 그리고 원문에의 “CPU clock normalization stable” 이 뭔소린지 잘 모르겠다. ↩

5. 이 문장이 잘 이해도 안되고 갑자기 왜 튀어나온지도 모르겠다. 원본 문장: “The absence of dependencies and the opportunities for data-parallelism that FastLanes code exposes, make it profit from total CPU execution capability, which is the product of ILP and register width.” ↩

6. Dependency-free instruction 이 ISA-free 를 말하려는 것 같은데, 이거랑 data type 에 따른 성능이랑 어떤 연관이 있는건지 모르겠다. ↩

7. 이건 또 뭔소리임; 위 문단에서는 fusing 하면 더 좋다고 하고 FOR 와 fusing 한 것을 실험하여 Figure 11 에서 보여주기도 했는데? 원몬 문장: “In case of decoding into compressed vectors, fusing is not needed for DICT and FOR (decoding is just bit-unpacking in that case ś therefore we do not micro-benchmark these schemes separately).” ↩

8. 뭐 할 수 있을 것 같기는 한데 BP-unpack 이랑 fusing 하는 것을 설명하는 본 section 에서 왜 이런얘기를 하는지는 모르겠다. ↩