skip to main content
research-article

Schedulability analysis of preemptive and nonpreemptive EDF on partial runtime-reconfigurable FPGAs

Published: 03 October 2008 Publication History

Abstract

Field Programmable Gate Arrays (FPGAs) are very popular in today's embedded systems design, and Partial Runtime-Reconfigurable (PRTR) FPGAs allow HW tasks to be placed and removed dynamically at runtime. Hardware task scheduling on PRTR FPGAs brings many challenging issues to traditional real-time scheduling theory, which have not been adequately addressed by the research community compared to software task scheduling on CPUs. In this article, we consider the schedulability analysis problem of HW task scheduling on PRPR FPGAs. We derive utilization bounds for several variants of global preemptive/nonpreemptive EDF scheduling, and compare the performance of different utilization bound tests.

References

[1]
Agron, J., Peck, W., Anderson, E., Andrews, D. L., Komp, E., Sass, R., Baijot, F., and Stevens, J. 2006. Run-time services for hybrid cpu/fpga systems on chip. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS). 3--12.
[2]
Baker, T. P. 2003. Multiprocessor edf and deadline monotonic schedulability analysis. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS). 120--129.
[3]
Baker, T. P. 2005a. An Analysis of EDF Schedulability on a Multiprocessor. IEEE Trans. Para. Distr. Syst. 16, 8, 760--768.
[4]
Baker, T. P. 2005b. Comparison of empirical success rates of global vs. partitioned fixed-priority and EDF scheduling for hard real time. Tech. rep. TR-050601, Florida State University.
[5]
Baker, T. P. 2005c. Further improved schedulability analysis of edf on multiprocessor platforms. Tech. Rep. TR-051001, Florida State University.
[6]
Baker, T. P. 2006a. An analysis of fixed-priority schedulability on a multiprocessor. Real-Time Syst. 32, 1-2, 49--71.
[7]
Baker, T. P. 2006b. A comparison of global and partitioned EDF schedulability tests for multiprocessors. In Proceedings of the International Conference on Real-Time and Network Systems (RTSN). 119--130.
[8]
Banerjee, S., Bozorgzadeh, E., Dutt, N., and Noguera, J. 2007. Selective band width and resource management in scheduling for dynamically reconfigurable architectures. In Proceedings of the IEEE/ACM Design Automation Conference (DAC). 771--776.
[9]
Baruah, S. 2007. Techniques for multiprocessor global schedulability analysis. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS).
[10]
Baruah, S., Mok, A., and Rosier, L. 1990. Preemptively scheduling hard-real-time sporadic tasks on one processor. In Proceedings of the 11th Real-Time Systems Symposium (RTSS). 182--190.
[11]
Baruah, S. K. 2006. The non-preemptive scheduling of periodic tasks upon multiprocessors. Real-Time Syst. 32, 1-2, 9--20.
[12]
Bertogna, M., Cirinei, M., and Lipari, G. 2005. Improved schedulability analysis of EDF on multiprocessor platforms. In Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS). 209--218.
[13]
Buttazzo, G. C. 2005. Rate monotonic vs. EDF: Judgment day. Real-Time Syst. 29, 1, 5--26.
[14]
Carpenter, J., Funk, S., Holman, P., Srinivasan, A., Anderson, J., and Baruah, S. 2004. A Categorization of Real-Time Multiprocessor Scheduling Problems and Algorithms. Chapman and Hall, 30-1--30-19.
[15]
Cirinei, M. and Baker, T. P. 2007. Edzl scheduling analysis. In Proceedings of the European Conference on Real-Time Systems (ECRTS). IEEE, 9--18.
[16]
Claus, C., Muller, F. H., Zeppenfeld, J., and Stechele, W. 2007. A new framework to accelerate Virtex-II Pro dynamic partial self-reconfiguration. In Proceedings of the International Parallel and Distributed Processing Symposium (IPDPS), Reconfigurable Architecture Workshop (RAW).
[17]
Danne, K., Muhlenbernd, R., and Platzner, M. 2006. Executing hardware tasks on dynamically reconfigurable devices under real-time conditions. In Proceedings of the International Conference on Field Programmable Logic and Applications (FPL).
[18]
Danne, K. and Platzner, M. 2006a. An EDF schedulability test for periodic tasks on reconfigurable hardware devices. In Proceedings of the ACM Conference on Languages, Compilers, and Tools for Embedded Systems (LCTES). 93--102.
[19]
Danne, K. and Platzner, M. 2006b. Partitioned scheduling of periodic real-time tasks onto reconfigurable hardware. In Proceedings of International Parallel and Distributed Processing Symposium (IPDPS), Reconfigurable Architecture Workshop (RAW).
[20]
Dyer, M., Plessl, C., and Platzner, M. 2002. Partially reconfigurable cores for xilinx virtex. In Proceedings of the International Conference on Field-Programmable Logic and Applications (FPL). Springer-Verlag, 292--301.
[21]
Goossens, J., Funk, S., and Baruah, S. K. 2003. Priority-driven scheduling of periodic task systems on multiprocessors. Real-Time Syst. 25, 2-3, 187--205.
[22]
Gu, Z., Yuan, M., and He, X. 2007. Optimal static task scheduling on reconfigurable hardware devices using model-checking. In Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS).
[23]
Guan, N., Gu, Z., Deng, Q., Liu, W., and Yu, G. 2007. Improved schedulability analysis of edf scheduling on reconfigurable hardware devices. In Proceedings of the Workshop on Parallel and Distributed Real-Time Systems (WDPRTS).
[24]
Guccione, S., Levi, D., and Sundararajan, P. 2000. Jbits: A java-based interface for reconfigurable computing. In Proceedings of the Annual Military and Aerospace Applications of Programmable Devices and Technologies Conference (MAPLD).
[25]
Hortaa, E., Lockwood, J., and Kofuji, S. 2002. Using parbit to implement partial run-time reconfigurable systems. In Proceedings of the the International Conference on Field Programmable Logic and Applications (FPL).
[26]
Jovanovic, S., Tanougast, C., and Weber, S. 2007. A hardware preemptive multitasking mechanism based on scan-path register structure for fpga-based reconfigurable systems. In Proceedings of the NASA/ESA Conference on Adaptive Hardware and Systems (AHS). 358--364.
[27]
Kalte, H. and Porrmann, M. 2005. Context saving and restoring for multitasking in reconfigurable systems. In Proceedings of the International Conference on Field Programmable Logic and Applications (FPL). 223--228.
[28]
Kalte, H. and Porrmann, M. 2006. Replica2pro: task relocation by bitstream manipulation in virtex-ii/pro fpgas. In Proceedings of the ACM International Conference on Computing Frontiers. 403--412.
[29]
Knuth, D. 1973. The Art of Computer Programming; Volume 3/Sorting and Searching. Addison Wesley.
[30]
Koch, D., Haubelt, C., and Teich, J. 2007. Efficient hardware checkpointing: concepts, overhead analysis, and implementation. In Proceedings of the ACM/SIGDA International Symposium on Field-Programmable Gate Arrays (FPGA). 188--196.
[31]
Lehoczky, J. P., Sha, L., and Ding, Y. 1989. The rate monotonic scheduling algorithm: Exact characterization and average case behavior. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS).
[32]
Li, Z. and Hauck, S. 2002. Configuration prefetching techniques for partial reconfigurable coprocessor with relocation and defragmentation. In Proceedings of the ACM/SIGDA International Symposium on Field-Programmable Gate Arrays (FPGA). 187--195.
[33]
Liu, C. L. and Layland, J. W. 1973. Scheduling algorithms for multiprogramming in a hard-real-time environment. J. ACM 20, 1, 46--61.
[34]
Lu, C., Stankovic, J. A., Son, S. H., and Tao, G. 2002. Feedback control real-time scheduling: Framework, modeling, and algorithms. Real-Time Syst. 23, 1-2, 85--126.
[35]
Lubbers, E. and Platzner, M. 2007. In Proceedings of the International Conference on Field Programmable Logic and Applications (FPL).
[36]
Phillips, C. A., Stein, C., Torng, E., and Wein, J. 1997. Optimal time-critical scheduling via resource augmentation (extended abstract). In Proceedings of the Annual Symposium on Theory of Computing (STOC). 140--149.
[37]
Raghavan, A. K. and Sutton, P. 2002. Jpgc a partial bitstream generation tool to support partial reconfiguration in virtex fpgas. In Proceedings of the International Parallel and Distributed Processing Symposium (IPDPS), Reconfigurable Architecture Workshop (RAW).
[38]
Silva, M. L. and Ferreira, J. C. 2006. Support for partial run-time reconfiguration of platform fpgas. J. Syst. Architec. 52, 12, 709--726.
[39]
Steiger, C., Walder, H., and Platzner, M. 2004. Operating systems for reconfigurable embedded platforms: Online scheduling of real-time tasks. IEEE Trans. Comput. 53, 11, 1393--1407.
[40]
Steiger, C., Walder, H., Platzner, M., and Thiele, L. 2003. Online scheduling and placement of real-time tasks to partially reconfigurable devices. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS). 224--235.
[41]
Xilinx. 2007. Virtex-4 configuration guide. http://www.xilinx.com.

