Researches On Task Placement And Task Duplication Methods Based On Reconfigurable Systems

With both the efficiency of hardware and the programmability of software,reconfigurable computing is one of the current hot topics in computer science. Partialdynamic reconfigurable technology can configure part of the reconfigurable resourceswhen the reconfigurable system works properly, making the execution of part of thetask proceed simultaneously with the configuration of another part, thus having theadvantage of saving hardware resources and enhancing the system flexibility.In the dynamic reconfigurable system, how to manage the free resources on achip and allocate the computing tasks of hardware has become one of the key factorsinfluencing the performance of the dynamic reconfigurable system. In order tominimize the task rejection rate and the task running time, improve the areautilization of reconfigurable resources, and make the performance of the system beoptimal and sub-optimal, we need to manage and schedule the hardware tasks throughthe high-quality placement and scheduling algorithms.Based on classical task model and computing model, the existing task placementand scheduling methods are investigated in this thesis. First, placement algorithm canbe improved by considering more about the task width and the existing one-dimensionplacement model, to design a new one in this thesis in order to enhance the placementquality because it is found not to have a comprehensive consideration of the taskproperty placed on FPGA. Second, referencing to the scheduling algorithm inhomogeneous and heterogeneous computing, combining its own characteristics of thereconfigurable multi-FPGA computing model, and based on the existing schedulingalgorithm, task duplication method is introduced to have a in-depth discussion on thetime and position of task duplication. This method will copy parent nodes on the taskgraph to the FPGA where child nodes are to reduce the overhead of communicationbetween father and son tasks, enabling the sub-tasks to be started earlier.Through the simulation program compare the proposed one-dimensional placedalgorithm with the existing algorithms, experimental results show that the presentedalgorithm improves the placement of place performance, reduced the task rejectionrate. Before and after the task duplication, performance testing shows that after taskduplication algorithm, the overall finish time of task graph is reduced greatly.