The Research On Online Hardware Task Schedule Algorithm Based-on Partial Reconfigurable Computing

Reconfigurable computing has two advantages, including the high performance of ASIC and the flexibility of general-purpose CPU. It can satisfy the needs for high-performance computing capacity from every field. Therefore, it has become a very hot research topic. Currently, reconfigurable logic devices have already owned the capacity of partially reconfiguring, which can meet the needs for high perfor-mance and multi-task dynamic execution of modern computer systems. However, it also puts new demands upon the operating systems for reconfigurable devices.Hardware task scheduling is a core function of the reconfigurable computing operating system. Efficient hardware task scheduling and placement is one of the most crucial factors in taking advantage of the benefits of partially reconfigurable computing technology. To improve the performance of task scheduling, this paper focuses on the on-line scheduling of hardware tasks on partially dynamic reconfi-gurable computing systems and proposes some improvevfpments after researching into the previous algorithms. My contributions are as follows:1. To eliminate the overhead in the existing algorithms caused by the increase of the number of tasks on reconfigurable devices, we proposes a novel resource manag-ing algorithm based on Segmentation Algorithm (SA) and the existing correlation matrix model. SA hides the occupied sections in scanning area and scans the large area after dividing it to many sub sections, which can reduce the time cost of resource management.2. By doing research on the task placement strategies of existing classical algo-rithms, we find that all of the cost functions are associated with the number of recon-figurable computing units around the occupied sections. This paper proves that Max-Adjacent Sides (MAS) placement strategy can effectively reduce the fragmenta-tion degree of reconfigurable resources and therefore increase the success rate of task scheduling and resource utilization.3. Because of the giant overhead of task switching on reconfigurable logic de-vices, the preemptable kernels for configurable systems do not gain enough attention from the academic world and industry. They ignore the special attributes in reconfi-gurable systems. Taking advantage of the special attributes of the reserved tasks, this paper proposes a novel Secondary Preemptable Scheduling Algorithm (SPSA) for on-line hardware tasks. When some tasks can not be scheduled, SPSA will preempt the reconfigurable resources previously assigned to reserved tasks by system and schedule these tasks together by a particular off-line algorithm in order to further in-crease the success rate of task scheduling and resource utilization.In order to verify the algorithm, this paper implements a simulation system, which is based on the existing on-line hardware task scheduling model, to simulate the proposed algorithm and existing classical algorithms. The result reveals that SA algorithm is very effective in reducing the overhead of reconfigurable resource man-agement; MAS placement strategy is able to successfully simplify the FE algorithm, and at the same costs, has a higher success rate of task scheduling and resource utili-zation than BV and KTVS strategies; SPSA algorithm, which is based on MAS strat-egy, can significantly enhance the success rate of task scheduling and resource utili-zation.