ylfink@water.waterloo.edu (ylfink) (02/07/89)
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
PARALLEL COMPUTATIONS SEMINAR
- Thursday, February 9, 1989
Dr. Zhiyuan Li, University of Illinois, Urbana-
Champagne, will speak on ``Intraprocedural and
Interprocedural Data Dependence Analysis for Parallel
Computing''.
TIME: 3:30 PM
ROOM: DC 1304
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. We address a few
fundamental issues in such analysis.
First, we present a powerful algorithm (lambda-test)
for testing dependences between multi-dimensional array
references. Previous algorithms are either too time-
consuming or too imprecise. Second, we discuss an
efficient and precise scheme for interprocedural data
dependence analysis which is important for programs
with procedure calls. Our scheme uses a compact and
precise data structure (called atom images) to
propagate array information between procedures. It
allows flexibility in selecting various data dependence
test algorithms depending on their usage. Further, it
can handle recursive procedure calls. In contrast,
other schemes do not allow recursive calls and they
tend to lose information thus are restricted to certain
less accurate or less efficient testing algorithms. We
give results from experiments with Parafrase, a
sophisticated parallelizing compiler developed in
University of Illinois at Urbana-Champaign.