Cited By

View all
  • (2023)On Guaranteeing Schedulability of Periodic Real-Time Hardware Tasks Under ReconOS$$^{64}$$Applied Reconfigurable Computing. Architectures, Tools, and Applications10.1007/978-3-031-42921-7_17(245-259)Online publication date: 16-Sep-2023
  • (2021)Maintaining Communication Consistency During Task Migrations in Heterogeneous Reconfigurable DevicesMulti‐Processor System‐on‐Chip 110.1002/9781119818298.ch11(255-285)Online publication date: 26-Mar-2021
  • (2018)Global Fixed Priority Scheduling with Constructing Execution Dependency in Multiprocessor Real-Time SystemsJournal of Circuits, Systems and Computers10.1142/S021812661850165727:10(1850165)Online publication date: Sep-2018
  • Show More Cited By

Index Terms

  1. Schedulability analysis of preemptive and nonpreemptive EDF on partial runtime-reconfigurable FPGAs

        Recommendations

        Comments

        Information & Contributors

        Information

        Published In

        cover image ACM Transactions on Design Automation of Electronic Systems
        ACM Transactions on Design Automation of Electronic Systems  Volume 13, Issue 4
        September 2008
        328 pages
        ISSN:1084-4309
        EISSN:1557-7309
        DOI:10.1145/1391962
        Issue’s Table of Contents
        Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

        Publisher

        Association for Computing Machinery

        New York, NY, United States

        Journal Family

        Publication History

        Published: 03 October 2008
        Accepted: 01 March 2008
        Revised: 01 October 2007
        Received: 01 March 2007
        Published in TODAES Volume 13, Issue 4

        Permissions

        Request permissions for this article.

        Check for updates

        Author Tags

        1. FPGA
        2. Real-time scheduling
        3. reconfigurable devices

        Qualifiers

        • Research-article
        • Research
        • Refereed

        Funding Sources

        Contributors

        Other Metrics

        Bibliometrics & Citations

        Bibliometrics

        Article Metrics

        • Downloads (Last 12 months)6
        • Downloads (Last 6 weeks)0
        Reflects downloads up to 15 Feb 2025

        Other Metrics

        Citations

        Cited By

        View all
        • (2023)On Guaranteeing Schedulability of Periodic Real-Time Hardware Tasks Under ReconOS$$^{64}$$Applied Reconfigurable Computing. Architectures, Tools, and Applications10.1007/978-3-031-42921-7_17(245-259)Online publication date: 16-Sep-2023
        • (2021)Maintaining Communication Consistency During Task Migrations in Heterogeneous Reconfigurable DevicesMulti‐Processor System‐on‐Chip 110.1002/9781119818298.ch11(255-285)Online publication date: 26-Mar-2021
        • (2018)Global Fixed Priority Scheduling with Constructing Execution Dependency in Multiprocessor Real-Time SystemsJournal of Circuits, Systems and Computers10.1142/S021812661850165727:10(1850165)Online publication date: Sep-2018
        • (2017)Adaptive optimization for OpenCL programs on embedded heterogeneous systemsACM SIGPLAN Notices10.1145/3140582.308104052:5(11-20)Online publication date: 21-Jun-2017
        • (2017)Adaptive optimization for OpenCL programs on embedded heterogeneous systemsProceedings of the 18th ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems10.1145/3078633.3081040(11-20)Online publication date: 21-Jun-2017
        • (2017)Spatio-Temporal Scheduling of Preemptive Real-Time Tasks on Partially Reconfigurable SystemsACM Transactions on Design Automation of Electronic Systems10.1145/305656122:4(1-26)Online publication date: 13-Jun-2017
        • (2017)Scrubbing Mechanism for Heterogeneous Applications in Reconfigurable DevicesACM Transactions on Design Automation of Electronic Systems10.1145/299764622:2(1-26)Online publication date: 9-Feb-2017
        • (2017)Reliability and Makespan Optimization of Hardware Task Graphs in Partially Reconfigurable PlatformsIEEE Transactions on Aerospace and Electronic Systems10.1109/TAES.2017.266733853:2(983-994)Online publication date: Apr-2017
        • (2016)Generating Efficient Context-Switch Capable Circuits through Autonomous Design FlowACM Transactions on Reconfigurable Technology and Systems10.1145/299619910:1(1-23)Online publication date: 9-Dec-2016
        • (2016)Minimizing Stack Memory for Hard Real-Time Applications on Multicore Platforms with Partitioned Fixed-Priority or EDF SchedulingACM Transactions on Design Automation of Electronic Systems10.1145/284609621:3(1-25)Online publication date: 11-May-2016
        • Show More Cited By

        View Options

        Login options

        Full Access

        View options

        PDF

        View or Download as a PDF file.

        PDF

        eReader

        View online with eReader.

        eReader

        Figures

        Tables

        Media

        Share

        Share

        Share this Publication link

        Share on social media