An Improved Interconnection Network Based on NIN

The Novel Interconnection Network (NIN) based on inverted-graph topology and crossbar switch is a kind of lower latency and higher throughput interconnection network. But it has a vital disadvantage, high hardware complexity. In order to reduce system hardware cost, an improved NIN (ININ) structure is proposed. As same as NIN, ININ has constant network diameter. Besides of keeping advantages of NIN, hardware cost of ININ is lower than NIN. Furthermore, we design a new deadlock-free routing algorithm for the improved NIN. Key words NIN - ININ - inverted-graph interconnection network - hardware complexity - network band-width - network throughput CLC number TP 302 Foundation item: Supported by the National Natural Science Foundation of China (69873016)Biography: Li Fei (1974-), male, Ph. D candidate, research direction: architecture of interconnection network.

Some LCP Decompositions of Multistage Interconnection Networks

Some useful layered cross product decompositons are derived both for general bit permutation networks and for(2n-1)-stage multistage interconnection networks.Several issues in related works are clarified and the rearrangeability of some interesting networks are considered.In particular, the rearrangeability of one class of networks is formulated as a new type of combinatorial design problmes.

Reliability Assessment of a New General Matching Composed Network

The reliability of a network is an important indicator for maintaining communication and ensuring its stable operation. Therefore, the assessment of reliability in underlying interconnection networks has become an increasingly important research issue. However, at present, the reliability assessment of many interconnected networks is not yet accurate,which inevitably weakens their fault tolerance and diagnostic capabilities. To improve network reliability,researchers have proposed various methods and strategies for precise assessment. This paper introduces a novel family of interconnection networks called general matching composed networks(gMCNs), which is based on the common characteristics of network topology structure. After analyzing the topological properties of gMCNs, we establish a relationship between super connectivity and conditional diagnosability of gMCNs. Furthermore, we assess the reliability of g MCNs, and determine the conditional diagnosability of many interconnection networks.

A practical interconnection network RP(k) and its routing algorithms

Based on Petersen graph, a new interconnection network, the RP(k) network, is devel-oped and the properties of the RP(k) network are investigated. The diameter of the RP(k) network is [ k/2] + 2 and its degree is 5. We prove that the diameter of the RP(k) network is much smaller than that of the 2-D Torus network when the number of nodes in interconnection networks is less than or equal to 300. In order to analyze the communication performance in a group of nodes, we propose the concepts of the optimal node groups and the diameter of the optimal node groups. We also show that the diameter of the optimal node groups in the RP(k) network is less than that in the 2-D Torus net-work. Especially when the number of nodes in an optimal node group is between 6 and 100, the diam-eter of the optimal node groups in the RP(k) network is half of that in the 2-D Torus network. Further-more based on the RP(k) network we design a set of routing algorithms which are point-to-point rout-ing, permutation routing, one-to-all routing and all-to-all routing. Their communication efficiencies are [ k/2] +2, k + 5, [k/2] + 2, and k + 5 respectively. The RP(k) network and the routing algorithms can provide efficient communication means for parallel and distributed computer system.

A High-Performance and Cost-Efficient Interconnection Network for High-Density Servers

The high-density server is featured as low power, low volume, and high computational density. With the rising use of high-density servers in data-intensive and large-scale web applications, it requires a high-performance and cost-efficient intra-server interconnection network. Most of state-of-the-art high-density servers adopt the fully-connected intra-server network to attain high network performance. Unfortunately, this solution costs too much due to the high degree of nodes. In this paper, we exploit the theoretically optimized Moore graph to interconnect the chips within a server. Accounting for the suitable size of applications, a 50-size Moore graph, called Hoffman-Singleton graph, is adopted. In practice, multiple chips should be integrated onto one processor board, which means that the original graph should be partitioned into homogeneous connected subgraphs. However, the existing partition scheme does not consider above problem and thus generates heterogeneous subgraphs. To address this problem, we propose two equivalent-partition schemes for the Hoffman-Singleton graph. In addition, a logic-based and minimal routing mechanism, which is both time and area efficient, is proposed. Finally, we compare the proposed network architecture with its counterparts, namely the fully-connected, Kautz and Torus networks. The results show that our proposed network can achieve competitive performance as fully-connected network and cost close to Torus.

