Reversing the iteration dimensions

[SamirDroubi]

In some problems, you want to reverse the direction in which you iterate over a dimension.

For example, the natural starting algorithm of an algorithm that operate on the upper triangular part of a matrix is to iterate in the following way:

---------
| ----->|
|  ---->|
|   --->|
|    -->|
|     ->|
--------

However, as you schedule you want the tail to be at the diagonal rather than at the right side of the matrix; I can provide more context why is that if necessary. So, you will want to reverse the direction of the iteration dimensions over the rows:

---------
| <-----|
|  <----|
|   <---|
|    <--|
|     <-|
--------

Supporting that will require a new primitive that performs the following transformation:

@sched_op([ForCursorA])
def reverse_loop(proc, loop):
     """
     for i in seq(lo, hi):
          s
          ->
          s [i -> hi - (i - lo) - 1]
     """

As a sanity check: revese_loop(reverse_loop(proc, loop), loop) would give us hi - ((hi - (i - lo) - 1) - lo) - 1 = hi - hi + i - lo + 1 + lo - 1 = i

There is a question of what analysis might be necessary to support this. A simple over-approximation would be to reuse the same analysis for parallelizing a loop then write a more specific analysis later on when the analysis gets revamped.

[yamaguchi1024]

Loop carry dependency analysis will be necessary to support this, this is a good motivating example for the value sensitive analysis

[gilbo]

Yes, the value sensitive analysis will be important in many cases. However consider a trivially independent loop, such as adding two vectors. What analysis is necessary to allow for this?One simple safety criterion is that all individual loop iterations should pairwise commute. How should we pose such a query?Similar to reordering loops, we want to consider two copies of the body effect each substituted or bound with a different copy of the loop iteration variable i. Call these i1 and i2. Under the assumption that i1 ≠ i2, we want to show these commute. By symmetry we can strengthen this precondition to i1 < i2.Does this make sense?On Jan 20, 2024, at 12:33 PM, Yuka Ikarashi @.***> wrote: Loop carry dependency analysis will be necessary to support this, this is a good motivating example for the value sensitive analysis

—Reply to this email directly, view it on GitHub, or unsubscribe.You are receiving this because you are subscribed to this thread.Message ID: @.***>