# A curated collection of COVID-19 online datasets

Isa Inuwa-Dutse Ioannis Korkontzelos
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

One of the defining moments of the year 2020 is the outbreak of Coronavirus
Disease (Covid-19), a deadly virus affecting the body’s respiratory system to
the point of needing a breathing aid via ventilators. As of June 21, 2020
there are 12,929,306 confirmed cases and 569,738 confirmed deaths across 216
countries, areas or territories. The scale of spread and impact of the
pandemic left many nations grappling with preventive and curative approaches.
The infamous lockdown measure introduced to mitigate the virus spread has
altered many aspects of our social routines in which demand for online-based
services skyrocketed. As the virus propagate, so does misinformation and fake
news around it via online social media, which seems to favour virality over
veracity. With a majority of the populace confined to their homes for a long
period, vulnerability to the toxic impact of online misinformation is high. A
case in point is the various myths and disinformation associated with the
Covid-19, which, if left unchecked, could lead to a catastrophic outcome and
hamper the fight against the virus.

While the scientific community is actively engaged in identifying the virus
treatment, there is a growing interest in combating the associated harmful
infodemic. To this end, researchers have been curating and documenting various
datasets about Covid-19. In line with existing studies, we provide an
expansive collection of curated datasets to support the fight against the
pandemic, especially concerning misinformation. The collection consists of 3
categories of Twitter data, information about standard practices from credible
sources and a chronicle of global situation reports. We describe how to
retrieve the hydrated version of the data and proffer some research problems
that could be addressed using the data.

###### keywords:

COVID-19, Coronavirus, SARS-CoV-2, Social Networks, Twitter Data, Covid-19
Datasets

##  1 Introduction

Since the beginning of 2020, the dominant issue for the public is the
coronavirus disease (COVID-19)111COVID-19 and Covid-19 are used
interchangeably in this work., which is caused by a new strain of
zoonotic222i.e. capable of being transmitted between animals and people
coronavirus (SARS-CoV-2), that was first reported by the World Health
Organisation (WHO) on December 31, 2019, in Wuhan, China. The latest update
from the WHO at the time of writing this paper reported 12,929,306 confirmed
cases and 569,738 confirmed deaths across 216 countries, areas or
territories333www.who.int/emergencies/diseases/novel-coronavirus-2019. As
cases for the Covid-19 increase, so does the associated infodemic. It can be
argued that the need for online-based services has never been in higher demand
as being witnessed in the Covid-19-induced lockdown era. In this technology-
driven society, online social networks support various forms of interactions
that play a crucial role in enabling global connectivity. Because various
aspects of our social lives have been affected during the pandemic with
substantial reliance on online-based services, people are more vulnerable to
misleading online information. While various credible bodies strive to contain
the outbreak with sound and cautious approaches, various misinformation and
fake news sources exist, playing a role in misleading the public. The
proliferation of misinformation and uncensored posts on social media
platforms444such as Twitter www.twitter.com and Facebook www.facebook.com are
being supported by a communication system that is focused on generating a huge
amount of data (virality) at the expenses of vitality. Despite the efforts to
curtail the spread of unsubstantiated claims, such as Twitter’s new feature of
flagging posts, it is still difficult to ascertain the veracity of the
information we consume. As a result, there is huge interest at various levels
to combat the pandemic.

While the scientific community is actively engaged in identifying a lasting
cure for the virus causing Covid-19, i.e. SARS-Cov-2, there is a growing
interest of the computer science research community in addressing the negative
impact of the corresponding infodemic. This opens up another frontier of
challenge in the fight against the virus in the form of misinformation, fake
news and unfounded claims. To this end, researchers have been curating and
documenting various datasets about Covid-19. We observe that there is limited
availability of curated ground-truth data that could be used to debunk myths
and misinformation around the pandemic. Moreover, the existing tweet-based
corpora, discussed in Section 1.1, need to comprise of various relevant
stakeholders. This paper aims at addressing this gap by making available
various datasets about Covid-19. The data collection555See
https://github.com/ijdutse/covid19-datasets for details. consists of 3
categories of Twitter data, information about standard practices from credible
sources and a chronicle of global situation reports from WHO. The central goal
of making these datasets available is to enable the study of how the spread of
misinformation and rumours could be mitigated. We describe how to retrieve the
hydrated version of the data and proffer some research problems that could be
addressed using the data.

###  1.1 Related Work

Within a short span of the outbreak, we have witnessed a plethora of
Covid-19-related studies covering various aspects of the pandemic. We provide
a cursory discussion on relevant studies and published datasets from online
social networks. The interested reader may refer to [1], which offers a review
of related studies and a comprehensive list of relevant datasets across
various domains. The earliest data in social networks about the virus can be
traced back to January 22, 2020 by [2]. The dataset consists of tweets
collected using some specific hashtags and credible accounts. The work of [3]
reported a collection of image-based data about Covid-19 from Instagram. To
understand the digital response in online social media, infodemics observatory
[4] documents a large collection of public messages666see
https://covid19obs.fbk.eu related to Covid-19. The data have been classified
and categorised accordingly with informative visualisations about the scale of
the pandemic. The work of [5] provides a large collection of Covid-19 datasets
in Arabic and details about Covid-19 related articles across Wikipedia
projects are being documented online777http://covid-data.wmflabs.org.
Recently, Twitter made available a dedicated Application Programming Interface
(API) that can be used to retrieve tweets related to Covid-19 [6].

The remaining of this paper is structured as follows: Section 2 presents a
detailed description of the data collection and processing. Section 3 offers
longitudinal and exploratory analyses of the data and proffer some research
problems worthy of investigation using the datasets. Section 4 concludes the
study and discusses some future work.

##  2 The Curated Datasets

One of the main goals of this study is to contribute diverse datasets to
support research on Covid-19 and related pandemics. Thus, the onus is on
identifying relevant stakeholders as the basis for the collection. Our
datasets can be divided into two broad classes according to their sources: the
tweet-based collection, consisting of three categories of selected tweets, and
the non-tweet collection, comprising of information about standard practices
from credible sources and a chronicle of global situation reports. Regarding
the first category, we collected Twitter data from both monitored and
unmonitored accounts using relevant terms within a period of 5 weeks: March 23
to May 13, 2020. Some of the data collection terms are captured in the
following regular expressions to pull out tweets of interest. For instance,
retrieving tweets matching all possible variations of referring to covid-19
using:

`(r’[Cc]ovid(?<=)\w+|[cC]orona[vV]irus|pandemic’)`

###  2.1 Tweet-based collection

The tweet-based collection contains tweet objects retrieved from Twitter via
the Twitter Standard Search API based on a set of relevant keywords, as shown
in Table 1. A tweet object is a complex data object composed of numerous
descriptive fields, which enables the extraction of various features for
further analysis. Based on the method that was used for collection, the tweet-
based data consist of the following data categories:

#### Account-based collection

Users on Twitter are broadly classified as verified or unverified. To prevent
fake users masquerading celebrities or other popular individuals, Twitter
performs a verification to authenticate users before appending the verified
label to the account handle. We monitored several accounts for a period of
five weeks and retrieved tweets related to the pandemic. More details about
the accounts that were monitored are shown in Table 1.

#### Random collection

This set consists of a generic collection of daily tweets spanning numerous
topics related to the pandemic collected via Twitter’s Streaming API. The
rationale is to capture a wide discussion topics surrounding the prevailing
pandemic. Owing to the huge amount of the retrieved tweets and noting how a
hashtag represents an umbrella covering many tweets related to a topic, we
retain only original posts associated with a relevant hashtag and we exclude
retweets in the collection. A tweet associated with a hashtag stands a better
chance of attracting much attention. This hashtag-based collection of tweets
may also contain tweets in languages other than English, which have at least
100 tweets related to the pandemic.

#### Miscellaneous collection

Noting the misinformation and myths surrounding the pandemic, we use terms
associated with such myths to collect the data, as shown in Table 1. This
category is motivated by the growing scepticism surrounding Covid-19. We
manually identify users who openly dismisses Covid-19 related information put
forward by credible sources such as the WHO. On that basis, each data is
categorised to reflect the inclination of the user based on the content and
its associated sentiment. We annotate the datasets by computing the sentiment
of the users associated with the posts. The data from WHO, dubbed proWHO, and
the antiWHO, dismissing WHO’s guidelines on combating Covid-19 pandemic, are
the two broad sub-categories under the miscellaneous collection that can be
used for various studies. Such studies could involve community detection and a
critical analysis of users perceptions about measures taken in curtailing the
pandemic.

###  2.2 Non-tweet collection

There is no gainsay that well-documented information about Covid-19 has been
and is still made publicly available. Such endeavour is work in progress as
new insights are being found. Consequently, we report a curated collection of
datasets from credible sources concerned with combating the pandemic. We focus
on the following sources: the World Health Organisation (WHO), UK’s National
Health Service (NHS-UK), the Nigeria Centre for Disease Control (NCDC-NG), and
USA’s Centre for Disease Control and Prevention (CDC-USA). The collection aims
to provide informative material for a robust factual analysis and broad scope
comparison. Through a combination of manual processing and web
scrapping888using the BeautifulSoup package, available at
www.crummy.com/software/BeautifulSoup, we obtain useful data from applicable
websites. The rationale of using these datasets is to expand the analysis
scope and enable researchers to find responses to a wide range of questions
related to Covid-19. While all the sources have similar content, the data from
the WHO consist of both standard practices999This ranges from debunking myths
to protective measures. and a chronicle of global situation reports.

