\section{Recommendation Background}~\label{sec:background}
Recommendation is the task of suggesting new content to users based on their preferences and prior content interactions. Recommendation is used in many popular internet services (e.g., search, entertainment streaming, e-commerce) to improve user experience by enabling personalization.
The main challenge for recommendation systems is accurately modeling users' preferences based on sparse training data --- users often explore only a tiny fraction of all available items.
This section explores how recommendation systems have evolved over time.
More specifically, we discuss the semantics of classical recommendation approaches and important algorithmic components of state-of-the-art deep learning methods.

\begin{figure}[t]
    \centering
    \includegraphics[width=\linewidth]{figures/model_evolution_8.png}
    \caption{\textbf{Evolution of Recommendation Systems.} Traditional collaborative filtering (\textbf{top}) models user preferences as two (user and item) embedding tables and inner product between table entries. Deep learning based methods (\textbf{bottom}) still leverage embedding tables -- though the number of tables, number of lookups per table, latent dimension, and subsequent matrix operations (gray blocks) are all highly configurable.}
    \label{fig:model_evolution}
    \vspace{-1em}
\end{figure}

\input{tables/rec_models_wide}

\subsection{Classical Recommendation Systems}
Classical recommendation systems are generally categorized as either content-based filtering or collaborative filtering.
Content-based filtering recommends content based on a user's personal preferences and item interaction history while collaborative filtering exploits preference similarity across users.
Content-based filtering models each user as feature vector $\mathbf{u}_i \in \mathbb{R}^{k}$ and each item as feature vector $\mathbf{v}_j \in \mathbb{R}^{k}$, where $k$ is the number of learned features (i.e., latent dimension) for each user and item.

Collaborative filtering represents historical interactions between $N$ users and $M$ items as a partially-observed matrix $R \in \mathbb{R}^{N \times M}$, where $r_{ij}$ is the historical interaction between user $i$ and item $j$.
To compensate for unobserved entries, collaborative filtering approximates $R$ with matrix factorization (MF) as a user matrix $U \in \mathbb{R}^{N \times k}$ and item matrix $V \in \mathbb{R}^{M \times k}$, where $k$ is again the latent dimension:
\begin{align}
    R \approx \hat{R} \equiv UV^T
    \label{eqn:mf}
\end{align}
As shown in Figure \ref{fig:model_evolution} (top), to predict the interaction score of user $i$ with item $j$ ($r_{ij}$) we would have to find the inner product of the $i^{th}$ row of $U$ and the $j^{th}$ row of $V$:
\begin{align}
    r_{ij} \approx \hat{r_{ij}} \equiv {\mathbf{u}_i}^T{\mathbf{v}_j}
    \label{eqn:mf_inference}
\end{align}

\subsection{Deep Recommendation Systems}
In order to leverage the abundance of user data and model complex user-item interactions, recommendation systems have shifted from the aforementioned techniques, e.g., \cite{Sarwar2001CF, funk2006matrix}, to deep-learning based approaches\cite{zhang2019recsurvey}.
Figure~\ref{fig:model_evolution} (bottom) shows the general deep-learning based model architecture; the embedding tables and components shaded in gray (i.e., DNN-stacks and pooling/interaction layers) are highly configurable:

\begin{itemize}[leftmargin=*]
    \item \textbf{Embedding Tables.} Deep recommendation systems rely on embedding tables (Figure~\ref{fig:model_evolution}, red and blue outline) to encode information about users and items. Every input sample has categorical components (e.g., movies a user likes) -- represented as multi-hot encoded vectors -- that are processed as table lookups.
    Embedding tables are configured based on the

    number of lookups, number of entries per table, number of tables, and latent dimension of embedding vectors.
    As table sizes increase ($\sim$GBs), access patterns become increasingly sparse -- leading to irregular memory accesses that make system optimizations challenging.
    \item \textbf{DNN Stacks.} In addition to categorical features, input samples also include continuous features (e.g., user age) that are processed directly by DNN stacks. DNN stacks range from vanilla fully-connected (FC) layers to more complicated architectures (e.g., autoencoders, CNNs, RNNs).

    \item \textbf{Feature Interaction Layers.} To unify outputs from embedding table lookups and DNN stacks, deep recommendation systems have feature interaction layers that range from simple concatenation to attention mechanisms.
\end{itemize}

\section{Discussion}~\label{sec:discussion}

\section{Conclusion}~\label{sec:conclusion}
It is important to characterize deep recommendation models across different layers in the execution stack because this helps us better understand the bottlenecks that arise from our evaluations. By understanding more about these bottlenecks and how they realize themselves at different levels (i.e., as operators in Caffe2 and as inefficiencies of different CPU components), we can intelligently design future hardware that optimizes for deep recommendation inference.
\section{Acknowledgements}~\label{sec:acknowledgements}
We would like to thank the anonymous reviewers for their thoughtful comments and suggestions.
We would also like to thank Glenn Holloway and Emma Wang for their valuable feedback.
This work was sponsored in part by NSF CCF-1533737 and a National Science Foundation Graduate Research Fellowship (NSFGRFP).
\section{Related Work}~\label{sec:related_work}
\textbf{Analysis and optimizations for recommendation systems.} Recommendation systems have recently come under the spotlight for computer systems researchers. As mentioned earlier, a few recent works explore near-memory processing techniques for recommendation models dominated by table lookup operations.
TensorDimm evaluates near-data processing enabled custom DIMM modules on recommendation models similar to RM1-3~\cite{rhu2019tensordimm};
RecNMP evaluates a set of techniques centered around memory-side caching on production-representative embedding traces~\cite{ke2019recnmp}.
Ginart et al. and Shi et al.~\cite{ginart2019mixed, shi2019compositional} compresses embedding tables in recommendation models while maintaining the model accuracy.
Centaur extends near-memory processing designs to also account for the MLP layers through a chiplet-based accelerator design~\cite{hwang2020centaur}.
Other works have explored at-scale optimizations~\cite{gupta2020architectural}:
DeepRecSys explores different optimizations at the datacenter scale; the recommendation suite evaluated throughout this paper is from DeepRecSys's open sourced implementations~\cite{gupta2020deeprecsys}. Other work has started to explore implications of training~\cite{kalamkar2020optimizing, naumov2020fbtraining}.
In contrast, this paper focuses on purely characterizing the recommendation suite introduced in~\cite{gupta2020deeprecsys}. To the best of our knowledge, this is the first detailed microarchitectural characterization of deep recommendation systems.

\textbf{DNN benchmarks and accelerator designs.} Current benchmarks and characterizations for DNNs primarily focus on FC, CNNs, and RNNs~\cite{adolf2016fathom,wei2019benchmarking,coleman2017dawnbench,zhu2018benchmarking, mlperf-reco-advisory, mlperf}. Building upon the performance bottlenecks derived from these studies, a variety of hardware solutions have been proposed to optimize for traditional DNNs~\cite{scnn,rhu2016vdnn,kwon2018beyond,choi2019prema,gupta2019masr,eyeriss,eie, minerva,gonzalez2018pact,fletcher2018micro,fletcher2019micro,dadiannao,cambricon,sharma2016dnnweaver,du2015shidiannao,liu2015pudiannao,chi2016prime,shafiee2016isaac,kim2016neurocube,likamwa2016redeye,mahajan2016tabla,gao2017tetris,maxnvm,albericio2017bit}.
While these DNNs share the operators introduced in Section~\ref{sec:software}, recommendation models present them in unique ratios and model architecture organizations.
\section{Algorithms and Software Characterization}~\label{sec:software}
To better understand the system performance trends, in this section, we provide an algorithmic characterization of the different models and use cases.
More specifically, we breakdown Caffe2 operators' usage for inference across the eight models and batch sizes.
Furthermore, we show that the algorithmic bottlenecks are consistent across deep-learning frameworks (i.e., Caffe2 and Tensorflow), demonstrating that the performance trends are fundamental to model architectures.

\subsection{Operator Breakdown}

Operator usage breakdowns allow us to quantify the importance of each operator and compare them across model architectures in a \textit{unified} manner. This is extremely important as model architectures for deep recommendation systems are rapidly evolving. In fact, these model architectures often mirror recent advances in deep learning\cite{zhang2019recsurvey}. Figure \ref{fig:op_breakdown} shows the operator breakdown of the eight models -- implemented in Caffe2 -- across four different batch sizes on Broadwell, Cascade Lake, GTX 1080 Ti, and T4 machines. We see that different generations of hardware (top versus bottom rows) and classes of hardware (left versus right columns) alter operator usage breakdown. The important observations are:

\textbf{1) GPUs accelerate models dominated by \texttt{FC} operators on CPUs but struggle with those bottlenecked by \texttt{SparseLengthsSum} on CPUs.} Since GPUs contain large arrays of SMs that execute matrix multiplication efficiently, models with \texttt{FC}-dominated runtimes show the most acceleration (see: NCF, RM3, WnD, and MT-WnD).
On the other hand, models with CPU runtimes bottlenecked by the \texttt{SparseLengthsSum} operator do not perform as well on GPUs.
The \texttt{SparseLengthsSum} operator itself consists of both looking up a specified number of embedding vectors from each table and a subsequent partial sum.
This becomes an issue for GPUs when the number of lookups per table and the table counts increase, leading to irregular memory access patterns.

\begin{figure}[t]
    \centering
    \includegraphics[width=0.9\linewidth]{figures/td_both_v.png}
    \caption{\textbf{TopDown pipeline slot breakdowns.} \textbf{(Top)} On Broadwell, models that rely on matrix operations (i.e., NCF, RM3, WnD, MT-WnD), fill most of their pipeline slots with retiring instructions; the remaining models are either frontend bound or backend bound.
    \textbf{(Bottom)} On Cascade Lake, models with large FC components (i.e., RM3, WnD, MT-WnD) have fewer retiring  pipeline slots due to wider SIMD width.
    The remaining models exhibit an increase in retiring mainly due to a reduction in bad speculation pipeline slots.}
    \label{fig:td_both}
    \vspace{-1em}
\end{figure}

