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

doi:10.11896/jsjkx.200500110

摘要/Abstract

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

关键词: FPGA, 调度, 动态部分可重构, 划分, 模拟退火

Abstract: 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.

Key words: Dynamically partially reconfigurable, FPGA, Partition, Scheduling, Simulated annealing

中图分类号:

TP302

王喆, 唐麒, 王玲, 魏急波. 一种基于模拟退火的动态部分可重构系统划分-调度联合优化算法[J]. 计算机科学, 2020, 47(8): 26-31. https://doi.org/10.11896/jsjkx.200500110

WANG Zhe, TANG Qi, WANG Ling, WEI Ji-bo. Joint Optimization Algorithm for Partition-Scheduling of Dynamic Partial Reconfigurable Systems Based on Simulated Annealing[J]. Computer Science, 2020, 47(8): 26-31. https://doi.org/10.11896/jsjkx.200500110

参考文献

[1]Xilinx, Inc.Vivado Design Suite User Guide Partial Reconfiguration[OL].https://www.xilinx.com/support/documentation/sw_manuals/xilinx2020_1/ug909-vivado-partial-reconfiguration.pdf.
[2]SAHA S, SARKAR A, CHAKRABARTI A.Scheduling dynamic hard real-time task sets on fully and partially reconfigurable platforms[J].IEEE Embedded Systems Letters, 2015, 7(1):23-26.
[3]DEIANA E A, RABOZZI M, CATTANEO R, et al.A multiobjective reconfiguration-aware scheduler for FPGA-based heterogeneous architectures[C]∥2015 International Conference on ReConFigurable Computing and FPGAs (ReConFig).IEEE, 2015:1-6.
[4]RABOZZI M, LILLIS J, SANTAMBROGIO M D.Floorplanning for partially-reconfigurable fpga systems via mixed-integer linear programming[C]∥2014 IEEE 22nd Annual International Symposium on Field-Programmable Custom Computing Machines.IEEE, 2014:186-193.
[5]SEYOUM B B, BIONDI A, BUTTAZZO G C.FLORA:Floorplan Optimizer for Reconfigurable Areas in FPGAs[J].ACM Transactions on Embedded Computing Systems (TECS), 2019, 18(S5):1-20.
[6]ZHU L H, WANG L, TANG Q, et al.Efficient MILP Model for HW/SW Partitioning of Dynamic Partial Reconfigurable SoC [J].Computer Science, 2020, 47(4):18-24.
[7]MA Y, LIU J, ZHANG C, et al.HW/SW partitioning for region-based dynamic partial reconfigurable FPGAs[C]∥2014 IEEE 32nd International Conference on Computer Design (ICCD).IEEE, 2014:470-476.
[8]SALAMY H, ASLAN S.A genetic algorithm based approach to pipelined memory-aware scheduling on an MPSoC[C]∥2015 IEEE Dallas Circuits and Systems Conference (DCAS).IEEE, 2015:1-4.
[9]CHARITOPOULOS G, KOIDIS I, PAPADIMITRIOU K, et al.Hardware task scheduling for partially reconfigurable FPGAs[C]∥International Symposium on Applied Reconfigurable Computing.Springer, Cham, 2015:487-498.
[10]RABOZZI M, DURELLI G C, MIELE A, et al.Floorplanning automation for partial-reconfigurable FPGAs via feasible placements generation[J].IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2016, 25(1):151-164.
[11]XIE D, SONG L F, DONG Y P, et al.Efficient dynamic partial Reconfigurable Design of FPGA based on clustering Partition algorithm [J].Electronics and Packaging, 2018, 18(9):8, 14.
[12]FERRANDI F, LANZI P L, PILATO C, et al.Ant colony optimization for mapping, scheduling and placing in reconfigurable systems[C]∥2013 NASA/ESA Conference on Adaptive Hardware and Systems (AHS-2013).IEEE, 2013:47-54.
[13]TANG Q, WU S, SHI J, et al.Modeling of schedule-aware synchronous dataflow[J].Journal of National University of Defense Technology, 2017(2):19.
[14]TANG Q, WU S F, SHI J W, et al.Optimization of duplication-based schedules on network-on-chip based multi-processor system-on-chips[J].IEEE transactions on parallel and distributed systems, 2016, 28(3):826-837.
[15]DHAR A, YU M, ZUO W, et al.Leveraging Dynamic PartialReconfiguration with Scalable ILP Based Task Scheduling[C]∥2020 33rd International Conference on VLSI Design and 2020 19th International Conference on Embedded Systems (VLSID).IEEE, 2020:201-206.
[16]CANON L C, SAYAH M E, PIERRE-CYRILLE H.A Comparison of Random Task Graph Generation Methods for Scheduling Problems[M]∥Euro-Par 2019:Parallel Processing.2019.
[17]TANG Q, BASTEN T, GEILEN M, et al.Mapping of synchronous dataflow graphs on MPSoCs based on parallelism enhancement[J].Journal of Parallel & Distributed Computing, 2017, 101(MAR.):79-91.

