Multiple Templates Access of Trees in Parallel Memory Systems

We study the problem of mapping the N nodes of a data structure on M memory modules so that they can be accessed in parallel by templates i.e. distinct sets of nodes. In literature several algorithms are available for arrays (accessed by rows, columns, diagonals and subarrays) and trees (accessed by subtrees, root-to-leaf paths, etc.). Although some mapping algorithms for arrays allow conflict-free access to several templates at once (for example rows and columns), no mapping algorithm is known for efficiently accessing both subtree and rootto -leaf path templates in complete binary trees. We prove that any mapping algorithm that is conflict-free for one of these two templates has\Omega\Gamma M= log M ) conflicts on the other. Therefore, no mapping algorithm can be found that is conflict-free on both templates. We give an algorithm for mapping complete binary trees with N = 2 M \Gamma 1 nodes on M memory modules in such a way that: ffl the number of conflicts for accessing a subtre..