\textbf{2) In addition to the impact of varying model architecture, batching inference requests across different hardware platforms uncovers additional opportunities for hardware optimization.} Previous work has categorized recommendation models into three types: \textit{MLP-}, \textit{Embedding-}, or \textit{Attention}-dominated models based on using a Broadwell CPU at a fixed batch size of 64 \cite{gupta2020deeprecsys}. While this offers an efficient grouping for high-level discussions, analyzing operator breakdowns across all possible use cases reveals even more optimization points for designing future hardware. For example, on RM1, varying batch sizes from 4 to 64 will shift the dominant operator bottleneck from \texttt{FC} to \texttt{SparseLengthsSum}.
Classifying the recommendation models based on their GPU performance also leads to different conclusions.
For example, WnD, an FC-heavy model on CPUs, is dominated by the \texttt{SparseLengthsSum} operator at small batch sizes on GPUs.
Identifying these shifting bottlenecks is important in order to thoroughly explore optimization opportunities.
Designing efficient hardware that specializes for low-latency targets (i.e., smaller batch sizes), high-throughput (i.e., larger batch sizes), or other specific cases will require revisiting the operator breakdowns at target use cases.

\textbf{3) Different generations of the same platform type (i.e., CPU/GPU) affect exact operator usages but retain general trends.} On the left subplots of Figure \ref{fig:op_breakdown} are Broadwell and Cascade Lake breakdowns and on the right are GTX 1080 Ti and T4 breakdowns.
Inter-generation microarchitectural changes (i.e. Broadwell to Cascade Lake) affect operator breakdowns (e.g., for RM1 and RM2, time spent on FC layers is reduced) -- Section \ref{sec:hardware} goes more in depth on how microarchitectural differences lead to this.

\subsection{Effects of Different Deep Learning Frameworks}

Figure \ref{fig:op_breakdown_tf} compares operator breakdowns between Caffe2 and TensorFlow for DLRM-based models.
As the operator breakdowns are similar, we know the optimization targets will be, to first order, the same regardless of differences in software frameworks. The mapping of the operator responsible for FC stacks is straightforward: \texttt{FC} in Caffe2 maps to \texttt{FusedMatMul} in TensorFlow.
However, the \texttt{SparseLengthsSum} operator in Caffe2 maps to the combination of \texttt{ResourceGather} (lookup) and \texttt{Sum} (pool) operators in TensorFlow.

\section{Introduction}~\label{sec:introduction}
Recommendation systems recommend items to users based on the users' personal preferences.
E-commerce marketplaces (e.g., Amazon, Alibaba) that recommend relevant goods for purchase~\cite{linden2003amazon, zhou2018din, zhou2019dien},
social media platforms (e.g., Facebook, Twitter) that regularly update user feeds with new multimedia content\cite{naumov2019dlrm},
and entertainment services (e.g., Netflix, YouTube) that promote new playlists~\cite{he2017ncf, zhao2019mtwnd} all heavily rely on high-accuracy recommendation systems to maintain quality of service and positive user experience.
To achieve the highest possible recommendation accuracies, these recommendation algorithms have evolved from using classical information filtering techniques \cite{Sarwar2001CF, funk2006matrix} to state-of-the-art deep-learning based solutions. Figure \ref{fig:rec_overview} depicts the general workflow of a typical recommendation system in the context of the aforementioned internet-based applications -- these algorithms are programmed using different deep learning frameworks and executed on systems of different architectures.

While deep-learning solutions provide high quality recommendations, they also require high infrastructure overheads to run efficiently.
For instance, Facebook's recommendation use cases require more than 10$\times$ the datacenter inference capacity compared to computer vision and natural language processing tasks~\cite{kim2018hpca}.
As a result, over 80\% of machine learning inference cycles on Facebook's datacenter fleet are devoted to recommendation filtering and ranking~\cite{gupta2020architectural}. The model training process tells a similar story --- over 50\% of the training demands are attributed to deep recommendation models\cite{naumov2020fbtraining}.
Similar capacity demands can be found at other companies like Google~\cite{jouppi2017datacenter}, Amazon~\cite{mckinsey2018rec},  Alibaba~\cite{zhou2018din, zhou2019dien}, and Baidu~\cite{zhao_2019}.

\begin{figure}[t]
    \centering
    \includegraphics[width=\linewidth]{figures/rec_overview_5.png}%
    \caption{\textit{Recommendation systems} leverage information about a user's preferences to recommend new content. The three main components include users, items, and the recommendation system itself.
    This paper analyzes recommendation inference at three different levels of the computing stack: algorithms and software, systems platforms, and microarchitectures.

    }
    \label{fig:rec_overview}
    \vspace{-1em}
\end{figure}

Given the importance of recommendation models, exploring custom hardware solutions will be important for further workload acceleration and infrastructure efficiency.
Recent work has demonstrated that some recommendation models -- given their large memory capacity requirements and irregular memory access patterns -- pose unique performance bottlenecks compared to other deep learning based workloads (e.g., CNNs and RNNs)~\cite{gupta2020deeprecsys}.
Thus, existing proposals for accelerating datacenter scale CNNs and RNNs do not directly apply to recommendation models.
By exploiting these unique compute characteristics, researchers have demonstrated that novel memory systems can provide significant speedup on a specific class of recommendation models dominated by table lookup operations~\cite{rhu2019tensordimm, ke2019recnmp, hwang2020centaur}.
However, there still exists large algorithmic diversity across recommendation use cases \cite{zhang2019recsurvey, gupta2020deeprecsys, mlperf-reco-advisory}.
Because of this diversity, holistic architectural bottleneck analysis -- for both CPU microarchitecture and heterogeneous hardware -- will enable hardware customization for improving recommendation inference efficiency.

In this paper, we perform a detailed workload characterization of recommendation inference at three different levels of the execution stack: algorithms and software, systems platforms, and hardware microarchitectures.
First, we evaluate the eight recommendation networks on a variety of server class CPUs and AI accelerators (i.e., GPUs).
This evaluation shows the optimal system -- between CPUs and GPUs and between microarchitecture generations (i.e., Intel Broadwell versus Cascade Lake and NVIDIA Pascal versus Turing) -- varies based on the model architectures and inference batch sizes.
In addition to heterogeneous system evaluation, we demonstrate that Caffe2 software operator usage breakdowns -- which vary across model architectures, batch sizes, and underlying hardware -- expose performance bottlenecks and opportunities for architectural optimizations.
Finally, we perform a detailed microarchitectural performance analysis on server class Intel Broadwell and Cascade Lake CPUs using TopDown~\cite{yasin2014topdown}.
Our microarchitectural analysis reveals that recommendation inference suffers from a variety of microarchitecture inefficiencies related to frontend decoders, backend functional units and memory systems, and branch speculation.

The main contributions of this paper are:

\begin{enumerate}

  \item
  While conventional wisdom and recent research indicates that AI accelerators, such as GPUs, readily accelerate deep learning workloads, this work shows the optimal hardware system (i.e., CPU versus GPU) varies based on recommendation use cases (Section \ref{sec:speedup}).
  \item In addition to overall execution times, we analyze software operator usage at the algorithm level. Previous work classifies recommendation models based on their operator breakdowns at fixed use cases on CPUs. In contrast, our analysis shows that varying the model architecture, batch-size, and hardware platform can alter the target operators for future hardware optimization

  (Section \ref{sec:software}).

  \item
  Based on the detailed TopDown results from a server class Intel Broadwell CPU, we see that pipeline bottlenecks vary based on model architecture features.

  FC-intensive models (i.e., RM3, WnD, MT-WnD) suffer from insufficient functional units; embedding-intensive models (i.e., RM1, RM2) suffer from ineffective frontend decoders;
  attention-based models (i.e., DIN, DIEN) suffer from instruction cache misses (Section~\ref{sec:hardware}).

  \item We compare the microarchitectural performance characteristics of Broadwell and Cascade Lake CPUs.
  The Cascade Lake microarchitecture improves recommendation inference performance across all use cases with its wider Single Instruction Multiple Data (SIMD) execution units and enhanced speculation capabilities.
  With these optimizations, the performance bottleneck on Cascade Lake shifts to the backend memory subsystem (Section~\ref{sec:hardware}).

\end{enumerate}

\section{CPU Microarchitectural Characterization}~\label{sec:hardware}
Complementing the operator breakdowns, in this section we present a detailed CPU microarchitectural characterization that provides additional insights into the performance trends for recommendation inference.
In order to better understand the architectural bottlenecks in general purpose processors, we use TopDown-based performance measurement unit (PMU) analysis for server-class Broadwell and Cascade Lake CPUs (Table \ref{tab:hw}) \cite{yasin2014topdown}.
This analysis shows the important microarchitectural components that form the performance bottlenecks for different recommendation models on Broadwell and how the bottlenecks change for Cascade Lake CPUs.

\subsection{TopDown analysis}
Following TopDown performance analysis~\cite{yasin2014topdown}, we break down the CPU pipeline into four major portions: frontend, speculation, backend, and retiring.
The frontend fetches instructions from memory and converts them into micro-operations ($\mu$ops); speculation realizes predictive optimizations; backend schedules and executes the $\mu$ops; retiring commits the $\mu$ops.
In order to optimize the performance of a processor we must maximize instructions per cycle (IPC).
Generally, IPC can be improved by increasing the fraction of processor cycles devoted to retiring as opposed to stalled in the frontend, speculation, or backend portions.
Recent work uses TopDown analysis to better understand the fraction of cycles in each pipeline portion for server and datacenter workloads~\cite{kanev2015warehouse, sriraman2019softsku, yasin2014topdown}.

\subsection{Recommendation performance using TopDown}

Figure \ref{fig:td_both} shows the TopDown breakdown of the eight deep recommendation models, with a batch-size of 16, on Broadwell and Cascade Lake CPUs.
Generally, on Broadwell, models with larger FC layers (i.e., RM3, WnD, and MT-WND) spend the majority of their cycles in retiring.
On the other hand, the remaining models (i.e., NCF, RM1, RM2, DIN, and DIEN) suffer from a variety of frontend, backend, and bad speculation bottlenecks.
Following are notable observations:

\textbf{1) On Broadwell, larger FC-dominated models benefit from vector execution but remain limited with insufficient functional units.} On Broadwell, models that rely on FC layers (i.e., NCF, RM3, WnD, MT-WND) spend a large percentage of pipeline slots on retiring instructions.
Thus, the natural next step would be to investigate the \textit{degree} of instruction vectorization for these models (Figure \ref{fig:avx}).
On Broadwell, over $60\%$ of all retired instructions for RM3, WnD, and MT-WnD are Advanced Vector Instructions (AVX) (Figure \ref{fig:avx} (Left)).
This is a result of machine learning frameworks, like Caffe2, translating FC layers to vectorized matrix operations.

