一种面向动态部分可重构片上系统的列表式软硬件划分算法

doi:10.11896/jsjkx.200700198

计算机科学 ›› 2021, Vol. 48 ›› Issue (6): 19-25.doi: 10.11896/jsjkx.200700198

一种面向动态部分可重构片上系统的列表式软硬件划分算法

郭彪^1,2, 唐麒², 文智敏³, 傅娟⁴, 王玲¹, 魏急波²

1 湖南大学电气与信息工程学院长沙410082
2 国防科技大学电子科学学院长沙410073
3 长沙轨道交通运营有限公司车辆部长沙410000
4 军事科学院系统工程研究院北京100101

收稿日期:2020-07-30 修回日期:2020-08-20 出版日期:2021-06-15 发布日期:2021-06-03
通讯作者: 唐麒(q.tang.andy@qq.com)

List-based Software and Hardware Partitioning Algorithm for Dynamic Partial Reconfigurable System-on-Chip

GUO Biao^1,2, TANG Qi², WEN Zhi-min³, FU Juan⁴, WANG Ling¹, WEI Ji-bo²

1 College of Electrical and Information Engineering,Hunan University,Changsha 410082,China
2 School of Electronic Science and Technology,National University of Defense Technology,Changsha 410073,China
3 Vehicle Department of Changsha Rail Transit Operation Co.,Ltd,Changsha 410000,China
4 Institute of System Engineering,Academy of Chinese PLA Military Science,Beijing 100101,China

Received:2020-07-30 Revised:2020-08-20 Online:2021-06-15 Published:2021-06-03
About author:GUO Biao,born in 1995,postgraduate.His main research interests include software defined radio and dynamic partially reconfiguration technology of FPGA.(guobiao@hnu.edu.cn)
TANG Qi,born in 1986,Ph.D,assistant professor.His main research interests include reconfigurable computing,embedded parallel computing,algorithm designand software defined system.

摘要/Abstract

摘要： 并行计算是提高系统资源利用率的重要手段,越来越多的多处理器片上系统通过集成具有不同功能特点的处理器来满足不同计算任务的需求。具备动态部分可重构特性的异构多处理器片上系统(Dynamic Partial Reconfiguration-Heteroge-neous Multiprocessor Systems-on-Chip,DPR-HMPSoC)因其并行性好、计算效率高而被广泛使用,而低复杂度和高求解性能的软硬件划分算法是充分发挥其计算性能优势的重要保证。已有的相关软硬件划分算法时间复杂度高,且对DPR-HMPSoC平台的支撑不足。针对上述问题,首先提出了一种列表启发式软硬件划分与调度算法,其通过构建基于任务优先级的调度列表,完成任务的调度、映射、FPGA动态部分可重构区域划分等一系列操作;接着给出了软件应用建模、计算平台建模及所提算法的详细设计方案。仿真实验结果表明,所提算法与混合整数线性规划(Mixed Integral Linear Programming,MILP)和蚁群优化(Ant Colony Optimization,ACO)算法相比,可有效减少求解时间,且时间优势与任务规模成正比;在调度长度方面,所提算法的平均性能提升了约10%。

关键词: 调度, 动态部分可重构, 列表启发式, 软硬件划分, 现场可编程逻辑门阵列

Abstract: Parallel computing is an important means to improve the utilization rate of system resources.More and more systems on multi-processor chip meet the requirements of different computing tasks by integrating processors with different functional characteristics.A heterogeneous multiprocessor system-on-chip (DPR-HMPSoC) with dynamic partial reconfigurability is widely used because of its good parallelism and high computing efficiency,while the software/hardware partitioning algorithm with low complexity and high solving performance is an important guarantee for giving full play to its computational performance advantages.The existing related software/hardware partitioning algorithms have high time complexity and insufficient support for the DPR-HMPSoC platform.In response to the above problems,this paper proposes a list heuristic software/hardware partitioning and scheduling algorithm.By constructing a scheduling list based on task priority,a series of operations such as task scheduling,mapping and FPGA dynamic partial reconfigurable area partitioning are completed.It introduces software application mode-ling,computing platform modeling,and the detailed design scheme of the proposed algorithm.The simulation experiment results show that the proposed algorithm can effectively reduce the solution time compared with the MILP and ACO algorithms,and the time advantage is proportional to the task scale.In terms of scheduling length,the average performance of the proposed algorithm is improved by about 10%.

Key words: Dynamic partial reconfigurable, FPGA, List-based heuristics, Scheduling, Software/hardware partitioning

中图分类号:

TP302

郭彪, 唐麒, 文智敏, 傅娟, 王玲, 魏急波. 一种面向动态部分可重构片上系统的列表式软硬件划分算法[J]. 计算机科学, 2021, 48(6): 19-25. https://doi.org/10.11896/jsjkx.200700198

GUO Biao, TANG Qi, WEN Zhi-min, FU Juan, WANG Ling, WEI Ji-bo. List-based Software and Hardware Partitioning Algorithm for Dynamic Partial Reconfigurable System-on-Chip[J]. Computer Science, 2021, 48(6): 19-25. https://doi.org/10.11896/jsjkx.200700198

参考文献

[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.

相关文章 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]	柳鹏, 刘波, 周娜琴, 彭心怡, 林伟伟. 混合云工作流调度综述 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

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

一种面向动态部分可重构片上系统的列表式软硬件划分算法

List-based Software and Hardware Partitioning Algorithm for Dynamic Partial Reconfigurable System-on-Chip

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0