This paper proposes a parallel algorithm, called KDOP (K-DimensionalOptimal Parallel algorithm), to solve a general class of recurrence equations efficiently. The KDOP algorithm partitions the computation into a serie...This paper proposes a parallel algorithm, called KDOP (K-DimensionalOptimal Parallel algorithm), to solve a general class of recurrence equations efficiently. The KDOP algorithm partitions the computation into a series of sub-computations, 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 Write Parallel Ran-dom Access Machine model) using p<N1-e processors, where N is the size of the problem, and e is a given constant. This is an optimal algorithm (itsspeedup is O(p)) in the case of p<N1-e. Such an optimal speedup for this problem was previously achieved only in the case of p<N0.5. The algorithm can be implemented on machines with multiple processing elements or pipelined vector machines with parallel memory systems.展开更多
文摘This paper proposes a parallel algorithm, called KDOP (K-DimensionalOptimal Parallel algorithm), to solve a general class of recurrence equations efficiently. The KDOP algorithm partitions the computation into a series of sub-computations, 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 Write Parallel Ran-dom Access Machine model) using p<N1-e processors, where N is the size of the problem, and e is a given constant. This is an optimal algorithm (itsspeedup is O(p)) in the case of p<N1-e. Such an optimal speedup for this problem was previously achieved only in the case of p<N0.5. The algorithm can be implemented on machines with multiple processing elements or pipelined vector machines with parallel memory systems.
