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 con icts 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 con icts; (iii) the complex- ity of the memory addressing scheme. We show that there exist trade-os between these criteria.....