COMPGROUPS.NET | Search | Post Question | Groups | Stream | About | Register

### Examples of loop skewing, or polytope model?

• Email
• Follow

```   I've been trying to write up the Wikipedia article on the "polytope
model" (which I believe is the same thing as "loop skewing"?),
http://en.wikipedia.org/wiki/Polytope_model
and I'm looking for a good example of where it could be useful.

The page
http://www.infosun.fmi.uni-passau.de/cl/loopo/doc/loopo_doc/node3.html
gives the following example:

for i := 0 to n do
for j := 0 to i+2 do
A(i, j) := A(i-1, j) + A(i, j-1)
end
end

which can be transformed via the method into a similar loop nest in which
the inner loop's iterations can be run in parallel.

But this seems to me like a silly example, because I can't see any
practical application for that particular calculation. So I'm looking
for an example that's more realistic, while still being simple enough
for a relative beginner to comprehend. And preferably in two dimensions,
so it can be shown in the diagrammatic form used in that tutorial above.

The requirements are basically that you have nested loops, and the
calculation in the inner loop depends on earlier calculations that also
happen to be "physically" to one side of the current array index, as
if the calculation is proceeding in a wave across the array.

Successive over-relaxation
http://www.damtp.cam.ac.uk/lab/people/sd/lectures/nummeth98/pdes.htm
#L_4_Successive_Over_Relaxation_SOR_
might be relevant, but since its dependencies "point both ways" in
the diagram, I don't see how to apply the polytope method to it.

Any help?

-Arthur
```
 0
Reply ajonospam (382) 12/12/2006 8:59:56 PM

See related articles to this posting

```Arthur J. O'Dwyer wrote:
> I've been trying to write up the Wikipedia article on the "polytope
> model" (which I believe is the same thing as "loop skewing"?),
> http://en.wikipedia.org/wiki/Polytope_model
> and I'm looking for a good example of where it could be useful.

Since no one else has answered I'll take a stab.

(Do any present-day compilers really
make this complicated general transform?
I suppose modeling of physical systems
(nuclear reactors, atmosphere, etc.) is where
the applications are, but my experience is
more in image manipulation.)

What you're looking for is a "causal" or
"anti-causal" multi-dimensional filter which
operates in-place (source same as destination).
"Causal" implies signal values must be used
only *after* they're changed; anti-causal implies
they must be used only *before* change;
but for Arthur's purpose I think these two
cases can be treated as equivalent (!), e.g.
by reversing a loop control
for (x = Min; x <= Max; x++)
to be
for (x = Max; x >= Min; x--)

Two examples of Causal in-place filters would be
* error diffusion for dithering, e.g. the
Floyd-Steinberg algorithm.
* codec using quantized prediction error.

When you examine the details of Floyd-Steinberg,
you see that separate processors will be updating
the same signal value concurrently:
Arr[i][j] += Foo1;
Arr[i][j] += Foo2;
This would work *provided* the read-modify-writes
are made atomic *and* the compiler is smart enough
to understand that associativity and commutativity
principles allow the updates to occur in any order.

The codec using quantized prediction error
may be a better example for you, but is perhaps
too complicated for your purpose, and yet would
still be too simple to be a realistic
compression method.

Since no better causal filter examples come to mind,
let's consider anti-causal filters....

A finite-support filter can be made in-place and
anti-causal by shifting the data during processing.
For example, a 7x7 sharpening filter might be written

/* change 3 to 6 for 2-pass filters */
char	Image[HEI+3][WID+3];

for (x...) for (y...)
Image[x-3][y-3] = Convolution at x,y...;

This might be a good simple example for your purpose.
(Even when memory is plentiful, the forgoing in-place
loop might be preferred to separate buffers in
order to improve cache utilization.)

James Dow Allen

```
 0
Reply jdallen2000 (495) 12/14/2006 8:44:42 AM

```On Thu, 14 Dec 2006, James Dow Allen wrote:
> Arthur J. O'Dwyer wrote:
>> I've been trying to write up the Wikipedia article on the "polytope
>> model" (which I believe is the same thing as "loop skewing"?),
>> http://en.wikipedia.org/wiki/Polytope_model
>> and I'm looking for a good example of where it could be useful.
>
> Since no one else has answered I'll take a stab.
>
> (Do any present-day compilers really
> make this complicated general transform?
> I suppose modeling of physical systems
> (nuclear reactors, atmosphere, etc.) is where
> the applications are, but my experience is
> more in image manipulation.)

I have no idea, but from my reading I gather that it's more of a
theoretical thing. Certainly I don't think any general-purpose compilers
do it --- and for good reason, since, as I found out, it's really hard
to come up with a case in which it's even possible to do it! :)
But then, if anyone did it, it would have to be in Fortran, because
C has too many aliasing issues. And I don't know anything about Fortran
compilers.

> What you're looking for is a "causal" or
> "anti-causal" multi-dimensional filter which
> operates in-place (source same as destination).
> "Causal" implies signal values must be used
> only *after* they're changed; anti-causal implies
> they must be used only *before* change;
> but for Arthur's purpose I think these two
> cases can be treated as equivalent (!), e.g.
> by reversing a loop control
>     for (x = Min; x <= Max; x++)
> to be
>     for (x = Max; x >= Min; x--)

I'm not sure I understand that paragraph; if I do understand it, I
think it's wrong. (This is the first time I've heard the terms "causal"
and "anti-causal" in this context, so I could easily be wrong.) If a
filter is "anti-causal", that means no "new" values depend on other
"new" values, right? in which case it would normally be implemented
not-in-place, and could be done all in parallel, without needing any
clever optimizations. True?
I also don't think reversing the direction of a loop would change
an anti-causal filter into a causal version of the /same/ filter. It
might give you a causal filter, but if that new filter didn't do
something useful, it wouldn't... well, it wouldn't be very useful. :)

> Two examples of Causal in-place filters would be
> * error diffusion for dithering, e.g. the
>     Floyd-Steinberg algorithm.
> * codec using quantized prediction error.

Aha! Thanks. I now remember that I had thought about texture synthesis
http://graphics.stanford.edu/projects/texture/
as an example, but discarded it as too complicated, both because of the
number of "inputs" to each cell's new value, and because of the complexity
of the actual function computed on each cell.
Floyd-Steinberg dithering has exactly the same "inputs" structure, but
a much simpler actual function. If I get the time soon, I'll try to play
around with it to get fewer than four "inputs" (well, they're "outputs"
in the traditional algorithm, but I don't think that's a problem). Or
even better, I'll see whether anyone else has already done that research!

> The codec using quantized prediction error
> may be a better example for you, but is perhaps
> too complicated for your purpose, and yet would
> still be too simple to be a realistic
> compression method.

Haven't heard of that one. I'll look it up.

> Since no better causal filter examples come to mind,
> let's consider anti-causal filters....
>
> A finite-support filter can be made in-place and
> anti-causal by shifting the data during processing.
> For example, a 7x7 sharpening filter might be written
>
> /* change 3 to 6 for 2-pass filters */
> char	Image[HEI+3][WID+3];
>
>         for (x...) for (y...)
>             Image[x-3][y-3] = Convolution at x,y...;
>
> This might be a good simple example for your purpose.

But how would loop skewing apply to that loop?

Thanks much,
-Arthur
```
 0
