Network Mapping Optimization Algorithm On Chip

NoC (Network on Chip) is a new solution to the problems caused by the size of chip and on-chip communication demands in very-large scale integrated circuit design. After analyzing the basic principles on NoC, this thesis focuses on the low power consumption and low latency of the NoC mapping problem. A concept of hierarchical mapping is introduced. Consequently, an efficient algorithm is proposed to deal with the mapping problem for searching an optimal solution.In this thesis, the process of mapping is divided into two stages, namely mapping the tasks of an application task graph onto the IP cores, and mapping the IP cores to the locations on the NoC platform. According to the features of the 2D Mesh NoC platform, this paper presents two types of energy consumption and delay models, including coarse ones and precise ones, in order to fit those two different mapping stages. In the first phase of the mapping search, the coarse estimation models for energy consumption and delay are used to evaluate the task assignment, and in the second phase the precise model is adopted since IPs are assigned to specific NoC tiles.NoC mapping is an NP problem. Meanwhile, energy- and latency- aware mapping problem is a Multiple Objective Programming. In order to approach an optimal solution for NoC mapping, the chaotic discrete particle swarm optimization (DPSO) algorithm is adopted. Since chaotic DPSO is a swarm intelligence optimization algorithm, which has the advantages of simple calculation, fast convergence, hardly falling into local optimum, it is suitable to solve the discrete space optimization problems. Conjunction with the evaluation based on the energy consumption and delay models proposed in this paper, chaotic DPSO algorithm can be adopted for the two-stage mapping to find the optimal solution quickly. In the two stages of mapping, some data structures (e.g. NoC-IP table) and rules (e.g. table-exchange) are designed. And a set of suitable procession mechanisms for the two stages are proposed. Thus the problem of how to use the chaotic DPSO to search the optimal solution for NoC is solved.Experiments show that the optimal search algorithm based on chaotic discrete particle swarm optimization is effective in searching for a low-power and low-latency NoC mapping solution.