標題: HIERARCHICAL SPANNING-TREES AND DISTRIBUTING ON INCOMPLETE HYPERCUBES
作者: TIEN, JY
YANG, WP
資訊科學與工程研究所
Institute of Computer Science and Engineering
關鍵字: INCOMPLETE HYPERCUBES;DISTRIBUTING, SPANNING TREES;DATA COMMUNICATION
公開日期: 1-Dec-1991
摘要: Incomplete hypercubes are gaining increasing attention as one of the possible solutions for the limitation on the number of nodes in the hypercubes. Distributing, in which one node sends distinct messages to distinct nodes, and its reverse operation are frequently used operations on data parallel computation. In this paper, we propose two types of spanning trees in incomplete hypercubes (composed of an n-cube and a k-cube): the binomial hierarchical spanning tree-binomial HST, and the balanced hierarchical spanning tree-balanced HST, for distributing (and its reverse operation). Distributing algorithms based on a balanced HST take better advantage of overlap between communication ports, or have speedup up to k/2 or n/2 over that based on the binomial HST when concurrently communication on all ports are possible, from the view point of communication complexity. An algorithm to construct hierarchical spanning trees in general incomplete hypercubes, which consist of an arbitrary number of nodes, is also devised.
URI: http://hdl.handle.net/11536/3627
ISSN: 0167-8191
期刊: PARALLEL COMPUTING
Volume: 17
Issue: 12
起始頁: 1343
結束頁: 1360
Appears in Collections:Articles