COMPUTING LINEAR DATA DEPENDENCIES IN NESTED LOOP PROGRAMS

Publisher Website
Google Scholar
Abstract
An important topic in automatically parallelizing nested loop programs (for the implementation on a parallel machine or for the mapping onto VLSI circuits) is the computation of linear data dependencies. Recently, Feautrier has developed an algorithm which is based on the solution of a parametric integer linear program. In this paper another method is presented. This method only works for special cases but it should be simpler and more efficient. Apart of these special cases the extensions suggested in this paper provide a system of fewer inequalities and variables in the general case compared to the original algorithm of Feautrier. The key idea is the solution of a system of linear diophantine equations.

This publication has 0 references indexed in Scilit: