A Survey: FPGA-Based Dynamic Scheduling of Hardware Tasks

LI Tianyang; ZHANG Fan; GUO Wei; SUN Mingqian; CHEN Li

doi:10.1049/cje.2021.07.021

Volume 30 Issue 6

Nov. 2021

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2021 > 30(6): 991-1007

LI Tianyang, ZHANG Fan, GUO Wei, et al., “A Survey: FPGA-Based Dynamic Scheduling of Hardware Tasks,” Chinese Journal of Electronics, vol. 30, no. 6, pp. 991-1007, 2021, doi: 10.1049/cje.2021.07.021

Citation:

LI Tianyang, ZHANG Fan, GUO Wei, et al., “A Survey: FPGA-Based Dynamic Scheduling of Hardware Tasks,” Chinese Journal of Electronics, vol. 30, no. 6, pp. 991-1007, 2021, doi: 10.1049/cje.2021.07.021

Citation:

PDF( 3901 KB)

A Survey: FPGA-Based Dynamic Scheduling of Hardware Tasks

doi: 10.1049/cje.2021.07.021

LI Tianyang^1,2,
ZHANG Fan^{1,2
,
,},
GUO Wei^1,2,
SUN Mingqian³,
CHEN Li^1,2

1. PLA Strategic Support Force Information Engineering University, Zhengzhou 450002, China;
2. National Digital Switching System Engineering and Technological R&D Center, Zhengzhou 450003, China;
3. Southeast University, Nanjing 210000, China

Funds:

This work is supported by the National Natural Science Foundation of China (No.61521003).

Received Date: 2020-12-09
Rev Recd Date: 2021-04-07

Available Online: 2021-09-23

Publish Date: 2021-11-05

Abstract

Abstract

To meet the increasing computing needs of various application fields, Field programmable gate array (FPGA) has been widely deployed. In FPGA-based processing, hardware tasks can be better accelerated by allocating appropriate computing resources. Therefore, FPGA-based hardware task scheduling has become one of the mainstream research directions in academia and industry. However, the optimization objectives of existing FPGA-based hardware task scheduling methods are relatively scattered. In this regard, this paper summarizes the research status of hardware task dynamic scheduling from the three essential elements of FPGA processing:time, resources, and power consumption. This paper analyzes, sorts out, categorizes the ideas and implementations of various scheduling methods and analyzes and evaluates optimization effects of various scheduling methods from multiple dimensions. Then, the shortcomings of the existing methods are summarized and some practical applications are introduced. Finally, the research direction of task scheduling based on FPGA is prospected and summarized.
- Field programmable gate array,
- Task scheduling,
- Optimization,
- Resource management,
- Dynamic reconfiguration

FullText(HTML)

References(87)

References

I.L. Markov, "Limits on fundamental limits to computation", Nature, Vol.512, No.7513, pp.147-154, 2014.

A. Putnam, A.M. Caulfield, E.S. Chung, et al. "A reconfigurable fabric for accelerating large-scale datacenter services", Proc. of International Symposium on Computer Architecture, USA, pp.13-24, 2014.

X. Liu, W. Liu, H. Ma, et al., "Large-scale vehicle reidentification in urban surveillance videos", Proc. of IEEE International Conference on Multimedia and Expo, City, State, USA, pp.1-6, 2016.

N. Tarafdar, T. Lin, E. Fukuda, et al., "Enabling flexible network FPGA clusters in a heterogeneous cloud data center", Proc. of ACM/SIGDA International Symposium, City, State, USA, pp.237-246, 2017.

D. Koch, "Partial reconfiguration on FPGAs:Architectures, tools and applications", Springer Science & Business Media, 2012.

S. Saha, A. Sarkar and A. Chakrabarti, "Scheduling dynamic hard real-time task sets on fully and partially reconfigurable platforms", IEEE Embedded Systems Letters, Vol.7, No.1, pp.23-26, 2015.

R. G. Michael and S. J. David, "Computers and intractability:A guide to the theory of np-completeness", W. H. Freeman and Company, San Fr, pp.90-91, 1979.

H. Murata, K. Fujiyoshi, S. Nakatake, et al., "Rectanglepacking-based module placement", Proc. of IEEE/ACM International Conference on Computer-aided Design, Springer, Boston, MA, pp.535-548, 2003.

M. M. Bassiri and H. S. Shahhoseini, "On-line HW/SW partitioning and co-scheduling in reconfigurable computing systems", Proc. of IEEE International Conference on Computer Science & Information Technology, pp.557-562, 2009.

