next up previous contents
Next: List-like Up: The allocation algorithm Previous: The allocation algorithm

Tree-like

Consider a basic binary tree structure, where at each level there are at most two sub trees, and we have numbered the processors $[1 \ldots
n]$. Then we can map the left sub tree to the set $[1 \ldots
\frac{n}{2} )$ and the right sub tree to the set $[\frac{n}{2} \ldots
n]$. This idea extends naturally to the situation where we have a tree with at most k sub trees, and maps distinct sub trees to distinct sets of processors.



Timothy Lewis
11/12/1997