TL;DR
This paper introduces "split annotations" (SAs), a novel technique that allows for significant performance improvements in data-intensive applications by optimizing data movement and parallelization across existing, unmodified library functions. By simply annotating functions and providing a small API for data partitioning, developers can achieve speedups of up to 15x without rewriting their libraries, often outperforming compiler-based solutions.
What Problem Does This Paper Address?
Modern computing is increasingly bottlenecked by the slow movement of data between the CPU and main memory, a problem that has grown much faster than improvements in computational throughput. While techniques like loop fusion, often implemented through compilers and intermediate representations (IRs), can address this by optimizing data flow across functions, they typically require intrusive changes to the underlying libraries themselves. This often means library developers must rewrite their functions using a new IR or adapt their code to a specific compiler's API, which is a significant burden and hinders adoption. The paper aims to bridge this gap by enabling these powerful data movement optimizations without requiring any modifications to the original library code.
Methods
The core innovation is split annotations (SAs). An SA is a declaration that tells a runtime how to split and merge data arguments for a specific function. This involves two key components:
- Split Types: These define how a data type can be partitioned (e.g., an array split into smaller chunks, a matrix split by rows or columns). They are parameterized to handle variations like array size or matrix dimensions.
- Splitting API: Annotators implement this API to provide concrete logic for how to split data into smaller pieces and how to merge these pieces back together after processing.
These SAs are used by the Mozart system, which consists of:
- Mozart Client Libraries (C++ and Python): These libraries transparently capture a dataflow graph of annotated function calls at runtime. They use techniques like wrapper functions and memory protection to intercept operations without modifying the original library code.
- Mozart Runtime: This component takes the captured dataflow graph and uses the SAs to create an execution plan. It then splits data, pipelines functions, and parallelizes execution across threads, all while respecting the correctness constraints defined by the split types.
Datasets
The paper evaluates its approach on a suite of 15 data analytics workloads. These include benchmarks from the Weld evaluation, numerical analysis workloads (Shallow Water), image processing workloads using ImageMagick, and a part-of-speech tagging workload using spaCy. Specific libraries used include NumPy, Pandas, spaCy, Intel MKL, and ImageMagick. No new benchmarks were introduced; instead, existing, representative workloads were used to demonstrate the generality of SAs.
Key Insights and Ideas
- Decoupling Optimization from Library Implementation: The most significant insight is that powerful data movement optimizations can be achieved externally to libraries, without requiring developers to rewrite their carefully hand-tuned code. This dramatically lowers the barrier to entry for performance optimization.
- Pipelining is King: The paper strongly emphasizes that data movement, not just parallelization, is the primary bottleneck. By enabling efficient pipelining of data across functions, Mozart significantly reduces memory traffic and improves cache utilization.
- Generics and Unknown Types for Flexibility: The introduction of generics and "unknown" split types allows SAs to handle a wide range of functions, including those with dynamic output shapes or those that operate on data in ways not easily predictable at compile time, making the approach more robust.
- Leveraging Existing Hand-Optimized Code: A key advantage of SAs is their ability to work with existing, highly optimized library functions. This allows them to outperform compiler-based approaches that might generate less efficient code for certain operations.
Key Results
- Significant Speedups: Mozart achieves speedups of up to 15x over single-threaded libraries and up to 4.7x over libraries that are already parallelized.
- Competitive with Compilers: Mozart's performance is competitive with, and in some cases (up to 2x better), outperforms compiler-based solutions that require function rewrites (e.g., Weld, Bohrium).
- Reduced Integration Effort: Integrating SAs required up to 17x less code compared to compiler-based approaches like Weld for similar performance gains.
- Scalability: Mozart demonstrates good scalability, with performance improvements increasing with the number of threads up to 16.
- Low Overheads: System overheads (client library, memory protection, planning) accounted for less than 0.5% of the total running time in most workloads.
Limitations and Future Work
- Side-Effect-Free Functions: SAs are currently limited to side-effect-free functions. Functions that modify global state or hold locks cannot be safely annotated.
- Unsupported Functions: A small number of functions in each library could not be annotated due to complex boundary conditions or non-standard processing (e.g., image blurring with edge effects). Annotators currently need to manually determine function compatibility.
- Formal Verification: The authors suggest that tools to formally prove the compatibility of functions with SAs would be beneficial.
- Memory Protection Overhead: While generally low, memory protection overhead can be significant for tasks with very little computation. The authors mention that newer system calls (pkeys) could further reduce this.
- Dynamic Work-Stealing: While Mozart uses static parallelism, the authors note that dynamic work-stealing schedulers are compatible and could be explored.
Summary updated