Problem description

Let us consider the following loop nest:

for i := 0 to n do
  for j := 0 to i do
    for k := 0 to i-j do
      statement(s)

Assume that the dependence analysis of this loop yields an optimal linear time-schedule defined by t(i, j, k) = i + j + k: any iteration (i, j, k) is computed at instant i + j + k.

We use our method to determine the parametric number of simultaneous calculations par(n, t) occuring at any instant t, in order to determine the parametric maximum parallelism maxpar(n) = MAX_t {par(n, t)}, i.e. the maximum number of simultaneous calculations.

Next page: The parametric vertices