一种基于模拟退火的动态部分可重构系统划分-调度联合优化算法

Joint Optimization Algorithm for Partition-Scheduling of Dynamic Partial Reconfigurable Systems Based on Simulated Annealing

基于FPGA的动态部分可重构(Dynamically Partially Reconfigurable,DPR)技术因在处理效率、功耗等方面具有优势,在高性能计算领域得到广泛应用。DPR系统中的重构区域划分和任务调度决定了整个系统的性能,因此如何对DPR系统的逻辑资源划分和调度问题进行建模,并设计高效的求解算法是保证系统性能的关键。在建立划分和调度模型的基础上,设计了基于模拟退火(Simulated Annealing,SA)的DPR系统划分-调度联合优化算法,用于优化重构区域的划分方案和任务调度。文中提出了一种新型新解产生方法,可有效跳过不可行解及较差解,加快了对解空间的搜索并提高了算法的收敛速度。实验结果表明,与混合整数线性规划(Mixed Integral Linear Programming,MILP)和IS-k两种算法相比,提出的基于SA的算法的时间复杂度更低;且针对大规模应用,该算法能够在较短的时间内获得较好的划分与调度结果。

Dynamically partially reconfigurable(DPR)technology based on FPGA has many applications in the field of high-performance computing because of its advantages in processing efficiency and power consumption.In the DPR system,the partition of the reconfigurable region and task scheduling determine the performance of the entire system.Therefore,how to model the lo-gic resource partition and scheduling of the DPR system and devising an efficient solution algorithm are the keys to ensure the performance of the system.Based on the establishment of the partition and scheduling model,a joint optimization algorithm of DPR system partition-scheduling based on simulated annealing(SA)is designed to optimize the reconfigurable region partitioning and task scheduling.A new method is proposed for skip infeasible solutions and poor solutions effectively which accelerates the search of solution space and increases the convergence speed of the SA algorithm.Experimental results show that,compared with mixed integer linear programming(MILP)and IS-k,the proposed algorithm based on SA has lower time complexity,and for the large-scale applications,it can solve better partition and scheduling results in a short time.