EFFICIENT EMULATIONS FOR X-TREES AND m-ARY TREES

[[abstract]]©1998 Taylor & Francis-Simulating a network by a smaller one with the same interconnection structure is also called emulation. In this paper, an efficient emulation for simulating an X-tree by another X;lree of smiiller size is proposed. The proposed emulation is load-balanced and of I-dilation. And, the congestion is LlGlflHIJ - 2xf=y 2g-IXh + I . The proposed emulation is optimal with respect to load and dilation. Besides, our emulation has the following advantages. First, it is simple and thus easy to compute. While using our emulation to simulate an X-tree G by a smaller X-tree H, we can casily determine the node that is responsible for simulating a given node of G in O(I) time. And, we can determine the nodes that are simulated by a given node of H in O(JGI/IHI) time. Second, our emulation can be directly applied to emulate a tree by another tree of smaller size withoul losing any efficiency. Finally, our emulation has the property that a root node is simulated by a root node and a leaf node is simulated by a leaf node. This property makes our emulation suitable for X-trees in which root nodes and leaf nodes should perform some special operations that cannot be performed by other internal nodes. For example, most ;llgorithms designed on X-trees assume that only the root and leaf nodes can perform I/O operations. The m-ary tree is a generalization of the binary tree, where m 2 2 and is an integer. In this paper. we also propose an eflicient emulation for ni-ary trees. The proposed emulation for nt-ary trees is load-balanced and of I-dilation. And, the congestion is LlGlIlHIJ- ~ 1 . t l l " h I , l ~ - t ~ h[[department]]資訊工程學