Table 1: Summary of data collection sources and corresponding description Collection 1 |  Account-based collection
---|---
Data Source |  Twitter
Description |  Tweets from specific accounts collected via Twitter’s Standard Search API
Keywords |  @WHO, @DrTedros, @POTUS, @CDCgov, @ECDC_EU, @EU_Health, ECDC_Outbreaks, @WHO_Europe,@WhiteHouse, @HHSGov, @WHO_Africa, @NHSEngland, @NHSEnglandLDN, @officialkarimia, @metpoliceuk, @NCDCgov, @WHONigeria, @fmohnigeria, @PIBFactCheck, #HealthForAll, #COVID 19
Collection 2 |  Random collection
Data Source |  Twitter
Description |  tweets from random accounts collected via Twitter’s Streaming API
Keywords |  COVID-19, covid-19, corona virus,coronavirus, corona & Corona, pandemic, endemic, quarantine, global health, self isolate, symptoms, corona outbreak, disease, mental health, test result & social distance, sport, election politicians
Collection 3 |  Miscellaneous collection
Data Source |  Twitter
Description |  A wide range collection of covid-19 data and opposition to WHO’s stance
Keywords |  @Jordan_Sather_ , @kciparrish, CDC, 5G Network, broadband, Wuhan China, US military, US Military Wuhan, wash hands, garlic + coronavirus, mask, ventilators, Covid-19 + Bio-weapon, bio-weapon+covid-19, fennel cure, hydroxychloroquine, #COVID19; we query the following accounts as the seed users: @PlanB1975, @simondolan, @LonsdaleKeith, @angiebUK, @HotelLubyanka, @jcho710
Collection 4 |  Non-tweet-based collection
Data Source |  WHO, NHS-UK, NCDC-NGN, and CDC-US

The seed users in Table 1 were used to further identify users who share common
interest or opinion with the seed users. A survey of the accounts of the seed
users depicts an open dismissal of WHO’s guidance on combating the pandemic.

#### Getting the hydrated tweets

The full version of the tweet-based collections cannot be made available due
to Twitter’s policy on content redistribution101010see
https://developer.twitter.com/en/developer-terms/agreement-and-policy. Instead
of the full tweets, we provide the relevant IDs, that can be used to retrieve
the data, and some meta-information about each tweet111111The data presented
in this paper are available at https://github.com/ijdutse/covid19-datasets.
Moreover, we include a short Jupyter notebook with a description of how to
retrieve the hydrated data and how it can be transformed onto a usable format.
Alternatively, interested users may use the hydrator package [7].

##  3 Meta-analysis

This section presents some longitudinal and exploratory analyses of the data
including a pointer to relevant research problems worthy of investigation
using the datasets.

#### Data pre-processing

Due to the multifaceted nature of the datasets, we use the following approach
to transform them so that they all conform to a unified format for
redistribution. The tweet-based collections are messy and difficult to use
directly [8], hence the need for data cleaning. We carried out a rudimentary
cleaning process involving tokenisation, stopwords removal and text
formatting. To separate content words from function words and improve
analysis, we normalise each contracted term to its expanded version. Finally,
lemmatisation, the process of converting the inflected form of words back to
their base forms, is performed on the normalised content words.

Figure 1: Most of the common hashtags in the account-based collection relate
to sensitisation and provision of genuine information about preventing the
virus spread.

#### Popular accounts and hashtags

Figure 1 shows a timeline of popular tweets over time during the collection
period. The y-axis denotes the frequency of tweets and the x-axis denotes the
popular hashtags and the corresponding dates in the title. While some of the
hashtags are expected, many derogatory ones stand out in the miscellaneous
collection, as shown in Figure 3. With Figure 1 showing the popularity of the
sources or hashtags, many questions can be answered. For instance, how does
the online popularity corroborate with offline relevance? For the tweets
posted by the monitored accounts, in the account-based collection, we
determine its online presence by analysing the proportion of retweets,
favourite counts, statuses count follower/followee and sentiment121212We
extract sentiment using the VADER package, available at
https://pypi.org/project/vaderSentiment. associated with the texts.

#### Ranking Hashtags

Because of the prevalence of many related hashtags in the collection, as
demonstrated in Figure 1 and Figure 2, we retain only the most frequent ones
in the posts to enable a complete textual analysis. As a result, each tweet is
merged with its corresponding hashtag text and a form of synonym resolution is
performed on the hashtags. For instance #covid-19 and #CoronaVirus would be
similar after the resolution.

Figure 2: Common hashtags in the random collection

We apply Latent Semantic Analysis (LSA) [9, 10], a popular topic modelling
method, to analyse further the full context of tweets in the corpus and
hashtags ranking. Topic models such as the LSA and Latent Dirichlet Allocation
(LDA) [11] are widely used in various tasks involving texts [12, 13, 14]. The
set of original hashtags are compared with the output of the ranked hashtag
computed by the LSA and are replaced accordingly. For instance, since the LSA
produces a ranked subset of the most relevant hashtags from the original set,
we make a comparison and replace the set of hashtag with a single highly
ranked hashtag as the best representative of the set. For those without exact
representation, the first hashtag in the list is used. Figures 1, 2 and 3 show
some relevant hashtags in the tweet-based collection.

Figure 3: Common hashtags in the miscellaneous collection Figure 4: Sentiment
and lexical richness across tweet-based collections

#### Relevant Themes and Sentiments

To identify relevant themes, we begin by aggregating a finite collection of
textual content, $\mathcal{T}$, from each tweet-based collection to discover
relevant themes and to analyse lexically and for sentiment. For any given
stream of texts ${t_{1},....t_{n}}\in\mathcal{T}$, each $t_{i}\in\mathcal{T}$
consists of n-gram features131313$n$ is any positive integer, e.g. 1, 2 and 3
for unigrams, bigrams and trigrams, respectively. given by:
$f_{i1},...,f_{im}\in t_{i}\in\mathcal{T}$. Accordingly, we provide a summary
of the relevant themes or topics and the corresponding sentiment in Figures 5
to 7. Due to the high frequency of terms related to the pandemic, e.g.,
covid-19 and coronavirus, we remove such variations to avoid the extinction of
other relevant terms in the data. Alongside the themes, we present the
sentiment associated with the posts, reporting on different levels of polarity
– negative, neutral, positive and overall sentiment. Negative topics often
relate to reports about fatalities and confirmed cases. The positive
collection contains many instances about reported cases from different
regions, as shown in the word clouds141414Word cloud visualisation is based
on: https://github.com/amueller/word_cloud, in Figures 5 to 7).

Figure 5: Sample texts in the account-based collection. Figure 6: Sample texts
in the miscellaneous set. Figure 7: Sample negative terms across all
collections. The visualisation is based on the learned topics using the LSA.

#### Lexical Richness

With respect to the tweet-based collections, we analyse lexical richness to
understand the diversity of lexicons used across them. Our intuition is that
content irrelevant to Covid-19 will have be richer lexically, because the
narration and conspiracies surrounding the pandemic keep changing, hence
employing diverse wording in the discourse. On the other hand, content from
recognised sources, such as the WHO, would remain relatively consistent and
slow to change due to the formal process and other health-related protocols or
standard practices that apply before posting. Moreover, lexical richness can
be viewed as a measure of consistency in the narration about the pandemic. A
longitudinal analysis of the richness of content may provide a glimpse of what
is happening. Figure 4 shows both sentiment intensity, in the first three
subplots, and lexical richness, in the last sub-plot, across the tweet-based
collections. Indeed, the observed result confirmed our intuition, showing low
richness in the account-based collection, which contains tweets that mostly
come from credible sources (see Table 1). Figures 5, 6 and 7 show some
examples from the topic analysis in form of the most relevant terms in the
collections.

###  3.1 Utility of the datasets

In this section, we identify relevant areas and research problems that could
be studied using the datasets. The increasing number of uncensored posts,
partly due their short size and the speed of communication via posts on
virtually anything, facilitates the proliferation of content that affects the
credibility of information on social media. Despite the measures taken by
social media platforms to curtail irrelevant content, many sources of
misleading information and rumours still exist. Concerning the Covid-19
pandemic, there exist various misinformation and conspiracy sources capable of
misleading the public. We identify the following relevant areas and high-level
research problems that could be investigated using the datasets presented in
this work.

  * -

content classification: to distinguish genuine content in an ecosystem
cluttered with spurious content

  * -

content validation: the focus is to ascertain the veracity of a tweet or
document using a large collection of ground-truth data from credible sources.

  * -

tone of misinformation: of interest is to analyse the tone of misinformation
in comparison to the genuine counterparts – emotional, negative, neutral,
positive.

  * -

misinformation diffusion: to understand the propagation of news, virus
infection, rumour, fake news and unfounded claims. It would be worthwhile to
study the propagation of information related to the pandemic and study how to
optimise methods to ensure that relevant content dominates and irrelevant
content is suppressed.

  * -

thematic analysis: the use of a streaming API returns a huge collection of
somewhat irrelevant data. It would be useful to streamline the work to focus
on a fixed number of tweets from each account and then perform textual
analysis to understand the topics being discussed. It is worth noting that a
single tweet is usually limited in conveying sufficient information about a
topic, making it difficult to fully understand the discussion context. Future
work could be extended to understand the specific topics being discussed and
compare the degrees of similarity among documents.

  * -

evaluation of lockdown policy: It would be interesting to assess or gauge
users’ acceptance of lockdown measures. This would enable the quantification
of various lockdown policy measures. For instance, each lockdown measure ca be
associated to the sentiment of users. Furthermore, it would make sense to
track sentiment over time and see how attitude changes.

  * -

community detection: the miscellaneous collection consists of two broad
categories of users annotated as proWHO and antiWHO based on their
inclinations towards the pandemic. Because this is a high-level
categorisation, we postulate that many overlapping communities may exist. For
instance, the proWHO group may consists of users who dismisses the content
posted by the group. This is also true in the antiWHO group. The dataset can
be used for various studies such as community detection and an indepth
analysis of users’ perceptions about the pandemic.

##  4 Conclusion

The prevailing technological advancements culminated in the computerisation
and automation of various tasks, which leads to a complex ecosystem of
information exchange mostly via social media platforms. The architecture of
social media networks simplifies the spread of information to a wide audience
making it a useful facility for instant information update and socialisation;
this also results in an increasing number of uncensored posts on virtually
anything. The prevailing Covid-19 pandemic in the age of social media has
reveal to us that as the virus propagate, so is false or misleading
information about it leading to infodemic. A case in point is the various
myths associated with the Covid-19, which often left the public bewildered
concerning what preventive measures to take and which information to believe.
Misinformation about Covid-19 can be considered along the dimensions of the
origin of the virus, the symptoms, preventive measures and cure. The latter is
probably the most crucial since an ill-formed medical advice will be
catastrophic.

