Ehrhart polynomials and maximum parallelism

The parametric vertices finding program tells that the parametric vertices are divided in two sets of occuring vertices depending on two validity domains of the parameters values. Hence, par(n, t) is also defined on two validity domains as Ehrhart polynomials in n and t.

According to results due to Eugčne Ehrhart and to our calculation method which is fully detailed in our papers and research reports, the following answers are computed:

For all 0 <= t <= n, the number of simultaneous calculations at instant t is given by the Ehrhart polynomial:

par(n, t) = 1/8 t^2 + [1/2, 3/4] t + [3/8, 1]
where [1/2, 3/4] = 1/2 if t mod 2 = 1 and [1/2, 3/4] = 3/4 otherwise.
For all n <= t <= 2n, the number of simultaneous calculations at instant t is given by the Ehrhart polynomial:

par(n, t) = n t - 1/2 n^2 + 1/2 n - 3/8 t^2 + [0, 1/4] t - [3/8, 1]

From these results, the maximum parallelism is deduced:

On the first validity domain (0 <= t <= n), par(n, t) is maximum when t is maximum, i.e. when t = n. Hence,

maxpar(n) = 1/8 n^2 + [1/2, 3/4] n + [3/8, 1]
On the second validity domain (n <= t <= 2n), we take the derivative of par(n, t) with respect to t: par'(n, t) = n - 3/4 t + [0, 1/4]. Hence, par(n, t) increases from t = n to t = (4 n - [0, 1]) / 3, and then decreases until t = 2 n: it is maximum for t = tmax = (4 n - [0, 1]) / 3. Since tmax is not always integral, a case study is necessary to get the exact value of maxpar(n) = par(n, tmax), checking the possible values of floor(tmax) and ceiling(tmax). It yields the following answer:

maxpar(n) = 1/6 n^2 + 5/6 n + [1, 23/24, 1]
In conclusion, the maximum parallelism of the loop nest is:

Forall n >= 0, maxpar(n) = 1/6 n^2 + 5/6 n + [1, 23/24, 1]

Previous page: The parametric vertices