# Introduction nterconnection networks are used to meet the communication demands of the numerous processing elements in high end parallel supercomputers, telecom switches and more recently their wide spread use is also seen for the communication requirement in complex SoC [1] having numerous processing elements. With the development of integration technology, System on Chip composed of numerous cores on a single chip has entered the billion transistor era. As the microprocessor industry moves from single core to multi core architectures, requiring efficient communication among processor. A high performance, flexible, scalable and design friendly interconnection network design is highly preferred for new SoC and chip designs. These interconnection networks for complex SoC also referred as on chip Networks. Network on chip have emerged as a viable option for scheming scalable messaging architecture for MPSOCs .In Noc, on chip micro networks are used to intersect the various cores, which are better than bus based systems, so used for dealing communication issues. Early works are done for standard topologies like mesh, torus etc where traffic cannot be statically predicted however challenges are different for diverse SoC with different core size, operation and communication requirement. In Irregular NoC each node can be connected to one or more core, as per the constraint and design requirement and therefore are best suited for application specific custom NoC design [2,3]. Here we propose a branch and bound [B&B] Author ? ? ?: Deptt. Of CSE, CTAE, MPUAT, Udaipur. e-mails: kalpana_jain2@rediffmail.com, naveenc121@yahoo.com, dharm94@gmail.com based heuristics for the design of customized energy efficient irregular NoC assuming an area optimized floor plan as a prerequisite. # II. # Communication Energy and Design of Irregular Network on Chip has two main issues to be dealt with respect to the proposed work that is calculating energy dissipated through the network for data transfer and finding the routes between the cores of network. Thus here we discuss the Energy Model and Routing methods used. a) Energy Model Ye et al. [4] proposed a model for communication for on chip networks. For regular networks the channels length between the cores is of uniform length. Thus the energy dissipated in transferring 1 bit of data from soured core to destination core comprising of both router energy and channel energy is as follows: Router Energy: (E Rbit ) E Rbit = E Sbit + E Bbit + E Wbit (1) Where E Sbit + E Bbit + E Wbit correspond to the dynamic energy elapsed by switch(E Bbit ), buffering(E Bbit ) and interconnection links (E Wbit ) within the switching framework. The dynamic energy dissipated on the channels between cores (E Lbit ) should also be considered, thus the dynamic energy dissipated in transferring one bit of information from a tile to its adjacent tile can be given as E bit = E Rbit +E Lbit (2) Thus the communication_energy required in sending 1 bit of information from source tile t j to destination tile tile t k is Where nhops is sum of tiles from source tile tj to destination t k and E Lbit is channel length between adjacent tiles (channel length is uniform for all adjacent tiles of regular networks). For irregular networks the channel length is not of uniform (equal), as channels are laid by maximum length constraint of link length. Thus the second operand of eq-3 is replaced as the summation of energy dissipated by each channel in the route of source tile t j to destination tile t k The popular routing algorithms with irregular topologies such as Left-Right routing [8], up -down routing [6] etc, uses the turn based model [7] to overcome deadlock state. In the proposed work minimum shortest paths are laid as preferred routing paths from the source tile to destination tile with a view to optimize communication energy requirements, however a methodology based on escape route [5] is used to achieve deadlock freedom in communication. # III. Proposed Methodology for Energy Efficient Branch and Bound based on Chip Irregular Network Design In the presented work, an energy efficient topology design is proposed. To design the energy efficient topology the, the channels laid should be such that they lead to shortest path for communication, this is achieved by finding the shortest path application communication characteristics, considering the constraints of node degree and length of channel as maximum length should not be exceeded due to physical signaling delay. Moreover the connectivity of network is assured by creating spanning tree for the network and a constraint according to up/down routing, is used to achieve the deadlock freedom in communication. The application characteristics are clustered according to the source traffic, and then using the shortest energy path as the optimization criteria and a branch and bound method is developed to get an customized energy efficient irregular on-chip network then the source with the maximum data rate are routed using shortest path and branch and bound method used to get the optimized solution. The design flow is given in figure 1 shows the input taken for topology synthesizer such as traffic characteristics, constraints and tile coordinates for Manhattan distance to lay the channel. a) Branch and Bound (B&B) Topology Generation A branch and bound [19 ] based optimization technique is developed to design a dynamic communication energy efficient methodology, which is custom tailored according to the traffic requirement (predefined) with the necessary constraints of node degree , channel length and routing. Figure 2 shows the partial representation of nodes generation of tree, traffic requirement is routed at each stage to form the efficient communication energy topology. The nodes of the tree can be one of the following types: UBC and LBC are cost of the nodes which helps us to determine the whether the nodes lead to optimal solution and helps in not making the search exhaustive. Finding optimal solution for the problem of efficient communication energy topology is searching leaf node with minimum cost. Branch is expansion(create child node) at each node by routing next application characteristics to be routed, and bound is check on child nodes whether they lead to the better solution. This checking is achieved by comparing their UBC and LBC with the global UBC and parent node. If cost or LBC is greater than global_min_UBC child nodes are discarded. # Global Journal of Computer Science and Technology Volume XIV Issue IV Version I b) The calculation of UBC and LBC UBC calculation: UBC of node is calculated by finding path of all remaining unrouted traffic characteristics using a greedy method for remaining unrouted traffic characteristics.For each step in the greedy method , the next unmapped application characteristics with highest communication demand is selected and its path is laid by shortest path method. This step is repeated until all application are routed. This leads to a complete routing and identifies a leaf node. If this node is illegal then it is discarded otherwise saved for the future expansion. LBC calculation: LBC of node is calculated by finding path of all remaining unrouted application characteristics, here constraints of topology are not considered in path setup. This step is repeated for all remaining unrouted traffic characteristics. Priority Queue is used to speed up the search for optimal leaf node; the nodes are inserted in sorted order of their cost, once the Queue is full, nodes are inserted only if they are leading to better solution. c) The Proposed methodology: Algorithm IV. # Experimental Results The random data sets required to evaluate the proposed methodology was generated using TGFF [18] with diverse communication data rate of the cores. An On Chip simulator is used for evaluation. The router energy dissipated is evaluated using the power simulator Orion [15,20] for 0.18?m technology. The dynamic bit energy dessipated for inter-node link (ELbit) can be computed using the below equation. E Lbit = (1/2) x ? x C phy x V 2 Where 1. ? = average probability of a one to zero or zero to one transition between two successive samples in the stream for a specific bit, assured average value of ? = 0.5. 2. C phy = physical capacitance of inter-node wire. 3. V DD is the supply voltage. Below graphs shows the evaluation comparison of proposed methodology with Genetic algorithms based methodology proposed [14] by Naveen Choudhary et al. for the similar data sets (tile coordinates and traffic characteristics) with Node_ degree =4 and link length as twice the length of the Maximum core size. Below Graphs shows the performance comparison of Branch and Bound and [14] over 100 sets of diverse application data. Average flit latency gain in the range of 5% to 20% and average communication energy gain in the range of 2% to 10% in comparison to [14] has achieved by the topologies generated by the proposed B&B method. # Conclusion The paper present a B&B based technique for designing an energy efficient custom tailored topology for Irregular on-chip networks. The customized topology is design as per the predefined traffic requirements. The necessary constraint of max node degree, max channel length, deadlock free communication and area optimized floor plan are incorporated in the proposed methodology provides a realistic solution .The results clearly elaborates that the proposed method is able to generate better energy efficient networks in comparison to the popular evolutionary based approach [14]. The proposed work can be further extended in a quite few ways such as incorporating the floor plan also in the proposed methodology which can be expected to provide improved energy efficient networks may be at the cost of increased area overhead. Another extension of the proposed work can be in the area of designing irregular 3D on-chip energy efficient networks. # Global Journal of Computer Science and Technology ![Energy Efficient Branch and Bound basedOn-Chip Irregular Network DesignGlobal Journal of Computer Science and TechnologyVolume XIV Issue IV Version I](image-2.png "I") ![Figure1: Design flow of Energy Efficient Branch and Bound based On-Chip Irregular Network Design](image-3.png "Figure1:") ![Root: traffic characteristics are not routed and represent the problem (energy efficient topology) to be optimized.Internal node: Each number in the label represents the Priority of traffic characteristics which are routed. For example node 201XX represents the partial routing of traffic characteristics with priority number 2, 0, 1. While traffic characteristics with priority 3 and 4 are still unrouted.](image-4.png "") 2![Figure 2 : partial nodes representation of tree. Leaf: All the traffic characteristics are routed and topology is created, select leaf node one with minimum cost. Every node is associated with cost, UBC:Upper bound cost and LBC:lower bound cost Cost: The cost of node is energy consumed in communication for routed traffic characteristics.UBC and LBC are cost of the nodes which helps us to determine the whether the nodes lead to optimal solution and helps in not making the search exhaustive.Finding optimal solution for the problem of efficient communication energy topology is searching leaf node with minimum cost. Branch is expansion(create child node) at each node by routing next application characteristics to be routed, and bound is check on child nodes whether they lead to the better solution. This checking is achieved by comparing their UBC and LBC with the global UBC and parent node. If cost or LBC is greater than global_min_UBC child nodes are discarded.](image-5.png "Figure 2 :") ![Sort the traffic characteristic by communication volume setmin_UBC=infinity,Gcost=infinity , Best_maping=NULL Create first level nodes of for all source traffic if they have any communication demand and insert in the priority queue. While( pqueue is not empty) { curnode= pqueue_next(); for each unrouted traffic characteristics , find the shortest path and create a new child If(newchild_LBC > min_UBC) discard the newchild If(newchild_LBC > parent_UBC) discard the newchild If (newchild is leaf node) { if(Best_maping is NULL) Best_maping=newchild else {if(best_maping.cost > newchild.cost) Set Best_maping to newchild } } Else If(min_UBC > newchild.UBC) set min_UBC= newchild cost Insert newchild into pqueue } Set escape path for given traffic characteristics and construct the tables required for the On Chip simulator.](image-6.png "") ![a. Average Communication Energy per flit b. Average flit latency Global Journal of Computer Science and Technology Volume XIV Issue IV Version I Journals Inc. (US) Energy Efficient Branch and Bound based On-Chip Irregular Network Design](image-7.png "") 34![Figure 3 : Performance comparison of proposed methodology with genetic approach on Random Benchmark. (a)Average Communication Energy per flit and (b) Average flit latency](image-8.png "Figure 3 :Figure 4 :") © 2014 Global Journals Inc. (US) Energy Efficient Branch and Bound based On-Chip Irregular Network Design ## This page is intentionally left blank * An Automated Technique for Topology and Route Generation of Application Specific On-Chip Interconnection Networks KSrinivasan Proc. ICCAD ICCAD 2005 * Analysis of power consumption on switch fabrics in network routers TTYe LBenini GDe Micheli Design Automation Conference IEEE 2002 Proceedings. 39th * High-performance routing in networks of workstations with irregular topology FSilla JDuato IEEE Transactions Parallel and Distributed Systems 11 7 2000 * Efficient adaptive routing in networks of workstations with irregular topology FSilla MPMalumbres ARobles PLópez JDuato Springer Berlin Heidelberg Communication and Architectural Support for Network-Based Parallel Computing 1997 * The turn model for adaptive routing CJGlass LMNi In ACM SIGARCH Computer Architecture News 20 2 1992 * L-turn routing: An adaptive routing in irregular networks MKoibuchi AFunahashi AJouraku HAmano IEEE Parallel Processing InternationalConference 2001 * Networks on chips: a new SoC paradigm LBenini GDe Micheli Computer 1 2002 * Key research problems in NoC design: a holistic perspective UYOgras JHu RMarculescu Proceedings of the 3rd the 3rd 2005 * IEEE/ACM/IFIP international conference on * Hardware/software codesign and system synthesis * Energy-aware mapping for tile-based NoC architectures under performance constraints JHu RMarculescu Proceedings of the Asia and South Pacific Design Automation Conference the Asia and South Pacific Design Automation Conference 2003 * Autonet: A high-speed, self-configuring local area network using point-to-point links MDSchroeder ADBirrell MBurrows HMurray RMNeedham TLRodeheffer CPThacker IEEE 1991 9 * GA based congestion aware topology generation for application specific NoC NChoudhary MSGaur VLaxmi VSingh Sixth References Références Referencias 2011 * Route packets,Not wires: On-chip interconnection International Symposium Electronic Design, Test and Application (DELTA) WJDally BTowles 2001 * Energy aware design methodologies for networks NChoudhary MSGaur VLaxmi VSingh Design Automation Conference. Proceedings IEEE 2010 * SUNMAP: A Tool for Automatic Topology Selection and Generation for NoCs SMurali GDeMicheli Proceeding of DAC. application specific NoC eeding of DAC. application specific NoC 2004 IEEE 28th Norchip Conference Finland * Orion: a power-performance simulator for interconnection HSWang XZhu LSPeh SMalik proc. International Symposium on Microarchitecture International Symposium on Microarchitecture 2002 * NIRGAM: a simulator for NoC interconnects routing and application modeling LJain BMAl-Hashimi MSGaur VLaxmi ANarayanan Design, Automation and Test in Europe Conference 2007 * Energy-and performance-aware mapping for regular NoC architectures JHu RMarculescu IEEE TransactionComputer-Aided Design of Integrated Circuits and Systems 24 4 2005 * TGFF: task graphs for free RPDick DLRhodes WWolf IEEE Computer Society. Proceedings of the 6th international workshop on Hardware/software codesign 1998 * CormenThomas H LeisersonCharles E RivestRonald L SteinClifford 2009 The MIT Press Introduction to Algorithms third edition * _Orion 2.0: a fast and accurate NoCpower and area model for early-stage design space exploration ABKahng BLi LSPeh KSamadi 2009 _ in DATE'09