Because misleading information can have catastrophic consequences and hampers
the fight about applying containment measures, it is pertinent to combat the
pandemic from all possible fronts. Consequently, our work contributed a
curated collection of relevant datasets to support multi-faceted research
works interested in the Covid-19 infodemic and related tasks. We provide a
basic but useful analyses of the datasets and proffer direction/relevant areas
to study using them. The datasets from various credible sources can be used as
benchmark to assess the veracity of information related to the pandemic. The
data will further enrich existing databases for debunking misinformation and
fact-checking avenues, such as the International Fact-Checking
Network151515IFCN: www.poynter.org/ifcn and AFP161616AFP:
https://factcheck.afp.com. The datasets can help in understanding how to
optimise or ensure that relevant content dominates and irrelevant content is
suppressed, especially during critical times of the pandemic.

## Acknowledgements

The second author has participated in this research work as part of the TYPHON
Project, which has received funding from the European Union’s Horizon 2020
Research and Innovation Programme under grant agreement No. 780251.

## References

  * [1] Siddique Latif, Muhammad Usman, Sanaullah Manzoor, Waleed Iqbal, Junaid Qadir, Gareth Tyson, Ignacio Castro, Adeel Razi, Maged N Kamel Boulos, Adrian Weller, et al.  Leveraging data science to combat covid-19: A comprehensive review.  TechRxiv, 2020.
  * [2] Emily Chen, Kristina Lerman, and Emilio Ferrara.  Covid-19: The first public coronavirus twitter dataset.  arXiv preprint arXiv:2003.07372, 2020.
  * [3] Koosha Zarei, Reza Farahbakhsh, Noel Crespi, and Gareth Tyson.  A first instagram dataset on covid-19.  arXiv preprint arXiv:2004.12226, 2020.
  * [4] Gallotti R, Castaldo N, Valle F, Sacco P, and De Domenico M.  Covid19 infodemics observatory.  DOI: 10.17605/OSF.IO/N6UPX, 2020.
  * [5] Sarah Alqurashi, Ahmad Alhindi, and Eisa Alanazi.  Large arabic twitter dataset on covid-19.  arXiv preprint arXiv:2004.04315, 2020.
  * [6] Twitter.  Covid-19 stream.  https://developer.twitter.com/en/docs/labs/covid19-stream/overview, 2020\.
  * [7] Hydrator [Computer Software].  Documenting the now.  https://github.com/docnow/hydrator, 2020.
  * [8] Isa Inuwa-Dutse, Mark Liptrott, and Ioannis Korkontzelos.  Detection of spam-posting accounts on twitter.  Neurocomputing, 315:496–511, 2018.
  * [9] Peter Wiemer-Hastings, K Wiemer-Hastings, and A Graesser.  Latent semantic analysis.  In Proceedings of the 16th international joint conference on Artificial intelligence, pages 1–14. Citeseer, 2004.
  * [10] Nathan Halko, Per-Gunnar Martinsson, and Joel A Tropp.  Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions.  SIAM review, 53(2):217–288, 2011.
  * [11] David M Blei, Andrew Y Ng, and Michael I Jordan.  Latent dirichlet allocation.  Journal of machine Learning research, 3(Jan):993–1022, 2003.
  * [12] Edoardo M Airoldi, David M Blei, Stephen E Fienberg, and Eric P Xing.  Mixed membership stochastic blockmodels.  Journal of machine learning research, 9(Sep):1981–2014, 2008.
  * [13] Xiaohui Yan, Jiafeng Guo, Yanyan Lan, and Xueqi Cheng.  A biterm topic model for short texts.  In Proceedings of the 22nd international conference on World Wide Web, pages 1445–1456. ACM, 2013.
  * [14] Pan Yali, Yin Jian, Liu Shaopeng, and Li Jing.  A biterm-based dirichlet process topic model for short texts.  In 3rd International Conference on Computer Science and Service System. Atlantis Press, 2014.


∎

11institutetext: Josefa Díaz Álvarez 22institutetext: Centro Universitario de
Mérida, Universidad de Extremadura, 06800 Mérida, Spain
Tel.: +34-924-387268
22email<EMAIL_ADDRESS>33institutetext: J. Manuel Colmenar 44institutetext:
Dept. of Computer Science and Statistics, Universidad Rey Juan Carlos, 28933
Móstoles, Spain
44email<EMAIL_ADDRESS>
55institutetext: José L. Risco-Martín 66institutetext: Juan Lanchares
77institutetext: Óscar Garnica 88institutetext: Dept. of Computer Architecture
and Automation, Universidad Complutense de Madrid, 28040 Madrid, Spain
88email<EMAIL_ADDRESS>

# Optimizing L1 Cache for Embedded Systems through Grammatical Evolution

Josefa Díaz Álvarez  J. Manuel Colmenar  José L. Risco-Martín  Juan Lanchares
Oscar Garnica

(Received: date / Accepted: date)

###### Abstract

Nowadays, embedded systems are provided with cache memories that are large
enough to influence in both performance and energy consumption as never
occurred before in this kind of systems. In addition, the cache memory system
has been identified as a component that improves those metrics by adapting its
configuration according to the memory access patterns of the applications
being run. However, given that cache memories have many parameters which may
be set to a high number of different values, designers face to a wide and
time-consuming exploration space.

In this paper we propose an optimization framework based on Grammatical
Evolution (GE) which is able to efficiently find the best cache configurations
for a given set of benchmark applications. This metaheuristic allows an
important reduction of the optimization runtime obtaining good results in a
low number of generations. Besides, this reduction is also increased due to
the efficient storage of evaluated caches. Moreover, we selected GE because
the plasticity of the grammar eases the creation of phenotypes that form the
call to the cache simulator required for the evaluation of the different
configurations.

Experimental results for the Mediabench suite show that our proposal is able
to find cache configurations that obtain an average improvement of $62\%$
versus a real world baseline configuration.

##  1 Introduction

Embedded computing systems have experienced a great development in last
decades, becoming one of the crucial driving forces in technology. Portable
devices such as smartphones, digital cameras, GPS, etc. are constantly
incorporating new functionalities. Most of these new features are devoted to
support new services and multimedia applications, despite that embedded
systems have limited resources. Portable systems, for instance, run on
batteries, which are limited in capacity and size, because of design
constraints. Moreover, they have a limited cooling ability and, hence, a low
energy consumption is a main requirement. Besides, portable systems usually
execute multimedia applications, which require high performance and,
therefore, are energy intensive tasks. As a consequence, one of the main
workforces of embedded systems designers is the search for the right balance
between increasing performance and reducing energy consumption at a low cost.

Previous studies have identified on-chip cache memory as one of the most
energy consuming components, ranging between $20\%$ and $30\%$ of the total
power of the chip in embedded processors Varma05 . In addition, the design of
the cache memory has a high influence on energy consumption and performance,
because of the different hardware complexity that it implies. For instance, a
direct mapped cache design presents the fastest hit times, but requires higher
cache size to obtain comparable performance than an $N$-way set associative
cache. On the other hand, set associative caches present higher energy
consumption given that they access to a set of $N$ tags on each operation
Hennessy2011 .

The cache memory behavior is not only conditioned by structural parameters
(capacity, block size, associativity, etc.), but also by parameters such as
algorithms for search, prefetch and replacement, write policies, etc. All
these features form the so-called cache configuration. Finding optimal values
for these parameters will bring us the best performance and energy consumption
and consequently, the best cache configuration.

Besides, applications have different behavior and hence have distinct cache
requirements to meet the specific objectives of energy consumption and
performance. Thus, we need to take into account the behavior of the target
application in order to find the best cache configuration that improves
performance or energy consumption.

In summary, an optimization scheme to determine the best cache configuration
should: (1) travel along the design space of cache configurations, which is
defined as the set of all combinations of values for all cache parameters; (2)
take into account the energy and performance of target applications for each
candidate cache configuration, because of different memory access patterns.

The evaluation of a cache configuration requires a cache simulator to process
a trace of the cache accesses from a previous execution of the target program.
This process will allow to calculate the execution time and energy consumption
for the application under study. This is a slow process because program traces
usually record billions of memory operations, which spends tens of seconds of
simulator runtime. Hence an exhaustive search on this design space will take
an unaffordable amount of time given the high number of cache configurations
that can be defined.

On the other hand, heuristic techniques reduce the number of evaluations while
performing the search towards the optimal and, therefore, fit well in this
kind of problems. Therefore, we present in this paper an optimization scheme
based on Grammatical Evolution (GE) Dempsey2009  that obtains, using program
traces, the optimized cache configuration in terms of execution time and
energy consumption for a given target application. Compared with the
exhaustive approach, the execution time is highly reduced due to two reasons:
(1) the metaheuristic algorithm converges even with a short number of
generations and population size; (2) we have added a hashed map to store the
objective values of each evaluated cache. In addition, the plasticity of the
grammar in GE help us to generate the parameters that the cache simulator call
requires for each evaluation, making more easy to communicate it with the
optimization algorithm.

In order to test our proposal, we have run experiments that find the best
cache configuration for a set of multimedia applications taken from the
Mediabench benchmarks mediabench , since they are representative for image,
audio and video processing, which are typical applications of embedded
systems. We have assumed in these experiments a hardware architecture based on
the ARM9 processors family ARM9 , broadly used in multimedia embedded devices.
As will be shown later, the average reduction of execution time and energy
consumption of the optimized cache configurations is $75\%$ and $96\%$
respectively in relation to a baseline cache. In addition, the optimization
runtime is affordable and we have estimated an average reduction of $94\%$ in
relation to a GE implementation with no storage of evaluations.

The rest of the paper is organized as follows. Section 2 describes the main
issues about cache design and defines the search space of the problem. Section
3 reviews the related work on the cache optimization techniques. Section 4
describe both performance and energy models adopted in this work to compute
the goodness of the candidate solutions. Section 5 describes the whole
optimization framework, detailing the off-line processes as well as the
Grammatical Evolution we manage. Then, Section 6 analyzes our experimental
results. Finally, Section 7 draws conclusions and future work.

##  2 Cache design and search space

In order to clarify the scope of the problem under study, we devote this
section to introduce some cache design concepts and related issues to be
addressed. These concepts will also help us determine the size of the search
space.

Firstly, it must be noticed that there exist diferent design features, also
named design parameters, that need to be tuned in order to decide a cache
configuration. The values given to those parameters influence on the cache
behavior in both execution time and energy consumption. However, those
parameters may be different depending on the processor where the cache will be
included.

In this regard, we first have to decide which type of cache to select for this
work. Taking into account that we focus our approach on embedded systems, we
have selected the cache of the ARM9 processors family ARM9 .

