×

zbMATH — the first resource for mathematics

Toward a formal semantic framework for deterministic parallel programming. (English) Zbl 1350.68057
Peleg, David (ed.), Distributed computing. 25th international symposium, DISC 2011, Rome, Italy, September 20–22, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-24099-7/pbk). Lecture Notes in Computer Science 6950, 460-474 (2011).
Summary: Deterministic parallelism has become an increasingly attractive concept: a deterministic parallel program may be easier to construct, debug, understand, and maintain. However, there exist many different definitions of “determinism” for parallel programming. Many existing definitions have not yet been fully formalized, and the relationships among these definitions are still unclear. We argue that formalism is needed, and that history-based semantics – as used, for example, to define the Java and C++ memory models – provides a useful lens through which to view the notion of determinism. As a first step, we suggest several history-based definitions of determinism. We discuss some of their comparative advantages, prove containment relationships among them, and identify programming idioms that ensure them. We also propose directions for future work.
For the entire collection see [Zbl 1225.68024].
MSC:
68N19 Other programming paradigms (object-oriented, sequential, concurrent, automatic, etc.)
Software:
Grace; Kendo; Multilisp
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Adve, V., Ceze, L., Ford, B.: Organizers. In: 2nd Workshop on Determinism and Correctness in Parallel Programming, Newport Beach, CA (March 2011)
[2] Adve, S.V., Hill, M.D.: Weak Ordering–A New Definition. In: 17th Intl. Symp. on Computer Architecture, Seattle, WA (May 1990)
[3] Allen, M.D., Sridharan, S., Sohi, G.S.: Serialization Sets: A Dynamic Dependence-Based Parallel Execution Model. In: 14th ACM Symp. on Principles and Practice of Parallel Programming, Raleigh, NC (February 2009) · doi:10.1145/1594835.1504190
[4] Aviram, A., Weng, S.-C., Hu, S., Ford, B.: Efficient System-Enforced Deterministic Parallelism. In: 9th Symp. on Operating Systems Design and Implementation, Vancouver, BC, Canada (October 2010)
[5] Bergan, T., Anderson, O., Devietti, J., Ceze, L., Grossman, D.: CoreDet: A Compiler and Runtime System for Deterministic Multithreaded Execution. In: 15th Intl. Conf. on Architectural Support for Programming Languages and Operating Systems, Pittsburgh, PA (March 2010) · doi:10.1145/1736020.1736029
[6] Bergan, T., Hunt, N., Ceze, L., Gribble, S.D.: Deterministic Process Groups in dOS. In: 9th Symp. on Operating Systems Design and Implementation, Vancouver, BC, Canada (October 2010)
[7] Bergan, T., Devietti, J., Hunt, N., Ceze, L.: The Deterministic Execution Hammer: How Well Does It Actually Pound Nails? In: 2nd Workshop on Determinism and Correctness in Parallel Programming, Newport Beach, CA (March 2011)
[8] Berger, E., Yang, T., Liu, T., Novark, G.: Grace: Safe Multithreaded Programming for C/C++. In: OOPSLA 2009 Conf. Proc., Orlando, FL (October 2009)
[9] Blundell, C., Lewis, E.C., Martin, M.M.K.: Deconstructing Transactional Semantics: The Subtleties of Atomicity. In: 4th Workshop on Duplicating, Deconstructing, and Debunking, Madison, WI (June 2005)
[10] Bocchino Jr., R.L., Adve, V.S., Dig, D., Adve, S., Heumann, S., Komuravelli, R., Overbey, J., Simmons, P., Sung, H., Vakilian, M.: A Type and Effect System for Deterministic Parallel Java. In: OOPSLA 2009 Conf. Proc., Orlando, FL (October 2009) · doi:10.1145/1640089.1640097
[11] Boehm, H.-J., Adve, S.V.: Foundations of the C++ Concurrency Memory Model. In: SIGPLAN 2008 Conf. on Programming Language Design and Implementation, Tucson, AZ (June 2008)
[12] Budimlić, Z., Burke, M., Cavé, V., Knobe, K., Lowney, G., Newton, R., Palsberg, J., Peixotto, D., Sarkar, V., Schlimbach, F., Taşirlar, S.: Concurrent Collections. Journal of Scientific Programming 18(3–4) (August 2010) · doi:10.1155/2010/521797
[13] Ceze, L., Adve, V.: Organizers. In: Workshop on Deterministic Multiprocessing and Parallel Programming, Seattle, WA (November-December 2009)
[14] Chazan, C., Miranker, W.: Chaotic Relaxation. Linear Algebra and Its Applications 2, 199–222 (1969) · Zbl 0225.65043 · doi:10.1016/0024-3795(69)90028-7
[15] Dalessandro, L., Scott, M.L., Spear, M.F.: Transactions as the Foundation of a Memory Consistency Model. In: 24th Intl. Symp. on Distributed Computing, Cambridge, MA (September 2010); Previously Computer Science TR 959, Univ. of Rochester (July 2010)
[16] Devietti, J., Lucia, B., Ceze, L., Oskin, M.: DMP: Deterministic Shared Memory Multiprocessing. In: 14th Intl. Conf. on Architectural Support for Programming Languages and Operating Systems, Washington, DC (March 2009) · doi:10.1145/1508244.1508255
[17] Emrath, P.A., Padua, D.A.: Automatic Detection of Nondeterminacy in Parallel Programs. In: ACM SIGPLAN/SIGOPS Workshop on Parallel and Distributed Debugging, Madison, WI (May 1988) · doi:10.1145/68210.69224
[18] Halstead Jr, R.H.: Multilisp: A Language for Concurrent Symbolic Computation. ACM Trans. on Programming Languages and Systems 7(4), 501–538 (1985) · Zbl 0581.68037 · doi:10.1145/4472.4478
[19] Herlihy, M.P., Wing, J.M.: Linearizability: A Correctness Condition for Concurrent Objects. ACM Trans. on Programming Languages and Systems 12(3), 463–492 (1990) · doi:10.1145/78969.78972
[20] Hower, D.R., Hill, M.D.: Rerun: Exploiting Episodes for Lightweight Memory Race Recording. In: 35th Intl. Symp. on Computer Architecture, Beijing, China (June 2008) · doi:10.1145/1394608.1382144
[21] Karp, R.M., Miller, R.E.: Properties of a Model for Parallel Computations: Determinacy, Termination, Queueing. SIAM Journal on Applied Mathematics 14(6), 1390–1411 (1966) · Zbl 0149.12501 · doi:10.1137/0114108
[22] Manson, J., Pugh, W., Adve, S.: The Java Memory Model. In: 32nd ACM Symp. on Principles of Programming Languages, Long Beach, CA (January 2005) · Zbl 1369.68079 · doi:10.1145/1040305.1040336
[23] Midkiff, S., Pai, V., Bennett, D.: Organizers. In: Workshop on Integrating Parallelism Throughout the Undergraduate Computing Curriculum, San Antonio, TX (February 2011)
[24] Montesinos, P., Ceze, L., Torrellas, J.: DeLorean: Recording and Deterministically Replaying Shared-Memory Multiprocessor Execution Efficiently. In: 35th Intl. Symp. on Computer Architecture, Beijing, China (June 2008) · doi:10.1145/1394608.1382146
[25] Netzer, R.H.B., Miller, B.P.: What Are Race Conditions? Some Issues and Formalizations. ACM Letters on Programming Languages and Systems 1(1), 74–88 (1992) · doi:10.1145/130616.130623
[26] Olszewski, M., Ansel, J., Amarasinghe, S.: Kendo: Efficient Deterministic Multithreading in Software. In: 14th Intl. Conf. on Architectural Support for Programming Languages and Operating Systems, Washington, DC (March 2009) · doi:10.1145/1508244.1508256
[27] Papadimitriou, C.H.: The Serializability of Concurrent Database Updates. Journal of the ACM 26(4), 631–653 (1979) · Zbl 0419.68036 · doi:10.1145/322154.322158
[28] Shavit, N.: Organizer. In: Workshop on Directions in Multicore Programming Education, Washington, DC (March 2009)
[29] Spear, M.F., Dalessandro, L., Marathe, V.J., Scott, M.L.: Ordering-Based Semantics for Software Transactional Memory. In: 12th Intl. Conf. on Principles of Distributed Systems, Luxor, Egypt (December 2008) · Zbl 05500314 · doi:10.1007/978-3-540-92221-6_19
[30] Steele Jr., G.L., Saraswat, V.A.: Organizers. In: Workshop on Curricula for Concurrency, Orlando, FL (October 2009)
[31] Veeraraghavan, K., Lee, D., Wester, B., Ouyang, J., Chen, P., Flinn, J., Narayanasamy, S.: DoublePlay: Parallelizing Sequential Logging and Replay. In: 16th Intl. Conf. on Architectural Support for Programming Languages and Operating Systems, Newport Beach, CA (March 2011) · doi:10.1145/1950365.1950370
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.