Efficient Evolutionary Algorithms for Network on Chip Systems

Efficient Evolutionary Algorithms for Network on Chip Systems

M. Keirthi1,

1PG Scholar, Department of ECE,

SSM Institute of Engineering and Technology, Dindigul, Tamilnadu, India

1. Karthigai Lakshmi 2,

   2Professor, Department of ECE,

   SSM Institute of Engineering and Technology, Dindigul, Tamilnadu, India

   Abstract-NETWORK-ON-CHIP (NoC) provides a ready architecture for scalable on-chip communication. In advanced Network-on-Chip systems, the decline constrains the on-chip bandwidth and network throughput. Fault aware routing algorithms aim to alleviate the impact on performance. This paper proposes to systematically analyze the performance related parameters of Ant Colony Optimization based Fault Aware Routing and Biogeography-based Krill Herd algorithms and hence a comparative study is made between the algorithms employed to improve the performance of the network on chip systems.

   Keywords: Ant Colony Optimization, Biogeography-Based Krill Herd, Network on Chip, Fault Aware Routing.

   1. INTRODUCTION

      Network on Chip (NoC or NOC) is a communication subsystem on an integrated circuit (commonly called a "chip"), typically between intellectual property (IP) cores in a system on a chip (SoC). NoCs can span synchronous and asynchronous clock domains or use unlocked asynchronous logic. NoC technology is often called a front-end solution to a back-end problem. As semiconductor transistor dimensions shrink and increasing amounts of IP block functions are added to a chip, the physical infrastructure that carries data on the chip and guarantees quality of service begins to crumble. Many of today's systems-on-chip are too complex to utilize a traditional hierarchal bus or crossbar interconnect approach. The vitality of NOC and SOC is equally important for any system. Moreover, there are four basic advantages that are associated to this integration.

      • Higher Operation Frequencies: When the NOC chip is linked with the SOC of a system then it is going to simplify the hardware applications by reducing the routing functions making the SOC interconnect with the NOC so that they can function promptly at higher operation frequencies. Similarly, a SOC is always embedded in a long sensitive path which need precise placement of such chips so that the IP of the system is not affected because of the integration. NOC is acclaimed to be globally asynchronous locally SOC (GALS) that allows the electronic module to operate in a synchronous manner maintaining a clockwise connection in- between them.

      • Reduced Wiring Congestions: Routing a particular data with the SOC requires a lot of wiring; this

        increases the wiring congestions causing a lot of complications for the system. This is where Network on chips can act as a lifesaver, because when a Network on chip is connected with the SOC then they significantly reduce the wiring connections that are required by the system to function.

      • Change IP at an Extreme Ease: A system quite often faces semiconductors Intellectual property block, so when you have integrated the circuit with the NOS then you can swap the IP blocks without any trouble. This allows the chips to respond in a timely manner and even makes sure that the embedded system is working in accordance to the protocol of the unit. In a small network unit the NOC interfaces with the synthesized targeted IP block, so that other topologies that are part of the system can function in an efficient manner.

      • Ease Timing Closure: When the NOC is precisely placed in the SOC framework then it can easily function in accordance to the timing closure without affecting the chip in any manner.

      Fig. 1. Routing on a Chip System

      For improving the reliability, a routing algorithm to achieve maximum performance under fault is proposed. This paper proposes fault aware routing algorithm. Routing is the process of selecting best paths in a network. In order to avoid congestion delays various routing algorithms are used. In this paper, the simulation result shows the effectiveness of the Biogeography based Krill Herd algorithm by comparing it with Ant Colony Optimization based Fault Aware Routing.

   2. ACO BASED FAULT AWARE ROUTING

      Ant colony optimization (ACO) is a population-based metaheuristic that can be used to find approximate solutions to difficult optimization problems. In ACO, a set of software agents called artificial ants search for good solutions to a given optimization problem. A probabilistic technique for solving computational problems which can be reduced to find good paths through graphs.

      Fig.2. Ant behavior

      Ants secrete pheromone while traveling from the nest to food, and vice versa in order to communicate with one another to find the shortest path.

      ACO based FAR algorithm is inspired by the fault-tolerant behavior of ant colony, which consists of three steps: 1) encounter; 2) search; and 3) select. Initially, the ants follow the original pheromone trail, and cannot proceed forward because of the obstacle. Then, they search for other available paths in arbitrary directions to detour from the obstacle. After a short period of discovering, more and fresher pheromone accumulates on the shorter detour. As a result, the ants would select this new path to bypass the obstacle.

      The process of fault aware routing is as follows:

      1. Notification Mechanism of Fault Information: We propose a low-cost dynamic notification mechanism to collect and propagate the fault information to neighboring region of the faulty node in the network.

      2. ACO-Based Fault-Aware Path Searching Mechanism: To identify legal routing path based on

      the fault information and provides as much path diversity as possible; this mechanism searches for possible paths to neighboring nodes except for faulty paths.

      ACO-Based Fault-Aware Path Selecting Mechanism: To evaluate the congestion condition of the routing paths and relieve the traffic congestion around the faulty nodes, this mechanism integrates the congestion and regional fault information into ant pheromone to select the better path.

      Fig.3. ACO routing operation

   3. BIOGEOGRAPHY BASED KRILL HERD

      Krill herd algorithm is a new meta-heuristic approach for solving high dimensional nonlinear complicated functions. In KH, the krill-related objective functions are mainly determined by the distances of each krill from food and optimal density of the herd. The krills position mainly includes three actions:

      1. Movement led by other krill

      2. Foraging motion, and

      3. Physical diffusion

         The improvement involves introducing a new krill migration (KM) operator when the krill updating to deal with optimization problems more efficiently.

         An improved habitat migration operator originally used in BBO performing local search, called krill migration (KM) operator, is combined with KH to form an effective biogeography-based krill herd (BBKH) approach. In BBKH, the KM operator is used to regulate the new solution generated by KH for each krill; while randomness is used in KH.

         In BBKH, to begin with, due to its fast convergence, KH is applied to make the krill cluster to a limited area. After that, the KM operator with good exploitation is used to search locally to choose better krill. In essence, the KH in BBKH centralizes on the exploration at early stage of the optimization; while later, the KM operator emphasizes the exploitation and makes most krill cluster around the best solution at the later of the optimization.

         The proposd algorithm can greatly enrich the diversity of krill population and improve the calculation accuracy, which leads to a good optimization performance.

         Fig.4. BBKH routing process

   4. EXPERIMENTAL RESULTS

      BBKH has much better ability to deliver the packets in the faulty network, because of its fully adaptive routing function that provides higher path diversity to tolerate the fault and it can also improve the packet delivery ratio.

      PDR=(1-rand/(10+length(field)))*100

      Fig.5. Packet Delivery Ratio

      The reduced latency can be evaluated using this formula,

      Latency=Trouter × H + Tcongestion

      Fig.6. Latency

   5. CONCLUSION

