# KdeHumor at SemEval-2020 Task 7: A Neural Network Model for Detecting
Funniness in Dataset Humicroedit

Rida Miraj  Masaki Aono
Department of Computer Science and Engineering
Toyohashi University of Technology, Japan.
<EMAIL_ADDRESS><EMAIL_ADDRESS>

###### Abstract

This paper describes our contribution to SemEval-2020 Task 7: Assessing Humor
in Edited News Headlines. Here we present a method based on a deep neural
network. In recent years, quite some attention has been devoted to humor
production and perception. Our team KdeHumor employs recurrent neural network
models including Bi-Directional LSTMs (BiLSTMs). Moreover, we utilize the
state-of-the-art pre-trained sentence embedding techniques. We analyze the
performance of our method and demonstrate the contribution of each component
of our architecture.

00footnotetext:  This work is licensed under a Creative Commons Attribution
4.0 International Licence. Licence details:
http://creativecommons.org/licenses/by/4.0/.

##  1 Introduction

Humor, a way of giving entertainment and provoking laughter, is an
exceptionally savvy communicative activity. In recent years, quite some
attention has been devoted to humor production and perception. What makes us
laugh when reading a funny sentence? Mostly it depends on the cultural area
background of a person. Humor cannot be defined in standards as it varies with
nation to nation, area to area, people to people. Many types of humor require
substantial external knowledge such as irony, wordplay, metaphor and sarcasm.
These factors make the task of humor recognition difficult.

Recently, with the advance of deep learning that allows end-to-end training
with big data without human intervention of feature selection, humor
recognition becomes promising. However detecting humor in news headlines from
which one word is chosen to be replaced by another word to make the micro-
edited sentences look funny is quite challenging. To address the challenges of
humor detection in edited news headlines, [Hossain et al., 2020] proposed
detection of funniness level in dataset named as Humicroedit111Dataset formed
for this task is named as humicroedit in the article [Hossain et al., 2019].,
Task 7 at SemEval-2020. They focus on two related subtasks. Task 1 defines
regression problem where a system needs to predict how much funny is the
edited news headlines (humicroedit) from range 0 to 3. Whereas Task 2 defines
the classification problem where a system need to predict the funniest
sentence between two edited headlines. In this paper, we only focus on the
Humicroedit data for both Tasks 1 and 2. No extra data, or other sources is
used to get more data. The rest of the paper is structured as follows: Section
2 provides a brief overview of prior research. In Section 3, we introduce our
proposed neural network model. Section 4 includes experiments and evaluations
as well as the analysis of our proposed method. Some concluded remarks and
future directions of our work are described in Section 5.

##  2 Related Research

11footnotetext:

Humor is omnipresent, universal, elusive event which exists in all societies
and cultures and fulfills a range of social, cognitive and emotional
functions. The task of automatic humor recognition refers to deciding whether
a given sentence expresses a certain degree of humor. In previous researches
and studies, mostly the problems related to humor were based on binary
classification, or based on selection on linguistic features. Taylor and
Mazlack analyzed on a specific type of humor. The methodology which they used
was based on the extraction of structural patterns and peculiar structure of
jokes newcite [Taylor and Mazlack, 2000]. Purandare and Litman used humorous
spoken conversations as data from a classic comedy television. To identify
humorous speech in the conversation, they used standard supervised learning
classifiers [Purandare and Litman, 2006]. Besides, a work has been done to
discover latent semantic structure behind humor from four perspectives:
incongruity, ambiguity, interpersonal effect and phonetic style. For that Yang
created a computational model. He also formulated a classifier to distinguish
between humorous and non-humorous instances [Yang et al., 2015].

In other researches, with the development of artificial neural networks, many
studies utilize the methods for humor recognition. Luke de Oliveira and
Alfredo applied recurrent neural network (RNN) to humor detection from reviews
in Yelp dataset. They also applied convolutional neural networks (CNNs) to
train a model and the results from model trained with CNNs have more accurate
humor recognition [De Oliveira and Rodrigo, 2015]. Recently, Bertero and Fung
proposed a first-ever attempt to employ a Long ShortTerm memory(LSTM) based
framework to predict humor in dialogues. They showed how the LSTM effectively
models the setup-punchline relation reducing the number of false positives and
increasing the recall [Bertero and Fung, 2016]. In a recent work, Chen and Lee
predicted audience’s laughter also using convolutional neural network. Their
work gets higher detection accuracy and is able to learn essential feature
automatically [Chen and Lee, 2018]. Among several prominent works, Peng-Yu
Chen and Von-Wun Soo build the humor recognizer by using CNNs with extensive
filter size and number, and the result shows higher accuracy from previous
CNNs models by conducting experiments on two different datasets. [Chen and
Soo, 2018].

##  3 Proposed Model

In this section, we describe the details of our proposed neural network model.
The goal of our proposed approach is to predict how much funny the edited news
headlines (humicroedit) is. We tried to train our model after data processing.
Figure 1 depicts an overview of our proposed model.

Figure 1: Proposed Model

At first, in a dataset, original sentences were changes by using edit words.
Then on edited sentences, pre-trained word embedding model was implemented to
obtain the high-quality distributed vector representations for our datasets.
Next, we apply the Bidirectional LSTMs (BiLSTMs) models to extract the higher
level feature sequences with sequential information from the edited news
headlines embedding. We employ an encoder pre-trained by Google News word2vec
model to encode each word into 300-dimensional feature vector. These feature
vectors are then sent to a Bidirectional LSTM module. Finally, the generated
output feature sequences from Bidirectional LSTMs fed into the fully-connected
prediction module to determine the prediction. Next, we describe each
component elaborately.

###  3.1 Embedding Layer

The Embedding layer in the leftmost part of Figure1 is initialized with random
weights and will learn an embedding for all of the words in the training
dataset. This flexible layer is defined as the first hidden layer of a
network. A pre-trained model used in embedding layer is nothing more than a
file containing tokens and their associated word vectors. The pre-trained
Google word2vec model was trained on Google news data (about 100 billion
words); it contains 3 million words and phrases and was fit using
300-dimensional word vectors with the size of 1.53 GB.

In our proposed framework, we utilize a pre-trained word embedding model based
on google news to obtain the high-quality distributed vector representations
of headlines. The dimensionality of the Embedding matrix will be $L\times D$,
where $L$ is the sentence length, and $D$ is the word-vector dimension.

###  3.2 Bidirectional LSTMs

Bidirectional Long Short Term Memory (BiLSTM) in the central part of Figure1
is a bidirectional version of LSTM. BiLSTM combines the forward hidden layer
with the backward hidden layer, which can access both the preceding and
succeeding contexts. BiLSTM neural network is resorted to attain the vector
representation of the input sentence, which can effectively capture the
semantics of the sentence. The final result from output layer of BiLSTM is
generated through combining the results produced by both RNN hidden layers
i.e. forward layer and backward layer. Following equations show the
mathematical formulation behind setting up the bidirectional hidden layer,
where $V$ is for vocabulary, $b$ as bias term of weight matrix $W$. The only
difference between these two relationships is in the direction of recursing
through the corpus.

$\overrightarrow{h}_{t}=f(\overrightarrow{W}x_{t}+\overrightarrow{V}\overrightarrow{h}_{t-1}+\overrightarrow{b})$
$\overleftarrow{h}_{t}=f(\overleftarrow{W}x_{t}+\overleftarrow{V}\overleftarrow{h}_{t-1}+\overleftarrow{b})$

###  3.3 Batch Normalization Layer

For training very deep neural networks, a technique named as Batch
normalization is used that standardizes the inputs to a layer for each mini-
batch. The effect of this method is to stabilize the learning process and to
dramatically reduce the number of training epochs required to train deep
networks. The batch normalization method is used to accelerate the training of
deep learning neural networks [Ioffe and Szegedy, 2015]. Batchnorm for short,
is proposed as a technique to help coordinate the update of multiple layers in
the model. It provides an elegant way to redesign or reparametrizing almost
every deep network. The reparametrization eliminates the issue of organizing
updates over several layers.

