Files in this item



application/pdfMayank.Thesis.pdf (2MB)
PhD Thesis of Mayank AgarwalPDF


Title:Identifying, Quantifying, Extracting and Enhancing Implicit Parallelism
Author(s):Agarwal, Mayank
Doctoral Committee Chair(s):Frank, Matthew I.
Doctoral Committee Member(s):Adve, Sarita V.; Dubey, Pradeep; Torrellas, Josep; Zilles, Craig
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Computer Architecture
Parallel Computing
Implicit Parallelism
Automatic Parallelization
Speculative Parallelization
Control Independence
Critical Path
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.
Issue Date:2009-05-15
Genre:Dissertation / Thesis
Publication Status:unpublished
Peer Reviewed:not peer reviewed
Rights Information:Copyright 2009 Mayank Agarwal
Date Available in IDEALS:2009-09-11

This item appears in the following Collection(s)

Item Statistics