DOJ: Dynamically parallelizing object-oriented programs

We present Dynamic Out-of-Order Java (DOJ), a dynamic paral-lelization approach. In DOJ, a developer annotates code blocks as tasks to decouple these blocks from the parent execution thread. The DOJ compiler then analyzes the code to generate heap exam-iners that ensure the parallel execution preserves the behavior of the original sequential program. Heap examiners dynamically ex-tract heap dependences between code blocks and determine when it is safe to execute a code block. Previous work on Out-of-Order Java used static analysis to allow code blocks to possibly execute out of order, similar to instructions in a super scalar processor. DOJ elides much of the complex and expensive static analysis in Out-of-Order Java. We have implemented DOJ and evaluated it on twelve bench-marks. We achieved an average compilation speedup of 31.15× over OoOJava and an average execution speedup of 12.73 × over sequential versions of the benchmarks