不完整高維立方體上一至多之資料傳輸

Abstract

近年來，高維立方體架構之多處理機系統愈來愈受重視。許多高維立方體架構，或類似高維立方體之計算機系統產品相繼問世。目前含數以千計處理機之高維立方體在技術上以及經濟效益上成為可行。高維立方體之主要限制在於處理機之個數必須是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).