Essentially, when applying this layer with BiLSTM layer, the non-linear
activations of the LSTM are removed but not the gate activations. To increase
the stability of a neural network, batch normalization normalizes the output
of a previous activation layer by subtracting the batch mean and dividing by
the batch standard deviation.

###  3.4 Prediction module

In the end a linear activation layer is used as our task is a regression type
problem. The final layer of the neural network will have one neuron and the
value it returns is a continuous numerical value. Using RELU function as
activation layer can be a good option as the output of our task is non-
negative real numbers. For loss function, we employ mean square error (MSE),
which is defined as follows:

$MSE=\frac{1}{n}\sum_{i=1}^{n}(y_{i}-\hat{y}_{i})^{2}$

, where $n$ is the number of samples, $y_{i}$ is the true value of $i$-th
data, and $\hat{y_{i}}$ is the predicted value of $i$-th data. For
optimization, we adopt RMSprop (Room Mean Square propagation), as RMSprop is
adaptive and fast. In RMSprop, instead of taking cumulative sum of squared
gradients it takes the exponential moving average of gradients [Med, 2020].

##  4 Experiments and Evaluations

###  4.1 Dataset Collection

For Sub-task-1, two training datasets named Humicroedit [Hossain et al., 2019]
and Funlines [hossain-etal-2020-stimulating] were provided. But only
Humicroedits data was used. The training, validation, and test set of the news
headline dataset contains the 9653, 2420 and 2025 humicroedits, respectively.

###  4.2 Model configuration

In the following, we describe the set of parameters that we have used to
design our proposed neural network model. The framework which we used to
designed our model was based on TensorFlow [Abadi et al., 2016] and training
of our model is done on a GPU [Owens et al., 2008] to capture the benefit from
the efficiency of parallel computation of tensors. We used the 300-dimensional
word2vec Google news pre-trained model, where the maximum length of sentence
in given data was 20. We trained all models with 100 epochs with a batch size
of 128 and an initial learning rate 0.001 by RMSprop optimizer. Unless
otherwise stated, default settings were used for the other parameters.

###  4.3 Evaluation Results

To evaluate the performance of the system, the organizers used different
strategies and metrics for the Sub-tasks 1 and 2 [Hossain et al., 2020]. For
the Sub-task 1, Root Mean Square (RMSE), RMSE@10, RMSE@20 and RMSE@30 were
applied to estimate the performance of a system. Among three evaluation
measures, RMSE was considered as the primary evaluation measure for this task.

Figure 2: Our approach for Sub-task 2.

Figure 2 illustrates our approach used for Sub-task 2. In our approach, given
two edited headlines, we apply KdeHumor Model from Sub-task 1 to each edited
headline, and decides which edited headline is funnier by comparing the
predicted values. In Sub-task 2, model Accuracy is used as the evaluation
measure. Another auxiliary metric called the Reward is used. For a larger
funniness difference between the two headlines in a pair, Reward is higher for
a correct classification.

###  4.4 Experimental Results

We now evaluate the performance of our proposed method in this section. The
summarized results for Sub-task 1 and 2 are presented in Tables 1 and 2,
respectively.

Team Name | RMSE | RMSE@10
---|---|---
KdeHumor | 0.6164 | 1.0175
Farah | 0.5339 | 0.9091
HonoMi | 0.4972 | 0.7791
Heidy | 0.6833 | 1.0496
frietz58 | 0.7225 | 1.0634
zxchen | 0.5288 | 0.8636
Mjason | 0.5351 | 0.8748
Table 1:  (Sub-task 1) KdeHumor results with other selected team.

At first, we presented the performance of our proposed method denoted by team
name KdeHumor as well as presenting the performance of randomly chosen top-
ranked participated systems.

Team Name | Accuracy | Reward
---|---|---
KdeHumor | 0.5190 | 0.0271
Farah | 0.6088 | 0.1840
HonoMi | 0.6742 | 0.2987
HumorAAC | 0.3204 | -0.2177
Heidy | 0.4197 | -.0990
Table 2:  (Sub-task 2) KdeHumor results with other selected team.

##  5 Conclusion

In this paper, we presented our approach for SemEval-2020 Task 7: Assessing
Humor in Edited News Headlines. Detection of humor is not an easy task. We
tried to tackle the problem by employing deep learning techniques. We
conducted some experiments using different models for example we implemented
simple regression model, multilayer perceptron model but the model that gave
better result was KdeHumor model. In future, we are planning to incorporate
BERT model for further improvement.

## Acknowledgements

This work was partially supported by JSPS KAKENHI Grant Number 17H01746.

## References

  * [Abadi et al., 2016]  Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, et al.  2016\.  Tensorflow: A system for large-scale machine learning.  In 12th $\\{$USENIX$\\}$ Symposium on Operating Systems Design and Implementation ($\\{$OSDI$\\}$ 16), pages 265–283.
  * [Bertero and Fung, 2016]  Dario Bertero and Pascale Fung.  2016\.  A long short-term memory framework for predicting humor in dialogues.  2016 Conf. North Am. Chapter Assoc. Comput. Linguist. Hum. Lang. Technol. NAACL HLT 2016 - Proc. Conf., (January 2016):130–135.
  * [Chen and Lee, 2018]  Lei Chen and Chong Min Lee.  2018\.  Predicting Audience’s Laughter During Presentations Using Convolutional Neural Network.  (c):86–90.
  * [Chen and Soo, 2018]  Peng-Yu Chen and Von-Wun Soo.  2018\.  Humor Recognition Using Deep Learning.  pages 113–117.
  * [De Oliveira and Rodrigo, 2015]  Luke De Oliveira and Alfredo L Rodrigo.  2015\.  Humor detection in yelp reviews.  Retrieved on December, 15:2019.
  * [Hossain et al., 2019]  Nabil Hossain, John Krumm, and Michael Gamon.  2019\.  “president vows to cut <taxes> hair”: Dataset and analysis of creative text editing for humorous headlines.  In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers), pages 133–142, Minneapolis, Minnesota, June. Association for Computational Linguistics.
  * [Hossain et al., 2020]  Nabil Hossain, John Krumm, Michael Gamon, and Henry Kautz.  2020\.  Semeval-2020 Task 7: Assessing humor in edited news headlines.  In Proceedings of International Workshop on Semantic Evaluation (SemEval-2020).
  * [Ioffe and Szegedy, 2015]  Sergey Ioffe and Christian Szegedy.  2015\.  Batch normalization: Accelerating deep network training by reducing internal covariate shift.  arXiv preprint arXiv:1502.03167.
  * [Med, 2020]  2020\.  Understanding rmsprop — faster neural network learning.  https://towardsdatascience.com/understanding-rmsprop-faster-neural-network-learning-62e116fcf29a.  [Online; accessed 30-Apri- 2020].
  * [Owens et al., 2008]  John D Owens, Mike Houston, David Luebke, Simon Green, John E Stone, and James C Phillips.  2008\.  Gpu computing.  Proceedings of the IEEE, 96(5):879–899.
  * [Purandare and Litman, 2006]  Amruta Purandare and Diane Litman.  2006\.  Humor: Prosody analysis and automatic recognition for f* r* i* e* n* d* s.  In Proceedings of the 2006 Conference on Empirical Methods in Natural Language Processing, pages 208–215.
  * [Taylor and Mazlack, 2000]  Julia M Taylor and Lawrence J Mazlack.  2000\.  Computationally Recognizing Wordplay in Jokes Theories of Humor.  (1991).
  * [Yang et al., 2015]  Diyi Yang, Alon Lavie, Chris Dyer, and Eduard Hovy.  2015\.  Humor recognition and humor anchor extraction.  Conf. Proc. - EMNLP 2015 Conf. Empir. Methods Nat. Lang. Process., (September):2367–2376.


# Optimization of Heterogeneous Systems with AI Planning Heuristics and
Machine Learning: A Performance and Energy Aware Approach