Xilinx, "Vivado design suite user guide:Partial reconfiguration", https://china.xilinx.com/supportdocumentation/sw_manuals/xilinx2019_2/ug909-vivado-partialreconfiguration.pdf,2019.

P. Lysaght, B. Blodget, J. Mason, et al., "Enhanced architectures, design methodologies and CAD tools for dynamic reconfiguration of Xilinx FPGAs", Proc. of International Conference on Field Programmable Logic and Applications, Madrid, Spain, pp.1-6, 2006.

R.P. Dick, D.L. Rhodes and W. Wolf, "TGFF:Task graphs for free", Proc. of International Workshop on Hardware/software Codesign, Seattle, WA, USA, pp.97-101, 1998.

J. Angermeier and J. Teich, "Heuristics for scheduling reconfigurable devices with consideration of reconfiguration overheads", Proc. of IEEE International Symposium on Parallel & Distributed Processing, Miami, FL, USA, pp.1-8, 2008.

Hauck and Scott, "Configuration prefetch for single context reconfigurable coprocessors", International Symposium on Field Programmable Gate Arrays, Monterey, California, USA, pp.65-74, 1998.

S. Banerjee, E. Bozorgzadeh and N. Dutt, "Considering runtime reconfiguration overhead in task graph transformations for dynamically reconfigurable architectures", Proc. of IEEE Symposium on Field-programmable Custom Computing Machines, Napa, CA, USA, pp.273-274, 2005.

J. Resano, D. Mozos and F. Catthoor, "A hybrid designtime/run-time scheduling flow to minimise the reconfiguration overhead of FPGAs", Microprocessors and Microsystems, Vol.28, No.5, pp.291-301, 2004.

J. Resano, D. Verkest, D. Mozos, et al., "A hybrid prefetch scheduling heuristic to minimize at run-time the reconfiguration overhead of dynamically reconfigurable hardware", Proc. of Design, Automation and Test in Europe, Munich, Germany, pp.106-111, 2005.

Q.H. Khuat, D. Chillet and M. Hubner, "Considering reconfiguration overhead in scheduling of dependent tasks on 2D Reconfigurable FPGA", Proc. of NASA/ESA Conference on Adaptive Hardware & Systems, Leicester, UK, pp.1-8, 2014.

R. Ramezani, "A prefetch-aware scheduling for FPGA-based multi-task graph systems", The Journal of Supercomputing, Vol.76, pp.7140-7160, 2020.

L. Bauer, A. Grudnitsky, M. Shafique, et al., "PATS:A performance aware task scheduler for runtime reconfigurable processors", Proc. of IEEE International Symposium on Field-Programmable Custom Computing Machines, Toronto, ON, Canada, pp.208-215, 2012.

Z. Dai and T. Qu., "Task scheduling technology for coarsegrained dynamic reconfigurable system based on configuration prefetching and reuse", Journal of Electronics & Information Technology, Vol.41, No.6, pp.1458-1465, 2019. (in Chinese)

R. Cattaneo, R. Bellini, G. Durelli, et al., "PaRAsched:A reconfiguration-aware scheduler for reconfigurable architectures", Proc. of IEEE International Parallel & Distributed Processing Symposium Workshops, Phoenix, AZ, USA, pp.243-250, 2014.

A.A. Nacci, C. Pilato, R. Cattaneo, et al., "A2B:An integrated framework for designing heterogeneous and reconfigurable systems", Proc. of NASA/ESA Conference on Adaptive Hardware & Systems, Turin, Italy, pp.198-205, 2013.

Y. Lu, T. Marconi, K. Bertels, et al., "Online task scheduling for the FPGA-based partially reconfigurable systems", Proc. of International Workshop on Applied Reconfigurable Computing, Vol.5453, pp.216-230, 2009.

A. Al-Wattar, S. Areibi and F. Saffih, "Efficient on-line hardware/software task scheduling for dynamic run-time reconfigurable systems", Proc. of IEEE International Parallel and Distributed Processing Symposium Workshops & PhD Forum, Shanghai, China, pp.401-406, 2012.

I. Hariharan and M. Kannan, "Algorithms for reducing reconfiguration overheads using prefetch, reuse, and optimal mapping of tasks", Concurrency & Computation Practice & Experience, Vol.33, No.7, 2018.

M. Mansub, B. Hadi and S. Shahhoseini, "Configuration reusing in on-line task scheduling for reconfigurable computing systems", Journal of Computer Science & Technology, Vol.26, No.3, pp.463-473, 2011.

E.A. Deiana, M. Rabozzi, R. Cattaneo, et al., "A multiobjective reconfiguration-aware scheduler for FPGAbased heterogeneous architectures", Proc. of International Conference on ReConFigurable Computing and FPGAs, Riviera Maya, Mexico, pp.1-6, 2015.

