Research On Algorithms Of Real-time Tasks Scheduling For Dynamic Reconfigurable System

Reconfigurable computing technology combines the advantages of GPP(General-Purpose Processor) and ASIC(Application Specific Integrated Circuits), providing the hardware efficiency and software programmability in one platform.It is one of the hot topics of current computer research. As the most recent development of reconfigurable computing technology,dynamic partial reconfiguration can reconfigure a part of the reconfigurable logic device while other parts of the system continue to operate,enabling the parallel execution of running tasks and reconfigurations. Dynamic reconfiguration technology can improve system flexibility and resource utilization,thus enhancing overall system performance.In a dynamic reconfigurable system, the hardware tasks scheduling is affecting the performance of dynamic reconfigurable system,the key factor. In order to maximize the utilization of the system chip,reducing hardware,the task rejection rate and the activation time overhead,which requires use of high-quality scheduling algorithm to a reasonable hardware tasks scheduling and management.This paper focuses on the on-line placement and scheduling of real-time tasks on a two-dimensional reconfigurable device,the research of this thesis addresses all these aspects, in which the new contributions are:(1) This paper considers the hardware tasks in accordance with the length, width and scheduling time to form a three-dimensional resource model,each hardware-task as a space block,vertex-based task management list,first select the value of a unit volume of space for large blocks,Then put the container back to space,in the place of space block,always occupied a certain angle,and the movement of space adjacent to a large degree as far as possible from all vertices in a viable location,choose the best vertex to place the task. It makes task arrangement more compact,reduces the waste of system resource and improves chip utilization.(2) This paper puts forward a scheduling algorithm based on the minimum space between the hardware of the vertex chain.The algorithm is done by the full consideration of delay of scheduling in the slack time of the task and adopt a placement method based on the adjacent degree of 3-D space,choose that the adjacency degree maximum placed vertex within the slack time and the time that task begins to perform.So it makes the task more orderly and closely placed,thereby reduces the reject rate of tasks,improves concurrent degree and resources utilization of the hardware tasks implementation.(3) Designing a simulation,compare MSSA(minimun space scheduling algorithm)with the MGS algorithm,Stuffing algorithm and CR algorithm respectively from task reject rate,reconfigurable resource area utilization to time complexity.The comparison though these four algorithms adopt the same parameter,results show that this algorithm has a higher acceptance rate of chip utilization and tasks. At the same time,the runtime and spending are not markedly increased.