Research On Technology Of Software-Hardware Functional Partition And Task Scheduling Of Reconfigurable System

With FPGA's increasing capacity and the rapid development of automatic design technology, reconfigurable logic device-based reconfigurable computing (RC) technology is rapidly maturing. RC technology combines both advantages of traditional software and hardware implementation, which possesses high-performance as hardware, but also has the flexibility of software. It is an innovative approach to achieve high-performance computing (HPC), and has become the industry's research focus. It has very good prospects on HPC applications, but also brings many new challenges, including applications'software/hardware functional partitioning on reconfigurable system, software/hardware task scheduling, hardware task's placement and reconfigurable resources management and so on.Aiming at the challenges for reconfigurable system, the main contributions of the thesis are as follows:1. A configuration prefetching and task-reuse based hybrid tasks scheduling algorithm (CTHTSA) for dynamic reconfigurable system is presented. Traditional scheduling algorithms (including task scheduling on a single CPU and parallel task scheduling on multi-CPUs) offer some reference for the scheduling on reconfigurable system, but cannot meet the needs of scheduling research on reconfigurable computing systems. At present, most of the task scheduling systems on reconfigurable system may have the following shortcomings: (1) the system model is based on a single CPU + FPGA architecture, does not taking into account the cooperative execution of CPU and FPGA. (2) Aimed at the factor of hardware task's configuration time, current algorithm adopts only a certain kind of optimization and limits the optimized effect.For the shortcoming of existing researches, CTHTSA algorithm takes full advantage of rich CPU cores and FPGA resources on reconfigurable system to achieve software hardware tasks'parallel execution, and to hide hardware task configuration overhead by configuration prefetching and task reuse, to further reduce program's execution time. Experimental results show that the algorithm can effectively improve the execution performance. 2. An improved genetic and configuration-prefetching scheduling based software/hardware partition algorithm (IGCPSPA) is presented. The algorithm combines program's partition and scheduling. First it encodes the problem, mapping problem domain to solution space, and then adopts strategies of roulette wheel and elitist selection, self-adaptive crossover and mutation for individual optimization in the evolutionary process, when in the evolutionary evening adopts climbing algorithm to optimize individual in its neighborhood, eventually gets an optimal software-hardware functional partition solution.Configuration-prefetching scheduling algorithm is used to evaluate the partition solution. It takes advantage of CPU cores and FPGA's parallelization, and adopts configuration-prefetching policy to hide the system reconfiguration overhead during the scheduling process, thereby improves the system's overall implementation performance. The results show that contrasting some of the existing software/hardware automatic partition methods, the proposed partition method is more effective.3. A task urgency and placement compactness based online scheduling algorithm TUPC is presented. Different from the existing FCFS scheduling algorithms, TUPC algorithm takes into account the relevant characteristics of adjacent tasks, schedules the task with most urgency preferentially, while places the task with maximal placement compactness area in the process of scheduling. Experimental results show that the algorithm can effectively improve the quality of task scheduling and placement, and scheduling success rate is better than the current mainstream scheduling algorithms.4. First heterogeneous reconfigurable device model and task model are built, and then the concepts of chip load (CL) and special load (SL) is proposed, and proved that both CL and SL have influence on scheduling performance by the HM-FF and HT-FF algorithm testing. On the basis of performance bottlenecks analysis of HT-FF algorithm, an online scheduling algorithm of region-based placement (SARP) is proposed, and on this basis, further, an improved scheduling algorithm - scheduling algorithm of region-based and sharing placement (SARSP) is proposed. Experimental results show that SARSP algorithm can effectively reduce tasks'scheduling rejection rate on the heterogeneous structure's reconfigurable system.