S. Fekete, E. Kohler and J. Teich, "Optimal FPGA module placement with temporal precedence constraints", Proc. of Design, Automation and Test in Europe, Munich, Germany, pp.658-665, 2001.

Y. Lu, T. Marconi, K. Bertels, et al., "A communication aware online task sheduling algorithm for FPGA-based partially reconfigurable systems", Proc. of IEEE Annual International Symposium on Field-Programmable Custom Computing Machines, Charlotte, NC, USA, pp.65-68, 2010.

A.E. Cadi, O. Souissi, R.B. Atitallah, et al., "Mathematical programming models for scheduling in a CPU/FPGA architecture with heterogeneous communication delays", Journal of Intelligent Manufacturing, Vol.29, No.3, pp.629-640, 2018.

F. Abdallah, C. Tanougast, I. Kacem, et al., " A comparison of two metaheuristic algorithms for scheduling problem on a heterogeneous CPU/FPGA architecture with communication delays", Proc. of International Conference on Control, Barcelona, pp.0294-0299, 2017.

A.Ahmadinia, C.Bobda, D.Koch, et al., "Task scheduling for heterogeneous reconfigurable computers", Proc. of Symposium on Integrated Circuits and System Design, Pernambuco, Brazil, pp.22-27, 2004.

Y. Sheng, Y. Liu, R. Li, et al., "A communication-aware scheduling algorithm for hardware task scheduling model on FPGA-based reconfigurable systems", Journal of Computers, Vol.9, No.11, pp.65-68, 2014.

M. Huang, V.K. Narayana, H. Simmler, et al., "Reconfiguration and communication-aware task scheduling for highperformance reconfigurable computing", ACM Transactions on Reconfigurable Technology and Systems, Vol.3, No.4, pp.1-25, 2010.

A. Yoosefi and H.R. Naji, "A clustering algorithm for communication-aware scheduling of task graphs on multi-core reconfigurable systems", IEEE Transactions on Parallel & Distributed Systems, Vol.28, No.10, pp.2718-2732, 2017.

K. Bazargan and R. Kaster, "Fast template placement for reconfigurable computing systems", IEEE Design & Test of Computers, Vol.17, No.1, pp.68-83, 2017.

H. Walder, C. Steiger and M. Platzner, "Fast online task placement on FPGAs:Free space partitioning and 2Dhashing", Proc. of International Parallel and Distributed Processing Symposium, Nice, France, 8 pages, 2003.

T. Marconi, Y. Lu, K. Bertels, et al., "Intelligent merging online task placement algorithm for partial reconfigurable systems", Proc. of Design, Automation and Test in Europe, Munich, Germany, pp.1346-1351, 2008.

M. Handa and R. Vemuri, "An efficient algorithm for finding empty space for online FPGA placement", Proc. of Annual Design Automation Conference, San Diego, CA, USA, pp.960-965, 2004.

T. Li and Y. Yang, "Algorithms of reconfigurable resource management and hardware task placement", Journal of Computer Research and Development, Vol.2, No.22, pp.171-178, 2008. (in Chinese)

G. Wang, S. Liu, J. Nie, et al., "An online task placement algorithm based on maximum empty rectangles in dynamic partial reconfigurable systems", Proc. of NASA/ESA Conference on Adaptive Hardware and Systems, Pasadena, CA, USA, pp.180-185, 2017.

A. Ahmadinia, C. Bobda, M. Bednara, et al., "A new approach for on-line placement on reconfigurable devices", International Parallel and Distributed Processing Symposium, Santa Fe, NM, USA, 7 pages, 2004.

R. Davis and A. Burns, "A survey of hard real-time scheduling for multiprocessor systems", ACM Comput. Surv., Vol.43, No.4, 44 pages, 2011.

T. Marconi, Y. Lu, K. Bertels, et al., "A novel fast online placement algorithm on 2D partially reconfigurable devices", International Conference on Field-Programmable Technology, Sydney, NSW, Australia, pp.296-299, 2009.

J. Tabero, J. Septien, H. Mecha, et al., "Task placement heuristics based on 3D-adjacency and look-ahead in reconfigurable systems", Asia and South Pacific Conference on Design Automation, Yokohama, Japan, 6 pages, 2006.

T. Marconi, Y. Lu, K. Bertels, et al., "3D Compaction:A novel blocking-aware algorithm for online hardware task scheduling and placement on 2D partially reconfigurable devices", International Symposium on Applied Reconfigurable Computing, Bangkok, Thailand, pp.194-206, 2010.

