KDimensional Optimal Parallel Algorithm for the Solution of a General Class of Recurrence Equations

Abstract
This paper proposes a parallel algorithm, called KDOP (KDimensionalOptimal Parallel algorithm), to solve a general class of recurrence equations efficiently. The KDOP algorithm partitions the computation into a series of subcomputations, each of which is executed in the fashion that all the processors work simultaneously with each one executing an optimal sequential algorithm to solve a subcomputation task. The algorithm solves the equations in O(N/p)steps in EREW PRAM model (Exclusive Read Exclusive Writ…

