Reseach On Layout Optimization For Network On Chips Based On Intelligent Algorithms

Network on chips(NoCs) effectively solve the complex communication problems between the multicores of system on chips(SoCs) using the packet switching method from computer networks instead of the traditional bus method, realizing the separation of processing units and communication structures. NoCs have attracted increasing attentions for their excellent properties. The layout structures of NoCs greatly affect the performances of the systems. The layout structure is associated to some system characteristics such as the average distance between IPCore(Intellectual Property Core) processing units, communication path length, traffic distribution and so on. These characteristics also affect the performance indices of systems such as power consumption, area, delay, throughput, load balance and so on.The important steps of the NoC layout, IPCore assignment, IPCore mapping and optimizing routing algorithm, are NP problems. These kinds of problems are difficult to obtain satisfactory solutions by using traditional optimization algorithms, so intelligent algorithms usually are used for solving these problems. Intelligent algorithms are applied to all kinds of optimization problems widely, one of important research trends of intelligent algorithms currently is the fusion of a variety of intelligent algorithms, proposing the algorithms with merits of many algorithms and applying them to solve optimization problems.In this dissertation, the layout optimization of NoCs based on intelligent algorithms are studied, focusing on NoC layout optimization modeling, IPCore assignment, IPCore mapping, fault tolerance mechanism, routing algorithm, topology structure. The main contents are as follows:(1) According to the requirements and constraints of NoC layouts, the optimization models are established. The evaluation models for IPCore assignment include: computing time, computing power consumption and area. The evaluation models for IPCore mapping include: communication time, communication power consumption, load balance and reliability. These models can reflect the design requirements.(2) To improve reliabilities and performances of NoC systems, according to the features of NoC communication and faults, a fault-tolerant mechanism is designed by using spatial redundancy and adaptive fault-tolerant routing. This fault-tolerant mechanism can recover the communication interruptions caused by switching node failures, improving system reliabilities. The fault-tolerant routing algorithm ensures the performance requirements of the fault-tolerant paths, avoiding deadlocks, obtaining the shortest paths and balancing communication loads.(3) According to the requirements of IPCore assignment, the schemes of IPCore assignment are designed, with the goal of reducing computing time, computing power consumption and area. Two intelligent algorithms for IPCore assignment are designed, one is multi-objective PSO with diversifying strategies(MPDS), the other is multi-objective PSO enhancing locality algorithm(MPEL). These two algorithms process parallel tasks by the critical path method, combing the multi-objective optimization strategies with intelligent optimization ideas. The diversifying and enhancing local searching strategies are introduced into standard intelligent algorithms. These algorithms take advantages of particle swarm optimization(PSO), genetic algorithm(GA) and simulated annealing(SA), overcoming the shortcomings of easily falling into local optimum of traditional single intelligent algorithms. The experimental results show the proposed algorithms, compared with other traditional single intelligent algorithms, have obtained more higher quality IPCore assignment schemes.(4) IPCore mapping is arranging IPCores to the processing unit positions in the NoC structure, constructing NoC topologies based on routing algorithms. According to the requirements and constraints of IPCore mapping layouts, with the goal of improving communication time, communication power consumption, reliability and load balance, the multi-objective scatter search algorithm with uncertainty strategies(MSSU) is proposed. The algorithm uses a controllable mechanism instead of the complete random search of traditional intelligent algorithms. It is based on a small group, introducing the non-dominated sorting method, realizing muilti-objective optimization. This algorithm takes advantages of Scatter Search(SS) and GA, its searching capability is better than other single intelligent algorithms. The simulation results show the proposed algorithm has obtained more higher quality IPCore mapping schemes compared with other common single intelligent algorithms.(5) The reconfigurable NoC structure based on Petersen graph is first proposed. The goal of the reconfigurable structure is constructing the suitable layout structures for multiple different NoC applications by adjusting topological relations with reconfigurable nodes, not changing the IPCore mapping positions. In this way, the reusability of NoC layout structures is improved. Taking Petersen graph as the basic re reconfigurable structure can reduce the communication distances because Petersen graph has small network diameter. The proposed reconfigurable structure can reduce the numbers of switching nodes in communication paths and reduce the communication power consumption and time. At the same time, the reconfigurable NoC structure improves the reusability and flexibility of NoC structures(6) The layout optimization algorithm based on multivalued quantum evolutionary algorithm MQG is first proposed and applied to solve NoC layout problems according to the characteristics and requirements of NoC mapping and routing. Quantum evolutionary algorithm combines quantum optimization and evolutionary algorithm. The multivalued quantum evolutionary coding method can carry more information compared to the traditional quantum coding, enhancing the diversity of evolutionary individuals. In the coding and decoding process, paths are built based on the continuity between the nodes, discarding the traditional whole path coding. This new coding method shortens the length of coding and avoids generating invalid paths. The routing and layout schemes obtained by this algorithm can search the optimized communication paths and avoid deadlocks, achieving shortest commutation distances. The experimental results show the layout schemes obtained from MQG algorithm based on reconfigured Petersen graph structure have lower communication cost. The idea of MQG algorithm is also applied to solve other NP problems.