J. Xu, L. Liu, W. Li, et al., "Reconfigurable hardware task scheduling algorithm based on 3D fragmentation layout strategy", Journal of Electronics & Information Technology, Vol.40, No.8, pp.247-254, 2018. (in Chinese)

G. Enemali, A. Adetomi and T. Arslan, "FAReP:Fragmentation-aware replacement policy for task reuse on reconfigurable FPGAs", IEEE International Parallel and Distributed Processing Symposium Workshops, Lake Buena Vista, FL, USA, pp.202-206, 2017.

K. Compton, Z. Li, J. Cooley, et al., "Configuration relocation and defragmentation for run-time reconfigurable computing", IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Vol.10, No.3, pp.209-220, 2002.

O. Diessel, H. ElGindy, M. Middendorf, et al., "Dynamic scheduling of tasks on partially reconfigurable FPGAs", IEE Proceedings-Computers and Digital Techniques, Vol.147, No.3, pp.181-188, 2000.

M.G. Gericota, G.R. Alves, M.L. Silva, et al., "Online defragmentation for run-time partially reconfigurable FPGAs", International Conference on Field Programmable Logic and Applications, Montpellier, France, pp.302-311, 1998.

G. Charitopoulos, I. Koidis, K. Papadimitriou, et al., "Hardware task scheduling for partially reconfigurable FPGAs", International Symposium on Applied Reconfigurable Computing, Bochum, Germany, pp.487-498, 2015.

A. Morales-Villanueva and A. Gordon-Ross, "HTR:Onchip hardware task relocation for partially reconfigurable FPGAs", International Symposium on Applied Reconfigurable Computing, Los Angeles, California, USA, pp.185-196, 2013.

G. Enemali, A. Adetomi and T. Arslan, "A placement management circuit for efficient realtime hardware reuse on FPGAs targeting reliable autonomous systems", International Symposium on Circuits and Systems, Baltimore, MD, pp.1-4, 2017.

T. Tuan and B. Lai, "Leakage power analysis of a 90nm FPGA", Custom Integrated Circuits Conference, San Jose, CA, USA, pp.57-60, 2003.

P.H. Yuh, C. Yang, C. Li, et al., "Leakage-aware task scheduling for partially dynamically reconfigurable FPGAs", ACM Trans. Des. Autom. Electron. Syst., Vol.14, No.4, 26 pages, 2009.

C. Li, P. Yuh, C. Yang, et al., "Post-placement leakage optimization for partially dynamically reconfigurable FPGAs", International Symposium on Low Power Electronics and Design, Portland, OR, USA, pp.92-97, 2007.

J. Hsieh, Y. Chang and W. Lee, "An enhanced leakage-aware scheduler for dynamically reconfigurable FPGAs", Asia and South Pacific Design Automation Conference, Yokohama, Japan, pp.661-667, 2011.

N.K. Pham, A.K. Singh and A. Kumar, "A multi-stage leakage aware resource management technique for reconfigurable architectures", Edition of the Great Lakes Symposium on VLSI, Houston, Texas, USA, pp.63-68, 2014.

S. Wang, N.K. Pham, A.K. Singh, et al., "Leakage and performance aware resource management for 2D dynamically reconfigurable FPGA architectures", International Conference on Field Programmable Logic and Applications, Munich, Germany, pp.1-4, 2014.

P.N. Khanh, A. Kumar, A.K. Singh, et al., "Leakage aware resource management approach with machine learning optimization framework for partially reconfigurable architectures", Template, Vol.47, pp.231-243, 2016.

T. Zhou, T. Pan, Z. Bao, et al., "A time-based leakageaware algorithm for task placement and scheduling problem on dynamic reconfigurable FPGA", International Conference on Systems and Informatics, Nanjing, China, pp.501-506, 2018.

M. Ghorbani, "A variation and energy aware ILP formulation for task scheduling in MPSoC", International Symposium on Quality Electronic Design, Santa Clara, CA, USA, pp.772-777, 2012.

B. Khodabandeloo, A. Khonsari, A. Majidi, et al., "Task assignment and scheduling in MPSoC under process variation:A stochastic approach", Asia and South Pacific Design Automation Conference, Jeju, Korea (South), pp.690-695, 2018.

C. Yang, J. Chen, L. Thiele, et al., "Energy-efficient realtime task scheduling with temperature-dependent leakage", Design, Automation & Test in Europe Conference & Exhibition, Dresden, Germany, pp.9-14, 2010.

H. Huang and G. Quan, "Leakage aware energy minimization for real-time systems under the maximum temperature constraint", Design, Automation & Test in Europe Conference & Exhibition, Grenoble, France, pp.1-6, 2011.

