Dear Jakub and all,
When handling loop nests whose loop bounds are linearly depending on
outer loop iterators and size parameters, it is known that the number of
iterations is a specific kind of polynomial of the size parameters, also
called an Ehrhart polynomial.
I have recently published a paper at IPDPS 2017 where the collapsing of
non-rectangular parallel loops is solved by inverting Ehrhart
polynomials. Benchmarks using OpenMP are exhibited. It uses floating
point computations to compute roots of such polynomials which are then
evaluated once per thread when running the parallel loop which results
from non-rectangular collapsed loops, in order for each thread to start
with correct iterators values.
The necessary computations can be handled with ISL, but an additional
computer algebra system is required to solve polynomial equations (I use
Maxima).
Please have a look at the IPDPS paper, freely available here:
https://www.researchgate.net/publication/317369488_Automatic_Collapsing_of_Non-Rectangular_Loops
Ehrhart polynomials for parametrized loop trip counts have been
introduced in this paper:
https://www.researchgate.net/publication/221235615_Counting_Solutions_to_Linear_and_Nonlinear_Constraints_Through_Ehrhart_Polynomials_Applications_to_Analyze_and_Transform_Scientific_Programs
I would be happy to discuss this topic.
Best regards,
Philippe
