Parallel Algorithms for Bucket Sorting and the Data Dependent Prefix Problem.
Yijie Han, Robert A. Wagner · Proceedings of the International Conference on Parallel Processing · 1986
The data dependent prefix problem is to compute all the n initial products x1⃝x2⃝...⃝xk, 1 ≤ k ≤ n, where the order is specified by a linked list. A parallel algorithm for the data dependent prefix problem is presented. This algorithm has time complexity O( n p + log n log n p ) using p processors on the exclusive-read exclusive-write computation model. A bucket sorting algorithm is also developed to be used as a component of the prefix algorithm. This bucket sorting algorithm sorts n numbers in the range {1, 2, ...,m} using p processors in O(⌈ logm log( n p + log p) ⌉( p + log p)) time. Index words – Prefix, bucket sorting, parallel algorithms, graph algorithms, optimal algorithms.