# INTRODUCTION he shrinking feature sizes in silicon technologies is making possible the integration of complex systems-on Chip (SoC), offering a remarkable amount of computational power. In order to address the design complexity and assist reuse, these systems are usually built from predesigned and preverified building blocks like general-purpose processor, a DSP, a memory subsystem, etc. Functionality of these systems is generally captured by a set of communicating tasks at a high level of abstraction. These tasks are mapped to computational resources which are interconnected by an underlying communication infrastructure. or regular based on their underlying communication infrastructure / topology. This communication infrastructure or topology impacts both performance and implementation costs of the system in terms of silicon area and energy consumption to a substantial extent. A large number of NoC architectures have been proposed based on regular building patterns ; Kumar, Jantsch, Soininen, Forsell, Millberg, Oberg, Tiensyrja & Hemani, 2002; Natvig, 1997) like meshes, tori, k-ary n-cubes or fat trees for the implementation of on-chip networks to overcome conventional bus-based designs. However regular topologies may not be appropriate where communication requirement are not uniformly distributed across cores and links. Moreover most application specific SoCs are designed with static (or semi-static) mapping of tasks to processors or hardware cores and consequently the communication requirements of the SoC can be well characterized at design time. Therefore, the NoCs with irregular topology customized to the application's requirements is expected to be the preferred choice for application specific SoC platforms. The routing function in NoC based systems is tightly coupled to the underlying topology defining the set of allowed paths on which packets may be sent from a sender to the destination core. The proper selection of the adequate topology and routing function form a key decision in the design of the overall NoC architecture. Conventionally, the proof of deadlock-freedom has mostly been carried out on the assumption of the regular topology (Dally & Seitz, 1987;Glass & Ni, 1992;Duato, Yalamanchili & Ni, 2003) and is far more complicated for NoC with underlying irregular topology. However in the NoC research domain some routing functions based on turn prohibition (Glass & Ni, 1992) methodology are proposed for irregular topology based NoCs such as prefix routing (Wu & Sheng, 1999), up*/down* (Schroeder et al. 1991), Left-Right (Jouraku, Funahashi, Amano & Koibuchi, 2001), L-turn (Jouraku, Funahashi, Amano & Koibuchi, 2001) and down/up (Sun, Yang, Chung & Hang, 2004). In this paper, two genetic algorithm based heuristics are proposed for the design of energy efficient customized irregular topology Networks-on-Chip based on the applied routing function for application having IP cores with varying communication bandwidth requirements. The presented methodologies exploit the predefined communication requirements of the application to generate energy efficient customized NoC along with the routing tables for supporting deadlock free communication. It is worth mentioning here that the topology and routing table generation are tightly coupled aspects of the NoC design and therefore optimization of only one aspect or one after another may lead to suboptimal solutions. The paper is organized as follows. A brief account of related work is presented in Section II. Communication model and architecture for Irregular NoC are defined in Section III. The proposed genetic algorithm based energy efficient NoC design methodologies are presented in Section IV. The Genetic Algorithm used in the proposed methodologies is described in Section V. Experimental results are presented in Section VI followed by a brief conclusion in Section VII. # II. # RELATED WORK Methods to collect and analyze traffic information that can be fed as input to the bus and NoC design processes have been presented in (Lahiri et al. 2004) and (Murali & De Micheli, 2005). Mappings of cores onto standard NoC topologies have been explored in (Murali & DeMicheli, 2004;Hansson et al. 2005;Hu & Marculescu, 2003;Murali et al. 2005). In (Murali & DeMicheli, 2004;Murali et al. 2005) a floorplanner is used during the mapping process to get area and wire-length estimates. These works only select from a library of standard topologies, and cannot generate a fully customized topology. In (Hansson et al. 2005), a unified approach to mapping, routing and resource reservation has been presented. However, the work does not explore the topology design process. Important research in macro networks has considered the topology generation problem (Ravi et al. 2001). As the traffic patterns on these networks are difficult to predict most approaches are tree-based (like spanning or Steiner trees) and only ensure connectivity with node degree constraints. These techniques cannot be directly extended to address the NoC synthesis problem. Application-specific custom topology design has been explored in (Pinto et al. 2003;Ho & Pinkston, 2003;Ahonen et al. 2004;Srinivasan et al. 2005). The works from (Pinto et al. 2003;Ho & Pinkston, 2003), do not consider the floorplanning information during the topology design process. In (Ahonen et al. 2004), a floorplanner is used during topology design to reduce power consumption on wires. It does not consider the area and power consumption of switches in the design. Also, the number and size of network partitions are manually fed. In (Srinivasan et al. 2005), a slicing tree based floorplanner is used during the topology design process. This work assumes that the switches are located at the corners of the cores and does not consider the network components (switches, network interfaces) during the floorplanning process. Actual sizes of the cores in (Srinivasan et al. 2005; Srinivasan, & Chatha 2005) are considered only after generating their relative positions. The resulting floorplan can be extremely area inefficient when compared to the standard floorplanning process. In (Choudhary, N et al. 2010), a methodology to generate Bandwidth Aware NoC topology according to the application requirement is proposed. This methodology does floorplanning as the first step with high priority and later accomplishes topology generation with better traffic load distribution across the channels of the NoC leading to reduced congestion as well as hot spots in the topology. A range of issues in the design methods and tools for efficient synthesis of application specific Network-on-Chip interconnect for 3D SoC were addressed in . In addition to the above, one of the major challenges for successful adoption of the Network-on-Chip paradigm is in reducing the energy consumed during the interaction between the IP cores. In (Hu & Marculescu, 2003;, Hu and Marculescu have presented an energy-aware mapping algorithm to minimize the total communication energy cost for a 2-D mesh NoC architecture under real-time performance constraints. Similarly in (Choudhary, N., Gaur, M. S., Laxmi, V., Singh, V. (2010)) a deterministic methodology of order O(n2) to generate energy efficient NoC topology is proposed. This methodology also does floorplanning as the first step with highest priority as in (Choudhary, N et al. 2010). However due to its deterministic nature the methodology is not capable to generate energy optimized NoC topology for all the given applications. The work in (Choudhary, N., Gaur, M. S., Laxmi, V., Singh, V. ( 2010 Definition 2 : NoC topology graph is a directed graph N (U, F) with each vertex ?i ?U representing a node/tile in the topology and a directed edge fi,j ?F represents direct communication channel between vertices ?i and ?j. Weight of the edge fi,j denoted by bi,j represents the available link/channel bandwidth across the edge fi,j. The energy model (Hu & Marculescu, 2003) for the regular Network-on-Chip can be defined as Follows : (1) Where E bit (t i , t j ) is the average dynamic energy consumption for sending one bit of data from tile ti to tile t j , n hops is the number of routers the bit traverses from tile t i to tile t j , Er bit is the energy consumed by router for transporting one bit of data and El bit is the energy consumed by link/channel for transporting one bit of data. In case of Irregular NoC with unequal length (2) Where the 2nd term of the summation in equation ( 2) represent the bit energy consumed by each channel in the route, the bit follows from communication source core to the intended destination cores. For optimized chip layout, floorplanning according to desired metric like area can be done as a first step with the help of available floorplannning tools such as B*-Trees (Chang, Chang, Wu & Wu, 2000; Lin & Chang, 2005). The presented work uses the escape path based routing function as proposed by (Silla & Duato, 2000). To provide deadlock free communication in the NoC, the up*/down* routing (Schroeder et al. 1991;Silla et al. 1997) and Left-Right routing (Jouraku, Funahashi, Amano & Koibuchi, 2001) were used. These routing functions assign direction to the channels of the NoC with the help of a spanning tree of the give NoC topology. In (Silla & Duato, 2000), a generic methodology for designing adaptive routing function for Irregular NoC was proposed. The proposed methodology allow messages to follow minimal paths, in most cases, reducing message latency and increasing network throughput (Duato, Yalamanchili & Ni 2003). Moreover the methodology enforces the deadlock free route to be followed only when the minimal path is occupied by other traffic/packet. This methodology assumes that all the physical channels in the NoC can be split into two virtual channels i.e. original virtual channel and the new virtual channel. Moreover the presence of a given deadlock free routing functions based on turn prohibition (Glass & Ni, 1992) for the given irregular NoC is also assumed. The methodology further proposes to extend the given routing function in such a way that newly injected messages can use new channels without any restriction as long as the original channels are used exactly in the same way as in the original routing function. In this paper original channels are made to use deadlock free paths based on up*/down* (Left-Right) deadlock free routing functions and new channels are allowed to follow the shortest available path to the destination. The modified routing function allows a packet arriving on a new channel following shortest path to be routed to any channel without any restrictions but preferably with higher priority to new channels as new channel assure shorter paths and higher adaptively (flexibility). If no new channels are available due to congestion, one of the original channels following up*/down* (Left-Right) must be provided. However, once a packet acquires an original channel following up*/down* (Left-Right) path, it is not allowed to do transition to a new channel anymore to avoid deadlock situation. Assuming over the cell routing (Srinivasan & Chatha, 2006), the link length among the nodes in the chip layout can be taken according to Manhattan distance. In both the proposed methodologies, the link/channel length is not allowed to exceed the maximum permitted channel length (e max ) due to constraint of physical signaling delay. This also prevents the algorithm from inserting wires that span long distances across the chip. Also, the nodes of the generated topology are not allowed to exceed a given maximum permitted node-degree (nd max ). This constraint prevents the algorithm from instantiating slow routers with a large number of I/O-channels that would otherwise decrease the achievable clock frequency due to internal routing and scheduling delay of the router. # IV. DESIGN METHODOLOGIES FOR ENERGY EFFICIENT NOC GENERATION # a) Minimum Spanning Tree First (MSTF) Methodology In this proposed methodology to generate the energy efficient customized topology, first a minimum spanning tree (MST) using Prim's algorithm (Cormen, Leiserson & Rivest, 1990) is generated on the nodes of the Core Graph according to information regarding the Manhattan distance from the floorplan with the constraints on nd max and e max . The node/core with maximum bandwidth requirement is assumed as the root of the tree. The minimum spanning tree in the topology helps us in classifying all the channels/links of the topology as "up" ("Left") or "down" ("Right"). The following phases of MSTF methodology helps in extending the network/topology for energy efficient deadlock free communication. Aware Topology Extension Phase : While keeping the constraints on nd max and e max , the topology is further extended by laying the shortest energy path for each traffic characteristics (edges corresponding to pair of nodes in the Core Graph). Due to constraints on nd max and e max , the order in which such shortest energy paths are generated basically decides the total communication energy requirement of the generated topology. The optimized order of traffic characteristics of the application is found using a genetic algorithm (refer next section). The routing tables of nodes/routers in the discovered shortest energy path are updated with the routing table entry type tag as shortest path. Deadlock Avoidance Phase : Lastly the proposed methodology uses the modified Dijkstra's algorithm (Cormen, Leiserson & Rivest, 1990) according to up*/down* (Left Right) rule for finding deadlock free escape routing paths from each node in the shortest energy path to the corresponding destination in the generated NoC and tags them as up*/down* (Left-Right). While taking routing decision the output channels tagged as shortest path are selected with higher priority and up*/down* (Left Right) tagged channels are selected only when no output channel corresponding to shortest path is free. b) Shortest Path First (SPF) Methodology SPF is similar to MSTF methodology with the exception that in SPF the topology generation is initiated by first finding the shortest energy path and later the topology is extended by constructing the MST. As in Energy Aware Topology Extension Phase of MSTF, a genetic algorithm is used to find the optimized energyefficient traffic characteristics order of the application. Since in MSTF, MST is constructed first, it is possible that a large number of links for a number of nodes/cores in the topology are the links pertaining to MST. As maximum links emanating from a node is limited to ndmax, this phenomenon can lead to increased value of hop count in the shortest energy paths generated later leading to increased communication energy. However the SPF overcomes this drawback by creating the links pertaining to shortest energy path before the links September pertaining to MST. As shortest energy paths in the topology are generated first in SPF and so there can be a possibility that not enough number of free ports is available to construct the MST in the topology later. In such case a minimum number of ports per node/core need to be reserved before finding the shortest energy paths. However experiments showed that if communication requirement are uniformly distributed over the Core Graph then such problems are rare if any. Algorithm 1 briefly presents the proposed methodologies. # VII. GENETIC ALGORITHM A genetic algorithm (Eiben & Smith, 2003) based heuristic is used to find the best order of the traffic characteristics to generate the shortest energy paths in topology such that the communication energy requirement of the application is optimized. Genetic algorithm is a search technique used in determining exact or approximate solutions to optimization and search problems. Genetic algorithms are a particular class of evolutionary algorithms which uses techniques inspired by evolutionary biology such as inheritance, mutation, selection, and crossover. The proposed genetic algorithm explores the search space extensively to generate an irregular topology with optimized communication energy requirement for the given application. The proposed genetic algorithm formulation is as follows. # a) Solution Space In formulation of the proposed methodology, each chromosome is represented as an array of genes. Maximum size of the gene array is equal to the number of edges in the Core Graph. Each gene of the chromosome represents a traffic characteristic (an edge corresponding to a pair of nodes in the Core Graph) b) Initial Population A large population (i.e. 500 chromosomes) of chromosome is initially generated. The chromosomes of the initial population are generated by assigning traffic characteristics of the application to the chromosome's gene array in some random order. The initial population is later sorted according to the increasing order of total communication energy requirement of the generated topology (chromosome). It is worth highlighting here that the communication energy consumption by a chromosome varies depending on the traffic characteristics order (order of elements in gene array) of the chromosome. # c) Crossover In each generation, crossover is performed on 50% of the population with the bias towards the Best Class of the chromosome population. For achieving crossover of two chromosomes, a random crossover point is selected. Two new chromosomes are created by the crossover operation. The new chromosomes are created by copying the traffic characteristics (genes) from their respective parents till crossover point or from crossover point to the end of the chromosome and then the remaining traffic characteristics (genes) are copied according to the order of traffic characteristics (genes) in the other chromosome such that there are no duplicate traffic characteristics in the created chromosomes. # d) Mutation In each generation, mutation is performed on 40% of the population to avoid the solution from getting stuck up in the local minima. Two types of mutations with probability of 50% each are performed in each generation. In first type of mutation a gene in the gene array of the chromosome with highest energy requirement is swapped with a randomly selected gene of the chromosome. In second type two randomly selected genes in the gene array of the chromosome are swapped. # e) Measure of Fitness The cost function used to measure the fitness of the chromosomes in the population can be formulated as under. Where X is maximum chromosome energy requirement among all the chromosomes in the population, Ec i is the energy requirement for chromosome c i . Fitness of chromosome is regarded as high if its cost approaches 0. It may be noted that, the best 10% chromosomes (referred as Best Class) in any generation are directly transferred to the next generation so as not to degrade the solution between the generations. Algorithm 2 briefly presents the proposed genetic algorithm formulation. After genetic algorithm methodology is made to run for a required number of generations, the NoC topology and routing tables corresponding to the best output chromosome are accepted as the customized energy optimized application specific NoC. # VIII. EXPERIMENTAL RESULTS The generated energy aware application specific topology was evaluated with respect to the communication energy consumption with applied traffic load on the NoC simulation framework. In order to obtain a broad range of different irregular traffic scenarios, multiple Core Graphs using TGFF (Dick, Rhodes & Wolf, 1998) were randomly generated with diverse bandwidth requirement of the IP Cores. For performance comparison, a NoC simulator IrNIRGAM, the extended version of NIRGAM (Jain, Al-Hashimi, Gaur, Laxmi & Narayanan, 2007; Jain 2007) supporting irregular topology with the provision of supporting escape path routing for avoiding deadlock condition, was deployed. IrNIRGAM is a discrete event, cycle accurate simulator. IrNIRGAM supports irregular topology framework with source and table based routing in a wormhole switching based architecture wherein an IP Core is directly connected to a dedicated router. In IrNIRGAM, input buffered routers can have multiple virtual channels (VCs) and uses wormhole switching for flow control. The packets are split into an arbitrary number of flits (flow control units) and forwarded through the network in a pipelined fashion. A Round-Robin scheme for switch arbitration is used in the router nodes to provide fair bandwidth allocation while effectively preventing scheduling anomalies like starvation. For performance comparison on experimental set, the IrNIRGAM was run for 10000 clock cycles with applied packet injection interval to evaluate the network performance with varying traffic load. The energy consumption by the flits reaching their corresponding destination and flit latency were used as performance metric. The energy consumption by router X Ec Cost i / = in transmitting a bit is evaluated using the power simulator orion (Kahng, Li, Peh & Samadi, 2009) for 0.18?m technology. Similarly the dynamic bit energy consumption for inter-node links (Elbit) can be calculated using the following equation. Where ? is the average probability of a 1 to 0 or 0 to 1 transition between two successive samples in the stream for a specific bit. The value of ? can be taken as 0.5 assuming data stream to be purely random. Cphy is the physical capacitance of inter-node wire under consideration for the given technology and VDD is the supply voltage. Figure 7 shows that SPF consistently performs better in comparison to BA-TGM as far as average dynamic communication energy consumption by flits reaching their destination is concerned. The SPF showed on average a reduction of 38.6% for the communication energy per flit in comparison to BA-TGM. # CONCLUSION In this paper, the energy efficient customized Irregular topology generation problem for NoC was addressed. Two genetic algorithm based novel methodologies are proposed for generating the NoC topology with optimized communication energy requirements according to the traffic characteristics of the given application. Although in this paper up*/down* and Left-Right routing were used as escape path for deadlock prevention, we argue that the proposed methodologies can be adapted with any of the topology agnostic routing algorithms where generic routing rules based on turn prohibition can be enforced. It is believed that the combined treatment of the routing and topology generation as done in the presented methods offers a huge potential of optimization for future applicationspecific NoC architectures. Some interesting extensions of the proposed design can be to combine the topology generation with the task partitioning/scheduling into the presented framework to make the design more adaptable to the dynamic communication requirement of the application in such a way that the computation and communication energy consumption can be optimized at the same time. ![The basic platform for the proposed methodology including the basic communication model assumed along with the associated NoC architecture and routing function are described in this section. The mapping of tasks in Task graphs (Hu & Marculescu, 2003; Dick, Rhodes & Wolf, 1998) to the actual physical IP cores in the NoC topology graph (NoC) can be done with the help of intermediate mapping to Core Graph as exhibited in Figure 1. The Core Graph and NoC topology graph can be defined as follows.](image-2.png "") 1![Fig.1 : Application specific communication model for NoC. Definition 1 : Core Graph is a directed graph, G (V, E) with each vertex ?i ?V representing an IP core and a directed edge ei,j ? E, representing the communication between the cores ?i and ?j. The weight of the edge ei,j denoted by bi,j, represents the desired average bandwidth requirement of the communication from ?i and ?j.Definition 2 : NoC topology graph is a directed graph N (U, F) with each vertex ?i ?U representing a node/tile in the topology and a directed edge fi,j ?F represents direct communication channel between vertices ?i and ?j. Weight of the edge fi,j denoted by bi,j represents the available link/channel bandwidth across the edge fi,j.The energy model(Hu & Marculescu, 2003) for the regular Network-on-Chip can be defined as](image-3.png "Fig. 1 :") 2![Fig.2 : Network construction using GA based Based on the routing scheme presented by Silla et. al.(Silla & Duato, 2000), two novel genetic algorithm based methodologies referred as MSTF (minimumspanning-tree-first) & SPF (shortest-paths-first) for energy efficient NoC topology generation are presented in this section. The presented methodologies generate an energy efficient customized NoC topology along with the required routing tables to provide deadlock free communication according to the communication requirement of the application under consideration. In both the presented methodologies, information from the floorplan and Core Graph exhibiting the chiplayout and traffic characteristics respectively are taken as inputs as exhibited in Figure2.Assuming over the cell routing (Srinivasan & Chatha, 2006), the link length among the nodes in the chip layout can be taken according to Manhattan distance. In both the proposed methodologies, the link/channel length is not allowed to exceed the maximum permitted channel length (e max ) due to constraint of physical signaling delay. This also prevents the algorithm from inserting wires that span long distances across the chip. Also, the nodes of the generated topology are not allowed to exceed a given maximum permitted node-degree (nd max ). This constraint prevents the algorithm from instantiating slow routers with a large number of I/O-channels that would otherwise decrease the achievable clock frequency due to internal routing and scheduling delay of the router.](image-4.png "Fig. 2 :") ![2011 Global Journals Inc. (US) Global Journal of Computer Science and Technology Volume XI Issue XVI Version I 50 2011](image-5.png "©") 1![MSTF & SPF Design MethodologyRequire : 1. ?=CG = Core Graph = {E edges (i.e. traffic characteristics), V vertices}2. V = {v i | v i is i th IP core} 3. E = {e ij : v i ? v j with weight bw ij | v i (source), v j (destination) ? V} ??? . 4 = NoC = {T (Topology), R (Set of routing tables), S (set of shortest path)} 5. TC_Array = {Array of traffic characteristic (i.e. ordered set of E)} 6. nd max = Maximum permitted node degree in the topology T 7. e max = The maximum permitted length of a link(channel) in topology T 8. Manhattan Distance = Î?"= {d ij | d ij = |v i -v j |, v i , v j ? V} 9. Manhattan Distance greater than e max are not considered. Ensure : Energy Aware NoC Topology for CG Procedure Minimum-Spanning-Tree-First () ??? ? .NoC EA ; // initialize the energy aware NoC (i.e. NoC EA ) ? NoC EA .T = ?; NoC EA .R = ?; NoC EA .S = ?; ? Î?" = {minimum spanning tree as per Î?" with constraint nd max & e max , root is node with maximum communication in ?} ? NoC EA .T = NoC EA .T ? {Î?"} ? (NoC EA , TC_Array) = GeniticAlgo(NoC EA , Î?") ? for each path s i ? S in NoC EA .S o N = {set of nodes in path s i } o for n j ? N ? NoC EA .R =NOC EA . R ? {update routing tables in NOC EA . R for nodes ? V in the root followed by the shortest up*/down* (Left-Right) escape path from node n j to the destination node of path s i . The routing](image-6.png "Algorithm 1 :") 2![Genetic Algorithm (GA) formulation of energy aware application specific NoC generator procedure GeniticAlgo( ??? NoCEA, T Î?") ? ? = % of chromosomes for mutation ? ? = % of chromosomes for crossover ? ? = % of chromosomes retained in next generation ? G = {gene array[] | size(gene array[]) = | E | (i.e. | traffic characteristics |)} ? C = chromosome = {G (set of genes), ??? (corresponding NoC )} ? Chromosome Population = CSet = {C i | C i is i th chromosome with gene array G i and associated NoC ???i}](image-7.png "Algorithm 2 :") 3![Fig.3 : Performance comparison with varying packet injection interval of (a) communication energy consumption (in pico joules) and (b) Average flit latency (in clock cycles) of the proposed Minimum-Spanning-Tree-First (MSTF) and Shortest-Path-First methodologies (SPF). The performance of the proposed Shortest-Path-First Methodology (SPF) and Minimum-Spanning-Tree-First Methodology (MSTF) were compared on the IrNIRGAM simulation framework with varying packet injection interval (i.e. varying communication traffic load).Figure 3 shows performance results averaged over 50 generated energy efficient irregular topologies generated based on up*/down* routing function with varying number of cores from 16 to 81, ndmax = 4 and](image-8.png "Fig. 3 :") 4![Fig.4 : Performance comparison with varying packet injection interval of dynamic communication energy consumption (in pico joules) of the (a) MSTF and MSTF (Deterministic) and (b) SPF and SPF (Deterministic). The performance of the proposed Genetic algorithm based Shortest-Path-First Methodology (SPF) and Minimum-Spanning-Tree-First Methodology (MSTF) were compared with deterministic methodologies MSTF (Deterministic) and SPF (Deterministic) proposed in (Choudhary, N., Gaur, M. S., Laxmi, V., Singh, V., 2010) of order O(n2). IrNIRGAM simulation framework was run for 10000 clock cycles with varying packet injection interval (i.e. varying communication traffic load) .Figure 4 shows comparison of the dynamic communication energy consumption by the proposed methodologies and the work proposed in (Choudhary, N., Gaur, M. S., Laxmi, V., Singh, V., 2010). The experimental results were averaged over 50 generated customized irregular topologies generated based on up*/down* routing](image-9.png "Fig. 4 :") 46![Fig.5 : MSTF performance comparison with 2D-Mesh (a) Average flit latency (in clock cycles) and (b) Average communication energy consumption per flit (in pico joules)](image-10.png "Figure 4 showsFig. 6 :") 6![shows the SPF performance results. The SPF with up*/down* (Left-Right) routing shows © 2011 Global Journals Inc. (US) Global Journal of Computer Science and Technology Volume XI Issue XVI Version I latency in the range of 10 (9.4) clocks to 20.9 (18.4) clocks and 13.8 (13.2) clocks to 76 (69) clocks in comparison to 2D-Mesh with XY and OE routing respectively. D. Experiments on SPF, 2D-Mesh, and BA-TGM The per flit dynamic communication energy consumption for proposed SPF and Bandwidth Aware Topology Generation Methodology (referred as BA-TGM) presented in (Choudhary, N. et al., 2010) are compared for 50 generated customized irregular topologies with cores having varying sizes and ndmax of 4 for number of cores varying between 16 to 81. For BA-TGM, up*/down* routing was assumed whereas for SPF escape path based up*/down* routing was used. The emax was taken as 1.5 times the length of the core having maximum length among all the cores of the NoC.](image-11.png "Figure 6") 7![Fig.7 : Comparison of average communication energy consumed by flits in reaching their destination for BA-TGM and SPF with ndmax = 4 IX.](image-12.png "Fig. 7 :") entrytype tag is set as up*/down* (Lef -Right) for these nodes} Endprocedure o endfor ? endfor Procedure Shortest-Paths-First ( ) ??? ? .NoC EA ; // initialize the energy aware NoC (i.e. NoC EA ) ? NoC is set as up*/down* (Lef -Right) for these nodes} o endfor ? endfor endprocedureEA .T = ?; NoC EA .R = ?; NoC EA .S = ?; ? Î?" = ? ; ? (NoCEA, TC_Array) = GeniticAlgo(NoC EA ,Î?") ? Î?" endprocedure © 2011 Global Journals Inc. (US) © 2011 Global Journals Inc. (US) Global Journal of Computer Science and Technology Volume XI Issue XVI Version I SeptemberEnergy Efficient Network Generation for Application Specific Noc © 2011 Global Journals Inc. (US) Global Journal of Computer Science and Technology Volume XI Issue XVI Version I 52 * Topology optimization for application specific networks on chip TAhonen Proceedings SLIP SLIP 2004 * Networks on Chips: a new SoC paradigm LBenini GDemicheli IEEE Comput 2002 35 * Networks on Chips: a new SoC paradigm LBenini GDemicheli IEEE Comput 2002 35 * B*-Trees : a new representation for nonslicing floorplans YCChang YWChang GMWu SWWu Proceeding of 37th Design Automation Conference eeding of 37th Design Automation Conference 2000 * Introduction to algorithms TCormen CLeiserson RRivest 1990 Prentice Hall International * Route packets, not wires: on-chip interconnection networks WJDally BTowles IEEE Proceedings of the 38th Design Automation Conference (DAC) 2001 * Deadlock-free message routing in multiprocessor interconnection networks WDally CSeitz IEEE Transactions on Computers 1987 * TGFF: task graphs for free RPDick DLRhodes WWolf Proceeding of the International Workshop on Hardware/Software Codesign eeding of the International Workshop on Hardware/Software Codesign 1998 * Interconnection networks: an engineering approach JDuato SYalamanchili LNi 2003 Elsevier * Introduction to evolutionary computing AEEiben JESmith 2003 Springer-Verlag Berlin, Heidelberg * The turn model for adaptive routing CGlass LNi Proceeding of 19¬th International Symposium on Computer Architecture eeding of 19¬th International Symposium on Computer Architecture 1992 * A unified approach to constrained mapping and routing on network-onchip architectures AHansson Proceeding of ISSS eeding of ISSS 2005 * A methodology for designing efficient on-chip interconnects on wellbehaved communication patterns WHHo TMPinkston HPCA US 2003. 2011 * Global Journal of Computer Science and Technology Volume XI Issue XVI Version I 55 2011 * energy-aware mapping for tile-based NoC architectures under performance constraints JHu RMarculescu ASP-DAC 2003 * Energy-and performance-aware mapping for regular NoC architectures JHu RMarculescu In IEEE Trans. on CAD of Integrated Circuits and Systems 24 4 2005 * Network on Chip simulator: NIRGAM LJain 2007. October 17. 2010 * NIRGAM: a simulator for NoC interconnect routing and application modelling LJain BMAl-Hashimi MSGaur VLaxmi ANarayanan 2007 In proceedings of DATE * AJouraku AFunahashi HAmano MKoibuchi L-turn routing: an adaptive routing in 2001 * Energy Efficient Network Generation for Application Specific Noc irregular networks Proceeding of the International Conference on Parallel Processing eeding of the International Conference on Parallel essing * BKahng BLLi SPeh KSamadi 2009 * Orion 2.0: a fast and accurate NoC power and area model for early-stage design space exploration Proceedings DATE DATE * A network on chip architecture and design methodology SKumar AJantsch JPSoininen MForsell MMillberg JOberg KTiensyrja AHemani Proceedings of VLSI Annual Symposium VLSI Annual Symposium 2002 ISVLSI 2002 * Design space exploration for optimizing on-chip communication architectures KLahiri IEEE TCAD 2004 23 * TCG : A transitive closure graph-based representation of general floorplans JMLin YWChang IEEE Transactions on VLSI Systems 2005 * An applicationspecific design methodology for STbus crossbar generation SMurali GDe Micheli Proceedings DATE DATE 2005 * Mapping and physical planning of networks on chip architectures with quality-of-service guarantees SMurali Proceedings ASPDAC ASPDAC 2005 * SUNMAP: a tool for automatic topology selection and generation for NoCs SMurali GDemicheli Proceeding of DAC eeding of DAC 2004 * Synthesis of networks on chips for 3d systems on chips SMurali CSeiculescu LBenini GDe Micheli Asian and South Pacific Design Automation Conference (ASPDAC) 2009 * High-level architectural simulation of the torus routing chip LNatvig Proceedings of the International Verilog HDL Conference the International Verilog HDL ConferenceCalifornia 1997 * Fast Energy Aware Application Specific Network-on-Chip Topology Generator NChoudhary MSGaur VLaxmi VSingh Proceeding of the IEEE International Conference IACC eeding of the IEEE International Conference IACCPatiala, India 2010 * Genetic Algorithm Based Topology Generation for Application Specific Network-on-Chip NChoudhary Proceeding of the IEEE International Conference ISCAS eeding of the IEEE International Conference ISCASParis, France 2010 * Key research problems in NoC design: a holistic perspective UOgras JHu RMarculescu IEEE CODES+ISSS 2005 * Efficient Synthesis of Networks on Chip APinto ICCD 2003 * Approximation algorithms for degree-constrained minimum cost network design problems RRavi Algorithmica 2001 31 * Autonet: a highspeed self-configuring local area network using point-to-point links MDSchroeder In Journal on Selected Areas in Communications 9 1991 * CSeiculescu SMurali LBenini GDe Micheli SunFloor 3D: a tool for networks on chip topology synthesis for 3d systems on chip. In Proceedings DATE 2009 * Efficient adaptive routing in networks of workstations with irregular topology FSilla Proceedings of the Workshop on Communications and Architectural Support for Network-Based Parallel Computing the Workshop on Communications and Architectural Support for Network-Based Parallel Computing 1997 * High-performance routing in networks of workstations with irregular topology FSilla JDuato IEEE Transactions on Parallel and Distributed Systems 2000 * Layout aware design of mesh based NoC architectures KSrinivasan KSChatha Proceedings of 4th International Conference on Hardware Software Codesign and System Synthesis 4th International Conference on Hardware Software Codesign and System SynthesisSeoul, Korea 2006 * An automated technique for topology and route generation of application specific on-chip interconnection networks KSrinivasan Proceedings ICCAD ICCAD 2005 * ISIS: A genetic algorithm based technique for custom onchip interconnection network synthesis KSrinivasan KSChatha Proceedings of 18th International Conference on VLSI Design 18th International Conference on VLSI DesignKolkata, India 2005 * An efficient deadlock-free tree-based routing algorithm for irregular wormhole-routed networks based on turn model YMSun CHYang YCChung TYHang Proceeding of International Conference on Parallel Processing eeding of International Conference on Parallel essing 2004 * Deadlock-free routing in irregular networks using prefix routing JWu LSheng DIMACS (Tech. Rep.) 1999