Efficiently scheduling runtime reconfigurations

ABSTRACT

Due to the emergence of portable devices that must run complex dynamic applications there is a need for flexible platforms for embedded systems. Runtime reconfigurable hardware can provide this flexibility but the reconfiguration latency can significantly decrease the performance. When dealing with task graphs, runtime support that schedules the reconfigurations in advance can drastically reduce this overhead. However, executing complex scheduling heuristics at runtime may generate an excessive penalty. Hence, we have developed a hybrid design-time/runtime reconfiguration scheduling heuristic that generates its final schedule at runtime but carries out most computations at design-time. We have tested our approach in a PowerPC 405 processor embedded on a FPGA demonstrating that it generates a very small runtime penalty while providing almost as good schedules as a full runtime approach.

REFERENCES

• 1: Belady, L. A. 1966. A study of replacement algorithms for virtual storage computers. IBM Syst. J., 5, 78--101.
• 2: EDK. 2007. Embedded System Tools Manual. http://www.xilinx.com/ise/embedded/edk91i_docs/est_rm.pdf.
• 3: ISE. 2007. http://www.xilinx.com/publications/prod_mktg/pn0010867.pdf.
• 4: 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]
• 5: Lysaght, P., Blodget, B., Mason, J., Young, J., and Bridgford B. 2006. Enhanced architectures, design methodologies and CAD tools for dynamic reconfiguration of Xilinx FPGAs. In Proceedings of the 2006 International Conference on Field Programmable Logic and Applications. Madrid, Spain, 1--6.
• 6: Théodore Marescaux , Andrei Bartic , Diederik Verkest , Serge Vernalde , Rudy Lauwereins, Interconnection Networks Enable Fine-Grain Dynamic Multi-tasking on FPGAs, Proceedings of the Reconfigurable Computing Is Going Mainstream, 12th International Conference on Field-Programmable Logic and Applications, p.795-805, September 02-04, 2002
• 7: Yury Markovskiy , Eylon Caspi , Randy Huang , Joseph Yeh , Michael Chu , John Wawrzynek , André DeHon, Analysis of quasi-static scheduling techniques in a virtualized reconfigurable machine, 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.503077]
• 8: Juanjo Noguera , Rosa M. Badia, Multitasking on reconfigurable architectures: microarchitecture support and dynamic scheduling, ACM Transactions on Embedded Computing Systems (TECS), v.3 n.2, p.385-406, May 2004 [doi>10.1145/993396.993404]
• 9: Peng Yang , Chun Wong , Paul Marchal , Francky Catthoor , Dirk Desmet , Diederik Verkest , Rudy Lauwereins, Energy-Aware Runtime Scheduling for Embedded-Multiprocessor SOCs, IEEE Design & Test, v.18 n.5, p.46-58, September 2001 [doi>10.1109/54.953271]
• 10: Pocket G. L. 2007. http:/www.sundialsoft.freeserve.co.uk/pgl.htm.
• 11: Yang Qu , Juha-Pekka Soininen , Jari Nurmi, A parallel configuration model for reducing the run-time reconfiguration overhead, Proceedings of the conference on Design, automation and test in Europe: Proceedings, March 06-10, 2006, Munich, Germany
• 12: Resano, J., Mozos D., Verkest, D. Vernalde, S., and Catthoor, F. 2004. A hybrid design-time/run-time scheduling flow to minimize the reconfiguration overhead of FPGAs. J. Microproc. Microarchi. 28, 5--6, 291--301.
• 13: Javier Resano , Daniel Mozos , Francky Catthoor, A Hybrid Prefetch Scheduling Heuristic to Minimize at Run-Time the Reconfiguration Overhead of Dynamically Reconfigurable Hardware, Proceedings of the conference on Design, Automation and Test in Europe, p.106-111, March 07-11, 2005 [doi>10.1109/DATE.2005.18]
• 14: 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]
• 15: Li Shang , Niraj K. Jha, Hardware-Software Co-Synthesis of Low Power Real-Time Distributed Embedded Systems with Dynamically Reconfigurable FPGAs, Proceedings of the 2002 conference on Asia South Pacific design automation/VLSI Design, p.345, January 07-11, 2002
• 16: Walder, H. and Platzner, M. 2004. A runtime environment for reconfigurable operating systems. In Proceedings of the 14th International Conference on Field-Programmable Logic and Applications, Leuven, Belgium, 831--835.
• 17: Chun Wong , Paul Marchal , Peng Yang, Task concurrency management methodology to schedule the MPEG4 IM1 player on a highly parallel processor platform, Proceedings of the ninth international symposium on Hardware/software codesign, p.170-177, April 2001, Copenhagen, Denmark [doi>10.1145/371636.371712]
• 18: Xilinx. 2007. http://www.xilinx.com/univ/xupv2p.html.
• 19: Yang, P. and Catthoor, F. 2004. Dynamic mapping and ordering tasks of embedded real-time systems on multiprocessor platforms. In Proceedings of Software and Compilers for Embedded Systems 8th International Workshop. 167--181.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.3 Other Architecture Styles
          Subjects: Adaptable architectures

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

General Terms:
Algorithms, Design, Performance

Keywords:
FPGAs, Reconfigurable architectures, hardware multitasking, runtime/design-time scheduling