On Parallel Selection and Searching in Partial Orders: Sorted Matrices
✍ Scribed by R. Sarnath; Xin He
- Publisher
- Elsevier Science
- Year
- 1997
- Tongue
- English
- Weight
- 246 KB
- Volume
- 40
- Category
- Article
- ISSN
- 0743-7315
No coin nor oath required. For personal study only.
✦ Synopsis
rithm given by Cole [3] runs in O(log n log* n) time on an EREW PRAM and in O(log n log* n/log log n) time on a CRCW PRAM. Both algorithms perform O(n) operations. However, not much work has been done on parallel algorithms for constrained selection. The sequential algorithm in [5] is parallelizable but this approach yields an O(log 2 n log* n) running time. Our algorithm solves the selection problem on an n ϫ n sorted matrix in O(log n log log n log* n) time with O(n/log n log* n) processors on an EREW PRAM. From the lower bound proved in [2], it follows that this running time is within O(log log 2 n log* n) of the optimal. The total work done is O(n log log n), which is within O(log log n) of the optimal. The algorithm generalizes to the selection problem on a set of sorted matrices.
Another interesting related problem is the searching problem on sorted matrices [1,6]. Given a sorted n ϫ n matrix X and an element e, we wish to determine whether e occurs in X or not. The searching problem for sorted matrices has an O(n) optimal sequential algorithm [1,6]. We present an optimal parallel algorithm for this problem that runs in O(log log n) time with O(n/log log n) processors on a Common CRCW PRAM. Using a technique similar to the one in [7], we show that no parallel algorithm can solve the problem in time faster than ⍀(log log n) using at most n log c n processors. The only restriction we impose on the parallel model of computation is that each processor can read at most one entry of the sorted matrix in one time step. Our lower bound holds even when we restrict all matrix entries to be drawn from the set ͕0, 1, 2͖ and we set e ϭ 1. We also show, by reducing the Boolean-OR problem to matrix search, that ⍀(log n) steps are needed to solve the matrix search problem on a CREW PRAM.
The model of parallel computation we have chosen is the EREW PRAM for selection and the Common CRCW PRAM for searching (see [8] for definitions of these models). We assume that the matrices are of size n ϫ n. Minor modifications to the algorithms will allow us to use them on matrices of size n ϫ m with m ϭ ⌰(n). For simplicity, we also assume that the elements in the matrices are dis-