TY - CHAP U1 - Konferenzveröffentlichung A1 - Berrendorf, Rudolf T1 - Trading Redundant Work Against Atomic Operations On Large Shared Memory Parallel Systems T2 - Omatu (Ed.): ADVCOMP 2013, The Seventh International Conference on Advanced Engineering Computing and Applications in Sciences N2 - 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. KW - redundant work KW - parallel BFS KW - atomic instructions UR - https://www.thinkmind.org/index.php?view=article&articleid=advcomp_2013_3_40_20059 SN - 2308-4499 SS - 2308-4499 SN - 978-1-61208-290-5 SB - 978-1-61208-290-5 SP - 61 EP - 66 PB - ThinkMind ER -