Parallelizing Parallel Programs: A Dynamic Pattern Analysis for Modernization of Legacy Parallel Code

Parallelization traditionally refers to the challenge of analyzing legacy sequential code, to generate equivalent, higher performing parallel code. Emerging mainstream parallelism has created a new challenge: legacy parallel code, typically hand-optimized for a particular system, becomes outdated as the hardware evolves. Modernizing such code line-by-line is not effective: instead we need to understand the program’s overall algorithmic intent, to re-express it for the new target. Re-expression can be simplified and futureproofed by coding with parallel patterns [4, 8, 9]. We address the remaining challenge of identifying the algorithm patterns in the original parallel source. We describe a novel dynamic approach to the identification of implicit algorithmic patterns. Our core principle is that the essence of a pattern is to be found in the dynamic data flows it invokes between operations and their repetition, rather than any specific source level encoding. This makes it neutral with respect to source code and hence immediately applicable to both legacy sequential and parallel code.
The high level structure of our approach is captured in Figure 1. Our LLVM pass instruments the legacy program, whose traced execution generates a dynamic dataflow graph (DDG). Our constraint-programming based pattern finding tool analyzes the DDG against a library of pattern definitions, reporting found instances back to the programmer.