A New Proposed Interconnection Topology: C2Mesh

A New Proposed Interconnection Topology: C2Mesh

1Rashmi H.U, 2Harshitha N.U, 3 Bindu.N.S

1,2B.E Student, Dept. of ECE

3Assistant professor, Dept. of E&C

1, 2,3Vidyavardhaka College of Engineering, Mysore, India rashmihasini9@gmail.com

harshithauthappa@gmail.com bindu.ns5@gmail.com

Abstract: Center-Connected mesh is a recent and a quite advanced interconnection topology. The performance of the c2 mesh technology is improved and has an edge over the simple 2D mesh and torus interconnection topologies. This paper focuses on the features of the center connected mesh topology. It also provides a detailed analysis of its architectural potential in terms of routing algorithms. The n*n c2 mesh has different topological properties which have been given primary importance here.

Index words: Mesh, Torus, Interconnection networks, routing.

1. INTRODUCTION

   The various network elements can be connected in different topologies like star, ring, mesh, tree topology etc. Among all the technologies the mesh topology is the most simple and efficient network topology. The network performance decreases drastically as the size of the mesh increases and also due to large network diameter and little bisection width [6]. In Torus network the diameter of the network is reduced but there is an increase in the bisection width and structural complexity. In order to overcome the above mentioned drawbacks some improved network topologies, like Dmesh [5], Dtorus [5], Xmesh[6] and SDTorus [6] have been proposed by adding some extra links [1],[3]. All these network topologies are usually very complex to design and are quite expensive.

   One of the important properties that all the network topologies should satisfy is the scalability property which states that the number of nodes requiredimmediately must be supported by the network and also there should be scope for improvement without causing any overhead. In order to enhance the scalability property and make the network complex the Center-connected Mesh (C2Mesh) network was proposed. The C2Mesh network has good topological properties compare to previous proposed networks.

   This paper is organized into different sections- Section 2 discusses related work, Section 3 describes theproposed network topology and its topological properties. Section 4 explainsthe routing algorithm for n×n C2Mesh. Finally, Section 5 concludes the work.

2. DISCRIPITION

   The layout pattern of the interconnections between the computers in a network is called as the network topology or network architecture. Devices on the network are referred to as nodes. The most common nodes are computers and peripheral devices. The mesh network is very simple and hence it is the most suitable network topology for small scale interconnections. In a mesh network each node is connected to every other node of the network. The figure1 shows a simple mesh network.

   Figure1: A simple Mesh

   The increase in the size of the network results in the increase of the network diameter and reduction in the bisection width. As a result the performance and the efficiency of communication between the nodes degenerate rapidly [6]. The DMesh and DTorus networks were introduced in order to promote the performance and scalability of the both Mesh and Torus network [5].By adding diagonal links to an ordinary mesh network a DMesh network can be constructed easily shown in figure 2.. In a DMesh network, each inner node has a degree of eight, and each peripheral node has adegree of three or five.

   Figure 2: An N = 5 x 5 diagonal mesh network in X-Y coordinates

   The DTorus topology reduces the network diameter [5]. For the purpose of network on chip a special Mesh-like topology known as XMesh, was

   Sub-section-A, provides the physical connection of C2Mesh using node numbers and subsection- B, explain the physical connection C2Mesh using 2D addressing.

   C2Mesh using node numbers

   In this method consider that all nodes has a unique number, where first node having the number 0 and is referred to as node(0) and second node having 1 and is referred to as node(1) and so on. In the n×n network, last node will have n×n -1 number so it is referred to as node (n×n -1), figure-4 shows how to design the n×n C2Mesh, first design simple n×n 2DMesh, and find the center , connect all four corner nodes to the center node(s). The center of the mesh can be calculatedas follows:

   introduced and its routing algorithm is called XM [6]. By adding some diagonal edges on the Mesh

   Center =

   ( 1)

   2

   topology, the average distances of the Xmesh network is reduced. The figure 3 shows the network diagram of XMesh. Given the same network size, XMesh has the same edge number with Torus topology [6]. The very regular and symmetrical interconnection network is The SD- Torus network [6]. Adding two extra diagonals to a 2D-Torus network the results in a SD-Torus network. Extra diagonals links from northwest to southeast direction are connected. Therefore each node increases its node degree with two extra edges. The DMesh, DTorus, the XMesh and SD- Torus, are still complicated and cost effective due to network design and implementation point of view and especially for its routing algorithm, because high node degree networks also leads to high cost.

   Figure3: XMesh Network Diagram

