首页 | 本学科首页   官方微博 | 高级检索  
     


EFFICIENT EMULATIONS FOR X-TREES AND /w-ARY TREES*
Abstract: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 smaller size is proposed. The proposed emulation is load-balanced and of 1-dilation. And, the congestion is /></span> 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 C by a smaller X-tree H, we can easily determine the node that is responsible for simulating a given node of G in O(1) time. And, we can determine the nodes that are simulated by a given node of H in O(|G|/|H|)time. Second, our emulation can be directly applied to emulate a tree by another tree of smaller size without 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 algorithms designed on X-trees assume that only the root and leaf nodes can perform I/O operations.</p> The m-ary tree is a generalization of the binary tree, where m ? 2 and is an integer. In this paper, we also propose an efficient emulation for n;-ary trees. The proposed emulation for m-ary trees is load-balanced and of I-dilation. And, the congestion is <span class= /></span> <span class= /></span></td> </tr> <tr> <td align=
Keywords:Interconnection networks  X-trees  m-ary trees  Simulation  Emulation  Parallel algorithms
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号