Browsing by Author "TIEN, JY"

Now showing 1 - 2 of 2

BROADCASTING ON INCOMPLETE HYPERCUBES
(1993-11-01)
TIEN, JY
;
HO, CT
;
YANG, WP
;
資訊工程學系
;
Department of Computer Science
Incomplete hypercubes make the hypercubes more flexible on task allocation in large cubes, cost of manufacturing hardware, and hypercubes with faulty nodes. In this correspondence, we devise and analyze a broadcasting algorithm based on edge-disjoint spanning trees in an incomplete hypercube of 2n + 2k nodes, where 0 less-than-or-equal-to k less-than-or-equal-to n. The broadcasting algorithm is strictly optimal.
HIERARCHICAL SPANNING-TREES AND DISTRIBUTING ON INCOMPLETE HYPERCUBES
(1991-12-01)
TIEN, JY
;
YANG, WP
;
資訊科學與工程研究所
;
Institute of Computer Science and Engineering
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.