\begin{figure}[t]
    \centering
    \includegraphics[width=\linewidth]{figures/core_bound_2.png}
    \caption{(\textbf{Top}) \textbf{Ratio of Core:Memory Backend Bound cycles}.  Majority of stalls come from functional units on Broadwell and from memory subsystem on Cascade Lake. (\textbf{Bottom}) \textbf{Functional unit usage}. RM3, WnD, and MT-WnD saturate Broadwell's functional units more than other models with a large fraction of cycles that use 3+ units out of 8. Cascade Lake decreases the pressure on functional units.}
    \label{fig:core_bound}
    \vspace{-1em}
\end{figure}

Despite this high degree of vectorization, the larger FC-dominant models still spend a significant fraction of pipeline slots backend bound -- highlighting the need for improved CPU backend pipelines for faster $\mu$ops consumption.
Backend bound cycles can be further classified as either core bound or memory bound.
Figure \ref{fig:core_bound} (Left) quantifies the core-bound nature of these backend-bound models on a Broadwell machine in two ways. The top row shows the breakdown of the backend bound slots as a core:memory bound ratio, where RM3, WnD, and MT-WnD all show numbers $>1$.
In the case of RM3, where the ratio $\sim2$, there are twice as many functional units-induced stall cycles as memory subsystem-induced stall cycles.
We see that for WnD and MT-WnD, this ratio is $>1.5$.
Thus, despite wide vector execution, larger FC-dominant models remain backend core-bound on Broadwell machines.

Figure \ref{fig:core_bound} (Bottom) details the cycle-level utilization of functional units.
Recall that Broadwell CPUs have eight functional units: four arithmetic units, two load units, and two store units.
Figure~\ref{fig:core_bound} (left, bottom) shows nearly 50\% of cycles in RM3, WnD, and MT-WnD require more than three functional units: this high functional unit utilization underscores the core-bound bottleneck.
This illustration of the core-bound bottleneck also corroborates the source of GPU speedups for RM3, WnD, and MT-WnD.
Since these models are bottlenecked by the lack of more functional units, the increase in the amount of compute units (streaming multiprocessors) on GPUs alleviates this core bound issue on Broadwell.

\begin{figure}[t]
    \centering
    \includegraphics[width=0.5\linewidth]{figures/retired_ins.png}
    \caption{\textbf{Retired Instructions Count} decreases from Broadwell to Cascade Lake due to the introduction of the more efficient AVX-512 VNNI instructions.}
    \label{fig:retired_ins}
    \vspace{-1em}
\end{figure}

\textbf{2) On Cascade Lake, larger FC-dominated models benefit from wider SIMD width and compute capabilities, shifting the bottleneck to the memory subsystem.}

Figure~\ref{fig:td_both} (bottom) shows the TopDown analysis of the eight recommendation models on Cascade Lake CPUs.
In comparison to Broadwell, Cascade Lake enables the majority of models (e.g., NCF, RM1, RM2, DIN, DIEN) to have a larger fraction of retiring pipeline slots.
This larger fraction of cycles spent on retiring instruction is the main reason why Cascade Lake provides consistent speedup over Broadwell (see Figure~\ref{fig:speedups}).
Note that the fraction of cycles devoted to the retiring stage did not increase between Broadwell to Cascade Lake for RM3, WnD, and MT-WnD.
The slight decrease in the retiring cycles is due to fewer total dynamic instructions, as shown in Figure~\ref{fig:retired_ins}; overall, the wider width AVX-512 Vector Neural Network Instructions (VNNI) improves performance for larger FC-dominated models.

Recall that RM3, WnD, and MT-WnD are core bound on Broadwell.
Figure~\ref{fig:core_bound} (right) shows the backend TopDown analysis on Cascade Lake.
Given the wider AVX512-VNNI instructions, Cascade Lake implements more sophisticated fused multiply-add hardware, which increases the compute capability of the processor.
The increased compute capability reduces pressure on the functional units as shown in Figure~\ref{fig:core_bound} (bottom, right).
Despite the reduced execution port utilization, inference performance for RM3, WnD, and MT-WnD remains backend bound on Cascade Lake.
As shown in Figure~\ref{fig:core_bound} (upper, right), the backend bottleneck has shifted from being core-bound to memory bound.
The particular memory subsystem limiting performance depends on the input batch size -- smaller batch sizes (i.e., less than $100$) are limited by L3 cache accesses while, larger batch-sizes are limited by DRAM latency.

\begin{figure}[t]
    \centering
    \includegraphics[width=0.9\linewidth]{figures/i_mpki_bdw.png}
    \caption{\textbf{NCF and attention-based models suffer from instruction cache misses.} NCF's small size shifts the bottleneck from execution units to i-cache. Attention-based models scale each embedding vector (from irregular memory accesses) with individual weights, leading to high i-cache MPKI.}
    \label{fig:i_mpki_bdw}
    \vspace{-1em}
\end{figure}

\textbf{3) Smaller FC-dominant models and attention-based models suffer from frontend latency -- especially L1 instruction cache latency.}
Not all FC-dominant models are core-bound.
For example, on Broadwell, NCF suffers from frontend latency bottlenecks and in particular, L1 instruction cache latency.
Because of its relatively small FC layers, NCF does not exhibit core-bound levels of high compute intensity.

To understand these frontend limitations, Figure \ref{fig:i_mpki_bdw} quantifies the L1 instruction cache miss rate.
NCF, along with attention-based models like DIN and DIEN, have higher L1 instruction cache miss rates compared to the remaining models.
For instance, we measure a L1 instruction misses per thousand instructions (i-MPKI) of 12.4 and 7.7 for DIN and DIEN, respectively.
The high instruction cache miss rates are tied to how DIN and DIEN implement attention.
Recall that for recommendation systems, attention allows networks to individually weight the importance of embedding vectors to offer higher personalization.
In DIN, attention is implemented using hundreds of local concatenation and FC layers; this leads to a large number of instructions with unique reference locations (since the instruction cache does not cache opcodes but specific instructions, including the reference operand).
Given the unique memory addresses for embedding table lookups, the instruction cache hit rate suffers from irregular memory accesses (i.e., lack of spatial and temporal locality).
DIEN's GRU implementation more efficiently translates to matrix operations compared to DIN's implementation with local concatenation-FC \textit{per lookup}. This offers cache friendly loops with regular operand and reference locations.

\begin{figure}[t]
    \centering
    \includegraphics[width=0.9\linewidth]{figures/decoder_bottleneck.png}
    \caption{\textbf{Frontend Decoder Pipeline Inefficiencies.} The two main decoder microarchitecture components are DSB and MITE. Shown are percent of cycles in which the CPU was limited by a specific decoder component (i.e., component was not supplying IDQ with optimal number of decoded instructions).}
    \label{fig:decoder_bottleneck}
    \vspace{-1em}
\end{figure}

\begin{figure}[t]
    \centering
    \includegraphics[width=0.4\linewidth]{figures/dram_bw.png}
    \caption{\textbf{RM2 also suffers from DRAM Bandwidth Congestion} from the large number of embedding lookups.}
    \label{fig:dram_bw}
    \vspace{-1em}
\end{figure}

\textbf{4) Models with more embedding table lookups suffer from instruction decoder bottlenecks. As the degree of embedding table lookups increases, the performance bottleneck shifts from pure decoder issues to also include DRAM bandwidth limitations.}
On Broadwell, RM1 and RM2 are frontend bandwidth-bound deep recommendation models.
Generally, this denotes inefficiencies in the instruction decode phase as opposed to in the instruction fetch phase.
Figure \ref{fig:decoder_bottleneck} illustrates the fraction of cycles spent on two parts of Broadwell's frontend decoder pipeline, the decoded i-cache (Decoded Stream Buffer - DSB) and the legacy decoder pipeline (Micro-Instruction Translation Engine - MITE).
MITE is responsible for fetching instructions from instruction memory and decoding them into $\mu$ops while the DSB caches results from MITE.
For each target instruction, DSB is first queried.
If the instruction is found in the DSB, the corresponding $\mu$ops are directly delivered to the instruction decode queue (IDQ).
If the instruction is not found, MITE is used to fetch and decode instructions and the result is added into DSB.

Figure \ref{fig:decoder_bottleneck} (bottom) shows Broadwell's decoder pipeline -- including DSB and MITE.
CPU cycles are analyzed to determine if either DSB or MITE could not supply IDQ with sufficient $\mu$ops.
For both RM1 and RM2, the frontend bandwidth bound models, TopDown analysis illustrates the bottlenecks in DSB as the main source of inefficiency.

The DSB bottleneck can be tied to algorithmic, model-architecture features of RM1 and RM2.
In particular, both models require a high degree, tens to hundreds, of embedding table lookups.
Combined with the irregular memory accesses coming from embedding lookups, larger instruction footprints stress the DSB.
Furthermore, RM1 and RM2 spend a large fraction of their cycles on bad speculation as shown in Figure~\ref{fig:td_both}.
Since DSB is also affected by the Branch Prediction Unit (BPU), the large amount of branch misprediction latency will degrade the performance of DSB, as the speculation stalls are primarily from branch mispredictions.

Despite the similarities between RM1 and RM2, RM2 has a unique performance bottleneck.
As shown in Table~\ref{tab:rec_models}, RM2 comprises more embedding tables (32 versus 8 in RM1) and more lookups per table (120 versus 80 in RM1).
Given the larger size, RM2 suffers from bottlenecks in both the frontend and backend pipeline.
Figure~\ref{fig:dram_bw} illustrates the DRAM bandwidth congestion of RM1, RM2, DIN, and DIEN.
DRAM bandwidth congestion, as defined by Intel, occurs when the offcore read queue occupancy exceeds 70\% of the maximum number of requests that can be served by the memory controller simultaneously; whereas when below 70\% occupancy, the stall can be characterized as DRAM latency bound~\cite{intel2020opt}.
We find that RM2 suffers from significantly higher DRAM bandwidth congestion limitations compared to the other models.
Previous work exploit this property to design near memory processing solutions for DRAM bandwidth-bound recommendation models~\cite{rhu2019tensordimm, ke2019recnmp}.

\begin{figure}[t]
    \centering
    \includegraphics[width=\linewidth]{figures/branches.png}
    \caption{\textbf{Branch Mispredicts} decrease significantly when we transition from Broadwell to Cascade Lake machines.}
    \label{fig:branches}
    \vspace{-1em}
\end{figure}

\textbf{5) Cascade Lake significantly reduces the amount of pipeline slots lost to bad speculation.}
One of the marked differences between the TopDown breakdowns of Broadwell and Cascade Lake in Figure \ref{fig:td_both} is the decrease in pipeline slots lost to bad speculation in Cascade Lake.
While the specific detail of the branch predictor designs used in Broadwell and Cascade Lake are not available, the transition from Broadwell to Skylake sees a penalty reduction for incorrect direct jump target~\cite{fog2020microarch}.
This overall improvement shifts the Cascade Lake backend bottlenecks to the memory subsystems as discussed in Observation \#2.

