Micro Partitioning: Friendly to the Hardware and the Developer

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.