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

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: Jason Agron , Wesley Peck , Erik Anderson , David Andrews , Ed Komp , Ron Sass , Fabrice Baijot , Jim Stevens, Run-Time Services for Hybrid CPU/FPGA Systems on Chip, Proceedings of the 27th IEEE International Real-Time Systems Symposium, p.3-12, December 05-08, 2006 [doi>10.1109/RTSS.2006.45]
• 2: Theodore P. Baker, Multiprocessor EDF and Deadline Monotonic Schedulability Analysis, Proceedings of the 24th IEEE International Real-Time Systems Symposium, p.120, December 03-05, 2003
• 3: Theodore P. Baker, An Analysis of EDF Schedulability on a Multiprocessor, IEEE Transactions on Parallel and Distributed Systems, v.16 n.8, p.760-768, August 2005 [doi>10.1109/TPDS.2005.88]
• 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: Theodore P. Baker, An Analysis of Fixed-Priority Schedulability on a Multiprocessor, Real-Time Systems, v.32 n.1-2, p.49-71, February 2006 [doi>10.1007/S11241-005-4686-1]
• 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: Sudarshan Banerjee , Elaheh Bozorgzadeh , Nikil Dutt , Juanjo Noguera, Selective bandwidth and resource management in scheduling for dynamically reconfigurable architectures, Proceedings of the 44th annual conference on Design automation, June 04-08, 2007, San Diego, California [doi>10.1145/1278480.1278673]
• 9: Sanjoy Baruah, Techniques for Multiprocessor Global Schedulability Analysis, Proceedings of the 28th IEEE International Real-Time Systems Symposium, p.119-128, December 03-06, 2007 [doi>10.1109/RTSS.2007.48]
• 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: Sanjoy K. Baruah, The Non-preemptive Scheduling of Periodic Tasks upon Multiprocessors, Real-Time Systems, v.32 n.1-2, p.9-20, February 2006 [doi>10.1007/s11241-006-4961-9]
• 12: Marko Bertogna , Michele Cirinei , Giuseppe Lipari, Improved Schedulability Analysis of EDF on Multiprocessor Platforms, Proceedings of the 17th Euromicro Conference on Real-Time Systems, p.209-218, July 06-08, 2005 [doi>10.1109/ECRTS.2005.18]
• 13: Giorgio C. Buttazzo, Rate monotonic vs. EDF: judgment day, Real-Time Systems, v.29 n.1, p.5-26, January 2005 [doi>10.1023/B:TIME.0000048932.30002.d9]
• 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: Michele Cirinei , Theodore P. Baker, EDZL Scheduling Analysis, Proceedings of the 19th Euromicro Conference on Real-Time Systems, p.9-18, July 04-06, 2007 [doi>10.1109/ECRTS.2007.14]
• 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: Klaus Danne , Marco Platzner, An EDF schedulability test for periodic tasks on reconfigurable hardware devices, Proceedings of the 2006 ACM SIGPLAN/SIGBED conference on Language, compilers, and tool support for embedded systems, June 14-16, 2006, Ottawa, Ontario, Canada
• 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: Matthias Dyer , Christian Plessl , Marco Platzner, Partially Reconfigurable Cores for Xilinx Virtex, Proceedings of the Reconfigurable Computing Is Going Mainstream, 12th International Conference on Field-Programmable Logic and Applications, p.292-301, September 02-04, 2002
• 21: Joël Goossens , Shelby Funk , Sanjoy Baruah, Priority-Driven Scheduling of Periodic Task Systems on Multiprocessors, Real-Time Systems, v.25 n.2-3, p.187-205, September-October 2003 [doi>10.1023/A:1025120124771]
• 22: Zonghua Gu , Mingxuan Yuan , Xiuqiang He, Optimal Static Task Scheduling on Reconfigurable Hardware Devices Using Model-Checking, Proceedings of the 13th IEEE Real Time and Embedded Technology and Applications Symposium, p.32-44, April 03-06, 2007 [doi>10.1109/RTAS.2007.22]
• 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: Edson L. Horta , John W. Lockwood , Sérgio T. Kofuji, Using PARBIT to Implement Partial Run-Time Reconfigurable Systems, Proceedings of the Reconfigurable Computing Is Going Mainstream, 12th International Conference on Field-Programmable Logic and Applications, p.182-191, September 02-04, 2002
• 26: S. Jovanovic , C. Tanougast , S. Weber, A Hardware Preemptive Multitasking Mechanism Based on Scan-path Register Structure for FPGA-based Reconfigurable Systems, Proceedings of the Second NASA/ESA Conference on Adaptive Hardware and Systems, p.358-364, August 05-08, 2007 [doi>10.1109/AHS.2007.4]
• 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: Heiko Kalte , Mario Porrmann, REPLICA2Pro: task relocation by bitstream manipulation in virtex-II/Pro FPGAs, Proceedings of the 3rd conference on Computing frontiers, May 03-05, 2006, Ischia, Italy [doi>10.1145/1128022.1128045]
• 29: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 30: Dirk Koch , Christian Haubelt , Jürgen Teich, Efficient hardware checkpointing: concepts, overhead analysis, and implementation, Proceedings of the 2007 ACM/SIGDA 15th international symposium on Field programmable gate arrays, February 18-20, 2007, Monterey, California, USA [doi>10.1145/1216919.1216950]
• 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: Zhiyuan Li , Scott Hauck, Configuration prefetching techniques for partial reconfigurable coprocessor with relocation and defragmentation, Proceedings of the 2002 ACM/SIGDA tenth international symposium on Field-programmable gate arrays, February 24-26, 2002, Monterey, California, USA [doi>10.1145/503048.503076]
• 33: C. L. Liu , James W. Layland, Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment, Journal of the ACM (JACM), v.20 n.1, p.46-61, Jan. 1973 [doi>10.1145/321738.321743]
• 34: Chenyang Lu , John A. Stankovic , Sang H. Son , Gang Tao, Feedback Control Real-Time Scheduling: Framework, Modeling, and Algorithms*, Real-Time Systems, v.23 n.1-2, p.85-126, July-September 2002 [doi>10.1023/A:1015398403337]
• 35: Lubbers, E. and Platzner, M. 2007. In Proceedings of the International Conference on Field Programmable Logic and Applications (FPL).
• 36: Cynthia A. Phillips , Cliff Stein , Eric Torng , Joel Wein, Optimal time-critical scheduling via resource augmentation (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.140-149, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258570]
• 37: Anup Kumar Raghavan , Peter Sutton, JPG - A Partial Bitstream Generation Tool to Support Partial Reconfiguration in Virtex FPGAs, Proceedings of the 16th International Parallel and Distributed Processing Symposium, p.192, April 15-19, 2002
• 38: Miguel L. Silva , João Canas Ferreira, Support for partial run-time reconfiguration of platform FPGAs, Journal of Systems Architecture: the EUROMICRO Journal, v.52 n.12, p.709-726, December, 2006 [doi>10.1016/j.sysarc.2006.04.004]
• 39: Christoph Steiger , Herbert Walder , Marco Platzner, Operating Systems for Reconfigurable Embedded Platforms: Online Scheduling of Real-Time Tasks, IEEE Transactions on Computers, v.53 n.11, p.1393-1407, November 2004 [doi>10.1109/TC.2004.99]
• 40: Christoph Steiger , Herbert Walder , Marco Platzner , Lothar Thiele, Online Scheduling and Placement of Real-time Tasks to Partially Reconfigurable Devices, Proceedings of the 24th IEEE International Real-Time Systems Symposium, p.224, December 03-05, 2003
• 41: Xilinx. 2007. Virtex-4 configuration guide. http://www.xilinx.com.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS

Additional Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING

General Terms:
Algorithms, Design, Performance

Keywords:
FPGA, Real-time scheduling, reconfigurable devices