1985 · 42 citations · 0 references
ComputingComputer EngineeringComputer ScienceAlgorithmsParallel AlgorithmsParallel ComputingAlgorithm AnalysisParallel ArchitecturesParallel Computer ArchitectureParallel Performance AnalysisParallel Prefix ComputationShared-memory ParallelismOptimal Prefix ComputationParallel Algorithm AnalysisParallel Algorithm ComplexityParallel Prefix NetworksParallel Speedup AnalysisPram AlgorithmsProbabilistic Analysis Of Algorithms
The prefix computation problem is to compute all n initial products a1* . . . *a1,i=1, . . ., n of a set of n elements, where * is an associative operation. An O(((logn) log(2n/p))XI(n/p)) time deterministic parallel algorithm using p≤n processors is presented to solve the prefix computation problem, when the order of the elements is specified by a linked list. For p≤O(n1-e)(e〉0 any constant), this algorithm achieves linear speedup. Such optimal speedup was previously achieved only by probabilistic algorithms. This study assumes the weakest PRAM model, where shared memory locations can only be exclusively read or written (the EREW model).