Introduction

Emerging applications in the domains of recognition, mining and synthesis (RMS); image and video processing; data warehousing; and automatic financial trading admit a particular style of parallelism termed flow-based parallelism. Realizing the emergence of flow-based parallelism, parallel libraries such as Groovy's GPars, Intel's TBB Flow Graph and Microsoft's TPL Dataflow have added constructs to help developers exploit flow-based parallelism. However, to reap the benefits of such constructs, developers must first use them. This involves refactoring their existing sequential code to incorporate these constructs -- a manual process that overwhelms even experts. To alleviate this burden, we introduce a set of practical analyses and transformations for flow-based parallelism. We implemented these ideas in our refactoring tool, JFlow. Unlike typical parallelizing compilers that attempt to automate the entire parallelization process, JFLow is meant to be used interactively. JFlow statically analyzes the code. If the analyses conclude it is safe to parallelize, the tool performs the transformation, generating source code that targets the constructs of a parallel library. Even when the analyses conservatively conclude that it is not safe to parallelize, the tool is still useful. It pinpoints and reports the issues. The developer has the opportunity to review the issues, change the code as necessary and reinvoke the tool. Our evaluation on seven applications demonstrates that JFlow can successfully parallelize applications from the aforementioned domains with good performance (offering up to 3.45x speedup on a 4-core machine) and is fast enough to be used interactively as part of a developer's workflow.

Screenshots

JFlow currently supports two transformations. Both are implemented inside the Eclipse IDE.

Extract Nodes

Invert Loop

Publications

Expressing Pipeline Parallelism Using TBB Constructs:A Case Study on What Works and What Doesn’t Workshop on Transitioning to Multicore at SPLASH'11. Available from ACM Digital Library

JFlow: Practical Refactorings for Flow-based Parallelism. Technical Report. Available from https://www.ideals.illinois.edu/handle/2142/44034

Known Limitations

WALA uses SSA for its internal representation. Moreover, it performs some optimizations on the SSA including copy propagation. See this thread on the WALA mailing list for more information. Because of this there is a bug with the way that we are mapping back SSA variables back to local variable names.