• search hit 20 of 191
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
Metadaten
Document Type:Conference Object
Language:English
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
ISBN:978-1-61208-290-5
ISSN:2308-4499
URL:http://www.thinkmind.org/index.php?view=article&articleid=advcomp_2013_3_40_20059
Publisher:ThinkMind
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):000 Informatik, Informationswissenschaft, allgemeine Werke / 000 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik
Entry in this database:2015/04/02