Actual PDF:
http://www.cs.chalmers.se/~tsigas/papers/Wait-Free-GPGPU-IPDPS08.pdf
http://doi.acm.org/10.1145/1400751.1400849
Wait-free programming for general purpose computations on graphics
processors
ABSTRACT
This paper aims at bridging the gap between the lack of
synchronization mechanisms in recent graphics processor (GPU)
architectures and the need of synchronization mechanisms in parallel
applications. Based on the intrinsic features of recent GPU
architectures, we construct strong synchronization objects like wait-
free and t-resilient read-modify-write objects for a general model of
recent GPU architectures without strong hardware synchronization
primitives like test-and-set and compare-and-swap. Accesses to the new
wait-free objects have time complexity O(N), where N is the number of
concurrent processes. The wait-free objects have space complexity O
(N2), which is optimal. Our result demonstrates that it is possible to
construct wait-free synchronization mechanisms for GPUs without the
need of strong synchronization primitives in hardware and that wait-
free programming is possible for GPUs.
Full text Pdf (456 KB)
Source
Annual ACM Symposium on Principles of Distributed Computing archive
Proceedings of the twenty-seventh ACM symposium on Principles of
distributed computing table of contents
Toronto, Canada
SESSION: B4-1 table of contents
Pages 452-452
Year of Publication: 2008
ISBN:978-1-59593-989-0
Authors
Phuong Hoai Ha University of Troms=F8, Troms=F8, Norway
Philippas Tsigas Chalmers University of Technology, Gothenburg,
Sweden
Otto J. Anshus University of Troms=F8, Troms=F8, Norway
Sponsors
SIGOPS: ACM Special Interest Group on Operating Systems
ACM: Association for Computing Machinery
SIGACT: ACM Special Interest Group on Algorithms and Computation
Theory
Publisher
ACM New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 23, Downloads (12 Months): 54, Citation
Count: 0
Additional Information:
abstract references index terms collaborative colleagues
Tools and Actions: Review this Article
Save this Article to a Binder Display Formats: BibTex EndNote ACM
Ref
DOI Bookmark: Use this link to bookmark this Article:
http://doi.acm.org/10.1145/1400751.1400849
What is a DOI?
ABSTRACT
This paper aims at bridging the gap between the lack of
synchronization mechanisms in recent graphics processor (GPU)
architectures and the need of synchronization mechanisms in parallel
applications. Based on the intrinsic features of recent GPU
architectures, we construct strong synchronization objects like wait-
free and t-resilient read-modify-write objects for a general model of
recent GPU architectures without strong hardware synchronization
primitives like test-and-set and compare-and-swap. Accesses to the new
wait-free objects have time complexity O(N), where N is the number of
concurrent processes. The wait-free objects have space complexity O
(N2), which is optimal. Our result demonstrates that it is possible to
construct wait-free synchronization mechanisms for GPUs without the
need of strong synchronization primitives in hardware and that wait-
free programming is possible for GPUs.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from
the full text article. ACM has opted to expose the complete List
rather than only correct and linked references.
1
NVIDIA CUDA Compute Unified Device Architecture, Programming Guide,
version 1.0. NVIDIA Cor****ation, 2007.
2
M. J. Fischer, N. A. Lynch, and M. S. Paterson. Impossibility of
distributed consensus with one faulty process. J. ACM, 32(2):374--382,
1985.
3
M. Herlihy. Wait-free synchronization. ACM Transaction on Programming
and Systems, 11(1):124--149, 1991.
4
J. D. Owens, D. Luebke, N. Govindaraju, M. Harris, J. Kruger, A. E.
Lefohn, and T. J. Purcell. A survey of general-purpose computation on
graphics hardware. Computer Graphics Forum, 26(1):80--113, 2007.
INDEX TERMS
Primary Classification:
D. Software
D.1 PROGRAMMING TECHNIQUES
D.1.3 Concurrent Programming
Subjects: Parallel programming
Additional Classification:
C. Computer Systems Organization
C.1 PROCESSOR ARCHITECTURES
C.1.2 Multiple Data Stream Architectures (Multiprocessors)
Subjects: Single-instruction-stream, multiple-data-stream
processors (SIMD)
E. Data
E.1 DATA STRUCTURES
Subjects: Distributed data structures
General Terms:
Algorithms, Reliability, Theory
Keywords:
consensus, graphics processors., many-core architectures, read-modify-
write objects, synchronization
Collaborative Colleagues:
Phuong Hoai Ha: colleagues
Philippas Tsigas: colleagues
Otto J. Anshus: colleagues
|