\subsection{Tying Model Architectures to Pipeline Bottlenecks}

To tie our microarchitectural observations to the specifics of recommendation model architectures, we quantify the effects of select algorithmic model architecture features with a linear regression model.

Figure \ref{fig:lr_weights} summarizes our linear regression modeling; all input features have been normalized so the weight magnitude represents degree of impact.
Data points are collected from running the 8 models at batch sizes from 1 to 16384. The model shows that each pipeline bottleneck is a result of a combination of different algorithmic model architecture features. For example, this model shows that a high ratio of FC to embedding weights reduces bad speculation while a top-heavy distribution of FC weights leads to increases in bad speculation. The first point explains the intuition that compute-intensive models have more predictable branches while the second point shows that more direct processing of continuous inputs is correlated with less bad speculation.

\begin{figure}[t]
    \centering
    \includegraphics[width=\linewidth]{figures/lr_weights_3.png}
    \caption{\textbf{Linear Regression modeling} of algorithmic model architecture components and pipeline bottlenecks reveals that there is not a single deciding factor for each bottleneck.}
    \label{fig:lr_weights}
\end{figure}
\section{Methodology}~\label{sec:methodology}

Personalized recommendation systems run a diverse collection of state-of-the-art deep-learning models across heterogeneous datacenter hardware.
To understand the impact of algorithmic model diversity on inference performance, we characterize eight industry-representative, publicly-available recommendation models.
The model implementations are from the open-sourced DeepRecSys repository and are also not pre-trained as this study focuses solely on inference compute requirements~\cite{gupta2020deeprecsys}.
We characterize the recommendation model performance on server class CPUs (i.e., Intel Broadwell and Cascade Lake) and GPU-based AI accelerators (i.e., NVIDIA 1080 Ti and T4).
This section describes the models and system platforms used in this work.

\subsection{Deep Recommendation Models}

Figure \ref{fig:model_evolution} (bottom) provides a generalization of deep recommendation model architectures.
Building on the general model architecture, our characterization studies eight industry-representative deep recommendation models with unique network parameters, as shown in Table~\ref{tab:rec_models}~\cite{gupta2020deeprecsys}.

\input{tables/hw}

\begin{enumerate}[leftmargin=*]

\begin{figure*}[ht!]
    \centering
    \includegraphics[width=0.95\linewidth]{figures/speedup_10.png}
    \caption{\textbf{Systems performance evaluation} represented as speedup over Broadwell CPU across models, batch-sizes, and hardware platforms. Models are grouped into three primary, overlapping categories -- ones that perform well on GPUs, ones that have comparable performance on CPUs and GPUs, and attention-based models with varying implementations.}
    \label{fig:speedups}
    \vspace{-1em}
\end{figure*}

\item \textbf{Neural Collaborative Filtering (NCF)} extends matrix factorization with multi-layer perceptrons (MLPs) and non-linearities:
\begin{equation}
    r_{ij} \approx \hat{r_{ij}} \equiv \phi(\mathbf{w}^T({\mathbf{u}_i}\circ{\mathbf{v}_j}))
    \label{eqn:gmf}
\end{equation}
where $\phi$ and $\mathbf{w}$ are the activation function and weights respectively. Although NCF has only four embedding tables, it has shown success with the MovieLens dataset~\cite{he2017ncf}.

\item \textbf{Deep Learning Recommendation Model (DLRM RM1, RM2, RM3)} is a highly configurable model with multi-hot encoded embedding lookups.
Outputs of embedding lookups are aggregated with the output of DNN stacks that process continuous input features.
We configure three representative DLRM networks -- RM1, RM2, RM3 -- with varying ratios of FC weights and embedding lookups based on Facebook's social media ranking models~\cite{naumov2019dlrm, gupta2019architectural, gupta2020deeprecsys}.

\item \textbf{Wide and Deep (WnD)} captures both the memorization and generalization benefits by concatenating outputs of one-hot encoded embedding lookups with continuous inputs.
The resulting features are then processed with deep feed-forward networks.
WnD has been used to rank applications in Google's Play Store~\cite{cheng2016wnd}.

\item \textbf{Multi-Task Wide and Deep (MT-WnD)} expands upon WnD by adding parallel output FC layers on top of WnD to evaluate multiple objectives. While the other models predict a single engagement objective such as click-through rate (CTR), MT-WnD evaluates multiple objectives such as likes and ratings.
MT-WnD provides high quality next video recommendations on YouTube \cite{zhao2019mtwnd}.

\item \textbf{Deep Interest Network (DIN)} addresses evolving user preferences by implementing the attention mechanism with local activation units for embedding table lookups.
User embedding tables process a small number of lookups while item embedding tables process hundreds of lookups.
DIN has been deployed to great success by Alibaba in its online marketplace for display advertising \cite{zhou2018din}.

\item \textbf{Deep Interest Evolution Network (DIEN)} also addresses evolving user preferences but uses multi-layered gated recurrent units (GRUs) to explicitly separate user preferences from user interaction history. For item embedding tables, this leads to fewer lookups per table as more of the information processing is offloaded to the GRU layers. Like DIN, DIEN has been deployed successfully by Alibaba on its display advertising services (specifically on Taobao) \cite{zhou2019dien}.
\end{enumerate}

\subsection{Systems Platforms}

State-of-the-art recommendation models are deployed across heterogeneous hardware systems in datacenters.
In fact, exploiting hardware heterogeneity to schedule inferences on optimum platforms based on use cases (i.e., model architecture, inference batch-size) significantly improves recommendation performance~\cite{gupta2020deeprecsys}.
This work mimics this hardware heterogeneity by providing in-depth characterizations on two server class CPUs (i.e., Intel Broadwell and Cascade Lake) and two GPUs (i.e., NVIDIA GTX 1080 Ti and T4).
Table~\ref{tab:hw} summarizes the key architectural features of the platforms.
GPUs are connected to CPUs via PCIe 3.0. All results assume single-threaded inference in Caffe2, and include both data loading and model computation times to capture end-to-end recommendation inference.

\section{Systems Platforms Evaluation}~\label{sec:speedup}
\begin{figure*}[t]
    \centering
    \includegraphics[width=0.9\linewidth]{figures/data_loading_8.png}
    \caption{\textbf{GPU data communication overheads} as percent of total execution time. While parts of this overhead can be attributed to software implementation overhead, the majority is due to GPU data loading (i.e., CPU-GPU communication overheads).}
    \label{fig:data_loading}
    \vspace{-1em}
\end{figure*}
This section describes the performance characteristics of the eight recommendation models at different use cases (i.e., input batch sizes and systems platforms).
The range of batch sizes follows recent work that shows recommendation in datacenters runs with batch sizes from tens to thousands to meet different SLA targets~\cite{gupta2020deeprecsys}; the range of systems platforms exposes the effects of different generations of CPUs and GPUs.
In the context of GPUs, we find that data-communication overheads limit GPU performance.
Overall, the analysis shows that the optimum hardware for recommendation inference depends on both model architecture and batch size.

Figure~\ref{fig:speedups} depicts the speedups of the Cascade Lake CPU, GTX 1080 Ti GPU, and T4 GPU over a baseline Broadwell CPU server.
The results are organized by recommendation model, across batch-sizes 1 to 16384, and consider end-to-end execution times (i.e., model-computation plus data-communication). The important observations are:

\textbf{1) Model architecture plays an important role in accelerating recommendation inference.}
Models in the bottom row of Figure~\ref{fig:speedups} exhibit high speedup on the NVIDIA 1080 Ti and T4 GPUs.
For larger batch sizes ($\sim10^{3}$), the GPUs provide \textit{an order of magnitude} speedup over the baseline Broadwell CPU; for smaller batch sizes ($<10^{2}$), we observe a $2-4\times$ speedup.
The relatively high speedups observed come from the models (i.e., NCF, RM3, WND, MT-WND, RM3) sharing an important algorithmic characteristic (Table~\ref{tab:rec_models}): whether it is fewer embedding tables in NCF, large FC stacks for continuous inputs in RM3, or large FC stacks to output final probability scores in WnD and MT-WnD, each of these models relies on FC stacks to model user preferences.
As GPUs readily accelerate matrix operations, they outperform CPUs on NCF, RM3, WND, and MT-WND.

Compared to the models with large FC components, RM1 and RM2 exhibit relatively lower speedups -- less than 4$\times$ -- when deployed on GPUs (Figure~\ref{fig:speedups} top left).
In fact, at small batch sizes, Cascade Lake consistently outperforms the 1080 Ti GPU (and by at least 2$\times$ at small batch sizes) and offers speedups within 10\% of the T4.
This is a result of RM1 and RM2 having a large number of lookups per embedding table -- 80 and 120 lookups respectively.
In comparison, the remaining models have fewer than 20 lookups per table.
The larfe number of lookups shifts the performance bottleneck towards embedding operations that comprise of irregular memory accesses (see Section~\ref{sec:software} for details).
Depending on the input batch-size, CPUs and GPUs perform comparably on these models dominated by irregular memory accesses.

\textbf{2) Different model architecture implementations of an algorithmic feature like the attention mechanism can have different hardware implications.}
Algorithmically, both DIN and DIEN use attention to learn users' evolving interests over time.
DIN implements attention with local activation units and small FC layers followed by concatenation operations for aggregation while DIEN implements attention using multi-layered gated-recurrent units (GRUs).
For DIN, Broadwell machines outperform GPUs at batch-sizes less than 100.
At larger batch-sizes, GPU speedup saturates below 4$\times$.
The lower speedups are a direct result of DIN implementing attention with heavy concatenation operations that perform poorly on GPUs.
In comparison, DIEN achieves up to 7$\times$ speedup on GPUs compared to Broadwell, as GRUs translate to matrix multiplications that perform well on GPUs.

\begin{figure}[t]
    \centering
    \includegraphics[width=0.9\linewidth]{figures/optimal_hw_2.png}
    \caption{\textbf{Optimal hardware for each model architecture and batch size:} each grid cell show the speedup over Broadwell when using the optimum hardware (color).}
    \label{fig:optimal_hw}
    \vspace{-1em}
\end{figure}