ARM processors, because of their low power consumption and cost, have a
prevalent position in the market of portable devices and they are widespread
on multimedia embedded devices. In fact, the Apple A7, A8 and A8X processors
included in the popular iPhone 5S, iPhone 6 and iPad Air 2 do implement the
ARMv8-A instruction set.

In addition, the ARM9 processors family is present in devices such as game
consoles (GP32, Nintendo DS), calculators (HP 49/50), mobile phones (HTC TyTN,
K and W series of Sony Ericsson) and car GPS (Samsung S3C2410), for example.

Processors belonging to this family allow the installation of a cache memory
with sizes between 4 KB and 128 KB. For instance, the ARM920T, ARM922T and
ARM940T processors (ARM9TDMI family) implement a separated 16KB, 8KB and 4KB
instruction and data cache, respectively. Although revisions on ARM9E family
allow sizes up to 1MB, such as the ARM946E-S processor.

Given that the separation into data and instruction caches is common in the
more recent ARM9 processors, we do consider this two-caches approach in our
work.

Hence, the cache parameters that can be tuned in the instruction and data
caches of this processor are the following: cache size, line size, replacement
algorithm, associativity and prefetch algorithm for both the instruction and
data caches, and also write policy for data cache. Here, cache size is the
memory cache capacity in bytes, block size represents the amount of data read
or written in each cache access, replacement algorithm is in charge of taking
the decision to evict a block from cache memory, and prefetch algorithm
decides how blocks are carried to the cache memory. Finally, the write policy
decides when data stored in the cache shall be written to main memory, and it
only affects the data cache.

In brief, the problem we address consists on selecting the values for the
cache parameters that optimize the execution time and energy consumption of a
given application. Therefore, the search space is formed by all the
combinations of different values for each one of the cache parameters. Thus,
in our target system, a cache configuration is formed by 11 parameters: 5 for
the instructions cache and 6 for the data cache. According to the typical
cache configurations of embedded systems, we selected a range of permitted
values for each parameter, which are shown in Figure 1.

For instructions cache (I-Cache), memory size may take 8 different values
ranging between 512 bytes and 64 KB, block size can take 4 different values, 3
replacement algorithms and 3 prefetch algorithms may be selected, and 8
associativities are available. This results in $2304$ possible configurations
for instructions cache.

Data cache (D-Cache) have the same parameters as instructions cache, but
adding the 2 possible write policies. Hence, $4608$ possible data cache
configurations can be selected.

Figure 1: Cache configuration parameters. Both instruction and data caches
must be customized with available values.

Thus, considering all the possible combinations of both caches, the size of
the search space is $2304\times 4608=10616832$ configurations. However, some
of the constraints are related to infeasible parameters combinations. For
example, a cache configuration of 512B, 64-ways set associative with 32 bytes
block size is not feasible. Then, if this combination is selected for
instruction or data caches, it shall be invalidated by any optimization
algorithm.

##  3 Related work

It is well proven that the cache memory is a component that plays a crucial
role to improve performance and energy consumption. In recent decades, many
researchers have focused their work on improving different characteristics of
the cache memory. Several optimization approaches have been addressed to
increase performance and/or reduce energy consumption, develop simulation and
evaluation tools, etc. Next, we analyze some of the works related to our
proposal that we have separted into two different cathegories: (1) works that
deal with cache reconfiguration, and (2) works based on evolutionary
techniques.

###  3.1 Cache reconfiguration

One of the main goals for years has been to configure the cache memory
according to the running workload, in order to mainly improve performance
and/or energy consumption. This requires both hardware support for cache
reconfiguration, and algorithms to decide the proper values of the parameters
that obtain the best performance taking into account the running application.
In this way, many research works have analyzed cache memory parameters and
proposed new reconfiguration techniques from different points of view.

Naz et al. Naz-2005  proposed a design with split data caches for embedded
systems. The data cache was split in scalar and array caches aiming to take
advantage of temporal and spatial localities respectively. Their optimization
was based on dealing with predefined cache configurations, where the values of
the parameters were fixed before the optimization. Hence, the search space in
this case is small compared with a space where all the parameter values are
taken into account.

Chen and Zou Chen-2007  presented an efficient reconfiguration management
algorithm for embedded systems. The cache configuration automatically changed
after identifying a phase change. The search space was composed by these
parameters: cache size, block size and associativity. From our point of view,
this work do not consider enough number of cache parameters.

Gordon-Ross et al. Gordon-2008  applied a method with an off-line phase
classification and an on-line predictor phase. Phase classification breaks
applications execution into fixed size intervals grouped according to its
similar behavior pattern. The phase predictor decides the cache configuration
for the next interval. Exploration space was defined by cache size, block size
and associativity, which means that only three parameters were considered to
define the search space. In this case, given the on-line prediction phase, a
low number of parameters was required.

Wang et al. Wang-2012  proposed dynamic cache reconfiguration for real time
embedded systems. They minimize energy consumption performing a static
analysis at runtime. This proposal is based in previous works Wang-2009 ;
Wang-2011  where they addressed an unified two-level cache hierarchy and
multi-level cache hierarchy respectively. A combination of static analysis and
dynamic tuning of cache parameters, without time overhead were performed in
both cases. However, a few number of parameters were optimized: cache size (1,
2 or 4KB), line-size (16, 32 or 64 bytes) and associativity (1-way, 2-way or
4-way).

New hardware technologies and core-based processor technologies, such as those
proposed, for example, by ARM ARMreconf2014 , allow changing the cache
configuration for each application. Changes affect the main parameters:
capacity, block size and associativity. However, an efficient algorithm is
needed to determine optimal values for each application.

###  3.2 Evolutionary Techniques

Evolutionary techniques have been widely applied in design optimization, both
for hardware and software optimization with different objectives.

The creators of the Grammatical Evolution technique published a work where a
caching algorithm was automatically generated ONeill99automaticgeneration .
However, they only considered the generation of the caching algorithm and kept
fixed some other parameters like cache size, for instance. Again, many
parameters were missed.

Palesi and Givargis Palesi-2002  presented a multi-objective optimization
approach to explore the design space of a system-on-a-chip (SoC) architecture
to find the pareto optimal configurations of the system. They performed the
optimization through a genetic algorithm where the evaluation is done directly
in the SoC. However, the number of parameters they study is lower than ours,
and their approach is not escalable to current multimedia applications given
the low performance of the SoC.

Filho et al. Filho-2008  presented an approach based on the NSGA-II algorithm
to evaluate cache configurations on a second level cache in order to improve
energy consumption and performance, optimizing cache size, line size and
associativity. However, again, the number of parameters is lower than in our
proposal and, therefore, the search space is smaller.

Dani et al. Dani2012  applied a genetic algorithm to find an optimal cache
configuration for a chip multiprocessor (CMP) system. They deal with a complex
system like a CMP. However, they do not manage a higher number of cache
parameters and, given that they encode the configuration of both the chip and
the cache into a chromosome, the decodification process is complex. This issue
makes difficult the application of the same method to a different
microarchitecture.

Risco et al. RiscoMartin2014109  presented a framework based on Grammatical
Evolution to design custom dynamic memory managers for multimedia applications
in embedded systems. They optimized memory accesses, memory usage and energy
consumption. However, they do not deal with cache parameters but optimizing
the operating system memory manager instead of dealing with cache design
parameters.

Finally, performing a deep search in the literature, and specially in one of
the main hubs of Grammatical Evolution publications GEpubs2015 , we have not
found any recent work which applied this technique to optimize the cache
design of a microarchitecture.

###  3.3 Summary

As seen, the approaches that make use of reconfiguration require extra
hardware complexity in the design of the memory subsystem. Also, in the
majority of the cases, this complexity adds an overhead in execution time. In
our work we propose a different approach focused on finding the best cache
configuration after exploring the search space of cache designs. This strategy
avoids the cache reconfiguration which does not add hardware complexity to the
cache memory design.

In addition, previous works define their design space by cache size, block
size and associativity of either instruction cache or data cache, but we have
not found any proposal that considers both caches at the same time on embedded
systems. Our motivation is different since we consider the optimization of
instruction and data caches together, and we selected all the parameters that
can be tunned: cache size, block size, associativity, replacement algorithm
and prefetch algorithm for both caches; and write policy for data cache.
Therefore, we explore a wider search space.

Moreover, to the best of our knowledge, none of the previous works considers
the optimization of as many parameters as we tackle in our proposal. Regarding
the works using evolutionary techniques, most of the cited papers have focused
their space exploration on typical structural cache parameters such as cache
size, line size and associativity and, in addition, they usually deal with
short ranges for parameter values. One of the most used technique in this kind
of works, the genetic algorithm, presents the drawback of the codification
process which has to be customized for every different cache paradigm and
simulator software.

On the other hand, the methodology we propose can be applied to any kind of
cache and processor architectures. To this aim, the main and unique change in
our framework will be the cache simulator and the grammar, as it will be shown
later.

##  4 Performance and energy models

In this research work we consider the execution time and energy consumption of
a given cache configuration when running a benchmark application. As explained
before, we deal with program traces that are processed by a cache simulator
that accounts for the number of hits and misses of each execution, which
represent the cache behavior.

As stated before, we selected the ARM9 processors family ARM9  as our target
embedded system where cache configuration will be optimized. Here, the L1
cache is divided into instructions cache and data cache, and an embedded DRAM
acts as main memory.

In addition to the target architecture, we consider that instructions cache is
read-only, and a main memory is available. The main memory features are
displayed in Table 1 and will be taken into account in the evluation of a
cache configuration.

Table 1: Main memory (DRAM) features. Size |  $64$ Mb
---|---
Access time |  $3.9889\times 10^{-9}$ sec.
Bandwidth |  $6.7108864\times 10^{9}$ bytes/sec.
Access power |  $1.051$ W

Once the hardware features are set, we need a model able to translate the
number of hits and misses of the benchmarks runs into execution times and
energy consumption. To this aim, we chose the performance and energy models
described in Janapsatya-2006  for our optimization framework.

The authors of the paper proved, with a 100% accuracy, that the models were
equivalent to the results obtained from a cache simulator. Therefore, given
this performance, and taking into account that the expressions of the models
could be evaluated very fast, they fit very well into an optimization
algorithm like the one we present.

