计算机科学 ›› 2020, Vol. 47 ›› Issue (4): 18-24.doi: 10.11896/jsjkx.190300001
朱丽花1,2, 王玲1, 唐麒2, 魏急波2
ZHU Li-hua1,2, WANG Ling1, TANG Qi2, WEI Ji-bo2
摘要: 异构片上系统(System-on-Chip,SoC)在同一芯片上集成了多种类型的处理器,在处理能力、尺寸、重量、功耗等各方面有较大优势,因此在很多领域得到了应用。具有动态部分可重构特性的SoC(Dynamic Partial Reconfigurability SoC,DPR-SoC)是异构SoC的一种重要类型,这种系统兼具了软件的灵活性和硬件的高效性。此类系统的设计通常涉及到软硬件协同问题,其中如何进行应用的软硬件划分是保证系统实时性的关键技术。DPR-SoC中的软硬件划分问题可归类为组合优化问题,问题目标是获得调度长度最短的调度方案,包括任务映射、排序和定时。混合整数线性规划(Mixed Integer Linear Programming,MILP)是求解组合优化问题的一种有效方法;然而,将具体问题建模为MILP模型是求解问题的关键一环,不同建模方式对问题求解时间有重要影响。已有针对DPR-SoC软硬件划分问题的MILP模型存在大量变量和约束方程,对问题求解时间产生了不利影响;此外,其假设条件过多,使得求解结果与实际应用不符。针对这些问题,提出了一种新颖的MILP模型,其极大地降低了模型复杂度,提高了求解结果与实际应用的符合度。将应用建模成DAG图,并使用整数线性规划求解工具对问题进行求解。大量求解结果表明,新的模型能够有效地降低模型复杂度,缩短求解时间;并且随着问题规模的增大,所提模型在求解时间上的优势表现得更加显著。
中图分类号:
[1]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,2007,14(11):1189-1202. [2]BAMBAGINI M,MARINONI M,AYDIN H,et al.Energy-Aware Scheduling for Real-Time Systems:A Survey[J].Acm Transactions on Embedded Computing Systems,2016,15(1):1-34. [3]DAVIS R I,BURNS A.A survey of hard real-time scheduling for multiprocessor systems[J].Acm Computing Surveys,2011,43(4):1-44. [4]ABDELHALIM M B,SALAMA A E,HABIB E D.Hardware Software Partitioning using Particle Swarm Optimization Technique[C]//The International Workshop on System-On-Chip for Real-Time Applications.IEEE,2006:189-194. [5]MOUNA A,YASSINE M,JOSEPH H.Hardware/Software Codesign Approach for heterogeneous MPSoC system [J].IJCSNS International Journal of Computer Science and Network Security,2018,18 (1):10-17. [6]SHENG W,HE W,JIANG J,et al.Pareto Optimal Temporal Partition methodology for Reconfigurable Architectures Based on Multi-objective Genetic Algorithm[C]//2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops & PhD Forum.2012:425-430. [7]HE H,DOU Q,XU W X.Hard/software partitioning for heterogeneous multicore SoC using genetic algorithm[C]//2012 Se-cond Internstionsl Conference on Intelligent System Design and Engineering Application.2012:1267-1270. [8]LI L Y,HAN S J.Hardware/software partitioning based on combination of genetic algorithm and simulated annealing[J].Computer Engineering & Applications,2010,46(28):73-76. [9]CORDONE R,REDAELLI F,REDAELLI M A,et al.Partitioning and Scheduling of Task Graphs on Partially Dynamically Reconfigurable FPGAs [J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2009,28(5):662-675. [10]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).2014:470-476. [11]MA Y C,ZHANG C,LUK W.Hybrid two-stage HW/SW partitioning algorithm for dynamic partial reconfigurable FPGAs[J].Journal of Tsinghua University (Science and Technology),2016,56(3):246-252,261. [12]WU J,WILLIAMS J,BERGMANN N.An ILP formulation for architectural synthesis and application mapping on FPGA-based hybrid multi-processor SOC[C]//2008 International Conference on Field Programmable Logic and Applications.Heidelberg,2008:451-454. [13]REDAELLI F,SANTAMBROGIO M D,OGRENCI M S.An ILP 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. [14]YUH P H,YANG C L,LI C F,et al.Leakage-aware task sched-uling for partially dynamically reconfigurable FPGAs[J].Acm Transactions on Design Automation of Electronic Systems,2009,14(4):2241-2256. [15]DEIANA E A,RABOZZˇ I 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).2015:1-6. [16]PURGATO A,TANTILLO D,RABOZZI M,et al.Resource-Efficient Scheduling for Partially-Reconfigurable FPGA-Based Systems[C]//Parallel and Distributed Processing Symposium Workshops,2016 IEEE International.IEEE,2016:189-197. [17]VENUGOPALAN S,SINNEN O.ILP formulations for Optimal Task Scheduling with Communication Delays on Parallel Systems[J].IEEE Transactions on Parallel & Distributed Systems,2014,26(1):142-151. [18]Xilnix partial reconfiguration user guide [EB/OL].http://www.xilinx.com/support/documentation navigation/design-hubs/dh0017-vivado-partial-reconfiguration-hub.html. [19]HE L B,LI J N,YANG X R,et al.RESSP:An FPGA-based REconfigurable SDN Switching Architecture[J].Computer Science,2018,45(1):205-210. [20]LI L,HAN W B.Implementation of Pipeline Structure on FPGA for SHA-1[J].Computer Science,2011,38(7):58-60. [21]Zynq-7000 [EB/OL].http://101.96.10.63/china.xilinx.com/support/documentation/data_sheets/ds190-Zynq-7000-Overview.pdf. [22]ALOUANI I,MEDIOUNI B L,NIAR S.A multi-objective approach for software/hardware partitioning in a multi-target tracking system[C]//International Symposium on Rapid System Prototyping.IEEE,2015:119-125. [23]KRYJAK T,KOMORKIEWIEZ M,GORGON M.Real-time hardware-software embedded vision system for ITS smart camera implemented in ZynqSoC[J].Journal of Real-Time Image Processing,2018,15(1):123-159. [24]NGO T D,MARTIN J M,DIGUET J P.Move Based Algorithm for Runtime Mapping of Dataflow Actors on Heterogeneous MPSoCs[J].Journal of Signal Processing Systems,2017,87(1):63-80. [25]WU J,WILLIAMS J ,BERGMANN N.An ILP formulation for architectural synthesis and application mapping on FPGA-based hybrid multi-processor SOC[C]//2008 International Conference on Field Programmable Logic and Applications.Heidelberg,2008:451-454. [26]SCHWIEGELSHOHN F,HUBNER M.An application scenario for dynamically reconfigurable FPGAs[C]//International Symposium on Reconfigurable and Communication-Centric Systems-On-Chip.IEEE,2014:1-8. [27]HE R,MA Y,ZHAO K,et al.ISBA:An independent set-based algorithm for automated partial reconfiguration module generation[C]//ACM International Conference on Computer-Aided Design (ICCAD).2012:500-507. [28]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,PP(99):1-1. [29]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:79-91. [30]TANG Q,WU S F,SHI J W,et al.Modeling of schedule-aware synchronous dataflow[J].Journal of National University of Defense Technology,2017,39(2):128-133. [31]Lindo API 11 [EB/OL].https://www.lindo.com/index.php/products/lindo-api-for-custom-optimiz. |
[1] | 王登天, 周华, 钱荷玥. LDPC自适应最小和译码算法及其FPGA实现 LDPC Adaptive Minimum Sum Decoding Algorithm and Its FPGA Implementation 计算机科学, 2021, 48(6A): 608-612. https://doi.org/10.11896/jsjkx.200800134 |
[2] | 郭彪, 唐麒, 文智敏, 傅娟, 王玲, 魏急波. 一种面向动态部分可重构片上系统的列表式软硬件划分算法 List-based Software and Hardware Partitioning Algorithm for Dynamic Partial Reconfigurable System-on-Chip 计算机科学, 2021, 48(6): 19-25. https://doi.org/10.11896/jsjkx.200700198 |
[3] | 齐延荣, 周夏冰, 李斌, 周清雷. 基于FPGA的CNN图像识别加速与优化 FPGA-based CNN Image Recognition Acceleration and Optimization 计算机科学, 2021, 48(4): 205-212. https://doi.org/10.11896/jsjkx.200600089 |
[4] | 王喆, 唐麒, 王玲, 魏急波. 一种基于模拟退火的动态部分可重构系统划分-调度联合优化算法 Joint Optimization Algorithm for Partition-Scheduling of Dynamic Partial Reconfigurable Systems Based on Simulated Annealing 计算机科学, 2020, 47(8): 26-31. https://doi.org/10.11896/jsjkx.200500110 |
[5] | 陈利锋, 朱路平. 一种基于云端加密的FPGA自适应动态配置方法 Encrypted Dynamic Configuration Method of FPGA Based on Cloud 计算机科学, 2020, 47(7): 278-281. https://doi.org/10.11896/jsjkx.190700110 |
[6] | 赵博, 杨明, 汤志伟, 蔡玉鑫. 基于FPGA的智能视频加速检索系统 Intelligent Video Surveillance Systems Based on FPGA 计算机科学, 2020, 47(6A): 609-611. https://doi.org/10.11896/JsJkx.190700118 |
[7] | 李斌, 周清雷, 斯雪明, 陈晓杰. 基于FPGA集群的Office口令恢复优化实现 Optimized Implementation of Office Password Recovery Based on FPGA Cluster 计算机科学, 2020, 47(11): 32-41. https://doi.org/10.11896/jsjkx.200500040 |
[8] | 周惠婷, 周杰. 基于改进NC-OFDM算法的仿真设计与分析 Simulation and Analysis on Improved NC-OFDM Algorithm 计算机科学, 2020, 47(10): 263-268. https://doi.org/10.11896/jsjkx.190800043 |
[9] | 贾迅, 钱磊, 邬贵明, 吴东, 谢向辉. FPGA应用于高性能计算的研究现状和未来挑战 Research Advances and Future Challenges of FPGA-based High Performance Computing 计算机科学, 2019, 46(11): 11-19. https://doi.org/10.11896/jsjkx.191100500C |
[10] | 李浪,刘波涛. Surge:一种新型、低资源、高效的轻量级分组密码算法 Surge:A New Low-resource and Efficient Lightweight Block Cipher 计算机科学, 2018, 45(2): 236-240. https://doi.org/10.11896/j.issn.1002-137X.2018.02.041 |
[11] | 潘青松,张怡,杨宗明,秦剑秀. 基于Zynq的图像角点及边缘检测系统的设计与实现 Design and Implementation of Image Corner and Edge Detection System Based on Zynq 计算机科学, 2017, 44(Z11): 530-533. https://doi.org/10.11896/j.issn.1002-137X.2017.11A.112 |
[12] | 王建中,杨璐. 高速实时系统数据采集与传输 Data Acquisition and Transmission in High Speed Real-time System 计算机科学, 2016, 43(Z11): 604-606. https://doi.org/10.11896/j.issn.1002-137X.2016.11A.137 |
[13] | 朱香元,李仁发,李肯立,胡忠望. 基于异构系统的生物序列比对并行处理研究进展 Advances in Biological Sequence Alignment Parallel Processing Based on Heterogeneous Systems 计算机科学, 2015, 42(Z11): 390-395. |
[14] | 李浪,邹祎,贺位位,李仁发,刘波涛. 一种轻量级TWINE密码硬件优化实现研究 Research on Hardware Optimization Implementation of TWINE 计算机科学, 2015, 42(2): 127-130. https://doi.org/10.11896/j.issn.1002-137X.2015.02.027 |
[15] | 余娟,贺昱曜,冯晓华. 改进的分布估计算法求解软硬件划分问题 Solving HW/SW Partitioning Problem by Improved Estimation of Distribution Algorithm 计算机科学, 2014, 41(9): 285-289. https://doi.org/10.11896/j.issn.1002-137X.2014.09.054 |
|