S. Saha, Y. Lu and J. S. Deogun, "Thermal-constrained energy-aware partitioning for heterogeneous multi-core multiprocessor real-time systems", IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, Seoul, Korea (South), pp.41-50, 2012.

J. Zhou, T. Wei, M. Chen, et al., "Thermal-aware task scheduling for energy minimization in heterogeneous real-time MPSoC systems", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol.35, No.8, pp.1269-1282, 2016.

Z. Ekhtiyari, V. Moghaddas and H. Beitollahi, "A temperature-aware and energy-efficient fuzzy technique to schedule tasks in heterogeneous MPSoC systems", The Journal of Supercomputing, Vol.75, 22 pages, 2019.

G. Dinelli, G. Meoni, E. Rapuano, et al., "MEM-OPT:A scheduling and data re-use system to optimize on-chip memory usage for CNNs on-board FPGAs", IEEE Journal on Emerging and Selected Topics in Circuits and Systems, Vol.10, No.3, pp.335-347, 2020.

J. Zhu, L. Wang, H. Liu, et al., "An efficient task assignment framework to accelerate DPU-based convolutional neural network inference on FPGAs", IEEE Access, Vol.8, 14 pages, 2020.

E. Oh, W. Han, E. Yang, et al., "Energy-efficient task partitioning for CNN-based object detection in heterogeneous computing environment", International Conference on Information and Communication Technology Convergence, Jeju, Korea (South), pp.31-36, 2018.

M. Carreras, G. Deriu, L. Raffo, et al., "Optimizing temporal convolutional network inference on FPGA-based accelerators", IEEE Journal on Emerging and Selected Topics in Circuits and Systems, Vol.10, No.3, pp.348-361, 2020.

J. Wei, Z. Song, J. Zhan, et al., "Optimized co-scheduling of mixed-precision neural network accelerator for real-time multitasking applications", Journal of Systems Architecture, Vol.110, 12 pages, 2020.

Y. Ma, Y. Cao, S. Vrudhula, et al., "Automatic compilation of diverse CNNs onto high-performance FPGA accelerators", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol.39, No.2, pp.424-437, 2020.

G. Dai, Y. Shan, F. Chen, et al., "Online scheduling for FPGA computation in the Cloud", International Conference on Field-Programmable Technology, Shanghai, China, pp.330-333, 2014.

X. Liu, P. Liu and L. Hu, "Energy-aware task scheduling with time constraint for heterogeneous cloud datacenters", Concurrency and Computation:Practice and Experience, Vol.32, No.18, 17 pages, 2020.

X. Liu, P. Liu, H. Li, et al., "Energy-aware task scheduling strategies with QoS constraint for green computing in cloud data centers", Proc. of the 2018 Conference on Research in Adaptive and Convergent Systems, Honolulu, Hawaii, USA, pp.260-267, 2018.

C. Kachris, D. Diamantopoulos, G.C. Sirakoulis, et al., "An FPGA-based integrated mapReduce accelerator platform", Journal of Signal Processing Systems, Vol.87, pp.357-369, 2017.

D. Li, Y.Hou, Z.Huang, et al., "A framework of multicharacteristics fuzzy dynamic scheduling for parallel video processing on MPSoC architecture", IEEE International Conference on Fuzzy Systems, Taipei, China, pp.627-634, 2011.

R. Osorio and J. Bruguera, "High-speed FPGA architecture for CABAC decoding acceleration in H.264/AVC standard", Journal of Signal Processing Systems, Vol.72, pp.119-132, 2013.

Z. Zhu, J. Zhang and J. Zhao, "A hardware and software taskscheduling framework based on CPU+FPGA heterogeneous architecture in edge computing", IEEE Access, Vol.7, 14 pages, 2019.

Y. Liu, Y. Shen and Z. Sun, "Task scheduling algorithm of FPGA for on-board reconfigurable coprocessor", International Conference on Computer Science and Artificial Intelligence, Beijing, China, pp.207-214, 2019.

X. Meng and V. Chaudhary, "A high-performance heterogeneous computing platform for biological sequence analysis", IEEE Transactions on Parallel and Distributed Systems, Vol.21, No.9, pp.1267-1280, 2010.

Y. Li, Z. Jia, S. Xie, et al., "Dynamically reconfigurable hardware with a novel scheduling strategy in energyharvesting sensor networks", IEEE Sensors Journal, Vol.13, No.5, pp.2032-2038, 2013.

J. Wu, "Meaning and vision of mimic computing and mimic security defense", Telecommunications Science, Vol.30, No.7, pp.2-7, 2014.

Relative Articles

Supplements(0)

Cited By

Proportional views