一种针对动态部分可重构SoC软硬件划分的高效MILP模型

doi:10.11896/jsjkx.190300001

摘要/Abstract

摘要： 异构片上系统(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图,并使用整数线性规划求解工具对问题进行求解。大量求解结果表明,新的模型能够有效地降低模型复杂度,缩短求解时间;并且随着问题规模的增大,所提模型在求解时间上的优势表现得更加显著。

关键词: DPR-SoC , FPGA, 动态部分可重构, 混合整数线性规划, 软硬件划分

Abstract: Heterogeneous System-on-Chip (SoC) integrates multiple types of processors on the same chip.It has great advantages in many aspects such as processing capacity,size,weight and power consumption,which makes it be widely used in many fields.The SoC with dynamic partial reconfigurability is an important type of heterogeneous SoC,which combines software flexibility with hardware efficiency.The design of such systems usually involves hardware and software coordination problems,and how to divide the software and hardware of the application is the key technology to ensure the real-time performance of the system.The hardware and software partitioning technology in this kind of system is a key technology for ensuring real-time system performance.The problem of hardware and software partitioning in DPR-SoC can be classified as a combinatorial optimization problem.The goal of this problem is to obtain the optimal solution with the shortest schedule length,including task mapping,sorting,and timing.Mixed integer linear programming (MILP) is an effective method for solving combinatorial optimization problems.However,building a proper model for a specific problem is the key part of solving the problem,which has great impacts on solving time.The existing MILP models for the HW/SW partitioning of DPR-SoC have a lot of variables and constraint equations.The redundant variables and constraint equations have negative impacts on solving time.Besides,the solution of the available method does not match with actual applications,for it makes too many assumptions.Basing on these exiting problems proposes a novel model which focuses on reducing the model complexity and improving its suitability to the application.Model the application as a DAG graph and solve the problem by an integer linear programming solver.Plenty of results show that the proposed model can reduce the model complexity and shorten the solving time.Further,as the scale of the problem grows,the solve time shortened more significantly.

Key words: DPR-SoC, Dynamic partial reconfiguration, FPGA, HW/SW partitioning, Mixed-integer linear programming

中图分类号:

TP302

朱丽花, 王玲, 唐麒, 魏急波. 一种针对动态部分可重构SoC软硬件划分的高效MILP模型[J]. 计算机科学, 2020, 47(4): 18-24. https://doi.org/10.11896/jsjkx.190300001

ZHU Li-hua, WANG Ling, TANG Qi, WEI Ji-bo. Efficient MILP Model for HW/SW Partitioning of Dynamic Partial Reconfigurable SoC[J]. Computer Science, 2020, 47(4): 18-24. https://doi.org/10.11896/jsjkx.190300001

参考文献

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

相关文章 15

[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

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed