Detecting data races in Cilk programs that use locks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Detecting data races in Cilk programs that use locks

Full text

Pdf (1.81 MB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures table of contents

Puerto Vallarta, Mexico

Pages: 298 - 309

Year of Publication: 1998

ISBN:0-89791-989-0

Authors

Guang-Ien Cheng	MIT Laboratory for Computer Science, 545 Technology Square, Cambridge, Massachusetts
Mingdong Feng	Department of Information Systems and Computer Science, National University of Singapore, 10 Lower Kent Ridge Road, Republic of Singapore 119260
Charles E. Leiserson	MIT Laboratory for Computer Science, 545 Technology Square, Cambridge, Massachusetts
Keith H. Randall	MIT Laboratory for Computer Science, 545 Technology Square, Cambridge, Massachusetts
Andrew F. Stark	MIT Laboratory for Computer Science, 545 Technology Square, Cambridge, Massachusetts

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture
SIGOPS: ACM Special Interest Group on Operating Systems

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 14, Downloads (12 Months): 61, Citation Count: 22

Additional Information:

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

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	J. Barnes and P. Hut. A hierarchical O(NlogN) force-calculation algorithm. Nature, 324:446-449, 1986.
	2	Philippe Bekaert, Frank Suykens de Laet, and Philip Dutre. Renderpark, 1997. Available on the Internet from http://www.cs. kuleuven, ae./cwis/research/graphi cs/KENDERPARK/.
	3	Robert D. Blumofe, Executing multithreaded programs efficiently, Massachusetts Institute of Technology, Cambridge, MA, 1996
	4	Robert D. Blumofe , Christopher F. Joerg , Bradley C. Kuszmaul , Charles E. Leiserson , Keith H. Randall , Yuli Zhou, Cilk: an efficient multithreaded runtime system, Journal of Parallel and Distributed Computing, v.37 n.1, p.55-69, Aug. 25, 1996 [doi>10.1006/jpdc.1996.0107]
	5	Robert D. Blumofe , Christopher F. Joerg , Bradley C. Kuszmaul , Charles E. Leiserson , Keith H. Randall , Yuli Zhou, Cilk: an efficient multithreaded runtime system, Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.207-216, July 19-21, 1995, Santa Barbara, California, United States
	6	Cilk-5.1 Reference Manual. Available on the lnternet fiom ht;tp:// "theory. Ics .mit. edu/" cilk.
	7	Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
	8	David E. Culler , Anurag Sah , Klaus E. Schauser , Thorsten von Eicken , John Wawrzynek, Fine-grain parallelism with minimal hardware support: a compiler-controlled threaded abstract machine, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.164-175, April 08-11, 1991, Santa Clara, California, United States
	9	A. Dinning , E. Schonberg, An empirical comparison of monitoring algorithms for access anomaly detection, Proceedings of the second ACM SIGPLAN symposium on Principles & practice of parallel programming, p.1-10, March 14-16, 1990, Seattle, Washington, United States
	10	Anne Dinning , Edith Schonberg, Detecting access anomalies in programs with critical sections, Proceedings of the 1991 ACM/ONR workshop on Parallel and distributed debugging, p.85-96, May 20-21, 1991, Santa Cruz, California, United States
	11	Anne Carolyn Dinning. Detecting Nondeterminism in Shared Memory Parallel Pmgrants. PhD thesis, Department of Computer Science, New York University, July 1990.
	12	P. A. Emrath , S. Chosh , D. A. Padua, Event synchronization analysis for debugging parallel programs, Proceedings of the 1989 ACM/IEEE conference on Supercomputing, p.580-588, November 12-17, 1989, Reno, Nevada, United States [doi>10.1145/76263.76329]
	13	Mingdong Feng , Charles E. Leiserson, Efficient detection of determinacy races in Cilk programs, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.1-11, June 23-25, 1997, Newport, Rhode Island, United States [doi>10.1145/258492.258493]
	14	Yaacov Fenster. Detecting parallel access anomalies. Master's thesis, Hebrew University, March 1998.
	15	Matteo Frigo , Charles E. Leiserson , Keith H. Randall, The implementation of the Cilk-5 multithreaded language, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.212-223, June 17-19, 1998, Montreal, Quebec, Canada
	16	A V Goldberg , R E Tarjan, A new approach to the maximum flow problem, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.136-146, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12144]
	17	Michael Halbherr, Yuli Zhou, and Chris E Joe,'g. MIMD-style parallel programming with continuation-passing threads. In Pn)ceedings of the 2nd International Workshop on Massive Parallelism: Hardware, Software, and Applications, Capri, Italy, September 1994.
	18	David R Helmbold, Charles E. McDowell, and Jian-Zhong Wang. Analyzing traces with anonymous synchronization. In Proceedings of the 1990 lnternatiomll Conference on Parallel Processing, pages II70- 1177, August 1990.
	19	Richard C. Holt, Some Deadlock Properties of Computer Systems, ACM Computing Surveys (CSUR), v.4 n.3, p.179-196, Sept. 1972 [doi>10.1145/356603.356607]
	20	Christopher F. Joerg, The cilk system for parallel multithreaded computing, Massachusetts Institute of Technology, Cambridge, MA, 1996
	21	Leslie Lamport. How to make a multiprocessor computer that correctly executes multiprocess programs. IEEE Transactions on Computers, C-28(9):690-691, September 1979.
	22	John Mellor-Crummey, On-the-fly detection of data races for programs with nested fork-join parallelism, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.24-33, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.125861]
	23	B. P. Miller , Jong-Deok Choi, A mechanism for efficient debugging of parallel programs, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.135-144, June 20-24, 1988, Atlanta, Georgia, United States
	24	Sang L. Min , Jong-Deok Choi, An efficient cache-based access anomaly detection scheme, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.235-244, April 08-11, 1991, Santa Clara, California, United States
	25	Greg Nelson, K. Rustan M. Leino, James B, Saxe, and Raymie Stata. Extended static checking home page, 1996. Available on the Internet from http ://www. research, digital, com/SRC/ esc/Esc, html,
	26	Robert H. B. Netzer and Sanjoy Ghosh. Efficient race condition detection for shared-memory programs with post/wait synchronization. in Proceedings of the 1992 International Conference on Parallel Processing, St. Charles, Illinois, August 1992.
	27	Robexl H. B. Netzer and Barton R Millet'. On the complexity of event ordering for shared-memory parallel program executions. In Proceedings of the 1990 International Conference on Parallel Processing, pages ll: 93-97, August 1990.
	28	Robert H. B. Netzer , Barton P. Miller, What are race conditions?: Some issues and formalizations, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.1, p.74-88, March 1992 [doi>10.1145/130616.130623]
	29	ltzhak Nudler and Larry Rudolph. Tools for the efficient development of efficient parallel programs, in Proceedings #ffthe First Israeli Conference on Computer Systems Engineering, May 1986.
	30	Dejan Perkovic , Peter J. Keleher, Online data-race detection via coherency guarantees, Proceedings of the second USENIX symposium on Operating systems design and implementation, p.47-57, October 29-November 01, 1996, Seattle, Washington, United States
	31	Martin C. Rinard , Pedro C. Diniz, Commutativity analysis: a new analysis framework for parallelizing compilers, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.54-67, May 21-24, 1996, Philadelphia, Pennsylvania, United States
	32	Stefan Savage , Michael Burrows , Greg Nelson , Patrick Sobalvarro , Thomas Anderson, Eraser: a dynamic data race detector for multi-threaded programs, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.27-37, October 05-08, 1997, Saint Malo, France
	33	Robert Endre Tarjan, Applications of Path Compression on Balanced Trees, Journal of the ACM (JACM), v.26 n.4, p.690-715, Oct. 1979 [doi>10.1145/322154.322161]

