Empirical study on array subscripts and data dependencies

Zhiyu Shen, Zhiyuan Li, Pen Chung Yew

Research output: Contribution to journalConference articlepeer-review

45 Scopus citations

Abstract

Results from an empirical study on array subscripts and data dependencies are reported. The state of the art in data dependence analysis and some parallel execution techniques are also examined. It is found that many subscripts contain symbolic terms with unknown values. A few methods to determine their values at compile time are evaluated. Arrays with coupled subscripts appear quite frequently. It may be necessary that all array dimensions be handled simultaneously in a dependence test, rather than just handling them separately as in current test algorithms. Nonzero coefficients of loop indices in most subscripts are found to be simple: they are either 1 or -1. This allows an exact real-valued test for one-dimensional or two-dimensional arrays. Dependencies with nonconstant distance are found to be rather common. This might have a significant impact on data synchronization, loop scheduling, and partitioning.

Original languageEnglish (US)
Pages (from-to)145-152
Number of pages8
JournalProceedings of the International Conference on Parallel Processing
Volume2
StatePublished - Dec 1 1989
EventProceedings of the 1989 International Conference on Parallel Processing - University Park, PA, USA
Duration: Aug 8 1989Aug 12 1989

Fingerprint

Dive into the research topics of 'Empirical study on array subscripts and data dependencies'. Together they form a unique fingerprint.

Cite this