Identifying, Quantifying, Extracting and Enhancing Implicit Parallelism

Agarwal, Mayank

Permalink

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

Description

Title

Identifying, Quantifying, Extracting and Enhancing Implicit Parallelism

Author(s)

Agarwal, Mayank

Issue Date

2009-05-15

Doctoral Committee Chair(s)

Frank, Matthew I.

Committee Member(s)

• Adve, Sarita V.
• Dubey, Pradeep
• Torrellas, Josep
• Zilles, Craig

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)

• Computer Architecture
• Parallel Computing
• Implicit Parallelism
• Automatic Parallelization
• Speculative Parallelization
• Control Independence
• Critical Path

Language

en

Abstract

The shift of the microprocessor industry towards multicore architectures has placed a huge burden on the programmers by requiring explicit parallelization for performance. Implicit Parallelization is an alternative that could ease the burden on programmers by parallelizing applications “under the covers” while maintaining sequential semantics externally. This thesis develops a novel approach for thinking about parallelism, by casting the problem of parallelization in terms of instruction criticality. Using this approach, parallelism in a program region is readily identified when certain conditions about fetch-criticality are satisfied by the region. The thesis formalizes this approach by developing a criticality-driven model of task-based parallelization. The model can accurately predict the parallelism that would be exposed by potential task choices by capturing a wide set of sources of parallelism as well as costs to parallelization. The criticality-driven model enables the development of two key components for Implicit Parallelization: a task selection policy, and a bottleneck analysis tool. The task selection policy can partition a single-threaded program into tasks that will profitably execute concurrently on a multicore architecture in spite of the costs associated with enforcing data-dependences and with task-related actions. The bottleneck analysis tool gives feedback to the programmers about data-dependences that limit parallelism. In particular, there are several “accidental dependences” that can be easily removed with large improvements in parallelism. These tools combine into a systematic methodology for performance tuning in Implicit Parallelization. Finally, armed with the criticality-driven model, the thesis revisits several architectural design decisions, and finds several encouraging ways forward to increase the scope of Implicit Parallelization.

Type of Resource

text

Permalink

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

Copyright and License Information

Copyright 2009 Mayank Agarwal

Owning Collections