Suejb Memeti  Blekinge Tekniska Hogskola, Department of Computer Science, 371
79 Karlskrona, Sweden; E-mail<EMAIL_ADDRESS>Sabri Pllana  Linnaeus
University, Department of Computer Science and Media Tech., 351 95 Vaxjo,
Sweden; E-mail<EMAIL_ADDRESS>
(Preprint)

###### Abstract

Heterogeneous computing systems provide high performance and energy
efficiency. However, to optimally utilize such systems, solutions that
distribute the work across host CPUs and accelerating devices are needed. In
this paper, we present a performance and energy aware approach that combines
AI planning heuristics for parameter space exploration with a machine learning
model for performance and energy evaluation to determine a near-optimal system
configuration. For data-parallel applications our approach determines a near-
optimal host-device distribution of work, number of processing units required
and the corresponding scheduling strategy. We evaluate our approach for
various heterogeneous systems accelerated with GPU or the Intel Xeon Phi. The
experimental results demonstrate that our approach finds a near-optimal system
configuration by evaluating only about 7% of reasonable configurations.
Furthermore, the performance per Joule estimation of system configurations
using our machine learning model is more than 1000x faster compared to the
system evaluation by program execution.

##  1 Introduction

Accelerators (such as, GPU or Intel Xeon Phi) are often used collaboratively
with general-purpose CPUs to increase the overall system performance and
improve energy efficiency. Currently, three of the top five most powerful
computers in the TOP500 list [8] are heterogeneous computers that use GPUs as
accelerators. Efficient programming of heterogeneous systems and splitting the
work between the CPUs and accelerators are domains of particular interest [7,
21, 2].

Due to different architectural characteristics and the large number of system
parameter configurations (such as, the number of threads, thread affinity,
workload partitioning between multi-core processors of the host and the
accelerating devices), achieving a good workload distribution that results
with optimal performance and energy efficiency on heterogeneous systems is a
non-trivial task [27, 33]. An optimal system configuration that results with
the highest throughput may not necessarily be the most energy efficient.
Furthermore, the optimal system configuration is most likely to change for
different types of applications, input problem sizes, and available resources.

Figure 1 depicts the process of system performance tuning. Traditionally the
process of finding the optimal system parameters involved many iterations of
selecting parameter values, program execution, and performance analysis
(Figure 1(a)). A brute-force search requires the program execution for all
parameter values of interest, and consequently for real-world programs and
systems it may take an unreasonable long time to find the optimum. In contrast
to brute-force search, an AI heuristic search [1, 34] enables to find a near-
optimum solution with fewer performance experiments based on nature-inspired
algorithms (for instance, simulated annealing [20] or Artificial Bee Colony
[18]). Figure 1(b) depicts our approach that combines AI heuristic parameter
value selection with a machine learning model for performance evaluation. The
advantage of our approach is two-fold:

  * •

heuristic parameter value selection reduces significantly the number of
performance experiments compared to brute-force search;

  * •

system performance evaluation using a model is usually much faster than the
program execution on a real-world system; moreover, availability of the system
under study during the performance optimization process is not required once
that the model has been developed.

(a) Brute-force search

(b) AI heuristic search

Figure 1: System performance tuning. (a) Evaluation of all possible
configurations with program execution, (b) AI heuristic selection of candidate
configurations and model-based evaluation.

In [26] authors provide a comprehensive review of literature that describes
various approaches for using heuristics or machine learning for optimization
of parallel computing systems from single-node systems [13, 19] to large scale
Grid and Cloud computing infrastructures [10, 14, 31, 38, 11, 32]. The related
work usually uses for system optimization either heuristics [30] or machine
learning [13] and there is insufficient research in combining these two
methods in particular for optimization of heterogeneous computing systems.
Preliminary results of our optimization approach are discussed in [25].
However, [25] was limited to only performance optimization of systems
accelerated with the Intel Xeon Phi. This paper extends our previous work as
follows,

  * •

we present a new machine learning model that estimates the performance per
Joule of the system (that is, it considers also energy consumption, beside the
performance);

  * •

we demonstrate that our approach is general-applicable and it is not limited
to Intel Xeon Phi, by applying our method also to GPU accelerated systems;

  * •

we demonstrate the applicability of our approach with two applications:
Pearson correlation coefficient and parallel pattern matching.

We use an AI heuristic search technique for parameter space exploration. The
optimization process involves generation of system configuration based on
random selection of parameter values and the system performance evaluation
using a machine learning model. Our method guides the process of intelligent
navigation through the parameter space towards the determination of the near-
optimal system configuration. As a result, our method requires only a small
fraction of possible performance experiments. The empirical evaluation of our
approach demonstrates that by using only about 7% of the total brute-force
experiments we are able to determine a near-optimal system configuration with
respect to the performance per Joule. Moreover, using our machine learning
model for evaluation of system configurations is more than 1000x faster than
the system evaluation by program execution.

This paper is organized as follows. Section 2 introduces computing systems and
applications that we use to illustrate our approach. We describe our
optimization approach in Section 3 and experimentally evaluate it in Section
4. We discuss the related research in Section 5. Section 6 provides a summary
of the paper and a description of the future work.

##  2 Heterogeneous Systems and Applications

In this section, we describe heterogeneous computing systems and applications
that we use in this paper to illustrate and evaluate our approach. In
addition, we describe input data-sets and parameters that define system
configurations.

###  2.1 Heterogeneous Computing Systems

Table 1 lists the major properties of heterogeneous computing systems Emil and
Ida that we use for experimentation in this paper.

Table 1: Major features of Ida and Emil. | Ida | Emil
---|---|---
| Intel Xeon E5 | GeForce GPU | Intel Xeon E5 | Intel Xeon Phi
Processor | E5-2650 v4 | GTX Titan X | E5-2695 v2 | 7120P
Core Frequency | 2.2 - 2.9 GHz | 1 - 1.1 GHz | 2.4 - 3.2 GHz | 1.2 - 1.3 GHz
Number of cores | 12 | 3072 | 12 | 61
Number of threads | 24 | / | 24 | 244
Cache size | 30 MB | / | 30 MB | 30.5 MB
Mem. Bandwidth | 76.8 GB/s | 336.5 GB/s | 59.7 GB/s | 352 GB/s
Memory size | 384 GB | 12 GB | 128 GB | 16 GB
TDP | 105 W | 250 W | 115 W | 300 W

Ida comprises two Intel Xeon E5-2650 v4 general purpose CPUs on the host, and
one GeForce GTX Titan X GPU as accelerator. Each CPU has 12 physical cores,
and each core of CPU supports two threads. In total, the host CPUs provide 24
cores and 48 threads. The GPU device has 24 Streaming Multiprocessors (SM),
and in total 3072 CUDA cores running at base frequency of 1 GHz.

Emil comprises two Intel Xeon E5-2695 v2 general purpose CPUs on the host, and
one Intel Xeon Phi 7120P co-processing device. Similar to Ida, Each CPU of
Emil has 12 cores that support two threads per core (known as logical cores)
that amounts to a total of 48 threads. The Xeon Phi device has 61 cores
running at 1.2 GHz base frequency; each core supports four hardware threads.
In total, the Xeon Phi supports 244 threads. The lightweight Linux operating
system installed on the Xeon Phi device runs on one of the cores.

The parameters that define the system configuration for our optimization
approach are shown in Table 2. All the parameters are discrete.

The considered system parameters for the PCC application executed on Ida
include the CPU workload and GPU workload. The workload fraction parameter can
have any number in the range $\\{0,..,100\\}$, such that if $60\%$ of the
workload is assigned for processing to the host CPU, the remaining
$100-60=40\%$ is assigned to the GPU device.

The considered parameters for the pattern matching application executed on
Emil include the number of CPU threads and accelerator threads, the CPU and
accelerator thread affinity, and the CPU and accelerator workload fraction.
The system parameter values for the host CPU threads are $\\{12,24,36,48\\}$,
whereas for the accelerator are $\\{60,120,180,240\\}$. The thread affinity
can vary between {none (0), compact (1), scatter (2)} for on host CPUs, and
{balanced (0), compact (1), scatter (2)} on accelerator. Similar to the Ida
system, the CPU and accelerator workload fraction can have values in the range
$\\{0,..,100\\}$.