相关文章 15

[1]	田真真, 蒋维, 郑炳旭, 孟利民. 基于服务器集群的负载均衡优化调度算法 Load Balancing Optimization Scheduling Algorithm Based on Server Cluster 计算机科学, 2022, 49(6A): 639-644. https://doi.org/10.11896/jsjkx.210800071
[2]	张捷, 唐强, 刘朔晗, 曹越, 赵维, 刘韬, 谢士明. 智能电网中基于优先级的预约式电动汽车充电管理研究 Priority Based EV Charging Management Under Service Reservation in Smart Grid 计算机科学, 2022, 49(6): 55-65. https://doi.org/10.11896/jsjkx.220200013
[3]	杨桃雨, 徐媛媛, 谭增洁. 面向6G的全景视频片划分优化编码算法 Tile Partition Optimized Omnidirectional Video Coding for 6G Network 计算机科学, 2022, 49(6): 66-72. https://doi.org/10.11896/jsjkx.220400034
[4]	成科扬, 王宁, 崔宏纲, 詹永照. 基于局部注意力图互迁移的可解释性优化方法 Interpretability Optimization Method Based on Mutual Transfer of Local Attention Map 计算机科学, 2022, 49(5): 64-70. https://doi.org/10.11896/jsjkx.210400176
[5]	柳鹏, 刘波, 周娜琴, 彭心怡, 林伟伟. 混合云工作流调度综述 Survey of Hybrid Cloud Workflow Scheduling 计算机科学, 2022, 49(5): 235-243. https://doi.org/10.11896/jsjkx.210300303
[6]	田冰川, 田臣, 周宇航, 陈贵海, 窦万春. 减少Hadoop集群中网络队头阻塞的调度算法 Reducing Head-of-Line Blocking on Network in Hadoop Clusters 计算机科学, 2022, 49(3): 11-22. https://doi.org/10.11896/jsjkx.210900117
[7]	林潮伟, 林兵, 陈星. 边缘环境下基于模糊理论的科学工作流调度研究 Study on Scientific Workflow Scheduling Based on Fuzzy Theory Under Edge Environment 计算机科学, 2022, 49(2): 312-320. https://doi.org/10.11896/jsjkx.201000102
[8]	谭双杰, 林宝军, 刘迎春, 赵帅. 基于机器学习的分布式星载RTs系统负载调度算法 Load Scheduling Algorithm for Distributed On-board RTs System Based on Machine Learning 计算机科学, 2022, 49(2): 336-341. https://doi.org/10.11896/jsjkx.201200126
[9]	沈彪, 沈立炜, 李弋. 空间众包任务的路径动态调度方法 Dynamic Task Scheduling Method for Space Crowdsourcing 计算机科学, 2022, 49(2): 231-240. https://doi.org/10.11896/jsjkx.210400249
[10]	杨林, 王永杰, 张俊. FAWA:一种异构执行体的负反馈动态调度算法 FAWA:A Negative Feedback Dynamic Scheduling Algorithm for Heterogeneous Executor 计算机科学, 2021, 48(8): 284-290. https://doi.org/10.11896/jsjkx.200900059
[11]	高士顺, 赵海涛, 张晓瀛, 魏急波. 一种自适应于不同场景的智能无线传播模型 Self-adaptive Intelligent Wireless Propagation Model to Different Scenarios 计算机科学, 2021, 48(7): 324-332. https://doi.org/10.11896/jsjkx.201000181
[12]	章菊, 李学鋆. 基于莱维萤火虫算法的智能生产线调度问题研究 Research on Intelligent Production Line Scheduling Problem Based on LGSO Algorithm 计算机科学, 2021, 48(6A): 668-672. https://doi.org/10.11896/jsjkx.210300118
[13]	王登天, 周华, 钱荷玥. LDPC自适应最小和译码算法及其FPGA实现 LDPC Adaptive Minimum Sum Decoding Algorithm and Its FPGA Implementation 计算机科学, 2021, 48(6A): 608-612. https://doi.org/10.11896/jsjkx.200800134
[14]	宁玉辉, 姚喜. 一种应急指挥系统的设计与实现 Design and Implementation of Emergency Command System 计算机科学, 2021, 48(6A): 613-618. https://doi.org/10.11896/jsjkx.201000136
[15]	王国武, 陈元琰. 基于跳数修正和遗传模拟退火优化DV-Hop定位算法 Improvement of DV-Hop Location Algorithm Based on Hop Correction and Genetic Simulated Annealing Algorithm 计算机科学, 2021, 48(6A): 313-316. https://doi.org/10.11896/jsjkx.201000101

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed