Rapid Parallelization by Collaboration

Lakshminarasimhan Sethumadhavan, Gail E. KaiserColumbia 2009 · DOI

TL;DR

This paper introduces COMPASS, a novel system that leverages the "wisdom of crowds" to help programmers parallelize their code for multi-core processors. By collecting and synthesizing expertise from experienced programmers, COMPASS aims to simplify the transition to parallel programming, making it faster and more accessible.

What Problem Does This Paper Address?

The widespread adoption of multi-core processors has created a pressing need for parallelizing software to maintain performance gains. However, the complexity and diversity of hardware architectures and software environments make effective parallelization a significant challenge for many programmers. Traditional approaches often require extensive training, specialized knowledge, or are limited in their applicability. This leaves many developers struggling to adapt their existing codebases, leading to performance bottlenecks and a delayed transition to the concurrency era. The paper highlights the difficulty for programmers like "Jo" to navigate the landscape of parallelization techniques, languages, and tools, often facing the "unknown unknown" problem where they don't know what they don't know.

Methods

COMPASS employs a collaborative, human-centered approach to parallelization advice. Its core components include:

  • Watcher: Observes and records how experienced programmers ("gurus") optimize their code, capturing the changes made.
  • Data Store: A centralized database that stores these optimizations as "signatures" (representing code segments and their parallelized versions).
  • Matcher: Identifies critical code regions in a learner's program and queries the data store for relevant optimizations.
  • Generator: Creates a "sketch" – a stylized outline of the parallelized code – tailored to the learner's specific code and environment.

A key innovation is the Segment Dependence Graph (SDG), a program abstraction that represents code segments and their dependencies. Unlike traditional Program Dependence Graphs (PDGs), SDGs use dynamic measurements to annotate edges, providing higher specificity and avoiding ambiguity issues. This allows for more precise matching of code segments.

The system also incorporates a "code rank" metric to prioritize advice, considering structural similarity, dependence annotation similarity, and the perceived importance of the optimization (based on user feedback and adoption).

Datasets

Not discussed in the paper. The paper focuses on the system's architecture and methodology, with the database being populated by user-contributed optimizations.

Key Insights and Ideas

  • Leveraging "Wisdom of Crowds": The paper argues that collective human intelligence, as seen in wikis, can be effectively applied to complex technical domains like parallelization.
  • "Push" vs. "Pull" Systems: COMPASS shifts from traditional "pull" systems (where users search for information) to a "push" system that proactively offers advice, addressing the "unknown unknown" problem.
  • SDGs for Specificity: The introduction of Segment Dependence Graphs with dynamic annotations is crucial for achieving high specificity in matching code segments, overcoming limitations of static analysis.
  • Tailored Advice: COMPASS aims to provide advice that is not only relevant but also customized to the user's specific code and execution environment.
  • Scalability through Hotspots: By focusing on "hot" code regions (those consuming most execution time), COMPASS can analyze large codebases more effectively than traditional methods.

Key Results

The paper describes the system's architecture and proposed use cases, but does not present quantitative results from a deployed system. It outlines how specificity, scalability, and universality will be measured in future evaluations. The paper mentions that a manual optimization of a code snippet for Inverse Discrete Cosine Transform using SSE instructions resulted in a 2x to 3x speedup, and COMPASS aims to capture and disseminate such optimizations.

Limitations and Future Work

  • Initial Database Population: The system relies on an initial set of "gurus" to populate the database. The quality and diversity of this initial data are critical.
  • Trustworthiness of Gurus: The paper acknowledges that some guru contributions might not be optimal or trustworthy, necessitating a ranking mechanism.
  • Ambiguous Syntactic Information: Converting SDGs back into code sketches can be challenging due to the loss of syntactic information. Inferring this information accurately is an ongoing area of work.
  • Scalability of Graph Matching: While SDGs help, graph isomorphism checks can still be computationally expensive, requiring efficient pre-filtering and ranking mechanisms.
  • Future Work: The authors plan to seed the database with more hand-coded optimizations, build more sophisticated database schemas, and open the system for trial release. They also envision future applications like a "marketplace for program optimizations" and a "programming utopia" where complex applications can be assembled through queries.

Summary updated

Abstract

The widespread adoption of Chip Multiprocessors has renewed the emphasis on the use of parallelism to improve performance. The present and growing diversity in hardware architectures and software environments, however, continues to pose difficulties in the effective use of parallelism thus delaying a quick and smooth transition to the concurrency era. In this document, we describe the research being conducted at the Computer Science Department at Columbia University on a system called COMPASS that aims to simplify this transition by providing advice to programmers considering parallelizing their code. The advice proffered to the programmer is based on the wisdom collected from programmers who have already parallelized some code. The utility of COMPASS rests, not only on its ability to collect the wisdom unintrusively but also on its ability to automatically seek, find and synthesize this wisdom into advice that is tailored to the code the user is considering parallelizing and to the environment in which the optimized program will execute in. COMPASS provides a platform and an extensible framework for sharing human expertise about code parallelization -- widely and on diverse hardware and software. By leveraging the "Wisdom of Crowds" model which has been conjunctured to scale exponentially and which has successfully worked for Wikis, COMPASS aims to enable rapid parallelization of code and thus continue to extend the benefits for Moore's law scaling to science and society.
BibTeX
@inproceedings{sethumadhavan2009rapid,
  author = {Lakshminarasimhan Sethumadhavan and Gail E. Kaiser},
  title = {{Rapid Parallelization by Collaboration}},
  booktitle = {Columbia},
  year = {2009},
  doi = {10.7916/d88p67dz},
}
Figure