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

PDF

DOI

10.1145/3592980.3595310 (ACM Digital Library)

May 2023

camera-ready version (PDF)

March 2023

Submission to DaMoN 2023 (accept)

• submission (PDF)
• reviews (accept, accept, accept)