VSkyline: Vectorization for Efficient Skyline Computation

摘要

A dominance test, which decides the dominance re-lationship between tuples, is a core operation in skyline computation. Optimizing dominance tests can thus im-prove the performance of all existing skyline algorithms. Towards this goal, this paper proposes a vectorization of dominance tests in SIMD architectures. Specifi-cally, our vectorization can perform the dominance test of multiple consecutive dimensions in parallel, thereby achieving a speedup of SIMD parallelism degree in theory. However, achieving such performance gain is non-trivial due to complex control dependencies within the dominance test. To address this problem, we de-vise an efficient vectorization, called VSkyline, which performs the dominance test with SIMD instructions by determining incomparability in a block of four dimen-sional values. Experimental results using a performance monitor show that VSkyline considerably reduces the numbers of both executed instructions and branch mis-predictions.