Resource-efficient algorithms for shared-memory parallel architectures
Xiaojun Guan · 1991
In this thesis, we devise new parallel algorithm design strategies for shared-memory parallel architectures. Our main goal is to achieve optimal speedup and, simultaneously, to require only constant extra space per processor, even when the number of processors is fixed. We apply our techniques to several classic problems, including merging, sorting, and related set operations. We also report on large-scale implementation and testing of our merging method.