Research On Real-time Task Scheduling Algorithm Of Reconfigurable System

Reconfigurable computing has both the flexibility of software and the performance of hardware, and it has become a new subject of a great deal of research in computing domain. As the features it has, reconfigurable computing will be used widely in such domains as embedded system, high-performance computing, real-time system and so on. Typical reconfigurable system is composed of one (or several) processor(s) and one (or several) FPGA(s). To achieve the flexibility and high-performance of reconfigurable system, the computation intensive parts of a real-time task can be converted into hardware tasks executing on FPGA accelerated and the other parts execute on processors as software tasks. Therefore tasks executing on reconfigurable platform include independent software tasks, tasks under precedence constraints executing on processors only and software/hardware hybrid tasks executing on processors and FPGA. In this paper, some scheduling problems are discussed for these there types of tasks and the main works are shown as follow:1. Because periodic and aperiodic tasks co-exist in real-time system and the proposed real-time scheduling algorithms for periodic/aperiodic hybrid tasks only applied to uniprocessor system, a hybrid real-time scheduling algorithm is proposed to apply to multiprocessor system. The algorithm schedules aperiodic tasks on DS servers and schedules DS servers and periodic tasks jointly. The algorithm can meet all periodic tasks'deadlines and the accepted aperiodic tasks'deadlines.2. In multiprocessor system, some real-time tasks are composed of several subtasks under precedence constraints. The proposed algorithms for tasks under precendence constrants are mostly static scheduling algorithms and their computing complexities are high and can't schedule aperiodic tasks, so a dynamic scheduling algorithm is proposed to schedule periodic and aperiodic hybrid tasks under precedence constraints. Because the algorithm tests periodic tasks'schedulability before system starting, its online scheduling overhead decreased greatly. The algorithm also can schedule aperiodic tasks on DS servers.3. In reconfigurable system, some real-time tasks not only have software subtasks executing on processor but also have hardware subtasks executing on FPGA directly. The proposed algorithms can only schedule software real-time tasks or hardware real-time tasks, so a scheduling algorithm is proposed for software/hardware hybrid real-time tasks. The algorithm partitions each real-time task's hardware subtasks into several groups and configures subtasks in the same group into one slot, therefore the reconfigurable resource utilization increases. The algorithm has analyzed real-time tasks'schedulability and can meet all tasks'deadlines.4. In reconfigurable system,circuit configure information is stored in static RAM and is susceptible to electromagnetic interference which can cause circuit fault. So a fault-tolerant scheduling algorithm is proposed to improve system reliability. The algorithm schedules each software subtask to execute on two processors at the same time, and if a fault occurs, the software subtasks will rollback to the last checkpoint which guarantees software subtasks'correctness. Each hardware subtask is included in three groups and executes in three slots simultaneously and the error result is masked off. The algorithm can tolerate several faults and guarantee all tasks'deadline with little hardware overhead.