Load balanced mappings of q-ary and binomial trees into parallel memory systems for fast and conflict-free access to subtree and path templates

Since the cycle time of a processor is typically higher by a factor of 5-10 than the average cycle time of the main memory, the memory access latency can significantly slowdown the overall performance of a computer system. To cope up with this problem, often the main memory of a multiprocessor architecture is organized as multiple banks. Although this enhances the ability of fetching data simultaneously from the memory, yet the contentions at the banks may pose a bottleneck. Therefore, efficient mapping schemes need to be designed that help decluster the memory accesses by regular patterns (called templates) when the number of banks is not sufficiently large. In the literature a lot of mapping schemes have been proposed for two- or three-dimensional arrays, but only limited attention has been paid to devise schemes for non-numeric data structures such as trees or graphs. In this paper, we formalize and study the conflict-free access to subtree and path templates in q-ary and binomial trees. For each template type, we derive the minimum number of memory banks required for its conflict-free access. Our mappings either minimize the number of contentions given a fixed number of banks, or minimize the number of memory banks required to guarantee conflict-free access to the templates. The mappings for template access in q-ary trees are direct, balanced, scalable and versatile. The proposed schemes for accessing arbitrary t-ary subtrees in q-ary trees as well as binomial subtree templates within binomial trees provide examples of optimal mappings far which the required number of memory banks is larger than the size of the templates.