| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Real-Time Management of Hardware and Software Tasks for FPGA-based Embedded Systems
December 2007 (vol. 56 no. 12)
pp. 1666-1680
Operating systems for reconfigurable devices enable the development of embedded systems where software tasks, running on a CPU, can coexist with hardware tasks running on a reconfigurable hardware device (FPGA). In this work, we consider real-time systems subject to dynamic workloads and whose tasks can be computationally intensive. We introduce a novel resource allocation scheme and an online admission control test that achieve high performance and flexibility; in addition, runtime reconfiguration is used to maximize the number of admitted real-time tasks. More in details, we first discuss a 1D system architecture and its prototype for a Xilinx Virtex-4 FPGA; then, we concentrate on the on-line admission control problem. Online task allocation and migration between the CPU and the reconfigurable device are discussed and sufficient feasibility tests are derived for both the commonly used slotted and 1D area models. Finally, the effectiveness of our admission control and relocation strategy is shown through a series of synthetic simulations.
[1] 1666 V. Nollet, P. Coene, D. Verkest, S. Vernalde, and R. Lauwereins, “Designing an Operating System for a Heterogeneous Reconfigurable SoC,” Proc. 10th Reconfigurable Architectures Workshop (RAW '03), Apr. 2003.[2] H. Walder and M. Platzner, “Reconfigurable Hardware Operating Systems: From Concepts to Realizations,” Proc. Int'l Conf. Eng. of Reconfigurable Systems and Algorithms (ERSA '03), 2003.[3] G. Wigley and D. Kearney, “The Development of an Operating System for Reconfigurable Computing,” Proc. IEEE Symp. FPGAs for Custom Computing Machines (FCCM '01), 2001.[4] J. Becker, M. Hübner, G. Hettich, R. Constapel, J. Eisenmann, and J. Luka, “Dynamic and Partial FPGA Exploitation,” Proc. IEEE, special issue: advanced automobile technologies, vol. 95, no. 2, pp.438-452, Feb. 2007.[5] Virtex-4, Virtex-II Pro and Virtex-II Pro X FPGA User Guide. Xilinx, Inc., http:/www.xilinx.com/, 2007.[6] J.-Y. Mignolet, S. Vernalde, D. Verkest, and R. Lauwereins, “Enabling Hardware-Software Multitasking on a Reconfigurable Computing Platform for Networked Portable Multimedia Appliances,” Proc. Int'l Conf. Eng. Reconfigurable Systems and Algorithms (ERSA '02), pp. 116-122, June 2002.[7] C. Plessel, 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, Oct. 2003.[8] A. Ortiz and N. Neogi, “Color Optic Flow: A Computer Vision Approach for Object Detection on UAVS,” Proc. 25th IEEE Digital Avionics Systems Conf. (DASC '06), Oct. 2006.[9] G. Simon, M. Maróti, Á. Lédeczi, G. Balogh, B. Kusy, A. Nádas, G. Pap, J. Sallai, and K. Frampton, “Sensor Network-Based Countersniper System,” Proc. ACM Second Int'l Conf. Embedded Networked Sensor Systems (SenSys '04), 2004.[10] Piccolo Users Guide. Cloud Cap Technology, http://www.cloud captech.compiccolo_plus.htm , 2007.[11] J. Diaz, E. Ros, F. Pelayo, E. Ortigosa, and S. Mota, “FPGA-Based Real-Time Optical-Flow System,” IEEE Trans. Circuits and Systems for Video Technology, vol. 16, no. 2, pp. 274-279, Feb. 2006.[12] Virtex-4 Configuration Guide. Xilinx, Inc., http:/www.xilinx.com/, 2007.[13] K. Compton and S. Hauck, “Reconfigurable Computing: A Survey of Systems and Software,” ACM Computing Surveys, vol. 34, no. 2, pp. 171-210, 2002.[14] P. Sedcole, “Reconfigurable Platform-Based Design in FPGAs for Video Image Processing,” PhD dissertation, Imperial College London, Jan. 2006.[15] OS Control of a Heterogeneous Reconfigurable MP-SoC Cluster. Interuniversity MicroElectronics Center, http://www.imec.be/reconfigurable/pdfGecko2_eUSA04.pdf , 2007.[16] K. Danne and M. Platzner, “Memory-Demanding Periodic Real-Time Applications on FPGA Computers,” Work-in-Progress Proc. 17th EuroMicro Conf. Real-Time Systems (ECRTS '05), July 2005.[17] P. Sedcole, B. Blodget, T. Becker, J. Anderson, and P. Lysaght, “Modular Dynamic Reconfiguration in Virtex FPGAs,” IEE Proc. Computers and Digital Techniques, vol. 153, no. 3, pp. 157-164, May 2006.[18] M. Huebner, T. Becker, and J. Becker, “Real-Time Lut-Based Network Topologies for Dynamic and Partial FPGA Self-Reconfiguration,” Proc. 17th Ann. Symp. Integrated Circuits and Systems Design (SBCCI '04), 2004.[19] B. Blodget, S. McMillan, and P. Lysaght, “A Lightweight Approach for Embedded Reconfiguration of FPGAs,” Proc. Design, Automation and Test in Europe Conf. and Exhibition (DATE '03), Apr. 2003.[20] L. Sha, R. Rajkumar, and J.P. Lehoczky, “Priority Inheritance Protocols: An Approach to Real-Time Synchronization,” IEEE Trans. Computers, vol. 39, no. 9, Sept. 1990.[21] T.P. Baker, “A Stack-Based Allocation Policy for Realtime Processes,” Proc. 11th IEEE Real-Time Systems Symp. (RTSS '90), Dec. 1990.[22] H. Simmler, L. Levinson, and R. Männer, “Multitasking on FPGA Coprocessors,” Proc. 10th Int'l Conf. Field-Programmable Logic and Applications (FPL '00), Aug. 2000.[23] K. Danne, “Memory Management to Support Multitasking on FPGA Based Systems,” Proc. Int'l Conf. Reconfigurable Computing and FPGAs, Sept. 2004.[24] J.-Y. Mignolet, V. Nollet, P. Coene, D. Verkest, S. Vernalde, and R. Lauwereins, “Infrastructure for Design and Management of Relocatable Tasks in a Heterogeneous Reconfigurable System-on-Chip,” Proc. Design, Automation and Test in Europe Conf. and Exposition (DATE '03), Mar. 2003.[25] MicroBlaze Processor Reference Guide. Xilinx, Inc., http:/www. xilinx.com/, 2007.[26] CoreConnect Bus Architecture. IBM Microelectronics, http://www-306.ibm.com/chipstechlib, 2001.[27] R. Pellizzoni and M. Caccamo, “Adaptive Allocation of Software and Hardware Real-Time Tasks for FPGA-Based Embedded Systems,” Proc. 12th IEEE Real-Time and Embedded Technology and Applications Symp. (RTAS '06), Apr. 2006.[28] J. Cong, Y. Fan, G. Han, W. Jiang, and Z. Zhang, “Platform-Based Behavior-Level and System-Level Synthesis,” Proc. IEEE Int'l Systems on Chip Conf. (SOCC '06), Sept. 2006.[29] F. Balarin, Y. Watanabe, H. Hsieh, L. Lavagno, C. Passerone, and A. Sangiovanni-Vincentelli, “Metropolis: An Integrated Electronic System Design Environment,” Computer, vol. 36, no. 4, pp. 45-52, Apr. 2003.[30] G. Buttazzo, Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications. Kluwer Academic, 1997.[31] C. Liu and J. Layland, “Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment,” J. ACM, vol. 20, no. 1, 1973.[32] L. Abeni and G. Buttazzo, “Integrating Multimedia Applications in Hard Real-Time Systems,” Proc. 19th IEEE Real-Time Systems Symp. (RTSS '98), Dec. 1998.[33] H. Kellerer, U. Pferschy, and D. Pisinger, Knapsack Problems. Springer, 2004.[34] R. Pellizzoni and M. Caccamo, Adaptive Real-Time Management of Relocatable Tasks for FPGA-Based Embedded Systems, technical report, Univ. of Illinois, http://pertsserver.cs.uiuc.edu/~mcaccamo papers/, 2005.[35] C. Steiger, H. Walder, and M. Platzner, “Operating Systems for Reconfigurable Embedded Platforms: Online Scheduling of Real-Time Tasks,” IEEE Trans. Computers, vol. 53, no. 11, pp. 1393-1407, Nov. 2004.[36] C. Steiger, H. Walder, M. Platzner, and L. Thiele, “Online Scheduling and Placement of Real-Time Tasks to Partially Reconfigurable Devices,” Proc. 24th IEEE Real-Time System Symp. (RTSS '03), Dec. 2003.[37] K. Danne and M. Platzner, “Periodic Real-Time Scheduling for FPGA Computers,” Proc. Third IEEE Int'l Workshop Intelligent Solutions in Embedded Systems (WISES '05), May 2005.[38] K. Danne and M. Platzner, “Partitioned Scheduling of Periodic Real-Time Tasks onto Reconfigurable Hardware,” Proc. 13th Reconfigurable Architectures Workshop (RAW '06), Apr. 2006.[39] K. Bazargan, R. Kastner, and M. Sarrafzadeh, “Fast Template Placement for Reconfigurable Computing Systems,” IEEE Design and Test of Computers, vol. 17, no. 1, pp. 68-83, Jan.-Mar. 2000.[40] O. Diessel, H. ElGindy, M. Middendorf, H. Schmeck, and B. Schmidt, “Dynamic Scheduling of Tasks on Partially Reconfigurable FPGAs,” IEE Proc. Computers and Digital Techniques, vol. 147, no. 3, pp. 181-188, May 2000.[41] G. Brebner and O. Diessel, “Chip-Based Reconfigurable Task Management,” Proc. 11th Int'l Conf. Field-Programmable Logic and Applications (FPL '01), pp. 182-191, 2001.[42] K. Compton, Z. Li, J. Cooley, S. Knol, and S. Hauck, “Configuration Relocation and Defragmentation for Run-Time Reconfigurable Computing,” IEEE Trans. Very Large Scale Integration (VLSI) Systems, vol. 10, no. 3, pp. 209-220, June 2002.[43] M. Gericota, G. Alves, M. Silva, and J. Ferreira, “On-Line Defragmentation for Run-Time Partially Reconfigurable FPGAs,” Proc. 12th Int'l Conf. Field-Programmable Logic and Applications (FPL '02), Sept. 2002.[44] S. Fekete, E. Köhler, and J. Teich, “Optimal FPGA Module Placement with Temporal Precedence Constraints,” Proc. Design, Automation and Test in Europe Conf. (DATE '01), pp. 658-665, 2001.[45] H. Amano, “A Survey on Dynamically Reconfigurable Processors,” IEICE Trans. Comm., vol. 89-B, no. 12, pp. 3179-3187, Dec. 2006.
Index Terms:
Reconfigurable devices, real-time resource management, online admission control, hardware and software tasks
Citation:
Rodolfo Pellizzoni, Marco Caccamo, "Real-Time Management of Hardware and Software Tasks for FPGA-based Embedded Systems," IEEE Transactions on Computers, vol. 56, no. 12, pp. 1666-1680, June 2007, doi:10.1109/TC.2007.70763
