Document Open Access Logo

The Silently Shifting Semicolon

Authors Daniel Marino, Todd Millstein, Madanlal Musuvathi, Satish Narayanasamy, Abhayendra Singh

PDF
Thumbnail PDF

File

LIPIcs.SNAPL.2015.177.pdf
  • Filesize: 430 kB
  • 13 pages

Document Identifiers

Author Details

Daniel Marino
Todd Millstein
Madanlal Musuvathi
Satish Narayanasamy
Abhayendra Singh

Cite AsGet BibTex

Daniel Marino, Todd Millstein, Madanlal Musuvathi, Satish Narayanasamy, and Abhayendra Singh. The Silently Shifting Semicolon. In 1st Summit on Advances in Programming Languages (SNAPL 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 32, pp. 177-189, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.SNAPL.2015.177

Abstract

Memory consistency models for modern concurrent languages have largely been designed from a system-centric point of view that protects, at all costs, optimizations that were originally designed for sequential programs. The result is a situation that, when viewed from a programmer's standpoint, borders on absurd. We illustrate this unfortunate situation with a brief fable and then examine the opportunities to right our path.
Keywords
  • memory consistency models; sequential consistency; safe programming languages; data races

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Sarita V. Adve and Hans-J. Boehm. Memory models: A case for rethinking parallel languages and hardware. Commun. ACM, 53(8):90-101, August 2010. Google Scholar
  2. Sarita V. Adve and Mark D. Hill. Weak ordering - a new definition. In Proceedings of the 17th Annual International Symposium on Computer Architecture, ISCA'90, pages 2-14, New York, NY, USA, 1990. ACM. Google Scholar
  3. Jade Alglave, Daniel Kroening, Vincent Nimal, and Daniel Poetzl. Don't sit on the fence: A static analysis approach to automatic fence insertion. CoRR, abs/1312.1411, 2013. Google Scholar
  4. Jade Alglave, Daniel Kroening, Vincent Nimal, and Daniel Poetzl. Don't sit on the fence - A static analysis approach to automatic fence insertion. In Computer Aided Verification - 26th International Conference, CAV 2014, pages 508-524, 2014. Google Scholar
  5. Colin Blundell, Milo M.K. Martin, and Thomas F. Wenisch. InvisiFence: Performance-transparent memory ordering in conventional multiprocessors. In Proceedings of the 36th Annual International Symposium on Computer Architecture, ISCA'09, pages 233-244, New York, NY, USA, 2009. ACM. Google Scholar
  6. Robert L. Bocchino, Jr., Vikram S. Adve, Danny Dig, Sarita V. Adve, Stephen Heumann, Rakesh Komuravelli, Jeffrey Overbey, Patrick Simmons, Hyojin Sung, and Mohsen Vakilian. A type and effect system for Deterministic Parallel Java. In Proceedings of the 24th ACM SIGPLAN Conference on Object Oriented Programming Systems Languages and Applications, OOPSLA'09, pages 97-116. ACM, 2009. Google Scholar
  7. Hans-J. Boehm and Sarita V. Adve. Foundations of the C++ concurrency memory model. In Proceedings of the 2008 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI'08, pages 68-78, New York, NY, USA, 2008. ACM. Google Scholar
  8. Chandrasekhar Boyapati, Robert Lee, and Martin Rinard. Ownership types for safe programming: Preventing data races and deadlocks. In Proceedings of the 17th ACM SIGPLAN Conference on Object-oriented Programming, Systems, Languages, and Applications, OOPSLA'02, pages 211-230, New York, NY, USA, 2002. ACM. Google Scholar
  9. Pietro Cenciarelli, Alexander Knapp, and Eleonora Sibilio. The Java memory model: Operationally, denotationally, axiomatically. In Proceedings of the 16th European Conference on Programming, ESOP'07, pages 331-346, Berlin, Heidelberg, 2007. Springer-Verlag. Google Scholar
  10. Tudor David, Rachid Guerraoui, and Vasileios Trigonakis. Everything you always wanted to know about synchronization but were afraid to ask. In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles, SOSP'13, pages 33-48. ACM, 2013. Google Scholar
  11. Yuelu Duan, Abdullah Muzahid, and Josep Torrellas. Weefence: Toward making fences free in TSO. In Proceedings of the 40th Annual International Symposium on Computer Architecture, ISCA '13, pages 213-224. ACM, 2013. Google Scholar
  12. John Erickson, Madanlal Musuvathi, Sebastian Burckhardt, and Kirk Olynyk. Effective data-race detection for the kernel. In Proceedings of the 9th USENIX Conference on Operating Systems Design and Implementation, OSDI'10, pages 1-16, Berkeley, CA, USA, 2010. USENIX Association. Google Scholar
  13. Cormac Flanagan and Stephen N. Freund. Type-based race detection for Java. In Proceedings of the ACM SIGPLAN 2000 Conference on Programming Language Design and Implementation, PLDI'00, pages 219-232, New York, NY, USA, 2000. ACM. Google Scholar
  14. Cormac Flanagan and Stephen N. Freund. FastTrack: Efficient and precise dynamic race detection. In Proceedings of the 2009 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI'09, pages 121-133, New York, NY, USA, 2009. ACM. Google Scholar
  15. Cormac Flanagan, Stephen N. Freund, Marina Lifshin, and Shaz Qadeer. Types for atomicity: Static checking and inference for java. ACM Trans. Program. Lang. Syst., 30(4):20:1-20:53, August 2008. Google Scholar
  16. K. Gharachorloo, A. Gupta, and J. Hennessy. Two techniques to enhance the performance of memory consistency models. In Proceedings of the 1991 International Conference on Parallel Processing, ICPP'91, pages 355-364, 1991. Google Scholar
  17. Chris Gniady, Babak Falsafi, and T. N. Vijaykumar. Is SC + ILP = RC? In Proceedings of the 26th Annual International Symposium on Computer Architecture, ISCA'99, pages 162-171, Washington, DC, USA, 1999. IEEE Computer Society. Google Scholar
  18. Mark D. Hill. Multiprocessors should support simple memory-consistency models. IEEE Computer, 31:28-34, 1998. Google Scholar
  19. Baris Kasikci, Cristian Zamfir, and George Candea. Data races vs. data race bugs: Telling the difference with portend. In Proceedings of the Seventeenth International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS XVII, pages 185-198, New York, NY, USA, 2012. ACM. Google Scholar
  20. Lindsey Kuper and Ryan R. Newton. Lvars: Lattice-based data structures for deterministic parallelism. In Proceedings of the 2Nd ACM SIGPLAN Workshop on Functional High-performance Computing, FHPC'13, pages 71-84. ACM, 2013. Google Scholar
  21. L. Lamport. How to make a multiprocessor computer that correctly executes multiprocess programs. IEEE Transactions on Computers, 100(28):690-691, 1979. Google Scholar
  22. Changhui Lin, Vijay Nagarajan, Rajiv Gupta, and Bharghava Rajaram. Efficient sequential consistency via conflict ordering. In Proceedings of the Seventeenth International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS XVII, pages 273-286, New York, NY, USA, 2012. ACM. Google Scholar
  23. Jeremy Manson, William Pugh, and Sarita V. Adve. The Java memory model. In Proceedings of the 32Nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL'05, pages 378-391, New York, NY, USA, 2005. ACM. Google Scholar
  24. Daniel Marino, Abhayendra Singh, Todd Millstein, Madanlal Musuvathi, and Satish Narayanasamy. A case for an SC-preserving compiler. In Proceedings of the 32Nd ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI'11, pages 199-210, New York, NY, USA, 2011. ACM. Google Scholar
  25. M. Naik, A. Aiken, and J. Whaley. Effective static race detection for Java. In PLDI'06: Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, pages 308-319, 2006. Google Scholar
  26. Satish Narayanasamy, Zhenghao Wang, Jordan Tigani, Andrew Edwards, and Brad Calder. Automatically classifying benign and harmful data races using replay analysis. In Proceedings of the 2007 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI'07, pages 22-31, New York, NY, USA, 2007. ACM. Google Scholar
  27. Benjamin Pierce. Types and Programming Languages. The MIT Press, 2002. Google Scholar
  28. Polyvios Pratikakis, Jeffrey S. Foster, and Michael Hicks. LOCKSMITH: Context-sensitive correlation analysis for race detection. In Proceedings of the 2006 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI'06, pages 320-331, New York, NY, USA, 2006. ACM. Google Scholar
  29. Parthasarathy Ranganathan, Vijay S. Pai, and Sarita V. Adve. Using speculative retirement and larger instruction windows to narrow the performance gap between memory consistency models. In Proceedings of the Ninth Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA'97, pages 199-210, New York, NY, USA, 1997. ACM. Google Scholar
  30. John Regehr. Race condition vs. data race. URL: http://blog.regehr.org/archives/490.
  31. S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and T. Anderson. Eraser: A dynamic data race detector for multithreaded programs. ACM Transactions on Computer Systems, 15(4):391-411, 1997. Google Scholar
  32. Dennis Shasha and Marc Snir. Efficient and correct execution of parallel programs that share memory. ACM Trans. Program. Lang. Syst., 10(2):282-312, April 1988. Google Scholar
  33. Abhayendra Singh, Satish Narayanasamy, Daniel Marino, Todd Millstein, and Madanlal Musuvathi. End-to-end sequential consistency. SIGARCH Comput. Archit. News, 40(3):524-535, June 2012. Google Scholar
  34. Zehra Sura, Xing Fang, Chi-Leung Wong, Samuel P. Midkiff, Jaejin Lee, and David Padua. Compiler techniques for high performance sequentially consistent Java programs. In Proceedings of the Tenth ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP'05, pages 2-13, New York, NY, USA, 2005. ACM. Google Scholar
  35. Viktor Vafeiadis, Thibaut Balabonski, Soham Chakraborty, Robin Morisset, and Francesco Zappa Nardelli. Common compiler optimisations are invalid in the c11 memory model and what we can do about it. In Proceedings of the 42Nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL'15, pages 209-220, New York, NY, USA, 2015. ACM. Google Scholar
  36. Jaroslav Ševčík and David Aspinall. On validity of program transformations in the Java memory model. In Proceedings of the 22Nd European Conference on Object-Oriented Programming, ECOOP'08, pages 27-51, Berlin, Heidelberg, 2008. Springer-Verlag. Google Scholar
  37. Yuan Yu, Tom Rodeheffer, and Wei Chen. RaceTrack: Efficient detection of data race conditions via adaptive tracking. In Proceedings of the Twentieth ACM Symposium on Operating Systems Principles, SOSP'05, pages 221-234, New York, NY, USA, 2005. ACM. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact