Optimal tree access by elementary and composite templates in parallel memory systems

In this paper we study strategies for mapping complete tree data structures, that are accessed by fixed templates, onto parallel memory systems. These mappings are evaluated with respect to the following three different criteria: (i) the number of memory conflicts that can occur in a parallel access to the data structure; (ii) the largest number of elements that can be accessed in parallel without memory conflicts; (iii) the complexity of the memory addressing scheme. We show that there exist trade-offs between these criteria. We describe an algorithm COLOR for mapping complete trees onto EA memory modules and prove that it achieves the following performance: (i) conflict-free access to complete subtrees of size K and paths of size N, for M/spl ges/N+K-[log K]; (ii) at most 1 conflict when accessing complete subtrees and paths of size M; (iii) O((K/M)+c) conflicts when accessing a composite template of K nodes consisting of c disjoint subsets, each being a complete subtree, a path or a set of consecutive nodes in a level of the tree.