Home // ADVCOMP 2013, The Seventh International Conference on Advanced Engineering Computing and Applications in Sciences // View article

Trading Redundant Work Against Atomic Operations On Large Shared Memory Parallel Systems

Authors:
Rudolf Berrendorf

Keywords: atomic instructions, redundant work, parallel BFS

Abstract:
Updating a shared data structure in a parallel program is usually done with some sort of high-level synchronization operation to ensure correctness and consistency. However, underlying synchronization instructions in a processor architecture are costly and rather limited in their scalability on larger multi-core/multi-processors systems. In this paper, we examine work queue operations where such costly atomic update operations are replaced with non-atomic modifiers (simple read+write). In this approach, we trade the exact amount of work with atomic operations against doing more and redundant work but without atomic operations and without violating the correctness of the algorithm. We show results for the application of this idea to the concrete scenario of parallel Breadth First Search (BFS) algorithms for undirected graphs on two large NUMA shared memory system with up to 64 cores.

Pages: 61 to 66

Copyright: Copyright (c) IARIA, 2013

Publication date: September 29, 2013

Published in: conference

ISSN: 2308-4499

ISBN: 978-1-61208-290-5

Location: Porto, Portugal

Dates: from September 29, 2013 to October 3, 2013