Hence, considering these models, we do account the performance and energy
model of the cache memory subsystem. The model of the rest of the components
of the chip (CPU, main memory, etc.) is not taken into account given that our
optimization scheme tackles only the cache subsystem. Next we briefly describe
these cache models.

###  4.1 Performance model

The cache performance model allows to obtain the execution time. This model is
based on the number of hits and misses on the cache memory system and the time
needed to solve them. We show in (1) the equation applied to compute execution
time. Each one of its components is described bellow, but a wider explanation
can be found in Janapsatya-2006 .

$\displaystyle T$ $\displaystyle\,=\,$ $\displaystyle Icache_{access}\times
Icache_{access\\_time}+$ (1) $\displaystyle Icache_{miss}\times
DRAM_{access\\_time}+$ $\displaystyle Icache_{miss}\times
Icache_{line\\_size}\times\frac{1}{DRAM\\_bwidth}+$ $\displaystyle
Dcache_{access}\times Dcache_{access\\_time}+$ $\displaystyle
Dcache_{miss}\times DRAM_{access\\_time}+$ $\displaystyle Dcache_{miss}\times
Dcache_{line\\_size}\times\frac{1}{DRAM\\_bwidth}$

Each term in the equation represents:

  * •

$Icache_{access}$ and $Dcache_{access}$ are the number of cache memory
accesses to the instruction and data caches, respectively.

  * •

$Icache_{miss}$ and $Dcache_{miss}$ are the number of cache misses. For each
one, data must be copied from the main memory.

  * •

$Icache_{access\\_time}$ and $Dcache_{access\\_time}$ represent the time
needed for each access to the instruction and data caches, respectively.

  * •

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

  * •

$Icache_{line\\_size}$ and $Dcache_{line\\_size}$ correspond to the line size
(block size) for instruction and data caches, respectively.

  * •

$DRAM\\_{bwidth}$ is the transfer capacity of the DRAM.

Therefore, the first and fourth parts in this equation represented by
$Icache_{access}\times Icache_{access\\_ti\\-me}$ and
$Dcache\\-_{access}\times Dca\\-che_{access\\_ti\\-me}$ compute the total time
needed to solve all instruction and data cache accesses, respectively.
$Ica\\-che_{miss}\times DRAM_{access\\_ti\\-me}$ and $Dca\\-che_{miss}\times
DRAM_{access\\_ti\\-me}$ are the total time spent by main memory accesses in
response to instruction and data cache misses. The third and sixth parts,
specified by $Ica\\-che_{miss}\times
Ica\\-che_{li\\-ne\\_si\\-ze}\times\frac{1}{DRAM\\_bwidth}$ and
$Dca\\-che_{miss}\times
Dca\\-che_{li\\-ne\\_si\\-ze}\times\frac{1}{DRAM\\_bwidth}$ calculate the
total time needed to fill in an instruction and data caches line when a miss
happens, respectively.

###  4.2 Energy model

The energy model is defined in (2), and also detailed in Janapsatya-2006 .
This equation is used to determine the dynamic energy consumption for a cache
configuration.

$\displaystyle E$ $\displaystyle\,=\,$ $\displaystyle Total_{time}\times
CPU_{power}+$ (2) $\displaystyle Icache_{access}\times
Icache_{access\\_energy}+$ $\displaystyle Dcache_{access}\times
Dcache_{access\\_energy}+$ $\displaystyle Icache_{miss}\times
Icache_{access\\_energy}\times Icache_{line\\_size}+$ $\displaystyle
Dcache_{miss}\times Dcache_{access\\_energy}\times Dcache_{line\\_size}+$
$\displaystyle Icache_{miss}\times DRAM_{access\\_power}+$
$\displaystyle(\small{DRAM_{access\\_time}}+\small{Icache_{line\\_size}}\times\frac{1}{\small{DRAM_{bwidth}}})+$
$\displaystyle Dcache_{miss}\times DRAM_{access\\_power}+$
$\displaystyle(\scriptsize{DRAM_{access\\_time}}+\scriptsize{Dcache_{line\\_size}}\times\frac{1}{\tiny{DRAM_{bwidth}}})$

Most of the components of the equation have been briefly described above. The
rest of the components are the following:

  * •

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

  * •

$Icache_{access\\_energy}$ and $Dcache_{access\\_energy}$ correspond to energy
consumption for each instruction and data caches access, respectively.

The $Icache_{access}\times Icache_{access\\_energy}$ and
$Dcache\\-_{access}\times Dcache_{access\\_energy}$ terms calculate the energy
consumption due to instruction and data caches, respectively.
$Icache_{miss}\times Icache_{access\\_energy}\times
Icache\\-_{line\\-\\_size}$ and $Dcache_{miss}\times
Dcache_{access\\_energy}\times Dcache\\-_{line\\-\\_size}$ is the energy cost
of writing data to the instruction and data caches when misses occur. The two
last terms calculate the energy cost of the DRAM when responding to cache
misses.

In our approach, we have removed the first term of the energy equation
$Total_{time}\times CPU_{power}$ because of three reasons: (1) the term
$CPU_{power}$ is constant and the term $Total_{time}$ corresponds to the total
time of the system, not only the cache subsystem, (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) this term could be large
enough to hide the differences because of memory cache operations. Thus, the
energy equation is reduced to:

$\displaystyle E$ $\displaystyle\,=\,$ $\displaystyle Icache_{access}\times
Icache_{access\\_energy}+$ (3) $\displaystyle Dcache_{access}\times
Dcache_{access\\_energy}+$ $\displaystyle Icache_{miss}\times
Icache_{access\\_energy}\times Icache_{line\\_size}+$ $\displaystyle
Dcache_{miss}\times Dcache_{access\\_energy}\times Dcache_{line\\_size}+$
$\displaystyle Icache_{miss}\times DRAM_{access\\_power}+$
$\displaystyle(\small{DRAM_{access\\_time}}+\small{Icache_{line\\_size}}\times\frac{1}{\small{DRAM_{bwidth}}})+$
$\displaystyle Dcache_{miss}\times DRAM_{access\\_power}+$
$\displaystyle(\small{DRAM_{access\\_time}}+\small{Dcache_{line\\_size}}\times\frac{1}{\small{DRAM_{bwidth}}})$

All the equations use seconds, watts, joules, bytes and bytes/sec as units to
measure time, power, energy, cache line size and bandwidth, respectively.

Next, we describe the whole process of optimization showing where these models
are applied.

##  5 Optimization methodology

As explained before, in this work we propose an approach to identify the best
cache configuration for a given set of applications. We define the best cache
configuration as the one which minimizes the execution time and energy
consumption for a given benchmark.

With this aim in mind, in this section we describe the optimization framework
that we propose to optimize the cache memory, in this case, of multimedia
embedded systems. Figure 2 presents an overview of the whole process.

Figure 2: Processes involved in the cache configuration optimization.

We divided our optimization process into three different stages. Firstly, two
processes are run just once before the optimization. These are called off-line
processes and perform: (1) cache characterization and (2) application
profiling. The third stage is the optimization, which is formed by the
evolutionary process running GE and calling the cache simulator.

The optimization is performed by the Grammatical Evolution (GE) module, as
seen in Figure 2. Each time a configuration has to be evaluated, the GE calls
Dinero IV, which is a trace-driven cache simulator DineroIV . It receives a
cache configuration from GE and returns the number of cache hits and misses
for the target application traces. These date are included in the models to
evaluate the configuration. Next, we give more detail of this optimization
flow.

###  5.1 Off-line process

Two tasks are run off-line: the characterization of the possible cache
configurations, and the profiling of the target benchmarks. Both tasks are
slow, but can be run just once, because their results are stored in data files
that are read by the cache simulator and the GE module.

The characterization process, on the upper left part of Figure 2, has the
specific task of combining all the parameter values for cache configurations.
That is, generates all the possible cache configurations and obtains their
access time and energy consumption per access. Hence, this process provides
the time and energy values used for the terms in equations (1) and (3). For
this purpose we used Cacti Mamidipaka2004  considering 32nm technology to
compute the DRAM and cache access times and dynamic energy consumed for each
cache access. Cacti is an analytical model widely applied to estimate energy
and power consumption, performance and area of cache memories. This
characterization was run only once, and we selected for this task the web tool
provided by the Cacti organization. The most important parameters required by
Cacti are those mainly related to hardware: cache size, line size and
associativity, and there is no distinction between instructions and data
caches. Hence, this is a slow but affordable task.

The profiling process, on the upper right part of Figure 2, is in charge of
the generation of the traces from the target applications. Again, this is a
process that has to be run just once. The profiling takes each benchmark
application and obtains the sequence of cache hits and misses from a run,
generating a memory trace file. This process is carried out by the open-source
compiler and performance monitoring infrastructure called Trimaran trimaran ,
which provides the resources required to obtain accurate application traces.
Given that the ARM processors are not directly addressed by Trimaran, we have
modified it by incorporating code from the architectural simulator
SimpleScalar simplescalar , which is able to model a wide set of different
architectures, being the ARM among them.

Besides, it has to be mentioned that input and output data of all the
benchmarks under study are represented in the trace file. Therefore, in order
to capture the mean behavior of each application, we will select the
recommended inputs indicated in the documentation of each benchmark.

###  5.2 Grammatical Evolution

The characterization of the cache ends up with two kind of results. On the one
hand, the time and energy required per access is obtained for each cache
configuration and, on the other hand, the traces with all the memory
operations of each benchmark application have been obtained. Therefore, our
framework is ready to evaluate the performance of any candidate cache
configuration, which will be generated in the optimization module, based on
Grammatical Evolution.

Grammatical Evolution ONeill2001 ; ONeill2003 ; ONeill2008 ; Dempsey2009  is
an evolutionary technique that is able to represent individuals by means of
grammars. GE is a form of Genetic Programming (GP) Koza2003  which evolves
programs that are evaluated according their fitness values. In this regard, GE
represents each program, that is, each individual, through an expression
generated by a grammar defined by the researcher.

GE performs evolutionary process on variable-length binary strings, which are
mapped to generate a program by selecting production rules in a Backus-Naur
form (BNF) grammar definition. Given that strings are similar to chromosomes,
GE allows using genetic operators like selection, crossover and mutation.
Problems such as financial modeling Brabazon2006 , game strategies Galvan-2010
, dynamic game environment Perez-2011 , 2D platforms games design Shaker-2012
, 3D design Byrne-2010  among others, have been successfully addressed by
using GE.

