More Web Proxy on the site http://driver.im/

research-article

Back to the futures: incremental parallelization of existing sequential runtime systems

Authors:

Robert Bruce Findler,

Matthew FlattAuthors Info & Claims

OOPSLA '10: Proceedings of the ACM international conference on Object oriented programming systems languages and applications

Pages 583 - 597

https://doi.org/10.1145/1869459.1869507

Published: 17 October 2010 Publication History

Abstract

Many language implementations, particularly for high-level and scripting languages, are based on carefully honed runtime systems that have an internally sequential execution model. Adding support for parallelism in the usual form -- as threads that run arbitrary code in parallel -- would require a major revision or even a rewrite to add safe and efficient locking and communication. We describe an alternative approach to incremental parallelization of runtime systems. This approach can be applied inexpensively to many sequential runtime systems, and we demonstrate its effectiveness in the Racket runtime system and Parrot virtual machine. Our evaluation assesses both the performance benefits and the developer effort needed to implement our approach. We find that incremental parallelization can provide useful, scalable parallelism on commodity multicore processors at a fraction of the effort required to implement conventional parallel threads.

References

[1]

}}Python design note on threads, 2008. http: //www.python.org/doc/faq/library/ #can-t-we-get-rid-of-the-global-interpreter-lock.

[2]

}}ALLEN, E., CHASE, D., HALLETT, J., LUCHANGCO, V., MAESSEN, J., AND STEELE, G. The Fortress language spec- ification. http://research.sun.com/projects/plrg/ fortress.pdf, 2005.

[3]

}}ARMSTRONG, J. A history of Erlang. In HOPL III: Pro- ceedings of the third ACM SIGPLAN conference on History of programming languages (2007), pp. 6--1--6--26.

Digital Library

[4]

}}BAILEY, D., BARTON, J., LASINSKI, T., AND SIMON, H. The NAS parallel benchmarks.Tech. Rep. RNR-91-002, NASA Ames Research Center, August 1991.

[5]

}}BLELLOCH, G. Implementation of a portable nested data- parallel language. Proceedings of the Fourth ACM SIGPLAN Symposium on Principles and Practice of Parallel Program- ming (1993), 102--111.

Digital Library

[6]

}}BLUMOFE, R., JOERG, C., KUSZMAUL, B., LEISERSON, C., RANDALL, K., AND ZHOU, Y. Cilk: An efficient mul- tithreaded runtime system. ACM SIGPLAN Notices (1995), 207--216.

Digital Library

[7]

}}BOURGOIN, M., JONQUET, A., CHAILLOUX, E., CANOU, B., AND WANG, P. OCaml4Multicore, 2007. http://www. algo-prog.info/ocmc/web/.

[8]

}}CHAKRAVARTY, M. T., LESHCHINSKIY, R., JONES, S. P., KELLER, G., AND MARLOW, S. Data Parallel Haskell: A status report. Proceedings of the 2007 Workshop on Declara- tive Aspects of Multicore Programming (2007), 10--18.

Digital Library

[9]

}}CHAMBERLAIN, B. L., CALLAHAN, D., AND ZIMA, H. P. Parallel programming and the Chapel language. International Journal of High Performance Computing Applications (Au- gust 2007), 291--312.

Digital Library

[10]

}}CHARLES, P., GROTHOFF, C., SARASWAT, V., DONAWA, C., KIELSTRA, A., EBCIOGLU, K., VON PRAUN, C., AND SARKER, V.X10: An object-oriented approach to non- uniform cluster computing. Proceedings of the 20th Annual ACM SIGPLAN Conference on Object-Oriented Program- ming, Systems, Languages, and Applications (2005), 519-- 538.

Digital Library

[11]

}}FLUET, M., RAINEY, M., REPPY, J., SHAW, A., AND XIAO, Y. Manticore: A heterogeneous parallel language. Proceed- ings of the 2007 Workshop on Declarative Aspects of Multi- core Programming (2007), 37--44.

Digital Library

[12]

}}FRUMKIN, M., SCHULTZ, M., JIN, H., AND YAN, J. Im- plementation of NAS parallel benchmarks in Java.Tech. Rep. NAS-02-009, Ames Research Center, Moffett Field, CA, USA, 2002.

[13]

}}HALSTEAD, JR., R. H. MULTILISP: A language for concur- rent symbolic computation. ACM Transactions on Program- ming Languages and Systems (TOPLAS) (October 1985), 501--538.

Digital Library

[14]

}}JONES, S., GORDON, A., AND FINNE, S.Concurrent Haskell. Conference Record of the 23rd ACM SIGPLAN- SIGACT Symposium on Principles of Programming Lan- guages (POPL '96) (January 1996), 295--308.

Digital Library

[15]

}}JUSZCZAK, C. Fast mergesort implementation based on half- copying merge algorithm, 2007. http://kicia.ift.uni. wroc.pl/algorytmy/mergesortpaper.pdf.

[16]

}}Thread state and the global interpreter lock. http://docs.python.org/c-api/init.html# thread-state-and-the-global-interpreter-lock, March 2010.

Cited By

