# Multi-objective Optimization of Energy Consumption and Execution Time in a
Single Level Cache Memory for Embedded Systems

Josefa Díaz Álvarez<EMAIL_ADDRESS>José L. Risco-Martín<EMAIL_ADDRESS>J.
Manuel Colmenar<EMAIL_ADDRESS>Centro Universitario de Mérida,
Universidad de Extremadura, 06800 Mérida, Spain  Dpt. of Computer Architecture
and Automation, Complutense University of Madrid, C/Prof. José García
Santesmases 9, 28040 Madrid, Spain  Dpt. of Computer Science, Rey Juan Carlos
University, 28933 Móstoles, Spain

###### Abstract

Current embedded systems are specifically designed to run multimedia
applications. These applications have a big impact on both performance and
energy consumption. Both metrics can be optimized selecting the best cache
configuration for a target set of applications. Multi-objective optimization
may help to minimize both conflicting metrics in an independent manner. In
this work, we propose an optimization method that based on Multi-Objective
Evolutionary Algorithms, is able to find the best cache configuration for a
given set of applications. To evaluate the goodness of candidate solutions,
the execution of the optimization algorithm is combined with a static
profiling methodology using several well-known simulation tools. Results show
that our optimization framework is able to obtain an optimized cache for
Mediabench applications. Compared to a baseline cache memory, our design
method reaches an average improvement of 64.43% and 91.69% in execution time
and energy consumption, respectively.

###### keywords:

Cache memory, Energy, Performance, Multi-objective optimization, Evolutionary
Computation

##  1 Introduction

Multimedia embedded systems like digital cameras, audio and video players,
smartphones, etc., are one of the major driving forces in technology.
Currently, they have less powerful resources than desktop systems, but these
systems must run multimedia software (video, audio, gaming, etc.). These
applications require high performance and consume much energy, which reduces
the battery lifetime. The battery in embedded systems is limited in capacity
and size because of design constraints. Hence, embedded systems designers must
be very concerned on both increasing performance and reducing energy
consumption, which in turn will also affect to the lifetime of the device.

In recent years, a number of scientific papers have been published indicating
that the memory subsystem acts as an energy bottleneck of the system [1]. In
fact, cache memory behavior affects both performance and energy consumption.
The best cache configuration gives us the minimum execution time and the
lowest energy consumption. Total cache and block sizes, associativity, and
algorithms for search, prefetch and replacement, or write policies are some of
the parameters that form a cache configuration. Finding optimal values for
these parameters will guide us to reach the best performance and energy
consumption. Finding an optimal cache configuration for one single application
is a bad choice for other applications with different memory access patterns
[2]. Thus, we tackle the problem of finding the optimal cache configuration
for all the applications executed in an embedded device, which will improve
performance and energy consumption.

Energy optimization directly affects aging of transistors, which is a limiting
factor for long term reliability of devices. In a common context where the
lifetime of a device is determined by the earliest failing component, the
aging impact is more serious on memory arrays, where failure of a single SRAM
cell would cause the failure of the whole system. Previous works have shown
that saving energy in the memory subsystem can effectively control aging
effects and can extend lifetime of the cache significantly [3], [4]. Our
approach, which optimizes performance and energy, is also indirectly improving
the long term reliability of the target device.

A first brute-force approach to obtain the best cache configuration would
require the execution and evaluation of time and energy for all available
cache configurations and target applications, which is an unmanageable task
given current time-to-market reduced windows. In addition, execution time and
energy consumption are conflicting objectives in practice. For example, if
associativity is increased, the number of misses is reduced, as well as the
execution time. However, a high associativity increases the hardware
complexity and thus the energy consumed by the cache memory [2]. Therefore, we
present in this paper a new methodology to evaluate cache configurations in
order to customize cache designs with the aim of reducing both the execution
time and the energy consumption by means of a multi-objective optimization
[5]. In particular, our optimization framework is built around the Non-
dominated Sorting Genetic Algorithm II (NSGA-II) [6]. In order to evaluate our
approach, we have automatically designed caches optimized for a set of
multimedia applications taken from Mediabench benchmarks [7], since they are
representative for image, audio and video processing. Our hardware
architecture is based on the ARM920T processor [8], broadly used in multimedia
embedded devices.

The rest of the paper is organized as follows. Next Section summarizes the
related work on the topic. Section 3 describes the design of the search space
for our multi-objective optimization. Section 4 shows details of our multi-
objective function, describing both performance and energy models. Our
optimization framework is integrated and explained in Section 5. Then, Section
6 analyzes our experimental results. In Section 7, we present our conclusions
based on the results obtained, and explain the main lines of our future work.

##  2 Related work

The optimization of performance and energy consumption in the memory subsystem
have received a lot of attention in the last decade. Regarding performance,
multiple research works have been developed with the aim of improving
performance through changing architectural parameters. With respect to energy,
previous studies have demonstrated that half of the energy consumption in
embedded systems is due to the cache memory [1]. The optimization of these
parameters has been conducted mainly using two different techniques: dynamic
reconfiguration and static profiling.

Regarding dynamic reconfiguration, Givargis [9] improved cache performance by
choosing a variable set of bits used as index into the cache. Zhang minimized
the energy consumption introducing a new cache design method called way
concatenation to reconfigure the cache by software [10]. However, this
approach provided a limited number of cache configurations, allowing the
system engineer to optimize associativity (one-way, two-way or four-way),
cache size and line size. Chen and Zou [11] proposed an efficient
reconfiguration management algorithm to optimize three parameters: cache size,
line size and associativity. Similarly, Gordon-Ross and Frank Vahid [12]
presented a dynamic tuning methodology to optimize cache sizes (2, 4, or 8
KBytes), line sizes (16, 32, or 64 bytes), and associativity (1-way, 2-way or
4-way). López et al. [13] proposed an on-line algorithm on _Simultaneous
Multithreading (SMT)_ to decide the cache configuration after a fixed set of
instructions, a technique based on a cache working-set adaptation [14].
Dynamic reconfiguration in soft real-time embedded systems on single-level
cache hierarchy was proposed by Wang et al. in [15], and on a multi-level
cache hierarchy in [16]. More recently, Wang et al. [17] minimize energy
consumption in real-time embedded systems performing dynamic analysis during
runtime. All these approaches optimize cache size (1, 2 or 4KB), line-size
(16, 32 or 64 bytes) and associativity (1-way, 2-way or 4-way). The main
inconvenient of dynamic reconfiguration is the addition of extra complexity in
the design of the memory subsystem. We also see that these approaches only
optimize a few number of cache parameters, minimizing either execution time or
energy consumption. In addition, it is proved in this work that an offline
multi-objective optimization may find optimal cache parameter values, without
the need of adding hardware complexity to the standard memory subsystem
design.

With respect to the use of static profiling, Rackesh Reddy in [18] studied the
effect of multiprogramming workloads on the data cache in a preemptive
multitasking environment, and proposed a technique that mapping tasks to
different cache partitions, significantly reduced both dynamic and leakage
power. Our approach is different, since we try to obtain the behavior of a
target set of applications, obtaining their full static profile and the best
memory cache configuration (i.e., size, associativity, and replacement and
prefetching algorithms for both data and instruction caches) for the whole
set. Andrade et al. presented in [19] an extension of a systematic analytical
modeling technique based on probabilistic miss equations, allowing the
automated analysis of the cache behavior for codes with irregular access
patterns resulting from indirections. Nevertheless, these models can only
optimize cache size and associativity. Feng et al. [20] applied a new cache
replacement policy to perform the replacement decision based on the reuse
information of the cache lines and the requested data developing two reuse
information predictors: a profile-based static predictor and a runtime
predictor. Similarly, Xingyan and Hongyan [21], based on a profiling scheme of
the OPT cache replacement, presented a method to generate best static cache
hints. However, these approaches only improve the replacement algorithm.
Gordon-Ross et al. [22] studied the interaction of code reordering and cache
configuration, obtaining excellent results. However, this technique is applied
to the intruction cache, and our systematic optimization method is applied to
the full configuration of both the instruction and data caches.

