Dynamic Tuning of Configurable
Architectures: The AWW Online Algorithm
Chen Huang, David Sheldon, and Frank
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
Department of Computer Science and Engineering University of
California, Riverside, USA
*Also with the Center for Embedded Computer Systems, UC Irvine
reconfiguration problem: The problem is to choose a
every application in the sequence to minimize total time T,
configuration schedule. Every configuration change in that schedule is
reconfiguration incurring time R. Total time T is the
application execution times on the corresponding configuration in the
plus the time for all reconfigurations.
Three EEMBC apps running on MIPS (SimpleScalar) with 2 Kbyte
instruction cache having configurable line sizes of 16, 32, or
Reconfiguring may reduce total time if reconfiguration is fast, but may
increase total time if reconfiguration is slow
entire paper (PDF).
source code (aww.cpp).
Regents. Permission to use or modify is granted for education and
Any other use requires explicit permission. Contact Frank Vahid at
firstname.lastname@example.org with questions.
For publications derived from these materials, kindly cite the
C. Huang, D. Sheldon, and F. Vahid. Dynamic Tuning of
Architectures: The AWW Online Algorithm.
IEEE/ACM Int. Conf. on Hardware/Software Codesign and System Synthesis,
(CODES/ISSS), Oct 2008.