Geometric Techniques for Parallelizing and Scheduling Fortran Do-loops

Parallel Processing Research

Geometric Techniques for Parallelizing and
Scheduling Fortran Do-loops 

In Proc. 7th Internationale Conference on Parallel and
Distribuited Computing Systems,
Las Vegas, October 1994

Author(s)
DonXing Tang, Gopal Gupta

Abstract
To parallelize a DO-loop in a Fortran program, the independence of various iterations of the DO-loop has to be detected. Two commonly used tests to check for iteration independence are the GCD and the Banerjee test. In this paper we introduce a new data dependence test called the Diagonal test that is based on some very simple geometric properties of straight lines and hyper-planes. We show that the Diagonal test is equivalent to Banerjee test. However, the Diagonal test is more intuitive, especially for singly-nested loops. The Diagonal test also inspires a new approach to parallelizing DO-loops by repeatedly partitioning a loop into smaller loops, and scheduling these smaller loops for parallel execution based on the data-dependence analysis.

The whole paper

can be downloaded from our

server.


 Parallel Proc. Page   Research Page   Lab Home Page