Additionally, all the aforementioned approaches minimized either execution
time or energy consumption. We propose the use of multi-objective optimization
to simultaneously minimize both objectives. To this end, we use the concept of
multi-objective optimization, which can be easily applied in evolutionary
computation. Evolutionary computation and multi-objective optimization are
being widely used in _Computer Aided Design (CAD)_ problems. Close to cache
optimization, Risco et al. [23] applied a novel parallel multi-objective
evolutionary algorithm to optimize desktop applications for their use in
multimedia embedded systems, improving performance, memory usage and energy
consumption of the memory subsystem. In [24] a simple online _Genetic
Algorithm (GA)_ was used to obtain the best cache associativity to improve the
performance of SMT processors. In this line, Bui et al. [25] proposed a
solution for the cache interference problem applying cache partitioning
techniques using a simple GA whose solution sets the size of each cache
partition and assigns tasks to partitions such that system worst-case
utilization is minimized thus increasing real-time schedulability. An approach
based on NSGA-II algorithm was used in [26] to evaluate cache configurations
on a second cache-level in order to improve energy consumption and
performance, optimizing cache size, line size and associativity. However, none
of these approaches is able to simultaneously optimize cache performance and
energy consumption for a target set of applications as our methodology
performs.

To the best of our knowledge none of the previous works tackle the
optimization of all the parameters that we propose in this research work. Most
of the cited papers focus their space exploration on cache size, line size and
associativity, even though the possible values for each configurable parameter
is quite small. In this work, we optimize the following cache parameters:
cache size, line size, associativity, replacement policy, prefetch policy and
write policy. We also consider first-level (L1) instruction/data caches,
although the methodology proposed can be applied to other cache types. All the
aforementioned configurable parameters complete the chromosome in the _Multi-
Objective Evolutionary Algorithm (MOEA)_ proposed. The aim is to find the best
cache configurations that minimizes memory access time (performance) and
energy consumption. As we try to minimize two conflicting objectives, multi-
objective optimization is suitable to address this problem. Our approach is
valid on embedded systems, where the small number of applications allows the
engineer to select one cache design among all the optimizations performed, as
we show in this work.

##  3 Design of the search space representation

Figure 1: Taxonomy for a cache configuration. Both instruction and data
caches, labeled as I-Cache and D-Cache, must be customized with available
values.

Designing a cache memory implies the configuration of the set of parameters
that define it: cache size, line size, replacement algorithm, associativity
and prefetch algorithm for both the instruction and data caches, and also
write policy for data cache. Figure 1 shows these parameters and the possible
candidate values that we consider in our research for the instruction cache
(labeled as I-Cache) and data cache (labeled as D-Cache). These possible
values, most of them illustrated in Figure 1, are described below:

  * 1.

Cache size: memory cache capacity in bytes. We consider a fixed cache size of
16 KB, which is the default size of the ARM920T cache [8], our target system.

  * 2.

Line size: cache memory is divided into lines (blocks). When a miss takes
place, a whole line is moved from main memory to cache memory. Possible values
for this parameter are 8, 16, 32 and 64 bytes.

  * 3.

Cache replacement algorithm: set of techniques designed to replace blocks.
Algorithms selected to evaluate are: _Last Recently Used (LRU)_ , _First Input
First Output (FIFO)_ and RANDOM algorithms.

  * 4.

Associativity: the degree of associativity refers to the number of places in a
cache where a block can be located. It is defined by the number of ways. In
this work we deal with 4, 8, 16, 32 and 64 ways.

  * 5.

Prefetch algorithm: determines the policy to carry blocks to the cache memory.
We consider three of them: (1) when a cache miss occurs (MISS-PREFETCH), (2)
only when the data is required (ON-DEMAND), and (3) when data from a block is
referenced, the following block is also prefetched (ALWAYS-PREFETCH).

  * 6.

Write policy: it is designed to keep consistency between cache and main memory
when data is modified in cache memory. Data stored in L1-cache can be written
to main memory only when absolutely needed, with a COPY-BACK policy, or maybe
written to cache and main memory simultaneously, with a WRITE-TROUGH policy.

Hence, the size of the search space is 64800 cache configurations for each
cache size. Thereby, a deterministic technique can take huge time slots to
find an optimal solution (more than four months, as shown in Section 6), since
each configuration must be evaluated with a program trace. In this regard,
heuristic techniques fit well in solving the multi-objective optimization
problem especially when a set of conflicting design objectives must be
minimized. MOEAs usually provide good results in a multi-objective
environment. In this context, a set of candidate solutions called individuals
evolves improving a multi-objective fitness function (an individual is formed
by a chromosome plus the associated value of the multi-objective function).

According to this choice, the encoding of different parameters values is
necessary for the suitable development of the selected technique. An
appropriate coding of the chromosome is essential to achieve the optimal
solution and this will depend on the kind of problem to solve. Our approach
works with the first-level cache and both instruction and data cache can be
customized with eligible values for each parameter. Thus, a possible solution
(individual) is defined as a specific cache configuration for I-cache and
D-cache. Individual genes are then related to possible values of cache
configuration parameters. Therefore, a chromosome is defined by the sequence
of parameters for a specific cache configuration, coded as integer values. A
chromosome, in our approach, looks like the one depicted in Figure 2.

Figure 2: Chromosome Specification.

Thus, the chromosome applies an encoding scheme where each gene is an integer
value that is mapped to the alphanumeric symbols (e.g. 8, 16, 32 for Line Size
and LRU, FIFO, RANDOM for Replacement Policy) defined in Figure 1, considering
values from left to right, and starting with $0$.

As an example, lets consider the chromosome in Figure 4. The first and fifth
genes “1” and “0” are the line sizes for the I-cache and D-cache, 16 and 8
bytes, respectively (following Figure 1). Next, second and sixth genes “0” and
“2” correspond to the degree of associativity, 4 and 16 ways. The third and
seventh genes “1” and “0” correspond to the replacement algorithm, and are
mapped to the FIFO and LRU algorithms. The fourth and eighth genes “2” and “0”
are the MISS-PREFETCH and ON-DEMAND prefetch algorithms. Finally, the ninth
gene “0” is mapped to copy-back policy. So, full genome decoded is shown in
Figure 4.

Figure 3: A chromosome or individual’s genome.

Figure 4: Decoded individual’s genome.

##  4 Multi-objective function

Our approach defines a decision variable $\mathbf{x}\in\mathbf{X}$ in a multi-
objective optimization context (see A). Variable $\mathbf{x}$ defines a set of
cache parameters values that represent a cache configuration to evaluate. The
evaluation process consists of calculating the multi-objective function
$\mathbf{f}$ as the execution time and the energy consumption, both of them
related to cache memory operations. Therefore, the best cache configuration
will correspond with low values of execution time and energy consumption. As
stated above, both are conflicting objectives.

In order to evaluate different cache configurations we have applied energy and
performance models based on [27]. So, the design of the embedded system
architecture consists of a processor with one cache level with an instruction
cache, a data cache and embedded DRAM as main memory. Both instruction and
data caches are 16 Kbytes in size according to the default characteristics of
the ARM920T processor [8], our target platform. The instruction cache is read-
only. Main memory is 64 MB in size according to datasheets of devices like Car
GPS HS-3502, for example.

###  4.1 First objective: performance model

The equation used to calculate execution time is described bellow. Execution
time is computed according to time needed to solve accesses and misses on the
cache memory system.

