One-To-All Data Communications On Incomplete Hypercubes
|摘要:||近年來，高維立方體架構之多處理機系統愈來愈受重視。許多高維立方體架構，或類似高維立方體之計算機系統產品相繼問世。目前含數以千計處理機之高維立方體在技術上以及經濟效益上成為可行。高維立方體之主要限制在於處理機之個數必須是2的冪次方。不完整高維立方體為自高維立方體上移掉部份處理機所形成。被移掉的處理機其編號需大於任何存留之處理機之編號。造成不完整高維立方體之原因包括：(1)硬體製造 (2)部份處理機失效 (3)應用程式取用部份之處理機。
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).
|Appears in Collections:||Thesis|