Research On Reconfigurable Task Scheduling Algorithms Based On LRSS

Reconfigurable devices with the Run-Time Partial Reconfigurable (RTPR) function, which is programmable and configurable in a repeated way, not only allow tasks to be executed in parallel at the same time, but also allow different tasks to be executed in the way of time division multiplexing. Because of limit device scale and resource competition among different tasks, key performance measures, like throughput and task duration and so on, of a reconfigurable system is directly dependent on the allocation of resource to the relevant tasks. Therefore, to design an effective resource management model and related task scheduling algorithms is an essential way for us to address the above problems.The thesis includes all researching work relay on a sub-project of the 11th five-year plan named"The Researching and Manufacture of Reconfigurable Router Components". Reviewing the development of reconfigurable technology; Introducing the composition and functions of reconfigurable system, resource model and task models, standards for measuring an algorithm; Analyzing the problems in present algorithms, there are three main problems existing in present algorithms: Firstly, it is hard to manage the resource state effectively. Secondly, the fashion of task scheduling in First Come First Served brings selfish in resource reservation and blindness in scheduling. Thirdly, the delay of task scheduling causes by poor placement. Aim at these problems, this thesis proposes the List of Resource Slice State (LRSS) resource management tactics based on task events, a scheduling algorithm based discrete time-interval and a heuristic-list scheduling algorithm applied on related task model. Comparing the performance of different algorithms by simulations, the experiment results verify the effectiveness.The work of thesis concentrates on the resource management and task scheduling, and the main parts are as following:1 Proposing the LRSS reconfigurable resource management model based on task events. The main idea of model is: The resource state is mapped to a two-dimension matrix; Analyzing the relation between state of resource and task events Verifying the feasibility of representing a continuous the resource state by some discrete slice state. Slices are arrayed in the order of time sequence, and updated according to the task events. The model is beneficial to reduce the storage redundancy, and provide a model basis for the later scheduling algorithms.2 Proposing a task scheduling algorithm based on the Discrete Time-Interval (DTI). The main idea is: Putting the waiting tasks into an adjusting sequence by the order of priorities; Select the task with the highest priority in sequence to acquire the resource every time and avoid the scheduling selfish; With the slice state in LRSS, calculating the earliest finishing time and setting the timer, what provides the start time to scheduler. It is help to avoid the blindness in task scheduling. The experiment results show that the DTI algorithm make a improvement in successful scheduling rate and scheduling efficiency.3 Proposing a heuristic list algorithm applied to the related task model. The main idea is: Describing the task's relation ship by directed acyclic graph; Analyzing the affection factors of scheduling delay. With the t_level,b_level and task area size as the parameters, calculate the priority of scheduling. The scheduling process abides the following rules: the former task should be scheduled firstly among related tasks, and the task with the higher priority between non-related tasks. The simulation results show that the new algorithm has a better performance in reducing the whole running time-overhead, and get a max reduction of 15%.According to above analysis and experiments, the scheduling algorithms based on LRSS have improve performance on reducing storage and avoiding the scheduling selfish and blindness, reducing the overhead of running time. These methods are helpful to improve the system performance in resource storage and management, capacity of dealing with tasks based on recon figurable technology.