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

template mapping, trees, lower bound.

In parallel processing, efﬁcient 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 conﬂicts. 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 conﬂict-free access) in such a way that the load is balanced among all memory banks. Let f_{h, 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} f_{h,j}, and y _{h } = min _{0 ≤ j ≤ h - 1} f_{h,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