Routing for applications in NoC using ACO-based algorithms

Networks-on-Chips (NoCs) have been used as an interesting option in design of communication infrastructures for embedded systems, providing a scalable structure and balancing the communication between cores. Because several data packets can be transmitted simultaneously through the network, an efficient routing strategy must be used in order to avoid congestion delays. In this paper, ant colony algorithms were used to find and optimize routes in a mesh-based NoC, where several randomly generated applications have been mapped. The routing optimization is driven by the minimization of total latency in packets transmission between tasks. The simulation results show the effectiveness of the ant colony inspired routing by comparing it with general purpose algorithms for deadlock free routing.     

Application Specific Routing Algorithms for Networks on Chip

In this paper we present a methodology to develop efficient and deadlock free routing algorithms for Network-on-Chip (NoC) platforms which are specialized for an application or a set of concurrent applications. The proposed methodology, called Application Specific Routing Algorithm (APSRA), exploits the application specific information regarding pairs of cores which communicate and other pairs which never communicate in the NoC platform to maximize communication adaptivity and performance. The methodology also exploits the known information regarding concurrency/non-concurrency of communication transactions among cores for the same purpose. We demonstrate, through analysis of adaptivity as well as simulation based evaluation of latency and throughput, that algorithms produced by the proposed methodology give significantly higher performance as compared to other deadlock free algorithms for both homogeneous as well as heterogeneous 2D mesh topology NoC systems. For example, for homogeneous mesh NoC, APSRA results in approximately 30% less average delay as compared to Odd-Even algorithm just below saturation load. Similarly the saturation load point for APSRA is significantly higher as compared to other adaptive routing algorithms for both homogeneous and non-homogeneous mesh networks.     

基于拥塞控制的片上网络多播路由算法

为了满足片上网络日益丰富的应用要求,多播路由机制被应用到片上网络,以弥补传统单播通信方式的不足。以Mesh和Torus类的片上网络为例,分析了基于路径的3种多播路由算法(即XY路由、UpDown路由和SubPartition路由算法),并研究了相应的拥塞控制策略。通过模拟实验表明,多播较单播通信具有更小的平均传输延时和更高的网络吞吐量,且负载分配均匀;特别是SubPartition路由算法随着规模增大效果更加明显;提出的多播拥塞控制机制,能更有效地利用多播通信,提高片上网络的性能。     

Energy Efficient Run-Time Incremental Mapping for 3-D Networks-on-Chip

3-D Networks-on-Chip(NoC) emerge as a potent solution to address both the interconnection and design complexity problems facing future Multiprocessor System-on-Chips(MPSoCs).Effective run-time mapping on such 3-D NoC-based MPSoCs can be quite challenging,as the arrival order and task graphs of the target applications are typically not known a priori,which can be further complicated by stringent energy requirements for NoC systems.This paper thus presents an energy-aware run-time incremental mapping algorithm(ERIM) for 3-D NoC which can minimize the energy consumption due to the data communications among processor cores,while reducing the fragmentation effect on the incoming applications to be mapped,and simultaneously satisfying the thermal constraints imposed on each incoming application.Specifically,incoming applications are mapped to cuboid tile regions for lower energy consumption of communication and the minimal routing.Fragment tiles due to system fragmentation can be gleaned for better resource utilization.Extensive experiments have been conducted to evaluate the performance of the proposed algorithm ERIM,and the results are compared against the optimal mapping algorithm(branch-and-bound) and two heuristic algorithms(TB and TL).The experiments show that ERIM outperforms TB and TL methods with significant energy saving(more than 10%),much reduced average response time,and improved system utilization.     

Combining mapping and partitioning exploration for NoC-based embedded systems

Networks on Chip (NoC) have emerged as the key paradigm for designing a scalable communication infrastructure for future Systems on Chip (SoC). An important issue in NoC design is how to map an application on this architecture and how to determine the hardware/software partition that satisfies the performance, cost and flexibility requirements. In this paper, we propose an approach that concurrently optimizes the mapping and the partitioning of streaming applications. The proposed approach exploits multiobjective evolutionary algorithms that are fed by execution performances scores corresponding to the evaluated mappings and partitioning ability to pipeline execution of the streaming application. As result, most promising solutions are highlighted for mapping multimedia applications onto a SoC architecture interconnecting 16 nodes through 2D-Mesh and Ring NoC.     

