Book contents
- Frontmatter
- Contents
- List of Figures
- Preface
- 1 The Key Idea
- 2 Approaches to Parallel Software Development
- 3 Architectural Background
- 4 Models and Their Properties
- 5 The Categorical Data Type of Lists
- 6 Software Development Using Lists
- 7 Other Operations on Lists
- 8 A Cost Calculus for Lists
- 9 Building Categorical Data Types
- 10 Lists, Bags, and Finite Sets
- 11 Trees
- 12 Arrays
- 13 Graphs
- 14 Conclusions
- A C++ Library for Lists
- B Historical Background
- References
- Index
8 - A Cost Calculus for Lists
Published online by Cambridge University Press: 25 October 2009
- Frontmatter
- Contents
- List of Figures
- Preface
- 1 The Key Idea
- 2 Approaches to Parallel Software Development
- 3 Architectural Background
- 4 Models and Their Properties
- 5 The Categorical Data Type of Lists
- 6 Software Development Using Lists
- 7 Other Operations on Lists
- 8 A Cost Calculus for Lists
- 9 Building Categorical Data Types
- 10 Lists, Bags, and Finite Sets
- 11 Trees
- 12 Arrays
- 13 Graphs
- 14 Conclusions
- A C++ Library for Lists
- B Historical Background
- References
- Index
Summary
We have already discussed why a set of cost measures is important for a model of parallel computation. In this chapter we develop something stronger, a cost calculus. A cost calculus integrates cost information with equational rules, so that it becomes possible to decide the direction in which an equational substitution is cost-reducing. Unfortunately, a perfect cost calculus is not possible for any parallel programming system, so some compromises are necessary. It turns out that the simplicity of the mapping problem for lists, thanks to the standard topology, is just enough to permit a workable solution.
Cost Systems and Their Properties
Ways of measuring the cost of a partially developed program are critical to making informed decisions during the development. An ideal cost system has the following two properties:
It is compositional, so that the cost of a program depends in some straightforward way on the cost of its pieces. This is a difficult requirement in a parallel setting since it amounts to saying that the cost of a program piece depends only on its internal structure and behaviour and not on its context. However, parallel operations have to be concerned about the external properties of how their arguments and results are mapped to processors since there are costs associated with rearranging them. So, for parallel computing, contexts are critically important.
It is related to the calculational transformation system, so that the cost of a transformation can be associated with its rule.
- Type
- Chapter
- Information
- Foundations of Parallel Programming , pp. 89 - 114Publisher: Cambridge University PressPrint publication year: 1994