标题: 不完整高维立方体上一至多之资料传输
One-To-All Data Communications On Incomplete Hypercubes
作者: 田振扬
Tien, Jenn-Yang
杨维邦
Yang, Wei-Pang
资讯科学与工程研究所
关键字: 不完整高维立方体;分散资料;广播;阶层性展树;不相交展树群
公开日期: 1990
摘要: 近年来,高维立方体架构之多处理机系统愈来愈受重视。许多高维立方体架构,或类似高维立方体之计算机系统产品相继问世。目前含数以千计处理机之高维立方体在技术上以及经济效益上成为可行。高维立方体之主要限制在于处理机之个数必须是2的幂次方。不完整高维立方体为自高维立方体上移掉部份处理机所形成。被移掉的处理机其编号需大于任何存留之处理机之编号。造成不完整高维立方体之原因包括:(1)硬体制造 (2)部份处理机失效 (3)应用程式取用部份之处理机。
本论文中,我们探讨在平行计算机中常使用之两个动作--分散资料及广播,在不完整立方体上之处理方法。无论是分散资料或广播,均为自单一处理机送出讯息给所有其他处理机。分散资料时,每一接收者得到不同之讯息;广播时则所有处理机得到同一讯息。
高维立方体具有许多优点,其中包括高传输频宽。由于不完整高维立方体失去了高维立方体优良之对称性,使得有效使用其传输频宽变得极其困难。本论文中,我们提出在不完整高维立方体上,做分散资料及广播时,有效使用传输频宽之方法。
首先,我们限制不完整高维立方体有2n+2k个处理机。在此有限制的不完整高维立方体上,我们提出两种分散资料之方法。其分散资料之路径分别定主义为二项式阶层性展开树及平衡式阶层性展开树。而且,以平衡式阶层性展开树为路径之方法有较传统方法(二项式阶层性展开树)低之传输复杂度。我们也提出两种广播之方法。依其路径分别定义为阶层性不相交展开树群及不相交展开树群。以阶层性不相交展开树群为路径之广播方法,其传输复杂度为下限之2倍;而以不相交展开树群为路径之广播方法则为下限之(n+1)/(k+1)倍。如果所有传输线可同时传收资料,则以不相交展开树群为路径之广播方法为最佳之方法。
最后,我们将不完整高维立方体之处理机个数之限制去除。为了说明方便,我们仍然先限制处理机之个数为2n-2k。我们在此限制之不完整高维立方体上,建造了最多个数之不相交展开树群。然后,依此方法,我们也在无限制之不完整高维立方体上,建造最多个数之不相交展开树群。从展开树之个数讨论,我们所建立之所有不相交展开树均为上限个数(最多个);从菜开树之高度讨论,我们所建立之所有不相交展开树群都是最佳(或接近最佳)。
Recently, hypercube multiprocessors have been drawing considerable attention. Several computers with hypercube, or hypercube-like, topology have become commercially available. Current technology has made it both technically and economically feasible to build hypercubes with large number of modes. The main restriction on hypercubes is that the number of nodes should be an integer power of two. The incomplete hypercube is a hypercube with a certain number of nodes removed, the removed nodes have node addresses greater than that any remaining node has. An incomplete hypercube may be caused by the hardware construction; some nodes of a complete hypercube become faulty; or allocating partial of nodes of a complete hypercube to an application.
In this thesis, we studied two operations, distributing and broadcasting, in the incomplete hypercube. Both of which are frequently used operations n the parallel computation. In broadcasting, a data set is copied from a node to all other nodes. In distributing, a node sends a unique (distinct) data set to each other node. During broadcasting, nodes in a routing path receive message and propagate it, if that node is not at the end of the routing path. That is, only one copy of the message traverses over a path.
One of attractive properties of the hypercube is high communication bandwidth. As incomplete hypercube lose the symmetricity (in some degree) of the hypercube, it becomes more difficult to utilize the communication bandwidth of the incomplete hypercube effectively. In this thesis, we show that the bandwidth of incomplete hypercubes can be utilized effectively for broadcasting and distributing.
First, we restrict the incomplete hypercube to have 2n+2k nodes. On the restricted incomplete hypercube, we proposed two distributing algorithms. The routes of proposed algorithms are defined as binomial hierarchical spanning tree-binomial HST and balanced hierarchical spanning tree-balanced HST. Distributing algorithms based on the balanced HST take better advantage of overlap between communication ports and have speed-up of either k/2 or n/2 over that based on the conventional binomial HST. For broadcasting, we proposed hierarchical edge-disjoint spanning trees-hierarchical EDST and edge-disjoint spanning trees -EDST's as route of broadcasting. If a node can send and receive on one of its ports at a time, broadcasting algorithms based on the Hierarchical EDST are optimal with a factor of 2 and that based on the EDST's are optimal with a factor of (n+1)/(k+1). If a node can communicate on all its ports concurrently, broadcasting algorithms based on the EDST's are strictly optimal.
A general incomplete hypercube is an incomplete hypercube that the number of removed nodes is arbitrary. To facilitate the description of constructing maximum number of EDST's in the general incomplete hypercube, we construct the maximum number of EDST's in another type of restricted incomplete hypercube in which the number of removed nodes is 2k, for some integer k. And, then we devise the hierarchical spanning trees and edge-disjoint spanning trees in the general incomplete hypercube, which is a hypercube with arbitrary number of nodes removed. Let the height of EDST's be the height of the highest spanning tree in the set of EDST's. The height of EDST's we constructed are optimal (or near optimal).
URI: http://140.113.39.130/cdrfb3/record/nctu/#NT793392001
http://hdl.handle.net/11536/55575
显示于类别:Thesis