3. C2MESH NETWORK

   When the corner nodes of a simple 2D Mesh is connected to the center nodes of mesh, center connected mesh will be formed. Thus we need four extra edges to design the n×n C2Mesh. To design a nxn Torus mesh 2n additional edges are required, when compared to a basic nxn mesh.

   One of the important advantages of c2 mesh is that it requires only four extra links irrespective of the sizeof the mesh. This has reduced the implementation cost.

   (1) 1

   2

   And if n is odd then center= (n*n-1)/2, and corners will be connected as follows: North-West corner will connect to node(center), North- East corner will connect to node(center), West-South corner will connect to node(center), South-East corner will connect to node(center), Means all corners will connected to single center node, figure-4.

   Fig.-4: n×n C2Mesh for odd n=5.

   If n is even than center = n*(n-1)/2-1, and the corners will be connect as follows: North-West corner will connect to node (center), North- East corner will connect to node (center +1), West- South corner will connect to node (center +n), and South-East corner will connect to node (center

   +(n+1)), figure-5.

   Fig. 5: n×n C2Mesh for even n=6.

   1. C2Mesh using 2D addressing scheme.

      In this method consider that network is in 2D matrix form and all nodes has a unique address in the form of node(i, j),such as first node having the address (0,0) and refer as node(0,0) and second node having address (0,1) and referred as node(0,1) and so on. In the n×n network, last node will have address (n-1,n -1) so will refer as node(n- 1, n -1),figure-6.To design the n×n C2Mesh, first design simple n×n 2DMesh by this addressing scheme, and find the center to connect all four corner nodes to center node(s). The center address (i,j) of the mesh can be calculated as follows:

      = 1 , =

      connected to node(i,j+1), West-South corner will connect to node(i+1,j), and South- East corner will connect to node(i+1,j+1),figure-7

      Figure-7 n×n C2Mesh for even n=6.

   2. Topological Properties

      For C2Mesh network topology with n×n nodes, it has the following topological properties.First of all C2Mesh ntwork is simple as Mesh, with four extra edges, while it perform like as Torus. It can be seen in the figure-1 and figure-2. The design and implementation is simple and easy like Mesh. Secondly, the diameter of C2Mesh network with n×n nodes is n-1 in all cases, except n is 2 or 4. In the case when n is 2 or 4, than its diameter is equal to n. From the distance distribution for the given node in C2Mesh network in figure-1 (b) and figure 2 (b), we can see in that, the maximum distance

      between two nodes in the C2Mesh network is n-1.

      (i, j)= 2

      = 1, =

      2

      If n is odd than i = (n-1)/2 , j = I, and the corners will be connect as follows: North-West corner will connect to node(i,j),North-East cornerwill connect to node(i ,j), West- South corner will connected to node(i, j), and South-East corner will connected to node(i, j),means all corners connected to single center node,figure-3.

      Fig. 6: n×n C2Mesh for odd n =5.

      If n is even than i = n/2-1, j = i, and the corners will be connect as follows: North-West corner will connect to node(i,j),North-East corner will

      Third, the bisection width of C2Mesh network with n×n nodes is n in the case of even n, and n+3 in the case of odd n. The bisection width is smallest with compare to other networks. To divide a C2Meshnetwork with n×n nodes into two equal sets of nodes, is easy when n is even but when n is odd, a horizon and vertical line can be drawn along with the center node of the network, let see figure- 8.

      1. 6×6 C2Mesh

   Figure-7 n×n C2Mesh for even n=6.

   In the table-1, the topological properties comparison for different networks is given. Comparing with the other networks, with the same size n×n node, the C2Mesh network has the same diameter as the torus, Mesh, Dmesh, Dtorus, and XMesh networks. The cost of a network is typically measured in terms of the number of links and the complexity of the routing nodes. For C2Mesh network with n×n nodes, has node degree 4 with some nodes of degree 3, but when n is even, 4 nodes has degree 5, and when n is odd only one, center node has degree 8.

4. ROUTING ALGORITHM

   The best feature of C2Mesh network with n×n nodes, is the shortest path from any source to any destination is maximum n-1, it means the shortest path length of any source to any destination node is not more than n it will be always less than n (except if n =2 or 4).

   To design n×n Torus, then it requires 2n extra links then n×n Mesh while in the n×n C2Mesh topology requires only 4 extra links, and it is fixed for any size of C2Mesh. In order to design the routing algorithm, we have implemented both methods using node numbers and using 2D addressing, but both methods uses the following set of steps: Routing Algorithm for C2Mesh (CCM routing):routing_CCM(src_node, dest_node)

   1. Find centers of C2Mesh.

   2. Find the corner nodes of C2Mesh.

   3. Find sub-meshes-1 for src_node and sub-mesh-2 fardest_node.

   4. Move from src_node to center node of the sub- mesh-1if (distance of corner node +1 < distance of centernode)move from src_node to corner node than dest_node maximum n 1, it means the shortest path length of any source to any destination node is not more than n it will be always less than n (except if n =2 or 4).direct tocenter nodeelse move from src_node to center node to dest_node

5. CONCLUSION

   The C2Mesh network is a simple improved mesh network where all four corner nodes are connected to the center of Mesh. The C2Mesh network provides the network diameter n-1 in large networks, and it provides good performance then Mesh and similar to

   Torus. The further study will focus on the evaluation of C2Mesh network performance with other networks.

6. REFERENCES

1. Tang K W, Padubidri S A., Diagonal and toroidal mesh networks, IEEE Transactions on Computers, 1994, 43(7), pp. 815-826

2. Dally W J, Towles B., Principles and practices of interconnection networks, San Francisco, CA, USA:Morgan Kaufmann, 2004

3. Ogras U Y, Marculescu R., It's a small world after all: NoC performance optimization via long-range link insertion, IEEE Transactions on Very Large ScaleIntegration (VLSI)

   Systems, 2006, 14(7), pp. 693-706

4. Zhu X J, Hu W W, Ma K, et al., XMesh: mesh-like topology for network on chip, Journal of Software, 2007, 18(9): 2194-2204.

5. Ouyang Y M, Zhu B, Liang H G, et al, Networks on chip based on diagonal interlinked mesh topology structure,

   Computer Engineering, 2009, 35(22), pp. 100-102

6. Ya-gang WANGa, Hui-min DUb, Xu-bang SHENa, Topological properties and routing algorithm for semi- diagonal torus networks, The Journal of ChinaUniversities of Posts and Telecommunications, Volume 18, Issue 5,

   October 2011, pp.6470

7. C2Mesh : New Proposed Topology Lalit Kishore Arora1, Rajkumar