$\displaystyle execTime$ $\displaystyle=$ $\displaystyle I_{access}\times
I_{access\\_time}+$ (1) $\displaystyle I_{miss}\times DRAM_{access\\_time}+$
$\displaystyle I_{miss}\times I_{line\\_size}\times\frac{1}{DRAM\\_bw}+$
$\displaystyle D_{access}\times D_{access\\_time}+$ $\displaystyle
D_{miss}\times DRAM_{access\\_time}+$ $\displaystyle D_{miss}\times
D_{line\\_size}\times\frac{1}{DRAM\\_bw}$

  * 1.

$I_{access}$ and $D_{access}$ are the number of cache memory accesses to the
instruction and data cache, respectively.

  * 2.

$I_{miss}$ and $D_{miss}$ are the number of cache misses (when the data
searched is not found in the cache memory and must be copied from the main
memory).

  * 3.

$I_{access\\_time}$ and $D_{access\\_time}$ represent the access time to the
instruction and data cache respectively per access.

  * 4.

$DRAM_{access\\_time}$ is the main memory latency time.

  * 5.

$I_{line\\_size}$ and $D_{line\\_size}$ correspond to line size (or block
size) for instruction a data cache, respectively.

  * 6.

$DRAM\\_{bw}$ is the bandwidth of the DRAM (transfer capacity).

This equation have six well defined parts, as detailed in [27]. Therefore,
$I_{access}\times I_{access\\_time}$ is the total time due to instruction
cache accesses. $I_{miss}\times DRAM_{access\\_time}$ is the total time spent
by main memory accesses in response to instruction cache misses.
$I_{miss}\times I_{line\\_size}\times\frac{1}{DRAM\\_bw}$ represents the total
time needed to fill a cache line for each cache miss on the instructions
cache. $D_{access}\times D_{access\\_time}$ is the total time due to data
cache accesses. $D_{miss}\times DRAM_{access\\_time}$ is the total time spent
by main memory accesses in response to data cache misses and $D_{miss}\times
D_{line\\_size}\times\frac{1}{DRAM\\_bw}$ represents the total time needed to
fill a cache line for each cache miss on the data cache.

###  4.2 Second objective: energy model

Energy model is explained according to the following equation:

$\displaystyle Energy$ $\displaystyle=$ $\displaystyle execTime\times
CPU_{power}+$ (2) $\displaystyle I_{access}\times I_{access\\_energy}+$
$\displaystyle D_{access}\times D_{access\\_energy}+$ $\displaystyle
I_{miss}\times I_{access\\_energy}\times I_{line\\_size}+$ $\displaystyle
D_{miss}\times D_{access\\_energy}\times D_{line\\_size}+$ $\displaystyle
I_{miss}\times DRAM_{access\\_power}\times$
$\displaystyle(\small{DRAM_{access\\_time}}+\small{I_{line\\_size}}\times\frac{1}{\small{DRAM_{bw}}})+$
$\displaystyle D_{miss}\times DRAM_{access\\_power}\times$
$\displaystyle(\small{DRAM_{access\\_time}}+\small{D_{line\\_size}}\times\frac{1}{\small{DRAM_{bw}}})$

where varibles not described in Section 4.1 are:

  * 1.

$DRAM_{access\\_power}$ is the power consumption for each DRAM access.

  * 2.

$I_{access\\_energy}$ and $D_{access\\_energy}$ correspond to energy
consumption in each instruction and data cache access, respectively.

The $I_{access}\times I_{access\\_energy}$ and $D_{access}\times
D_{access\\_energy}$ terms calculate the energy consumption because of
instructions and data cache, respectively. $I_{miss}\times
I_{access\\_energy}\times I_{line\\_size}$ and $D_{miss}\times
D_{access\\_energy}\times D_{line\\_size}$ is the energy cost of filling
information into instruction and data caches respectively from main memory
when miss occurs. The last two terms calculate the energy cost of the DRAM to
respond to cache misses.

In our approach we remove the first term of the Energy equation
$execTime\times CPU_{power}$ because of three reasons: (1) the term
$CPU_{power}$ is constant and the term $execTime$ is already being minimized
in the first objective, (2) it represents the amount of energy consumed by the
CPU and we are optimizing just the performance and energy consumed by the
memory subsystem, and (3) in a multi-objective optimization all the objectives
must be as orthogonal as possible, i.e., the term $execTime$ is redundant.
Thus, our second objective is reduced to:

$\displaystyle Energy$ $\displaystyle=$ $\displaystyle I_{access}\times
I_{access\\_energy}+$ (3) $\displaystyle D_{access}\times
D_{access\\_energy}+$ $\displaystyle I_{miss}\times I_{access\\_energy}\times
I_{line\\_size}+$ $\displaystyle D_{miss}\times D_{access\\_energy}\times
D_{line\\_size}+$ $\displaystyle I_{miss}\times DRAM_{access\\_power}\times$
$\displaystyle(\small{DRAM_{access\\_time}}+\small{I_{line\\_size}}\times\frac{1}{\small{DRAM_{bw}}})+$
$\displaystyle D_{miss}\times DRAM_{access\\_power}\times$
$\displaystyle(\small{DRAM_{access\\_time}}+\small{D_{line\\_size}}\times\frac{1}{\small{DRAM_{bw}}})$

All the equations use seconds for time, watts for power, Joules for energy,
bytes for cache line size and bytes/sec for bandwidth.

Our algorithm evolves to minimize execution time and/or energy consumption.
After a given number of generations the algorithm returns a Pareto Front (an
approximation to the Pareto Optimal Front), that represents the best set of
configurations to apply to the cache memory. The higher the number of
generations, the better is the quality of the cache memory.

##  5 Optimization framework

In this section we describe the framework used to optimize cache memories for
multimedia embedded systems. As mentioned above, this work proposes an
approach to determine the best cache configurations for a given set of
applications. The best cache configurations are those which take less
execution time and less energy consumption. Figure 5 depicts all the steps
needed to carry out the optimization process.

Figure 5: Three processes are involved in the cache configuration
optimization: (1) cache characterization, (2) application profiling and (3)
cache optimization.

We have divided our optimization process into three different phases, labeled
in Figure 5. Firstly, two processes are executed just once before the
optimization (labeled as 1 and 2). Next, the optimization is performed
(labeled as 3), using as input the results of the previous two phases. We have
extracted the first two off-line phases from the optimization phase to save
execution time. The first phase is performed in one hour, whereas the second
phase can be completed in four hours. Using this pre-characterization policy
saves months to the optimization process (more details of execution time are
provided in Section 6). In the following, we describe more in depth these
three phases.

The first phase is _cache characterization_. The characterization of the DRAM
and cache memory is performed using Cacti [28] to compute access times and
energy. Cacti is a widely used analytical model to estimate energy and power
consumption, performance and area of caches. The characterization is performed
off-line. Basic inputs required by Cacti are cache size, line size and
associativity. Since the cache size is fixed, and line size and degree of
associativity have 4 possible values, the number of possible cache
characterizations is 16. After this phase, all the parameters needed in the
objective function (equations 1 and 3) are available.

The second phase is _application profiling_. All the target applications are
simulated with Trimaran and all cache memory accesses are compiled and saved
in program traces. Trimaran is an integrated compilation and performance
monitoring infrastructure which provides enough resources to obtain
application traces with accuracy. Trimaran customizes ARM processors through
simpleScalar [29], an architectural simulator that can model a large set of
different architectures. The processing time required to perform this phase
depends on the number of target applications and the number of instructions to
simulate.