CITED BY 22

	Robert D. Blumofe , Charles E. Leiserson, Scheduling multithreaded computations by work stealing, Journal of the ACM (JACM), v.46 n.5, p.720-748, Sept. 1999
	Radu Rugina , Martin Rinard, Symbolic bounds analysis of pointers, array indices, and accessed memory regions, ACM SIGPLAN Notices, v.35 n.5, p.182-195, May 2000
	Matteo Frigo , Charles E. Leiserson , Keith H. Randall, The implementation of the Cilk-5 multithreaded language, ACM SIGPLAN Notices, v.33 n.5, p.212-223, May 1998
	Radu Rugina , Martin C. Rinard, Pointer analysis for structured parallel programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.25 n.1, p.70-116, January 2003
	Robert O'Callahan , Jong-Deok Choi, Hybrid dynamic data race detection, ACM SIGPLAN Notices, v.38 n.10, October 2003
	Dawson Engler , Ken Ashcraft, RacerX: effective, static detection of race conditions and deadlocks, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
	Chandrasekhar Boyapati , Martin Rinard, A parameterized type system for race-free Java programs, ACM SIGPLAN Notices, v.36 n.11, p.56-69, 11/01/2001
	Daniel Jackson , Martin Rinard, Software analysis: a roadmap, Proceedings of the Conference on The Future of Software Engineering, p.133-145, June 04-11, 2000, Limerick, Ireland
	Dan Grossman, Type-safe multithreading in cyclone, ACM SIGPLAN Notices, v.38 n.3, March 2003
	Radu Rugina , Martin Rinard, Pointer analysis for multithreaded programs, ACM SIGPLAN Notices, v.34 n.5, p.77-90, May 1999
	Edith Schonberg, On-the-fly detection of access anomalies, ACM SIGPLAN Notices, v.39 n.4, April 2004
	Shaz Qadeer , Dinghao Wu, KISS: keep it simple and sequential, ACM SIGPLAN Notices, v.39 n.6, May 2004
	Jong-Deok Choi , Keunwoo Lee , Alexey Loginov , Robert O'Callahan , Vivek Sarkar , Manu Sridharan, Efficient and precise datarace detection for multithreaded object-oriented programs, ACM SIGPLAN Notices, v.37 n.5, May 2002
	Radu Rugina , Martin C. Rinard, Symbolic bounds analysis of pointers, array indices, and accessed memory regions, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.2, p.185-235, March 2005
	Michael A. Bender , Jeremy T. Fineman , Seth Gilbert , Charles E. Leiserson, On-the-fly maintenance of series-parallel relationships in fork-join multithreaded programs, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain
	Michael F. Ringenburg , Dan Grossman, AtomCaml: first-class atomicity via rollback, ACM SIGPLAN Notices, v.40 n.9, September 2005
	Mayur Naik , Alex Aiken , John Whaley, Effective static race detection for Java, ACM SIGPLAN Notices, v.41 n.6, June 2006
	Paul Sack , Brian E. Bliss , Zhiqiang Ma , Paul Petersen , Josep Torrellas, Accurate and efficient filtering for the Intel thread checker race detector, Proceedings of the 1st workshop on Architectural and system support for improving software dependability, p.34-41, October 21-21, 2006, San Jose, California
	Tayfun Elmas , Shaz Qadeer , Serdar Tasiran, Goldilocks: a race and transaction-aware java runtime, ACM SIGPLAN Notices, v.42 n.6, June 2007
	Bohuslav Krena , Zdenek Letko , Rachel Tzoref , Shmuel Ur , Tomáš Vojnar, Healing data races on-the-fly, Proceedings of the 2007 ACM workshop on Parallel and distributed systems: testing and debugging, July 09-09, 2007, London, United Kingdom
	Zachary Anderson , David Gay , Rob Ennals , Eric Brewer, SharC: checking data sharing strategies for multithreaded c, ACM SIGPLAN Notices, v.43 n.6, June 2008
	Marek Olszewski , Jason Ansel , Saman Amarasinghe, Kendo: efficient deterministic multithreading in software, ACM SIGPLAN Notices, v.44 n.3, March 2009