Computer Science

Computer Science ›› 2020, Vol. 47 ›› Issue (8): 26-31.doi: 10.11896/jsjkx.200500110

;

Previous Articles     Next Articles

Joint Optimization Algorithm for Partition-Scheduling of Dynamic Partial Reconfigurable Systems Based on Simulated Annealing

WANG Zhe1, 2, TANG Qi2, WANG Ling1, WEI Ji-bo2,   

  1. 1 College of Electrical and Information Engineering, Hunan University, Changsha 410082, China
    2 College of Electronic Science and Technology, National University of Defense Technology, Changsha 410073, China
  • Online:2020-08-15 Published:2020-08-10
  • About author:WANG Zhe, born in 1995, postgra-duate.His main research interests include software defined radio and reconfiguring computing.
    WANG Ling, born in 1962, Ph.D, professor.Her main research interests include digital signal processing and radio communication.

PDF (PC)

856

Abstract: Dynamically partially reconfigurable (DPR) technology based on FPGA has many applications in the field of high-performance computing because of its advantages in processing efficiency and power consumption.In the DPR system, the partition of the reconfigurable region and task scheduling determine the performance of the entire system.Therefore, how to model the lo-gic resource partition and scheduling of the DPR system and devising an efficient solution algorithm are the keys to ensure the performance of the system.Based on the establishment of the partition and scheduling model, a joint optimization algorithm of DPR system partition-scheduling based on simulated annealing (SA) is designed to optimize the reconfigurable region partitioning and task scheduling.A new method is proposed for skip infeasible solutions and poor solutions effectively which accelerates the search of solution space and increases the convergence speed of the SA algorithm.Experimental results show that, compared with mixed integer linear programming (MILP) and IS-k, the proposed algorithm based on SA has lower time complexity, and for the large-scale applications, it can solve better partition and scheduling results in a short time.

Key words: Dynamically partially reconfigurable, FPGA, Partition, Scheduling, Simulated annealing

CLC Number: 

  • TP302
[1]Xilinx, Inc.Vivado Design Suite User Guide Partial Reconfiguration[OL].https://www.xilinx.com/support/documentation/sw_manuals/xilinx2020_1/ug909-vivado-partial-reconfiguration.pdf.
[2]SAHA S, SARKAR A, CHAKRABARTI A.Scheduling dynamic hard real-time task sets on fully and partially reconfigurable platforms[J].IEEE Embedded Systems Letters, 2015, 7(1):23-26.
[3]DEIANA E A, RABOZZI 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).IEEE, 2015:1-6.
[4]RABOZZI M, LILLIS J, SANTAMBROGIO M D.Floorplanning for partially-reconfigurable fpga systems via mixed-integer linear programming[C]∥2014 IEEE 22nd Annual International Symposium on Field-Programmable Custom Computing Machines.IEEE, 2014:186-193.
[5]SEYOUM B B, BIONDI A, BUTTAZZO G C.FLORA:Floorplan Optimizer for Reconfigurable Areas in FPGAs[J].ACM Transactions on Embedded Computing Systems (TECS), 2019, 18(S5):1-20.
[6]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.
[7]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).IEEE, 2014:470-476.
[8]SALAMY H, ASLAN S.A genetic algorithm based approach to pipelined memory-aware scheduling on an MPSoC[C]∥2015 IEEE Dallas Circuits and Systems Conference (DCAS).IEEE, 2015:1-4.
[9]CHARITOPOULOS G, KOIDIS I, PAPADIMITRIOU K, et al.Hardware task scheduling for partially reconfigurable FPGAs[C]∥International Symposium on Applied Reconfigurable Computing.Springer, Cham, 2015:487-498.
[10]RABOZZI M, DURELLI G C, MIELE A, et al.Floorplanning automation for partial-reconfigurable FPGAs via feasible placements generation[J].IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2016, 25(1):151-164.
[11]XIE D, SONG L F, DONG Y P, et al.Efficient dynamic partial Reconfigurable Design of FPGA based on clustering Partition algorithm [J].Electronics and Packaging, 2018, 18(9):8, 14.
[12]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-2013).IEEE, 2013:47-54.
[13]TANG Q, WU S, SHI J, et al.Modeling of schedule-aware synchronous dataflow[J].Journal of National University of Defense Technology, 2017(2):19.
[14]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 and distributed systems, 2016, 28(3):826-837.
[15]DHAR A, YU M, ZUO W, et al.Leveraging Dynamic PartialReconfiguration with Scalable ILP Based Task Scheduling[C]∥2020 33rd International Conference on VLSI Design and 2020 19th International Conference on Embedded Systems (VLSID).IEEE, 2020:201-206.
[16]CANON L C, SAYAH M E, PIERRE-CYRILLE H.A Comparison of Random Task Graph Generation Methods for Scheduling Problems[M]∥Euro-Par 2019:Parallel Processing.2019.
[17]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.
[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] YANG Tao-yu, XU Yuan-yuan, TAN Zeng-jie. Tile Partition Optimized Omnidirectional Video Coding for 6G Network [J]. Computer Science, 2022, 49(6): 66-72.
[4] 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.
[5] 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.
[6] 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.
[7] 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.
[8] SHEN Biao, SHEN Li-wei, LI Yi. Dynamic Task Scheduling Method for Space Crowdsourcing [J]. Computer Science, 2022, 49(2): 231-240.
[9] WANG Ru-bin, LI Rui-yuan, HE Hua-jun, LIU Tong, LI Tian-rui. Distributed Distance Join Algorithm for Massive Spatial Data [J]. Computer Science, 2022, 49(1): 95-100.
[10] 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.
[11] GAO Shi-shun, ZHAO Hai-tao, ZHANG Xiao-ying, WEI Ji-bo. Self-adaptive Intelligent Wireless Propagation Model to Different Scenarios [J]. Computer Science, 2021, 48(7): 324-332.
[12] ZHANG Ju, LI Xue-yun. Research on Intelligent Production Line Scheduling Problem Based on LGSO Algorithm [J]. Computer Science, 2021, 48(6A): 668-672.
[13] WANG Guo-wu, CHEN Yuan-yan. Improvement of DV-Hop Location Algorithm Based on Hop Correction and Genetic Simulated Annealing Algorithm [J]. Computer Science, 2021, 48(6A): 313-316.
[14] WANG Zheng, JIANG Chun-mao. Cloud Task Scheduling Algorithm Based on Three-way Decisions [J]. Computer Science, 2021, 48(6A): 420-426.
[15] 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.
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.