TL;DR
This paper introduces NewAge, a novel hardware prototype that achieves near-linear speedup on multi-core processors by automatically parallelizing sequential programs. Unlike previous approaches that only demonstrated scaling through emulation, NewAge runs natively on x86 hardware and successfully achieves true speedup by predicting future program states and speculatively executing them.
What Problem Does This Paper Address?
The paper tackles the long-standing challenge of automatic parallelization, which is crucial for harnessing the power of multi-core processors, especially as Dennard scaling has ended. While previous work on Automatically Scalable Computation (ASC) showed promise in scaling by modeling program execution and predicting future states, it was limited to software emulation and thus couldn't demonstrate actual speedup. The authors aim to bridge this gap by creating a native hardware implementation of ASC that can achieve real-world performance gains.
Methods
NewAge implements the ASC architecture, which treats program execution as a dynamical system. The core idea is to predict future program states and speculatively execute them on available cores. If the prediction is correct, the main program can "fast-forward" to the completed speculative result, saving time. Key methodological contributions include:
- Recognizer: A subsystem that identifies "recognized instruction pointers" (RIPs) – locations in the program amenable to prediction.
- Machine Learning Models: Two learners are used:
- A neural network for online training (building models and predicting simultaneously).
- An offline-trained collection of decision trees for more robust predictions.
- Cache: A mechanism to store predicted states and their corresponding speculative results. It uses live register contents as a unique fingerprint for efficient lookups, significantly reducing the problem of matching large state vectors.
- Dependency Tracking: Dynamic instrumentation (using Pin) is employed to precisely identify the bits of the program state that are actually depended upon by a speculative computation. This drastically reduces the size of the state space that needs to be predicted.
- Scheduler: Manages the dispatch of speculative tasks to worker processes, ensuring that predictions are made for future timesteps and that workers complete their tasks before the main process reaches those states.
- Pintool: A custom instrumentation tool used with Pin to monitor memory reads/writes and capture register state at the RIP for model building and prediction.
- Scattering and Gathering: Techniques using
ptraceand shared memory to efficiently copy and update process state between the main process and worker processes. - Cache Stitching: An optimization to combine cache entries where the speculated state of one entry matches the predicted state of another, effectively reducing the need for iterated cache lookups.
Datasets
The paper evaluates NewAge on a set of benchmark kernels. These include:
- Kernels from the original ASC paper (e.g.,
collatz,ising). - Kernels written by the authors (e.g.,
3sum,readmap). - Kernels from the PolyBench/C suite (e.g.,
cov,gemm,trmm,syrk,syr2k,2mm,3mm).
The authors note that some PolyBench/C kernels (like warshall, cholesky) were not amenable to speedup due to inaccurate predictions, and others (like gesummv, stencils) had runtimes too small relative to memory size to overcome overheads.
Key Insights and Ideas
- Predictability is Key: Programs are either highly predictable (amenable to ASC) or totally unpredictable (not amenable). There's no middle ground for ASC-like techniques.
- Native Execution Enables Speedup: Moving from emulation to native hardware execution is critical for achieving actual performance gains, not just theoretical scaling.
- Register Fingerprinting is Effective: Using live register contents as a cache key is a surprisingly effective and efficient way to index speculative results, even for complex programs.
- Data Dependency Tracking is Crucial: Precisely identifying the bits that matter for a computation dramatically reduces the state space, making prediction and caching feasible for larger problems.
- Overhead is the Bottleneck: For many programs, speedup is ultimately limited by the overhead of dependency tracking, state manipulation, and the underlying instrumentation (Pin).
- ASC Handles Complex Data Structures: NewAge can parallelize programs with linked data structures that are typically challenging for traditional compiler-based parallelization.
Key Results
- Near-Linear Speedup: NewAge achieves near-linear speedup up to 44 cores for several classes of programs, including computational kernels, map-style programs, and matrix operations.
- High Predictive Accuracy: The machine learning models (especially decision trees) achieve high accuracy in predicting program states.
- Significant State Space Reduction: Data dependency tracking reduces the state space size by orders of magnitude for programs like
gemmandcov. - CPU Efficiency Varies: CPU efficiencies (ratio of uninstrumented to instrumented runtime) range from 10.1% (
gemm) to 65.4% (ising). - Computational Cache Hit Rates: High hit rates (up to 80% for
ising) correlate with speedup, indicating that workers are performing a significant portion of the computation. - Handles Non-Trivial Programs: NewAge successfully parallelizes programs with pointer dereferencing (
ising) and loop-carried dependencies (Listing 1with predictablef(j)).
Limitations and Future Work
- Limitations:
- Unpredictable Programs: Programs with inherently unpredictable behavior (e.g., cryptographic hashes) cannot be parallelized by ASC.
- Large State Spaces & Memory Overhead: Programs with extremely large memory footprints (e.g.,
gemm,cov) suffer from high overheads in gathering, scattering, and cache operations, limiting speedup. - Non-Uniform Breakpoint Distances: In some cases, the varying distances between breakpoints can lead to suboptimal scheduling and wasted worker time.
- Dependency Tracking Overhead: While effective, Pin's overhead is a significant factor limiting overall CPU efficiency.
- Future Work:
- Improving Dependency Tracking Efficiency: Exploring specialized hardware or virtual memory integration to reduce the cost of tracking memory dependencies.
- Minimizing State Space: Further reducing the state space for programs where dependency tracking is insufficient (e.g., accumulators).
- Optimizing State Operations: Improving the performance of scatter, gather, and prediction operations, especially for high-memory kernels.
- More Powerful Learners: Developing more sophisticated machine learning models to handle a wider range of program behaviors.
Summary updated