So, the GE traverses the search space of cache configurations according to the
grammar definition. For each individual, it calls the cache simulator to
obtain the number of hits and misses for the target benchmarks. Then, using
the access time and energy per access previously computed by Cacti, and the
performance and energy models described in Section 4, the fitness is computed.
This process is repeated till the selected number of generations for GE is
reached. As a result, an optimized cache configuration is obtained for each
one of the benchmark programs.

As seen in Section 2, the search space of this problem is defined by the set
of cache configurations. However, GE works with individuals that represent
those configurations under a proper codification. In fact, GE uses a linear
genome rather than a tree-based structure, as in GP. Linear genome facilitates
the application of genetic operators. Here, the chromosome of each individual
consists of a string of integer values corresponding to codons. Each codon
stores a value of 8 bits, hence forming the genotype. The genotype is decoded
in a process called mapping, where a grammar is used to translate the codons
into the phenotype of the individual.

One individual represents a particular cache configuration that must be
evaluated in order to measure its execution time and energy consumption. In
this regard, we have decided to consider the same weight for both features of
the cache. Therefore, for a given cache configuration $c_{i}$, the evaluation
process is conducted by the fitness function $f$ defined in (4).

$\centering
f(c_{i})=0.5\times\frac{T(c_{i})}{T(Baseline)}+0.5\times\frac{E(c_{i})}{E(Baseline)}\@add@centering$
(4)

Each component of the fitness, that is, execution time and energy consumption,
are normalized with respect to a baseline configuration. By normalizing to a
baseline we are able to correctly scale and operate the units of different
measures like time and energy. As seen in (4), both terms are weighted to
$50\%$ seeking the best balance between the improvement of the performance and
energy consumption. The best cache configuration in GE will be the one that
minimizes the fitness value.

Given that the evaluation of a cache configuration involves a call to the
cache simulator, we have designed a grammar that produces phenotypes which
form the parameters of the call to the simulator. In fact, one of the benefits
of GE is the ability to create complex phenotypes from a genotype formed by
integer values.

Figure 3 shows, in BNF format, the grammar we have designed for the cache
optimization under the previously defined search space. As stated before, the
grammar produces the string of parameters that will be sent to the cache
simulator. In fact, we have adapted the parameters to the requirements of the
simulator. As seen in the figure, the replacement algorithm will take values
like l, f or r, which correspond in the simulator, respectively, to LRU, FIFO
and RANDOM. The same applies for prefetching and write policy.

According to the terminology, a grammar is described as a tuple {N, T, S, P},
where N represents the non-terminals symbols, T is the set of terminals, S
represents the start symbol belonging to N, and P defines the set of
production rules that map the values of N to T. The “$|$” symbol separates the
different choices within a single production rule. In our grammar, P is formed
by production rules from I to VII.

⬇

N = { <DineroParams>, <CacheSizeB>, <LineSizeB>,

<ReplAlg>, <Assoc>, <PrefAlg>, <WritePol> }

T = { 1, 2, 4, 8, 16, 32, 64, 128 512, 1024, 2048,

4096, 8192, 16384, 32768, 65536, l, f, r, m,

d, a, n }

S = <DineroParams>

P = { I <DineroParams> ::= -l1-isize <CacheSizeB>

-l1-ibsize <LineSizeB>

-l1-irepl <ReplAlg>

-l1-iassoc <Assoc>

-l1-ifetch <PrefAlg>

-l1-dsize <CacheSizeB>

-l1-dbsize <LineSizeB>

-l1-drepl <ReplAlg>

-l1-dassoc <Assoc>

-l1-dfetch <PrefAlg>

-l1-dwback <WritePol>

II <CacheSizeB> ::= 512 | 1024 | 2048 | 4096

| 8192 | 16384 | 32768

| 65536

III <LineSizeB> ::= 8 | 16 | 32 | 64

IV <ReplAlg> ::= l | f | r

V <Assoc> ::= 1 | 2 | 4 | 8 | 16 | 32 | 64

| 128

VI <PrefAlg> ::= m | d | a

VII <WritePol> ::= a | n }

Figure 3: Grammar for cache configuration description.

Next we show an example of the mapping process for the problem at hand using
the grammar in Figure 3. Let’s consider the genotype shown in the upper part
of Figure 4 as a candidate solution. This individual is a genotype that
represents a cache configuration. However, it has to be decoded in order to
obtain the values of each one of the 11 parameters of the cache configuration
previously described.

The mapping or decodification process is performed by applying the modulus
operation between the codon value and the number of options of each production
rule corresponding to the non-terminal symbol being processed.

Figure 4: Decoding process in GE that, starting from the genotype above,
obtains the phenotype by mapping through the proposed grammar.

Then, considering the example individual, the decoding process is performed as
shown in Figure 4. It begins decoding the starting symbol, <DineroParams>,
which is substituted by its production, that corresponds to the parameterized
call to the cache simulator. Here, several non-terminal symbols are present,
and the first one is <CacheSizeB>. Hence, the first gene of the genotype is
selected, $20$. Given that the production for <CacheSizeB> (rule II) has $8$
different options, the selected value is option $4$ ($20\ MOD\ 8=4$), which
corresponds to 8192. Notice that the first option of the rule is linked to
$0$, the second to $1$ and so on. Next, the second gene is read and its value,
$35$, is used to decode the following non-terminal symbol, <LineSizeB>. The
production rule for this symbol is III, and has $4$ options. Then, after the
modulus operation ($35\ MOD\ 4=3$) <LineSizeB> is replaced by 64. The
following non-terminal symbol to be decoded is <ReplAlg>, whose production
rule, IV has $3$ different options. Then, the codon value, $71$, is processed.
Given that $71\ MOD\ 3=2$, the selected value is r. In an analogous way, the
next codon, $96$ for <Assoc> is turned into $1$ given that $96\ MOD\ 8=0$. The
last non-terminal corresponding to the instructions cache parameters,
<PrefAlg>, is determined by the codon value $123$ which is replaced by m, once
that $123\ MOD\ 3=0$. Next, the mapping process continues with the codon $210$
and the second <CacheSizeB> symbol, which maps $2048$ and corresponds to the
data cache size. Then, $137$ maps <LineSizeB> to $16$, gene $7$ maps <ReplAlg>
to f and $5$ maps <Assoc> to $4$.

At this point, all the genes have been used but the expression is still
partially decoded. However, GE is able to work with variable length
chromosomes and, if the decodification process reaches the end of the
chromosome and there are still non-terminal symbols, GE goes to the first
codon and allows the decodification to finish. This process is called
wrapping. Hence, in our example a wrap takes place at this point. Therefore,
<PrefAlg> is decoded with the first gene, $20$, obtaining a. Finally,
decodification ends mapping <WritePol> to n with gene value $35$.

As a result, our genotype example returns the phenotype shown in the lower
part of Figure4, which represents a cache configuration where instructions
cache size is $8192$, instructions cache block size is $64$, and so on.

Once decoded, the phenotype is used to call the cache simulator in order to
evaluate the corresponding configuration on the target application, obtaining
both the execution time and energy consumption according to the fitness
defined in (4). At the end of the selected number of generations, the GE
returns the cache configuration that obtains the best fitness value.

As seen, the grammar determines both the concrete parameters to be optimized,
as well as the communication with the cache simulator, which provides the
fitness value. Therefore, changing the grammar will allow different
optimization approaches: fix the value of some parameters, add new parameters,
change the cache simulator, use variable length arguments in the cache
simulator (for custom algorithms, for example), an so on.

In this way, given both an invariable number (and type) of parameters and a
cache simulator, the grammar forces the evolution of a fixed structure, and GE
acts optimising the parameters in this structure. Hence, this problem could be
tackled with a fixed-length algorithm like a GA, PSO and so on. However, in
this kind of approaches, any change in the number or type of parameters, or
even in the simulator, will require the modification of an important part of
the code, mainly in the decodification and fitness evaluation modules. Hence,
our approach based on GE provides a great flexibility as well as extensibility
features because those changes could be incorporated with a simple change of
the grammar.

The GE algorithm was developed in Java by our research team, and is publicly
available as the JECO library JECO .

##  6 Experimental results

In order to test our experimental framework, we selected twelve benchmarks
from the Mediabench suite mediabench , which are representative of multimedia
applications. Next, we describe the features of these benchmarks. The full
description can be found on the Mediabench website.

  * •

JPEG is a C software to compress (cjpeg) and uncompress (djpeg) full-color and
gray-scale JPEG images.

  * •

MPEG is an optimized implementation for transmitting high quality digital
video. The mpegenc benchmark is in charge of encode process, and the mpegdec
benchmark to the decode process.

  * •

GSM implements an algorithm to reliable voice recognition. The algorithm is
based on the implementation of the European GSM 06.10 provisional standard for
full-rate speech transcoding. The gsmenc benchmark performs the compression
frames process, and the gsmdec performs the decompression process.

  * •

Pegwit implements the process for public key encryption and authentication.
The process uses an elliptic curve over GF($2^{255}$), the codification
algorithm SHA1 for hashing, and the symmetric block cipher square. Pegwitenc
and pegwitdec perform encoding and decoding respectively.

  * •

EPIC (Efficient Pyramid Image Coder) performs image data compression (epic)
and decompression (unepic). The algorithms are based on a biorthogonal
critically-sampled dyadic wavelet decomposition and a combined run-
length/Huffman entropy coder.

  * •

ADPCM (Adaptive Differential Pulse Code Modulation) implements speech
compression and decompression algorithms. Rawcaudio performs the compression
while rawdaudio performs the decompression. The algorithm they use achieves a
compression rate of 4:1 on 16 bits linear PCM samples.

Our experiments were carried out in a machine provided with an Intel i5 660
processor at 3.3 GHz. Given that this is a 4-core processor, we run a maximum
of 4 experiments at the same time. The available RAM in the machine was 8 Gb,
and the operating system was Ubuntu Desktop 14.04.

###  6.1 Experimental setup