The third phase is _cache optimization_. This phase must be repeated for each
target application and is carried out by the NSGA-II algorithm implemented in
the JECO library [30]. NSGA-II evaluates every candidate solution calling
Dinero IV, which is a trace-driven cache simulator [31]. Dinero IV receives a
cache configuration from NSGA-II and returns the number of cache hits and
misses for the corresponding target application trace. These data, and the
parameters obtained in the first phase are then included in the multi-
objective function to compute both the execution time and energy consumed.

We have selected NSGA-II as the multi-objective optimization algorithm
because, according to a recent survey published in [32], the current de facto
standard evolutionary algorithm for multi-objective optimization is NSGA-II.
This survey states that NSGA-II was used as a single algorithm in 53% of the
examined papers, positioning the algorithm as one of the most widely used
MOEAs, and obtaining very competitive results. Since our aim is to provide a
technique to automatically design optimized cache memories, and not to find
the best optimization algorithm, we propose the use of this one.

Figure 6: Single point crossover. Figure 7: Integer flip mutation.

For NSGA-II, we have used single point crossover and integer flip mutation
operators. The single point crossover is illustrated in Figure 6, where a
random point is selected in the chromosome and used to generate two children.
Similarly, the integer flip mutation is depicted in Figure 7. A random integer
is generated for all those genes that must be mutated (according to the
mutation probability), always constrained to the limits of the corresponding
gene. Following the example given in Figure 7, the third gene is mutated,
modifying its value from “1” to “0”, which in the phenotype is translated into
a change from FIFO to LRU replacement algorithm, respectively.

##  6 Experiments

Our simulation environment consists of an Intel(R) Core(TM) i7-3770 CPU @
3.40GHz with 16 GB RAM memory, with a GNU/Linux Debian 7 Operating System
running a master-worker parallel version of NSGA-II with 8 workers.
Experimental results are based on the ARM architecture. ARM processors are
widespread on multimedia embedded devices. ARM920T [8] is a typical embedded
processor used in tablets, smartphones, and set-top boxes like Motorola Q9m
Verizon Mobile Phone, Car GPS HS-3502, etc. The ARM920T processor is a member
of the ARM9TDMI family of general-purpose microprocessors, which have a
standalone processor core on a Harvard architecture device. By default, the
ARM920T processor implements a separate 16 KB instruction and data cache.

###  6.1 Setup

To evaluate the effectiveness of our approach we have selected a subset of the
Mediabench [7] applications suite as our target applications. Although our
methodology can be used with any kind of applications, the Mediabench
benchmark has been selected because of the high variability in block size,
which provides heterogeneity to the exploration space. Using our methodology,
we design an optimal first level cache memory with fixed-size for instructions
and data, similar to some devices that have an ARM920T processor. After that,
we have validated our optimization framework with two additional hardware
platforms. We have simulated twelve Mediabench benchmarks: cjpeg, djpeg,
mpegdec, mpegenc, gsmdec, gsmenc, epic, unepic, pegwitdec, pegwitenc,
rawcaudio and rawdaudio, all of them with their standard input. As stated
above, we have generated their traces using Trimaran tools [33]. Trimaran
works with SimpleScalar [29]. Thus, we have modified both SimpleScalar and
Trimaran tools to obtain application traces according to the Dinero IV cache
simulator, which is continuously called by our parallel NSGA-II implementation
to evaluate each candidate solution.

Every application has been simulated for $7.5\times 10^{7}$ instructions to
reach a balance between the simulation time, the size of the program traces
generated and a proper number of instructions. NSGA-II has been executed 30
times for each target application.

Number of generations | $250$
---|---
Population size | $100$
Chromosome length | $9$
Probability of crossover | $0.9$
Probability of mutation | $1/9$
Table 1: NSGA-II Algorithm Parameters.

Table 1 shows the NSGA-II configuration. As crossover and mutation
probabilities, we have used the values recommended in [6]. The number of
generations and individuals has been fixed after several tests.

###  6.2 Optimization Results

In the following we show and analyze all the results obtained in this research
work. Figures 8 and 9 show the Pareto fronts obtained with our optimization
framework. Each point in the graph represents a cache configuration and the
corresponding execution time and energy, driven by equations (1) and (3),
respectively.

Figure 8: Pareto front representation for epic, unepic, gsmdec, gsmenc,
pegwitdec and pegwitenc. Figure 9: Pareto front representation for cjpeg,
djpeg, mpegdec, mpegenc, rawcaudio and rawdaudio.

From Figures 8 and 9, we may observe that the algorithm obtains at least one
optimized cache configuration for each application. Indeed we confirm our
hypothesis that both execution time and energy are conflicting objectives. It
is worth noting that we can see a single point in some plots, which seems to
represent a single solution instead of a Pareto front. However, these single
points represent more than one cache configuration with the same values in the
objective space. To illustrate this point, we show in Table 2 the Pareto set
obtained for each application, along with their respective objective values.
The mpegdec application, for example, shows two different cache configurations
for the same objective values. The same happens with rawcaudio, with 17
different configurations with same objective values. This is an excellent
result, because the selection of a good cache configuration for all the target
applications is simplified.

Application | LI | WI | RI | SI | LD | WD | RD | AD | SD | ExTime | Energy
---|---|---|---|---|---|---|---|---|---|---|---
mpegdec | 8 | 4 | RANDOM | Always | 8 | 4 | LRU | Write-back | Miss-prefetch | 0.04116 | 0.00082
Write-through | 0.04116 | 0.00082
mpegenc | 8 | 4 | LRU | Always | 8 | 4 | LRU | Write-back | Miss-prefetch | 0.04371 | 0.000864
Write-through | 0.04371 | 0.000864
32 | Write-back | 0.04351 | 0.001101
Write-through | 0.04351 | 0.001101
jpeg | 8 | 4 | LRU | Always | 8 | 4 | LRU | Write-back | Miss-prefetch | 0.04778 | 0.000917
Write-through | 0.04778 | 0.000917
16 | Write-back | 0.04649 | 0.001043
Write-through | 0.04649 | 0.001043
32 | Write-back | 0.04548 | 0.001367
Write-through | 0.04548 | 0.001367
djpeg | 8 | 4 | LRU | Always | 8 | 4 | LRU | Write-back | Miss-prefetch | 0.05233 | 0.00102
Write-through | 0.05233 | 0.00102
16 | Write-back | 0.05197 | 0.00120
Write-through | 0.05197 | 0.00120
32 | Write-back | 0.05132 | 0.00169
Write-through | 0.05132 | 0.00169
epic | 8 | 4 | LRU | Always | 8 | 4 | LRU | Write-back | Miss-prefetch | 0.03187 | 0.00062
Write-through | 0.03187 | 0.00062
16 | Write-back | 0.03154 | 0.00067
Write-through | 0.03154 | 0.00067
32 | Write-back | 0.03129 | 0.00078
Write-through | 0.03129 | 0.00078
unepic | 8 | 4 | LRU | Always | 8 | 4 | LRU | Write-back | Miss-prefetch | 0.007488 | 0.0001399
Write-through | 0.007488 | 0.0001399
16 | RANDOM | Write-back | 0.007108 | 0.0001561
Write-through | 0.007108 | 0.0001561
32 | Write-back | 0.0069067 | 0.0001997
Write-through | 0.0069067 | 0.0001997
RANDOM | Write-back | 0.0069068 | 0.0001997
Write-through | 0.0069068 | 0.0001997
rawcaudio | 8 | 4 | FIFO | Always | 8 | 4 | FIFO | Write-back | Miss-prefetch | 0.00673 | 0.00013
Write-through | 0.00673 | 0.00013
LRU | Write-back | 0.00673 | 0.00013
Write-through | 0.00673 | 0.00013
RANDOM | Write-back | 0.00673 | 0.00013
Write-through | 0.00673 | 0.00013
LRU | FIFO | Write-back | 0.00673 | 0.00013
Write-through | 0.00673 | 0.00013
LRU | Write-back | 0.00673 | 0.00013
Write-through | 0.00673 | 0.00013
RANDOM | Write-back | 0.00673 | 0.00013
Write-through | 0.00673 | 0.00013
RANDOM | FIFO | Write-back | 0.00673 | 0.00013
Write-through | 0.00673 | 0.00013
LRU | Write-back | 0.00673 | 0.00013
Write-through | 0.00673 | 0.00013
rawdaudio | 8 | 4 | LRU | Always | 8 | 4 | FIFO | Write-back | Miss-prefetch | 0.00492 | 0.000098
Write-through | 0.00492 | 0.000098
LRU | Write-back | 0.00492 | 0.000098
Write-through | 0.00492 | 0.000098
RANDOM | Write-back | 0.00492 | 0.000098
Write-through | 0.00492 | 0.000098
RANDOM | Write-back | 0.00492 | 0.000098
Write-through | 0.00492 | 0.000098
gsmdec | 8 | 4 | LRU | Always | 8 | 4 | LRU | Write-back | Miss-prefetch | 4.91E-005 | 9.29E-007
Write-through | 4.91E-005 | 9.29E-007
16 | Write-back | 4.84E-005 | 1.08E-006
Write-through | 4.84E-005 | 1.08E-006
32 | Write-back | 4.80E-005 | 1.49E-006
Write-through | 4.80E-005 | 1.49E-006
gsmenc | 8 | 4 | LRU | Always | 8 | 4 | LRU | Write-back | Miss-prefetch | 0.000048 | 0.0000009
Write-through | 0.000048 | 0.0000009
16 | Write-back | 0.000047 | 0.0000011
Write-through | 0.000047 | 0.0000011
32 | Write-back | 0.000047 | 0.0000014
Write-through | 0.000047 | 0.0000014
pegwitdec | 8 | 4 | RANDOM | Always | 8 | 4 | LRU | Write-back | On-demand | 0.01795 | 0.00034
Write-through | 0.01795 | 0.00034
pegwitenc | 8 | 4 | LRU | Always | 8 | 4 | LRU | Write-back | On-demand | 0.02952 | 0.00055
Write-through | 0.02952 | 0.00055
Table 2: Pareto Sets for a Cache Size of 16 KB.

