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
