On an Open Problem of a Template Mapping Algorithm for Complete Binary Trees

S.K. Das (USA) and K. Qiu (Canada)


template mapping, trees, lower bound.


In parallel processing, efficient mapping schemes are required to distribute data in such a way that regular patterns called templates of various data structures such as trees can be retrieved in parallel without memory conflicts. In their paper [1], Das and Pinotti studied the problem when the underlying structures are general q-ary trees and binomial trees and templates are leaf-to-root paths and subtrees. In particular, for complete binary trees where templates are leaf-to-root paths, an optimal and balanced scheme was proposed. To this end, nodes of a complete binary tree are colored (assigned to different memory banks) such that for any path from a leaf to the root, nodes on the path are as signed different colors (to guarantee conflict-free access) in such a way that the load is balanced among all memory banks. Let fh, j be the frequency of the color ,em>j used in a complete binary tree of height h, x h , =max 0 ≤ j ≤ h - 1 fh,j, and y h = min 0 ≤ j ≤ h - 1 fh,j, where x ,h and y h are the maximum and minimum load on the memory banks (the root and only the root is assigned color h, thus f h, h = 1), an open problem raised in [1] is whether x h / y h ≤ 3/2. In this paper, we show that 3/2 is indeed a lower bound to the ratio x h / y h. In addition, we study the many interesting combinatorial properties of the sequence {f h, j }.

Important Links:

Go Back