In this regard, Table 2 shows that there are two cache configurations found in
nine out of the twelve applications under study. One of these two
configurations is shown in Figure 10.

Figure 10: Cache Configuration shared by all the Pareto sets.

Mpegdec, pegwitdec and pegwitenc are the only applications that do not share
this cache configuration. The best configurations found save a $63.45\%$ and
$91.68\%$ for mpegdec, $60.09\%$ and $92.46\%$ for pegwitdec and $59.74\%$ and
$92.55\%$ for pegwitenc in execution time and energy, respectively. However,
we have detected that using the cache configuration of Figure 10, we save
almost the same quantities in execution time and energy ($61.39\%$ and
$90.98\%$ for mpegdec, $60.05\%$ and $91.83\%$ for pegwitdec and $58.89\%$ and
$92.14\%$ for pegwitenc). Definitely, these are really good results to unify
the selection process of an optimized cache configuration, for a target set of
applications.

However, the number or points in the final Pareto front is small compared to
the size of the search space (more than 64000 alternatives, as computed in
Section 3). It might occur because NSGA-II have found the global optimum or
the algorithm usually falls into a strong local optimum. To clarify this
point, we have computed the hypervolume indicator ($I_{H}^{-}$) for each
single run (see A).

Table 3 shows all the hypervolumes averaged for most of the 30 different runs
and 7 applications. We did not compute the hypervolume indicator for all the
target applications because in some of them we just obtained the same single
solution in each of the 30 runs, and the hypervolume cannot be computed for
one single point. In the remaining cases, it is worth noting that the standard
deviation is almost 0 for all the seven applications, i.e., NSGA-II is finding
the same Pareto front on each simulation. Given that the algorithm always
started with a different random initial population, it probably means that
NSGA-II reached the _Pareto-Optimal_ front.

Application | Mean | STD
---|---|---
epic | $-0.61$ | 0
unepic | $-0.69$ | 0
jcpeg | $-0.61$ | 0
jdpeg | $-0.47$ | 0
gsmdec | $-0.64$ | 0
gsmenc | $-0.62$ | $1.18\times 10^{-16}$
mpegenc | $-0.21$ | 0
Table 3: Hypervolume Metric (S-metric).

###  6.3 Comparison with a baseline cache

To analyze the level of improvement using our optimization framework, we
compare our results with those obtained by a baseline cache configuration. The
selected baseline configuration appears in devices mentioned above (Motorola
Q9m Verizon Mobile Phone, Car GPS HS-3502, among others). This cache has the
following configuration values:

  * 1.

Icache: Cache size: 16 KB; Block size: 16; Associativity: 64; Replacement
algorithm: LRU: Prefetch policy: ON-DEMAND;

  * 2.

Dcache: Cache size: 16 KB; Block size: 16; Associativity: 64; Replacement
algorithm: LRU: Prefetch policy: ON-DEMAND; Write policy: COPY-BACK;

We have computed execution time and energy for this baseline cache following
our model developed in Section 4. Next, we compare each point in the Pareto
fronts depicted in Figures 8 and 9 with the baseline metrics using the
following equations:

$\displaystyle\mathrm{Improvement}_{\mathrm{execTime}}$ $\displaystyle=$
$\displaystyle
100\times\frac{T_{\mathrm{baseline}}-T_{\mathrm{optimized}}}{T_{\mathrm{baseline}}}$
(4) $\displaystyle\mathrm{Improvement}_{\mathrm{Energy}}$ $\displaystyle=$
$\displaystyle
100\times\frac{E_{\mathrm{baseline}}-E_{\mathrm{optimized}}}{E_{\mathrm{baseline}}}$
(5)

where $T_{\mathrm{baseline}}$ and $T_{\mathrm{optimized}}$ are the execution
time of the baseline and optimized caches, respectively. In the same manner,
$E_{\mathrm{baseline}}$ and $E_{\mathrm{optimized}}$ are the energy computed
for baseline and optimized caches, respectively.

Figure 11: Pareto front execution time with respect to the baseline configuration (labels represent the percentage of improvement in execution time). Each color represents one point in the non-dominated front. For example, unepic has 4 points, whereas pegwitdec has one single point. Figure 12: Pareto front energy consumption with respect to the baseline configuration (labels represent the percentage of improvement in energy consumption). Each color represents one point in the non-dominated front, as in Figure 11. Application | Execution Time | Energy Consumption
---|---|---
epic | 62.79 | 90.85
unepic | 60.74 | 89.75
gsmdec | 63.12 | 91.48
gsmenc | 63.21 | 91.52
pegwitdec | 60.09 | 92.43
pegwitenc | 59.74 | 92.55
cjpeg | 87.23 | 96.68
djpeg | 62.37 | 89.44
mpegdec | 63.45 | 91.68
mpegenc | 63.28 | 90.56
rawcaudio | 63.59 | 91.68
rawdaudio | 63.58 | 91.68
Average | 64.43 | 91.69
Table 4: Percentage of improvement, averaged for each Pareto front and single
objective vs. baseline cache configuration.