Ant Algorithms: Theory and Applications

This paper reviews the theory and applications of ant algorithms, new methods of discrete optimization based on the simulation of self-organized colony of biologic ants. The colony can be regarded as a multi-agent system where each agent is functioning independently by simple rules. Unlike the nearly primitive behavior of the agents, the behavior of the whole system happens to be amazingly reasonable. The ant algorithms have been extensively studied by European researchers from the mid-1990s. These algorithms have successfully been applied to solving many complex combinatorial optimization problems, such as the traveling salesman problem, the vehicle routing problem, the problem of graph coloring, the quadratic assignment problem, the problem of network-traffic optimization, the job-shop scheduling problem, etc. The ant algorithms are especially efficient for online optimization of processes in distributed nonstationary systems (for example, telecommunication network routing).__________Translated from Programmirovanie, Vol. 31, No. 4, 2005.Original Russian Text Copyright © 2005 by Shtovba.     

Routing table updating by using intelligent agents

In a network, one of the important problems is making an efficient routing decision. Many studies have been carried out on making a decision and several routing algorithms have been developed. In a network environment, every node has a routing table and these routing tables are used for making routing decisions. Nowadays, intelligent agents are used to make routing decisions. Intelligent agents have been inspired by social insects such as ants. One of the intelligent agent types is self a cloning ant. In this study, a self cloning ant colony approach is used. Self cloning ants are a new synthetic ant type. This ant assesses the situation and multiplies through cloning or destroying itself. It is done by making a routing decision and finding the optimal path. This study explains routing table updating by using the self cloning ant colony approach. In a real net, this approach has been used and routing tables have been created and updated for every node.     

A survey of routing algorithm for mesh Network-on-Chip

With the rapid development of semiconductor industry, the number of cores integrated on chip increases quickly, which brings tough challenges such as bandwidth, scalability and power into on-chip interconnection. Under such background, Network-on-Chip (NoC) is proposed and gradually replacing the traditional on-chip interconnections such as sharing bus and crossbar. For the convenience of physical layout, mesh is the most used topology in NoC design. Routing algorithm, which decides the paths of packets, has significant impact on the latency and throughput of network. Thus routing algorithm plays a vital role in a wellperformed network. This study mainly focuses on the routing algorithms of mesh NoC. By whether taking network information into consideration in routing decision, routing algorithms of NoC can be roughly classified into oblivious routing and adaptive routing. Oblivious routing costs less without adaptiveness while adaptive routing is on the contrary. To combine the advantages of oblivious and adaptive routing algorithm, half-adaptive algorithms were proposed. In this paper, the concepts, taxonomy and features of routing algorithms of NoC are introduced. Then the importance of routing algorithms in mesh NoC is highlighted, and representative routing algorithms with respective features are reviewed and summarized. Finally, we try to shed light upon the future work of NoC routing algorithms.     

Ant colony optimization for routing and load-balancing: survey and new directions

Although an ant is a simple creature, collectively a colony of ants performs useful tasks such as finding the shortest path to a food source and sharing this information with other ants by depositing pheromone. In the field of ant colony optimization (ACO), models of collective intelligence of ants are transformed into useful optimization techniques that find applications in computer networking. In this survey, the problem-solving paradigm of ACO is explicated and compared to traditional routing algorithms along the issues of routing information, routing overhead and adaptivity. The contributions of this survey include 1) providing a comparison and critique of the state-of-the-art approaches for mitigating stagnation (a major problem in many ACO algorithms), 2) surveying and comparing three major research in applying ACO in routing and load-balancing, and 3) discussing new directions and identifying open problems. The approaches for mitigating stagnation discussed include: evaporation, aging, pheromone smoothing and limiting, privileged pheromone laying and pheromone-heuristic control. The survey on ACO in routing/load-balancing includes comparison and critique of ant-based control and its ramifications, AntNet and its extensions, as well as ASGA and SynthECA. Discussions on new directions include an ongoing work of the authors in applying multiple ant colony optimization in load-balancing.     

Deadlock free routing algorithms for irregular mesh topology NoC systems with rectangular regions