\begin{figure*}[t]
    \centering
    \includegraphics[width=\linewidth]{figures/op_breakdown_master_5.png}
    \caption{\textbf{Caffe2 operator breakdowns} with CPUs (left) and GPUs (right). Models readily accelerated by GPUs are dominated by matrix operations (i.e., FC in red and recurrent layers in purple).
    Operator breakdowns between CPUs and GPUs vary significantly --- models dominated by FC execution time on CPUs spend a large fraction of time on other operators on GPUs.}
    \label{fig:op_breakdown}
    \vspace{-1em}
\end{figure*}

\textbf{3) Compared to Broadwell, Cascade Lake improves performance across all models and batch sizes.}
Across all use cases, encompassing models and batch-sizes, Cascade Lake achieves higher performance than Broadwell CPUs.
Following Table~\ref{tab:hw}, the improved performance is a result of various micro-architectural features such as wider SIMD width for FC-focused models, larger L2 cache capacity, and higher DRAM frequency.
Section~\ref{sec:hardware} details the micro-architectural features that enable higher performance on Cascade Lake.

\begin{figure}[t]
    \centering
        \includegraphics[width=\linewidth]{figures/op_breakdown_tf.png}%
    \caption{\textbf{Comparison of Caffe2 and TensorFlow operator breakdowns} for DLRM-based recommendation models. Operators that comprise the majority of execution time are similar across both frameworks. Note, embedding table operations correspond to \texttt{SparseLengthsSum} in Caffe2 and the combination of \texttt{ResourceGather} and \texttt{Sum} in TensorFlow.}
    \label{fig:op_breakdown_tf}
    \vspace{-1em}
\end{figure}

\textbf{4) Compared to GTX 1080 Ti, T4 improves performance for specific models and batch-sizes.}
For NCF, RM3, WnD, MT-WnD, and DIEN, T4 outperforms the 1080 Ti at batch sizes larger than $\sim 10^3$, offering higher speedups due to higher streaming multiprocessor (SM) count.
However, for RM1 and RM2, T4 becomes advantageous at smaller batch sizes -- due to the increase in GDDR5X to GDDR6 frequency.
This is important as for latency-critical applications with strict SLA targets, input samples must run at small batch sizes.

\textbf{5) GPU speedup over CPU is limited by data communication overheads.}
Figure \ref{fig:data_loading} quantifies the fraction of time spent on data communication for different models and batch sizes.
Data communication overheads come from offloading both continuous and categorical inputs via PCIe.
For all models, the fraction of time spent on data communication scales with batch size as compute operations are readily accelerated (sub-linear) but data communication is not.
Exact percentage of time spent on data-communication still depends on the model architecture; models that rely on embedding lookups suffer most.
Given the high data-communication overheads, we conclude that running recommendation models out of the box on GPUs underutilizes the GPUs' compute resources.

Figure \ref{fig:optimal_hw} summarizes the results of Section \ref{sec:speedup} by showing how the optimal system platform (color coded) and speedup (number inside cell) vary across the use cases (models across the rows and batch sizes across the columns).
While this section provides a high level intuition on the tradeoffs between CPUs and GPUs, the following sections dive deeper into the heterogeneity behind Figure \ref{fig:optimal_hw}.
\section{Introduction}
This document is a model and instructions for \LaTeX.
Please observe the conference page limits.

\section{Ease of Use}

\subsection{Maintaining the Integrity of the Specifications}

The IEEEtran class file is used to format your paper and style the text. All margins,
column widths, line spaces, and text fonts are prescribed; please do not
alter them. You may note peculiarities. For example, the head margin
measures proportionately more than is customary. This measurement
and others are deliberate, using specifications that anticipate your paper
as one part of the entire proceedings, and not as an independent document.
Please do not revise any of the current designations.

\section{Prepare Your Paper Before Styling}
Before you begin to format your paper, first write and save the content as a
separate text file. Complete all content and organizational editing before
formatting. Please note sections \ref{AA}--\ref{SCM} below for more information on
proofreading, spelling and grammar.

Keep your text and graphic files separate until after the text has been
formatted and styled. Do not number text heads---{\LaTeX} will do that
for you.

\subsection{Abbreviations and Acronyms}\label{AA}
Define abbreviations and acronyms the first time they are used in the text,
even after they have been defined in the abstract. Abbreviations such as
IEEE, SI, MKS, CGS, ac, dc, and rms do not have to be defined. Do not use
abbreviations in the title or heads unless they are unavoidable.

\subsection{Units}
\begin{itemize}
\item Use either SI (MKS) or CGS as primary units. (SI units are encouraged.) English units may be used as secondary units (in parentheses). An exception would be the use of English units as identifiers in trade, such as ``3.5-inch disk drive''.
\item Avoid combining SI and CGS units, such as current in amperes and magnetic field in oersteds. This often leads to confusion because equations do not balance dimensionally. If you must use mixed units, clearly state the units for each quantity that you use in an equation.
\item Do not mix complete spellings and abbreviations of units: ``Wb/m\textsuperscript{2}'' or ``webers per square meter'', not ``webers/m\textsuperscript{2}''. Spell out units when they appear in text: ``. . . a few henries'', not ``. . . a few H''.
\item Use a zero before decimal points: ``0.25'', not ``.25''. Use ``cm\textsuperscript{3}'', not ``cc''.)
\end{itemize}

\subsection{Equations}
Number equations consecutively. To make your
equations more compact, you may use the solidus (~/~), the exp function, or
appropriate exponents. Italicize Roman symbols for quantities and variables,
but not Greek symbols. Use a long dash rather than a hyphen for a minus
sign. Punctuate equations with commas or periods when they are part of a
sentence, as in:
\begin{equation}
a+b=\gamma\label{eq}
\end{equation}

Be sure that the
symbols in your equation have been defined before or immediately following
the equation. Use ``\eqref{eq}'', not ``Eq.~\eqref{eq}'' or ``equation \eqref{eq}'', except at
the beginning of a sentence: ``Equation \eqref{eq} is . . .''

\subsection{\LaTeX-Specific Advice}

Please use ``soft'' (e.g., \verb|\eqref{Eq}|) cross references instead
of ``hard'' references (e.g., \verb|(1)|). That will make it possible
to combine sections, add equations, or change the order of figures or
citations without having to go through the file line by line.

Please don't use the \verb|{eqnarray}| equation environment. Use
\verb|{align}| or \verb|{IEEEeqnarray}| instead. The \verb|{eqnarray}|
environment leaves unsightly spaces around relation symbols.

Please note that the \verb|{subequations}| environment in {\LaTeX}
will increment the main equation counter even when there are no
equation numbers displayed. If you forget that, you might write an
article in which the equation numbers skip from (17) to (20), causing
the copy editors to wonder if you've discovered a new method of
counting.

{\BibTeX} does not work by magic. It doesn't get the bibliographic
data from thin air but from .bib files. If you use {\BibTeX} to produce a
bibliography you must send the .bib files.

{\LaTeX} can't read your mind. If you assign the same label to a
subsubsection and a table, you might find that Table I has been cross
referenced as Table IV-B3.

{\LaTeX} does not have precognitive abilities. If you put a
\verb|\label| command before the command that updates the counter it's
supposed to be using, the label will pick up the last counter to be
cross referenced instead. In particular, a \verb|\label| command
should not go before the caption of a figure or a table.

Do not use \verb|\nonumber| inside the \verb|{array}| environment. It
will not stop equation numbers inside \verb|{array}| (there won't be
any anyway) and it might stop a wanted equation number in the
surrounding equation.

\subsection{Some Common Mistakes}\label{SCM}
\begin{itemize}
\item The word ``data'' is plural, not singular.
\item The subscript for the permeability of vacuum $\mu_{0}$, and other common scientific constants, is zero with subscript formatting, not a lowercase letter ``o''.
\item In American English, commas, semicolons, periods, question and exclamation marks are located within quotation marks only when a complete thought or name is cited, such as a title or full quotation. When quotation marks are used, instead of a bold or italic typeface, to highlight a word or phrase, punctuation should appear outside of the quotation marks. A parenthetical phrase or statement at the end of a sentence is punctuated outside of the closing parenthesis (like this). (A parenthetical sentence is punctuated within the parentheses.)
\item A graph within a graph is an ``inset'', not an ``insert''. The word alternatively is preferred to the word ``alternately'' (unless you really mean something that alternates).
\item Do not use the word ``essentially'' to mean ``approximately'' or ``effectively''.
\item In your paper title, if the words ``that uses'' can accurately replace the word ``using'', capitalize the ``u''; if not, keep using lower-cased.
\item Be aware of the different meanings of the homophones ``affect'' and ``effect'', ``complement'' and ``compliment'', ``discreet'' and ``discrete'', ``principal'' and ``principle''.
\item Do not confuse ``imply'' and ``infer''.
\item The prefix ``non'' is not a word; it should be joined to the word it modifies, usually without a hyphen.
\item There is no period after the ``et'' in the Latin abbreviation ``et al.''.
\item The abbreviation ``i.e.'' means ``that is'', and the abbreviation ``e.g.'' means ``for example''.
\end{itemize}
An excellent style manual for science writers is \cite{b7}.

\subsection{Authors and Affiliations}
\textbf{The class file is designed for, but not limited to, six authors.} A
minimum of one author is required for all conference articles. Author names
should be listed starting from left to right and then moving down to the
next line. This is the author sequence that will be used in future citations
and by indexing services. Names should not be listed in columns nor group by
affiliation. Please keep your affiliations as succinct as possible (for
example, do not differentiate among departments of the same organization).

\subsection{Identify the Headings}
Headings, or heads, are organizational devices that guide the reader through
your paper. There are two types: component heads and text heads.

Component heads identify the different components of your paper and are not
topically subordinate to each other. Examples include Acknowledgments and
References and, for these, the correct style to use is ``Heading 5''. Use
``figure caption'' for your Figure captions, and ``table head'' for your
table title. Run-in heads, such as ``Abstract'', will require you to apply a
style (in this case, italic) in addition to the style provided by the drop
down menu to differentiate the head from the text.

Text heads organize the topics on a relational, hierarchical basis. For
example, the paper title is the primary text head because all subsequent
material relates and elaborates on this one topic. If there are two or more
sub-topics, the next level head (uppercase Roman numerals) should be used
and, conversely, if there are not at least two sub-topics, then no subheads
should be introduced.

\subsection{Figures and Tables}
\paragraph{Positioning Figures and Tables} Place figures and tables at the top and
bottom of columns. Avoid placing them in the middle of columns. Large
figures and tables may span across both columns. Figure captions should be
below the figures; table heads should appear above the tables. Insert
figures and tables after they are cited in the text. Use the abbreviation
``Fig.~\ref{fig}'', even at the beginning of a sentence.