Reply ajonospam (382) 12/14/2006 7:10:14 PM

```On Thu, 14 Dec 2006, Arthur J. O'Dwyer wrote:
> On Thu, 14 Dec 2006, James Dow Allen wrote:
>> Arthur J. O'Dwyer wrote:
>>> I've been trying to write up the Wikipedia article on the "polytope
>>> model" (which I believe is the same thing as "loop skewing"?),
>>> http://en.wikipedia.org/wiki/Polytope_model
>>> and I'm looking for a good example of where it could be useful.
>>
>> Since no one else has answered I'll take a stab.
[...]
>> * error diffusion for dithering, e.g. the
>>     Floyd-Steinberg algorithm.
>> * codec using quantized prediction error.
>
>  Aha! Thanks. I now remember that I had thought about texture synthesis
> http://graphics.stanford.edu/projects/texture/
> as an example, but discarded it as too complicated, both because of the
> number of "inputs" to each cell's new value, and because of the complexity
> of the actual function computed on each cell.
>  Floyd-Steinberg dithering has exactly the same "inputs" structure, but
> a much simpler actual function. If I get the time soon, I'll try to play
> around with it to get fewer than four "inputs" (well, they're "outputs"
> in the traditional algorithm, but I don't think that's a problem). Or
> even better, I'll see whether anyone else has already done that research!

Turns out they have, thank goodness. The file
http://www.efg2.com/Lab/Library/ImageProcessing/DHALF.TXT
has a lot of good historical information on Floyd-Steinberg variations.

So I took the simplest of those dithering algorithms (three inputs to
each cell); "inverted" it so that each loop iteration read four cells
and wrote one, instead of reading one and writing four; and then spent
a lot of time debugging. (This is one optimization I'm happy to leave
to the compilers, because I obviously can't do it right!) The Wikipedia
article is finished now, and has even prettier pictures than the tutorial
I was originally working from. Anyone who's interested...
http://en.wikipedia.org/wiki/Polytope_model

-Arthur
```
 0
Reply ajonospam (382) 12/16/2006 6:44:32 AM

```Arthur J. O'Dwyer wrote:
> On Thu, 14 Dec 2006, James Dow Allen wrote:
> > What you're looking for is a "causal" or
> > "anti-causal" multi-dimensional filter which
> > operates in-place (source same as destination).

>    ... would normally be implemented
> not-in-place, and could be done all in parallel, without needing any
> clever optimizations. True?

Yes, one of my examples reused the same buffer "for
improved cache utilization", though the real reason
for using it was just to serve as an example for

>    I also don't think reversing the direction of a loop would change
> an anti-causal filter into a causal version of the /same/ filter.

In image processing, "causal" is applied to x, y, *not* time.
In other words, in a "causal image filter", the new value
at (x,y) depends only on pixels above and/or to the left
of (x,y).  It may seem like a silly use of the word
"causal", but the term isn't my invention.

> > A finite-support filter can be made in-place and
> > anti-causal by shifting the data during processing.
> > For example, a 7x7 sharpening filter ...

>    But how would loop skewing apply to that loop?

Same as your original example.  The looping axis which
allows parallelism is neither x nor y, but (x+y).

> ... Floyd-Steinberg variations.
>
>    So I took the simplest of those dithering algorithms (three inputs to
> each cell); "inverted" it so that each loop iteration read four cells
> and wrote one, instead of reading one and writing four; and then spent
> a lot of time debugging.

I didn't mention this "inversion" possibility because it seems
so inefficient (for one thing, the inverted form needs two buffers,
standard form, one).  But perhaps it's the best way to
exploit parallelism.

> http://en.wikipedia.org/wiki/Polytope_model

Neat article!  Congratulations!

James

```
 0
Reply jdallen2000 (495) 12/16/2006 8:04:53 AM

4 Replies
56 Views

Similar Articles

12/7/2013 11:28:12 PM
page loaded in 28885 ms. (0)