Document Open Access Logo

Transactional Tasks: Parallelism in Software Transactions

Authors Janwillem Swalens, Joeri De Koster, Wolfgang De Meuter

PDF
Thumbnail PDF

File

LIPIcs.ECOOP.2016.23.pdf
  • Filesize: 0.93 MB
  • 28 pages

Document Identifiers

Author Details

Janwillem Swalens
Joeri De Koster
Wolfgang De Meuter

Cite As Get BibTex

Janwillem Swalens, Joeri De Koster, and Wolfgang De Meuter. Transactional Tasks: Parallelism in Software Transactions. In 30th European Conference on Object-Oriented Programming (ECOOP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 56, pp. 23:1-23:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ECOOP.2016.23

Abstract

Many programming languages, such as Clojure, Scala, and Haskell, support different concurrency models.
In practice these models are often combined, however the semantics of the combinations are not always well-defined.
In this paper, we study the combination of futures and Software Transactional Memory.
Currently, futures created within a transaction cannot access the transactional state safely, violating the serializability of the transactions and leading to undesired behavior.

We define transactional tasks: a construct that allows futures to be created in transactions.
Transactional tasks allow the parallelism in a transaction to be exploited, while providing safe access to the state of their encapsulating transaction.
We show that transactional tasks have several useful properties: they are coordinated, they maintain serializability, and they do not introduce non-determinism.
As such, transactional tasks combine futures and Software Transactional Memory, allowing the potential parallelism of a program to be fully exploited, while preserving the properties of the separate models where possible.

Subject Classification

Keywords
  • Concurrency
  • Parallelism
  • Futures
  • Threads
  • Fork/Join
  • Software Transactional Memory

Metrics

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

Supplementary Materials

References

  1. K. Agrawal, J. T. Fineman, and J. Sukha. Nested Parallelism in Transactional Memory. In PPoPP, 2008. Google Scholar
  2. W. Baek, N. Bronson, C. Kozyrakis, and K. Olukotun. Implementing and evaluating nested parallel transactions in software transactional memory. In SPAA, 2010. Google Scholar
  3. H. C. Baker and C. Hewitt. The incremental garbage collection of processes. In Symposium on Artificial Intelligence and Programming Languages, pages 55-59, 1977. Google Scholar
  4. J. Barreto, A. Dragojević, P. Ferreira, R. Guerraoui, and M. Kapałka. Leveraging parallel nesting in transactional memory. In PPoPP, 2010. Google Scholar
  5. C. Beeri, P. A. Bernstein, and N. Goodman. A model for concurrency in nested transactions systems. Journal of the ACM, 36(2):230-269, 1989. Google Scholar
  6. P. A. Bernstein and N. Goodman. Concurrency Control in Distributed Database Systems. ACM Computing Surveys, 13(2):185-221, 1981. Google Scholar
  7. G. E. Blelloch, P. B. Gibbons, and Y. Matias. Provably efficient scheduling for languages with fine-grained parallelism. Journal of the ACM, 46(2):281-321, 1999. Google Scholar
  8. R. D. Blumofe, C. F. Joerg, B. C. Kuszmaul, C. E. Leiserson, K. H. Randall, and Y. Zhou. Cilk: An Efficient Multithreaded Runtime System. In PPoPP, 1995. Google Scholar
  9. S. Burckhardt, A. Baldassin, and D. Leijen. Concurrent programming with revisions and isolation types. In OOPSLA, 2010. Google Scholar
  10. S. Burckhardt and D. Leijen. Semantics of Concurrent Revisions. In ESOP, 2011. Google Scholar
  11. D. M. Chickering, D. Heckerman, and C. Meek. A Bayesian approach to learning Bayesian networks with local structure. In UAI, 1997. Google Scholar
  12. M. Felleisen, R. B. Findler, and M. Flatt. Semantics Engineering with PLT Redex. The MIT Press, 2009. Google Scholar
  13. C. Flanagan and M. Felleisen. The Semantics of Future and Its Use in Program Optimizations. In POPL, 1995. Google Scholar
  14. R. Guerraoui, M. Kapałka, and J. Vitek. STMBench7: A Benchmark for Software Transactional Memory. In European Conference on Computer Systems, 2007. Google Scholar
  15. N. Haines, D. Kindred, J. G. Morrisett, S. M. Nettles, and J. M. Wing. Composing first-class transactions. ACM Transactions on Programming Languages and Systems, 16(6):1719-1736, 1994. Google Scholar
  16. R. H. Halstead. MULTILISP: a language for concurrent symbolic computation. ACM Transactions on Programming Languages and Systems, 7(4):501-538, 1985. Google Scholar
  17. T. Harris, S. Marlow, S. Peyton-Jones, and M. Herlihy. Composable memory transactions. In PPoPP, 2005. Google Scholar
  18. M. Herlihy and J. E. B. Moss. Transactional Memory: Architectural Support for Lock-Free Data Structures. ACM SIGARCH Computer Architecture News, 21:289-300, 1993. Google Scholar
  19. S. Imam and V. Sarkar. Cooperative Scheduling of Parallel Tasks with General Synchronization Patterns. In ECOOP, 2014. Google Scholar
  20. C. Y. Lee. An algorithm for path connections and its applications. IRE Transactions on Electronic Computers, EC-10(3):346-365, 1961. Google Scholar
  21. C. C. Minh, J. Chung, C. Kozyrakis, and K. Olukotun. STAMP: Stanford Transactional Applications for Multi-Processing. In Symposium on Workload Characterization, 2008. Google Scholar
  22. K. F. Moore and D. Grossman. High-level small-step operational semantics for transactions. In POPL, 2008. Google Scholar
  23. J. E. B. Moss. Nested Transactions: An Approach to Reliable Distributed Computing. PhD thesis, Massachusetts Institute of Technology, 1981. Google Scholar
  24. J. E. B. Moss and A. L. Hosking. Nested transactional memory: Model and architecture sketches. Science of Computer Programming, 63(2):186-201, 2006. Google Scholar
  25. Y. Ni, V. S. Menon, A. Adl-Tabatabai, A. L. Hosking, R. L. Hudson, J. E. B. Moss, B. Saha, and T. Shpeisman. Open nesting in software transactional memory. In PPoPP, 2007. Google Scholar
  26. N. Shavit and D. Touitou. Software transactional memory. Distributed Computing, 10(2):99-116, 1997. Google Scholar
  27. S. Tasharofi, P. Dinges, and R. E. Johnson. Why Do Scala Developers Mix the Actor Model with Other Concurrency Models? In ECOOP, 2013. Google Scholar
  28. J. Vitek, S. Jagannathan, A. Welc, and A. L. Hosking. A Semantic Framework for Designer Transactions. In ESOP, 2004. Google Scholar
  29. H. Volos, A. Welc, A. Adl-Tabatabai, T. Shpeisman, X. Tian, and R. Narayanaswamy. NePaLTM: Design and Implementation of Nested Parallelism for Transactional Memory Systems. In ECOOP, 2009. Google Scholar
  30. A. Warth, Y. Ohshima, T. Kaehler, and A. Kay. Worlds: Controlling the Scope of Side Effects. In ECOOP, 2011. Google Scholar
  31. I. Watson, C. Kirkham, and M. Lujan. A Study of a Transactional Parallel Routing Algorithm. In PACT, 2007. Google Scholar
  32. A. Welc, S. Jagannathan, and A. Hosking. Safe futures for Java. In OOPSLA, 2005. Google Scholar
  33. Y. Zhang and E. A. Hansen. Parallel Breadth-First Heuristic Search on a Shared-Memory Architecture. In Heuristic Search, Memory-Based Heuristics and Their Applications, 2006. Google Scholar
  34. J. Zhao, R. Lublinerman, Z. Budimlić, S. Chaudhuri, and V. Sarkar. Isolation for nested task parallelism. In OOPSLA, 2013. 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 About DROPS Imprint Privacy Contact