\input{tables/ieee_sample_table}

\begin{figure}[htbp]
\centerline{\includegraphics{figures/fig1}}
\caption{Example of a figure caption.}
\label{fig}
\end{figure}

Figure Labels: Use 8 point Times New Roman for Figure labels. Use words
rather than symbols or abbreviations when writing Figure axis labels to
avoid confusing the reader. As an example, write the quantity
``Magnetization'', or ``Magnetization, M'', not just ``M''. If including
units in the label, present them within parentheses. Do not label axes only
with units. In the example, write ``Magnetization (A/m)'' or ``Magnetization
\{A[m(1)]\}'', not just ``A/m''. Do not label axes with a ratio of
quantities and units. For example, write ``Temperature (K)'', not
``Temperature/K''.

\section*{Acknowledgment}

The preferred spelling of the word ``acknowledgment'' in America is without
an ``e'' after the ``g''. Avoid the stilted expression ``one of us (R. B.
G.) thanks $\ldots$''. Instead, try ``R. B. G. thanks$\ldots$''. Put sponsor
acknowledgments in the unnumbered footnote on the first page.

\section*{References}

Please number citations consecutively within brackets \cite{b1}. The
sentence punctuation follows the bracket \cite{b2}. Refer simply to the reference
number, as in \cite{b3}---do not use ``Ref. \cite{b3}'' or ``reference \cite{b3}'' except at
the beginning of a sentence: ``Reference \cite{b3} was the first $\ldots$''

Number footnotes separately in superscripts. Place the actual footnote at
the bottom of the column in which it was cited. Do not put footnotes in the
abstract or reference list. Use letters for table footnotes.

Unless there are six authors or more give all authors' names; do not use
``et al.''. Papers that have not been published, even if they have been
submitted for publication, should be cited as ``unpublished'' \cite{b4}. Papers
that have been accepted for publication should be cited as ``in press'' \cite{b5}.
Capitalize only the first word in a paper title, except for proper nouns and
element symbols.

For papers published in translation journals, please give the English
citation first, followed by the original foreign-language citation \cite{b6}.


\section{Background and related work}
\label{sec:background}

Reinforcement learning was originally invented for robotics and automation.
Recently with the artificial intelligence and machine learning being introduced to broader research areas, reinforcement learning has started to be applied in communications and networking. The main advantage of reinforcement learning is that it does not need a large dataset during the training process. A reinforcement-learning agent is capable to sense the environment and learn to make decisions by itself during the training. To design a reinforcement learning agent, a description of the environment is essential, either mathematically modelled as an input to the agent (i.e., model-based), or learnt by the agent itself (i.e., model-free). In this paper we model the cloud computational resource allocation problem as an \ac{MDP}, which is a commonly used model to describe a stochastic process \cite{suttonbook}. We then get optimal solutions for the agent by value iteration, which is an effective reinforcement-learning algorithm to solve the \ac{MDP}.

There are some recent works published on reinforcement learning utilisation on the computational resource allocation and offloading at the edge computing or fog computing. For instance, authors in \cite{LiGaLv18} used reinforcement learning to optimise the computational task offloading problem from mobile users to edge computing servers. The authors in \cite{LeTh18} proposed a reinforcement-learning method to offload the computational task from one user to another user in ad-hoc wireless networks with \ac{MDP} model.
Besides, authors in \cite{TaZhZh18} applied \ac{MDP} to model the container migration problem in fog computing and then use reinforcement learning to design an agent that migrates containers between different physical servers while optimising the total power consumption.
Despite the fact that reinforcement learning has been used for addressing many different resource or task allocation problems in cloud computing, to the best of our knowledge, our work is the first one that investigates the problem of dynamic CPU resource allocation of cloud-based wireless networks by reinforcement learning.

\section{Conclusion and future work}
\label{sec:conclusion}

In this paper, we have designed and implemented an \ac{MDP}-based model to represent the dynamic CPU resource allocation problem in cloud-based wireless networks. We use value iteration algorithm to build a reinforcement learning agent to get the optimal policy. We have investigated different scenarios with different parameters as well as comparing the performance with another baseline algorithm, namely \ac{RAS}. From the simulation results we have found that our agent gets the optimal policy rapidly in under 100 iterations and the algorithm are extendable to many different scenarios. Our agent with value iteration outperforms or at least equally performs in energy savings compared to the baseline algorithm.

In this paper, we predefined the transition probabilities in the \ac{MDP} according to the statistics, which means that the agent is fully aware of the environment. In future, we plan to build more sophisticated reinforcement learning scenarios where the agent is not fully aware of the environment, and has to update its optimal decisions with time goes by. These will involve deep Q-learning techniques with neural networks.

\section{Introduction}
\label{sec:introduction}

Cloud-based systems have been proposed and implemented for many promising \ac{IoT} applications, such as smart city and e-health~\cite{NaGu18, MoRoSi18}. Two enabling technologies, \ac{SDR} and \ac{SDN}, recently started to be utilised in the cloud to support the virtualisation of the \ac{IoT} network~\cite{AhAlMa19}.
In a cloud environment, computational resources (e.g. CPU, memory, and storage) are virtualised and allocated to fulfil the requirements
of different \ac{IoT} services.
Optimising computational resource allocation in the cloud to balance energy consumption and processing performance is an important research topic.
Reinforcement learning provides an effective method for solving such an optimisation problem in a stochastic and dynamic environment.

In this paper, we design and implement a model-based reinforcement-learning agent based on \ac{MDP}, to intelligently allocate  computational resources for cloud-based wireless networks. The agent analyses the state transition probabilities between different states, reflecting different levels of \ac{CPU} utilisation,  as well as the corresponding reward functions, and then decides to either remain in the same state or to change states by adding/reducing one CPU core. The reward function for each state-action pair drives the agent to optimise the total reward after multiple \ac{MDP} steps.
We use a value iteration algorithm  \cite{suttonbook} for the agent to solve this \ac{MDP} and arrive at an optimal policy
that balances the energy savings and cloud performance.

We simulate many different \ac{SDR} and \ac{SDN} scenarios
to evaluate the performance of our reinforcement-learning agent. We have found that the optimal policies carried out by the agent are different for \ac{SDR} or \ac{SDN} cases. The results show that our agent with value iteration outperforms a baseline algorithm in terms of energy savings in some of the scenarios while achieving similar performance in the other scenarios. We also investigate the performance of our agent with different transition probabilities as well as a higher number of \ac{MDP} states to verify the scalability of our agent.

Our contribution in this paper can be summarised as follows: 1) the modelling of the dynamic CPU resource allocation problem in the cloud-based wireless networks by \ac{MDP}; 2) the utilisation of value iteration method to solve the \ac{MDP} to get the optimal policy; and 3) the comprehensive analysis of the performance of our reinforcement learning agent in various scenarios with different parameters.

\section*{Acknowledgement}
This publication has emanated from the research supported
by the European Commission Horizon 2020 under grant agreements
no. 732174 (ORCA), and co-funded
under the European Regional Development Fund from
Science Foundation Ireland under Grant Number 13/RC/2077
(CONNECT). This material is also based on works supported by Science Foundation Ireland under Grant No. SFI/12/RC/2289\_P2.

\bibliographystyle{IEEEtran}

\section{Experimental results}
\label{sec:results}

To evaluate the performance of our agent running the aforementioned value iteration algorithm in a cloud-based wireless network scenario, we investigate two commonly-used network processes, i.e., \ac{SDN} and \ac{SDR}. We conduct our simulations with different experimentation parameters and compare the results with another baseline algorithm.

\subsection{Definition of transition probabilities and rewards of \ac{MDP}}

We start with an experiment of 3 states for the \ac{MDP} (shown in Figure \ref{fig:MDP_picture}).
We define the parameters we use for the \ac{MDP} simulation for both \ac{SDN} and \ac{SDR} cases in Table \ref{tab:parameters_3_states}. The transition probabilities between the 3 states (i.e., 3 levels of CPU core usage percentage) are derived from
the general experimental data statistics of the Trinity College Dublin Iris testbed \cite{iris_link}.
The \ac{SDN} and \ac{SDR} cases have different transition probabilities, due to the facts that 1) a single \ac{SDN} process utilises a lower percentage of a CPU core but there are usually multiple processes running at the same time to share the same CPU core, meaning that \ac{SDN} processes are more likely to be parallelised; 2) a single \ac{SDR} process utilises a higher percentage of a CPU core and is usually not capable to be parallelised. Therefore, the probability for \ac{SDN} to transit to other states is larger than the one for \ac{SDR} when increasing or decreasing the number of allocated CPU cores.

Besides, we define the normalised rewards of the reinforcement learning procedure when solving the \ac{MDP} (also shown in Table \ref{tab:parameters_3_states}). The definition of the rewards is based on the objective that is to minimise the total number of running CPU cores (to save energy) while avoiding long-term high CPU load percentage (to guarantee the overall performance of the cloud system).
In general, the reward is positive when 1) reducing one CPU core and the CPU load keeps the same level; or 2) adding one CPU core and the CPU load level gets lower. The reward is negative when 1) doing nothing (i.e. with action $a0$); or 2) adding one CPU core but CPU load level remains; or 3) reducing one CPU core and CPU load level increases.

\begin{table}

\centering
\caption{State transition probability and corresponding rewards for the 3 states transition map}
\label{tab:parameters_3_states}
\begin{tabular}{|c|c|c||c|c|}
\hline\hline
 \multicolumn{3}{|c||}{Transition probabilities} & \multicolumn{2}{|c|}{Rewards} \\ \hline
 & SDN & SDR &   &  SDN \& SDR  \\\hline\hline
$P(s0 |s0, a0)$ & 1 & 1 & $r(s0, a0, s0)$ & -3 \\ \hline
$P(s0 |s0, a1)$ & 1 & 1 & $r(s0, a1, s0)$ & -5\\ \hline
$P(s0 |s0, a2)$ & 0.3 & 0.7 & $r(s0, a2, s0)$ & +5\\ \hline
$P(s1 |s0, a2)$ & 0.7 & 0.3 & $r(s0, a2, s1)$ & -5\\ \hline
$P(s1 |s1, a0)$ & 1 & 1 & $r(s1, a0, s1)$ & -1\\ \hline
$P(s0 |s1, a1)$ & 0.8 & 0.2 & $r(s1, a1, s0)$ & +5\\ \hline
$P(s1 |s1, a1)$ & 0.2 & 0.8 & $r(s1, a1, s1)$ & -5\\ \hline
$P(s1 |s1, a2)$ & 0.3 & 0.7 & $r(s1, a2, s1)$ & +5\\ \hline
$P(s2 |s1, a2)$ & 0.7 & 0.3 & $r(s1, a2, s2)$ & -5\\ \hline
$P(s2 |s2, a0)$ & 1 & 1 & $r(s2, a0, s2)$ & -5\\ \hline
$P(s1 |s2, a1)$ & 0.8 & 0.2 & $r(s2, a1, s1)$ & +5\\ \hline
$P(s2 |s2, a1)$ & 0.2 & 0.8 & $r(s2, a1, s2)$ & -5\\ \hline
\hline
\end{tabular}
\vspace{-0.1in}
\end{table}

