Parallelization of priority queue-based algorithms

Question

There's a number of algorithms that operate by maintaining and consuming a priority queue of "events". I'm thinking primarily of geometric algorithms, particularly sweep-line algorithms like Bentley-Ottmann and Fortune's algorithm, but also things like Dijkstra's algorithm and Prim's algorithm.

There's no trivial way to parallelize these algorithms: In non-degenerate cases there's exactly one event which is legal to process. One could speculatively distribute the next n events to n processors, but (a) handling them in any interleaved order would generally violate the algorithm's invariants, and (b) would often add new events to the priority queue which should have been handled earlier.

Nevertheless, for things like sweep-line algorithms, there's a natural locality to exploit. Handling two events which are close to each other along the sweep axis but far away on the perpendicular axis would probably be okay as long as the underlying state structure could be concurrently updated, and one could imagine either speculatively handling those events and rolling back only when interactions were detected, and/or partitioning a prefix of the queue into mutually independent workloads.

Are there any articles which explore this sort of approach, either for specific problems or for paradigms like sweep-line algorithms?

Answer 1

Two old, but, I think, still very useful resources:

• M.T.Goodrich, M.R.Ghouse, and J.Bright. Sweep Methods for Parallel Computational Geometry. Algorithmica (1996), 15:126-153. - closely related to what you are asking about, download for free: link.

• S.G.Akl, K.A.Lyons. Parallel Computational Geometry. Prentice-Hall, 1993 - monograph about first ten years of research in parallel computational geometry. In the Chapter Four they say: "The plane sweep technique appears to be inherently sequential", but nevertheless refer to a number of parallel sweeping algorithms. Please see: link.