Figures 11 and 12 show the level of improvement computed for each point in the
Pareto fronts obtained for all the 12 target applications. Figure 11 depicts
the percentage of improvement in execution time, whereas Figure 12 depicts the
level of improvement in energy consumption. As can be seen, our approach
achieves a significant improvement in both objectives. In this regard, Table 4
shows these improvements averaged over each Pareto front, and their averages
in the last row. Our optimization method is able to reach cache configurations
which are, in average, a 64.43% and 91.69% better in execution time and
energy, respectively. To better understand this high improvement, we must
compare the baseline configuration with, for example, the optimized cache
configuration shown in Figure 10. Firstly, the baseline configuration has a 16
bytes block size, whereas the optimized configuration has an 8 bytes block
size. Moving 16 bytes from main memory to cache memory consumes more energy
than moving 8 bytes. Secondly, the baseline configuration has 64 ways versus
the 4 ways of the optimized version. It means that the baseline configuration
is much more associative and then finding the desired block spends much more
time and energy, since each label must be compared 64 times against 4.
Finally, the prefetch policy of the baseline instructions cache configuration
is “ON-DEMAND”, whereas in the optimized cache is “ALWAYS”. Instructions are
usually loaded from consecutive memory addresses (discarding branch
instructions), and thus, the “ON-DEMAND” prefetch policy will consume more
time and energy than the optimized “ALWAYS” prefetch policy [2].

Regarding the convergence of the optimization process, Table 5 shows a summary
of the evolution for both objectives. Column labeled as INI represents the
level of improvement for each objective averaged over the initial random
population. Column labeled as END represents the same values averaged over the
final population. Column AVG shows averaged improvements for each objective
and over all the generations and individuals, from INI to END. As Table 5
shows, NSGA-II easily improves the performance of the baseline cache even
after the first generation. The same does not happen in energy, where after
the first generation, only in the case of cjpeg NSGA-II is able to improve the
energy consumption of the baseline cache. Fortunately, after 3-4 generations,
NSGA-II quickly find cache configurations that improve the baseline cache in
both performance and energy. Surprisingly, the improvement in energy, which
started with worst values, quickly grows up and reach much better values than
the improvement in execution time (up to $97\%$ in the case of cjpeg). In
summary, Table 5 demonstrates that our optimization methodology, even when
starting from bad initial solutions, is able to reach high levels of
improvement with respect to a baseline configuration.

Application | Execution Time | Energy Consumption
---|---|---
INI | AVG | END | INI | AVG | END
epic | 11.40 | 57.04 | 63.11 | -71.42 | 77.56 | 91.71
unepic | 12.55 | 54.97 | 61.80 | -95.27 | 75.79 | 91.74
cjpeg | 66.13 | 85.01 | 87.51 | 48.03 | 91.77 | 97.25
djpeg | 12.88 | 55.26 | 62.77 | -69.11 | 74.77 | 91.91
gsmdec | 1.25 | 53.37 | 63.52 | -97.14 | 77,22 | 93,19
gsmenc | 4.46 | 55.01 | 63.65 | -71.97 | 77.58 | 93.20
rawcaudio | 12.63 | 57.27 | 63.59 | -80.69 | 76.90 | 91.68
rawdaudio | 10.27 | 57.50 | 63.58 | -60.05 | 77.95 | 91.68
mpegdec | 2.18 | 57.17 | 63.45 | -105.70 | 76.63 | 91.68
mpegenc | 4.02 | 57.08 | 63.37 | -66.60 | 76.97 | 91.74
pegwitdec | -1.02 | 51.56 | 60.09 | -146.23 | 73.00 | 92.46
pegwitenc | 12.07 | 51.03 | 59.74 | -161.10 | 71.76 | 92.55
Table 5: Improvement percentages: initial, average and final improvements per
application vs. the baseline configuration.

###  6.4 Validation with two additional baseline cache

To validate our optimization framework, we have optimized the cache memory of
two additional different hardware platforms included in some Apple devices of
the family of SoC Apple AX, like iPhone 5, iPhone 5s, iPad 2, iPod-touch or
iApple-TV. Apple AX series integrate the ARM processors family, for instance
Cortex-A9 (iPad 2, iPod-touch or iApple-TV) or Cortex-A15 (iPhone 5, iPhone
5s). According to this, these two new cache configurations are:

  * Baseline 2

: Cache size: 32 KB; Block size: 64; Associativity: 4; Replacement algorithm:
RANDOM: Prefetch policy: ALWAYS; Write policy (DCache): COPY-BACK;

  * Baseline 3

: Cache size: 32 KB; Block size: 64; Associativity: 2; Replacement algorithm:
LRU: Prefetch policy: ALWAYS; Write policy (DCache): COPY-BACK;

Application | Baseline 2 | Baseline 3
---|---|---
ExTime% | Energy% | ExTime% | Energy%
epic | 19.80 | 87.60 | 11.77 | 88.66
unepic | 9.73 | 87.28 | 1.05 | 88.34
gsmdec | 23.97 | 89.35 | 16.98 | 90.27
gsmenc | 24.18 | 89.51 | 16.98 | 90.37
pegwitdec | 34.26 | 92.25 | 28.12 | 92.72
pegwitenc | 35.42 | 92.61 | 29.49 | 93.05
cjpeg | 21.11 | 87.98 | 13.11 | 88.98
djpeg | 27.38 | 88.74 | 21.01 | 89.93
mpegdec | 24.80 | 88.01 | 18.61 | 89.42
mpegenc | 22.20 | 87.65 | 14.32 | 88.70
rawcaudio | 22.80 | 87.97 | 14.68 | 88.92
rawdaudio | 24.13 | 87.81 | 16.14 | 88.77
Average | 24.15 | 88.90 | 16.85 | 89.84
Table 6: Percentage of improvement for the best cache configuration obtained
vs. new baselines chosen.

We have repeated the process for the two additional baselines, computing the
percentage of improvement obtained in the comparison of each baseline cache
memory with the best cache configuration obtained by the optimization
framework. Table 6 shows the percentages obtained, in execution time and
energy consumption. It is worth noting that whereas the energy savings are
still similar to Baseline 1 (close to 90%), the improvement in execution time
is decreased (from 64% to 24% and 17%, respectively). These differences are
given to the nature of the MediaBench benchmark and each specific baseline
architecture. The first baseline, a Car GPS device, is oriented to a very
specific navigation application, completely different in nature to MediaBench.
It explains the high level of optimization in both execution time and energy.
On the other hand, baselines 2 and 3 are general-purpose devices, and their
cache memories are oriented to a wide range of different block sizes. It is
translated into a low associativity but a big size, or in other words, better
execution time but more energy, which explains the low level of improvement in
execution time versus the high level of improvement in energy.

###  6.5 On the performance of the optimization framework

Finally, with respect to the execution time of the optimization process, our
master-worker architecture computed optimized cache configurations in an
averaged wall-clock time of 10 hours (0.42 days) per application. The
optimization of the set of 12 applications was performed in 5 days. Taking
into account that the averaged time used by our simulation framework to
evaluate one single cache configuration is equal to 13 seconds, an exhaustive
optimization algorithm would take almost 10 days to find the Pareto optimal
front for one single application, and 117 days to reach the set of 12 Pareto
optimal fronts. As a result, a parallel master-worker NSGAII algorithm obtain
excellent solutions (64.43% and 91.69% better in execution time and energy,
respectively) with a difference of more than three months, obtaining a speed-
up of 23.4 with respect to the exhaustive algorithm.

##  7 Conclusion and future work

Current multimedia embedded devices like smartphones, video players, etc. are
highly constrained from battery lifetime and performance. Cache memories are
added to these devices in order to improve performance. However, the selection
of the best cache configuration for each embedded system is a hard task
because of the large space of possible cache configurations. Several design
techniques have been proposed for years in order to facilitate the search of
the best cache configuration for different applications.

In this paper, we have presented a novel technique based on static profiling
and multi-objective optimization to find the best cache configuration for a
given target embedded system and a target set of applications. The process has
been divided in two phases: the first one is responsible for obtaining the
program traces and parameters needed to characterize the set of candidate
cache configurations. The second phase applies multi-objective evolutionary
algorithm, using NSGA-II and Dinero IV, to evaluate each application under the
candidate set of cache configurations.

