The Jrpm system for dynamically parallelizing Java programs

Michael K. Chen, Kunle OlukotunACM SIGARCH Computer Architecture News 2003 · DOI

TL;DR

This paper introduces Jrpm, a system that automatically parallelizes sequential Java programs using thread-level speculation (TLS) on chip multiprocessors (CMPs). By combining dynamic compilation, hardware profiling, and TLS, Jrpm identifies and parallelizes suitable loops with minimal programmer intervention, achieving significant speedups on multi-core processors.

What Problem Does This Paper Address?

As instruction-level parallelism (ILP) reaches its limits, the focus shifts to coarser-grained parallelism. However, traditional multiprocessors struggle with fine-grained thread-level parallelism (TLP) due to high inter-processor communication costs. Existing parallelizing compilers face challenges with complex program structures like irregular memory accesses and dynamic control flow, often leading to conservative synchronization that hinders performance. This paper addresses the need for a system that can automatically exploit TLP in general-purpose programs, specifically Java, without requiring extensive programmer effort or complex static analysis.

Methods

Jrpm employs a multi-pronged approach:

  • Chip Multiprocessor (CMP) with Thread-Level Speculation (TLS): Jrpm leverages the Hydra CMP, which offers low inter-processor communication costs. TLS allows optimistic parallel execution, where threads run in parallel and correctness is guaranteed by hardware mechanisms that ensure sequential memory ordering.
  • Hardware Profiler (TEST): The Tracer for Extracting Speculative Threads (TEST) is a hardware profiler that analyzes program execution in real-time. It estimates dynamic dependency behavior, thread size, and buffering requirements to identify the most promising loops for parallelization.
  • Java Virtual Machine (JVM) with Dynamic Compilation: Jrpm uses a JVM with a dynamic compiler (microJIT) to abstract away hardware details and allow for on-the-fly recompilation of identified parallel loops into speculative threads. This approach avoids modifying source code.
  • Compiler Optimizations: Jrpm's microJIT compiler performs several optimizations specifically for speculative execution, including:
  • Loop invariant register allocation: Preserves loop invariants across thread restarts.
  • Non-communicating loop inductors: Manages loop induction variables efficiently without explicit communication.
  • Reset-able non-communicating loop inductors: Handles unpredictable inductor values.
  • Thread synchronizing lock: Uses a special non-violating load instruction to manage frequent inter-thread dependencies.
  • Reduction operator optimization: Transforms reduction operations to avoid inter-thread dependencies.
  • Multilevel STL decompositions: Handles nested loops by dynamically switching between outer and inner loop speculation.
  • Hoisted startup and shutdown routines: Reduces overhead for frequently entered STLs.

Datasets

The paper evaluates Jrpm using a suite of benchmarks including applications from jBYTEmark, SPECjvm98, and Java Grande benchmarks, as well as real-world applications found on the internet. Specific benchmarks mentioned include: Assignment, BitOps, compress, db, deltaBlue, EmFloatPnt, Huffman, IDEA, jess, jLex, MipsSimulator, monte Carlo, NumHeapSort, raytrace, euler, fft, LuFactor, moldyn, NeuralNet, shallow, decJpeg, encJpeg, h263dec, mpeg Video, and mp3.

Key Insights and Ideas

  • TLS as a Game Changer for Fine-Grained Parallelism: The paper strongly advocates for TLS as a key enabler for exploiting fine-grained TLP, which was previously impractical due to synchronization overheads.
  • Dynamic Analysis is Crucial for General Programs: Static analysis alone is insufficient for complex Java programs. Jrpm's reliance on real-time hardware profiling (TEST) to identify parallel regions is a critical insight.
  • Hardware-Software Co-design for Automatic Parallelization: The synergy between the Hydra CMP's TLS support, the TEST profiler, and the dynamic JVM compiler is what makes automatic parallelization feasible.
  • Optimizations Tailored for Speculative Execution: The paper highlights that standard compiler optimizations are not enough; specialized techniques are needed to mitigate the overheads and potential issues arising from speculative execution (e.g., handling register state after violations).
  • Minimal Programmer Effort is Achievable: The system demonstrates that significant speedups can be obtained with little to no explicit programmer intervention, making parallel programming more accessible.

Key Results

  • Speedups: On a 4-processor CMP, Jrpm achieved speedups of:
  • 3x to 4x for floating-point applications.
  • 2x to 3x for multimedia applications.
  • 1.5x to 2.5x for integer applications.
  • Profiling Overhead: The TEST profiling system incurred minimal slowdowns, typically around 7.8%, with only a few applications experiencing higher overheads.
  • Optimization Impact: Various compiler optimizations significantly improved performance, with VM modifications (parallelizing memory allocation and removing synchronized object locks) showing a substantial impact.
  • Data Set Sensitivity: The paper notes that for some applications, the optimal thread decompositions can change based on input data set sizes, suggesting the need for adaptive strategies.

Limitations and Future Work

  • Limitations:
    • System Calls: Programs with system calls in critical code sections cannot be parallelized speculatively by Jrpm.
  • Loop Characteristics: Some loops were too large or executed too few iterations for effective speculation. Serializing dependencies within critical STLs also posed challenges.
  • Buffer Overflow Prediction: While TEST accounts for buffer overflows, its predictions might underestimate the impact of frequent overflows due to averaging effects.
  • Load Imbalance: Speculative execution can lead to load imbalance, where processors wait for preceding threads to commit, which is not fully accounted for in performance prediction.
  • Dynamic Violations: Some benchmarks exhibit dynamic violations that are difficult to mitigate even with synchronization or value prediction.
  • Future Work:
    • More Applications: Testing Jrpm on a wider range of applications.
  • Profiling Granularity: Investigating the minimum amount of profiling data required for effective recompilation.
  • Advanced Optimizations: Developing new techniques to further improve performance for applications with high dynamic violation frequencies.
  • Adaptive Strategies: Exploring ways to adapt to changing input data set sizes and their impact on decomposition selection.

Summary updated

Abstract

We describe the Java runtime parallelizing machine (Jrpm), a complete system for parallelizing sequential programs automatically. Jrpm is based on a chip multiprocessor (CMP) with thread-level speculation (TLS) support. CMPs have low sharing and communication costs relative to traditional multiprocessors, and thread-level speculation (TLS) simplifies program parallelization by allowing us to parallelize optimistically without violating correct sequential program behavior. Using a Java virtual machine with dynamic compilation support coupled with a hardware profiler, speculative buffer requirements and inter-thread dependencies of prospective speculative thread loops (STLs) are analyzed in real-time to identify the best loops to parallelize. Once sufficient data has been collected to make a reasonable decision, selected loops are dynamically recompiled to run in parallel.Experimental results demonstrate that Jrpm can exploit thread-level parallelism with minimal effort from the programmer. On four processors, we achieved speedups of 3 to 4 for floating point applications, 2 to 3 on multimedia applications, and between 1.5 and 2.5 on integer applications. Performance was achieved by automatic selection of thread decompositions by the hardware profiler, intra-procedural optimizations on code compiled dynamically into speculative threads, and some minor programmer transformations for exposing parallelism that cannot be performed automatically.
BibTeX
@inproceedings{chen2003jrpm,
  author = {Michael K. Chen and Kunle Olukotun},
  title = {{The Jrpm system for dynamically parallelizing Java programs}},
  booktitle = {ACM SIGARCH Computer Architecture News},
  year = {2003},
  doi = {10.1145/871656.859668},
}
Figure