arif-arman/origami-sort

This repository contains the implementation of the components and algorithms of the Origami framework described in the Origami paper. The framework was developed by the IRL @ Texas A&M University, published in the PVLDB Volume 15, and will be presented in the VLDB 2022.

Mergesort is a popular algorithm for sorting real-world workloads as it is immune to data skewness, suitable for parallelization using vectorized intrinsics, and relatively simple to multithread. We introduce Origami, an in-memory mergesort framework that is optimized for scalar, as well as all current SIMD (single-instruction multiple-data) CPU architectures. For each vector-extension set (e.g., SSE, AVX2, AVX-512), we present an in-register sorter for small sequences that is up to 8X faster than prior methods and a branchless merger that achieves up to a 1.5X speed-up over the naive merge. In addition, we introduce a cache-residing quad-merge tree to avoid bottlenecking on memory bandwidth and a parallel partitioning scheme to maximize threadlevel concurrency. We develop an end-to-end sort with these components and produce a highly utilized mergesort pipeline by reducing the synchronization overhead between threads. Single-threaded Origami performs up to 2X faster than the closest competitor and achieves a nearly perfect speed-up in multi-core environments.

A quick preview of Origami sort performance is given in the tables below. For a deeper analysis and discussion, please refer to the paper. Benchmarks run all code compiled with Visual Studio 2019 in Windows Server 2016 on an 8-core Intel Skylake-X (i7-7820X) CPU with a fixed 4.7 GHz clock on all cores, 1 MB L2 cache, and 32 GB of DDR4-3200 quad-channel RAM. When AVX-512 was used, BIOS defaulted to a 400-MHz lower clock (i.e., 4.3 GHz), which is known as the AVX offset implemented by many motherboard manufacturers to keep core temperature under control. We enable the maximum level of optimization and use appropriate flags (e.g., /arch:AVX512) to ensure the compiler uses all available SIMD registers.

The following table shows the performance comparison of Origami with prior works in corresponding SIMD architectures. It compares the sort speed of different chunk sizes in a 1 GB array of 32-bit random keys.

Origami is distribution insensitive i.e. it retains almost constant speed on all inputs. The next table shows this characteristic on 1 GB data for the following distributions:

D1: Uniformly random, generated by Mersenne Twister
D2: All same keys
D3: Sorted
D4: Reverse sorted
D5: Almost sorted, where every 7th key is set to KEY_MAX
D6: Pareto keys, generated as min(ceil(beta(1/(1-u) - 1)), 10000), where beta = 7 and u ~ uniform[0, 1]
D7: Bursts of same keys, where the length of each subsequence is drawn from D6 and key from D1
D8: Random shuffle, generated by randomly permuting D7
D9: Fibonacci, wrapped around when overflows number of items to sort

Origami achieves near perfect speedup in multi-core environments. The next table shows the scalability for 1 GB random data:

Recommended Setup:

• OS: Windows Server 2019 or Server 2016
• Compiler: MSVC++ 14.29 (Visual Studio 2019 16.11)

1. Make sure to check that the project is set for x64 Release.
2. Set C++ standard to C++17 or later under Project > Properties > Configuration Properties > General.
3. Set register type (Scalar, SSE, AVX2 or AVX-512) and sort key type (uint32, int64 or <int64, int64> key-value pair) in config.h.
4. Set appropriate compiler flags (e.g., /arch:AVX2, /arch:AVX512 etc.) under Project > Properties > Configuration Properties > C/C++ > Command Line.
5. Make sure no Windows update from 03/21 or later is installed as they make AVX2 and AVX-512 bmerge upto 20% slower.
6. Update parameters in config.h if necessary (details below). Current tuned parameters are for the Skylake-X mentioned above.

Parameters:

1. _P1_NREG: Number of register available, typically 16 or 32
2. _P1_SWITCH: Switch point from mcmerge to mrmerge, get this from bench_sort_phases:phase1_matrix_merge_test()
3. _P1_N: Switch point from in register sort to bmerge, get this from bench_sort_phases:phase2_switch_point_test()
4. _P2_MERGE_UNROLL: In-cache bmerge unroll, get this from bench_bmerge:bmerge_test()
5. _P2_MERGE_NREG_1x: Number of registers per stream in bmerge no unroll
6. _P2_MERGE_NREG_2x: Number of registers per stream in bmerge 2X unroll
7. _P2_MERGE_NREG_3x: Number of registers per stream in bmerge 3X unroll
8. _P3_MERGE_UNROLL: Out-of-cache bmerge unroll, get this from bench_bmerge:bmerge_test()
9. _P3_MERGE_NREG_1x: Number of registers per stream in bmerge no unroll
10. _P3_MERGE_NREG_2x: Number of registers per stream in bmerge 2X unroll
11. _P3_MERGE_NREG_3x: Number of registers per stream in bmerge 3X unroll
12. _MTREE_NREG: Number of registers per stream while merging withing mtree, get this from bench_mtree:mtree_single_thread_test()
13. _MT_L1_BUFF_N: Buffer size at the internal node of each 4-way node in mtree
14. _MT_L2_BUFF_N: Buffer size at the root of each 4-way node in mtree
15. _MIN_K: Minimum way of merge to avoid memory bandwidth bottleneck, get this from bench_mtree:mtree_multi_thread_test()

Run:

Once all parameters are set, Origami sort API can be used as shown in bench_sort:sort_bench().

This project is licensed under the GPLv3.0 License - see the LICENSE file for details.

Arif Arman, Dmitri Loguinov