Table 2: The set of considered parameters and their values for our target systems. System | Parameters | Parameter values
---|---|---
Ida | CPU workload fraction (CPU-W) | {0…100}
GPU workload fraction (GPU-W) | {100 - CPU-W}
Emil | CPU threads (CPU-T) | {12, 24, 36, 48}
Accelerator threads (ACC-T) | {60, 120, 180, 240}
CPU thread affinity (CPU-A) | {none (0), scatter (1), compact (2)}
Accelerator thread affinity (ACC-A) | {balanced (0), scatter (1), compact (2)}
CPU workload fraction (CPU-W) | {0…100}
Accelerator workload fraction (ACC-W) | {100 - CPU-W}

###  2.2 Applications

In this section, we describe two applications that we have prepared for
execution in hybrid mode (that is, the workload is shared between the host
CPUs and the accelerating device): (1) Pearson Correlation Coefficient (PCC)
and (2) parallel pattern matching. While the PCC application is adapted to
GPU-accelerated systems, the pattern matching application targets systems
accelerated with the Intel Xeon Phi.

####  2.2.1 Pearson Correlation Coefficient (PCC)

The Pearson Correlation Coefficient [5], which is also known as Pearson
product-moment correlation, is a statistical method for measuring the strength
of a relationship between two variables x and y. The correlation may be
positive (1), negative (-1), or there is no correlation (0). Positive
correlation means that if variable x is increased, there will be an increase
on the y variable, whereas the negative correlation means that an increase on
x would result with a decrease on y. A value of 0 for the correlation means
that the two variables are not related and increase on one variable has no
effect on the other one.

The strength of the relationship is measured using the absolute value of the
correlation, for instance, abs(-0.23) = 0.23 is a stronger relationship than
0.2.

The Pearson correlation coefficient is calculated using the following formula
[9]:

$\rho_{xy}=\frac{\sum_{i=1}^{n}(x_{i}-\bar{x})(y_{i}-\bar{y})))}{\sqrt{\sum_{i=1}^{n}(x_{i}-\bar{x})^{2})}\sqrt{\sum_{i=1}^{n}(y_{i}-\bar{y})^{2})}}$
(1)

The Pearson coefficient correlation has a wide range of applications. For
instance, [9] show its application to Magnetic Resonance Imaging (MRI) for
analyzing the functional connectivity of different brain regions.

In this paper, we apply the Pearson coefficient correlation to rows of
matrices. Note that for each row, we calculate the relationship with all other
rows below in the matrix. We added the glue code to the CPU and GPU PCC
implementations for enabling the hybrid execution. The input matrix is split
row-wise between the CPUs on the host and GPU.

It is worth to mention, that for this specific application, a 50% - 50%
workload distribution does not mean that the work is equally divided between
the host and the accelerator. This is because, for instance row 0 compares
itself with rows 1, 2, 3 … n. However, row 50 compares itself only with rows
51, 52, … n. As the program execution progresses through the rows of the
matrix, there is less and less work to perform.

####  2.2.2 Parallel Pattern Matching

Pattern matching is the process of finding multiple and overlapping
occurrences of sub-strings in a string. Common uses of pattern matching are in
search and replace functions, determining the location of a pattern, or
highlighting important information out of huge data sets [37]. Pattern
matching is also used in intrusion detection systems (to identify potential
threats) or computational biology (to identify the location of some patterns
in large DNA sequences).

In this paper, we use a pattern matching implementation [23, 24] to find sub-
sequences of strings in the real-world human DNA sequence (3.17GB) obtained
from the GenBank sequence database of the National Center for Biological
Information [28].

Please note that the 50%-50% workload distribution of the pattern matching
application means that the workload is equally divided between the host and
the accelerator.

##  3 Our Approach for Optimization of Heterogeneous Systems

In this section, we first motivate with one experiment the need for systematic
optimization approaches, and thereafter we describe our approach for
optimization of heterogeneous computing systems that combines AI heuristic
search techniques with machine learning.

###  3.1 Motivational Experiment

Heterogeneous computing systems may comprise several CPUs and accelerators.
Optimal work-sharing among available CPUs and accelerators is not obvious.
Furthermore, considering both execution time and energy consumption makes the
work-sharing problem more complex.

Figure 2 illustrates this problem with the PCC application running on the Ida
heterogeneous system that comprises two general-purpose CPUs and one GPU as
accelerator. For simplicity, we only show the results for a particular input
size (that is a matrix with 1024 rows and 8192 columns) and we only vary the
parameter CPU Fraction (that is the number of rows of the matrix mapped to the
CPU). Furthermore, we consider only CPU Fraction values that are product of
32.

From this experiment, we may derive the following insights:

  * •

When we consider the $Throughput~{}[MB/s]$ only, the optimal value for the CPU
fraction is 160 rows and rest of the work is mapped to the GPU (Figure 2(a)).

  * •

When optimizing for the $Power~{}[W]$ consumption, the execution on the CPU
only is preferable (Figure 2(b)); please note that also the overhead of data
transfers between CPU and GPU is considered for optimization.

  * •

When optimizing for $Energy~{}Efficiency~{}[MB/J]$ that considers both the
throughput and the power consumption, the optimal value for the CPU fraction
is 256 (Figure 2(c)).

(a) Max throughput is achieved when 160 rows are mapped to CPU and the rest to
GPU.

(b) All 1024 rows of matrix mapped to CPU results with the minimal power
consumption. Data transfer between CPU and GPU is prohibitive.

(c) Max energy efficiency is achieved when 256 rows are mapped to CPU and the
rest to GPU.

Figure 2: The CPU fraction that delivers the highest throughput (MB/s), lowest
power consumption (W), or highest energy efficiency (MB/J) is not the same.
The figure shows the experiments for the PCC application running on Ida for
matrix size 1024x8192. Measurements include also the performance overhead for
data transfers between CPU and GPU.

###  3.2 System Optimization with AI heuristics and Machine Learning (AML)

In this section, we propose an intelligent approach for determination of near-
optimal system configuration using AI heuristic search techniques and machine
learning. We contrast traditional approaches (also known as brute-force
search) that we refer to as Enumeration and Measurements (EM), with our
approach of combining AI heuristics with Machine Learning (AML).

Figure 3: Enumeration and measurements may help to determine the optimal
system configuration, however the required effort may be high due to the large
parameter space.

The EM technique (also known, as brute-force search) is depicted in Figure 3.
Compartment _Enumeration_ visualizes the process of selecting each feasible
value of various system parameters. Thereafter, for each combination of
parameter values the system performance is measured. Basically, EM involves
program execution on a real computing system for all feasible system parameter
values. For real-world programs and systems, EM may result with a very large
number of performance measurement experiments. Furthermore, program execution
on real computing systems may be time-consuming. Usually computing systems are
shared among various users and it may be impractical to block other users for
an unreasonable large amount of time while we execute our performance
experiments. Key EM drawbacks include,

  * •

a prohibitively large number of performance experiments,

  * •

requires a dedicated access to the system under study.

Determining the optimal system configuration using brute-force may be
prohibitively time expensive. The number of all possible system configurations
is a product of parameter value ranges,

$\prod_{i=1}^{n}R_{c_{i}}=R_{c_{1}}\times R_{c_{2}}\times..\times R_{c_{n}}$
(2)

where $C=\\{c_{1},c_{2},...,c_{n}\\}$ is a set of parameters and each $c_{i}$
has a value range $R_{c_{i}}$.

The aim is to find an optimization approach that is able to find a near-
optimal system configuration without having to measure the system performance
for all feasible parameter values. Our approach AML is depicted in Figure 4.
Key AML features include,

  * •

requires only a small fraction of possible performance experiments,

  * •

uses a machine learning model for performance evaluation.

Figure 4: Our approach uses an AI heuristic search technique for design space
exploration and machine learning for system performance evaluation.