Fault Aware Routing algorithms has been proposed to tolerate on-chip failures, increase network throughput, and decrease total latency of network. The proposed BBKH algorithm provides higher path diversity and fault-awareness than ACO-FAR. Packet Delivery Ratio was found and based on this the other parameters are measured. ACO-FAR also balance the distribution of traffic flow in the faulty network and increases the packet delivery ratio.

REFERENCE

1. Colorni, M. Dorigo, V. Maniezzo and M. Trubian, Ant system for job- Shop scheduling, JORBEL-Belgian J. Oper. Res., Statist. Conzp. Sci., vol. 34, no. 1, pp. 39-53.

2. E.Bonabeau,M.Dorigo,andG.Theraulaz,Inspirationforoptimization from social insect behavior, Nature, vol. 406, pp. 3942, July 2000.

3. Z.W. Geem, J.H. Kim, G.V. Loganathan, A new heuristic optimization algorithm: harmony search, Simulation 76 (2) (2001) 6068.

4. M. Dorigo, E. Bonabeau, and G. Theraulaz, Ant algorithms and stigmergy, Future Gener. Comput. Syst., vol. 16, no. 8, pp. 851871, 2000.

5. C. Fallin, X. Yu, G. Nazario, and O. Mutlu, A high performance hierarchical ring on-chip interconnect with low-cost routers, Computer Architecture Lab (CALCM), Carnegie Mellon University, Tech.Rep., 2011.

6. S. Lee, Deadlock detection and recovery for true fully adaptive routing in regular wormhole networks, Journal of Information Science and Engineering, pp. 465-479, 2009.

7. H.-K. Hsin, E.-J. Chang, C.-H. Chao, and A.-Y. Wu, Regional ACO- based routing for load-balancing in NoC systems, IEEE Second World Congress on Nature and Biologically Inspired Computing, Dec. 2010.

8. G. Wang, L. Guo, A novel hybrid bat algorithm with harmony search for global numerical optimization, J. Appl. Math. 2013 (2013) 121.

9. D. Zou, J. Wu, L. Gao, et al., A Modified Differential Evolution Algorithm for Unconstrained Optimization Problems, Neurocomputing 120 (2013) 469481.