IDEALS Home University of Illinois at Urbana-Champaign logo The Alma Mater The Main Quad

Identifying, Quantifying, Extracting and Enhancing Implicit Parallelism

Show full item record

Bookmark or cite this item: http://hdl.handle.net/2142/13735

Files in this item

File Description Format
PDF Mayank.Thesis.pdf (2MB) PhD Thesis of Mayank Agarwal PDF
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
Degree: Ph.D.
Genre: Dissertation
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
Type: Text
Language: English
URI: http://hdl.handle.net/2142/13735
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)

Show full item record

Item Statistics

  • Total Downloads: 283
  • Downloads this Month: 3
  • Downloads Today: 0

Browse

My Account

Information

Access Key