MOY CFELLEISEN M(2023)Trace contractsJournal of Functional Programming10.1017/S095679682300009633Online publication date: 13-Dec-2023
https://doi.org/10.1017/S0956796823000096
Sivaramakrishnan KDolan SWhite LJaffer SKelly TSahoo AParimala SDhiman AMadhavapeddy A(2020)Retrofitting parallelism onto OCamlProceedings of the ACM on Programming Languages10.1145/34089954:ICFP(1-30)Online publication date: 3-Aug-2020
https://dl.acm.org/doi/10.1145/3408995
Meier RGross TMarr SFumero J(2019)Reflections on the compatibility, performance, and scalability of parallel PythonProceedings of the 15th ACM SIGPLAN International Symposium on Dynamic Languages10.1145/3359619.3359747(91-103)Online publication date: 20-Oct-2019
https://dl.acm.org/doi/10.1145/3359619.3359747
Show More Cited By

Index Terms

Back to the futures: incremental parallelization of existing sequential runtime systems
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
      1. Runtime environments

Recommendations

Back to the futures: incremental parallelization of existing sequential runtime systems
OOPSLA '10

Many language implementations, particularly for high-level and scripting languages, are based on carefully honed runtime systems that have an internally sequential execution model. Adding support for parallelism in the usual form -- as threads that run ...
Bulk synchronous parallel ML with exceptions

Bulk Synchronous Parallel ML is a high-level language for programming parallel algorithms. Built upon OCaml and using the BSP model, it provides a safe setting for their implementation, avoiding concurrency related problems (deadlocks, indeterminism). ...
Seeing the futures: profiling shared-memory parallel racket
FHPC '12: Proceedings of the 1st ACM SIGPLAN workshop on Functional high-performance computing

This paper presents the latest chapter in our adventures coping with a large, sequentially-tuned, legacy runtime system in today's parallel world. Specifically, this paper introduces our new graphical visualizer that helps programmers understand how to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

OOPSLA '10: Proceedings of the ACM international conference on Object oriented programming systems languages and applications

October 2010

984 pages

ISBN:9781450302036

DOI:10.1145/1869459

General Chairs:
William R. Cook
University of Texas at Austin
,
Siobhán Clarke
Trinity College Dublin
,
Program Chairs:
Martin Rinard
MIT
,
Kevin J. Sullivan
University of Virginia
,
Daniel H. Steinberg
Dim Sum Thinking Inc.

ACM SIGPLAN Notices Volume 45, Issue 10
OOPSLA '10
October 2010
957 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1932682
Issue’s Table of Contents

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 October 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SPLASH '10

Sponsor:

SIGPLAN

SPLASH '10: Systems Programming Languages and Applications: Software for Humanity

October 17 - 21, 2010

Nevada, Reno/Tahoe, USA

Acceptance Rates

Overall Acceptance Rate 268 of 1,244 submissions, 22%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
355
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)1

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

MOY CFELLEISEN M(2023)Trace contractsJournal of Functional Programming10.1017/S095679682300009633Online publication date: 13-Dec-2023
https://doi.org/10.1017/S0956796823000096
Sivaramakrishnan KDolan SWhite LJaffer SKelly TSahoo AParimala SDhiman AMadhavapeddy A(2020)Retrofitting parallelism onto OCamlProceedings of the ACM on Programming Languages10.1145/34089954:ICFP(1-30)Online publication date: 3-Aug-2020
https://dl.acm.org/doi/10.1145/3408995
Meier RGross TMarr SFumero J(2019)Reflections on the compatibility, performance, and scalability of parallel PythonProceedings of the 15th ACM SIGPLAN International Symposium on Dynamic Languages10.1145/3359619.3359747(91-103)Online publication date: 20-Oct-2019
https://dl.acm.org/doi/10.1145/3359619.3359747
Meier RRigo AGross T(2018)Virtual machine design for parallel dynamic programming languagesProceedings of the ACM on Programming Languages10.1145/32764792:OOPSLA(1-25)Online publication date: 24-Oct-2018
https://dl.acm.org/doi/10.1145/3276479
Daloze BTal AMarr SMössenböck HPetrank E(2018)Parallelization of dynamic languages: synchronizing built-in collectionsProceedings of the ACM on Programming Languages10.1145/32764782:OOPSLA(1-30)Online publication date: 24-Oct-2018
https://dl.acm.org/doi/10.1145/3276478
Hale KDinda P(2018)An Evaluation of Asynchronous Software Events on Modern Hardware2018 IEEE 26th International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS)10.1109/MASCOTS.2018.00041(355-368)Online publication date: Sep-2018
https://doi.org/10.1109/MASCOTS.2018.00041
Hale KHetland CDinda P(2017)Multiverse: Easy Conversion of Runtime Systems into OS Kernels via Automatic Hybridization2017 IEEE International Conference on Autonomic Computing (ICAC)10.1109/ICAC.2017.24(177-186)Online publication date: Jul-2017
https://doi.org/10.1109/ICAC.2017.24
Surendran RSarkar V(2016)Automatic parallelization of pure method calls via conditional future synthesisACM SIGPLAN Notices10.1145/3022671.298403551:10(20-38)Online publication date: 19-Oct-2016
https://dl.acm.org/doi/10.1145/3022671.2984035
Hale KDinda P(2016)Enabling Hybrid Parallel Runtimes Through Kernel and Virtualization SupportACM SIGPLAN Notices10.1145/3007611.289225551:7(161-175)Online publication date: 25-Mar-2016
https://dl.acm.org/doi/10.1145/3007611.2892255
Surendran RSarkar VVisser ESmaragdakis Y(2016)Automatic parallelization of pure method calls via conditional future synthesisProceedings of the 2016 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications10.1145/2983990.2984035(20-38)Online publication date: 19-Oct-2016
https://dl.acm.org/doi/10.1145/2983990.2984035
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents