Search

The recursive dual-net is a newly proposed interconnection network for massive parallel computers. The recursive dual-net is based on recursive dual-construction of a symmetric base network. A k-level dual-construction for k > 0 creates a network containing (2n0)2k/2 nodes with node-degree d0 + k, where n0 and d0 are the number of nodes and the node-degree of the base network, respectively. The recursive dual-net is node and edge symmetric and can contain huge number of nodes with small node-degree and short diameter. Disjoint-paths routing and fault-tolerant routing are fundamental and critical issues for the performance of an interconnection network. In this paper, we propose efficient algorithms for disjoint-paths and fault-tolerant routings on the recursive dual-net. [ABSTRACT FROM AUTHOR]

Abstract: Let be a free tree in which each vertex has a weight and each edge has a length. Let . Given T and parameters k and l, a -tree core is a subtree X of T with diameter ⩽l, having k leaves, which minimizes the sum of the weighted distances from all vertices in T to X. In this paper, two efficient algorithms are presented for finding a -tree core of T. The first algorithm has time complexity for the case that each edge has an arbitrary length. The second algorithm has time complexity for the case that the lengths of all edges are 1. The -tree core problem has an application in distributed database systems. [Copyright &y& Elsevier]

The hypercube, or n-cube, has been widely used as the interconnection network in parallel computers. However, the major drawback of the hypercube is the increase in the number of communication links for each node with the increase in the total number of nodes in the system. This paper introduces a new interconnection network, namely dual-cube, for large-scale parallel computers and describes the algorithms for efficient collective communications in dual-cube. The dual-cube network mitigates the problem of increasing number of links in the large-scale hypercube network while retains hypercube’s topological properties. Design of efficient routing algorithms for collective communications is the key issue for any interconnection network. In this paper, we show that the collective communications can be done in dual-cube with almost the same communication times as in hypercube. [ABSTRACT FROM AUTHOR]

Looks at a general fault tolerant routing problem of cluster fault tolerant (CFT) routing in hypercubes. What is a cluster; Information on the study done on k-pairwise CFT routing; Method of the study; Details on the CFT routing problem.

The perfect hierarchical hypercube (HHC) interconnection network, also known as the cube-connected cube, was introduced as a topology for large parallel computers. One of its interesting properties is that it can connect many nodes while retaining a small diameter and a low degree. The first node-to-set disjoint-path routing algorithm in perfect HHCs was previously introduced by Bossard et al. [(2011) Node-to-Set Disjoint-Path Routing in Perfect Hierarchical Hypercubes. Proc. 11th Int. Conf. Computational Science, Tsukuba, Japan, June 1–3. Elsevier, Amsterdam]. In this paper, we propose a novel solution to the node-to-set disjoint-path routing problem in HHC. Inside a (2m + m)-dimensional HHC, we shall describe an algorithm that can find disjoint paths between a source node and at most m + 1 destination nodes of maximum length O(2m), significantly shorter than the maximum path length O(m2m) of Bossard et al. [(2011) Node-to-Set Disjoint-Path Routing in Perfect Hierarchical Hypercubes. Proc. 11th Int. Conf. Computational Science, Tsukuba, Singapore, June 1–3. Elsevier, Amsterdam]. [ABSTRACT FROM AUTHOR]