MinDeg: a performance-guided replacement policy for run-time reconfigurable accelerators

ABSTRACT

Reconfigurable Processors utilize a reconfigurable fabric (to implement application-specific accelerators) and may perform run-time reconfigurations to exchange the set of deployed accelerators during application execution. Depending on the application requirements, the high utilization of the reconfigurable fabric (due to run-time reconfiguration) leads to a performance improvement compared to non-reconfigurable application-specific processors (ASIPs). However, as the reconfiguration time of fine-grained reconfigurable fabrics (i.e. FPGA-like structures) is rather long (in the range of milliseconds), it is crucial to avoid frequent cycles of reconfiguration-replacement-reconfiguration of the accelerators in order to exploit the real benefits of Reconfigurable Processors. Similar to memory caches, a replacement policy has to decide which reconfigurable accelerators shall be replaced in order to reconfigure additional accelerators. In the case that a recently replaced accelerator is demanded again, the reconfiguration delay might noticeably increase the application execution time.

In this paper, we demonstrate that well-known policies for cache and page replacement (typically also used in state-of-the-art Reconfigurable Processors) are not generally suitable to replace reconfigurable accelerators.

We therefore propose our novel performance-guided Minimum Degradation (MinDeg) replacement policy that particularly targets Reconfigurable Processors and replaces reconfigurable accelerators at run time. It accounts for the performance penalty that occurs due to replacement of a certain accelerator. Comparisons with the most-prominent replacement policies show the superiority of our approach. We evaluate and compare MinDeg for a wide range of different reconfiguration bandwidths and reconfigurable fabric sizes and achieve a speedup of up to 2.26x (1.74x compared to the widely used LRU policy). The introduced overhead to achieve this speedup is minor in comparison to the obtained application acceleration, i.e. the highest observed overhead (to calculate our MinDeg replacement policy) affected the obtained application acceleration by only 0.30%. A parallel hardware implementation of our MinDeg algorithm demands only 4,440 gate equivalents, which corresponds to 64% of the average requirements of one real-world reconfigurable accelerator (note: multiple accelerators are demanded per kernel). However, our MinDeg policy does not rely on hardware support, i.e. a trade-off between the hardware requirements and the acceleration is possible.

REFERENCES

• 1: K. Atasu, L. Pozzi, P. Ienne, "Automatic Application-Specific Instruction-Set Extensions Under Microarchitectural Constraints", Design Automation Conf. (DAC), pp. 256--261, 2003.
• 2: P. Biswas, V. Choudhary, K. Atasu, L. Pozzi, P. Ienne, N. Dutt, "Introduction of local memory elements in instruction set extensions", DAC, pp. 729--734, 2004.
• 3: N. Cheung, J. Henkel, S. Parameswaran, "Rapid Configuration & Instruction Selection for an ASIP: A Case Study", Conf. Design, Autom., and Test (DATE), pp. 802--807, 2003.
• 4: MiBench (http://www.eecs.umich.edu/mibench/).
• 5: C. Lee, M. Potkonjak, W. H. Mangione-Smith, "MediaBench: A Tool for Evaluating and Synthesizing Multimedia and Communications Systems", MICRO, pp. 330--335, 1997.
• 6: L. Bauer, M. Shafique, J. Henkel, "Efficient Resource Utilization for an Extensible Processor through Dynamic Instruction Set Adaptation", Transaction on Very Large Scale Integration (TVLSI), volume 16, issue 10, pp. 1295--1308, 2008.
• 7: Z. Li, S. Hauck, "Configuration prefetching techniques for partial reconfigurable coprocessors with relocation and defragmentation", Int'l Symp. on Field--Programmable Gate Arrays (FPGA), pp. 187--195, 2002.
• 8: L. Bauer, M. Shafique, J. Henkel, "Run-time Instruction Set Selection in a Transmutable Embedded Processor", Design Automation Conference (DAC), pp. 56--61, 2008.
• 9: ITU-T Rec. H.264 and ISO/IEC 14496--10:2005 (E) (MPEG-4 AVC) "Advanced video coding for generic audiovisual services", 2005.
• 10: A. S. Tanenbaum, "Modern Operating System", 3rd revised edition, Prentice Hall, 2007.
• 11: L. A. Belady, "A Study of Replacement Algorithms for a Virtual-Storage Computer", IBM Systems Journal, vol. 5, issue 2, pp. 78--101, 1966.
• 12: P. Kalla, X. S. Hu, J. Henkel, "LRU-SEQ: A Novel Replacement Policy for Transition Energy Reduction in Instruction Caches", Int'l Conference on Computer Aided Design (ICCAD), pp. 518--522, 2003.
• 13: C. Bobda, "Introduction to Reconfigurable Computing", Springer, ISBN 978-1-4020-6088-5, 2007.
• 14: S. Vassiliadis, D. Soudris, "Fine- and Coarse-Grain Reconfigurable Computing", Springer, ISBN 978-1-4020-6504-0, 2007.
• 15: S. Vassiliadis, et al., "The MOLEN polymorphic processor", Trans. on Comp., vol. 53, issue 11, pp. 1363--1375, 2004.
• 16: J. A. Jacob, P. Chow, "Memory interfacing and instruction specification for reconfigurable processors", Int'l Symp. on FPGA, pp. 145--154, 1999.
• 17: E. M. Panainte, K. Bertels, S. Vassiliadis, "The Molen Compiler for Reconfigurable Processors", TECS, vol. 6, issue 1, 2007.
• 18: K. Compton, et al., "Configuration Relocation and Defragmentation for Run-Time Reconfigurable Computing", TVLSI, vol. 10, issue 3, pp. 209--220, 2002.
• 19: A. Ahmadinia, C. Bobda, D. Koch, M. Majer, J. Teich, "Task Scheduling for Heterogeneous Reconfigurable Computers", Symposium on Integrated Circuits and System Design (SBCCI), pp. 22--27, 2004.
• 20: J. Resano, D. Mozos, D. Verkest, F. Catthoor, S. Vernalde, "Specific Scheduling Support to Minimize the Reconfiguration Overhead of Dynamically Reconfigurable Hardware", Design Automation Conference (DAC), pp. 119--124, 2004.
• 21: L. Bauer, M. Shafique, S. Kreutz, J. Henkel, "Run-time System for an Extensible Embedded Processor with Dynamic Instruction Set", Conf. on Design, Automation & Test (DATE), pp. 752--757, 2008.

INDEX TERMS

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

General Terms:
Design, Performance

Keywords:
accelerator, extensible embedded processor, kernel, reconfigurable computing, replacement, run-time adaptation