Wait-free programming for general purpose computations on graphics processors

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Wait-free programming for general purpose computations on graphics processors

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ø, Tromsø, Norway
Philippas Tsigas	Chalmers University of Technology, Gothenburg, Sweden
Otto J. Anshus	University of Tromsø, Tromsø, 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): 27, Downloads (12 Months): 106, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions 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(N²), 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 Corporation, 2007.
	2	Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (JACM), v.32 n.2, p.374-382, April 1985 [doi>10.1145/3149.214121]
	3	Maurice Herlihy, Wait-free synchronization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.1, p.124-149, Jan. 1991 [doi>10.1145/114005.102808]
	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.