Synchronization using counting semaphores

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Synchronization using counting semaphores

Full text

Pdf (1.09 MB)

Source

International Conference on Supercomputing archive
Proceedings of the 2nd international conference on Supercomputing table of contents

St. Malo, France

Pages: 627 - 637

Year of Publication: 1988

ISBN:0-89791-272-1

Author

V. Sarkar

T. J. Watson Research Center, Yorktown Heights, NY

Sponsor

SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 15, Downloads (12 Months): 55, Citation Count: 5

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/55364.55426 What is a DOI?

ABSTRACT

This paper studies the optimization problem of enforcing a dependence graph with the minimum number of synchronization operations. For a dependence graph with N vertices, it is shown that binary semaphores may require &Ogr;(N2) operations, compared to &Ogr;(N) operations for counting semaphores. Though the optimization problem of using the minimum number of counting semaphore operations is shown to be NP-complete, we present an approximation algorithm that is observed to be very close to optimal (within 0.5%) on small, randomly generated dependence graphs. A surprising property of the problem is that the inclusion (rather than removal) of transitive edges can actually help reduce the number of synchronization operations. We characterize as class of dependence graphs for which the approximation algorithm is optimal. This class includes forests of fan-in trees, fan-out trees and series-parallel graphs. The number of synchronization operations needed for binary and counting semaphores are compared for randomly generated dependence graphs, using an implementation of the approximation algorithm in LISP/VM. The experimental results show that the use of counting semaphores significantly reduces the total number of synchronization operations, compared to binary semaphores.

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	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	2	Zhiyuan Li. A Technique for Reducing Synchronization Overhead in Large Scale Multiprocessors, Center for Supercomputing Research & Development, U. of illinois, May 1985. CSRD Report No. 521.
	3	Samuel Pratt Midkiff. Automatic Generation of Synchronization Instructions For Parallel Processors, Center for Supercomputing Research & Development, U. of Illinois, May 1986. CSRD Rept. No.588, UILU-ENG-86-8002.
	4	S. P. Midkiff , D. A. Padua, Compiler algorithms for synchronization, IEEE Transactions on Computers, v.36 n.12, p.1485-1495, Dec. 1987 [doi>10.1109/TC.1987.5009499]
	5	Robert Tarjan. Depth-first Search and Linear Graph Algorithms. SIAM Journal of Computing, 1,2:146-160, September 1972.

CITED BY 6

	T. M. Watts , M. L. Soffa , R. Gupta, Techniques for integrating parallelizing transformations and compiler-based scheduling methods, Proceedings of the 1992 ACM/IEEE conference on Supercomputing, p.830-839, November 16-20, 1992, Minneapolis, Minnesota, United States
	Zhiyuan Li, Compiler algorithms for event variable synchronization, Proceedings of the 5th international conference on Supercomputing, p.85-95, June 17-21, 1991, Cologne, West Germany
	F. Allen , M. Burke , R. Cytron , J. Ferrante , W. Hsieh, A framework for determining useful parallelism, Proceedings of the 2nd international conference on Supercomputing, p.207-215, June 1988, St. Malo, France
	Jun Shirako , David M. Peixotto , Vivek Sarkar , William N. Scherer, Phasers: a unified deadlock-free construct for collective and point-to-point synchronization, Proceedings of the 22nd annual international conference on Supercomputing, June 07-12, 2008, Island of Kos, Greece
	Jun Shirako , Jisheng M. Zhao , V. Krishna Nandivada , Vivek N. Sarkar, Chunking parallel loops in the presence of synchronization, Proceedings of the 23rd international conference on Supercomputing, June 08-12, 2009, Yorktown Heights, NY, USA
	V. Sarkar, Automatic partitioning of a program dependence graph into parallel tasks, IBM Journal of Research and Development, v.35 n.5-6, p.779-804, Sept./Nov. 1991