局部k-子立方连通的超立方网络中的广播容错算法

基于局部k-子立方体连通性的概念,提出了在局部k-子立方连通的超立方体中的,“播路由算法该算法是分布的、基于局部信息的,在容错性上有了很大的提高,能在线性时间内构造超立方体H1中接近最优的路径。     

A fault-tolerant wormhole routing scheme for torus networks with nonconvex faults

In this paper, we present a fault-tolerant routing algorithm for torus networks by using only 4 virtual channels. The proposed algorithm is based on the solid fault model, which includes rectangular faults and many practical nonconvex faults. Previous works need at least 6 virtual channels to achieve the same fault-tolerant ability.     

A study of fault tolerance in star graph

The bounds on f(n,k), the number of faulty nodes to make every (n−k)-dimensional substar Sn−k in an n-dimensional star network Sn, have been derived. The exact value for f(n,k) is determined when n is prime and k=2, or when n−2?k?n. For 2<k<n−2, a general method is presented to derive a set of faulty nodes which damage all Sn−k's in Sn.     

Fault-tolerant wormhole routing for hypercube networks

We present an adaptive fault-tolerant wormhole routing algorithm for hypercubes by using 3 virtual networks. The routing algorithm can tolerate at least n−1 faulty nodes and can route a message via a path of length no more than the shortest path plus four. Previous algorithms which achieve the same fault tolerant ability need 5 virtual networks. Simulation results are also given in this paper.     

Probabilistic analysis on mesh network fault tolerance

Mesh networks are among the most important interconnection network topologies for large multicomputer systems. Mesh networks perform poorly in tolerating faults in the view of worst-case analysis. On the other hand, such worst cases occur very rarely in realistic situations. In this paper, we study the fault tolerance of 2-D and 3-D mesh networks under a more realistic model in which each network node has an independent failure probability. We first observe that if the node failure probability is fixed, then the connectivity probability of these mesh networks can be arbitrarily small when the network size is sufficiently large. Thus, it is practically important for multicomputer system manufacture to determine the upper bound for node failure probability when the probability of network connectivity and the network size are given. We develop a novel technique to formally derive lower bounds on the connectivity probability for 2-D and 3-D mesh networks. Our study shows that these mesh networks of practical size can tolerate a large number of faulty nodes thus are reliable enough for multicomputer systems. For example, it is formally proved that as long as the node failure probability is bounded by 0.5%$0.5\%$, a 3-D mesh network of up to a million nodes remains connected with a probability larger than 99%$99\%$.     

Characterization of spatial fault patterns in interconnection networks

Parallel computers, such as multiprocessors system-on-chip (Mp-SoCs), multicomputers and cluster computers, are consisting of hundreds or thousands multiple processing units and components (such as routers, channels and connectors) connected via some interconnection network that collectively may undergo high failure rates. Therefore, these systems are required to be equipped with fault-tolerant mechanisms to ensure that the system will keep running in a degraded mode. Normally, the faulty components are coalesced into fault regions, which are classified into two major categories: convex and concave regions. In this paper, we propose the first solution to calculate the probability of occurrences of common fault patterns in torus and mesh interconnection networks which includes both convex (-shaped, □-shaped) and concave (L-shaped, T-shaped, +-shaped, H-shaped) regions. These results play a key role when studying, particularly, the performance analysis of routing algorithms proposed for interconnection networks under faulty conditions.     

Embedding a long fault-free cycle in a crossed cube with more faulty nodes

The crossed cube is an important variant of the most popular hypercube network for parallel computing. In this paper, we consider the problem of embedding a long fault-free cycle in a crossed cube with more faulty nodes. We prove that for n?5 and f?2n−7, a fault-free cycle of length at least n²−f−(n−5) can be embedded in an n-dimensional crossed cube with f faulty nodes. Our work extends some previously known results in the sense of the maximum number of faulty nodes tolerable in a crossed cube.     

Edge-fault-tolerant diameter and bipanconnectivity of hypercubes

Let n(?3) be a given integer and . And let Qn be an n-dimensional hypercube and F⊂E(Qn), such that every vertex of the graph Qn−F is incident with at least two edges. Assume x and y are any two vertices with Hamming distance H(x,y)=h. In this paper, we obtain the following results: (1) If h?2 and |F|?min{n+h−1,2n−5}, then in Qn−F there exists an xy-path of each length l∈Ωh+2, and the upper bound n+h−1 on |F| is sharp when 2?h?n−4, and the upper bound 2n−5 on |F| is sharp when n−4?h?n−1 and h=2. (2) If |F|?2n−5, then in Qn−F there exists an xy-path of each length l∈Ωs, where s=h if n−1?h?n, and s=h+2 if n−4?h?n−2 and h?2, and s=h+4 otherwise. Hence, the diameter of the graph Qn−F is n. Our results improve some previous results.     

Hamiltonian properties of twisted hypercube-like networks with more faulty elements

Twisted hypercube-like networks (THLNs) are a large class of network topologies, which subsume some well-known hypercube variants. This paper is concerned with the longest cycle in an n-dimensional (n-D) THLN with up to 2n−9 faulty elements. Let G be an n-D THLN, n≥7. Let F be a subset of V(G)?E(G), |F|≤2n−9. We prove that G−F contains a Hamiltonian cycle if δ(G−F)≥2, and G−F contains a near Hamiltonian cycle if δ(G−F)≤1. Our work extends some previously known results.     

