Automatic Worst Case Complexity Analysis of Parallel Programs

TitleAutomatic Worst Case Complexity Analysis of Parallel Programs
Publication TypeTechnical Report
Year of Publication1990
AuthorsZimmermann, W.
Other Numbers630
Abstract

This paper introduces a first approach for the automatic worst case complexity analysis. It is an extension of previous work on the automatic complexity analysis of functional programs. The language is a first order parallel functional language which allows the definition of indexed data types and parallel execution of indexed terms. The machine model is a parallel reduction system based on eager evaluation. It is shown how parallel programs based on the basic design principles balanced binary tree technique, divide-and-conquer technique and pointer jumping technique can be analyzed automatically. The analysis techniques are demonstrated by various examples. Finally it is shown that an average case analysis of parallel programs is difficult.

URLhttp://www.icsi.berkeley.edu/pubs/techreports/tr-90-066.pdf
Bibliographic Notes

ICSI Technical Report TR-90-066

Abbreviated Authors

W. Zimmermann

ICSI Publication Type

Technical Report