计算机科学 ›› 2021, Vol. 48 ›› Issue (6): 19-25.doi: 10.11896/jsjkx.200700198
郭彪1,2, 唐麒2, 文智敏3, 傅娟4, 王玲1, 魏急波2
GUO Biao1,2, TANG Qi2, WEN Zhi-min3, FU Juan4, WANG Ling1, WEI Ji-bo2
摘要: 并行计算是提高系统资源利用率的重要手段,越来越多的多处理器片上系统通过集成具有不同功能特点的处理器来满足不同计算任务的需求。具备动态部分可重构特性的异构多处理器片上系统(Dynamic Partial Reconfiguration-Heteroge-neous Multiprocessor Systems-on-Chip,DPR-HMPSoC)因其并行性好、计算效率高而被广泛使用,而低复杂度和高求解性能的软硬件划分算法是充分发挥其计算性能优势的重要保证。已有的相关软硬件划分算法时间复杂度高,且对DPR-HMPSoC平台的支撑不足。针对上述问题,首先提出了一种列表启发式软硬件划分与调度算法,其通过构建基于任务优先级的调度列表,完成任务的调度、映射、FPGA动态部分可重构区域划分等一系列操作;接着给出了软件应用建模、计算平台建模及所提算法的详细设计方案。仿真实验结果表明,所提算法与混合整数线性规划(Mixed Integral Linear Programming,MILP)和蚁群优化(Ant Colony Optimization,ACO)算法相比,可有效减少求解时间,且时间优势与任务规模成正比;在调度长度方面,所提算法的平均性能提升了约10%。
中图分类号:
[1]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. [2]BANERJEE S,BOZORGZADEH E,DUTT N D.Integratingphysical constraints in HW-SW partitioning for architectures with partial dynamic reconfiguration[J].IEEE Transactions on Very Large Scale Integration (VLSI) Systems,2006,14(11):1189-1202. [3]CHAKRABORTTY R K,SARKER R A,ESSAM D L.A Comparative Study of Different Integer Linear Programming Approaches for Resource Constrained Project Scheduling Problems[M].Lecture Notes in Management and Industrial Engineering,2018. [4]REDAELLI F,SANTAMBROGIO M D,OGRENCI M S.AnILP Formulation for the Task Graph Scheduling Problem Tailored to Bi-dimensional Reconfigurable Architectures[C]//International Conference on Reconfigurable Computing and Fpgas,2008.IEEE,2008:97-102. [5]TOPCUOGLU H,HARIRI S,WU M Y.Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computing[J/OL].IEEE Transactions on Parallel and Distributed Systems.https://ieeexplore.ieee.org/document/993206. [6]WANG Z,TANG Q,WANG L,et al.A Joint Optimization Algorithm for Partition-Scheduling of Dynamic Partial Reconfigurable Systems Based on Simulated Annealing [J].Computer Science,2020,47(8):26-31. [7]CHEN S,HUANG J,XU X,et al.Integrated Optimization ofPartitioning,Scheduling,and Floorplanning for Partially Dyna-mically Reconfigurable Systems[J].Physical Review B,2018,17(10):4114-4116. [8]HOU E S H,ANSARI N.A genetic algorithm for multiprocessor scheduling[J].IEEE Transactions on Parallel and Distributed Systems,1994,5(2):113-120. [9]ABDALLAH F,TANOUGAST C,KACEM I,et al.Genetic algorithms for scheduling in a CPU/FPGA architecture with he-terogeneous communication delays[J/OL].Computers & Industrial Engineering.https://www.sciencedirect.com/science/article/abs/pii/S0360835219304644. [10]HOU N,HE F Z.Hybrid parallel genetic strategy with two-step adjustment for HW/SW partitioning[J].Huazhong Univ.of Sci.& Tech.(Natural Science Edition),2017,45(12):39-45. [11]CATTANEO R,BELLINI R,DURELLI G,et al.PaRA-Sched:A Reconfiguration-Aware Scheduler for Reconfigurable Architectures[C]//2014 IEEE International Parallel & Distributed Processing Symposium Workshops (IPDPSW).IEEE,2014. [12]TUMEO A,PILATO C,FERRANDI F,et al.Ant colony optimization for mapping and scheduling in heterogeneous multiprocessor systems[C]//Embedded Computer Systems:Architectures,Modeling,and Simulation.IEEE,2008. [13]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).IEEE,2013. [14]BRUCKER P,DREXL A,MOEHRI R,et al.Resource-con-strained project scheduling:Notation,classification,models,and methods[J].European Journal of Operational Research,1999,112(1):3-41. [15]DHAR A,YU M,ZUO W,et al.Leveraging Dynamic Partial Reconfiguration with Scalable ILP Based Task Scheduling[C]//2020 33rd International Conference on VLSI Design and 2020 19th International Conference on Embedded Systems (VLSID).2020. [16]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 & Distributed Systems,2017(3):1-1. [17]BIONDI A,BALSINI A,PAGANI M,et al.A Framework for Supporting Real-Time Applications on Dynamic Reconfigurable FPGAs[C]//2016 IEEE Real-Time Systems Symposium (RTSS).IEEE,2016. [18]MA Y,LIU J,ZHANG C,et al.HW/SW partitioning for re-gion-based dynamic partial reconfigurable FPGAs[C]//IEEE International Conference on Computer Design.IEEE,2014:470-476. [19]VIPIN K,FAHMY S A.FPGA Dynamic and Partial Reconfiguration:A Survey of Architectures,Methods,and Applications[J].ACM Computing Surveys,2018,51(4):1-39. [20]XIAO X,LI Z.Chemical Reaction Multi-Objective Optimization for Cloud Task DAG Scheduling[J].IEEE Access,2019(99):1-1. [21]XU J R,ZHU H J.Multi-objective scheduling algorithm of DAG tasks in cloud computing[J].Application Research ofCompu-ters.http://en.cnki.com.cn/Article_en/CJFDTotal-JSYJ201901008.htm. [22]STUIJK S,GEILEN M,BASTEN T.SDF3:SDF For Free[C]//6th International Conference on Application of Concurrency to System Design,ACSD 2006,Proceedings.IEEE,2006:276-278. [23]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. [24]CANON L C,SAYAH M E,PIERRE-CYRILLE H.A Comparison of Random Task Graph Generation Methods for Scheduling Problems[J].arXiv:1902.05808,2019. [25]LINDO API 11[EB/OL].https://www.lindo.com/index.php/products/lindo-api-for-custom-optimiz. |
[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] | 柳鹏, 刘波, 周娜琴, 彭心怡, 林伟伟. 混合云工作流调度综述 Survey of Hybrid Cloud Workflow Scheduling 计算机科学, 2022, 49(5): 235-243. https://doi.org/10.11896/jsjkx.210300303 |
[4] | 田冰川, 田臣, 周宇航, 陈贵海, 窦万春. 减少Hadoop集群中网络队头阻塞的调度算法 Reducing Head-of-Line Blocking on Network in Hadoop Clusters 计算机科学, 2022, 49(3): 11-22. https://doi.org/10.11896/jsjkx.210900117 |
[5] | 林潮伟, 林兵, 陈星. 边缘环境下基于模糊理论的科学工作流调度研究 Study on Scientific Workflow Scheduling Based on Fuzzy Theory Under Edge Environment 计算机科学, 2022, 49(2): 312-320. https://doi.org/10.11896/jsjkx.201000102 |
[6] | 谭双杰, 林宝军, 刘迎春, 赵帅. 基于机器学习的分布式星载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 |
[7] | 沈彪, 沈立炜, 李弋. 空间众包任务的路径动态调度方法 Dynamic Task Scheduling Method for Space Crowdsourcing 计算机科学, 2022, 49(2): 231-240. https://doi.org/10.11896/jsjkx.210400249 |
[8] | 杨林, 王永杰, 张俊. FAWA:一种异构执行体的负反馈动态调度算法 FAWA:A Negative Feedback Dynamic Scheduling Algorithm for Heterogeneous Executor 计算机科学, 2021, 48(8): 284-290. https://doi.org/10.11896/jsjkx.200900059 |
[9] | 宋海宁, 焦健, 刘永. 高速公路中的移动边缘计算研究 Research on Mobile Edge Computing in Expressway 计算机科学, 2021, 48(6A): 383-386. https://doi.org/10.11896/jsjkx.200900212 |
[10] | 王政, 姜春茂. 一种基于三支决策的云任务调度优化算法 Cloud Task Scheduling Algorithm Based on Three-way Decisions 计算机科学, 2021, 48(6A): 420-426. https://doi.org/10.11896/jsjkx.201000023 |
[11] | 宁玉辉, 姚喜. 一种应急指挥系统的设计与实现 Design and Implementation of Emergency Command System 计算机科学, 2021, 48(6A): 613-618. https://doi.org/10.11896/jsjkx.201000136 |
[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] | 马泽华, 刘波, 林伟伟, 李加伟. 无服务器平台资源调度综述 Survey of Resource Scheduling for Serverless Platforms 计算机科学, 2021, 48(4): 261-267. https://doi.org/10.11896/jsjkx.200800023 |
[14] | 王锡龙, 李鑫, 秦小麟. 电力物联网下分布式状态感知的源网荷储协同调度 Collaborative Scheduling of Source-Grid-Load-Storage with Distributed State Awareness UnderPower Internet of Things 计算机科学, 2021, 48(2): 23-32. https://doi.org/10.11896/jsjkx.200900209 |
[15] | 蒋从锋, 殷继亮, 胡海周, 闫龙川, 张纪林, 万健, 仇烨亮. 混合部署数据中心失效负载分析 Analysis of Workload Failure in Co-located Data Centers 计算机科学, 2021, 48(11A): 225-231. https://doi.org/10.11896/jsjkx.201200066 |
|