Files in this item



application/pdf9912266.pdf (6MB)Restricted to U of Illinois
(no description provided)PDF


Title:Interprocedural Parallelization Using Memory Classification Analysis
Author(s):Hoeflinger, Jay Philip
Doctoral Committee Chair(s):Padua, David A.
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Computer Science
Abstract: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.
Issue Date:1998
Description:140 p.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1998.
Other Identifier(s):(MiAaPQ)AAI9912266
Date Available in IDEALS:2015-09-25
Date Deposited:1998

This item appears in the following Collection(s)

Item Statistics