计算机科学 ›› 2020, Vol. 47 ›› Issue (8): 26-31.doi: 10.11896/jsjkx.200500110
所属专题: 高性能计算
王喆1, 2, 唐麒2, 王玲1, 魏急波2
WANG Zhe1, 2, TANG Qi2, WANG Ling1, WEI Ji-bo2,
摘要: 基于FPGA的动态部分可重构(Dynamically Partially Reconfigurable, DPR)技术因在处理效率、功耗等方面具有优势, 在高性能计算领域得到广泛应用。DPR系统中的重构区域划分和任务调度决定了整个系统的性能, 因此如何对DPR系统的逻辑资源划分和调度问题进行建模, 并设计高效的求解算法是保证系统性能的关键。在建立划分和调度模型的基础上, 设计了基于模拟退火(Simulated Annealing, SA)的DPR系统划分-调度联合优化算法, 用于优化重构区域的划分方案和任务调度。文中提出了一种新型新解产生方法, 可有效跳过不可行解及较差解, 加快了对解空间的搜索并提高了算法的收敛速度。实验结果表明, 与混合整数线性规划(Mixed Integral Linear Programming, MILP)和IS-k两种算法相比, 提出的基于SA的算法的时间复杂度更低;且针对大规模应用, 该算法能够在较短的时间内获得较好的划分与调度结果。
中图分类号:
[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. |
[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 |
|