Work-Stealing Prefix Scan: Addressing Load Imbalance in Large-Scale Image Registration
IEEE Transactions on Parallel and Distributed Systems, vol. 33, pp. 523–535
Abstract
Parallelism patterns (e.g., map or reduce) have proven to be effective tools for parallelizing high-performance applications. In this article, 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.
Authors 5
-
Affiliation as printed
Department of Computer Science, ETH Zurich, Zürich, Switzerland
Department of Computer Science, ETH Zürich, Zurich, Switzerland
-
Affiliation as printed
School of Informatics, University of Edinburgh, Edinburgh, U.K
[School of Informatics, University of Edinburgh, Edinburgh, U.K.]
-
Affiliation as printed
Department of Computer Science, ETH Zurich, Zürich, Switzerland
Department of Computer Science, ETH Zürich, Zurich, Switzerland
-
Affiliation as printed
Department of Computing Science, Umeå University, Umeå, Sweden
Department of Computing Science, Umeå University, Umeå, Sweden#TAB#
-
Affiliation as printed
AICES Graduate School, Institute for Geometry and Practical Mathematics, RWTH Aachen University, Aachen, Germany
Cited by 0 stored of 0
No patents citing this paper on Lens.org (checked 2026-10-06).