Research on reliability index of a large communication network with domain partition and interconnection

In order to indicate the performances of a large-scale communication network with domain partition and interconnection today, a kind of reliability index weighed by normalized capacity is defined. Based on the route rules of network with domain partition and interconnection, the interconnection indexes among the nodes within the domain and among the domains are given from several aspects. It is expatiated on that the index can thoroughly represent the effect on the reliability index of the objective factor and the subjective measures of the designer, which obeys the route rules of a network with domain partition and interconnection. It is discussed that the defined index is rational and compatible with the traditional index.

A New Family of Interconnection Networks of Fixed Degree Three

A new family of interconnection networks WG_n is proposed, that is constantdegree 3 Cayley graph, and is isomorphic to a Cayley graph of the wreath product Z_2\S_n when thegenerator set is chosen properly. Its different algebraic properties is investigated and a routingalgorithm is given with the diameter upper bounded by 3n^2 - 6n + 4. The embedding properties andthe fault tolerance are devired. In conclusion, we present a comparison of some familiar networkswith constant degree 3.

A Kind of Multistage Interconnection Networks with Multiple Paths

Multistage Interconnection Networks (MINs) are often used to provide interconnections in multiprocessor systems. A unique path MIN usually has lower hardware complekity and a simple control algorithm, but it lacks fault tolerance.This paper proposes a kind of multipath MINs, which are obtained by adding auxiliary links at the final stage in Quad nee (QT) networks so that they canprovide more paths between each source-destination pair, and presents theirrouting algorithm which is both destination tag based and adaptive. Starting with the routing tag for the minimum path between a given source-destinationpair, the routing algorithm uses a set of rules to select switches and modifyrouting tag. In addition to trying the andliary link when linko and link1 areunavailable, link1 will be tried when link0 is unavailable. This feattire dis-tinguishing the proposed routing algorithm from that for QT networks makesbetter use of all the possible paths between the given source-destination pair.In the end, this paper introduces a performance index, which is called capacity,to compare different kinds of MINs. Comparison shows that the proposed MINshave better capacity than QT networks.

Panconnectivity for Interconnection Networks with Faulty Elements

Let Go and G1 be two graphs with the same vertices. The new graph G（G0, G1; M） is a graph with the vertex set V（0o） ∪）V（G1） and the edge set E（Go） UE（G1） UM, where M is an arbitrary perfect matching between the vertices of Go and G1, i.e., a set of cross edges with one endvertex in Go and the other endvertex in G1. In this paper, we will show that if Go and G1 are f-fault q-panconnected, then for any f 〉 2, G（G0, G1; M） is （f ＋ 1）-fault （q ＋ 2）-panconnected.

Detailed and clock-driven simulation for HPC interconnection network

Performance and energy consumption of high performance computing （HPC） interconnection networks have a great significance in the whole supercomputer, and building up HPC interconnection network simulation plat- form is very important for the research on HPC software and hardware technologies. To effectively evaluate the per- formance and energy consumption of HPC interconnection networks, this article designs and implements a detailed and clock-driven HPC interconnection network simulation plat- form, called HPC-NetSim. HPC-NetSim uses application- driven workloads and inherits the characteristics of the de- tailed and flexible cycle-accurate network simulator. Besides, it offers a large set of configurable network parameters in terms of topology and routing, and supports router＇s on/off states. We compare the simulated execution time with the real execution time of Tianhe-2 subsystem and the mean error is only 2.7%. In addition, we simulate the network behaviors with different network structures and low-power modes. The results are also consistent with the theoretical analyses.

A General Approach to L(h,k)-Label Interconnection Networks