AML uses a AI heuristic search technique for parameter space exploration. The
optimization process involves generation of system configuration based on
random selection of parameter values and the system performance evaluation
using a machine learning model. AML guides the process of intelligent
navigation through the parameter space towards the determination of the near-
optimal system configuration. As a result, AML requires only a small fraction
of possible performance experiments.

In what follows, we describe into more details the two most important
components of our approach, which are the Simulated Annealing heuristic for
design space exploration and boosted decision tree machine learning algorithm
for system performance evaluation.

####  3.2.1 Using Simulated Annealing (SA) for Parameter Space Exploration

Simulated Annealing (SA) [20] algorithm is a probabilistic optimization
technique for approximately determining the global optimum of a function. SA
is a popular technique for searching for optimum in a discrete space, where
gradient-based methods are not applicable. An important feature of SA is the
capability to find a global optimum also for functions that have many local
optimums.

SA is inspired from the process of annealing in metallurgy, a technique that
requires heating and controlled cooling of materials [34]. At high
temperatures $T$ particles of the material have more freedom of movement, and
as the temperature decreases the movement of particles is restricted. When the
material is cooled slowly, the particles are ordered in the form of a crystal
that represents minimal energy state of the material.

Algorithm 1 Our SA-based algorithm for exploration of system configuration
space.

1:$T$: SA parameter for accepting a system configuration as improvement

2:$x$: intermediate system configuration

3:$winner$: optimal system configuration

4:Initially evaluate CPU only and accelerator only solutions

5:Set the initial temperature $T$

6:Randomly generate the initial system configuration $x$

7:while $T>1$ do

8: Generate a new solution $x$’ by randomly modifying $x$

9: Evaluate $x$’ using our machine learning model

10: if $x$’ better than $x$ or acceptance criterion is met then

11: Replace $x$ with $x$’

12: update $winner$

13: end if

14: Decrease $T$

15:end while

Algorithm 1 shows the pseudo-code of SA-based method for system configuration
space exploration. A system configuration is determined by specific parameter
values (see Table 2.) Since the optimal workload distribution for some of the
experiments is to either run everything on the CPU or GPU, we initially
evaluate the CPU and accelerator only system configurations (line 4). The
process starts by initializing the temperature $T$ (line 5) and generating a
random system configuration $x$ (line 6). New solutions $x^{\prime}$ are
generated by randomly modifying the parameter values of current solution $x$
(line 8). We evaluate each of the generated system configurations using our
machine learning based prediction model (line 9). If the performance per Joule
of $x^{\prime}$ is better than the one of $x$, we replace $x$ with
$x^{\prime}$ unconditionally (line 11), otherwise we consider accepting
$x^{\prime}$ based on probability $p$ that is described by Equation 3.

$p=exp((x-x^{\prime})/T)$ (3)

The acceptance criterion (also known as Boltzmann’s probability distribution
[34]) allows simulated annealing to get out of local optimums in favor of a
global optimum. The temperature variable plays a decisive role in the
acceptance criterion. If the temperature $T$ is high, the system is more
likely to accept solutions that are worse than the current one. After each new
solution we decrease the temperature (line 14). Steps 8-14 are repeated as
long as the temperature $T$ is greater than one (line 15).

Figure 5: An example of the configuration space exploration for PCC on Ida
using our SA-based method. We may observe the presence of multiple local
optimums, and that the SA determined the global optimum.

Figure 5 illustrates the process of space exploration using SA for PCC
application on Ida system (see Section 2.2.1). While there are many local
optimums, our SA-based method manages to avoid them and finds the global
optimum.

Our _optimization goal_ is to maximize the performance per Joule, which is the
rate of computation that can be delivered for every consumed watt. In HPC
community, the standard metric for computationally-intensive application is
the floating point operations per second (FLOPS). As we target data-intensive
applications we use megabytes-per-second (MB/s) as a metric to indicate the
application’s throughput at run time. Beside the application performance we
also consider the energy consumption, therefore the optimization goal metric
is indicated by the total amount of data that can be processed for every
consumed watt, that is megabytes-per-watt-second (MB/Ws). Section 4.1
introduces evaluation metrics.

####  3.2.2 Using Machine Learning for Evaluation of System Configuration

In this section, we describe our supervised machine learning model that is
used for evaluation of performance and energy consumption of data-parallel
applications.

Our goal is to build a machine learning model that is able to predict the
energy efficiency for a target data-parallel application running on target
heterogeneous system based on characteristics of the given workload, and the
available resources. Instead of using analytical models that are tightly
coupled to a particular problem and environment, we use supervised machine
learning that can be trained for various data-parallel programs and
heterogeneous systems.

Preliminary results that compare various machine learning models (including
linear regression, Poisson regression, and boosted decision tree regression)
have suggested that for this particular type of problem the decision tree
regression machine learning algorithm results with highest prediction scores.
Hence, the decision tree regression is used in our approach.

We use the python science kit [29] (scikit-learn) to develop our machine
learning model. The decision tree regression model is boosted with the
Adaboost ensemble method, which results with further improvement with respect
to the prediction accuracy.

To validate the results, we have used two types of well-established validation
techniques, the k-fold cross-validation [3] (where k=10) and the train test
split technique (where 80% of the data is used for training and 20% of the
data is used for testing). In both cases, the model resulted with high (more
than 95%) prediction accuracy scores, which we consider acceptable for the
purpose of this study. Note that for evaluating the prediction model, we use
the R squared [36] metric, also known as the coefficient of determination,
which basically measures how close the data are to the fitted regression line.
Also, note that there is still room for improvement with respect to the
accuracy of the prediction model, for instance by tuning the hyper parameters,
or providing more training data (especially for the data-set for the example
of PCC running on GPU), which was out of scope of this paper.

The data pre-processing transforms the string-type input values (such as
thread affinity, which value is balanced, scatter, or compact) into integer
types (see Table 2 for the full set of parameters and their corresponding
values).

##  4 Evaluation

In this section, we evaluate experimentally our proposed optimization approach
for workload distribution on heterogeneous computing platforms.

###  4.1 Evaluation Metrics

In this section, we describe a collection of metrics that we use for
performance evaluation.

Time: is determined by the execution time of the slowest processing unit (that
is, CPU or accelerator),

$Time(s)=max(CPU_{Time},ACC_{Time})$ (4)

$CPU_{Time}$ is workload processing time on CPU, and $ACC_{Time}$ is workload
processing time on accelerator; $ACC_{Time}$ includes also the overhead for
transferring data between CPU and accelerator.

Throughput: is the amount of data processed within a given time,

$Throughput(MB/s)=Workload\\_size/Time$ (5)

We can also express the throughput separately for each available processing
unit as follows,

$\displaystyle CPU_{Throughput}(MB/s)=CPU_{Workload\\_size}/CPU_{Time}$ (6)
$\displaystyle ACC_{Throughput}(MB/s)=ACC_{Workload\\_size}/ACC_{Time}$

Energy: is the total energy consumed by all used processing unit. We use
MeterPU for energy measurement of host CPUs and GPUs, and x-MeterPU [22] for
energy measurements on Intel Xeon Phi.

$Energy(J)=CPU_{Energy}+ACC_{Energy}$ (7)

Power: is the consumed energy per time unit.

$\displaystyle CPU_{Power}(W)=CPU_{Energy}/CPU_{Time}$ (8) $\displaystyle
ACC_{Power}(W)=ACC_{Energy}/ACC_{Time}$ $\displaystyle
Power(W)=CPU_{Power}+ACC_{Power}$

$CPU_{Power}$ is power consumed by CPU, $ACC_{Power}$ is power consumed by
accelerator, and $Power$ is the total power consumption for workload
processing by CPU and accelerator.

Energy Efficiency: is the ratio of throughput to power,

$Energy\\_Efficiency(MB/J)=Throughput(MB/s)/Power(W)$ (9)

###  4.2 Performance Comparison of AML and EM

In this section we,

  * •

demonstrate experimentally the prediction accuracy of the ML-based performance
model for Ida and Emil,

  * •

