Subdomain dependence test for massive parallelism

Abstract

The authors present a new dependence test which can detect disjoint regions of an iteration space. The test therefore reports accurate dependences for a class of conditional statements. The proposed algorithm can discover large-scale parallelism in cases where previous decision algorithms fail. The methods and algorithms for solving the subdomain dependence test are described. Also considered is the application of the subdomain dependence test to the problem of 'dependence cycle breaking' and the use of the subdomain dependence test in analyzing functional programs. >