Back to the Futures: Incremental Parallelization of Existing Sequential Runtime Systems

Many language implementations, particularly for high-level and scripting languages, are based on carefully honed run-time 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. The authors describe an alternative approach to incremental parallelization of run-time systems. This approach can be applied inexpensively to many sequential run-time systems, and they demonstrate its effectiveness in the Racket run-time system and Parrot virtual machine.