Accession Number:

ADA288589

Title:

A Parallel Complexity Model for Functional Languages.

Descriptive Note:

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE

Personal Author(s):

• Belloch, Guy
• Greiner, John

Report Date:

1994-10-20

Pagination or Media Count:

28.0

Abstract:

A complexity model based on the A-calculus with an appropriate operational semantics in presented and related to various parallel machine models, including the PRAM and hypercube models. The model is used to study parallel algorithms in the context of sequential functional languages and to relate these results to algorithms designed directly for parallel machine models. For example, the paper shows that equally good upper bounds can be achieved for merging two sorted sequences in the pure A-calculus with some arithmetic constants as in the EREW PRAM, when they are both mapped onto a more realistic machine such as a hypercube or butterfly network. In particular for n keys and p processors, they both result in an Onp log 2 p time algorithm. These results argue that it is possible to get good parallelism in functional languages without adding explicitly parallel constructs. In fact, the lack of random access seems to be a bigger problem than the lack of parallelism.

Descriptors:

• *PROGRAMMING LANGUAGES
• ALGORITHMS
• MODELS
• SEMANTICS
• PARALLEL PROCESSING
• RANDOM ACCESS COMPUTER STORAGE
• TIME
• CONSTANTS
• LANGUAGE
• PARALLEL ORIENTATION
• ARITHMETIC

Subject Categories:

• Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE