Practical analyses and transformations for flow-based parallelism

Emerging applications demand new parallel abstractions. Traditional parallel abstractions such as data parallelism and task parallelism, while necessary, do not fully address the needs of today's multi-threaded commercial applications. Emerging applications in the domains of recognition, mining and synthesis (RMS); image and video processing; data warehousing; and automatic financial trading exhibit flow-based forms of parallelism. How can we help developers parallelize their sequential applications to leverage flow-based parallelism? To take advantage of any form of parallelism, developers face two key challenges: analysis and transformation of their code. Both are typically done manually. Unfortunately, manual analysis is error-prone: given a sufficiently large and unfamiliar code base, it is hard for developers to identify code portions that inhibit parallelism, e.g., data races. Additionally, manual transformation is tedious: after analyzing the code to parallelize, developers still have to write repetitive, boilerplate code to initiate and stop the parallel code, e.g., starting and joining threads. This dissertation demonstrates that it is possible to reduce the manual burden of such analyses and transformation through automation. The crux of our solution is an interactive approach based on source-to-source analyses and transformations that target the constructs available in modern flow-based parallel libraries. Evaluation on a representative set of emerging flow-based applications demonstrates that these analyses and transformations are useful and practical. Our approach can successfully parallelize applications from the aforementioned domains with good performance, while remaining fast enough to be used interactively as part of a developer's workflow. Moreover, by engaging the developer, we are able to parallelize more applications than would have been possible through static analysis alone