As stated before, our experimental framework is parameterized according to the
ARM architecture. Then, to evaluate our approach we consider a first level
cache memory with a range of sizes between 512B and 64KB, increased in powers
of two. With this set of possible cache sizes we cover many of the sizes for
some devices of the ARM9 processor family. According to these features, the
search space for GE was described in Section 2 combining both instruction and
data caches. However, the cache characterization is performed for individual
memories taking into account only the hardware parameters in the offline
characterization process. In our search space, these parameters correspond to
$8$ possible cache sizes, $8$ different associativity degrees and $4$
possibles values for block size, as shown in Figure 1. Hence, the number of
cache characterizations to be run are $256$.

Using our methodology for off-line profiling, we have generated the Mediabench
traces using Trimaran tools trimaran  in connection with SimpleScalar
simplescalar  to evaluate the ARM architecture. In the light of the above, the
appropriate changes have been made for both SimpleScalar and Trimaran tools to
generate application traces able to be processed by the Dinero IV cache
simulator.

This kind of experiments require to manage full application traces or execute
a number of appropriate instructions which reflects the behavior of the full
program. This way prevents to capture a partial or phase behavior. For
instance, phase behavior happens at the beginning of the application run, when
all data blocks must be copied from the main memory, so all accesses to cache
memory are misses. Thus, a small number of instructions can provide results
that cannot be considered as significant or conclusive. In this regard, we
have simulated every application a maximum of $7.5\times 10^{7}$ instructions,
or even the full application, if the total number of instructions for the
complete execution is lower than this value. The aim is to reach a balance
between the simulation time, the size of the program traces and a proper
number of instructions.

In addition, GE has been run 10 times for each target application with the aim
of reducing the probability to get a local optimum.

Table 2 shows the parameters for GE. We have also applied simple dominance,
single point crossover and integer flip mutation operator with probabilities
according to recommendations in Deb2002 .

Table 2: Parameters for GE. Number of generations | $100$
---|---
Population size | $50$
Probability of crossover | $0.9$
Probability of mutation | $0.01$

As stated in (4) (see Section 5.2), our algorithm requires a baseline cache
configuration in order to calculate the goodness of an individual. For these
experiments we selected a baseline cache configuration that is similar to the
cache of the first core in the GP2X portable game console, which incorporates
a dual 200 MHz ARM940T processor.

Table 3 shows the size of the cache, the size of the block, the number of ways
(associativity degree), replacement policy, search algorithm and, for the data
cache, the allocation policy of the baseline configuration.

Table 3: Baseline cache configuration. It is formed by parameters of
instructions and data caches.

Instructions Cache
---
Size | Block Sz. | Assoc. | Replac. | Search Alg.
16 KB | 32 B | 4 | LRU | On-Demand

Data Cache
---
Size | Block Sz. | Assoc. | Replac. | Search Alg. | Alloc.
16 KB | 32 B | 4 | LRU | On-demand | Copy-Back

Execution time and energy consumption for the baseline cache was computed
following the models described in Section 4.

###  6.2 Objective function

Firstly, we analyze the results regarding the value of the objective function.
We would like to recall that objective value $1$ corresponds to the execution
time and energy consumption of the baseline cache configuration running each
one of the bechmarks. Therefore, we minimize the objective function in order
to reduce both features.

Table 4 shows the following statistics, averaged for each one of the
benchmarks: objective value, deviation percentage with respect to the best
objective found, and number of best results found.

Table 4: Objective function values. Benchmark | Avg. Obj. | Dev. (%) | # Best
---|---|---|---
cjpeg | 0.3986650026 | 0.74% | 8
djpeg | 0.4746031647 | 3.06% | 1
epic | 0.3365548961 | 1.24% | 7
unepic | 0.3977187056 | 0.65% | 1
gsmdec | 0.3857290316 | 1.15% | 7
gsmenc | 0.4442631856 | 1.82% | 4
mpegdec | 0.3682433302 | 1.09% | 6
mpegenc | 0.3631493163 | 0.89% | 3
pegwitdec | 0.3663486721 | 0.01% | 9
pegwitenc | 0.3568943181 | 0.00% | 10
rawcaudio | 0.3052829963 | 0.00% | 8
rawdaudio | 0.31533024 | 0.56% | 9

As seen in the table, the average objective values range from $0.47$ to
$0.30$, which mean improvements from $53\%$ to $70\%$, with an average
improvement of $62\%$ in the objective value. Hence, the optimization obtains
really good objective improvements. In addition, the low values of the standar
deviation show that GE obtains very close results across the optimization
runs. In fact, the number of times the best result is found is higher or equal
to $70\%$ in 7 out of the 12 benchmarks. In particular, GE obtains great
results in pegwitdec, pegwitenc, rawcaudio and rawdaudio benchmarks. On the
other hand, despite that GE obtains the best value only once in djpeg and
unepic, the deviation is below $3.1\%$ and $0.7\%$ respectively, which again
is a very good result.

These results prove that a metaheuristic like GE, even with a low number of
generations and population size, is able to find solutions where the objetive
function is reduced above the $62\%$ for the cache optimization problem.

###  6.3 Optimization runtime

We have made another analysus regarding the optimization runtime (RT). Table 5
shows the average optimization runtime in hours, the average number of
evaluations in relation to the maximum expected for GE, the average runtime
for the evaluation of one cache configuration in seconds, the maximum
optimization runtime of GE if all evaluations were performed, and the runtime
savings of the experiments in relation to that time.

Table 5: Runtime values. For each benchmark, it shows the average runtime (hours), average number of evaluations vs max. GE, average runtime for one cache evaluation (seconds), maximum runtime for GE (no evaluation recall) and runtime savings in relation to maximum GE. Benchmark | RT (h.) | # Eval. (%) | Eval. (sec.) | Max GE (h.) | RT Sav.
---|---|---|---|---|---
cjpeg | 2.185 | 5.96% | 26.200 | 36.389 | 93.99%
djpeg | 2.647 | 5.74% | 33.064 | 45.923 | 94.24%
epic | 1.405 | 5.87% | 17.148 | 23.816 | 94.10%
unepic | 0.350 | 5.79% | 4.340 | 6.028 | 94.19%
gsmdec | 0.004 | 6.33% | 0.043 | 0.060 | 93.67%
gsmenc | 0.003 | 5.58% | 0.041 | 0.057 | 94.41%
mpegdec | 2.275 | 5.69% | 28.805 | 40.006 | 94.31%
mpegenc | 2.031 | 5.80% | 25.209 | 35.013 | 94.20%
pegwitdec | 0.945 | 6.38% | 10.667 | 14.815 | 93.62%
pegwitenc | 0.869 | 5.98% | 10.466 | 14.537 | 94.02%
rawcaudio | 0.372 | 5.95% | 4.483 | 6.227 | 94.03%
rawdaudio | 0.274 | 5.89% | 3.343 | 4.642 | 94.10%

At the same time the optimization was run, we measured the time spent for the
evaluation of each cache configuration. As seen in the table, the average
evaluation time is high is some of the benchmarks like djpeg, mpegdec and
mpegenc. Taking into account this time values, we have calculated the
optimization time that a GE execution will spent if the 5000 evaluations were
run, that is, if the algorithm will not implement memory for evaluated
individuals.

As seen in the savings columns, the execution time is reduced in more than
$93.6\%$. Therefore, it is clear that our GE implementation is able to run in
reasonable amounts of time due to the memory of evaluated individuals.

The reduced optimization runtimes are caused by two factors. On the one hand,
the number of evaluations is low because the exploration of the GE algorithm
reaches an area of minimum values making the population to converge to that
minimum. In other words, the individuals of the population are becoming
similar over the generations. On the other hand, given that our algorithm
recalls the evaluation of each individual, the previously evaluated
configurations are not sent to the external simulator, but read from the GE
memory. This is a very fast process because we implemented it through hashed
maps.

###  6.4 Execution time and energy consumption

As stated in 5.2, the objective function incorporates both the execution time
and energy consumption values of a given cache configuration. Then, once we
have obtained the optimized cache configurations, we show how these results
are interpreted in terms of execution time and energy consumption.

Figure 5: Average energy consumption for the solutions obtained on each
benchmark in relation to baseline (100%).

Figure5 plots the average enery consumption of the runs for each benchmark
considering that 100% is the energy consumption of the baseline cache. On
average, the solutions we have obtained reach the $3.04\%$ of the baseline.

Figure 6: Average execution time for the solutions obtained on each benchmark
in relation to baseline (100%).

Figure6 plots the average execution time of the runs for each benchmark
considering that 100% is the energy consumption of the baseline cache. On
average, the solutions we have obtained reach the $24.74\%$ of the baseline.

In brief, we have improved the cache behavior by $97\%$ in energy consumption
and, at the same time, by $75\%$ in execution time considering a commercial
baseline cache. These results were obtained in very short runtimes compared
with the expected time that a GE with no evaluation recall will reach.

For the sake of clarity, we would like to remark that the baseline
configuration acts as a reference point from which the GE process optimizes.
In fact, given that our framework uses the characterization from a cache
emulator (Cacti in our case), any baseline configuration could be optimized by
providing the framework with the corresponding baseline characterization
values.

In addition, given that the benchmark results for the baseline cache are not
optimised, the improvements obtained by GE (which are optimised) should be
taken as indicative of potential performance gains.

##  7 Conclusions and future work

The significant increase of multimedia applications in embedded devices such
as tablets, smartphones, GPS navigation systems, etc. has caused researchers
focus their works on improving either the execution time and energy
consumption, or both. In order to improve the execution time, current embedded
systems include a cache hierarchy similar to desktop computers. However, the
wide range of possible cache configurations complicates the search of the best
cache configuration. Not to mention the fact that the execution time and
energy consumption are directly affected by the memory access patterns of
applications. Therefore, new and efficient techniques have been proposed for
years to explore and decide the best cache configuration for different
applications. However, we have not found in literature any work that optimize,
at the same time, all the parameters that configure both the instructions and
the cache memory for a given set of applications.

In this paper we have presented an optimization framework based on static
profiling and metaheuristics to automatically search for the best cache
configuration given a set of applications to be run on a target embedded
system. Our optimization scheme considers 11 different parameters that
configure both the instruction and the data caches. The framework is divided
into two phases. The fist one is an off-line phase in charge to provide the
program traces and the features of the set of possible hardware configurations
for cache memories. The second phase is an optimization process that applies
GE obtaining the cache configuration that would obtain the best behavior for
each target application. In order to evaluate a cache configuration, GE
obtains the performance of each configuration with the help of the Dinero IV
cache simulator. In this way, the grammar of GE eases the communication with
Dinero IV given that the phenotype is formed by the parameters and formats
required by the simulator call.

