Accession Number:

ADA001376

Title:

The Complexity of Parallel Evaluation of Linear Recurrences.

Descriptive Note:

Interim rept.,

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1974-11-01

Pagination or Media Count:

14.0

Abstract:

The concept of computers such as C.mmp and ILLIAC 4 is to achieve computational speed-up by performing several operations simultaneously with parallel processors. This type of computer organization is referred to as a parallel computer. In this paper, the authors prove upper bounds on speed-ups achievable by parallel computers for a particular problem, the solution of first order linear recurrences. The authors consider this problem because it is important in practice and also because it is simply stated so that one might obtain some insight into the nature of parallel computation by studying it.

Subject Categories:

  • Computer Hardware

Distribution Statement:

APPROVED FOR PUBLIC RELEASE