Practical analyses and transformations for flow-based parallelism

Chen, Nicholas Chun Y.

Permalink

https://hdl.handle.net/2142/45453 Copy

Description

Title

Practical analyses and transformations for flow-based parallelism

Author(s)

Chen, Nicholas Chun Y.

Issue Date

2013-08-22T16:40:36Z

Director of Research (if dissertation) or Advisor (if thesis)

Johnson, Ralph E.

Doctoral Committee Chair(s)

Johnson, Ralph E.

Committee Member(s)

• Agha, Gul A.
• Marinov, Darko
• Voss, Michael J.

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• parallelism
• flow-based parallelism
• refactoring
• static analysis
• interactive tool

Abstract

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.

Graduation Semester

2013-08

Permalink

http://hdl.handle.net/2142/45453

Copyright and License Information

Copyright 2013 Nicholas Chun Y Chen

Owning Collections