In addition, our approach allows to modify the number of parameters to be
optimized, as well as the change of the cache simulator by simply modifying
the grammar at hand. Besides, if a cache simulator will allow variable length
parameters, an appropriate grammar will be able to generate correct simulator
calls without any modification in our optimization framework.

We have tested our proposal with twelve applications from the Mediabench
benchmarks considering an actual cache configuration as baseline. Our results
averaged an improvement of $97\%$ in energy consumption and $75\%$ in
execution time versus the baseline cache.

Our future plans include efforts to simplify processes and design an effective
framework that allow customize the optimization process for a set of target
applications at a time. In addition, we would take into account the different
load that memory operations represent on the target applications in order to
precisely balance their weight in the optimization. In fact, a natural step
forward after this research will be to analyze the influence between execution
time and energy results, and consider a multi-objective optimization.

## References

  * (1) http://www.grammatical-evolution.org/pubs.html (2015)
  * (2) ARM Ltd.: ARM9 Processor Family.  http://www.arm.com/products/processors/classic/arm9/ (2013)
  * (3) ARM946E-S TM: Technical reference manual.  http://www.arm.com/products/processors/classic/arm9/ arm946.php (2014)
  * (4) Brabazon, A., O’Neill, M.: Biologically Inspired Algorithms for Financial Modelling.  Springer (2006)
  * (5) Burger, D., T.M.Austin: The simplescalar tool set, version 2.0.  In: Technical Report, pp. CS–TR–97–1342. University of Wisconsin-Madison (1997)
  * (6) Byrne, J., McDermott, J., Galvaón-Loópez, E., O’Neill, M.: Implementing an intuitive mutation operator for interactive evolutionary 3d design.  In: Evolutionary Computation (CEC), 2010 IEEE Congress on, pp. 1–7 (2010).  DOI 10.1109/CEC.2010.5586485
  * (7) Chakrapani, L.N., Gyllenhaal, J., mei W. Hwu, W., Mahlke4, S.A., Palem1, K.V., Rabbah5, R.M.: Trimaran: An infrastructure for research in instruction-level parallelism.  In: In Instruction-Level Parallelism. Lecture Notes In Computer Science (2005).  URL http://www.trimaran.org/
  * (8) Chen, L., Zou, X., Lei, J., Liu, Z.: Dynamically reconfigurable cache for low-power embedded system.  In: Natural Computation, 2007. ICNC 2007. Third International Conference on, vol. 5, pp. 180 –184 (2007).  DOI 10.1109/ICNC.2007.346
  * (9) Dani, A., Srikant, Y., Amrutur, B.: Efficient cache exploration method for a tiled chip multiprocessor.  In: High Performance Computing (HiPC), 2012 19th International Conference on, pp. 1–6 (2012).  DOI 10.1109/HiPC.2012.6507524
  * (10) Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast and elitist multiobjective genetic algorithm: Nsga-ii.  Evolutionary Computation, IEEE Transactions on 6(2), 182–197 (2002).  DOI 10.1109/4235.996017
  * (11) Dempsey, I., O’Neill, M., Brabazon, A.: Foundations in Grammatical Evolution for Dynamic Environments, _Studies in Computational Intelligence_ , vol. 194\.  Springer (2009).  URL http://www.springer.com/engineering/book/978-3-642-00313-4
  * (12) Edler, J., Hill, M.D.: Dinero iv trace-driven uniprocessor cache simulator (1998).  URL http://pages.cs.wisc.edu/ markhill/DineroIV/
  * (13) Galván-López, E., Swafford, J., O’Neill, M., Brabazon, A.: Evolving a ms. pacman controller using grammatical evolution.  In: C. Chio, S. Cagnoni, C. Cotta, M. Ebner, A. Ekrt, A. Esparcia-Alcazar, C.K. Goh, J. Merelo, F. Neri, M. Preu, J. Togelius, G. Yannakakis (eds.) Applications of Evolutionary Computation, _Lecture Notes in Computer Science_ , vol. 6024, pp. 161–170. Springer Berlin Heidelberg (2010).  DOI 10.1007/978-3-642-12239-2_17.  URL http://dx.doi.org/10.1007/978-3-642-12239-2_17
  * (14) Gordon-Ross, A., Lau, J., Calder, B.: Phase-based cache reconfiguration for a highly-configurable two-level cache hierarchy.  In: Proceedings of the 18th ACM Great Lakes symposium on VLSI, GLSVLSI ’08, pp. 379–382. ACM, New York, NY, USA (2008).  DOI 10.1145/1366110.1366200.  URL http://doi.acm.org/10.1145/1366110.1366200
  * (15) Hennessy, J.L., Patterson, D.A.: Computer Architecture: A Quantitative Approach.  Morgan Kaufmann (2011)
  * (16) Janapsatya, A., Ignjatovic, A., Parameswaran, S.: Finding optimal l1 cache configuration for embedded systems.  In: Design Automation, 2006. Asia and South Pacific Conference on, p. 6 pp. (2006).  DOI 10.1109/ASPDAC.2006.1594783
  * (17) Koza, J.R., Poli, R.: Introductory tutorials in optimization, search and decision support (2003)
  * (18) Lee, C., Potkonjak, M., Mangione-Smith, W.H.: 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, pp. 330–335. IEEE Computer Society, Washington, DC, USA (1997).  URL http://dl.acm.org/citation.cfm?id=266800.266832
  * (19) Mamidipaka, M., Dutt, N.: eCACTI: An enhanced power estimation model for on-chip caches.  Tech. Rep. TR-04-28, CECS, UC Irvine (2004)
  * (20) Naz, A., Kavi, K., Rezaei, M., Li, W.: Making a case for split data caches for embedded applications.  SIGARCH Comput. Archit. News 34(1), 19–26 (2005).  DOI 10.1145/1147349.1147355.  URL http://doi.acm.org/10.1145/1147349.1147355
  * (21) O’Neill, M., Hemberg, E., Gilligan, C., Bartley, E., McDermott, J., Brabazon, A.: GEVA - grammatical evolution in Java.  SIGEVOlution 3(2), 17–22 (2008).  DOI http://doi.acm.org/10.1145/1527063.1527066
  * (22) O’Neill, M., Ryan, C.: Automatic generation of caching algorithms.  In: Evolutionary Algorithms in Engineering and Computer Science, pp. 127–134. John Wiley & Sons (1999)
  * (23) O’Neill, M., Ryan, C.: Grammatical evolution.  IEEE Trans. Evolutionary Computation 5(4), 349–358 (2001)
  * (24) O’Neill, M., Ryan, C.: Grammatical Evolution: Evolutionary Automatic Programming in an Arbitrary Language.  Kluwer Academic Publishers (2003)
  * (25) Palesi, M., Givargis, T.: Multi-objective design space exploration using genetic algorithms.  In: Hardware/Software Codesign, 2002. CODES 2002. Proceedings of the Tenth International Symposium on, pp. 67–72 (2002).  DOI 10.1109/CODES.2002.1003603
  * (26) Perez, D., Nicolau, M., O’Neill, M., Brabazon, A.: Evolving behaviour trees for the mario ai competition using grammatical evolution.  In: C. Chio, S. Cagnoni, C. Cotta, M. Ebner, A. Ekrt, A. Esparcia-Alcázar, J. Merelo, F. Neri, M. Preuss, H. Richter, J. Togelius, G. Yannakakis (eds.) Applications of Evolutionary Computation, _Lecture Notes in Computer Science_ , vol. 6624, pp. 123–132. Springer Berlin Heidelberg (2011).  DOI 10.1007/978-3-642-20525-5_13.  URL http://dx.doi.org/10.1007/978-3-642-20525-5_13
  * (27) Risco-Martín, J.L., Colmenar, J.M.: Java Evolutionary COmputation library (JECO).  Available at: https://sourceforge.net/projects/jeco (2013)
  * (28) Risco-Martín, J.L., Colmenar, J.M., Hidalgo, J.I., Lanchares, J., Díaz, J.: A methodology to automatically optimize dynamic memory managers applying grammatical evolution.  Journal of Systems and Software 91(0), 109 – 123 (2014).  DOI http://dx.doi.org/10.1016/j.jss.2013.12.044.  URL http://www.sciencedirect.com/science/article/pii/S016412121400017X
  * (29) Shaker, N., Nicolau, M., Yannakakis, G., Togelius, J., O’Neill, M.: Evolving levels for super mario bros using grammatical evolution.  In: Computational Intelligence and Games (CIG), 2012 IEEE Conference on, pp. 304–311 (2012).  DOI 10.1109/CIG.2012.6374170
  * (30) Silva-Filho, A., Bastos-Filho, C., Falcao, D., Cordeiro, F., Castro, R.: 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, pp. 19 –26 (2008).  DOI 10.1109/SBAC-PAD.2008.9
  * (31) Varma, A., Debes, E., Kozintsev, I., Jacob, B.: Instruction-level power dissipation in the intel xscale embedded microprocessor.  In: In SPIEs 17th Annual Symposium on Electronic Imaging Science & Technology (2005)
  * (32) Wang, W., Mishra, P.: Dynamic reconfiguration of two-level caches in soft real-time embedded systems.  In: VLSI, 2009. ISVLSI ’09. IEEE Computer Society Annual Symposium on, pp. 145–150 (2009).  DOI 10.1109/ISVLSI.2009.22
  * (33) Wang, W., Mishra, P., Gordon-Ross, A.: Dynamic cache reconfiguration for soft real-time systems.  ACM Trans. Embed. Comput. Syst. 11(2), 28:1–28:31 (2012).  DOI 10.1145/2220336.2220340.  URL http://doi.acm.org/10.1145/2220336.2220340
  * (34) Wang, W., Mishra, P., Ranka, S.: Dynamic cache reconfiguration and partitioning for energy optimization in real-time multi-core systems.  In: Proceedings of the 48th Design Automation Conference, pp. 948–953. ACM, New York, NY, USA (2011).  DOI 10.1145/2024724.2024935.  URL http://doi.acm.org/10.1145/2024724.2024935