On the power of nonconservative PRAM
A Dessmark, A Lingas - International Symposium on Mathematical …, 1996 - Springer
A Dessmark, A Lingas
International Symposium on Mathematical Foundations of Computer Science, 1996•Springer… In [4], Albers and Hagerup also presented a method of reduction of parallel conservative
integer sorting to parallel nonconservative integer sorting. Combining their method with our
new bounds on nonconservative parallel integer sorting, we also obtain improved bounds
on conservative parallel integer sorting in the EREW PRAM model. In particular, we show
that n integers of size n can be sorted in time O(log 3/2 n) on a EREW PRAM with n~ logn
processors. Previously, such a result was known only in the CREW …
integer sorting to parallel nonconservative integer sorting. Combining their method with our
new bounds on nonconservative parallel integer sorting, we also obtain improved bounds
on conservative parallel integer sorting in the EREW PRAM model. In particular, we show
that n integers of size n can be sorted in time O(log 3/2 n) on a EREW PRAM with n~ logn
processors. Previously, such a result was known only in the CREW …
Abstract
An alternative simple method of exploiting word parallelism in a nonconservative RAM and PRAM model is considered. In effect, improved bounds for parallel integer sorting in the nonconservative and conservative EREW PRAM models are obtained.
Springer
Showing the best result for this search. See all results