The result of the optimization is a set of cache configurations that minimizes
execution time and energy consumption for each application. Therefore, this
improves the performance and increases the lifetime of both batteries and
devices. Taking a cache configuration commonly used in current multimedia
systems as a baseline, experimental results show an average improvement of
$64.43\%$ and $91.69\%$ in execution time and energy consumption,
respectively.

Our methodology still needs human decisions to select the final cache memory,
the best possible for the whole set of applications. We have seen that this is
not a difficult task. However, as our future work, we are already extending
this methodology to allow us the automatic optimization of all the target
applications at a time. This will require a greater parallelization degree of
the evaluation process and the design of a new accurate multi-objective
function, incorporating for instance fuzzy decisions to reduce the number of
objectives from $12~{}\mathrm{applications}\times 2~{}\mathrm{objectives}$ to
two or three objectives.

## Acknowledgment

This work has been partly funded by the Spanish Ministry of Economy and
Competitivity under research grants TIN2014-54806-R and TIN2014-56494-C4-2-P.

## References

  * [1] M. T. Kandemir, Reducing energy consumption of multiprocessor soc architectures by exploiting memory bank locality, ACM Trans. Des. Autom. Electron. Syst. 11 (2) (2006) 410–441.  doi:10.1145/1142155.1142163.
URL http://doi.acm.org/10.1145/1142155.1142163

  * [2] J. L. Hennessy, D. A. Patterson, Computer Architecture: A Quantitative Approach, Morgan Kaufmann, 2011.
  * [3] Y. Cai, M. Schmitz, A. Ejlali, B. Al-Hashimi, S. Reddy, Cache size selection for performance, energy and reliability of time-constrained systems, in: Design Automation, 2006. Asia and South Pacific Conference on, 2006, pp. 6 pp.–.  doi:10.1109/ASPDAC.2006.1594804.
  * [4] H. Mahmood, M. Poncino, E. Macii, Cache aging reduction with improved performance using dynamically re-sizable cache, in: Proceedings of the Conference on Design, Automation & Test in Europe, DATE ’14, European Design and Automation Association, 3001 Leuven, Belgium, Belgium, 2014, pp. 174:1–174:6.
URL http://dl.acm.org/citation.cfm?id=2616606.2616821

  * [5] K. Deb, Multi-Objective Optimization Using Evolutionary Algorithms, Wiley, 2009\.
  * [6] K. Deb, A. Pratap, S. Agarwal, T. Meyarivan, A fast and elitist multiobjective genetic algorithm: Nsga-ii, Evolutionary Computation, IEEE Transactions on 6 (2) (2002) 182–197.  doi:10.1109/4235.996017.
  * [7] C. Lee, M. Potkonjak, W. H. Mangione-Smith, Mediabench: a tool for evaluating and synthesizing multimedia and communicatons systems, in: Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, MICRO 30, IEEE Computer Society, Washington, DC, USA, 1997, pp. 330–335.
URL http://dl.acm.org/citation.cfm?id=266800.266832

  * [8] A. Ltd., ARM920T Technical Reference Manual,
http://infocenter.arm.com/help/topic/com.arm.doc.ddi0151c/ARM920T_TRM1_S.pdf
(2013).

  * [9] T. Givargis, Zero cost indexing for improved processor cache performance, ACM Trans. Des. Autom. Electron. Syst. 11 (1) (2006) 3–25.  doi:10.1145/1124713.1124715.
URL http://doi.acm.org/10.1145/1124713.1124715

  * [10] W. Zang, A. Gordon-Ross, A survey on cache tuning from a power/energy perspective, ACM Comput. Surv. 45 (3) (2013) 32:1–32:49.  doi:10.1145/2480741.2480749.
URL http://doi.acm.org/10.1145/2480741.2480749

  * [11] L. Chen, X. Zou, J. Lei, Z. Liu, Dynamically reconfigurable cache for low-power embedded system, in: Natural Computation, 2007. ICNC 2007. Third International Conference on, Vol. 5, 2007, pp. 180 –184.  doi:10.1109/ICNC.2007.346.
  * [12] A. Gordon-Ross, F. Vahid, A self-tuning configurable cache, in: Proceedings of the 44th annual Design Automation Conference, DAC ’07, ACM, New York, NY, USA, 2007, pp. 234–237.  doi:10.1145/1278480.1278537.
URL http://doi.acm.org/10.1145/1278480.1278537

  * [13] S. Lopez, S. Dropsho, D. Albonesi, O. Garnica, J. Lanchares, Rate-driven control of resizable caches for highly threaded smt processors, in: Parallel Architecture and Compilation Techniques, 2007. PACT 2007. 16th International Conference on, 2007, pp. 416–416.  doi:10.1109/PACT.2007.4336244.
  * [14] D. S. Gracia, A. Ferrerón, L. M. D. Campo, T. M. Arnal, V. V. n. Yúfera, Revisiting lp-nuca energy consumption: Cache access policies and adaptive block dropping, ACM Trans. Archit. Code Optim. 11 (2) (2014) 19:1–19:26.  doi:10.1145/2632217.
URL http://doi.acm.org/10.1145/2632217

  * [15] W. Wang, P. Mishra, Dynamic reconfiguration of two-level caches in soft real-time embedded systems, in: VLSI, 2009. ISVLSI ’09. IEEE Computer Society Annual Symposium on, 2009, pp. 145–150.  doi:10.1109/ISVLSI.2009.22.
  * [16] W. Wang, P. Mishra, S. Ranka, Dynamic cache reconfiguration and partitioning for energy optimization in real-time multi-core systems, in: Proceedings of the 48th Design Automation Conference, DAC ’11, ACM, New York, NY, USA, 2011, pp. 948–953.  doi:10.1145/2024724.2024935.
URL http://doi.acm.org/10.1145/2024724.2024935

  * [17] W. Wang, P. Mishra, A. Gordon-Ross, Dynamic cache reconfiguration for soft real-time systems, ACM Trans. Embed. Comput. Syst. 11 (2) (2012) 28:1–28:31.  doi:10.1145/2220336.2220340.
URL http://doi.acm.org/10.1145/2220336.2220340

  * [18] R. Reddy, P. Petrov, Cache partitioning for energy-efficient and interference-free embedded multitasking, ACM Trans. Embed. Comput. Syst. 9 (3) (2010) 16:1–16:35.  doi:10.1145/1698772.1698774.
URL http://doi.acm.org/10.1145/1698772.1698774

  * [19] D. Andrade, B. B. Fraguela, R. Doallo, Precise automatable analytical modeling of the cache behavior of codes with indirections, ACM Trans. Archit. Code Optim. 4 (3) (Sep. 2007).  doi:10.1145/1275937.1275940.
URL http://doi.acm.org/10.1145/1275937.1275940

  * [20] M. Feng, C. Tian, C. Lin, R. Gupta, Dynamic access distance driven cache replacement, ACM Trans. Archit. Code Optim. 8 (3) (2011) 14:1–14:30.  doi:10.1145/2019608.2019613.
URL http://doi.acm.org/10.1145/2019608.2019613

  * [21] T. Xingyan, D. Hongyan, Static cache hint generation based on a profile of the opt cache replacement, in: Computer Application and System Modeling (ICCASM), 2010 International Conference on, Vol. 9, 2010, pp. V9–84–V9–87.  doi:10.1109/ICCASM.2010.5623081.
  * [22] A. Gordon-Ross, F. Vahid, N. Dutt, Combining code reordering and cache configuration, ACM Trans. Embed. Comput. Syst. 11 (4) (2013) 88:1–88:20.  doi:10.1145/2362336.2399177.
