별도의 명시가 없는 한, 본 글의 모든 그림은 위 논문에서 가져왔습니다.
목차
1. Instruction
1.0. Overview
- OLAP 과 같은 시스템에서는 보통 columnar data format 을 많이 이용한다. 그 이유는:
- Row data 를 load 하면 불필요한 column 까지 load 되기 때문
- Columnar data 는 compression 이 용이해 보통 데이터의 크기가 더 작기 때문
1.0.1. Vectorized execution
- Chunk (Vector) 단위로 query execution 을 처리하는 것을 의미한다.
- 여기서 Chunk (Vector) 는 하나의 데이터 (single row) 가 아닌 여러개의 데이터 (multiple rows) 를 의미한다.
- 보통 1024 개를 묶어 하나의 vector 라고 한다.
- 가령 loop 을 돌며 어떤 작업 (func) 을 하는 다음의 코드는,
int arr[MAX];
void func(int i) {
// do something...
}
for (int i = 0; i < MAX; i++){
func(arr[i]);
}- 이것 대신
int arr[MAX];
void func(int* vec, int begin) {
for (int i = begin; i < begin + 1024; i++) {
// do something...
}
}
for (int i = 0; i < MAX; i += 1024) {
func(arr, i);
}- 이렇게 하는 방식이다.
- 위 두 방식은 동일하지만, vectorized execution 하는 것이 더 좋다. 왜냐면:
1.0.2. Vectorized decoding
- 위와 같은 vectorized execution 은 decompression 에도 적용하여 이점을 볼 수 있다. (즉, Vectorized decoding)
- 또한 uncompressed 상태의 vector 크기를 L1 혹은 L2 캐시에 맞춘다면 decompression 이후 memory 에 저장하지 않고 캐시에서 바로 가져다가 query execution 을 할 수 있으므로 memory 에는 compressed vector 만 저장되게 되어 memory 사용량 또한 줄일 수 있다.
1.0.3. Parquet
- Parquet 에서는 무조건 DICT 를 적용하고, 이렇게 해서 생성된 code sequence 에 대해서는 RLE 나 BP 를 적용한다.
- 하지만 이때 RLE 나 BP 는 데이터의 사이즈가 가변적 2 이고,
1.0.4. Compressed execution
- Compressed Query Execution 은 데이터가 compressed 된 상태에서 그것을 decompression 하지 않고 (혹은 processing 가능한 최소의 크기로만 부분적으로 decompression 하여) query processing 을 하는 것을 일컫는다.
- “부분적” 이라는 것은 가령 8bit 로 compressed 된 데이터가 원래는 64bit 로 decompression 되어야 하지만 16bit 로만 decompression 해도 processing 이 가능하다면 그렇게 하는 것이라 생각하면 된다.
- DuckDB 와 같은 근래의 DBMS 들은 이러한 compressed vector (random access 가 가능한 compressed data) 를 지원한다.
- 이렇게 함으로써 SIMD 와 같은 optimization 도 사용할 수 있게 되었고, (SIMD 에서는 작은 사이즈 데이터 여러개를 레지스터에 넣으니깐은) 캐시나 메모리 사용량도 더 줄일 수 있게 되었다.
- 또한 compressed vector 를 “부분적으로” decompress 하여 가능한 최소 사이즈의 lane-width (processing size 라고 이해하자) 가 되게 하는 best-case scan decoding 을 best-case 를 넘어 common-case 가 되게 했다고 한다.
1.0.5. FastLanes
- FastLanes 는 (저자의 소속인) CWI 에서 시작한 next-generation bigdata format 이다.
- 이것은 parallel processing 의 기회를 최대한 늘린 columnar compression layout 으로,
- 다양한 Instruction Set Architecture (ISA) 에 대응할 수 있고,
- 즉, 특정 architecture 에 의존적이지 않고 공통적으로 지원하는 instruction 에만 의존하고
- Scalar-only code 를 사용하여 vectorized execution 을 사용하지 않고도 효과적 3 이다.
- 다양한 Instruction Set Architecture (ISA) 에 대응할 수 있고,
1.1. Challenges and Contributions
- FastLanes 의 핵심은 데이터의 의존성을 최대한 줄여 parallel processing 을 최대로 활용할 수 있게 한다는 것에 있다. 이때 당면한 문제들 (Challeges) 와 그에 대한 해결 방법 (Contribution) 들을 알아보자.
- 요약하자면:
| CHALLENGE | CONTRIBUTION |
|---|---|
| SIMD register 크기가 다양함 | 1024bit 크기의 가상 register FLMM1024 를 가정 |
| 다양한 SIMD ISA 가 있음 | 모든 SIMD ISA 가 공통적으로 제공하는 instruction 들로 FLMM1024 에 대한 instruction 을 정의 |
| (DELTA) 데이터 간의 의존성이 있음 | Transposing: column 내 데이터들의 순서를 바꿔 이런 의존성을 무력화함 |
| 기존의 scheme 들은 특정 lane-width 에만 효과적임 | Unified Transposed Layout: 모든 lane-width 에 적용할 수 있는 scheme |
| Code portability: 특정 ISA 에서만 사용할 수 있는 코드여서는 안됨 | Scalar code 를 작성, vectorization 은 intrinsic 을 사용하는 것이 아닌 compiler 에게 맡기는 방식 |
| LOAD, STORE bound | Memory 에는 compressed data 만 유지, cache 에 들어갈 정도의 크기까지만 decompress 하여 cache 된 데이터가 바로 execition 될 수 있도록 함 (reduce LOAD-bound) + BP fusing 으로 STORE-bound 해결 |
1.1.1. Many SIMD widths
- 지난 25년동안 SIMD 레지스터 크기는 8배나 증가했다. 이에 따라 현 시점에서 가장 큰 사이즈의 SIMD 레지스터 크기에 맞추는 것이 아닌, 추후에 더 증가할 것이라는 예측에 따라 1024bit 의 가상 SIMD 레지스터
FLMM1024를 사용하여 FastLanes 를 설계했다고 한다.- 이건 기존의 어떤 ISA 보다도 성능이 좋고, scalar code 보다도 좋다고 한다. 4
- Bit 레벨에서는, BP 를 interleaving 해서 128 개의 8bit lane (즉, 총 1024bit) 에 맞춘다고 한다.
- 가령 3bit value 들을 8bit lane 에 round robin 으로 할당하는거지
- Implementation 레벨에서는, 1024-value vector 를 한꺼번에 처리 5 하여 vector 하나 처리하는 데에 어떤 경우에는 17 cycle 만에도 가능했다고 한다.
1.1.2. Heterogeneous ISAs
- SIMD instruction 들은 ISA 마다도 다르지만, ISA 내에서도 generation 에 따라서도 다르다.
- 가령 x86 에서 SSE 와 AVX 가 다른것처럼
- 따라서 이런 다양성을 무마하기 위해,
FLMM1024레지스터에 대한 간단한 instruction 또한 정의했다고 한다.- 당연히 이 instruction 들은 다양한 ISA 들이 제공하는 instruction 들의 intersection 일것이다.
- 본 논문에서는 자세하게 언급하지는 않았지만,
FLMM1024instruction 들은 GPU 나 TPU 와 같은 다른 accelerator 들과의 호환 가능성도 제시한다.
1.1.3. Decoding dependencies
- RLE 는 control dependency 가 있다.
- 이 control dependency 에 대해서는 딱히 어떤 해결책을 내놓지는 않는 것 같다.
- 그리고 DELTA 에게는 data dependency 가 있다.
- FastLanes 에서는 column data 의 순서를 바꿔 data dependency 를 해결하는 Transposing 기법을 제시한다.
- 그리고 DELTA 와 DICT 의 조합에 RLE 을 다시 매핑해서 훨씬 효율적인 DELTA encoding 을 한다고 한다 6.
1.1.4. Layouts that depend on lane-width
- 기존의 연구들은 하나의 data stream (예를 들어 column 하나) 에 대한 encoding 만을 고려했고, 따라서 특정 lane width 에서만 최적의 성능을 보여줬다.
- 하지만 여러 column 들은 각기 다른 data distribution 을 가질 수 있기에, lane width 또한 다양해질 수 있다.
- BP 의 bit width 가 다양할 수 있기 때문에
- 따라서 가능한 모든 lane width 에 대응할 수 있는 방법이 필요하다.
- 또한 저자가 말하는 Transposing 을 사용할 때는 각 column 들의 순서가 달라질 수 있다.
- 단순하게 생각하면 column A 는 오름차순, column B 는 내림차순인 등
- 근데 이렇게되면 안되자나?
- 그래서 위의 두 문제 7 (모든 가능한 lane width 에 대응 + column 들의 reordering 순서 통일) 를 해결하기 위한 것이 Unified Transposed Layout 이다.
- 여기서는 1024개의 값을 16개씩 8묶음으로 만들어서 0-4-2-6-1-5-3-7 순서로 나열한다.
- 이렇게 하는 것이 왜 문제를 해결하는지는 뒤에서 배운다.
1.1.5. Keeping code portable
- 저자가 소개하는
FLMM1024instruction set 은 단순하게 설계되어있기 때문에uint64레지스터와 연산으로 저것들을 구현 (시뮬레이션?) 할 수 있다고 한다. - 이러한 portability (특정 ISA 에 구애받지 않음) 는 SIMD 를 지원하지 않고 32bit 연산을 지원하는 매우 저사양의 CPU 에서도 FastLanes 를 사용했을 떄 성능 향상을 이뤄낼 수 있다고 한다.
- 일반적인 64bit ISA 에서는, SIMD 를 사용하지 않는 scalar code 의 경우에도 lane width 가 작을 때 SIMD 와 유사한 acceleration 이 일어났다고 한다.
- 즉, independency 를 늘려 SIMD 에 친화적으로 설계하는 것이 SIMD 를 사용하는 것 뿐만 아니라 사용하지 않았을 때에도 성능향상이 있었다고 한다.
- 또한 근래의 compiler 들은 optimizing 과정에서 SIMD 와 같은 vectorized execution 을 활용하게 되고, 따라서 FastLanes 는 별도의 SIMD intrinsic 을 사용하지 않아도 컴파일 과정에서 arch 가 지원하는 SIMD instruction 으로 컴파일된다 - 즉, high-level code 에는 특정 ISA 가 특정되어 있지 않기 때문에 그만큼 유연성을 가지는 것
1.1.6. Avoid getting LOAD, STORE bound
- FastLanes 에서 compressed data 는 memory 에 들어오고, 그것을 decompression 한 것은 CPU 의 L1 캐시에도 들어갈 정도로 작기 때문에 바로 query execution 을 위한 pipeline 으로 진입할 수 있도록 설계되어 있다.
- 따라서 CPU-memory 간 traffic 을 compression ratio 만큼이나 줄일 수 있게 된다.
- 이에 따라 대부분의 CPU time 은 query execution 에 사용되기 때문에, CPU-memory 대역폭도 덜 사용할 수 있게 된다.
- 여기에 sequential scan 의 경우 prefetching 까지 결부되어 더욱 좋은 성능을 보여준다.
- 정리하자면, 이 모든것들은 결국
LOADinstruction 을 적게 사용하게 되어 부담을 줄이게 된다 (reduce LOAD-bound) - 하지만 decoding 이 너무 빨라 연산의 결과를 다시 저장하는 (
STORE) 것에 부담 (STORE-bound) 이 생기게 된다. - 이를 위해 FOR, DELTA, RLE, DICT 에다가 BP 를 fusing 하여 STORE+LOAD bound 를 줄였다고 한다 8.
1.2. Outline
- Section 2 에서는 FastLanes 의 구체적인 logic 을 살펴본다. 다음의 세 파트로 이루어져 있다.
- Section 3 에서는 decompression performance evaluation 을 하며
- Section 4 에서는 기존의 방법들과 FastLane 의 차이점에 대해 알아보고
- Section 5 에서 마무리 짓는 형식이다.
Footnotes
-
주인장의 추측이다. ↩
-
여기서 variable sized 라는 것이 뭔지 잘 모르겠음; BP 는 bit width 가 가변적이라고 받아들일 수 있는데 RLE 는 뭐가 가변적이라는거고 ↩
-
Vectorized execution 을 사용하지 않아도 좋다는 것이 맞는 해석인지 모르겠음. ↩
-
더 안좋은 것에 base 를 맞춰야 하는 것 아닌가? virtual 이 actual 보다 더 좋다면 actual performance 는 virtual 일때보다 evaluation 결과가 더 안좋을텐데 그럼 논리가 이상한데 ↩
-
아니 ㅅㅂ 뭐라는거야 128개의 8bit lane 이면 한번에 128 개씩 처리하는거 아닌가 ↩
-
뭔소리임? ↩
-
원문에서는 이것이 별도의 문제가 아니고 하나의 흐름으로 연결되어 하나의 문제처럼 나온다. 근데 아직 감은 안온다. ↩
-
아직 이게 뭔지는 모른다. ↩