Micro Partitioning: Friendly to the Hardware and the Developer
Title
Micro Partitioning: Friendly to the Hardware and the Developer
Authors
Jan Mühlig and Jens Teubner
Published
Proc. of the 19th Int'l Workshop on Data Management on Modern Hardware (DaMoN), Seattle, WA, USA, June 2023
Abstract
Modern hardware’s complexity has made studying hardware-conscious algorithms a relevant topic for many years. Partitioning algorithms, for instance, break data into bits that fit into fast CPU caches. Unfortunately, they are often challenging to design, develop, and maintain. While hardware-oblivious algorithms are easier to build, they may perform poorly when hardware or data deviate from expectations.
In this paper, we introduce micro partitioning, which enhances the partitioning problem in a way that outperforms state-of-the-art solutions while being hardware-agnostic. By storing tuples in a tight address space, micro partitioning creates an access pattern that is friendly to both caches and translation lookaside buffers. We also show how micro partitioning interacts with task-based execution strategies in a symbiotic way, making micro partitioning intuitive to express for developers.
Download
DOI
10.1145/3592980.3595310 (ACM Digital Library)
Publication Log
May 2023
camera-ready version (PDF)
March 2023
Submission to DaMoN 2023 (accept)
- submission (PDF)
- reviews (accept, accept, accept)