\subsection{Results with 3 states, certain transition probability and predefined rewards}

As mentioned in the previous section, we design the reinforcement-learning agent to find the optimal policy $\pi^*$ using the value iteration algorithm (Algorithm \ref{alg:vi}). We use Python 3.5 open-source \ac{MDP} library \cite{mdp_link} to implement the \ac{MDP} model, the value iteration procedure and simulation of the results.
The threshold of the convergence ($\epsilon$ in the Algorithm~\ref{alg:vi}) is set to be a very small value ($10^{-3}$). The value iteration algorithm converges rapidly to optimal values. For SDN case it converges after 66 iterations, while for SDR case it converges after 56 iterations.

Figure \ref{fig:value_function_SDR} and Figure \ref{fig:value_function_SDN} show the value function variations and convergence during the value iteration process for \ac{SDR} and \ac{SDN} respectively. For the case of \ac{SDR} there is $V(s0)>V(s1)>V(s2)$ when converged; while for the case of \ac{SDN} there is $V(s2)>V(s1)>V(s0)$ when converged. The results mean that in the case of \ac{SDR} the agent prefers to go for a lower CPU load state, while in the case of \ac{SDN} the agent prefers to go for a higher CPU load state. To understand the decision of the agent, we should take into account the fact that the \ac{SDN} processes are easier to be parallelised than the \ac{SDR} processes, therefore it is safer to push to a higher CPU load state for \ac{SDN} to save resources than \ac{SDR}, because in the case of \ac{SDN} adding one CPU will more likely bring down the high CPU load and get positive reward. However for the \ac{SDR} case the states tend to stay when adding/reducing CPUs therefore there is a higher risk for the agent to stay in the high CPU load state and get continuously high penalties.

\begin{figure}[ht]
    \vspace{-0.1in}
	\centering
\includegraphics[width=0.45\textwidth]{sdr_value_function}
	\caption{Value function of the 3 different states vs. Iterations for SDR}
	\label{fig:value_function_SDR}
    \vspace{-0.1in}
\end{figure}

\begin{figure}[ht]

	\centering
\includegraphics[width=0.45\textwidth]{sdn_value_function}
	\caption{Value function of the 3 different states vs. Iterations for SDN}
	\label{fig:value_function_SDN}
    \vspace{-0.1in}
\end{figure}

Besides, the agent also derives the optimal policy denoted by state-action pairs $(s,a)$. For the case of \ac{SDR} they are $(s0,a2)$, $(s1,a2)$, and $(s2,a1)$, while for the case of \ac{SDN} they are $(s0,a2)$, $(s1,a1)$, and $(s2,a1)$. These two cases have the same optimal actions at the state $s0$ and $s2$, which are $a2$ and $a1$ respectively, meaning that the agent chooses to reduce one CPU when the CPU load is low and to add one CPU when the CPU load is high, which is straightforward to understand since these two actions are the only options in these two states to get an immediate positive reward.
However, the optimal action for the medium state $s1$ is different for \ac{SDR} and \ac{SDN}, For the case of \ac{SDR} the agent prefers to reduce one CPU at the state of $s1$ while for the case of \ac{SDN} the agent prefers to add one CPU at the state of $s1$. These two decisions are not obvious to understand since both actions on state $s1$ can make the same immediate reward. Therefore the agent has to decide these actions not only by the immediate reward, but also by maximising the total reward considering future rewards with the discount factor $\gamma$ (see Equation (\ref{eqn:total_rewards})). These decisions are optimised by the value iteration.

\subsection{Results with different transition probabilities}

In the previous subsection, we obtain the transition probabilities shown in Table \ref{tab:parameters_3_states} based on the general statistics of the Trinity College Dublin Iris testbed \cite{iris_link}.
In this subsection we change these probabilities and see how the changes would effect to the results, to further evaluate the scalability of our algorithm to other testbeds/scenarios. We keep those probability values that equal to 1 in Table \ref{tab:parameters_3_states} for the cases in which state transition is definite, and vary the other "not-equal-to-1" values that are for the transition probability between different states. We assume that
for the \ac{SDR} case those values vary among 0.01, 0.1, 0.2, 0.3, and 0.4, while for the \ac{SDN} case those values vary among 0.6, 0.7, 0.8, 0.9 and 0.99. The reason is that \ac{SDN} processes are more likely to be parallelised thus more likely to transit to another state when adding/reducing one CPU core.

The results in Figure \ref{fig:different_probability_standard_deviation} show the relation between the aforementioned state transition probability from one state to another state (X axis) and the standard deviation of the value functions of the 3 states (Y axis).
The results show that the variation of transition probabilities affects a lot to the standard deviation of the value functions for the \ac{SDR} case but not so much for the \ac{SDN} case. Besides, the curves for the \ac{SDR} and \ac{SDN} cases show different tendencies with the increasing of transition probability. In general, higher standard deviation of value functions means the reinforcement-learning agent has more obvious preferences on different states.
In Figure \ref{fig:different_probability_standard_deviation} we also plot the case for equal probability values (i.e. with 0.5 transition probability, meaning equal probability to stay in the same state or to transit to another state), in which case the state value functions all equal to 0 ($V(s0)=V(s1)=V(s2)=0$). This means that the agent is indifferent to the 3 different states therefore the value iteration does not work properly in this case.

\begin{figure}[ht]
    \vspace{-0.1in}
	\centering
\includegraphics[width=0.45\textwidth]{different_probability_standard_deviation}
	\caption{Standard deviation of the value functions in different transition probability cases}
	\label{fig:different_probability_standard_deviation}
	\vspace{-0.1in}
\end{figure}

\subsection{Results compared to other algorithms}

In this subsection, we compare the results of our value iteration algorithm with another baseline algorithm.
According to the previous analysis and review values in Table \ref{tab:parameters_3_states}, for the states $s0$ or $s2$ there is only one optimal choice of state-action pair, (i.e., $(s0, a2)$ or $(s2, a1)$), which has positive reward value. Therefore any optimisation algorithm would choose these two state-action pairs.
However, the difference occurs when transiting from the state $s1$,
where there is no obvious preference for the agent on taking the action $a1$ or $a2$ in terms of immediate rewards. The benefit of the algorithm will appear with time goes by. Therefore, to compare the performance of our algorithm and the baseline algorithm, we simulate the \ac{MDP} procedure to calculate the cumulative reward (defined by Equation \ref{eqn:total_rewards}) after a certain number of \ac{MDP} steps.

We define the baseline algorithm, namely \ac{RAS} algorithm, to compare with our value iteration algorithm. The \ac{RAS} algorithm randomly chooses the action $a1$ or $a2$ made at the state $s1$ with equally 50\% probability respectively. Figure \ref{fig:rewards_comparison_SDR} shows the comparison of cumulative reward between our value iteration approach and the \ac{RAS} approach for one single time-based \ac{MDP} simulation. The simulation is conducted under the same SDR case with the state transition probability equal to 0.1 for both adding one CPU and reducing one CPU. The results show that our agent with value iteration gets more cumulative reward during the reinforcement learning process than the agent with \ac{RAS}, meaning our agent works more efficiently to reach our goal.

\begin{figure}[ht]

	\centering
\includegraphics[width=0.45\textwidth]{sdr_vi_ras}
	\caption{Cumulative reward comparison between value iteration approach and RAS approach for an SDR MDP case}
	\label{fig:rewards_comparison_SDR}
    \vspace{-0.1in}
\end{figure}

We also build simulations to compare the energy savings and CPU working performance for value iteration and \ac{RAS} algorithm, in a cloud with 1000+ available CPU cores.
Instead of showing the results for a single \ac{MDP} as Figure \ref{fig:rewards_comparison_SDR}, we build 10000 independent \ac{MDP} simulations with each simulation having 1000 \ac{MDP} steps and take average results to get more reliable comparisons.

To showcase the energy savings, Figure \ref{fig:CPU_comparison} shows the comparison between value iteration and \ac{RAS} for total number of added/reduced CPU cores in different transition probability cases (positive numbers on Y-axis mean adding CPUs while negative numbers mean reducing CPUs). Besides, to showcase the performance maintenance, Figure \ref{fig:high_percentage_comparison} shows the comparison between value iteration and \ac{RAS} for percentage of time in high CPU load state ($s2$) in different transition probability cases.

By looking at Figure \ref{fig:CPU_comparison},
for \ac{SDR} case, our agent with value iteration reduces more number of CPU cores in the MDP than \ac{RAS}, especially for cases where transition probability is less than 0.2. This means that our agent saves more energy than the baseline \ac{RAS} in the cloud systems for the \ac{SDR} case. For instance, for the case where transition probability equals to 0.01, our value iteration agent saves energy consumption of 40 more CPUs than \ac{RAS} does. If one high-performance CPU core consumes 80 watts \cite{intel_link}, saving 40 CPUs corresponds to around 76.8 kWh energy savings per day.
However, Figure \ref{fig:high_percentage_comparison} shows that
value iteration has around 25\% more time in high-load CPU state than \ac{RAS} in \ac{SDR} cases (although it is still below 50\% of time), meaning that our agent takes higher risk on keeping the CPUs on high-load states than \ac{RAS}.
For \ac{SDN} case, our agent with value iteration has similar CPU core reductions (i.e. energy savings) as \ac{RAS}, but takes lower risk on keeping the CPUs on high-load states than \ac{RAS}.
Note that we don't consider the case in which the transition probability equals to 0.5 on the X-axis because in this case the value iteration does not work properly (as mentioned in Figure~\ref{fig:different_probability_standard_deviation}).

\begin{figure}[ht]

	\centering
\includegraphics[width=0.45\textwidth]{Total_number_of_added_reduced_CPU}
	\caption{Comparison between value iteration and RAS for total number of added/reduced CPUs in different transition probability cases}
	\label{fig:CPU_comparison}
    \vspace{-0.1in}
\end{figure}

\begin{figure}[ht]

    \centering
