Compilers - Banerjee inequality

Author

Banerjee inequality

Pertti Kellomäki

2007-11-02, 10:11 pm

I am trying to wrap my head around the Banerjee inequality (a basis
for a particular form of dependence testing in loops). While I
understand the gross outline, I am trying to work out the details to
convince myself. However, the proofs in Allen and Kennedy's Optimizing
Compilers for Modern Architectures are given in such high level that I
am having a hard time filling in some of the gaps.

Does anyone know of sources where the proofs would be spelled
out in more detail?
--
Pertti

Jason Lee Eckhardt

2007-11-06, 7:19 pm

=?ISO-8859-1?Q?Pertti_Kellom=E4ki?= <pertti.kellomaki@tut.fi> wrote:
>I am trying to wrap my head around the Banerjee inequality (a basis
>for a particular form of dependence testing in loops). While I
>understand the gross outline, I am trying to work out the details to
>convince myself. However, the proofs in Allen and Kennedy's Optimizing
>Compilers for Modern Architectures are given in such high level that I
>am having a hard time filling in some of the gaps.
>
>Does anyone know of sources where the proofs would be spelled
>out in more detail?

See:
Zima and Chapman, "Supercompilers for Parallel and Vector Computers", 1991.
Chapter 4 and Appendix B.

George Neuner

2007-11-06, 7:19 pm

On Fri, 02 Nov 2007 11:32:01 +0200, Pertti Kellomdki <pertti.kellomaki@tut.fi> wrote:

>I am trying to wrap my head around the Banerjee inequality (a basis
>for a particular form of dependence testing in loops). While I
>understand the gross outline, I am trying to work out the details to
>convince myself. However, the proofs in Allen and Kennedy's Optimizing
>Compilers for Modern Architectures are given in such high level that I
>am having a hard time filling in some of the gaps.
>
>Does anyone know of sources where the proofs would be spelled
>out in more detail?

You might try:

David Klappholz, Kleanthis Psarris, and Xiangyun Kong, "On the perfect
accuracy of an approximate subscript analysis test", ACM SIGARCH
Computer Architecture News , Proceedings of the 4th international
conference on Supercomputing ICS '90, Volume 18 Issue 3b, June 1990.

or

Kleanthis Psarris, David Klappholz, and Xiangyun Kong, On the
Accuracy of the Banerjee Test, Journal of Parallel and Distributed
Computing, Special Issue on Shared Memory Multiprocessors, Vol. 12,
No. 2, June 1991.

ACM has the first paper. I haven't found the second one - it came up
in the bibliography of another paper on dependency analysis.

George

Pertti Kellomäki

2007-11-06, 7:19 pm

rcmetzger wrote
> Dependence Analysis for Supercomputing, U. Banerjee, Kluwer Academic
> Publishers, 1988

Thanks, I was also recommended the same book privately. I'll try to
get hold of a copy. One of the online used book sellers has a copy to
sell, but I am not convinced I would be willing to buy the 170 euros
they are asking!
--
Pertti

Pertti Kellomäki

2007-11-08, 7:14 pm

George Neuner wrote
> David Klappholz, Kleanthis Psarris, and Xiangyun Kong, "On the perfect
> accuracy of an approximate subscript analysis test", ACM SIGARCH
> Computer Architecture News , Proceedings of the 4th international
> conference on Supercomputing ICS '90, Volume 18 Issue 3b, June 1990.

Thanks, this is a good source. It also provides an interesting
reason why the Banerjee test works so well in practice: "if there
is a coefficient of +1 or -1, and if all coefficients are smaller,
in absolute value, than all loop iteration ranges, then the Banerjee
test checks for integer solutions".
--
Pertti

Sponsored Links