TPDSWork-stealing prefix scan: Addressing load imbalance in large-scale image registration
Parallelism patterns (e.g., map or reduce) have proven to be effective tools for parallelizing high-performance applications. In this paper, we study the recursive registration of a series of electron microscopy images - a time consuming and imbalanced computation necessary for nano-scale microscopy analysis. We show that by translating the image registration into a specific instance of the prefix scan, we can convert this seemingly sequential problem into a parallel computation that scales to over thousand of cores. We analyze a variety of scan algorithms that behave similarly for common low-compute operators and propose a novel work-stealing procedure for a hierarchical prefix scan. Our evaluation shows that by identifying a suitable and well-optimized prefix scan algorithm, we reduce time-to-solution on a series of 4,096 images spanning ten seconds of microscopy acquisition from over 10 hours to less than 3 minutes (using 1024 Intel Haswell cores), enabling derivation of material properties at nanoscale for long microscopy image series.
Cite
@article{copik2021workstealing,
author = {Copik, Marcin and Grosser, Tobias and Hoefler, Torsten and Bientinesi, Paolo and Berkels, Benjamin},
title = {Work-stealing prefix scan: Addressing load imbalance in large-scale image registration},
journal = {IEEE Transactions on Parallel and Distributed Systems},
series = {TPDS},
volume = {},
number = {},
pages = {1-1},
year = {2021},
month = {7},
doi = {10.1109/TPDS.2021.3095230},
url = {https://ieeexplore.ieee.org/document/9477174}
}