Research On Task Compilation Technology Based On Heuristic Algorithms On Reconfigurable System

With the development of semiconductor manufacturing technology,the microprocessor performance is meeting bottlenecks.The ‘energy wall' and ‘performance wall' make Moore's law being difficult to continue the development of high performance.Computers can not rely on technological progress,but need to change the calculation method and system architecture.The heterogeneous architecture of dynamic partial reconfigurable system,which consists of general processor and large scale integrated circuit,has good performance in flexibility and energy efficency,and is one of the directions of high performance computing research.In reconfigurable system,the compiler is responsible for controlling the application.The quality of the compiler directly affects the operating speed and energy consumption of system.One of the most important problems in the research of reconfigurable system is to optimize the compilation technologies of the system.The task partioning,task scheduling and task placement strategy are the key algorithms in heterogeneous multi-core system.Researches show that task partioning,task scheduling and task placement problem in reconfigurable system can be abstracted as the multi-objective optimization model.The heuristic methods can solve these three problems but still have the following shortcomings:(1)the task partitioning algorithm is easy to fall into local extremum,reducing the solusion's quality and reliability(2)the configuration prefetching model of task scheduling is complex,increasing the complexity of the algorithm;(3)the task placement strategy has poor applicability of the system and lack of fault tolerance.To solve the above problems,the thesis introduced the optimization theory of heuristic method into reconfigurable system partitioning,task scheduling and task placement strategy,improving the system performance of reconfigurable system compiler.The main work and innovation are as follows:1.According to the shortcomings of the task partition algorithm which is easy to fall into the local extremum,making the low precision of the solution,the poor quality of the partition and reliability.Firstly,the evaluation function of the algorithm is designed according to the model of the system constraints,and then the reverse learning mechanism is proposed to degrade ther process.The algorithm can jump out the local extremum,improve the precision and improve the reliability of the algorithm.2.The task scheduling model of reconfigurable system is complex and the cost of the algorithm is large,affecting the real-time performance of the system.First,we proposed an improved reconfigurable system task scheduling model with configuration prefetching.Then a scheduling scheme is proposed which named discrete particle swarm optimization task scheduling strategy.Finally the pre-generation strategy is put forward to improve the reliability of the algorithm and the convergence rate.The algorithm has low time complexity,high reliability and accuracy.3.In order to solve the problem that the task placing strategy is difficult to use a variety of scale tasks and lack of consideration of the fault tolerance,we proposes a reconfiguration strategy based on dynamic genetic algorithm.Firstly,the multi-reconfigurable task placement model is introduced.Then Area-First strategy is put forward.Finally we proposed the dynamic genetic algorithm.The dynamic factor can avoid genetic process into local extremum.The algorithm is applicable to a wide range of task placement models with a limited area,which can improve the quality of the solution and reduce the communication delay.