الگوریتم های هیوریسیک جدید برای نرم افزار نقشه برداری انرژی آگاه و مسیریابی در ورزشکار و توری مبتنی بر شبکه بر روی تراشه

Ever shrinking technologies in VLSI era made it possible to place several IP (Intellectual Property) blocks onto a single die. This technology improvement also brought the challenge of inventing new communication methods since traditional bus-based systems suffer from signal propagation delays, signal integrity, and scalability on these large platforms. Network-on-Chip (NoC) is the biggest step towards the solution of this communication bottleneck of System-on-Chip (SoC) architectures. Topology selection is the very first step of designing NoC systems and mesh topology is the commonly accepted topology type for NoCs. However, mapping applications represented by the weighted task graphs onto the mesh architectures is an NP-hard problem. In this paper, we present a new low complexity heuristic algorithm, CastNet, for the application mapping and bandwidth constrained routing algorithm for mesh-based NoC architectures aiming to minimize the energy consumption. We compared the presented approach with the one that generates the optimal solutions and two existing heuristic methods. Our experiments on multimedia benchmarks show that the proposed mapping algorithm obtains optimal or, in worst case, within 6% to the optimal solutions in very short times.

Rapid improvements in VLSI technology sizes made it possible to integrate multiple components of an electronic system on a single chip. Such a system that contains several components (e.g. processors, memory blocks, analog interfaces, DSPs, etc.) is called System-on-Chip (SoC) [1]. The increase in the number of IP (Intellectual Property) blocks on a SoC platform and high throughput demand of today’s applications forced the designers to investigate new communication methods as a superior alternative to the traditional bus-based or point-to-point based communication structures. In the beginning of this millennium, Network-on-Chip (NoC) technology, also known as on-chip interconnection network (OCIN), has been proposed [2] for parallel execution of system components to meet the system needs for performance, power consumption, and high throughput. NoC inherits the traditional computer network concepts and mimics it on the SoC platforms for on-chip communication. Several studies and real industrial implementations demonstrated the substantial performance gain of the NoC systems over conventional bus based systems. However, NoC system design methodologies are still in their early phases and there are several problems ahead to be solved such as the need for synthesis tools for topology generation or selection; for optimal, fault-tolerant, deadlock free routing mechanisms; and for mapping and scheduling algorithms [3]. Selecting the most suitable topology for the given application is the first step in designing a NoC architecture. This synthesis step is not trivial since the optimization parameters such as energy, cost, and performance may vary from one topology to another. Additionally, the flow control and the routing mechanisms depend heavily on the selected topology. The topologies for NoC architectures can be categorized into two main groups based on their architectural structures; namely, regular topologies and irregular topologies. Mesh, torus, fat tree, butterfly topologies are the examples for the regular topologies [4]. The irregular topologies are custom generated topologies based on the communication structures of the application [5]. Irregular topologies demonstrate better performance characteristics than their regular counterparts since they are costumed for the given application allowing more optimization area. However, they lack the reusability. Additionally, the design procedures of the regular topologies are simpler than irregular topology generation. Existing industrial interconnection networks use different regular topologies such as ring [6] and [7], crossbar [8], and mesh [9]. One important point to note is that the final product of the design procedure will be a 2D VLSI implementation of the network. Thus, we must avoid topologies that results in die stacking, which introduces need for 3D networks. A simple, regular mapping to 2D VLSI implementation, and most commonly used topology for the NoC systems is the mesh topology. In a mesh topology, the cores (or the components of the system) are connected to each other in a grid fashion. Intel’s teraflops chip is one good example that uses mesh topology for its 80 cores that are connected in a 8×108×10 grid. The leading researchers from academia and industry proposed the next generation chip multiprocessor (CMP) of the year 2015, which is also build on a mesh topology of size 16×1616×16[10]. After selecting the topology and its flow control mechanism for the application, the next step is mapping the tasks of the application onto the cores of the mesh and selecting a deadlock free routing path between communicating tasks. Mapping an application onto the mesh architecture is known to be NP-hard. If the number of cores on the target architecture has enough cores for the given application, n!n! different solutions can be found for the application with n tasks. There have been several algorithms presented so far [11], [12], [13], [14], [15], [16] and [17] for the problem of application mapping onto the mesh architectures. These methods use different optimization techniques such as integer linear programming (ILP) [11], heuristic methods [12] and [13], simulated annealing [16], and genetic algorithms [17] to minimize the total communication cost or the total energy consumption of the system. Some of these methods [11], [12], [13] and [15] have high complexities resulting in huge increase in computation times. Some of them [16] and [17] do not guarantee optimal results and may not obtain desirable solutions. In this paper, we propose a new low complexity heuristic algorithm called CastNet for the application mapping onto the mesh based Network-on-Chip architectures. Our algorithm aims to map highly communicating tasks close to each other aiming to minimize the path the data travel through. To do this, it first analyzes the mesh architecture based on its dimensions and determines the initial mapping positions for the first task. Then, it gives a priority to each task on the application graph. After the first task is mapped on to the initial core, our algorithm maps remaining tasks one by one based on their communication weight between mapped tasks. We next present a routing table-based deterministic routing method that runs under bandwidth constraints. The routing algorithm uses the mapping result from our previous step and aims to minimize the required bandwidth of the system. We tested our CastNet algorithm on several real benchmarks and custom generated graphs and in the worst case, we obtained energy consumption results within 6% to the optimal solutions. We also evaluated the performance of our routing algorithm by comparing it with XY, odd–even, and west-first algorithms. The remaining of this paper is organized as follows. We give the problem definition and a motivational example in Section 2. We explain the details of our mapping and routing algorithms in Sections 3 and 4, respectively. We present the complexity analysis of our algorithms in Section 5. We give our experimental results illustrating the effectiveness of our approach in Section 6. Finally, we conclude this paper in Section 7.

In this paper, we presented new low complexity heuristic algorithms for application mapping and routing onto mesh based Network-on-Chip architectures. We compared the presented approach with the one that generates optimal solutions and with two previous heuristic methods. Our experiments showed that proposed mapping algorithm obtains optimal or very close to optimal solutions in a short time. We also compared our routing table based routing algorithm with XY, Odd–Even, and West First routing algorithms. Our routing algorithm performs as well as odd–even routing algorithm.