Volltext-Downloads (blau) und Frontdoor-Views (grau)
The search result changed since you submitted your search request. Documents might be displayed in a different sort order.
  • search hit 20 of 193
Back to Result List

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

  • 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.

Export metadata

Additional Services

Share in Twitter Search Google Scholar Availability


Document Type:Conference Object
Author:Rudolf Berrendorf
Parent Title (English):Omatu (Ed.): ADVCOMP 2013, The Seventh International Conference on Advanced Engineering Computing and Applications in Sciences
First Page:61
Last Page:66
Date of first publication:2013/09/29
Award:Best Paper Award
Tag:atomic instructions; parallel BFS; redundant work
Departments, institutes and facilities:Fachbereich Informatik
Dewey Decimal Classification (DDC):0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik
Entry in this database:2015/04/02