While parallel processing provides an opportunity for continued growth in mainstream computational power, it also requires that programs be built to use multiple threads of execution. The process of writing parallel programs is acknowledged as requiring a significant level of skill beyond general programming, relegating parallel programming to a small class of expert programmers. The difficulty of parallel programming is only compounded when attempting to modify an existing program. Given that the vast majority of existing programs have not been written to use parallelism, a significant amount of code could benefit from an overhaul.
An alternative to explicitly encoding parallelism into a program is to use speculative parallelism of some form. Speculative parallelism removes the burden of guaranteeing the independence of parallel threads of execution, which greatly simplifies the process of parallel program development. This is especially true when retrofitting existing programs because the programmer is less likely to have a complete understanding of the code base.
In many cases, the safety of the parallelism can be speculative. There also cases in which it makes sense to parallelize tasks that are inherently speculative. One may wish to speculate about the result of some computation, on the safety of applying an optimization, or on the best heuristics to use when searching for a solution. This style is speculative parallelism is referred to as speculative optimization.
In this work I describe a speculative parallelism system based on POSIX processes and communication. The system is comprised of a set of run-time libraries and compiler support for easily generating a speculatively parallel program. The implementation is designed to be general and portable, and the programming interface is designed to minimize the programmer effort needed to effectively parallelism a program. There are two variants on the run-time system intended for different forms of parallelism. Both of these general forms of speculative parallelism are generally applicable to many different problems.