Research On Scheduling Reconfigurable Tasks Based On Service Attribute Differentiated

With the design development of reconfigurable devices, the scale of reconfigurable resources provided in a device is larger than earlier devices. Some reconfigurable devices have the run-time partial reconfigurable function (RTPR), which allows a task to be configured and executed without affecting running tasks in the device. With efficient management of resource and reasonable scheduling and placement method of tasks, which means selecting appropriate time and area to configure and place task. It is beneficial for more tasks to run in parallel and making better utilization of devices. Scheduling algorithms of reconfigurable tasks play an important effort on performance of reconfigurable computing system.According to the fundamental technique research task of the"The Researching and Manufacture of Reconfigurable Router Components"project of the National High-Tech Research and Development Program of China (863 Program), this thesis analyzing existing reconfigurable tasks scheduling system, concluding as follows: Every task is scheduled and placed according to its space and time attribute, ignoring the service attribute differentia of consecutive tasks, which including urgency and dependence of different tasks. The thesis proposes a reconfigurable task scheduling system model which supports differential service attributes. A discrete planning task scheduling algorithm is used in this system. By analyzing and proving the feasibility of planning preemptive scheduling, and considering differential urgency among tasks, a preemptive scheduling algorithm based on urgency differentiated is proposed. For the tasks which have dependent relation with other tasks, proposing a dependence differentiating sequence scheduling algorithm based on the dependent relations of consecutive tasks, which could improve the configuration procedure of task and reduce the whole executing time of tasks.The thesis is organized as follows:This thesis analyses existing reconfigurable systems and scheduling algorithms. Several problems of these systems are pointed out: The existing scheduling system pays more attention to placement than scheduling, treating tasks in FCFS (First Come First Serviced) mode and ignoring the differentia of service attributes. Current scheduling algorithms are classified as two types: BS (Basic Scheduling) and PS (Planning Scheduling). Because the scheduling of each task is independent, these algorithms can not reflect the differentia of service attributes and bring selfishness and blindness in the scheduling process, which opposed to the utilization of reconfigurable resource.A reconfigurable scheduling system model supporting differential service attributes is brought forward, and the component and function of system is described. The system takes scheduler as kernel part which is different from the known scheduling system model. Placer and Resource Manager both work in the control of scheduler. The time domain resource slices make up of resource management, which is the base of the latter discrete planning scheduling algorithm. The scheduler has the special function to alter the old scheduling results, which can support planning preemptive scheduling algorithm.An Elastic Discrete Planning (EDP) scheduling algorithm is proposed. Firstly, the feasibility of the elastic scheduling algorithm is proved. According to the resource management, it is proved that the moment for placing process could just execute at the beginning time of resource slice, and the other time could be ignored. The potential placing time list (PPTL) is generated based on the types of slice. Comparing to Stuffing algorithm, the process of placement only be executed at the proper moment in EDP scheduling algorithm. By avoiding executing placement manipulation at every activated moment in task's laxity, EDP algorithm improves the efficiency of scheduling process.A Preemptive Scheduling algorithm based on Urgency Differentiated (PSUD) is proposed. By analyzing the feasibility of preemptive scheduling, defining the conception of urgency, the Maximum Urgency First (MUF) is proposed as the scheduling method. With strategy of resource considered first, foundation of preemptive threshold and the backup and recovering mechanism of planning results, it can reduce quantity of rescheduling invalid tasks again, and increase the efficiency of preemptive scheduling process. The experiments show that PSUD could improve the success rate of scheduling comparing to BS and PS algorithm. In the preemptive process, EDP algorithm has the same success rate with Stuffing algorithm, but reduces time-consuming of scheduling. The result validates the rationality of designing PPTL on other side.With regard to task set with dependent relation and the restriction of limited resource, a Dependence Differentiating Sequence (DDS) scheduling algorithm is proposed. By using the Direct Acyclic Graph (DAG) to describe the complex relations of tasks, it is pointed out that the sequence strategy is necessary, and establishing a three-dimensional resource model of reconfigurable tasks. It is proved that discrete planning scheduling algorithm based on PPTL-E could also be used for correlative task scheduling process. The experiments show that the DDS algorithm could avoid the deadlock in the process of scheduling tasks, and reducing the running times of all tasks by pre-configuration of tasks.