We define a new type of recurrence equations called "Simple Indexed Recurre
nces" (SIR). In this type of equations. ordinary recurrences are generalize
d to X[g(i)] = op(i) (X[f(i)],X[g(i)]), where f,g : {1... n}bar right arrow
{1...m}, op(i)(x, y) is a binary associative operator and g is distinct. i.
e., For All (i) not equal j g(i) not equal g(j). This enables us to model c
ertain sequential loops as a sequence of SIR equations. A parallel algorith
m that solves a set of SIR equations will, in fact, parallelize sequential
loops of the above type. Such a parallel SIR algorithm must be efficient en
ough to compete with the O(n) work complexity of the original loop. We show
why efficient parallel algorithms for the related problems of List Ranking
and Tree Contraction. which require O(n.) work, cannot be applied to solvi
ng SIR. We instead use repeated iterations of pointer jumping to compute th
e final values of X[] in n/p . log p steps and n . logp work, with I, proce
ssors. A sequence of experiments was performed to test the effect of synchr
onous and asynchronous executions on the actual performance of the algorith
m. These experiments show that pointer jumping requires O(n) work in most p
ractical cases of SIR loops.
An efficient solution is given for the special case where we know how to co
mpute the inverse of op(i), and finally, useful applications of SIR to the
well-known Livermore Loops benchmark are presented.