Array data flow benchmarks

We are putting together a set of small benchmarks to compare the accuracy
and speed of various tests for exact array data-flow dependence analysis.
This information is needed to determine when array privatization is legal,
among other reasons.


For example, we want to be able to determine that in the following
example, all values read from the work array are written in the same
iteration of the j loop. Therefore, it is legal to make the work array
private to the j loop, allowing us to run the j loop in parallel.


for j = 1,n1,2 do
    for i = 1,n2p do
        work(2*i-1) = a(i,j)
        work(2*i) = a(i,j+1)
    endfor
    for i = 1,n2p do
        a(i,j) = work(i)
        a(i,j+1) = work(i+n2p)
    endfor
endfor


These benchmarks will not use procedure calls or non-linear subscripts.
Most of the benchmarks will not contain any control flow other than nested
"do" loops. Some benchmarks will have simply control flow (structured
if-then-else's), although not all techniques will be able to analyze these
benchmarks.


We are planning to include the following:


  * The benchmarks Paul Feautrier used in [Fea91]:
      "across" "choles" "gosser" "relax" "burg2" "lczos" "yacobi"
  * Some simplified versions of some routines from the
      Perfect Club Benchmarks (probably OLDA and INTERF)
  * Some very short examples we use to test specific cases


We are looking for other good benchmarks.


Let us know if either
  (a) you have suggestions for other benchmarks
  (b) you would like to receive our set of benchmarks


Thanks,
Dave Wonnacott
davew@cs.umd.edu


References


Fea91: author = {Paul Feautrier},
title = {Dataflow Analysis of Array and Scalar References},
journal = {International Journal of Parallel Programming},
month = feb, year = 1991, volume = 20, number = 1
--

Return to the comp.compilers page.
Search the comp.compilers archives again.