Intraprocedural and interprocedural data dependence analysis for parallel computing
Li, Zhiyuan
This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/20688
Description
Title
Intraprocedural and interprocedural data dependence analysis for parallel computing
Author(s)
Li, Zhiyuan
Issue Date
1989
Doctoral Committee Chair(s)
Yew, Pen-Chung
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Computer Science
Language
eng
Abstract
A parallelizing compiler relies on data dependence analysis to detect independent operations in a user's program. In scientific and engineering programs, it is important for the compiler to analyze data dependences involving array references. This dissertation addresses a few fundamental issues in such an analysis.
The first part of the dissertation discusses algorithms for data dependence tests. A real-valued algorithm ($\lambda$-test) is proposed for testing dependences between multi-dimensional array references, since previous algorithms are either too time-consuming or too imprecise. Algorithms for an unconstrained integer test and an exact integer test are also presented for some common classes of array references. In order to evaluate the complexity of array references and data dependences in real programs, an empirical study was conducted, and some of its results are presented.
The second part of the dissertation is devoted to interprocedural analysis for parallel computing. The key to successful parallelization of programs which contain procedure calls is an efficient and accurate interprocedural data dependence analysis. A scheme, called the atom image scheme, is proposed for this analysis. Unlike previous approaches, the atom image scheme preserves precise array reference details while allowing recursive calls to be analyzed. Further, its precise form for representing the subscript details allows flexibility in selecting various data dependence test algorithms, depending on their usage. Such flexibility is important to the accuracy and efficiency of data dependence analysis.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
