Paraphrasing: Generating Parallel Programs Using Refactoring

Christopher Brown, Kevin Hammond, Marco Danelutto, Peter Kilpatrick, Holger Schöner, Tino BreddinFMCO 2011 · DOI

TL;DR

This paper introduces PARAPHRASE, a novel refactoring tool designed to automatically transform sequential programs into efficient parallel implementations. By leveraging a system of formal pattern rewrite rules, PARAPHRASE aims to significantly improve the programmability of parallel systems, making parallel programming more accessible to both experts and novices.

What Problem Does This Paper Address?

The increasing prevalence of multi-core and many-core processors means that parallel programming is no longer a niche concern but a necessity for modern software development. However, developing parallel programs is notoriously difficult, often requiring deep expertise in parallel programming models and low-level communication primitives like MPI. This complexity leads to programs that are hard to write, debug, and maintain. The paper addresses the challenge of making parallel programming more accessible and efficient by proposing a refactoring-based approach. Instead of manually implementing complex parallel skeletons, programmers can use PARAPHRASE to automatically introduce these structures into their existing sequential code, focusing on the core business logic.

Methods

The core of PARAPHRASE is a refactoring engine that operates on a unified Abstract Syntax Tree (AST) representation of programs. The process involves:

  1. Parsing and Semantic Analysis: Source code (initially C/C++ and Erlang) is parsed into an AST, and static semantic information (like variable bindings and types) is extracted. This is crucial for understanding the program's structure.
  2. Unified AST: The ASTs from different languages are transformed into a unified AST that can represent concepts across various paradigms.
  3. Component AST: This unified AST is further transformed into a component AST, which highlights high-level constructs suitable for parallel patterns. These constructs are often identified as software components.
  4. Pattern-Based Refactoring: The component AST is then refactored using a set of well-defined transformation rules that correspond to parallel patterns (e.g., Task Farm, Pipeline, Map-Reduce). These rules are expressed in a high-level abstract language, independent of specific syntax.
  5. Pretty-Printing: The refactored component AST is converted back into the source syntax, aiming to preserve original layout and comments for a seamless developer experience.

The system is designed to be extensible through an API, allowing users to define new patterns and refactorings.

Datasets

Not discussed in the paper. The paper focuses on demonstrating the refactoring process with examples in C, C++, and Erlang, rather than on training or evaluating against specific datasets.

Key Insights and Ideas

  • Refactoring as a Bridge to Parallelism: The paper convincingly argues that refactoring, traditionally used for improving sequential code design, can be a powerful mechanism for introducing parallelism. This shifts the focus from manual implementation of parallel constructs to automated transformation.
  • Pattern-Based Refactoring: The core innovation is the use of formal, pattern-based rewrite rules to drive the refactoring process. This allows for a systematic and generalizable approach to introducing parallel skeletons like Task Farms and Map-Reduce.
  • Abstraction Over Syntax: By using a unified AST and a pattern language independent of specific syntax, PARAPHRASE aims for generality across different programming languages and paradigms (imperative vs. functional).
  • Automating Boilerplate: A significant benefit highlighted is the automation of boilerplate code (e.g., MPI calls, synchronization, communication setup) that is often tedious and error-prone in manual parallel programming. This frees up developers to concentrate on algorithm design.
  • Flexibility in Parallel Patterns: The refactoring approach allows for easy switching between different parallel patterns (e.g., Farm vs. Map), enabling exploration of optimal solutions for specific architectures and program structures.

Key Results

The paper demonstrates the effectiveness of the PARAPHRASE approach through several examples:

  • C Task Farm: A sequential C program is refactored into an MPI-based Task Farm, automatically generating significant boilerplate code for communication and synchronization.
  • Erlang Task Farm: An equivalent refactoring is shown for Erlang, highlighting the applicability of the approach to functional languages.
  • Matrix Factorization: A more complex use case involving large-scale matrix factorization is presented. The paper shows how a sequential version can be refactored first into a Farm pattern for parallel SGD computations, and then further refactored to use a Map pattern, demonstrating the ability to switch between parallel patterns.

While quantitative speedup results are not the primary focus, the paper emphasizes the substantial reduction in manual effort and the potential for improved program structure and maintainability.

Limitations and Future Work

  • User Extensibility: While the tool is designed to be user-extensible, the full extent of this extensibility and the ease of defining new patterns and rules require further investigation.
  • Automatic Component Identification: The paper mentions that high-level constructs are typically expressed as software components, which might be identified automatically. The effectiveness and robustness of this automatic identification are not fully detailed.
  • Non-Functional Properties: The paper acknowledges the need to specify and verify non-functional properties (like performance) of refactored systems, which is an area for future work.
  • Side-Effect Free Code: The refactoring of functions that are not yet side-effect free is mentioned as a desirable future extension.
  • Integration with Editing Environments: The plan to integrate the tool with popular editors (Emacs, Eclipse) is noted, but the current status and user experience of such integration are not detailed.
  • New Identifier Conflicts: The paper mentions that checks for new identifier conflicts are performed, but the complexity and handling of such conflicts in large codebases might be a challenge.

Future work will involve further investigation into the automatic performance analysis, the integration with IDEs, and the handling of more complex refactorings and non-functional requirements.

Summary updated

BibTeX
@inproceedings{brown2011paraphrasing,
  author = {Christopher Brown and Kevin Hammond and Marco Danelutto and Peter Kilpatrick and Holger Schöner and Tino Breddin},
  title = {{Paraphrasing: Generating Parallel Programs Using Refactoring}},
  booktitle = {FMCO},
  year = {2011},
  doi = {10.1007/978-3-642-35887-6\_13},
}
Figure