BOUNCE: Memory-Efficient SIMD Approach for Lightweight Integer Compression.
Publikation: Beitrag in Buch/Konferenzbericht/Sammelband/Gutachten › Beitrag in Konferenzband › Beigetragen › Begutachtung
Beitragende
Abstract
Integer compression plays an important role in
columnar database systems to reduce the main memory footprint
as well as to speedup query processing. To keep the additional
computational effort of (de)compression as low as possible, the
powerful Single Instruction Multiple Data (SIMD) extensions of
modern CPUs are heavily applied. While a scalar compression
algorithm usually compresses a block of N consecutive integers,
the state-of-the-art SIMD implementation scales the block size to
k∗N with k as the number of elements which could be simultane-
ously processed in an SIMD register. On the one hand, this scaling
SIMD approach improves the performance of (de)compression
but can lead to a degradation of the compression ratio compared
to the scalar variant on the other hand. Within this paper, we
analyze this degradation effect for an heavily applied and well-
performing integer compression algorithm called BitPacking (BP)
and present a novel SIMD concept to overcome that effect. Our
novel SIMD idea called BOUNCE is to concurrently compress k
different blocks of size N within SIMD registers achieving the
same compression rate as the scalar variant. As we are going to
show, our proposed SIMD idea works well for BP and may offer
a new generalized approach to optimize further algorithms.
columnar database systems to reduce the main memory footprint
as well as to speedup query processing. To keep the additional
computational effort of (de)compression as low as possible, the
powerful Single Instruction Multiple Data (SIMD) extensions of
modern CPUs are heavily applied. While a scalar compression
algorithm usually compresses a block of N consecutive integers,
the state-of-the-art SIMD implementation scales the block size to
k∗N with k as the number of elements which could be simultane-
ously processed in an SIMD register. On the one hand, this scaling
SIMD approach improves the performance of (de)compression
but can lead to a degradation of the compression ratio compared
to the scalar variant on the other hand. Within this paper, we
analyze this degradation effect for an heavily applied and well-
performing integer compression algorithm called BitPacking (BP)
and present a novel SIMD concept to overcome that effect. Our
novel SIMD idea called BOUNCE is to concurrently compress k
different blocks of size N within SIMD registers achieving the
same compression rate as the scalar variant. As we are going to
show, our proposed SIMD idea works well for BP and may offer
a new generalized approach to optimize further algorithms.
Details
Originalsprache | Englisch |
---|---|
Titel | Proceedings of the 38th International Conference on Data Engineering Workshops (ICDEW) |
Seiten | 123-128 |
Seitenumfang | 6 |
ISBN (elektronisch) | 9781665481045 |
Publikationsstatus | Veröffentlicht - 2022 |
Peer-Review-Status | Ja |
Externe IDs
Scopus | 85134880989 |
---|---|
Mendeley | a7c40734-473a-3159-8a1a-d16123b7a2dc |
ORCID | /0000-0001-8107-2775/work/142253555 |
Schlagworte
Forschungsprofillinien der TU Dresden
DFG-Fachsystematik nach Fachkollegium
Fächergruppen, Lehr- und Forschungsbereiche, Fachgebiete nach Destatis
Schlagwörter
- SIMD, integer compression, memory-efficiency