demonstrate that it is significantly faster to evaluate the performance using
the ML-based prediction model in comparison to the execution of the real
program on Emil and Ida,

  * •

demonstrate that AML is capable to determine a near-optimal system
configuration with a small fraction of performance experiments in comparison
to EM (that is, brute force search).

####  4.2.1 Prediction Accuracy and Time-efficiency of the ML-based
Performance Model

To predict the energy efficiency of PCC application on Ida computing system,
we have developed a prediction model based on Boosted Decision Tree
Regression. In this section, we address two concerns: (1) are the model-based
predicted results comparable to those obtained by measurements, and (2) how
much faster is to evaluate the performance using the model compared to
measurement?

Figure 6 depicts measured and predicted energy efficiency for PCC application
on Ida system for various matrix sizes and fractions of matrix rows processed
by CPU. We may observe that there is good matching of results obtained from
the model with the measurement results.

Figure 6: Measured and predicted energy efficiency for PCC application on Ida
system. Energy efficiency is predicted for various matrix sizes and fractions
of matrix rows processed by CPU using our prediction model built based on
Boosted Decision Tree Regression.

EM involves running PCC on Ida to determine energy efficiency for various
parameter values. Execution of 2912 EM experiments in this study took 13404
seconds (approximately 3.7 hours). In contrast to EM, AML uses a machine
learning model to predict energy efficiency for various parameter values;
model-based evaluation lasts 3.5 milliseconds. Regarding time-efficiency, for
2912 performance experiments EM and AML compare as follows,

  * •

EM: 13404 [s]

  * •

AML: 10 [s]

We may observe that in this study AML is more than 1300 times faster than EM.

####  4.2.2 Determining Near-optimal System Configuration for PCC on Ida

In this section, we compare AML with EM with respect to search for a near-
optimal system configuration for PCC application on Ida computing system. The
optimization goal is the energy efficiency. Major properties of PCC and Ida
are described in Section 2. AML and EM optimization techniques are described
in Section 3.2.

Figure 7: Examples of estimation of near-optimal CPU Fraction with AML and EM
for PCC application on Ida. CPU Fraction is the percentage of matrix rows that
is mapped for processing to CPU. The optimization goal is the energy
efficiency.

We performed experiments for various numbers of matrix rows (16, 32, 64, 128,
256, 512, 1024, 2048, 4096, 8192) and columns (16, 32, 64, 128, 256, 512,
1024, 2048, 4096, 8192, 16384, 32768, 65536). The matrix elements are
initialized with random values of float type. Note that the performance
results reported in this section do not include the effort required to
initialize the matrix. Considering parameter values ranges in this study there
are,

  * •

14677 AML experiments, and

  * •

212914 EM experiments.

Figure 7 depicts examples of estimation of near-optimal CPU fraction with AML
and EM for PCC application on Ida for various matrix sizes. CPU Fraction is
the percentage of matrix rows that is mapped for processing to CPU; the rest
of matrix is processed by GPU. The optimization goal is the energy efficiency
(see Section 4.1).

Please note that the Figure 7 shows only examples of results where the CPU
fraction determined by AML differs from the one determined by EM; that is only
24 matrix sizes out of 130 in total. The data points depicted as small
rectangles correspond to the EM results, whereas the data points depicted as
small circles show the AML values. The vertical red lines show the difference
between AML and EM.

We may observe that in most of the cases AML can determine near-optimal CPU
fraction that yields the energy efficiency that is comparable to the one
determined by EM. For 106 matrix sizes there was no difference between AML and
EM.

Table 3: Examples of achieved energy efficiency with EM and AML for various workload sizes of PCC application on Ida. Workload: Matrix (R x C) | EM | AML | $|Difference|$
---|---|---|---
512 x 32768 | 3.169 | 3.169 | 0.00000
1024 x 4096 | 2.072 | 2.067 | 0.00474
1024 x 8192 | 2.021 | 2.021 | 0.00000
1024 x 16384 | 1.750 | 1.744 | 0.00552
2048 x 2048 | 1.186 | 1.076 | 0.10936
2048 x 4096 | 1.079 | 1.059 | 0.01982
2048 x 8192 | 0.994 | 0.990 | 0.00362
4096 x 128 | 0.439 | 0.433 | 0.00587
4096 x 256 | 0.633 | 0.561 | 0.07285
4096 x 512 | 0.602 | 0.589 | 0.01367
4096 x 1024 | 0.597 | 0.580 | 0.01656
4096 x 2048 | 0.569 | 0.547 | 0.02169
4096 x 4096 | 0.529 | 0.523 | 0.00684
4096 x 8192 | 0.522 | 0.505 | 0.01669
4096 x 16384 | 0.487 | 0.487 | 0.00034
8192 x 128 | 0.233 | 0.211 | 0.02153
8192 x 256 | 0.252 | 0.243 | 0.00980
8192 x 512 | 0.280 | 0.268 | 0.01191
8192 x 1024 | 0.298 | 0.276 | 0.02204
8192 x 2048 | 0.279 | 0.270 | 0.00907
8192 x 4096 | 0.268 | 0.260 | 0.00828
8192 x 8192 | 0.267 | 0.256 | 0.01145
8192 x 16384 | 0.255 | 0.252 | 0.00338
8192 x 65536 | 0.529 | 0.529 | 0.00000

The highest observed difference is 15.6% in the case of matrix size
8192x16384; the EM suggests to map all the matrix rows to the GPU (that is,
CPU fraction is 0), but the AML suggests to map 15.6% of the workload to the
CPU and the rest to the GPU . While the CPU fraction difference of 15.6% is
substantial, the difference between AML and EM with respect to the achieved
optimization goal (that is, energy efficiency) is insignificant:

  * •

AML achieved energy efficiency: 0.252 (MB/J)

  * •

EM achieved energy efficiency: 0.255 (MB/J)

The corresponding energy efficiency results for workload sizes depicted in the
Figure 7 are listed in Table 3. We may observe that the difference between EM
and AML with respect to energy efficiency is not significant; that is AML is
capable of determining system configurations that result with energy
efficiency comparable to EM.

####  4.2.3 Determining Near-optimal System Configuration for Parallel Pattern
Matching on Emil

In this section, we compare AML with EM with respect to search for a near-
optimal system configuration for parallel pattern matching on Emil computing
system. The optimization goal is the energy efficiency. We have described
parallel pattern matching and Emil computing system in Section 2.

In this study, despite the fact that we tested only what we considered
reasonable parameter values (listed on Table 2 in Section 2.1), 5590
experiments were required when we used EM. Our heuristic-guided approach AML
that is based on Simulated Annealing and Machine Learning leads to
comparatively good performance results, while requiring only a relatively
small set of experiments to be performed.

Figure 8: Comparison of AML with EM for various percentages of possible system
configurations of Emil. Note that the total number of configurations is 5590
and by trying only about 7% of all configurations using AML we manage to find
a near optimal system configuration that delivers up to 97.55% of the energy
efficiency that is determined by the EM by trying all possible configurations.

Figure 8 depicts the energy efficiency of the pattern matching application
when running using the system configuration suggested by AML. The solid
horizontal line indicates the energy efficiency of the system configuration
determined by EM. EM finds the optimal solution by a kind of brute-force
search. We may observe that after evaluating only about 7% of the possible
configurations, AML is able to determine a system configuration that results
with energy efficiency that is close to the one of the system configuration
determined by EM. The difference between AML and EM with respect to the
achieved optimization goal (that is, energy efficiency) is as follows:

  * •

AML achieved energy efficiency: 43,87 (MB/J)

  * •

EM achieved energy efficiency: 44,97 (MB/J)

Please note that AML uses a stochastic search algorithm for global
optimization and to avoid ending at a local optima during the search sometimes
it accepts a worse system configuration (see Section 3.2.1).

##  5 Related Work

In this section, first we discuss related research that addresses optimization
of heterogeneous computing systems. We are interested to know whether the
optimization involves host CPUs and device accelerators (such as, GPU or Intel
Xeon Phi), AI heuristics are used for searching for optimal system parameters,
machine learning is used for optimization, and whether the optimization goals
are power / energy consumption and performance. A summary of related work is
provided in Table 4. Thereafter, we briefly describe how our approach that is
presented in this paper differs from the related work.

