About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
IEEE TPDS
Paper
Parallel solutions of simple indexed recurrence equations
Abstract
We define a new type of recurrence equations called 'Simple Indexed Recurrences' (SIR). In this type of equations, ordinary recurrences are generalized to X[g(i)] = opi(X[f(i)], X[g(i)]), where f,g: {1...n}→{1...m}, opi(x,y) is a binary associative operator and g is distinct. This enables us to model certain sequential loops as a sequence of SIR equations. A parallel algorithm that solves as a set of SIR equations will, in fact, parallelize sequential loops of the above type. Such a parallel SIR algorithm must be efficient enough 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 solving SIR. A sequence of experiments was performed to test the effect of synchronous and asynchronous executions on the actual performance of the algorithm. An efficient solution is given for the special case where we know how to compute the inverse of opi, and finally, useful applications of SIR to the well-known Livermore Loops benchmark are presented.