Optimal book embeddings of the FFT, benes, and barrel shifter networks

This paper gives 3-page book embeddings of three important interconnection networks: the FFT network, the Benes rearrangeable permutation network, and the barrel shifter network. Since all three networks are eventually nonplanar, they require three pages and the present embeddings are optimal. Also, the embeddings have pages of comparable widths.The embeddings of the FFT and barrel shifter networks are obtained by decomposing these recursively defined networks into smaller copies of themselves and using induction. The embedding of the Benes network uses a novel decomposition of the network into eight copies of a smaller FFT network.This work was accomplished as a part of the MITRE Corporation's Independent Research and Development Program.     

The super connectivity of exchanged hypercubes

The exchanged hypercube EH(s,t) where s?1 and t?1 are two positive integers, proposed by Loh et al. [The exchanged hypercube, IEEE Transactions on Parallel and Distributed Systems 16 (9) (2005) 866-874], is obtained by systematically removing links from a binary hypercube Qn. This paper determines that the super connectivity and the super edge-connectivity of EH(s,t) are 2s where s?t. That is, for s?t, at least 2s vertices (resp. 2s edges) of EH(s,t) are removed to get a disconnected graph that contains no isolated vertex.     

Efficient reconfiguration algorithms for communication-aware three-dimensional processor arrays

Homogeneous processor arrays are emerging in tera-scale computation and effective fault tolerance techniques are essential to improving the reliability of such complex integrated circuits. We study the degradable processor arrays to achieve fault tolerance by employing reconfiguration. Three bypass schemes and three rerouting schemes are proposed to reconfigure three-dimensional processor arrays with defective processors to achieve target arrays without faults. A heuristic algorithm is proposed to construct a target array on the selected rows and columns. It is also proved that the proposed greedy plane rerouting algorithm (GPR) produces maximum target array. In addition, the problem of constructing the communication efficient array is considered in this paper. An algorithm is proposed to refine the communication among processors within the target array constructed by GPR. Experimental study shows that the proposed algorithm GPR produces target arrays with higher harvest and lower degradation on the host arrays with fault density no more than 5%. In addition, the communication performance is significantly optimized by reducing the number of long interconnects, and the average improvement is about 34% for all cases considered in this paper.     

The super connectivity of augmented cubes

The augmented cube AQn, proposed by Choudum and Sunitha [S.A. Choudum, V. Sunitha, Augmented cubes, Networks 40 (2) (2002) 71-84], is a (2n−1)-regular (2n−1)-connected graph (n≠3). This paper determines that the super connectivity of AQn is 4n−8 for n?6 and the super edge-connectivity is 4n−4 for n?5. That is, for n?6 (respectively, n?5), at least 4n−8 vertices (respectively, 4n−4 edges) of AQn are removed to get a disconnected graph that contains no isolated vertices. When the augmented cube is used to model the topological structure of a large-scale parallel processing system, these results can provide more accurate measurements for reliability and fault tolerance of the system.     

On the maximal connected component of hypercube with faulty vertices (II)

In evaluating the fault tolerance of an interconnection network, it is essential to estimate the size of a maximal connected component of the network at the presence of faulty processors. Hypercube is one of the most popular interconnection networks. In this paper, we prove that for n?≥?6, an n-dimensional cube with a set F of at most (4n???10) failing processors has a component of size ≥2″???|F|???3. This result demonstrates the superiority of hypercube in terms of the fault tolerance.     

Conditional connectivity of Cayley graphs generated by transposition trees

Given a graph G and a non-negative integer h, the Rh-(edge)connectivity of G is the minimum cardinality of a set of (edges)vertices of G, if any, whose deletion disconnects G, and every remaining component has minimum degree at least h. Similarly, given a non-negative integer g, the g-(edge)extraconnectivity of G is the minimum cardinality of a set of (edges)vertices of G, if any, whose deletion disconnects G, and every remaining component has more than g vertices. In this paper, we determine R₂-(edge)connectivity and 2-extra(edge)connectivity of Cayley graphs generated by transposition trees.     

On the maximal connected component of hypercube with faulty vertices

In evaluating an interconnection network, it is indispensable to estimate the size of the maximal connected components of the underlying graph when the network begins to lose processors. Hypercube is one of the most popular interconnection networks. This article addresses the maximal connected components of an n-dimensional cube with faulty processors. We first prove that an n-cube with a set F of at most 2n???3 failing processors has a component of size ≥2 ⁿ ???|F|???1. We then prove that an n-cube with a set F of at most 3n???6 missing processors has a component of size ≥2 ⁿ ???|F|???2.     

Super connectivity of Kronecker products of graphs

Let G₁ and G₂ be two connected graphs. The Kronecker product G₁×G₂ has vertex set V(G₁×G₂)=V(G₁)×V(G₂) and the edge set . In this paper, we show that if G is a bipartite graph with κ(G)=δ(G), then G×Kn(n?3) is super-κ.