Huang et al. [17] propose a strategy for improvement of GPU power consumption
based on dynamic voltage and frequency scaling (DVFS). They developed a DVFS
model for energy optimization based on proportional-integral-derivative neural
network (PIDNN). Three NVIDIA GPUs are used for experimental evaluation:
Quadro FX 380, GTX 460, GTX 680. Authors have applied their method only to
single GPU systems, and they plan to study multi-GPU systems in future.

Haidar et al. [15] study the relationship between energy consumption and
performance for various BLAS kernels on Intel Xeon Phi Knights Landing (KNL).
Authors use the PAPI library for power and performance monitoring. A
conclusion of this study is that to achieve a good performance with minimal
power consumption it is important to maximize the use of MCDRAM memory on KNL
device and minimize the use of DDR4 RAM of the system.

In [19], Kasichayanula et al. propose a software approach for real-time energy
consumption measurements and analysis on individual GPU components. They use
small subset of real-time statistics, and are able to infer about the activity
of other micro-components using a linear-regression based prediction model.

Pereira et al. [30] propose an approach for determining optimal CUDA block
dimension for execution of a wind field calculation program on GPU. Authors
use particle swarm optimization (PSO) heuristic to find the CUDA block
dimension that results with minimal program execution time. Using PSO they
achieve 2x speed up compared to the previous GPU version of the program.

Hong and Kim [16] proposed an integrated energy and performance prediction
model for GPU accelerators that is able to predict the optimal number of
processors for a given memory-bound application that results with the peak
performance and lowest energy consumption. Their experimental results with
five various memory bound application benchmarks on a GPU architecture show up
to 10% reduction of energy consumption.

Cerotti et al. [6] study the performance modeling of GPU accelerated computing
systems. Authors present a language for description of system components and
workload elements. Properties of system components are described with a set of
parameters. For modeling systems that comprise CPUs and GPUs authors use
queuing networks.

Benkner et al. [4] developed PEPPHER that is a programming framework for
heterogeneous systems that comprise CPUs and accelerators (such as, GPU or
Intel Xeon Phi). PEPPHER involves source-to-source compilation and a run-time
system capable of mapping code components on an extensible set of target
processor architectures. To address the performance portability, PEPPHER uses
optimized component implementation variants for each execution context.
Regression analysis of historical performance data from previous component
executions is used to continuously learn associated performance models for
run-time scheduling decisions.

The distribution of computation in heterogeneous systems accelerated with GPU
devices for energy optimization has been studied by Ge et al. [12]. Authors
propose the so called PEACH model that distributes the computations by
splitting the workload between host and accelerators, and adaptively schedules
these computations with regards to the computation units speed and energy
consumption. Authors use analytical models to optimally determine the workload
distribution and scheduling that aims at minimal energy consumption and best
performance.

Ravi and Agrawal [35] propose a dynamic scheduling framework for heterogeneous
computing systems that comprise various processing elements (such as, CPU or
GPU). Authors specifically address data parallel loops. Scheduling decisions
consider architectural trade-offs, computation and communication patterns.
Performance optimization aims at minimizing data transfer between CPU and GPU,
reducing the number of kernel invocation on GPU, and reducing the idle time of
resources.

Grewe and O’Boyle [13] study task partitioning for OpenCL programs. Authors
address task partitioning and mapping on heterogeneous systems that comprise a
CPU and a GPU. Static analysis is used for code features extraction (such as,
int and float operations, or data transfer size), and thereafter a machine
learning model that is developed based on support vector machines (SVM) is
used to map code features to work partition. The model predicts the
percentages of work that should be assigned to GPU and CPU to achieve optimal
performance.

Table 4: A summary of related work with respect to whether optimization involves host CPUs and device accelerators (such as, GPU or Intel Xeon Phi), heuristic search is used for optimal system parameters, machine learning is used for optimization, and whether the optimization goals are power / energy consumption and performance. Reference |  Host |  Device |  Heuristic search |  Machine learning |  Power, energy |  Performance
---|---|---|---|---|---|---
Huang [17] |  no |  yes |  no |  yes |  yes |  no
Haidar [15] |  no |  yes |  no |  no |  yes |  yes
Kasichayanula [19] |  no |  yes |  no |  yes |  yes |  no
Pereira [30] |  no |  yes |  yes |  no |  no |  yes
Hong [16] |  no |  yes |  no |  no |  yes |  yes
Cerotti [6] |  yes |  yes |  no |  no |  no |  yes
Benkner [4] |  yes |  yes |  no |  yes |  no |  yes
Ge [12] |  yes |  yes |  no |  no |  yes |  yes
Ravi [35] |  yes |  yes |  no |  no |  no |  yes
Grewe [13] |  yes |  yes |  no |  yes |  no |  yes
This paper |  yes |  yes |  yes |  yes |  yes |  yes

Compared to the related work summarized in Table 4, in addition to using
machine learning for modeling and evaluation of performance and power
consumption, we use heuristics to search for a near-optimal system
configuration. In a large parameter space for system configuration, heuristics
have advantages (such as, time to solution or general applicability) compared
to time-prohibitive brute-force approaches that aim at considering all
possible configurations or compared to ad hoc approaches that are limited to a
specific case.

##  6 Summary and Future Work

Heterogeneous architectures are a viable way of building computer systems with
a high peak performance and a lower energy consumption. Optimal work-sharing
among available CPUs and accelerators is not obvious, and considering both
performance and energy consumption further complicates the work-sharing
problem. We have presented an approach that uses a probabilistic heuristic
search technique for parameter space exploration. The optimization process
involves generation of system configuration based on random selection of
parameter values and the system performance evaluation using a machine
learning model. We have evaluated our approach experimentally on heterogeneous
systems that are accelerated with the Intel Xeon Phi or GPU for two
applications: Pearson correlation coefficient and parallel pattern matching.
In our experiments we have observed that,

  * •

the more than 95% accuracy of the developed machine learning model enables to
inform the search for optimal system configuration,

  * •

by considering only about 7% of the possible system configurations our method
finds a near-optimal configuration with respect to performance per Joule;

  * •

our method is 1300x faster than the brute-force search combined with
measurement of program execution;

  * •

applicability of our approach is not limited to one type of accelerator or
application; the model can be trained for various accelerated systems.

Future work will study work-sharing in the context of the Edge, Fog and Cloud
systems.

