Interprocedural Parallelization Using Memory Classification Analysis

This thesis outlines a way of addressing the goal of precise interprocedural analysis, based on a combination of techniques: for representing memory accesses within interprocedural. sections of code, for summarizing dependence information in program contexts, and for testing that dependence. The thesis presents a new technique for summarizing the memory access activity in an arbitrary section of code, called Memory Classification Analysis (MCA), using a precise form for representing memory access patterns, called the Access Region Descriptor (ARD). A new, simple dependence test, the Access Region Test (ART), is also described which uses the summary sets of ARDs produced by MCA. This test is capable of parallelizing loops containing non-affine subscript expressions, such as those found in FFT codes. A unified parallelization framework is described, which combines privatization, reduction and induction analysis. Array references using subscripting arrays, such as are found in sparse codes are precisely representable using ARDs, and can sometimes be parallelized using the parallelization framework. Parallelization conditions are generated at critical points in the analysis when dependence cannot be disproved. These can be used to drive on-demand deeper program analysis. Whatever conditions remain unproven can then be generated as code to be used for runtime dependence testing. Its precise memory access representation makes the ARD useful within algorithms for generating data movement messages.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2015

Author dc:creator

• Hoeflinger, Jay Philip

Contributors dc:contributor

• Padua, David A.

• Computer Science

Language dc:language

eng

Identifier

(MiAaPQ)AAI9912266

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/81925