An EDF schedulability test for periodic tasks on reconfigurable hardware devices

ABSTRACT

In this paper, we consider the scheduling of periodic real-time tasks on reconfigurable hardware devices. Such devices can execute several tasks in parallel. All executing tasks share the hardware resource, which makes the scheduling problem differ from single- and multiprocessor scheduling. We adapt the global EDF multiprocessor scheduling approach to the reconfigurable hardware execution model and define two preemptive scheduling algorithms, EDF-First-k-Fit and EDF-Next-Fit. For these algorithms, we present a novel linear-time schedulability test and give a proof based on a resource augmentation technique. Then, we propose a task placement and relocation scheme utilizing partial device reconfiguration. This scheme allows us to extend the schedulability test to include reconfiguration time overheads. Experiments with synthetic workloads compare the scheduling test with the actual scheduling performance of EDF-First-k-Fit and EDF-Next-Fit. The main evaluation result is that the reconfiguration overhead is acceptable if the task computation times are one order of magnitude higher than the device reconfiguration time.

REFERENCES

• 1: B. Andersson , J. Jonsson, Fixed-priority preemptive multiprocessor scheduling: to partition or not to partition, Proceedings of the Seventh International Conference on Real-Time Systems and Applications (RTCSA'00), p.337, December 12-14, 2000
• 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: V. Baumgarte, F. May, A. Nückel, M. Vorbach, and M. Weinhardt. Pact xpp - a self-reconfigurable data processing architecture. In ERSA, Las Vegas, Nevada, June 2001.
• 4: Kiarash Bazargan , Ryan Kastner , Majid Sarrafzadeh, Fast Template Placement for Reconfigurable Computing Systems, IEEE Design & Test, v.17 n.1, p.68-83, January 2000 [doi>10.1109/54.825678]
• 5: Marko Bertogna , Michele Cirinei , Giuseppe Lipari, Improved Schedulability Analysis of EDF on Multiprocessor Platforms, Proceedings of the 17th Euromicro Conference on Real-Time Systems (ECRTS'05), p.209-218, July 06-08, 2005 [doi>10.1109/ECRTS.2005.18]
• 6: Christophe Bobda , Mateusz Majer , Ali Ahmadinia , Thomas Haller , Andre Linarth , Jurgen Teich , Jan van der Veen, The Erlangen Slot Machine: A Highly Flexible FPGA-Based Reconfigurable Platform, Proceedings of the 13th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM'05), p.319-320, April 18-20, 2005 [doi>10.1109/FCCM.2005.63]
• 7: Gordon J. Brebner , Oliver Diessel, Chip-Based Reconfigurable Task Management, Proceedings of the 11th International Conference on Field-Programmable Logic and Applications, p.182-191, August 27-29, 2001
• 8: G. Chen , M. Kandemir , U. Sezer, Configuration-Sensitive Process Scheduling for FPGA-Based Computing Platforms, Proceedings of the conference on Design, automation and test in Europe, p.10486, February 16-20, 2004
• 9: Katherine Compton , Scott Hauck, Reconfigurable computing: a survey of systems and software, ACM Computing Surveys (CSUR), v.34 n.2, p.171-210, June 2002 [doi>10.1145/508352.508353]
• 10: K. Danne. Memory management to support multitasking on FPGA based systems. In Proceedings of the International Conference on Reconfigurable Computing and FPGAs (ReConFig04) ISBN 970-692-169-9. Mexican Society of Computer Science, SMCC, 20 - 21 Sept. 2004.
• 11: K. Danne and M. Platzner. A heuristic approach to schedule periodic real-time tasks on reconfigurable hardware. In Proceedings of the International Conference on Field Programmable Logic and Applications (FPL05), Tampere, Finland, 24 - 26 Aug. 2005. Piscateway, NJ: IEEE.
• 12: Oliver Diessel , Hossam A. ElGindy, Run-time compaction of FPGA designs, Proceedings of the 7th International Workshop on Field-Programmable Logic and Applications, p.131-140, September 01-03, 1997
• 13: O. Diessel, H. ElGindy, M. Middendorf, H. Schmeck, and B. Schmidt. Dynamic scheduling of tasks on partially reconfigurable FPGAs. IEE Proceedings -- Computers and Digital Techniques, 147(3):181--188, May 2000.
• 14: ELIXENT Ltd. DFA 1000 RISC Accelerator (data sheet). www.elixent.com/assets/EMH2090ElixDFA1000DS.pdf.
• 15: ELIXENT Ltd. The Reconfigurable Algorithm Processor (white paper). www.elixent.com/assets/WP0001_D_Fabrix_Apps.pdf.
• 16: 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]
• 17: R. Hartenstein, A decade of reconfigurable computing: a visionary retrospective, Proceedings of the conference on Design, automation and test in Europe, p.642-649, March 2001, Munich, Germany
• 18: Jack S. N. Jean , Karen Tomko , Vikram Yavagal , Jignesh Shah , Robert Cook, Dynamic Reconfiguration to Support Concurrent Applications, IEEE Transactions on Computers, v.48 n.6, p.591-602, June 1999 [doi>10.1109/12.773796]
• 19: H. Kalte and M. Porrmann. Context saving and restoring for multitasking in reconfigurable systems. In 15th International Conference on Field Programmable Logic and Applications, pages 223--228, 24 - 28 Aug. 2005.
• 20: 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]
• 21: 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]
• 22: Christian Plessl , Rolf Enzler , Herbert Walder , Jan Beutel , Marco Platzner , Lothar Thiele , Gerhard Tröster, The case for reconfigurable hardware in wearable computing, Personal and Ubiquitous Computing, v.7 n.5, p.299-308, October 2003 [doi>10.1007/s00779-003-0243-x]
• 23: P. Sedcole, B. Blodget, T. Becker, J. Anderson, and P. Lysaght. Modular Partial Reconfiguration in Virtex FPGAs. In Proceedings of the International Conference on Field Programmable Logic and Applications (FPL05), 2005.
• 24: Lui Sha , Tarek Abdelzaher , Karl-Erik Årzén , Anton Cervin , Theodore Baker , Alan Burns , Giorgio Buttazzo , Marco Caccamo , John Lehoczky , Aloysius K. Mok, Real Time Scheduling Theory: A Historical Perspective, Real-Time Systems, v.28 n.2-3, p.101-155, November-December 2004 [doi>10.1023/B:TIME.0000045315.61234.1e]
• 25: H. Simmler , L. Levinson , Reinhard Männer, Multitasking on FPGA Coprocessors, Proceedings of the The Roadmap to Reconfigurable Computing, 10th International Workshop on Field-Programmable Logic and Applications, p.121-130, August 27-30, 2000
• 26: 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]
• 27: Greg Stitt , Brian Grattan , Jason Villarreal , Frank Vahid, Using On-Chip Configurable Logic to Reduce Embedded System Software Energy, Proceedings of the 10th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.143, September 22-24, 2002
• 28: Jürgen Teich , Sándor P. Fekete , Jörg Schepers, Optimization of Dynamic Hardware Reconfigurations, The Journal of Supercomputing, v.19 n.1, p.57-75, May 2001 [doi>10.1023/A:1011188411132]
• 29: M. Ullmann, M. Huebner, B. Grimm, and J. Becker. An FPGA Runtime System for Dynamical On-Demand Reconfiguration. In Proceedings of the Reconfigurable Architectures Workshop (RAW04), 2005.
• 30: H. Walder and M. Platzner. A Runtime Environment for Reconfigurable Operating Systems. In Proceedings of the International Conference on Field Programmable Logic and Applications (FPL04), pages 831--835, 2004.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

Additional Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design
          Subjects: Real-time systems and embedded systems

General Terms:
Algorithms, Performance, Theory

Keywords:
FPGA, periodic tasks, real-time, reconfigurable hardware, scheduling