Reconfigurable Real-time Scheduling Tasks In The System And Real-time Layout Algorithm

Reconfigurable computing systems have been developed on the basis of microprocessor and ASIC, which can achieve much better performance than microprocessor and maintains a higher level of flexibility than ASIC. It is necessary to manage the reconfigurable resources and hardware tasks for operating system, which can bring higher performance and programmable ability. Therefore, reconfigurable hardware operating system for reconfigurable computing has been a novel hot topic in last few years.Reconfigurable hardware operating systems fill two key roles in computing: simplifying the programming interface through an abstracted programming model and managing shared resources. The online scheduling and online placement as the critical part of the reconfigurable hardware operation systems.The number of the resource on reconfigurable device increasing dramatically makes it possible to operate concurrent in a multi-user manner. Because of this, the thesis presents a multi-user multi-tasking reconfigurable computing model, and in-depth study on the task online scheduling and online placement algorithm on the basis of this model. This thesis consists of the following parts.The first part analysis of existing reconfigurable computing platform, proposed a multi-user multi-tasking reconfigurable computing system model, and analyzes the general form of a task model.The second part discusses the online scheduling algorithm. User task set (UTS) is scheduled by an improved first come first served schedule (FCFS) algorithm. The multitasks within the UTS are scheduled by a new temporal partition technique—critical segment cut (CSC) algorithm.The third part shows the placement algorithm. The data-independent UTS uses resource utilization as the placement criterion, so a new placement algorithm—maximal residual empty rectangle (MRER) is applied to solve the UTS placement. When dealing with the data-dependent UTS internal multitasks, using communication-cost as the criterion, so a new placement algorithm—minimal routing cost (MRC) is presented to resolve the UTS internal multitask placement problem.The final part detailed analyses and evaluations of the strategies from the resource utilization, task rejection rate, fragmentation of RHD and many other points of view.