Given two non-negative integers h and k, an L（h, k）-labeling of a graph G = （V, E） is a function from the set V to a set of colors, such that adjacent nodes take colors at distance at least h, and nodes at distance 2 take colors at distance at least k. The aim of the L（h, k）-labeling problem is to minimize the greatest used color. Since the decisional version of this problem is NP-complete, it is important to investigate particular classes of graphs for which the problem can be efficiently solved. It is well known that the most common interconnection topologies, such as Butterfly-like, Beneg, CCC, Trivalent Cayley networks, are all characterized by a similar structure： they have nodes organized as a matrix and connections are divided into layers. So we naturally introduce a new class of graphs, called （l × n）-multistage graphs, containing the most common interconnection topologies, on which we study the L（h, k）-labeling. A general algorithm for L（h, k）-labeling these graphs is presented, and from this method an efficient L（2, 1）-labeling for Butterfly and CCC networks is derived. Finally we describe a possible generalization of our approach.

Fast Multicast on Multistage Interconnection Networks Using Multi-Head Worms

This paper proposes a new approach for implementing fast multicast on multistage interconnection networks (MINs) with multi-head worms. For an MIN with n stages of k×k switches, a single multi-head worm can cover an arbitrary set of destinations with a single communication start-up. Compared with schemes using unicast messages, this approach reduces multicast latency significantly and performs better than multi-destination worms.

A Scalable Interconnection Scheme in Many-Core Systems

Recent architectures of multi-core systems may have a relatively large number of cores that typically ranges from tens to hundreds;therefore called many-core systems.Such systems require an efficient interconnection network that tries to address two major problems.First,the overhead of power and area cost and its effect on scalability.Second,high access latency is caused by multiple cores’simultaneous accesses of the same shared module.This paper presents an interconnection scheme called N-conjugate Shuffle Clusters(NCSC)based on multi-core multicluster architecture to reduce the overhead of the just mentioned problems.NCSC eliminated the need for router devices and their complexity and hence reduced the power and area costs.It also resigned and distributed the shared caches across the interconnection network to increase the ability for simultaneous access and hence reduce the access latency.For intra-cluster communication,Multi-port Content Addressable Memory(MPCAM)is used.The experimental results using four clusters and four cores each indicated that the average access latency for a write process is 1.14785±0.04532 ns which is nearly equal to the latency of a write operation in MPCAM.Moreover,it was demonstrated that the average read latency within a cluster is 1.26226±0.090591 ns and around 1.92738±0.139588 ns for read access between cores from different clusters.

Research on the Method of Implementing Named Data Network Interconnection Based on IP Network

In order to extend the application scope of NDN and realize the transmission of different NDNs across IP networks,a method for interconnecting NDN networks distributed in different areas with IP networks is proposed.Firstly,the NDN data resource is located by means of the DNS mechanism,and the gateway IP address of the NDN network where the data resource is located is found.Then,the transmission between different NDNs across the IP network is implemented based on the tunnel technology.In addition,in order to achieve efficient and fast NDN data forwarding,we have added a small number of NDN service nodes in the IP network,and proposed an adaptive probabilistic forwarding strategy and a link cost function-based forwarding strategy to make NDN data obtaining the cache service provided by the NDN service node as much as possible.The results of analysis and simulation experiments show that,the interconnectionmethod of NDN across IP network proposed is generally effective and feasible,and the link cost function forwarding strategy is better than the adaptive probability forwarding strategy.

Reliability Analysis of Varietal Hypercube

Connectivity is a vital metric to explore fault tolerance and reliability of network structure based on a graph model. Let be a connected graph. A connected graph G is called supper-κ (resp. supper-λ) if every minimum vertex cut (edge cut) of G is the set of neighbors of some vertex in G. The g-component connectivity of a graph G, denoted by , is the minimum number of vertices whose removal from G results in a disconnected graph with at least g components or a graph with fewer than g vertices. The g-component edge connectivity can be defined similarly. In this paper, we determine the g-component (edge) connectivity of varietal hypercube for small g.