Computer Science ›› 2021, Vol. 48 ›› Issue (6): 19-25.doi: 10.11896/jsjkx.200700198

• Computer Architecture • Previous Articles     Next Articles

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

GUO Biao1,2, TANG Qi2, WEN Zhi-min3, FU Juan4, WANG Ling1, WEI Ji-bo2   

  1. 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: 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

CLC Number: 

  • TP302
[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] TIAN Zhen-zhen, JIANG Wei, ZHENG Bing-xu, MENG Li-min. Load Balancing Optimization Scheduling Algorithm Based on Server Cluster [J]. Computer Science, 2022, 49(6A): 639-644.
[2] ZHANG Jie, TANG Qiang, LIU Shuo-han, CAO Yue, ZHAO Wei, LIU Tao, XIE Shi-ming. Priority Based EV Charging Management Under Service Reservation in Smart Grid [J]. Computer Science, 2022, 49(6): 55-65.
[3] LIU Peng, LIU Bo, ZHOU Na-qin, PENG Xin-yi, LIN Wei-wei. Survey of Hybrid Cloud Workflow Scheduling [J]. Computer Science, 2022, 49(5): 235-243.
[4] TIAN Bing-chuan, TIAN Chen, ZHOU Yu-hang, CHEN Gui-hai, DOU Wan-chun. Reducing Head-of-Line Blocking on Network in Hadoop Clusters [J]. Computer Science, 2022, 49(3): 11-22.
[5] LIN Chao-wei, LIN Bing, CHEN Xing. Study on Scientific Workflow Scheduling Based on Fuzzy Theory Under Edge Environment [J]. Computer Science, 2022, 49(2): 312-320.
[6] TAN Shuang-jie, LIN Bao-jun, LIU Ying-chun, ZHAO Shuai. Load Scheduling Algorithm for Distributed On-board RTs System Based on Machine Learning [J]. Computer Science, 2022, 49(2): 336-341.
[7] SHEN Biao, SHEN Li-wei, LI Yi. Dynamic Task Scheduling Method for Space Crowdsourcing [J]. Computer Science, 2022, 49(2): 231-240.
[8] YANG Lin, WANG Yong-jie, ZHANG Jun. FAWA:A Negative Feedback Dynamic Scheduling Algorithm for Heterogeneous Executor [J]. Computer Science, 2021, 48(8): 284-290.
[9] ZHANG Ju, LI Xue-yun. Research on Intelligent Production Line Scheduling Problem Based on LGSO Algorithm [J]. Computer Science, 2021, 48(6A): 668-672.
[10] WANG Zheng, JIANG Chun-mao. Cloud Task Scheduling Algorithm Based on Three-way Decisions [J]. Computer Science, 2021, 48(6A): 420-426.
[11] 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.
[12] NING Yu-hui, YAO Xi. Design and Implementation of Emergency Command System [J]. Computer Science, 2021, 48(6A): 613-618.
[13] 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.
[14] MA Ze-hua, LIU Bo, LIN Wei-wei, LI Jia-wei. Survey of Resource Scheduling for Serverless Platforms [J]. Computer Science, 2021, 48(4): 261-267.
[15] GAO Ji-ji, YUE Xue-rong, CHEN Zhi-bin. Approximate Ratios Analysis of New Algorithm for Classical Parallel Scheduling [J]. Computer Science, 2021, 48(4): 37-42.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!