In this paper, the concept of k-submesh and k-submesh connectivity fault tolerance model is proposed. And the fault tolerance of 3-D mesh networks is studied under a more realistic model in which each network node has...In this paper, the concept of k-submesh and k-submesh connectivity fault tolerance model is proposed. And the fault tolerance of 3-D mesh networks is studied under a more realistic model in which each network node has an independent failure probability. It is first observed that if the node failure probability is fixed, then the connectivity probability of 3-D mesh networks can be arbitrarily small when the network size is sufficiently large. Thus, it is practically important for multicomputer system manufacturer to determine the upper bound for node failure probability when the probability of network connectivity and the network size are given. A novel technique is developed to formally derive lower bounds on the connectivity probability for 3-D mesh networks. The study shows that 3-D mesh networks of practical size can tolerate a large number of faulty nodes thus are reliable enough for multicomputer systems. A number of advantages of 3-D mesh networks over other popular network topologies are given. Compared to 2-D mesh networks, 3-D mesh networks are much stronger in tolerating faulty nodes, while for practical network size, the fault tolerance of 3-D mesh networks is comparable with that of hypercube networks but enjoys much lower node degree.展开更多
The （s＋t＋1）-dimensional exchanged crossed cube, denoted as ECQ（s, t）, combines the strong points of the exchanged hypercube and the crossed cube. It has been proven that ECQ（s, t） has more attractive propertie...The （s＋t＋1）-dimensional exchanged crossed cube, denoted as ECQ（s, t）, combines the strong points of the exchanged hypercube and the crossed cube. It has been proven that ECQ（s, t） has more attractive properties than other variations of the fundamental hypercube in terms of fewer edges, lower cost factor and smaller diameter. In this paper, we study the embedding of paths of distinct lengths between any two different vertices in ECQ（s, t）. We prove the result in ECQ（s, t）： if s≥3, t≥3, for any two different vertices, all paths whose lengths are between max{9,「s＋1/2」 ＋「t＋1/2＋4}and 2s＋t＋1？1 can be embedded between the two vertices with dilation 1. Note that the diameter of ECQ（s, t） is「s＋1/2 」＋「t＋1/2 」＋2. The obtained result is optimal in the sense that the dilations of path embeddings are all 1. The result reveals the fact that ECQ（s, t） preserves the path embedding capability to a large extent, while it only has about one half edges of CQn.展开更多
Scalability is an important issue in the design of interconnection networks for massively parallel systems. In this paper a scalable class of interconnection network of Hex-Cell for massively parallel systems is intro...Scalability is an important issue in the design of interconnection networks for massively parallel systems. In this paper a scalable class of interconnection network of Hex-Cell for massively parallel systems is introduced. It is called Multilayer Hex-Cell (MLH). A node addressing scheme and routing algorithm are also presented and discussed. An interesting feature of the proposed MLH is that it maintains a constant network degree regardless of the increase in the network size degree which facilitates modularity in building blocks of scalable systems. The new addressing node scheme makes the proposed routing algorithm simple and efficient in terms of that it needs a minimum number of calculations to reach the destination node. Moreover, the diameter of the proposed MLH is less than Hex-Cell network.展开更多
文摘In this paper, the concept of k-submesh and k-submesh connectivity fault tolerance model is proposed. And the fault tolerance of 3-D mesh networks is studied under a more realistic model in which each network node has an independent failure probability. It is first observed that if the node failure probability is fixed, then the connectivity probability of 3-D mesh networks can be arbitrarily small when the network size is sufficiently large. Thus, it is practically important for multicomputer system manufacturer to determine the upper bound for node failure probability when the probability of network connectivity and the network size are given. A novel technique is developed to formally derive lower bounds on the connectivity probability for 3-D mesh networks. The study shows that 3-D mesh networks of practical size can tolerate a large number of faulty nodes thus are reliable enough for multicomputer systems. A number of advantages of 3-D mesh networks over other popular network topologies are given. Compared to 2-D mesh networks, 3-D mesh networks are much stronger in tolerating faulty nodes, while for practical network size, the fault tolerance of 3-D mesh networks is comparable with that of hypercube networks but enjoys much lower node degree.
基金This work is supported by the National Natural Science Foundation of China under Grant Nos. 61572337 and 61502328, the Program for Postgraduates Research Innovation in University of Jiangsu Province under Grant No. KYLX16_0126, Collaborative Innovation Center of Novel Software Technology and Industrialization, and tile Natural Science Foundation of tile Jiangsu Higher Education Institutions of China under Grant No. 14KJB520034.
文摘The （s＋t＋1）-dimensional exchanged crossed cube, denoted as ECQ（s, t）, combines the strong points of the exchanged hypercube and the crossed cube. It has been proven that ECQ（s, t） has more attractive properties than other variations of the fundamental hypercube in terms of fewer edges, lower cost factor and smaller diameter. In this paper, we study the embedding of paths of distinct lengths between any two different vertices in ECQ（s, t）. We prove the result in ECQ（s, t）： if s≥3, t≥3, for any two different vertices, all paths whose lengths are between max{9,「s＋1/2」 ＋「t＋1/2＋4}and 2s＋t＋1？1 can be embedded between the two vertices with dilation 1. Note that the diameter of ECQ（s, t） is「s＋1/2 」＋「t＋1/2 」＋2. The obtained result is optimal in the sense that the dilations of path embeddings are all 1. The result reveals the fact that ECQ（s, t） preserves the path embedding capability to a large extent, while it only has about one half edges of CQn.
文摘Scalability is an important issue in the design of interconnection networks for massively parallel systems. In this paper a scalable class of interconnection network of Hex-Cell for massively parallel systems is introduced. It is called Multilayer Hex-Cell (MLH). A node addressing scheme and routing algorithm are also presented and discussed. An interesting feature of the proposed MLH is that it maintains a constant network degree regardless of the increase in the network size degree which facilitates modularity in building blocks of scalable systems. The new addressing node scheme makes the proposed routing algorithm simple and efficient in terms of that it needs a minimum number of calculations to reach the destination node. Moreover, the diameter of the proposed MLH is less than Hex-Cell network.
