Hard real-time reconfiguration port scheduling

ABSTRACT

When modern partially and dynamically reconfigurable FPGAs are to be used as resources in hard real-time systems, the two dimensions area and time have to be considered in the focus of availability and deadlines. In particular, area requirements must be guaranteed for the tasks' duration. While execution environments that abstract the space demand of tasks exist and methods for occupancy of resources over time are discussed in the literature, few works focus on another fundamental bottleneck, the reconfiguration port. As all resource requests are served by this mutually exclusive device, profound concepts for scheduling the port access are vital requirements for FPGA realtime scheduling. Nevertheless, as the port must be accessed sequentially, we can inherit and apply monoprocessor scheduling concepts that are well researched. In this paper, we introduce monoprocessor scheduling algorithms for the reconfiguration port of FPGAs.

REFERENCES

• 1: Ali Ahmadinia , Christophe Bobda , Dirk Koch , Mateusz Majer , Jürgen Teich, Task scheduling for heterogeneous reconfigurable computers, Proceedings of the 17th symposium on Integrated circuits and system design, September 07-11, 2004, Pernambuco, Brazil [doi>10.1145/1016568.1016582]
• 2: A. Ahmadinia, C. Bobda, and J. Teich. A Dynamic Scheduling and Placement Algorithm for Reconfigurable Hardware. In ARCS, pp. 125--139, Augsburg, Germany, 2004.
• 3: A. N. Audsley, A. Burns, M. Richardson, K. Tindell, and A. J. Wellings. Applying new scheduling theory to static priority pre-emptive scheduling. Software Engineering Journal, 8:284--292, 1993.
• 4: N. C. Audsley, A. Burns, M. F. Richardson, and A. J. Wellings. Hard Real-Time Scheduling: The Deadline Monotonic Approach. In Proc. 8th IEEE Workshop on Real-Time Operating Systems and Software, Atlanta, 1991.
• 5: Sudarshan Banerjee , Elaheh Bozorgzadeh , Nikil Dutt, Physically-aware HW-SW partitioning for reconfigurable architectures with partial dynamic reconfiguration, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, Anaheim, California, USA [doi>10.1145/1065579.1065667]
• 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: P. Brucker, C. Dhaenens-Flipo, S. Knust, S. A. Kravchenko, and F. Werner. Complexity results for parallel machine problems with a single server. J. of Scheduling, 5:429--457, 2002.
• 8: Giorgio C. Buttazzo, Hard Real-time Computing Systems: Predictable Scheduling Algorithms And Applications (Real-Time Systems Series), Springer-Verlag Telos, 2004
• 9: 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]
• 10: K. Danne and M. Platzner. Executing hardware tasks on dynamically reconfigurable devices under real-time conditions. In Proceedings of the FPL06, Madrid, Spain, 2006.
• 11: F. Dittmann and M. Götz. Applying Single Processor Algorithms to Schedule Tasks on Reconfigurable Devices Respecting Reconfiguration Times. In 13th RAW, Rhodes Island, Greece, 2006. IEEE.
• 12: S. Fekete , E. Köhler , J. Teich, Optimal FPGA module placement with temporal precedence constraints, Proceedings of the conference on Design, automation and test in Europe, p.658-667, March 2001, Munich, Germany
• 13: J. Leung and J. W. Whitehead. On the complexity of fixed priority scheduling of periodic real-time tasks. Performance Evaluation, pp. 237--250, 2(4), 1982.
• 14: P. Lysaght, B. Blodget, J. Mason, J. Young, and B. Bridge-ford. Enhanced architectures, design methodologies and CAD tools for dynamic reconfiguration on XILINX FPGAS. In Proceedings of the FPL 2006, Madrid, Spain, 2006.
• 15: Javier Resano , Daniel Mozos , Diederik Verkest , Francky Catthoor, A Reconfiguration Manager for Dynamically Reconfigurable Hardware, IEEE Design & Test, v.22 n.5, p.452-460, September 2005 [doi>10.1109/MDT.2005.100]
• 16: L. Sha , R. Rajkumar , J. P. Lehoczky, Priority Inheritance Protocols: An Approach to Real-Time Synchronization, IEEE Transactions on Computers, v.39 n.9, p.1175-1185, September 1990 [doi>10.1109/12.57058]
• 17: B. Sprunt, L. Sha, and J. Lehoczky. Aperiodic task scheduling for hard-real-time systems. Journal of Real-Time Systems, 1(1):27--60, June 1989.
• 18: M. Ullmann, M. Hübner, B. Grimm, and J. Becker. On-Demand FPGA Run-Time System for Dynamical Reconfiguration with Adaptive Priorities. In Proceedings of the FPL, pp. 454--463, Antwerp, Belgium, 2004. Springer.
• 19: H. Walder and M. Platzner. Non-preemptive Multitasking on FPGAs: Task Placement and Footprint Transform. In International Conference on Engineering of Reconfigurable Systems and Algorithms (ERSA), pp. 24--30, June 2002.
• 20: Herbert Walder , Marco Platzner, Online Scheduling for Block-Partitioned Reconfigurable Devices, Proceedings of the conference on Design, Automation and Test in Europe, p.10290, March 03-07, 2003
• 21: H. Walder and M. Platzner. A Runtime Environment for Reconfigurable Hardware Operating Systems. In Proceedings of the 14th International Conference on Field Programmable Logic and Application (FPL'04), pp. 831--835. Springer, August 2004.