Conflict-free template access in k-ary and binomial trees

Load balanced data distribution among various memory modules in a multiprocessor architecture or among multiple disks in a parallel I/O subsystem is an important problem. The goal is to provide parallel access without memory conflicts to specified templates of a host data structure, using a few modules or disks as possible. An efficient solution to this problem leads to a higher memory bandwidth and hence better system performance. Since various kinds of trees are among the most frequently used data structures in numerous applications, we investigate conflict-free access to paths and subtrees in hosts like k-ary and binomial trees. Two schemes are developed for conflict-free path access: one is recursive while the other is direct and can be computed locally. Both the schemes use an optimal number of memory modules, equal to the size of the template, and evenly balance the memory load. For accessing subtrees of a given height in a k-ary tree, our approach uses a simple algebraic function based on the node index to map the host nodes into the memory modules. This assignment is direct, balanced and optimal in terms of the number of memory modules required. We also provide a scheme for conflict-free access to any binomial subtree of a given order in a binomial tree host. The large overlapping among various subtree instances brings out the intricacy of the problem and also justifies the requirement of more modules than the template size, which is the absolute lower bound on the number of memory modules. Therefore, we define what are called oriented subtrees, and restrict their occurrences in such a way that conflict-freeness can still be guaranteed with the same number of modules as the template size.