Dynamic Tuning of Configurable Architectures: The AWW Online Algorithm

Chen Huang, David Sheldon, and Frank Vahid*
Department of Computer Science and Engineering University of California, Riverside, USA
*Also with the Center for Embedded Computer Systems, UC Irvine
{chuang/dsheldon/vahid}@cs.ucr.edu

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 or 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.

Problem overview:

Architecure reconfiguration problem: The problem is to choose a configuration for every application in the sequence to minimize total time T, yielding a configuration schedule. Every configuration change in that schedule is a reconfiguration incurring time R. Total time T is the sum of application execution times on the corresponding configuration in the schedule, plus the time for all reconfigurations.


p1

Figure 1: Three EEMBC apps running on MIPS (SimpleScalar) with 2 Kbyte direct-mapped instruction cache having configurable line sizes of 16, 32, or 64 bytes


p2

Figure 2: Reconfiguring may reduce total time if reconfiguration is fast, but may increase total time if reconfiguration is slow

Resources:
  1. The entire paper (PDF).
  2. The data (EXCEL).
  3. The source code (aww.cpp).

Copyright 2008 UC Regents. Permission to use or modify is granted for education and research purposes only.
Any other use requires explicit permission. Contact Frank Vahid at vahid@cs.ucr.edu with questions.
For publications derived from these materials, kindly cite the following:
C. Huang, D. Sheldon, and F. Vahid.  Dynamic Tuning of Configurable Architectures: The AWW Online Algorithm.
IEEE/ACM Int. Conf. on Hardware/Software Codesign and System Synthesis, (CODES/ISSS), Oct 2008.