Dynamic tuning of configurable architectures: the AWW online algorithm

ABSTRACT

Architectures with software-writable parameters, or configurable architectures, enable runtime reconfiguration of computing platforms to the applications they execute. Such dynamic tuning can improve application performance, as well as energy. However, reconfiguring incurs a temporary performance cost. Thus, online algorithms are needed that decide when to reconfigure and which configuration to choose such that overall performance is optimized. We introduce the adaptive weighted window (AWW) algorithm, and compare with several other algorithms, including algorithms previously developed by the online algorithm community. We describe experiments showing that AWW results are within 4% of the offline optimal on average. AWW outperforms the other algorithms, and is robust across three datasets and across three categories of application sequences too. AWW improves a non-dynamic approach on average by 6%, and by up to 30% in low-reconfiguration-time situations.

REFERENCES

• 1: D.H. Albonesi. Selective Cache Ways: On-Demand Cache Resource Allocation. Journal of Instruction Level. Parallelism, May 2000.
• 2: Rajeev Balasubramonian , David Albonesi , Alper Buyuktosunoglu , Sandhya Dwarkadas, Memory hierarchy reconfiguration for energy and performance in general-purpose processor architectures, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.245-257, December 2000, Monterey, California, United States [doi>10.1145/360128.360153]
• 3: Yair Bartal , Avrim Blum , Carl Burch , Andrew Tomkins, A polylog(n)-competitive algorithm for metrical task systems, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.711-719, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258667]
• 4: Avrim Blum , Carl Burch, On-line Learning and the Metrical Task System Problem, Machine Learning, v.39 n.1, p.35-58, April 2000 [doi>10.1023/A:1007621832648]
• 5: Allan Borodin , Nathan Linial , Michael E. Saks, An optimal on-line algorithm for metrical task system, Journal of the ACM (JACM), v.39 n.4, p.745-763, Oct. 1992 [doi>10.1145/146585.146588]
• 6: W.R. Burley and S. Irani. On algorithm design for metrical task system. Algorithmica, 1997, Vol. 18, pp. 461--485.
• 7: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 8: Ann Gordon-Ross , Frank Vahid, A self-tuning configurable cache, Proceedings of the 44th annual conference on Design automation, June 04-08, 2007, San Diego, California [doi>10.1145/1278480.1278537]
• 9: Rakesh Kumar , Dean M. Tullsen , Norman P. Jouppi , Parthasarathy Ranganathan, Heterogeneous Chip Multiprocessors, Computer, v.38 n.11, p.32-38, November 2005 [doi>10.1109/MC.2005.379]
• 10: Kanishka Lahiri , Anand Raghunathan , Ganesh Lakshminarayana , Sujit Dey, Communication architecture tuners: a methodology for the design of high-performance communication architectures for systems-on-chips, Proceedings of the 37th conference on Design automation, p.513-518, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337561]
• 11: Afzal Malik , Bill Moyer , Dan Cermak, A low power unified cache architecture providing power and performance flexibility (poster session), Proceedings of the 2000 international symposium on Low power electronics and design, p.241-243, July 25-27, 2000, Rapallo, Italy [doi>10.1145/344166.344610]
• 12: David Sheldon , Rakesh Kumar , Roman Lysecky , Frank Vahid , Dean Tullsen, Application-specific customization of parameterized FPGA soft-core processors, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California [doi>10.1145/1233501.1233553]
• 13: Krishna Sekar , Kanishka Lahiri , Sujit Dey, Dynamic Platform Management for Configurable Platform-Based System-on-Chips, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.641, November 09-13, 2003 [doi>10.1109/ICCAD.2003.57]
• 14: Pablo Viana , Ann Gordon-Ross , Eamonn Keogh , Edna Barros , Frank Vahid, Configurable cache subsetting for fast cache tuning, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA [doi>10.1145/1146909.1147085]
• 15: Chuanjun Zhang , Frank Vahid , Walid Najjar, A highly configurable cache architecture for embedded systems, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California

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.1 PROCESSOR ARCHITECTURES
      C.1.3 Other Architecture Styles
          Subjects: Heterogeneous (hybrid) systems

General Terms:
Algorithms, Design, Performance

Keywords:
FPGAs, cache, configurable architecture, dynamic optimization, online algorithms, runtime configuration, tuning