Computer Science

Computer Science ›› 2020, Vol. 47 ›› Issue (4): 18-24.doi: 10.11896/jsjkx.190300001

• Computer Architecture • Previous Articles     Next Articles

Efficient MILP Model for HW/SW Partitioning of Dynamic Partial Reconfigurable SoC

ZHU Li-hua1,2, WANG Ling1, TANG Qi2, WEI Ji-bo2   

  1. 1 College of Electrical and Information Engineering,Hunan University,Changsha 410082,China;
    2 College of Electronic Science,National University of Defense Technology,Changsha 410073,China
  • Received:2019-02-05 Online:2020-04-15 Published:2020-04-15
  • Contact: WANG Ling,born in 1962,Ph.D,Professor,Ph.D supervisor,is not a member of China Computer Federation.Her main research interests include digital signal processing and radio communication.
  • About author:ZHU Li-hua,born in 1995,postgraduate,is not a member of China Computer Federation.Her main research interests include software-defined radio and resource virtualization.
  • Supported by:
    This work was supported by the National Natural Science Foundation of China(61601482).

PDF (PC)

1189

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

CLC Number: 

  • TP302
[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] WANG Deng-tian, ZHOU Hua, QIAN He-yue. LDPC Adaptive Minimum Sum Decoding Algorithm and Its FPGA Implementation [J]. Computer Science, 2021, 48(6A): 608-612.
[2] 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.
[3] QI Yan-rong, ZHOU Xia-bing, LI Bin, ZHOU Qing-lei. FPGA-based CNN Image Recognition Acceleration and Optimization [J]. Computer Science, 2021, 48(4): 205-212.
[4] WANG Zhe, TANG Qi, WANG Ling, WEI Ji-bo. Joint Optimization Algorithm for Partition-Scheduling of Dynamic Partial Reconfigurable Systems Based on Simulated Annealing [J]. Computer Science, 2020, 47(8): 26-31.
[5] CHEN Li-feng, ZHU Lu-ping. Encrypted Dynamic Configuration Method of FPGA Based on Cloud [J]. Computer Science, 2020, 47(7): 278-281.
[6] ZHAO Bo, YANG Ming, TANG Zhi-wei and CAI Yu-xin. Intelligent Video Surveillance Systems Based on FPGA [J]. Computer Science, 2020, 47(6A): 609-611.
[7] LI Bin, ZHOU Qing-lei, SI Xue-ming, CHEN Xiao-jie. Optimized Implementation of Office Password Recovery Based on FPGA Cluster [J]. Computer Science, 2020, 47(11): 32-41.
[8] ZHOU Hui-ting, ZHOU Jie. Simulation and Analysis on Improved NC-OFDM Algorithm [J]. Computer Science, 2020, 47(10): 263-268.
[9] JIA Xun, QIAN Lei, WU Gui-ming, WU Dong, XIE Xiang-hui. Research Advances and Future Challenges of FPGA-based High Performance Computing [J]. Computer Science, 2019, 46(11): 11-19.
[10] LI Lang and LIU Bo-tao. Surge:A New Low-resource and Efficient Lightweight Block Cipher [J]. Computer Science, 2018, 45(2): 236-240.
[11] HE Lu-bei, LI Jun-nan, YANG Xiang-rui and SUN Zhi-gang. RESSP:An FPGA-based REconfigurable SDN Switching Architecture [J]. Computer Science, 2018, 45(1): 205-210.
[12] LI Yi-ke and WANG Zhan. Hardware Implementation of Fast Huffman Coding Based on Different Sorting Methods [J]. Computer Science, 2017, 44(Z11): 476-479.
[13] PAN Qing-song, ZHANG Yi, YANG Zong-ming and QIN Jian-xiu. Design and Implementation of Image Corner and Edge Detection System Based on Zynq [J]. Computer Science, 2017, 44(Z11): 530-533.
[14] WANG Jian-zhong and YANG Lu. Data Acquisition and Transmission in High Speed Real-time System [J]. Computer Science, 2016, 43(Z11): 604-606.
[15] ZHU Xiang-yuan, LI Ren-fa, LI Ken-li and HU Zhong-wang. Advances in Biological Sequence Alignment Parallel Processing Based on Heterogeneous Systems [J]. Computer Science, 2015, 42(Z11): 390-395.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.