Accession Number:

ADA012492

Title:

Optimal Sorting Algorithms for Parallel Computers.

Descriptive Note:

Interim rept.,

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1975-05-01

Pagination or Media Count:

13.0

Abstract:

The problem of sorting a sequence of n elements on a parallel computer with k processors is considered. The algorithms the authors present can all be run on a single instruction stream multiple data stream computer. For large n, each achieves an asymptotic speed-up ratio of k with respect to the best sequential algorithm. This linear in k speed-up is optimal in the number of processors used.

Subject Categories:

  • Computer Programming and Software
  • Computer Hardware

Distribution Statement:

APPROVED FOR PUBLIC RELEASE