CaltechAUTHORS
  A Caltech Library Service

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

Thornley, John (1995) Performance of a Class of Highly-Parallel Divide-and-Conquer Algorithms. Computer Science Technical Reports, California Institute of Technology , Pasadena, CA. (Unpublished) http://resolver.caltech.edu/CaltechCSTR:1995.cs-tr-95-10

[img]
Preview
Postscript - Submitted Version
See Usage Policy.

688Kb
[img]
Preview
PDF - Submitted Version
See Usage Policy.

353Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechCSTR:1995.cs-tr-95-10

Abstract

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.


Item Type:Report or Paper (Technical Report)
Additional Information:© 1995 California Institute of Technology. October 1, 1995.
Group:Computer Science Technical Reports
DOI:10.7907/Z9WH2N1H
Record Number:CaltechCSTR:1995.cs-tr-95-10
Persistent URL:http://resolver.caltech.edu/CaltechCSTR:1995.cs-tr-95-10
Usage Policy:You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.
ID Code:26883
Collection:CaltechCSTR
Deposited By: Imported from CaltechCSTR
Deposited On:14 May 2001
Last Modified:02 May 2017 17:47

Repository Staff Only: item control page