\includegraphics[width=0.45\textwidth]{high_CPU_load_percentage.png}
	\caption{Comparison between value iteration and RAS for percentage of time in high CPU load state ($s2$) in different transition probability cases}
	\label{fig:high_percentage_comparison}
    \vspace{-0.1in}
\end{figure}

\subsection{Results with more states}

In this subsection, we investigate the case with more \ac{MDP} states (4 states) and see if the results follow the similar trend, to evaluate the scalability of our agent using value iteration when the CPU-usage levels are defined to be more fine-grained.
To make the case for ``4 states"
we add one more intermediate state to the previous 3-state scenario shown in Figure~\ref{fig:MDP_picture}, between the low-CPU-usage state $s0$ and high-CPU-usage state $s2$ (becoming $s3$ after adding one state) while keeping the same structure of actions $a$'s, transition probabilities and rewards.
We conduct the experiments on the 4-state scenario with the same transition probabilities and reward parameters as the 3-state scenario.
The results
show the same trend as Figure \ref{fig:value_function_SDR} and Figure \ref{fig:value_function_SDN}.
The number of iterations to reach convergence is also around 60.
For the \ac{SDR} case the value functions follow $V(s0)>V(s1)>V(s2)>V(s3)$, while for the \ac{SDN} case the value functions follow $V(s3)>V(s2)>V(s1)>V(s0)$.  Besides, the optimal state-action pair selections for the 4-state case are the same as the 3-state case as well.
We are not showing the figures here due to the page limits. These results mean that our agent with value iteration is extendable to scenarios with more states and more fine-grained CPU levels.

\section{System Model}
\label{sec:system_model}

In this section we first describe the \ac{MDP} model that we build for the dynamic computational resource allocation problem of cloud-based wireless networks. After that we define the reward function, value function and Q function for this \ac{MDP} model, as the parameters for our reinforcement-learning agent. Finally we present the value iteration algorithm that can help solve the \ac{MDP} model and get optimal policies by reinforcement learning.

\subsection{The MDP model}

\ac{MDP} is a discrete-time stochastic process that is used for modelling the decision making procedure involving multiple states and actions in a stochastic environment \cite{Bel}.
According to our observation of the statistics of Trinity College Dublin's cloud-based Iris testbed \cite{iris_link}, we model the stochastic process of the CPU usage and the CPU allocation of cloud processes in our testbed as an \ac{MDP}. Supposing $L_{max}$ denotes the maximum instant CPU load percentage for the cores that are being used (e.g., if a container in the cloud is using 3 CPU cores with the load percentage of 50\%, 60\% and 70\%, $L_{max}=70\%$), the core with $L_{max}$ becomes the bottle neck of the container in terms of the processing performance.
We then categorise the CPU load percentage $L_{max}$ into three levels, i.e., low utilisation state $s0$ ($<20\%$), medium utilisation state $s1$ ($20-80\%$) and high utilisation state $s2$ ($>80\%$), corresponding to the three states in the \ac{MDP}.
Note that we have also made the cases with more states (i.e., more fine-grained categorisation of CPU load percentage levels) later on in the result section and proved that the results with more states are similar with the three states case.

After defining the states, we define the three options of actions for the reinforcement-learning agent in the \ac{MDP} to be 1) keeping the current CPU numbers, i.e., $a0$; 2) adding one CPU core, i.e., $a1$; 3) reducing one CPU core, i.e., $a2$. The transitions between the states $s$'s after operating the action $a$'s are stochastic processes due to the uncertainty of the parallelisation situations of the processes running on the CPU cores, i.e., adding or reducing one CPU core would not necessarily change the states.
We define the state transition probability $P(s'|s, a)$ as the probability of getting into the next state $s'$ (either the same one or a different one) if taking action $a$ from state $s$. We also define the reward of this transition as $r(s, a, s')$, as the parameter for our reinforcement learning agent.
The time interval of the agent taking the actions can be customised to be different levels (e.g. in seconds, in minutes or in hours) depending on the needs of the network administrators.

\begin{figure}[ht]
    \vspace{-0.1in}
	\centering
\includegraphics[width=0.5\textwidth]{MDP_picture}
	\caption{MDP state transition diagram}
	\label{fig:MDP_picture}
    \vspace{-0.1in}
\end{figure}

Figure \ref{fig:MDP_picture} illustrates the state transition diagram of the aforementioned \ac{MDP} model, including the 3 states, i.e. $s0$, (low CPU load percentage), $s1$ (medium CPU load percentage) and $s2$ (high CPU load percentage), as well as the 3 actions, i.e., $a0$ (doing nothing), $a1$ (adding one CPU core) and $a2$ (reducing one CPU core). The figure also shows the transition probabilities $P(s'|s, a)$ as well as the corresponding rewards $r(s, a, s')$ with the arrowed lines between the states and actions.
Different colours of arrowed lines are only for improving visibility.
Note that taking action $a2$ from state $s2$ is not considered because it is not realistic to reduce one CPU core when the CPU load percentage is already high.

\subsection{Reward function, Value function, and Q function}

In this subsection we define the reward function, value function and Q function from this \ac{MDP} for the reinforcement learning~\cite{suttonbook}.
The objective of solving this \ac{MDP} is to find a policy $\pi$ that maximises the total reward $R$ when the system transits between the states after certain \ac{MDP} steps $T$. The total reward $R$ follows Equation (\ref{eqn:total_rewards}) where $r_i$ denotes the reward of each time step $i$ and $\gamma$ is the discount factor ($0 < \gamma < 1$, set to be 0.9 in this paper) that avoids the total reward going to infinity~\cite{suttonbook}.

\begin{equation}
    R = \sum_{i=1}^{T}\gamma^{i-1}r_i
    \label{eqn:total_rewards}
\end{equation}

We then define the value function of each state $V^{\pi}(s)$, denoting the expected total reward for an agent starting from state $s$ with the policy $\pi$ (shown in Equation (\ref{eqn:value_function})).  In this way, $V^{\pi}(s)$ indicates how good the state $s$ is for an agent to stay. Among all policy $\pi$'s, there existing an optimal policy $\pi^*$ that makes $V^{\pi}(s)$ to be maximum (shown in Equation (\ref{eqn:optimal_pi}))~\cite{suttonbook}.

\begin{equation}
    V^{\pi}(s) = E[\sum_{i=1}^{T}\gamma^{i-1}r_i]
    \label{eqn:value_function}
\end{equation}

\begin{equation}
    \pi^* = \arg \max_{\pi} V^{\pi}(s)
    \label{eqn:optimal_pi}
\end{equation}

We then define $V(s)$ as the short version for $V^{\pi}(s)$ from now on for simplicity.
In order to get the optimal $V(s)$, in reinforcement learning, the agent needs to try all policy $\pi$'s that include all possible combinations of state-action pairs $(s, a)$. The Q function $Q(s, a)$ for each state-action pair can be defined to indicate how beneficial it is for the agent to use action $a$ when in the state $s$. Therefore the maximum value of $V(s)$ ($V^*(s)$) equals to the maximum value of $Q(s, a)$ ($Q^*(s, a)$) for all the possible action $a$'s (shown in Equation (\ref{eqn:optimal_q}))~\cite{suttonbook}.

\begin{equation}
    V^*(s) = Q^*(s, a) = \max_{a}Q(s, a)
    \label{eqn:optimal_q}
\end{equation}

According to the Bellman Equation \cite{Bellmanbook2003}, The optimal $Q^*(s, a)$ equals to the summation of 1) the expectation of immediate reward $r(s, a, s')$ after taking action $a$ from state $s$ (considering all possible next states $s'$'s) and 2) the discounted expectation of all future maximum rewards $V^*(s')$ (for all possible next states $s'$'s as well), shown in Equation (\ref{eqn:bellman})~\cite{suttonbook}.

\begin{equation}
    Q^*(s, a) = \sum_{s'}P(s'|s, a)r(s, a, s') + \gamma \sum_{s'}P(s'|s, a)V^*(s')
    \label{eqn:bellman}
\end{equation}

Therefore, according to Equation (\ref{eqn:optimal_q}) and (\ref{eqn:bellman}), we can derive Equation (\ref{eqn:optimal_v_and_q}), for all possible state $s'$'s transiting from state $s$ taking action $a$~\cite{suttonbook}.

\begin{equation}
    V^*(s) = \max_{a}\sum_{s'}P(s'|s, a)(r(s, a, s') + \gamma V^*(s'))
    \label{eqn:optimal_v_and_q}
\end{equation}

\subsection{Reinforcement learning and value iteration}

According to the aforementioned Equations (\ref{eqn:value_function})-(\ref{eqn:optimal_v_and_q}), the reinforcement learning agent needs to obtain the maximum $V^*(s)$ and the corresponding optimal policy $\pi^*$ to perform an optimal solution to this \ac{MDP}. Assuming $P(s'|s, a)$ and $r(s, a, s')$ are both known for all the triple tuples $(s, a, s')$, we can use a reinforcement learning method, namely value iteration algorithm, to solve the optimal $V^*(s)$, by a recursive method using Equation (\ref{eqn:optimal_v_and_q}). The pseudo code of the value iteration algorithm can be expressed as the following Algorithm \ref{alg:vi} \cite{suttonbook}:

\begin{algorithm}
\caption{Value iteration algorithm}\label{alg:vi}
\begin{algorithmic}[1]
\State Initialisation: initial $V_{(0)}(s) = 0$ for all $s$
\For {$j = 0, 1, 2 ...$ ($j$ denotes the iteration step)}
\For {all $s$ in state set $S$}
\State $Q_{j}(s, a) \gets \sum_{s'}P(s'|s, a)(r(s, a, s') + \gamma V_{j}(s'))$
\State $V_{j+1}(s) \gets \max_{a} Q_{j}(s, a)$
\If {$|V_{j}(s) - V_{j+1}(s)| < \epsilon $}
\State \textbf{break}
\EndIf
\EndFor
\EndFor
\State $V^*(s) \gets V_{j}(s)$
\State \textbf{return} $V^*(s)$ and $\pi^*$
\end{algorithmic}
\end{algorithm}

The value iteration algorithm first initialises the value function $V(s)$ with arbitrary values (in our case, zeros), and then updates it with the value of the latest Q function $Q(s, a)$ when making a step ahead. After a number of iterations the value function $V(s)$ converges to the optimal value $V^*(s)$, when the difference between the last two iterations is less than a very small value $\epsilon$. The corresponding policy $\pi^*$ becomes the optimal policy (i.e., the optimal state-action pairs $(s, a)$).