Identifying, Quantifying, Extracting and Enhancing Implicit Parallelism

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

Agarwal, Mayank

关键词: Computer Architecture;    Parallel Computing;    Implicit Parallelism;    Automatic Parallelization;    Speculative Parallelization;    Control Independence;    Critical Path;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/13735/Mayank.Thesis.pdf?sequence=2&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

The shift of the microprocessor industry towards multicore architectures hasplaced a huge burden on the programmers by requiring explicit parallelizationfor performance. Implicit Parallelization is an alternative that could ease theburden on programmers by parallelizing applications “under the covers” whilemaintaining sequential semantics externally. This thesis develops a novelapproach for thinking about parallelism, by casting the problem ofparallelization in terms of instruction criticality. Using this approach,parallelism in a program region is readily identified when certain conditionsabout fetch-criticality are satisfied by the region. The thesis formalizes thisapproach by developing a criticality-driven model of task-basedparallelization. The model can accurately predict the parallelism that would beexposed by potential task choices by capturing a wide set of sources ofparallelism as well as costs to parallelization.The criticality-driven model enables the development of two key components forImplicit Parallelization: a task selection policy, and a bottleneck analysistool. The task selection policy can partition a single-threaded program intotasks that will profitably execute concurrently on a multicore architecture inspite of the costs associated with enforcing data-dependences and withtask-related actions. The bottleneck analysis tool gives feedback to theprogrammers about data-dependences that limit parallelism. In particular, thereare several “accidental dependences” that can be easily removed with largeimprovements in parallelism. These tools combine into a systematic methodologyfor performance tuning in Implicit Parallelization. Finally, armed with thecriticality-driven model, the thesis revisits several architectural designdecisions, and finds several encouraging ways forward to increase the scope ofImplicit Parallelization.