The simplicity of regular mesh topology Network on Chip (NoC) architecture leads to reductions in design time and manufacturing cost. A weakness of the regular shaped architecture is its inability to efficiently support cores of different sizes. A proposed way in literature to deal with this is to utilize the region concept, which helps to accommodate cores larger than the tile size in mesh topology NoC architectures. Region concept offers many new opportunities for NoC design, as well as provides new design issues and challenges. One of the most important among these is the design of an efficient deadlock free routing algorithm. Available adaptive routing algorithms developed for regular mesh topology cannot ensure freedom from deadlocks. In this paper, we list and discuss many new design issues which need to be handled for designing NoC systems incorporating cores larger than the tile size. We also present and compare two deadlock free routing algorithms for mesh topology NoC with regions. The idea of the first algorithm is borrowed from the area of fault tolerant networks, where a network topology is rendered irregular due to faults in routers or links, and is adapted for the new context. We compare this with an algorithm designed using a methodology for design of application specific routing algorithms for communication networks. The application specific routing algorithm tries to maximize adaptivity by using static and dynamic communication requirements of the application. Our study shows that the application specific routing algorithm not only provides much higher adaptivity, but also superior performance as compared to the other algorithm in all traffic cases. But this higher performance for the second algorithm comes at a higher area cost for implementing network routers.     

基于蚁群优化的无线传感器网络最适路由算法

如何在资源有限的条件下进行实时、高效的数据路由是无线传感器网络的研究热点之一。针对不同应用设计目标的差异性问题,提出一种基于改进蚁群算法的最适路由选择算法。因设计目标的不同,引入一个新的路由选择度量,兼顾实时性、能源效率和负载均衡等方面,并结合蚁群算法的寻优特点,对无线传感器网络最适路由选择问题进行优化。仿真结果表明,最适路由选择算法能够在满足不同设计目标的前提下,延长网络寿命,实现无线传感器网络实时、高效的路由。     

片上网络路由算法分析与评估

本文对片上网络中的确定性XY路由算法和基于拐弯模型的4种自适应路由算法进行分析,并采用Noxim模拟器在6种合成通信模式下对5种路由算法的性能进行评估。实验结果表明,在均匀随机通信模式下,XY路由算法的性能优于自适应路由算法;在置换1和混洗通信模式下,奇偶路由算法的性能优于其他路由算法;在置换2、位反和蝶形通信模式下,负向优先路由算法的性能优于其他路由算法。     

Improving performance of multi-core NUCA coherent systems using NoC-assisted mechanisms

The significant speed-gap between processor and memory makes last-level cache performance crucial for multi-core architectures (MCA). Non-uniform cache architecture (NUCA) has been proposed to overcome the performance limitations of MCA for many embedded applications. The cache is partitioned into sub-banks, with each sub-bank being an independently accessible entity connected with a fast on-chip network (NoC). This paper presents two NoC-assisted mechanisms to improve the performance and power consumption of NUCA coherence. The first mechanism provides priority-based communication based on the wormhole routing architecture to support NUCA coherence. High-priority coherent packets are transmitted first to save time. The second mechanism offers multicasting communication based on the proposed priority-based NoC to provide efficient cache coherency for NUCA. We dispatch and collect coherence packets at the collecting nodes (CN) to further decrease the number of coherent messages flowing in the NoC. Experimental results show that the priority-based transmission can improve performance by approximately 10?%. The proposed multicasting mechanism can further improve performance and decrease power consumption of the NoC in NUCA by approximately 15?%. The two proposed mechanisms can together enhance the performance by 25?% averagely.     

Preference-based multi-objective evolutionary algorithms for power-aware application mapping on NoC platforms

Network-on-chip (NoC) are considered the next generation of communication infrastructure in embedded systems. In the platform-based design methodology, an application is implemented by a set of collaborative intellectual property (IP) blocks. The selection of the most suited set of IPs as well as their physical mapping onto the NoC infrastructure to implement efficiently the application at hand are two hard combinatorial problems that occur during the synthesis process of Noc-based embedded system implementation. In this paper, we propose an innovative preference-based multi-objective evolutionary methodology to perform the assignment and mapping stages. We use one of the well-known and efficient multi-objective evolutionary algorithms NSGA-II and microGA as a kernel. The optimization processes of assignment and mapping are both driven by the minimization of the required silicon area and imposed execution time of the application, considering that the decision maker’s preference is a pre-specified value of the overall power consumption of the implementation.     

基于蚁群优化算法的NoC映射

