| With the emergence of emerging applications such as artificial intelligence,Internet of Things,and autonomous driving,the amount of data and calculations are increasing dramatically,and people have higher requirements for the efficiency and real-time performance of data processing.As Moore's Law is gradually failing,it has been difficult to improve the performance of the processor by increasing the density of transistors.Chip designers often add multiple cores or increase the frequency to improve the performance of the Central Processing Unit(CPU).However,after reaching a certain threshold,the growth rate of CPU performance will gradually slow down,traditional computing methods are facing great challenges.Because of the parallelism of Field Programmable Gate Array(FPGA),it has a great advantage over CPU in terms of computational efficiency.The realization of dynamically partially reconfigurable(DPR)technology on FPGA further exploits the potential of FPGA.In order to improve the performance of DPR system,this paper studies the resource partitioning and task scheduling of the DPR system based on FPGA.First,the DPR system and FPGA are analyzed in this paper,and we establish the partitioning and scheduling model.The input of DPR system should not only meet the needs of the system,but also have a clear structure.It is modeled as Directed Acyclic Graph(DAG)in this paper.Nodes in the DAG are the application tasks that need to be mapped to the reconfigurable region for execution.Therefore,before mapping all tasks to regions,the reconfiguration resources should be virtualized into multiple regions to meet the demands of tasks and ensure the parallelism of system execution to the greatest extent.In the meantime,it is necessary to determine the reconfiguration order of tasks which establish the relationship of priority in time.After that,the size and quantity of the region should be determined according to the mapping relationship and reconfiguration order,and then a complete partitioning and scheduling scheme can be obtained.Thus,it can be seen that the reconfiguration order,region size and mapping relation are all components of the system model,so it is necessary to make a more in-depth analysis of resource partitioning and task scheduling.Secondly,this paper proposes two solving algorithms,establishes a representation method of the solution.In order to judge the feasibility of the solution,the feasibility problem of the solution is classified from the two aspects of resource constraints and execution constraints,and sufficient and necessary conditions for a feasible solution are given.In order to improve the quality of the final solution,a neighborhood solution set method is designed,which speeds up the convergence speed of understanding and improves the quality of the final solution obtained.In addition,this paper presents an algorithm to solve the objective function,which can accurately solve the scheduling length of the solution.Since judging the feasibility of the solution takes a huge amount of time,the paper also provides another solving algorithm that is related to the reconfiguration order and the data dependency.While losing part of the quality of the solution,it also greatly reduces the time complexity of the algorithm.Finally,through several sets of experiments,this paper determines the length of the neighborhood solution set and verifies the performance of the algorithms proposed in this paper.In this experiment,two DAG groups were selected as the input of the experiment.The experimental results show that the two algorithms in this paper have their own advantages in terms of time complexity and solution quality.One algorithm can find a better-quality solution in a longer time,while the other algorithm is a tradeoff between time complexity and solution quality.Compared with other algorithms,the two algorithms proposed in this paper have greater advantages in solution time and solution quality,and can solve a better-quality solution in a shorter time. |
PDF Full Text Request