Cited By
View all- Ciccozzi FAddazi LAsadollah SLisper BMasud AMubeen S(2023)A Comprehensive Exploration of Languages for Parallel ComputingACM Computing Surveys10.1145/348500855:2(1-39)Online publication date: 31-Mar-2023
Concurrency-aware object-oriented programming with roles
Article No.: 130, Pages 1 - 30
Abstract
Object-oriented Programming has been effective in reducing code complexity in sequential programs, but in current practice, concurrent programs still present a number of challenges. We present here a model of object-oriented programming that identifies concurrent tasks and the relationship between objects and tasks, effectively making objects concurrency-aware. This awareness is formalized in a parallel programming model where every object plays a role in every task (e.g., the readonly role). When an object is shared with a new task, it adapts to the new sharing pattern by changing its roles, and therefore its behavior, i.e., the operations that can be performed with this object. This mechanism can be leveraged to prevent interfering accesses from concurrently executing tasks, and therefore makes parallel execution deterministic.
To this end, we present a role-based programming language that includes several novel concepts (role transitions, guarding, slicing) to enable practical, object-oriented deterministic parallel programming. We show that this language can be used to safely implement programs with a range of different parallel patterns. The implementations to 8 widely used programming problems achieve substantial parallel speedups and demonstrate that this approach delivers performance roughly on par with manually synchronized implementations.
Supplementary Material
WEBM File (a130-faes.webm)
- Download
- 101.61 MB
References
[1]
Gul Agha. 1986. Actors: A Model of Concurrent Computation in Distributed Systems. MIT Press, Cambridge, MA, USA.
[2]
Gul Agha. 1990. Concurrent Object-Oriented Programming. Commun. ACM 33, 9 (Sept. 1990), 125–141.
[3]
Jamie Allen. 2013. Effective Akka. O’Reilly and Associates, Sebastopol, Calif.
[4]
Matthew D. Allen, Srinath Sridharan, and Gurindar S. Sohi. 2009. Serialization Sets: A Dynamic Dependence-Based Parallel Execution Model. In Proceedings of the 14th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP ’09). ACM, New York, NY, USA, 85–96.
[5]
Joe Armstrong, Robert Virding, Claes Wikström, and Mike Williams. 1996. Concurrent Programming in ERLANG (2nd ed.). Prentice Hall International (UK) Ltd., Hertfordshire, UK.
[6]
Arvind, Rishiyur S. Nikhil, and Keshav K. Pingali. 1989. I-Structures: Data Structures for Parallel Computing. ACM Trans. Program. Lang. Syst. 11, 4 (Oct. 1989), 598–632.
[7]
Laurent Baduel, Françoise Baude, Denis Caromel, Arnaud Contes, Fabrice Huet, Matthieu Morel, and Romain Quilici. 2006. Programming, Composing, Deploying for the Grid. In Grid Computing: Software Environments and Tools. Springer, London, 205–229.
[8]
Henry C. Baker, Jr. and Carl Hewitt. 1977. The Incremental Garbage Collection of Processes. In Proceedings of the 1977 Symposium on Artificial Intelligence and Programming Languages. ACM, New York, 55–59.
[9]
Phil Bernstein, Sergey Bykov, Alan Geller, Gabriel Kliot, and Jorgen Thelin. 2014. Orleans: Distributed Virtual Actors for Programmability and Scalability. Technical Report MSR-TR-2014-41. Microsoft Research. https://www.microsoft.com/ en- us/research/publication/orleans- distributed- virtual- actors- for- programmability- and- scalability/
[10]
Kevin Bierhoff and Jonathan Aldrich. 2007. Modular Typestate Checking of Aliased Objects. In Proceedings of the 22nd Annual ACM SIGPLAN Conference on Object-Oriented Programming Systems and Applications (OOPSLA ’07). ACM, New York, NY, USA, 301–320.
[11]
Robert L. Bocchino and Vikram S. Adve. 2011. Types, Regions, and Effects for Safe Programming with Object-Oriented Parallel Frameworks. In Proceedings of the 25th European Conference on Object-Oriented Programming (ECOOP ’11). Springer-Verlag, Berlin, Heidelberg, 306–332.
[12]
Robert L. Bocchino, Vikram S. Adve, Sarita V. Adve, and Marc Snir. 2009a. Parallel Programming Must Be Deterministic by Default. In Proceedings of the 1st USENIX Conference on Hot Topics in Parallelism (HotPar ’09). USENIX Association, Berkeley. http://dl.acm.org/citation.cfm?id=1855591.1855595
[13]
Robert L. Bocchino, Vikram S. Adve, Danny Dig, Sarita V. Adve, Stephen Heumann, Rakesh Komuravelli, Jeffrey Overbey, Patrick Simmons, Hyojin Sung, and Mohsen Vakilian. 2009b. 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). ACM, New York, 97–116.
[14]
Chandrasekhar Boyapati, Robert Lee, and Martin Rinard. 2002. 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). ACM, New York, NY, USA, 211–230.
[15]
John Boyland. 2003. Checking Interference with Fractional Permissions. In Static Analysis (SAS ’03). Springer, Berlin, Heidelberg, 55–72.
[16]
John Tang Boyland and William Retert. 2005. Connecting Effects and Uniqueness with Adoption. In Proceedings of the 32nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’05). ACM, New York, NY, USA, 283–295.
[17]
Zoran Budimlić, Michael Burke, Vincent Cavé, Kathleen Knobe, Geoff Lowney, Ryan Newton, Jens Palsberg, David Peixotto, Vivek Sarkar, Frank Schlimbach, and Sağnak Taşırlar. 2010. Concurrent Collections. Scientific Programming 18, 3 (Jan. 2010), 203–217.
[18]
Chi Cao Minh, JaeWoong Chung, Christos Kozyrakis, and Kunle Olukotun. 2008. STAMP: Stanford Transactional Applications for Multi-Processing. In Proceedings of The IEEE International Symposium on Workload Characterization (IISWC ’08).
[19]
David G. Clarke, James Noble, and John Potter. 2001. Simple Ownership Types for Object Containment. In Proceedings of the 15th European Conference on Object-Oriented Programming (ECOOP ’01). Springer-Verlag, London, UK, 53–76.
[20]
David G. Clarke, John M. Potter, and James Noble. 1998. Ownership Types for Flexible Alias Protection. In Proceedings of the 13th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA ’98). ACM, New York, NY, USA, 48–64.
[21]
Joseph Devietti, Brandon Lucia, Luis Ceze, and Mark Oskin. 2009. DMP: Deterministic Shared Memory Multiprocessing. In Proceedings of the 14th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS XIV). ACM, New York, NY, USA, 85–96.
[22]
Eclipse Foundation. 2006. Xtext. http://www.eclipse.org/Xtext/
[23]
Michael Faes and Thomas R. Gross. 2017. Parallel Roles for Practical Deterministic Parallel Programming. In Proceedings of the 30th International Workshop on Languages and Compilers for Parallel Computing (LCPC ’17).
[24]
Michael Faes and Thomas R. Gross. 2018. Formal Proof of Determinism for the Parallel Roles Model. Technical Report. Department of Computer Science, ETH Zurich, Zürich, Switzerland. https://www.ethz.ch/content/dam/ethz/special- interest/ infk/inst- cs/lst- dam/documents/Publications/parallel- roles- determinism- proof.pdf
[25]
David Gay, Joel Galenson, Mayur Naik, and Kathy Yelick. 2011. Yada: Straightforward Parallel Programming. Parallel Comput. 37, 9 (Sept. 2011), 592–609.
[26]
Philipp Haller and Martin Odersky. 2007. Actors That Unify Threads and Events. In Proceedings of the 9th International Conference on Coordination Models and Languages (COORDINATION’07). Springer-Verlag, Berlin, Heidelberg, 171–190. http://dl.acm.org/citation.cfm?id=1764606.1764620
[27]
Robert H. Halstead, Jr. 1985. Multilisp: A Language for Concurrent Symbolic Computation. ACM Trans. Program. Lang. Syst. 7, 4 (Oct. 1985), 501–538.
[28]
Tim Harris and Keir Fraser. 2003. Language Support for Lightweight Transactions. In Proceedings of the 18th Annual ACM SIGPLAN Conference on Object-Oriented Programing, Systems, Languages, and Applications (OOPSLA ’03). ACM, New York, 388–402.
[29]
Maurice Herlihy and J. Eliot B. Moss. 1993. Transactional Memory: Architectural Support for Lock-Free Data Structures. In Proceedings of the 20th Annual International Symposium on Computer Architecture (ISCA ’93). ACM, New York, 289–300.
[30]
Stephen T. Heumann, Vikram S. Adve, and Shengjie Wang. 2013. The Tasks with Effects Model for Safe Concurrency. In Proceedings of the 18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP ’13). ACM, New York, 239–250.
[31]
Carl Hewitt, Peter Bishop, and Richard Steiger. 1973. A Universal Modular ACTOR Formalism for Artificial Intelligence. In Proceedings of the 3rd International Joint Conference on Artificial Intelligence (IJCAI’73). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 235–245. http://dl.acm.org/citation.cfm?id=1624775.1624804
[32]
Bart Jacobs, Jan Smans, Frank Piessens, and Wolfram Schulte. 2006. A Statically Verifiable Programming Model for Concurrent Object-Oriented Programs. In Proceedings of the 8th International Conference on Formal Methods and Software Engineering (ICFEM ’06). Springer-Verlag, Berlin, Heidelberg, 420–439.
[33]
Lindsey Kuper and Ryan R. Newton. 2013. LVars: Lattice-Based Data Structures for Deterministic Parallelism. In Proceedings of the 2nd ACM SIGPLAN Workshop on Functional High-Performance Computing (FHPC ’13). ACM, New York, 71–84.
[34]
Lindsey Kuper, Aaron Todd, Sam Tobin-Hochstadt, and Ryan R. Newton. 2014a. Taming the Parallel Effect Zoo: Extensible Deterministic Parallelism with LVish. In Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’14). ACM, New York, 2–14.
[35]
Lindsey Kuper, Aaron Turon, Neelakantan R. Krishnaswami, and Ryan R. Newton. 2014b. Freeze After Writing: QuasiDeterministic Parallel Programming with LVars. In Proceedings of the 41st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’14). ACM, New York, 257–270.
[36]
Monica S. Lam and Martin C. Rinard. 1991. Coarse-Grain Parallel Programming in Jade. In Proceedings of the 3rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP ’91). ACM, New York, 94–105.
[37]
Edward A. Lee. 2006. The Problem with Threads. Computer 39, 5 (May 2006), 33–42.
[38]
Li Lu and Michael L. Scott. 2011. Toward a Formal Semantic Framework for Deterministic Parallel Programming. In Proceedings of the 25th International Conference on Distributed Computing (DISC ’11). Springer-Verlag, Berlin, Heidelberg, 460–474.
[39]
Simon Marlow, Ryan Newton, and Simon Peyton Jones. 2011. A Monad for Deterministic Parallelism. In Proceedings of the 4th ACM Symposium on Haskell (Haskell ’11). ACM, New York, 71–82.
[40]
Nicholas D. Matsakis and Felix S. Klock, II. 2014. The Rust Language. In Proceedings of the 2014 ACM SIGAda Annual Conference on High Integrity Language Technology (HILT ’14). ACM, New York, NY, USA, 103–104.
[41]
Oracle Corporation. 2014. API Reference of the Java.Util.Stream Package (Java Platform SE 8). https://docs.oracle.com/ javase/8/docs/api/java/util/stream/package- summary.html
[42]
Lawrence Rauchwerger and David Padua. 1995. The LRPD Test: Speculative Run-Time Parallelization of Loops with Privatization and Reduction Parallelization. In Proceedings of the ACM SIGPLAN 1995 Conference on Programming Language Design and Implementation (PLDI ’95). ACM, New York, 218–232.
[43]
Martin C. Rinard and Monica S. Lam. 1998. The Design, Implementation, and Evaluation of Jade. ACM Trans. Program. Lang. Syst. 20, 3 (May 1998), 483–545.
[44]
Nir Shavit and Dan Touitou. 1995. Software Transactional Memory. In Proceedings of the 14th Annual ACM Symposium on Principles of Distributed Computing (PODC ’95). ACM, New York, 204–213.
[45]
L. A. Smith, J. M. Bull, and J. Obdrzálek. 2001. A Parallel Java Grande Benchmark Suite. In Proceedings of the 2001 ACM/IEEE Conference on Supercomputing (SC ’01). ACM, New York, NY, USA, 8–8.
[46]
Gurindar S. Sohi, Scott E. Breach, and T. N. Vijaykumar. 1995. Multiscalar Processors. In Proceedings of the 22nd Annual International Symposium on Computer Architecture (ISCA ’95). ACM, New York, 414–425.
[47]
Sriram Srinivasan and Alan Mycroft. 2008. Kilim: Isolation-Typed Actors for Java. In Proceedings of the 22Nd European Conference on Object-Oriented Programming (ECOOP ’08). Springer-Verlag, Berlin, Heidelberg, 104–128.
[48]
J. Steffan and T Mowry. 1998. The Potential for Using Thread-Level Data Speculation to Facilitate Automatic Parallelization. In Proceedings of the 4th International Symposium on High-Performance Computer Architecture (HPCA ’98). IEEE Computer Society, Washington, DC, 2–13.
[49]
Sven Stork, Paulo Marques, and Jonathan Aldrich. 2009. Concurrency by Default: Using Permissions to Express Dataflow in Stateful Programs. In Proceedings of the 24th ACM SIGPLAN Conference Companion on Object Oriented Programming Systems Languages and Applications (OOPSLA ’09). ACM, New York, NY, USA, 933–940.
[50]
Sven Stork, Karl Naden, Joshua Sunshine, Manuel Mohr, Alcides Fonseca, Paulo Marques, and Jonathan Aldrich. 2014. Æminium: A Permission-Based Concurrent-by-Default Programming Language Approach. ACM Trans. Program. Lang. Syst. 36, 1 (March 2014), 2:1–2:42.
[51]
The Rust Project Developers. 2011. Documentation of the Std::Sync Rust Module. https://doc.rust- lang.org/std/sync/
[52]
Carlos Varela and Gul Agha. 2001. Programming Dynamically Reconfigurable Open Systems with SALSA. SIGPLAN Not. 36, 12 (Dec. 2001), 20–34.
[53]
Christoph von Praun, Luis Ceze, and Calin Caşcaval. 2007. Implicit Parallelism with Ordered Transactions. In Proceedings of the 12th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP ’07). ACM, New York, 79–89.
[54]
Adam Welc, Suresh Jagannathan, and Antony Hosking. 2005. Safe Futures for Java. In Proceedings of the 20th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA ’05). ACM, New York, 439–453.
[55]
Akinori Yonezawa, Jean-Pierre Briot, and Etsuya Shibayama. 1986. Object-Oriented Concurrent Programming in ABCL/1. In Conference Proceedings on Object-Oriented Programming Systems, Languages and Applications (OOPSLA ’86). ACM, New York, NY, USA, 258–268.
Index Terms
- Concurrency-aware object-oriented programming with roles
Recommendations
A multi-threaded object-oriented programming model
This paper presents a concurrent object-oriented programming (COOP) model established around concurrent objects which may have a body. Once an object with a body is created, its body begins to run as a separate execution thread of the object. ...
Parallelism in Object-Oriented Languages: A Survey
Fourteen concurrent object-oriented languages are compared in terms of how they deal with communication, synchronization, process management, inheritance, and implementation trade-offs. The ways in which they divide responsibility between the programmer,...
Use concurrent programming models to motivate teaching of programming languages
Undergraduate computer science students typically have only a limited understanding of their favorite languages and no inkling of other programming paradigms. Yet modern programmers typically work with several languages, and the availability of cheap ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2018 Owner/Author.
This work is licensed under a Creative Commons Attribution International 4.0 License.
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 24 October 2018
Published in PACMPL Volume 2, Issue OOPSLA
Check for updates
Badges
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 732Total Downloads
- Downloads (Last 12 months)111
- Downloads (Last 6 weeks)12
Reflects downloads up to 22 Dec 2024
Other Metrics
Citations
Cited By
View all- Ciccozzi FAddazi LAsadollah SLisper BMasud AMubeen S(2023)A Comprehensive Exploration of Languages for Parallel ComputingACM Computing Surveys10.1145/348500855:2(1-39)Online publication date: 31-Mar-2023
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in