Simulation and Analysis of Multicast Routing Algorithm for 2-D Mesh Network on Chip

INTRODUCTION

As technology scale, the number of processors integrated on a System on Chip (SoC) is increasing sharply. The continuously increasing number of processors, traditional SoC interconnection became the bottleneck of on chip communication. SoCs also encounter some other challenges like grouping system complexity, negative effect of technology scaling on global interconnect, need to construct flexible multiuse design and platforms. With the large numbers of research on SoC design challenges, Network on Chips (NoCs) has been acknowledged as a solution to these problems. NoC applies the network concepts to SoC architecture design and simultaneously solve the communication bottleneck and also other challenges as we discussed in earlier (Benini and De Micheli, 2002; Dally and Towles, 2001). Recently, NoC architectures are investigated in the concept of network topology, router design and routing algorithms that offers the performance, cost, throughput and power consumptions. In addition to these parameters, some of the routing algorithms are used to find shortest path from source node to destination nodes based on routing techniques such as unicast or multicast (Boppana and Chalasani, 1993; Kowalik and Collier, 2003). Figure 1 shows nxm NoC topology that consists of Router Node, Router Interface, Core Element, Core Interface and Physical Link (Benini and De Micheli, 2006).

Past years different routing techniques had developed for various NoC topologies to eliminate bottleneck, find shortest path and provide Quality of Service. In addition to provide shortest path, another important encountered problem is deadlock.

Fig. 1:	Generic nxm network on chip architecture

This problem is eliminated by odd-even turn model and multiple path technique while increase communication efficiency (Kumar et al., 2002; Chiu, 2000; Carara and Moraes, 2008). Shortest path can also be achieved by balancing traffic among network with low latency and high throughput (Lin et al., 2008). Application specific routing algorithm is used to increase the communication adaptivity and performance while giving shortest path. This algorithm enables specific communication links only based on application and others remain silent (Palesi et al., 2009). Other algorithms such as unicast based, tree-based and path based also proposed to achieve shortest path in multicast messaging (McKinley et al., 1994; Malumbres et al., 1996). This study proposed a new algorithm has been developed and implemented on partitioned NoC takes the advantages of ad-hoc on demand distance vector routing.

NETWORK TOPOLOGIES AND SEGMENTATION

Similarities of NoCs with computer network, possible topologies in NoCs are Tree, Fat Tree, H-Tree, 2D mesh, 3D Mesh, C-Mesh, Ring, Torus, Mesh of Tree and etc. Due to the advantages of Mesh topologies like the addressing of cores quite simple during communication, layout efficacy, predictable result and good electrical properties, we are selecting nxm 2D mesh topology with 36 node counts for this study.

For providing better performance of NoCs, one of the such methods is partitioning of network architectures into several subsets based on Physical concepts (for static and dynamic communications) and Logical concepts (for data and instruction transfers) between the subsets which contains the destination nodes (Lin and Nil, 1993; Mohapatra and Varavithya, 1996). Two dimensional mesh based network looks like matrix, therefore network architecture partitioned with the help of node value (node N = nxm). Each node has its own integer coordinate pair (x, y), where, 0 ≤ x ≤ n and 0 ≤ y ≤ m. Network segmentation is described in Fig. 2. Network is partitioned in to four segment based on node label L(x, y) value of destination nodes; where label L(x, y) = yxn+x. Assume (x₀, y₀) is source node (Violet) and D is destination set. Initially, entire network is partitioned into two sets (D->{DH, DL}) by comparing node label values and each set are divided into two subsets (DH->{DH_L (Red), DH_R (Pink)}, DL->{DL_L (Blue), DL_R (Green)}). All orange colour nodes can be identified as destination nodes.

Fig. 2(a-c):	(a) 6x6 NoC structure, (b) Network partitioning and (c) NoC with 1 source and 9 destinations

Routing methodologies: Routing technique takes the advantages of deciding a path from source to destinations in a particular topology. After deciding network topology scheme, selection of routing algorithm is the next step. Routing algorithms realize the network topology and offer better communication among all the nodes. A good routing technique balances a load across the network channels to provide high throughput. The routing algorithms are classified into deterministic, oblivious and adaptive algorithms in terms of how they select between the set of possible paths from source to destinations. A well designed routing algorithm also keeps path lengths as short as possible, reducing the number of hops and overall message latency, these types of routing algorithms are known as shortest path routing algorithms. These routing techniques can be applied for both unicast and multicast NoC communications (Duato et al., 2003; Liao and Lin, 2008).

More number of routing algorithms had proposed to provide shortest path by many researchers. Some of the earliest algorithms are Dual Path, Multi Path, Column Path, Congestion Minimized Multipath, Distributed Congestion Minimized Multipath, Maxflow and Path Based (PB) shortest path. Based on analysis of all these algorithms, shortest path between source and destinations is achieved with some trade-offs between performance parameters (Al-Dubai and Romdhani, 2006; Al-Mahadeen and Omari, 2004; Xin et al., 2009; Dally and Towels, 2004).

PROPOSED ALGORITHM

Proposed algorithm is developed based on Floyd Wershal Shortest path algorithm for multicast messaging in 2D mesh NoC. The main feature of this algorithm is to provide the lengths between all pairs of nodes and also it is possible to provide a method to reconstruct the actual path between nodes. This algorithm also, utilizes the network partitioning concept which is similar to that of PBSP algorithm but here the shortest path is calculated based on the adjacent hop. The distance is calculated by incorporating three important issues. First, calculate the distance between the nodes to find the neighbor node. Second, choose the next hop neighbor which has the maximum distance from the source, towards the destination. Third, repeat the steps one and two until we find destination. The pseudo code for proposed algorithm is presented below as Algorithm 1. Message routing is to be done by using Ad-hoc On-Demand Distance Vector scheme (AODV). This scheme is called as reactive routing because it determines the routes when path is needed and it is suitable for both unicast and multicast messaging.

Fig. 3:	Message format

Message format: The message format for transmission is described as shown in Fig. 3. It consists of a segment header and a data section in which header section contains ten mandatory fields and optional extension field and data section contains payload data for carried applications. The length of the data section can be calculated by subtracting the combined length of the header and the encapsulating IP segment header from the total IP segment length. And flag register contains 8 bit, CWR (Congestion Window Reduced), ECE (ECN-Echo Indicates), ACK (Acknowledgment), PSH (Push), RST (Reset), SYN (Synchronize Sequence numbers), FIN (No address).