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:

1. 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.

2. It is related to the calculational transformation system, so that the cost of a transformation can be associated with its rule.