URL http://doi.acm.org/10.1145/2362336.2399177

  * [23] J. L. Risco-Martín, D. Atienza, J. Hidalgo, J. Lanchares, A parallel evolutionary algorithm to optimize dynamic data types in embedded systems, Soft Computing 12 (12) (2008) 1157–1167.  doi:10.1007/s00500-008-0295-y.
URL http://dx.doi.org/10.1007/s00500-008-0295-y

  * [24] J. Díaz, J. I. Hidalgo, F. Fernández, O. Garnica, S. López, Improving smt performance: an application of genetic algorithms to configure resizable caches, in: Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference: Late Breaking Papers, GECCO ’09, ACM, New York, NY, USA, 2009, pp. 2029–2034.  doi:10.1145/1570256.1570271.
URL http://doi.acm.org/10.1145/1570256.1570271

  * [25] B. Bui, M. Caccamo, L. Sha, J. Martinez, Impact of cache partitioning on multi-tasking real time embedded systems, in: Embedded and Real-Time Computing Systems and Applications, 2008. RTCSA ’08. 14th IEEE International Conference on, 2008, pp. 101–110.  doi:10.1109/RTCSA.2008.42.
  * [26] A. Silva-Filho, C. Bastos-Filho, D. Falcao, F. Cordeiro, R. Castro, An optimization mechanism intended for two-level cache hierarchy to improve energy and performance using the nsgaii algorithm, in: Computer Architecture and High Performance Computing, 2008. SBAC-PAD ’08. 20th International Symposium on, 2008, pp. 19 –26.  doi:10.1109/SBAC-PAD.2008.9.
  * [27] A. Janapsatya, A. Ignjatovic, S. Parameswaran, Finding optimal l1 cache configuration for embedded systems, in: Design Automation, 2006. Asia and South Pacific Conference on, 2006, p. 6 pp.  doi:10.1109/ASPDAC.2006.1594783.
  * [28] M. Mamidipaka, N. Dutt, eCACTI: An enhanced power estimation model for on-chip caches, Tech. Rep. TR-04-28, CECS, UC Irvine (2004).
  * [29] D. Burger, T.M.Austin, The simplescalar tool set, version 2.0., in: Technical Report, University of Wisconsin-Madison, 1997, pp. CS–TR–97–1342.
  * [30] J. L. Risco-Martín, J. M. Colmenar, Java Evolutionary COmputation library (JECO), Available at: https://sourceforge.net/projects/jeco (2013).
  * [31] J. Edler, M. D. Hill, Dinero iv trace-driven uniprocessor cache simulator”, 2014.
URL http://www.cs.wisc.edu/~markhill/DineroIV/

  * [32] A. Sayyad, H. Ammar, Pareto-optimal search-based software engineering (posbse): A literature survey, in: Realizing Artificial Intelligence Synergies in Software Engineering (RAISE), 2013 2nd International Workshop on, 2013, pp. 21–27.  doi:10.1109/RAISE.2013.6615200.
  * [33] L. N. Chakrapani, J. Gyllenhaal, W. mei W. Hwu, S. A. Mahlke4, K. V. Palem1, R. M. Rabbah5, Trimaran: An infrastructure for research in instruction-level parallelism, 2005.
URL http://www.trimaran.org/

##  Appendix A Multi-objective optimization and hypervolume indicator

###  A.1 Multi-objective optimization

Multi-objective optimization aims at simultaneously optimizing several
contradictory objectives. For such kind of problems, a single optimal solution
does not exist, and compromises have to be made. Thus, without any loss of
generality, we can assume the following formulation of the m-objective
minimization problem:

$\displaystyle\mathrm{Minimize}$
$\displaystyle\mathbf{y}=\mathbf{f}(\mathbf{x})$ $\displaystyle=$
$\displaystyle[f_{1}(\mathbf{x}),f_{2}(\mathbf{x}),...,f_{m}(\mathbf{x})]$
$\displaystyle\mathrm{Subject~{}to}$ $\displaystyle\mathbf{x}$
$\displaystyle=$ $\displaystyle(x_{1},x_{2},\ldots,x_{n})\in\mathbf{X}$
$\displaystyle\mathbf{y}$ $\displaystyle=$
$\displaystyle(y_{1},y_{2},\ldots,y_{m})\in\mathbf{Y}$

where $\mathbf{x}$ is the vector of $n$ decision variables, $\mathbf{f}$ is
the vector of $m$ objectives function. $\mathbf{X}$ is the feasible region in
the decision space, and $\mathbf{Y}$ is the feasible region in the objectives
space. A solution $\mathbf{x_{1}}\in\mathbf{X}$ is said to dominate another
solution $\mathbf{x_{2}}\in\mathbf{X}$ (denoted as
$\mathbf{x_{1}}\prec\mathbf{x_{2}}$) if the following two conditions are
satisfied:

$\displaystyle\forall i\in{1,2,....,m}$ , $\displaystyle
f_{i}(\mathbf{x_{1}})\leq f_{i}(\mathbf{x_{2}})$ $\displaystyle\exists
j\in{1,2,....,m}$ , $\displaystyle
f_{j}(\mathbf{x_{1}})<f_{j}(\mathbf{x_{2}})$

If there is no solution which dominates $\mathbf{x}\in\mathbf{X}$,
$\mathbf{x}$ is said to be a non-dominated solution. The non-dominated set of
the entire feasible search space $\mathbf{X}$ is the _Pareto optimal set_. The
image of the Pareto optimal set in the objective space is the _Pareto optimal
front_ of the multi-objective problem at hand. Since several solutions may be
mapped to the same multi-objective function, the Pareto optimal front does not
necessarily contain as many elements as the Pareto optimal set. A multi-
objective optimization problem is solved, when its complete Pareto optimal set
is found. In practice, the number of Pareto optima is too large, or the
determination of a single Pareto optimum is NP hard [5]. Therefore, the aim is
usually to find a satisfactory Pareto set approximation (usually named Pareto
set, or Pareto front in the objective space), as close as possible to the
Pareto optimal set.

Figure 13: Illustration, in a two objective space, of the concepts of
dominance, Pareto optimal front, Pareto front, and hypervolume indicator. For
the last one, the objective vector (2.1,2.1) is taken as the reference point.

Figure 13 depicts an example of a Pareto optimal front (continuous curve), the
set of solutions obtained by a given optimization algorithm (black shaded and
non-shaded circles), the subset of non-dominated solutions (black shaded
circles) that form a Pareto front, and the subset of dominated solutions (non-
shaded circles). In the following, we show how to analyze the quality of a
obtained Pareto front using the hypervolume indicator.

###  A.2 Hypervolume indicator

The hypervolume indicator is a metric that calculates the volume (in the
objective space) covered by members of a non-dominated set of solutions $Q$
[5]. Let $v_{i}$ be the volume enclosed by solution $i\in Q$. Then, a union of
all hypercubes is found and its hypervolume ($I_{H}$) is calculated as:

$I_{H}(Q)=\bigcup_{1}^{\left|Q\right|}v_{i}$ (6)

The hypervolume of a set is measured relative to a reference point, usually
the anti-optimal point or “worst possible” point in space. We do not address
here the problem of choosing a reference point. If the anti-optimal point is
not known or does not exist one suggestion is to take, in each objective, the
worst value from any of the fronts being compared. In this work, we consider
the hypervolume difference to a reference set $R$, defined as

$I_{H}^{-}(Q)=I_{H}(R)-I_{H}(Q)$ (7)

where smaller values correspond to higher quality. Since the reference set is
not given, we take $I_{H}(R)=0$.

Figure 13 shows an example of how $I_{H}(Q)$ is computed using the reference
point $(2.1,2.1)$.