功耗问题正逐渐成为NoC领域的研究热点,很多研究人员都在研究NoC功耗最小化的设计技术。文章采用一种有效的蚁群优化算法实现了NoC映射：在自动映射处理单元的同时,尽可能地减少了系统的通讯功耗。实验结果表明采用蚁群优化算法可以很快地收敛;针对不同的应用,可以减少25％-70％通讯功耗。     

Performance-driven assignment and mapping for reliable networks-on-chips

Network-on-chip （NoC） communication architectures present promising solutions for scalable communication requests in large system-on-chip （SoC） designs. Intellectual property （IP） core assignment and mapping are two key steps in NoC design, significantly affecting the quality of NoC systems. Both are NP-hard problems, so it is necessary to apply intelligent algorithms. In this paper, we propose improved intelligent algorithms for NoC assignment and mapping to overcome the draw-backs of traditional intelligent algorithms. The aim of our proposed algorithms is to minimize power consumption, time, area, and load balance. This work involves multiple conflicting objectives, so we combine multiple objective optimization with intelligent algorithms. In addition, we design a fault-tolerant routing algorithm and take account of reliability using comprehensive performance indices. The proposed algorithms were implemented on embedded system synthesis benchmarks suite （E3S）. Experimental results show the improved algorithms achieve good performance in NoC designs, with high reliability.     

An enhanced ant colony optimization (EACO) applied to capacitated vehicle routing problem

In this paper, an enhanced ant colony optimization (EACO) is proposed for capacitated vehicle routing problem. The capacitated vehicle routing problem is to service customers with known demands by a homogeneous fleet of fixed capacity vehicles starting from a depot. It plays a major role in the field of logistics and belongs to NP-hard problems. Therefore, it is difficult to solve the capacitated vehicle routing problem directly when solutions increase exponentially with the number of serviced customers. The framework of this paper is to develop an enhanced ant colony optimization for the capacitated vehicle routing problem. It takes the advantages of simulated annealing and ant colony optimization for solving the capacitated vehicle routing problem. In the proposed algorithm, simulated annealing provides a good initial solution for ant colony optimization. Furthermore, an information gain based ant colony optimization is used to ameliorate the search performance. Computational results show that the proposed algorithm is superior to original ant colony optimization and simulated annealing separately reported on fourteen small-scale instances and twenty large-scale instances.     

QoS multicast tree construction in IP/DWDM optical internet by bio-inspired algorithms

In this paper, two bio-inspired Quality of Service (QoS) multicast algorithms are proposed in IP over dense wavelength division multiplexing (DWDM) optical Internet. Given a QoS multicast request and the delay interval required by the application, both algorithms are able to find a flexible QoS-based cost suboptimal routing tree. They first construct the multicast trees based on ant colony optimization and artificial immune algorithm, respectively. Then a dedicated wavelength assignment algorithm is proposed to assign wavelengths to the trees aiming to minimize the delay of the wavelength conversion. In both algorithms, multicast routing and wavelength assignment are integrated into a single process. Therefore, they can find the multicast trees on which the least wavelength conversion delay is achieved. Load balance is also considered in both algorithms. Simulation results show that these two bio-inspired algorithms can construct high performance QoS routing trees for multicast applications in IP/DWDM optical Internet.     

一种带侦察子群蚁群算法的无线传感路由协议

针对无线传感器网络（WSNs）路由面临安全威胁和节点能量有限的不足,提出一种基于引入侦察子群的改进蚁群算法（SACO）路由协议。通过改进的蚁群算法构造一条数据传输链,选择其中能量最大节点为簇头,信息通过相邻节点传送。结果显示：该算法兼顾到节点的能量和路径消耗,较标准蚁群算法和贪婪算法具有高效的路由选择功能,能够使网络中节点能量消耗更加均衡,从而延长网络的使用寿命。     

蚁群算法研究与应用的新进展

蚁群算法是一种源于大自然生物界的仿生进化算法,具有自组织性、正反馈性、较强的鲁棒性和分布式计算等特性,且易于与其它算法相结合,在众多的复杂组合优化领域中有着广阔的应用前景。首先对蚁群算法的理论及其重要参数进行了阐述,继而分析了其在参数优化和智能融合方面的改进与应用;然后对其在车间作业调度问题、车辆路径问题、图像处理、电力系统优化等领域的应用进展进行了综述;最后对其理论研究和应用领域可能存在的问题及对策进行了探讨和展望。