Klaus Danne
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.
- B. Andersson and J. Jonsson. Fixed-priority preemptive multiprocessor scheduling: to partition or not to partition. In Seventh International Conference on Real-Time Computing Systems and Applications (RTCSA'00), pages 337--346, 2000.]] Google Scholar
Digital Library
- T. P. Baker. Multiprocessor EDF and deadline monotonic schedulability analysis. In RTSS, pages 120--129, 2003.]] Google ScholarDigital Library
- 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.]]Google Scholar
- K. Bazargan, R. Kastner, and M. Sarrafzadeh. Fast template placement for reconfigurable computing systems. IEEE Design and Test of Computers, pages 68--83, Mar. 2000.]] Google ScholarDigital Library
- M. Bertogna, M. Cirinei, and G. Lipari. Improved schedulability analysis of EDF on multiprocessor platforms. In proceedings of the 17th ERTCS, Palma de Mallorca, July 5--8 2005, Palma de Mallorca, Spain, July 2005. IEEE CS.]] Google ScholarDigital Library
- C. Bobda, M. Majer, T. Haller, A. Linarth, and J. Teich. The Erlangen Slot Machine: A Highly Flexible FPGA-Based Reconfiguration Platform. In Proceedings of the IEEE International Conference on Field Programmable Technology (FPT05), 2005.]] Google ScholarDigital Library
- G. Brebner and O. Diessel. Chip-based Reconfigurable Task Management. In Field-Programmable Logic and Applications (FPL'01), pages 182--191. Springer-Verlag, Berlin, Germany, 2001.]] Google ScholarDigital Library
- G. Chen, M. Kandemir, and U. Sezer. Configuration-sensitive process scheduling for FPGA-based computing platforms. In DATE '04: Proceedings of the conference on Design, automation and test in Europe, page 10486, Washington, DC, USA, 2004. IEEE Computer Society.]] Google ScholarDigital Library
- K. Compton and S. Hauck. Reconfigurable computing: a survey of systems and software. ACM Comput. Surv., 34(2):171--210, 2002.]] Google ScholarDigital Library
- 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.]]Google Scholar
- 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.]]Google ScholarCross Ref
- O. Diessel and H. ElGindy. Run-time Compaction of FPGA Designs. In Proceedings of the International Conference on Field Programmable Logic and Applications (FPL97), pages 121--140, 1997.]] Google ScholarDigital Library
- 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.]]Google ScholarCross Ref
- ELIXENT Ltd. DFA 1000 RISC Accelerator (data sheet). www.elixent.com/assets/EMH2090ElixDFA1000DS.pdf.]]Google Scholar
- ELIXENT Ltd. The Reconfigurable Algorithm Processor (white paper). www.elixent.com/assets/WP0001_D_Fabrix_Apps.pdf.]]Google Scholar
- J. Goossens, S. Funk, and S. Baruah. Priority-driven scheduling of periodic task systems on multiprocessors. Real-Time Syst., 25(2-3):187--205, 2003.]] Google ScholarDigital Library
- R. Hartenstein. A decade of reconfigurable computing: a visionary retrospective. In DATE '01: Proceedings of the conference on Design, automation and test in Europe, pages 642--649. IEEE Press, 2001.]] Google ScholarDigital Library
- J. S. N. Jean, K. Tomko, V. Yavagal, J. Shah, and R. Cook. Dynamic reconfiguration to support concurrent applications. IEEE Trans. on Computers, 48(6):591--602, June 1999.]] Google ScholarDigital Library
- 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.]]Google ScholarCross Ref
- C. L. Liu and J. W. Layland. Scheduling algorithms for multiprogramming in a hard-real-time environment. Journal of the ACM, 20(1):46--61, 1973.]] Google ScholarDigital Library
- C. Phillips, C. Stein, E. Torng, and J. Wein. Optimal time-critical scheduling via resource augmentation in 29 th ann. In In 29 th Ann. ACM Symp. on Theory of Computing, pages 140--149", El Paso, Texas, United States, 1997.]] Google ScholarDigital Library
- C. Plessl, R. Enzler, H. Walder, J. Beutel, M. Platzner, L. Thiele, and G. Tröster. The Case for Reconfigurable Hardware in Wearable Computing. Personal and Ubiquitous Computing, pages 299--308, October 2003. Springer-Verlag.]] Google ScholarDigital Library
- 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.]]Google ScholarCross Ref
- L. Sha, T. F. Abdelzaher, K.-E. Årzén, A. Cervin, T. P. Baker, A. Burns, G. C. Buttazzo, M. Caccamo, J. P. Lehoczky, and A. K. Mok. Real time scheduling theory: A historical perspective. Real-Time Systems, 28(2-3):101--155, 2004.]] Google ScholarDigital Library
- H. Simmler, L. Levinson, and R. Manner. Multitasking on FPGA coprocessors. In FPL, pages 121--130, 2000.]] Google ScholarDigital Library
- C. Steiger, H. Walder, and M. Platzner. Operating systems for reconfigurable embedded platforms: Online scheduling of real-time tasks. IEEE Transactions on Computers, 53(11):1392--1407, November 2004.]] Google ScholarDigital Library
- G. Stitt, B. Grattan, J. R. Villarreal, and F. Vahid. Using on-chip configurable logic to reduce embedded system software energy. In FCCM, pages 143--151, 2002.]] Google ScholarDigital Library
- J. Teich, S. Fekete, and J. Schepers. Optimization of dynamic hardware reconfigurations. The J. of Supercomputing, 19(1):57--75, May 2000.]] Google ScholarDigital Library
- 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.]]Google Scholar
- 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.]]Google ScholarCross Ref
Index Terms
- An EDF schedulability test for periodic tasks on reconfigurable hardware devices
Recommendations
Preference-oriented fixed-priority scheduling for periodic real-time tasks
A preference priority assignment (PPA) scheme that explicitly incorporates the ASAP and ALAP execution preferences of periodic real-time tasks is proposed.An online dual-queue based preference-oriented fixed- priority (POFP) scheduler is proposed 4, ...
Dynamic Real-time Scheduling of Firm Periodic Tasks with Hard and Soft Aperiodic Tasks
In this paper, we address the problem of the dynamic scheduling of skippable periodic task sets (i.e., period tasks allowing occasional skips of instances), together with aperiodic tasks. Scheduling of tasks is handled thanks to the merging of two ...
Schedulability analysis of preemptive and nonpreemptive EDF on partial runtime-reconfigurable FPGAs
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 ...
Comments