Introduction

We now turn to the problem of mapping the data nodes that we have named to the actual physical processors. Naturally this needs to be done in a manner that is transparent to the user, and allows the data structure to be manipulated in an efficient way. It is important to emphasise that in a situation where we have a dynamically growing and shrinking structure, the best solution is for a dynamic strategy that re-allocates nodes as the structure changes. I have not considered this problem, but have settled instead for a static allocation, which should provide a reasonable allocation for a balanced, static structure.

The issues that have motivated the allocation strategy are as follows.

• Locality: Data items that are near to each other in the structure need to be placed in nearby processors.
• Fair Division: As each data item corresponds to an amount of computation, to divide the work equally the data needs to be spread out amongst the processors as fairly as possible.
• Parallelism: The distinct sub parts of the structure need to be mapped to distinct sets of processors to encourage as much potential parallelism as possible.

Note that the idea here is to map the nodes to processors in a way that is completely known at the outset, and will not change as the structure changes dynamically. This means that we cannot use any information about the size of the structure, or how balanced it is. Ideally, we would also want to add a mechanism to re-distribute the nodes once certain conditions relating to how unbalanced the structure has become, but this problem has not been considered.