how do I permute this loop nest in ISL?

[R Raman]

Hi there!

I am trying to learn how to do some loop permutations.

I understand how to do this transformation (from the Banerjee book Example3.8.)

This looks like a pretty good example for me to get started in the ISL methods to do the same thing - but the manual looks daunting -

do I1 = 1,100

  do I2 = I1+1, 199

     do I3 = I2, I1+I2

        H(I1, I2, I3)

     enddo

  enddo

enddo

Permute such that I3-loop becomes outermost loop and I2-loop becomes innermost loop.  After the transformation, the new index variables (counted from outermost loop inward) would be K1, K2, K3

(K1, K2, K3) = (I3, I2, I1).

Basically in the example they go on to apply Fourier elimination method to obtain a range for K1 between two constants, a range for K2 between two functions based on K1, and finally for K3 based on two functions on K1 and K2.

I think we need to represent the input I1, I2, I3 constraints as a set. Then I need to map this set to (K1, K2, K3) after rewriting the input constraints based on (K1, K2, K3) = (I3, I2, I1). After that there needs to be a call to map_apply_range? Any help?!

Best,

Ram

[Michael Kruse]

I write prototype code which does this transformation, which might be useful:

https://github.com/SOLLVE/llvm-project/blob/pragma-clang-loop/polly/lib/Transform/ScheduleOptimizer.cpp#L3056

Michael

> --
>
> ---
> You received this message because you are subscribed to the Google Groups "isl Development" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to isl-developme...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/isl-development/13e0d542-adac-41aa-b371-2380c79c08e0%40googlegroups.com.



--
Tardyzentrismus verboten!

[Sven Verdoolaege]

If you're learning how to work with isl, it's probably best to start out
with an interactive environment such as the iscc tool that comes with barvinok.
Here's your permutation:

codegen { H[I1=1:100,I2=I1+1:199,I3=I2:I1+I2] -> [I3,I2,I1] };
for (int c0 = 2; c0 <= 299; c0 += 1)
for (int c1 = max(c0 - 100, c0 / 2 + 1); c1 <= min(199, c0); c1 += 1)
for (int c2 = max(1, c0 - c1); c2 <= min(100, c1 - 1); c2 += 1)
H(c2, c1, c0);

skimo

[R Raman]

Awesome! thanks for your help- I will check out iscc

[Pei Mu]

Hi Ram!

I'm learning the polyhedral compilation and isl too, recently.

> I understand how to do this transformation (from the Banerjee book Example3.8.)

> 

> This looks like a pretty good example for me to get started in the ISL methods to do the same thing - but the manual looks daunting -  

The manual looks daunting to me too. Could you please share the Banerjee book's full name?

By the way, how's your learning about isl? Is there any suggestion or guide to a freshman?

Thanks!

[R Raman]

Hi,

Loop transformations for restructuring compilers: The Foundations by Utpal Banerjee, 1993.

Perhaps good one for getting to know things - and to try out Fourier Motzkin using the included C code in the appendix. Another book would be the race car book by M. Wolfe.

It may be better to follow up on the advice given here, which is playing with an "interactive environment such as the iscc tool that comes with barvinok". 

Best wishes and stay safe,

Ram 

--

---
You received this message because you are subscribed to a topic in the Google Groups "isl Development" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/isl-development/zTO4OAhuqJg/unsubscribe.
To unsubscribe from this group and all its topics, send an email to isl-developme...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/isl-development/2633dea1-3d98-498c-91fb-3638609eb0f3n%40googlegroups.com.

[Pei Mu]

Thanks a lot!

[R Raman]

I am not sure if this is the correct place to ask this question - but given the group member's expertise: 

From what I understand we would be able to do tiling for loops like in gemm using the pluto algorithm- Are there ILP methods to figure out what tile sizes would need to be for a certain architecture? Also, are there methods to figure out best tiling for loops that take in account communication from earlier operations? Suppose K dimension can be done fully due to availability of memory vs partially because reader is starved if need to wait fully - Please let me know if there are papers on these topics.

To view this discussion on the web visit https://groups.google.com/d/msgid/isl-development/84f2a7bb-e93a-466e-bced-cdebe8a42573n%40googlegroups.com.

[Sven Verdoolaege]

On Mon, Aug 23, 2021 at 01:02:11PM -0400, R Raman wrote:
> I am not sure if this is the correct place to ask this question - but given
> the group member's expertise:

You could try polyhedra...@listes.ens-lyon.fr
although I haven't seen a lot of traffic there lately (or ever, really) or
use google.

If you write to the mailing list, it will probably help
if you use a subject line that matches the contents.

skimo