基于FPGA加速的异构计算多结点系统实时硬件任务调度与管理

发布时间：2018-03-15 07:22

本文选题：现场可编程门阵列　切入点：异构计算　出处：《华东交通大学》2013年硕士论文　论文类型：学位论文

【摘要】：随着单处理机计算速度和网络技术的不断提高与发展，计算机应用范围逐渐扩大，异构计算系统在现实生活和工作中得到了广泛运用。实时硬件任务调度与资源管理是异构计算系统的关键问题，是研究中亟待解决的一个难题。异构计算的实时硬件任务调度目标是在有限约束条件的前提下为实现一定性能指标而尽量减少整个系统的处理时间。文中所提出的异构计算系统是基于现场可编程门阵列FPGA加速的多结点处理系统。实时硬件任务调度分为全局系统调度和目标处理结点的局部调度。在全局系统调度下，，本文针对最佳适应算法Best-Fit的缺陷提出了性能更高的基于首适应的最佳适应算法BFBOFF；而在目标处理器结点的局部调度下，本文在避免最大入侵的原则上提出了一种避免入侵最佳适应算法AIBFA。通过实验的性能仿真证实了BFBOFF算法和AIBFA算法分别降低了全局系统调度的平均时间负载率和目标处理器结点局部调度的任务拒绝率。本文对目标处理结点上的FPGA资源管理的研究包括寻找空闲资源全集算法和任务在FPGA上的放置算法。高效的FPGA空闲资源管理策略对系统整体性起着非常重要的作用。针对寻找空闲资源全集的问题提出了一种基于单向栈的算法来寻找最大空闲矩形(MFR)，利用可重构计算单元的不同M值进出单向栈来搜索到所有最大空闲矩形，通过实验表明，算法通过使用单向栈与算法优化，有效提高了查找空闲资源全集时的性能。硬件任务在FPGA上的放置就类似于软件任务在计算机内存中的运行，随着硬件任务的放置，FPGA中的资源碎片可能会越来越多，这严重地影响着系统的整体性能，本文提出了一种基于二维空间邻接度算法TDSADA法来减少FPGA资源的碎片率。
[Abstract]:With the improvement and development of the computing speed and network technology of single processor, the scope of computer application is gradually expanding. Heterogeneous computing systems have been widely used in real life and work. Real-time hardware task scheduling and resource management is a key problem in heterogeneous computing systems and a difficult problem to be solved. The real-time hardware task scheduling goal of heterogeneous computing is to minimize the processing time of the whole system in order to achieve certain performance index under the premise of limited constraints. The heterogeneous computing system proposed in this paper is based on the field capability. The real-time hardware task scheduling is divided into global system scheduling and local scheduling of target processing nodes. Aiming at the defects of the optimal adaptive algorithm (Best-Fit), this paper proposes a better adaptive algorithm based on the first adaptive algorithm (BFBOFF), which is based on the local scheduling of the target processor nodes. Based on the principle of avoiding maximum intrusion, this paper proposes an optimal intrusion avoidance algorithm, AIBFA.Through the performance simulation of experiments, it is proved that the BFBOFF algorithm and the AIBFA algorithm reduce the average time load rate and the target of global system scheduling, respectively. Task rejection rate for local scheduling of processor nodes. In this paper, the research of FPGA resource management on target processing node includes searching for the complete set of free resources and placing tasks on FPGA. Efficient FPGA free resource management strategy plays an important role in the system integrity. Aiming at the problem of finding the complete set of free resources, this paper presents an algorithm based on one-way stack to find the maximum free rectangle MFRN, and uses the different M values of the reconfigurable computing unit to find all the maximum free rectangles in and out of the one-way stack. The experiments show that the algorithm can effectively improve the performance of searching the complete set of free resources by using unidirectional stack and algorithm optimization. The placement of hardware tasks on FPGA is similar to the running of software tasks in computer memory. With the placement of hardware tasks, there may be more and more resource fragments in FPGA, which seriously affects the overall performance of the system. In this paper, a two-dimensional spatial adjacency algorithm (TDSADA) is proposed to reduce the fragmentation rate of FPGA resources.
【学位授予单位】：华东交通大学
【学位级别】：硕士
【学位授予年份】：2013
【分类号】：TP332;TP301.6

【参考文献】