## References

  * [1] E. Alba.  How can metaheuristics help software engineers?  In T. E. Colanzi and P. McMinn, editors, Search-Based Software Engineering, pages 89–105, Cham, 2018. Springer International Publishing.
  * [2] V. Amaral, B. Norberto, M. Goulão, M. Aldinucci, S. Benkner, A. Bracciali, P. Carreira, E. Celms, L. Correia, C. Grelck, H. Karatza, C. Kessler, P. Kilpatrick, H. Martiniano, I. Mavridis, S. Pllana, A. Respício, J. Simão, L. Veiga, and A. Visa.  Programming languages for data-intensive HPC applications: A systematic mapping study.  Parallel Computing, 91:102584, 2020.
  * [3] D. Anguita, L. Ghelardoni, A. Ghio, L. Oneto, and S. Ridella.  The’k’in k-fold cross validation.  In ESANN, 2012.
  * [4] S. Benkner, S. Pllana, J. Traff, P. Tsigas, U. Dolinsky, C. Augonnet, B. Bachmayer, C. Kessler, D. Moloney, and V. Osipov.  PEPPHER: Efficient and Productive Usage of Hybrid Computing Systems.  Micro, IEEE, 31(5):28–41, 09 2011.
  * [5] S. Boslaugh.  Statistics in a nutshell: A desktop quick reference.  ” O’Reilly Media, Inc.”, 2012.
  * [6] D. Cerotti, M. Gribaudo, M. Iacono, and P. Piazzolla.  Modeling and analysis of performances for concurrent multithread applications on multicore and graphics processing unit systems.  Concurrency and Computation: Practice and Experience, 28(2):438–452, 2016.
  * [7] P. Czarnul.  Parallel Programming for Modern High Performance Computing Systems.  CRC Press, Boca Raton, Florida, USA, 2018.
  * [8] J. J. Dongarra, H. W. Meuer, E. Strohmaier, et al.  TOP500 Supercomputer Sites.  http://www.top500.org/, Nov. 2020.  Accessed: Jan. 2021.
  * [9] T. Eslami, M. G. Awan, and F. Saeed.  Gpu-pcc: A gpu based technique to compute pairwise pearson’s correlation coefficients for big fmri data.  In Proceedings of the 8th ACM International Conference on Bioinformatics, Computational Biology, and Health Informatics, pages 723–728, 2017.
  * [10] T. Fahringer, A. Jugravu, S. Pllana, R. Prodan, C. Seragiotto Jr, and H.-L. Truong.  Askalon: a tool set for cluster and grid computing.  Concurrency and Computation: Practice and Experience, 17(2‐4):143–169, 2005.
  * [11] T. Fahringer, S. Pllana, and J. Testori.  Teuta: Tool Support for Performance Modeling of Distributed and Parallel Applications.  In Computational Science - ICCS 2004, volume 3038 of Lecture Notes in Computer Science, pages 456–463. Springer Berlin Heidelberg, 2004.
  * [12] R. Ge, X. Feng, M. Burtscher, and Z. Zong.  Performance and energy modeling for cooperative hybrid computing.  In Networking, Architecture, and Storage (NAS), 2014 9th IEEE International Conference on, pages 232–241, Aug 2014.
  * [13] D. Grewe and M. F. O′Boyle.  A static task partitioning approach for heterogeneous systems using OpenCL.  In Compiler Construction, pages 286–305. Springer, 2011.
  * [14] D. Grzonka, A. Jakóbik, J. Kołodziej, and S. Pllana.  Using a multi-agent system and artificial intelligence for monitoring and improving the cloud performance and security.  Future Generation Computer Systems, 86:1106–1117, 2018.
  * [15] A. Haidar, H. Jagode, A. YarKhan, P. Vaccaro, S. Tomov, and J. Dongarra.  Power-aware computing: Measurement, control, and performance analysis for Intel Xeon Phi.  In 2017 IEEE High Performance Extreme Computing Conference (HPEC), pages 1–7, 2017.
  * [16] S. Hong and H. Kim.  An integrated gpu power and performance model.  In ACM SIGARCH Computer Architecture News, volume 38, pages 280–289. ACM, 2010.
  * [17] Y. Huang, B. Guo, and Y. Shen.  Gpu energy consumption optimization with a global-based neural network method.  IEEE Access, 7:64303–64314, 2019.
  * [18] D. Karaboga and B. Basturk.  Artificial Bee Colony (ABC) Optimization Algorithm for Solving Constrained Optimization Problems.  In Proceedings of the 12th International Fuzzy Systems Association World Congress on Foundations of Fuzzy Logic and Soft Computing, IFSA 07, pages 789––798, Berlin, Heidelberg, 2007. Springer-Verlag.
  * [19] K. Kasichayanula, D. Terpstra, P. Luszczek, S. Tomov, S. Moore, and G. D. Peterson.  Power aware computing on gpus.  In Application Accelerators in High Performance Computing (SAAHPC), 2012 Symposium on, pages 64–73. IEEE, 2012.
  * [20] S. Kirkpatrick, D. Gelatt, and M. Vecchi.  Optimization by Simulated Annealing.  Science, 220(4598):671–680, 1983.
  * [21] S. Markidis, S. Chien, E. Laure, I. Peng, and J. Vetter.  NVIDIA Tensor Core Programmability, Performance Precision.  In 2018 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), pages 522–531, 2018.
  * [22] S. Memeti, L. Li, S. Pllana, J. Kolodziej, and C. Kessler.  Benchmarking OpenCL, OpenACC, OpenMP, and CUDA: Programming Productivity, Performance, and Energy Consumption.  In Proceedings of the 2017 Workshop on Adaptive Resource Management and Scheduling for Cloud Computing, ARMS-CC ’17, pages 1–6, New York, NY, USA, 2017. ACM.
  * [23] S. Memeti and S. Pllana.  PaREM: A Novel Approach for Parallel Regular Expression Matching.  In 17th International Conference on Computational Science and Engineering (CSE-2014), pages 690–697, Chengdu, China, Dec 2014.
  * [24] S. Memeti and S. Pllana.  Accelerating dna sequence analysis using intel(r) xeon phi(tm).  In 2015 IEEE Trustcom/BigDataSE/ISPA, volume 3, pages 222–227. IEEE, 2015.
  * [25] S. Memeti and S. Pllana.  Combinatorial optimization of work distribution on heterogeneous systems.  In 45th International Conference on Parallel Processing Workshops (ICPPW), pages 151–160, Aug 2016.
  * [26] S. Memeti, S. Pllana, A. Binotto, J. Kołodziej, and I. Brandic.  Using meta-heuristics and machine learning for software optimization of parallel computing systems: a systematic literature review.  Computing, Apr 2018.
  * [27] S. Mittal and J. S. Vetter.  A Survey of CPU-GPU Heterogeneous Computing Techniques.  ACM Comput. Surv., 47(4):69:1–69:35, July 2015.
  * [28] NCBI.  National Center for Biotechnology Information U.S. National Library of Medicine.  http://www.ncbi.nlm.nih.gov/genbank, 2015.  Accessed: Dec. 2015.
  * [29] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, et al.  Scikit-learn: Machine learning in python.  the Journal of machine Learning research, 12:2825–2830, 2011.
  * [30] C. Pereira, A. Pinheiro, and R. Schirru.  Automatic block dimensioning on GPU-accelerated programs through particle swarm optimization.  Information and Software Technology, 123:106299, 2020.
  * [31] S. Pllana, S. Benkner, E. Mehofer, L. Natvig, and F. Xhafa.  Towards an Intelligent Environment for Programming Multi-core Computing Systems.  In Euro-Par Workshops, volume 5415 of Lecture Notes in Computer Science, pages 141–151. Springer, 2008.
  * [32] S. Pllana, I. Brandic, and S. Benkner.  A Survey of the State of the Art in Performance Modeling and Prediction of Parallel and Distributed Computing Systems.  International Journal of Computational Intelligence Research (IJCIR), 4(1):17–26, 01 2008.
  * [33] S. Pllana and F. Xhafa.  Programming Multicore and Many-core Computing Systems.  John Wiley & Sons, Inc., Hoboken, New Jersey, USA, 1 edition, 2017.
  * [34] W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery.  Numerical Recipes 3rd Edition: The Art of Scientific Computing.  Cambridge University Press, New York, 3 edition, 2007.
  * [35] V. T. Ravi and G. Agrawal.  A dynamic scheduling framework for emerging heterogeneous systems.  In High Performance Computing (HiPC), 2011 18th International Conference on, pages 1–10. IEEE, 2011.
  * [36] O. Renaud and M.-P. Victoria-Feser.  A robust coefficient of determination for regression.  Journal of Statistical Planning and Inference, 140(7):1852–1862, 2010.
  * [37] S. Vitabile, M. Marks, D. Stojanovic, S. Pllana, J. M. Molina, M. Krzyszton, A. Sikora, A. Jarynowski, F. Hosseinpour, A. Jakobik, A. Stojnev Ilic, A. Respicio, D. Moldovan, C. Pop, and I. Salomie.  Medical Data Processing and Analysis for Remote Health and Activities Monitoring, pages 186–220.  Springer International Publishing, Cham, 2019.
  * [38] F. Xhafa, J. A. Gonzalez, K. P. Dahal, and A. Abraham.  A ga(ts) hybrid algorithm for scheduling in computational grids.  In E. Corchado, X. Wu, E. Oja, Á. Herrero, and B. Baruque, editors, Hybrid Artificial Intelligence Systems, pages 285–292, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg.