Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published May 14, 2001 | Submitted
Report Open

Performance of a Class of Highly-Parallel Divide-and-Conquer Algorithms

Thornley, John


A wide range of important problems have efficient methods of solution based on the divide-and-conquer strategy. However, the traditional approach to parallel divide-and-conquer does not scale well due to the sequential component of the algorithms. We investigate the performance of a non-traditional, highly-parallel divide-and-conquer strategy that we refer to as "one-deep parallel divide-and-conquer". As representative examples, we measure and analyze the performance of highly-parallel variants of the quicksort and mergesort algorithms on a shared-memory multiprocessor. Both algorithms deliver impressive speedups. We present a systematic approach to modeling the performance of one-deep parallel divide-and-conquer algorithms and we demonstrate this approach with the two parallel sorting algorithms.

Additional Information

© 1995 California Institute of Technology. October 1, 1995.

Attached Files

Submitted - 95-10.pdf

Submitted - 95-10.ps


Files (1.1 MB)
Name Size Download all
362.1 kB Preview Download
705.5 kB Download

Additional details

August 20, 2023
October 24, 2023