# Visualizing Automatic Speech Recognition
– Means for a Better Understanding?

###### Abstract

Automatic speech recognition (ASR) is improving ever more at mimicking human
speech processing. The functioning of ASR, however, remains to a large extent
obfuscated by the complex structure of the deep neural networks (DNNs) they
are based on. In this paper, we show how so-called attribution methods, that
we import from image recognition and suitably adapt to handle audio data, can
help to clarify the working of ASR. Taking DeepSpeech, an end-to-end model for
ASR, as a case study, we show how these techniques help to visualize which
features of the input are the most influential in determining the output. We
focus on three visualization techniques: Layer-wise Relevance Propagation
(LRP), Saliency Maps, and Shapley Additive Explanations (SHAP). We compare
these methods and discuss potential further applications, such as in the
detection of adversarial examples.

Index Terms: speech recognition, visualization, explainable AI

##  1 Introduction

Figure 1: Different visualizations of the benign example “it has been
mentioned but the article is not mine”. (Top) The Saliency Map has the highest
attributions at low and high frequencies. (Middle) In the LRP, the lowest ten
MFCCs are the most attributing ones. (Bottom) For the SHAP, the attributions
show instead a more clustered-in-time behaviour while being equally
distributed along the different MFCC values.

DNNs find nowadays applications across a rich variety of domains, including
computer vision, language translation, and speech or recognition. Alongside
the increase of available computing power, DNNs’ architectures have became
extremely involved and may consist of up to millions of trainable parameters.
Such complexity makes the important task of understanding why a model outputs
a certain prediction challenging [1].

The pursuit of understanding DNNs’ has given rise to the new field of
interpretable (or explainable) machine learning [2]. In this context, a class
of interpretability algorithms called attribution-based methods has been
developed [3, 4] to evaluate the attributions of certain features of the DNN’s
input, that is, their effect on the output. In the past, these techniques have
been mainly applied to image object classification and natural language
processing [5, 6] and the question whether similar techniques can provide
insights in ASR remains open. In this paper, we address this question focusing
on the example of DeepSpeech and discuss how attribution-based approaches can
help to enable model transparency.

Indeed, a better understanding of the DNNs is crucial to allow the design of
ASR with higher and higher accuracy. Furthermore, a clearer visualization of
DNNs would potentially allow developers to design more secure ASR. With the
involvement of machine learning in more and more aspects of our daily life,
the discussion around security has been brought to the forefront. In certain
applications, like voice control systems for cars, the security of the ASR
system becomes critical even for the user’s physical safety.

As a specific example, a better understanding of DNNs could help to prevent
so-called adversarial examples. These intentionally perturbed inputs trick the
attacked models into misclassifications. Indeed, explanation methods have
already proven helpful in understanding adversarial examples and dataset-
related issues in the context of image analysis [7, 8], and have the potential
to provide similar insights in support of recent analyses on audio adversarial
examples for ASR [9, 10, 11, 12, 13].

Here, we show how attribution-based approaches can help to enable model
transparency for ASR. Focusing on the example of DeepSpeech, an end-to-end ASR
model, we compare three different atribution methods: Saliency Map [14],
Layer-wise Relevance Propagation (LRP) [15], and Shapley Additive Explanations
(SHAP) [16, 17]. The first two methods are based on the network’s gradient
towards the input, whereas the third is a game theory-based approach making
use of so-called Shapley values [18]. In the case of image classification,
these methods consist of determining and visualising with a heat map regions
of the input image that strongly influence a DNN’s output (see Figure 2). We
show that an analogous visualization is possible for audio data and ASR.

The remainder of our paper is structured as follows. In Section 2, we give a
short general overview on explanation methods and on our chosen network,
DeepSpeech. We provide a more technical account of the three explanation
techniques of interest and briefly outline our results in Section 3. In
Section 4, we briefly introduce our computational experiments, followed by a
discussion of the methods’ advantages and shortcomings. We conclude with an
outlook in Section 5.

##  2 Background on DeepExplain and DeepSpeech

With neural networks becoming more and more complex, explanation or
interpretation methods have become an important tool to gain insights on the
networks’ inner workings. Despite possible shortcomings [19, 6], these methods
can provide valuable insights for a first understanding. Further, explanation
methods can also provide means to detect adversarial examples [20]. There are
different implementations for visualization techniques online, e.g., Captum
[21].

For our implementations, we rely on DeepExplain111See
“https://github.com/marcoancona/DeepExplain”., a Tensorflow-based library that
aims at creating a unified framework for several state-of-the-art explanation
methods [3]. Originally developed within the image domain, it has now been
expanded to include techniques for NLP interpretation. The methods implemented
in DeepExplain are post-hoc attribution-based methods, that analyse the model
after training (during inference) without modifying it. The methods include
Saliency Map [14], LRP [15] and SHAP in a sampling-based approximation [16,
17, 5]. In our work, we have adapted these algorithms to work with
DeepSpeech222See “https://deepspeech.readthedocs.io/en” and
“https://github.com/mozilla/DeepSpeech/”., an open-source end-to-end speech-
to-text engine developed by Mozilla and based on Baidu’s Deep Speech research
paper [22].

In order to discuss the visualization, it is important to understand the rough
architecture of DeepSpeech. DeepSpeech’s classification process can be divided
into three stages: (i) a feature extraction stage that computes Mel-frequency
cepstral coefficients (MFCCs); (ii) a long short-term memory (LSTM) neural
network that takes MFCCs as input and outputs character probabilities; and
(iii) a language model that turns the neural network’s output into a properly
formatted text.

This paper focuses on the second step and visualize how the neural network
gets to a frame’s classification as a certain letter. In the neural network, a
pre-processing stage turns the input signal into an array of shape $(N,26)$,
where $N$ is the number of time frames (depending on input length) and $26$ is
the number of considered Mel-frequency cepstral coefficients (MFCCs). Each
time frame is sequentially fed into the LSTM neural network along with the
MFCCs of the nine previous and nine following time frames. The shape of the
considered input for every step is thus $(19,26)$.

##  3 Visualization Techniques

Among the wide range of interpretation methods developed for machine learning
in the image domain, a prominent class is that of _attribution methods_. An
attribution quantifies the effect of each input feature, e.g., a pixel, on a
neural network’s output.

A formal definition of attribution notion is provided in [3]. We adapt this
for the case of ASR. Given a NN that takes an input
$x^{i}\in\mathbb{R}^{19\times 26}$ (the currently evaluated audio slices) and
produces an output $S(x^{i})=[S_{1}(x^{i}),...,S_{28}(x^{i})]$ (probability
per letter), where $28$ is the total number of output neurons (representing
the Latin alphabet including the space and hyphen symbols). The attribution
for a specific target neuron $c$ is the matrix $A^{i}\in\mathbb{R}^{19\times
26}$ of the contribution of each input feature $x^{i}_{j,k}$ to the output
letter $S_{c}$. How the contribution $A^{i}_{j,k}$ is defined and computed
depends on the chosen method. To allow the visualization of the decision
process in DeepSpeech, we adapted two gradient-based methods from the image to
the audio domain: Saliency Map [14] and LRP [15], and one game theory-based
method: SHAP [16, 17]. For each method, the attributions are defined as
follows:

### Saliency Map

For a fixed time frame $i$, the contribution of each input feature
$x^{i}_{j,k}$ is defined as the absolute value of the partial derivative of
$S_{c}$ with respect to $x^{i}_{j,k}$, hence,

$\displaystyle A^{i}=\left|\frac{\partial S_{c}(x^{i})}{\partial
x^{i}}\right|.$

###  $\epsilon$ Layer-wise Relevance Propagation

The relevance is defined recursively by propagating backwards through the NN,
from the output layer to the input layer. Specifically, let $R_{u}^{(l)}$ be
the relevance of unit $u$ of layer $l$ with
$l\in\left\\{1,\,\ldots,\,L\right\\}$ for a NN consisting of $L$ layers. Then,
the relevance is first initialized in the last layer by:

$R_{u}^{(L)}=\begin{cases}S_{u}(x^{i}),&\text{if $u$ is the target neuron,}\\\
0&\text{else.}\end{cases}$ (1)

The algorithm then iteratively redistributes the predictions from layer $l+1$
to layer $l$, until the first layer is reached. Let
$z_{vu}=w^{(l+1,l)}_{vu}x_{u}^{(l)}$ be the weighted activation of a neuron
$u$ from layer $l$ onto neuron $v$ in layer $l+1$, $b_{v}$ the additive bias
of neuron $v$, and $\mathcal{N}_{l}$ the set of neurons in layer $l$, then we
define the relevance as

$R_{u}^{(l)}=\sum_{v\in\mathcal{N}_{l+1}}\frac{z_{vu}}{(1+\epsilon)\sum_{u^{\prime}\in\mathcal{N}_{l}}(z_{vu^{\prime}}+b_{v})}R_{v}^{(l+1)}.$
(2)

We set $\epsilon$ to $10^{-4}$, which is the default value used in [5]. Note
that the results may be highly sensitive to the chosen parameters, as
$\epsilon$ absorbs relevance for weak or contradictory contributions to the
activation of a neuron [23].

### Shapley values

In contrast to gradient-based methods, SHAP is a perturbation-based approach
that estimates the attributions by performing $M$ random feature permutations.
More specifically, Shapley values [24] are part of a concept from coalitional
game theory which calculates a fairly distributed payout for each player of
the game based on their contributions. From a machine learning perspective,
input features can be considered as “players”, the model performing the
prediction $f(\cdot)$ for a single input $x$ as a “game”, and the difference
between the actual prediction $f(x)$ and the average prediction for all
instances $\mathop{\mathbb{E}(f(X))}$ as the “gain”. A coalition of multiple
input features influence the final model output. Here, the Shapley values
allow us to check which features have the most significant impact on the
output by computing their marginal contributions. For a single feature the
Shapley value is the weighted sum of its marginal contributions. The general
definition of Shapley values for a given input feature $x^{i}_{j_{1},k_{1}}$
at time step $i$ and input value $x^{i}$ is:

$\displaystyle\begin{split}\phi^{i}_{j_{1},k_{1}}(x^{i})=\sum_{S\subseteq\left\\{x^{i}_{j,k}\right\\}_{j\neq
j_{1},k\neq k_{1}}}{\left[|S|\times\binom{F}{|S|}\right]}^{-1}\\\
\times\left[f_{\\{S\cup\\{x^{i}_{j_{1},k_{1}}\\}\\}}(x^{i})-f_{\\{S\\}}(x^{i})\right],\end{split}$
(3)

where $|S|$ is the cardinality of the feature subset $S$ and $F$ is the total
number of input features. Hence in our experiments, $F=19\times 26$. The
marginal contribution of a feature $x^{i}_{j_{1},k_{1}}$, calculated by
$f_{\\{S\cup\\{x^{i}_{j_{1},k_{1}}\\}\\}}(x^{i})-f_{\\{S\\}}(x^{i})$ is
computed by subtracting the model predictions of two permutations constructed
with and without $\\{x^{i}_{j_{1},k_{1}}\\}$. Next, a weighting scheme
described in [17] is applied to the marginal contributions. Finally, the
weighted sum of marginal contributions is a Shapley value estimation
$\phi^{i}_{j_{1},k_{1}}(\cdot)$ of the input feature $x^{i}_{j_{1},k_{1}}$.

As the total number of coalitions grows exponentially with the number of input
features ($2^{F}$), the exact calculation of the Shapley values is
computationally expensive. Hence, to overcome this problem, we use Monte-Carlo
sampling to estimate the Shapley values [25]. Additionally, to optimize the
calculations we use background samples [17], i.e., the median feature values
of certain frames in the training data. Randomly chosen combinations of
features from background samples are used to replace the features of the input
sample which results into a random permutation. A feature-wise difference of
two permutations is a marginal contribution of the feature
$x^{i}_{j_{1},k_{1}}$. The sum of marginal contributions computed with the
help of background samples is used in (3) to estimate Shapley values for
feature $x^{i}_{j_{1},k_{1}}$.

Figure 2: An overview of different explanation methods implemented in [3, 5].
The colours signify the areas of the image that each method considers as
influential. Figure taken from [5].

### Displaying Audio Data

In the original application of image classification, the attention values –
the values denoting the input’s influence on the classification – are plotted
on top of the simplified image. To transfer this visualization concept to the
audio domain, we propose three different approaches. Let $A$ denote the
attribution matrix of size $(N,19,26)$, we consider:

  * •

_Attribution per relative frame._ For a fixed relative frame
$j\in\left\\{1,\ldots,19\right\\}$, we can generate an attribution plot via
$A^{i}_{j,k}$. When $j=9$, the influence of the current frame on its own
classification is visualized.

  * •

_Attribution summed per frame._ For every frame, we can calculate its
influence on the others’ classification by summing diagonally (a zero is
considered for out-of-range indexes): $\sum_{n=0}^{18}A^{i+n}_{j+n,k}$

  * •

_Attribution summed per window._ Centered at every frame $i$, we sum over all
the attributions that the 19 frames have on $i^{\text{th}}$ frame’s
classification: $\sum_{j=1}^{19}A^{i}_{j,k}$.

In Figure 1, we visualize the attributions using Saliency Map, LRP, and SHAP
with the attribution summed per window. It shows the contribution of each
input feature to the predicted character indicated below the $x$ axis. Here,
we consider the benign audio file for the recorded sentence _“it has been
mentioned but the article is not mine”_. The gradient between two colors is
used to express the impact of the attributions on the model prediction. Higher
values, encoded in red, indicate a positive contribution of the features on
the model’s predictions. Features with negative impact on the decision process
are instead encoded in blue. We note that for an effective and informative
plotting of the attributions, the color code needs to be chosen carefully,
which we achieved by adapting the intensity scale for each method and choosing
a fixed percentile value for all plots.

##  4 Experiments and Discussion

In order to evaluate and compare the three visualization techniques, we have
performed experiments covering 360 benign speech samples from the Mozilla
Common Voice dataset333For more information, see
“https://commonvoice.mozilla.org/en/datasets”.. We have applied all three
visualization techniques and the three different methods for displaying the
data. For the SHAP method, we have tried different background noises in order
to compare the different attribution patterns. Further, we have studied the
behaviour on adversarial examples based on [9] and [10], the latter adapted
for DeepSpeech.

We aim to answer the following questions: (1) Which attribution method seems
the most suitable? (2) What do we learn about the underlying ASR system? We
base our illustrations on one example. According to our experiments, these
findings generalize to the dataset considered.

To answer the first question, we start by comparing the two gradient-based
methods, displayed in the two upper plots in Figure 1 for the attributions
summed per window and Figure 3 and Figure 4 in the appendix for the
attribution per frame. For both, Saliency Map and LRP, the magnitude of the
attribution is not evenly distributed amongst the frames. We observe that
frames nine to fourteen have a larger impact on the prediction than the other
ones, especially the first eight frames. Hence, we report that later frames
are more impactful for the final classification than earlier ones. This may be
due to the fact that DeepSpeech, being an LSTM model, already accounts for the
past, so that the future provides more new information.

We further observe that the attribution is also unevenly distributed among the
different MFCC bins. For LRP, the lowest coefficients are the most important
ones, the vast majority of the attribution being shared between the first ten
MFCCs. The result for the Saliency Map is quite different: the lowest and some
of the highest MFCCs are the most relevant while coefficients five to twenty
are less important. We understand the different bins to follow from the fact
that the LRP takes the input data into account by propagating the activation
value of the neurons back through the network, whereas the Saliency Map method
does not, as it instead simply computes the derivative of the NN’s output.

When comparing these results to the game theory inspired SHAP approach, we
find very different results visualized in the bottom plot of Figure 1 and in
Figure 5 in the appendix: (i) MFCC attributions obtained by applying the SHAP
method have an equally spread magnitude response among all MFCC values and
frames. (ii) We observe a clear difference in the response to frames
containing letters compared to frames containing whitespace characters only.

For observation (i), we see the following two reasons: The background sample
was chosen as the median of all frames with letters, i.e., input features were
substituted with median values which affected the resulting MFCC attributions.
The large amount of input features affected the weighting coefficients and
made them smaller which diminished the impact of each individual MFCC
attribution. The rationale behind observation (ii) might be that only frames
corresponding to letters were used to construct the background sample. We
randomly chose permutations of features in the input sample and substituted
them by a random subset of frame features from the background sample. For the
background sample, we used the median values of the frames transcribed to
letters. According to our experiments, this allows a better Shapley estimation
for actual letters.

Overall, the permutation-based SHAP method provides an alternative look at the
attributions of the audio samples by considering each frame and the according
MFCC values as independent features. In contrast, gradient-based methods
additionally rely on the timestamp of the audio signal appearance. The SHAP
method is model-agnostic, i.e., it applies to any method. Gradient-based
methods (LRP and Saliency Map) can only be employed with speech recognition
models trained using back propagation. The ability to incorporate the
gradients for attribution computation renders these methods computationally
much faster than perturbation-based methods, because the latter need a large
number of permutations to achieve a good estimation of the attributions.
Gradient and perturbation based methods can be used successfully to visualise
the attributions of audio samples, answering different questions and providing
different interpretations.

In summary, there is no visualization technique that is clearly the most
recommendable. However, the LRP method seems preferable to us, as the method
is fast to compute while providing very detailed information. Additionally,
since the different summation methods provide different insights on the
frame’s influence, they should all be considered.

To further shed light on the different visualization methods (second question)
and to better understand DeepSpeech itself, we have further considered
adversarial examples. We assume that one can better detect adversarial
examples (as a flaw of the NN) with a better understanding of the network.
Thus, we evaluated if our proposed visualization methods can be used to detect
adversarial examples. Visualizing attributions for adversarial examples
computed using the method by [9] and comparing them to benign audio samples
showed clear differences. Generally speaking, adversarial examples tend to
activate the NN to a greater extent, the magnitude of the attribution values
is higher, especially for the highest MFCCs when we incorporate gradient-based
visualisation methods. A similar effect was observed by applying the
perturbation-based method but the difference between benign and adversarial
samples was mainly captured among first $k$ frames. This phenomenon can be
attributed to the fact that the used attack perturbs the whole audio sample
uniformly and, hence, the largest difference can be measured at the very
beginning of the audio sample where no signal is present in case of benign
samples. With our first experiments at hand, we believe that these differences
can be used to perform adversarial example detection making ASR systems more
robust.

##  5 Conclusion

Visualization techniques in the audio domain are hard to evaluate: we do
generally not know the ground truth [1], i.e., which features are relevant to
the human and should be relevant for the classification system. Nevertheless,
our proposed explanation methods offer practical insights, e.g., the computed
attributions demonstrate which parts of the audio sample have the most
significant impact on the speech model’s prediction. Moreover, attribution
methods help to get a deeper understanding of the behavior of ASR models.
Finally, both, gradient and perturbation based methods, showed a great
potential in resolving the problem of detecting audio adversarial samples.
Future work may leverage our contribution to further explore this possibility
in many domains, including psychology, security, and general machine learning:
How do humans process speech in comparison to the algorithm? How do we need to
adjust our ASR systems in order to be closer to the human hearing? Can we use
this to detect adversarial examples?

Answering these questions might help to find possible reasons for why neural
networks can be fooled and thus allow developers to design strategies against
adversarial attacks [20].

##  6 Acknowledgments

This research was supported by the Bavarian Ministry of Economic Affairs,
Regional Development and Energy.

The authors acknowledge N. Schaaf for comments on the manuscript.

## References

  * [1] H. Zhang, J. Chen, H. Xue, and Q. Zhang, “Towards a unified evaluation of explanation methods without ground truth,” _arXiv preprint arXiv:1911.09017_ , 2019.
  * [2] L. H. Gilpin, D. Bau, B. Z. Yuan, A. Bajwa, M. Specter, and L. Kagal, “Explaining explanations: An overview of interpretability of machine learning,” in _2018 IEEE 5th International Conference on data science and advanced analytics (DSAA)_. IEEE, 2018, pp. 80–89.
  * [3] M. Ancona, E. Ceolini, C. Öztireli, and M. Gross, “Towards better understanding of gradient-based attribution methods for deep neural networks,” _arXiv preprint arXiv:1711.06104_ , 2017.
  * [4] M. Sundararajan, A. Taly, and Q. Yan, “Axiomatic attribution for deep networks,” in _International Conference on Machine Learning_. PMLR, 2017, pp. 3319–3328.
  * [5] M. Ancona, “Deepexplain github repository,” 2021. [Online]. Available: https://github.com/marcoancona/DeepExplain
  * [6] Y. Zhou, S. Booth, M. T. Ribeiro, and J. Shah, “Do feature attribution methods correctly attribute features?” _arXiv preprint arXiv:2104.14403_ , 2021.
  * [7] J. Gu and V. Tresp, “Saliency methods for explaining adversarial attacks,” _arXiv preprint arXiv:1908.08413_ , 2019.
  * [8] C. Etmann, S. Lunz, P. Maass, and C.-B. Schönlieb, “On the connection between adversarial robustness and saliency map interpretability,” _arXiv preprint arXiv:1905.04172_ , 2019.
  * [9] N. Carlini and D. Wagner, “Audio adversarial examples: Targeted attacks on speech-to-text,” in _2018 IEEE Security and Privacy Workshops (SPW)_. IEEE, 2018, pp. 1–7.
  * [10] Y. Qin, N. Carlini, G. Cottrell, I. Goodfellow, and C. Raffel, “Imperceptible, robust, and targeted adversarial examples for automatic speech recognition,” in _International conference on machine learning_. PMLR, 2019, pp. 5231–5240.
  * [11] T. Dörr, K. Markert, N. M. Müller, and K. Böttinger, “Towards resistant audio adversarial examples,” in _Proceedings of the 1st ACM Workshop on Security and Privacy on Artificial Intelligence_ , 2020, pp. 3–10.
  * [12] S. Hu, X. Shang, Z. Qin, M. Li, Q. Wang, and C. Wang, “Adversarial examples for automatic speech recognition: attacks and countermeasures,” _IEEE Communications Magazine_ , vol. 57, no. 10, pp. 120–126, 2019.
  * [13] H. Abdullah, K. Warren, V. Bindschaedler, N. Papernot, and P. Traynor, “Sok: The faults in our asrs: An overview of attacks against automatic speech recognition and speaker identification systems,” _arXiv e-prints_ , pp. arXiv–2007, 2020.
  * [14] K. Simonyan, A. Vedaldi, and A. Zisserman, “Deep inside convolutional networks: Visualising image classification models and saliency maps,” 2014.
  * [15] S. Bach, A. Binder, G. Montavon, F. Klauschen, K.-R. Müller, and W. Samek, “On pixel-wise explanations for non-linear classifier decisions by layer-wise relevance propagation,” _PloS one_ , vol. 10, no. 7, p. e0130140, 2015.
  * [16] J. Castro, D. Gómez, and J. Tejada, “Polynomial calculation of the shapley value based on sampling,” _Computers & Operations Research_, vol. 36, no. 5, pp. 1726–1730, 2009.
  * [17] S. Lundberg and S.-I. Lee, “A unified approach to interpreting model predictions,” _arXiv preprint arXiv:1705.07874_ , 2017.
  * [18] L. S. Shapley, “A value for n-person games,” _Classics in game theory_ , vol. 69, 1997.
  * [19] P.-J. Kindermans, S. Hooker, J. Adebayo, M. Alber, K. T. Schütt, S. Dähne, D. Erhan, and B. Kim, “The (un) reliability of saliency methods,” in _Explainable AI: Interpreting, Explaining and Visualizing Deep Learning_. Springer, 2019, pp. 267–280.
  * [20] N. Liu, M. Du, R. Guo, H. Liu, and X. Hu, “Adversarial attacks and defenses: An interpretation perspective,” _arXiv preprint arXiv:2004.11488_ , 2020\.
  * [21] N. Kokhlikyan, V. Miglani, M. Martin, E. Wang, B. Alsallakh, J. Reynolds, A. Melnikov, N. Kliushkina, C. Araya, S. Yan _et al._ , “Captum: A unified and generic model interpretability library for pytorch,” _arXiv preprint arXiv:2009.07896_ , 2020.
  * [22] A. Hannun, C. Case, J. Casper, B. Catanzaro, G. Diamos, E. Elsen, R. Prenger, S. Satheesh, S. Sengupta, A. Coates, and A. Y. Ng, “Deep speech: Scaling up end-to-end speech recognition,” 2014.
  * [23] G. Montavon, A. Binder, S. Lapuschkin, W. Samek, and K.-R. Müller, “Layer-wise relevance propagation: an overview,” _Explainable AI: interpreting, explaining and visualizing deep learning_ , pp. 193–209, 2019.
  * [24] L. S. Shapley, “A value for n-person games,” _Contributions to the Theory of Games_ , vol. 2, no. 28, pp. 307–317, 1953.
  * [25] E. Štrumbelj and I. Kononenko, “Explaining prediction models and individual predictions with feature contributions,” _Knowledge and Information Systems_ , vol. 41, pp. 647–665, 12 2013.

##  7 Appendix

In this appendix, we provide additional figures for the same setting as in
Figure 1. All plots show the third, the ninth, and the twelfth frame for the
three different methods: Saliency Map (see Figure 3), LRP (see Figure 4), and
SHAP (see Figure 5).

Figure 3: Saliency Map for the third, ninth and twelfth frame. Later frames
are assigned a higher attribution. Further, low and high MFFC values are
assigned a higher attribution, if the frame itself is transcribed to a letter.
For frames subscribed to a non-letter, the MFCCs’ attribution is distributed
more equally. Figure 4: LRP for the third, ninth and twelfth frame. Later
frames are assigned a higher attribution. Furher, low and mid-range MFCC
values are assigned a higher attribution, if the frame itself is transcribed
to a letter. For frames subscribed to a non-letter, the MFCCs’ attribution is
distrbuted more equally. Figure 5: SHAP for the third, ninth and twelfth
frame. All frames and MFCCs have similar attribution.


# Influence of atomic FAA on ParallelFor and a cost model for improvements

Ran Shuai
Microsoft, Silicon Valley Campus, Mountain View, CA, United States
<EMAIL_ADDRESS>
Abstract - this paper focuses on one of the most frequently visited
multithreading library interfaces - ParallelFor. In this study, it is inferred
that ParallelFor’s end-to-end latency performance is noticeably affected by
the frequency with which fetch-and-add (FAA) is called during program
execution. This can be explained by ParallelFor’s uniform semantics and the
utilization of atomic FAA. To prove this assumption, a battery of tests was
designed and conducted on diverse platforms. From the collected performance
statistics and overall trends, several conclusions were drawn and a cost model
is proposed to enhance performance by mitigating the influence of FAA.1[]
Abstract - this paper focuses on one of the most frequently visited
multithreading library interfaces - ParallelFor. In this study, it is inferred
that ParallelFor’s end-to-end latency performance is noticeably affected by
the frequency with which fetch-and-add (FAA) is called during program
execution. This can be explained by ParallelFor’s uniform semantics and the
utilization of atomic FAA. To prove this assumption, a battery of tests was
designed and conducted on diverse platforms. From the collected performance
statistics and overall trends, several conclusions were drawn and a cost model
is proposed to enhance performance by mitigating the influence of FAA.1

## Introduction

For decades, increasingly high-performance workstations have been adopted in
production environments to boost productivity. These machines are commonly
equipped with multi-core CPU(s) that allow for parallelism in applications and
services. Each CPU core hosts one or two hardware threads (e.g., hyper-
threading) that undertake assigned tasks independently. With a suitable task-
breakdown policy and wait-and-join semantics, an application or service could
allow several of its tasks to run simultaneously, instead of sequentially,
which reduces latency and promotes responsiveness.[1] [2] [3]

To fully utilize the hardware’s computing power, multi-threading software
libraries serve to bridge upstream software applications and hardware threads.
Usually, such libraries create, host, and maintain a set of software threads
known as a thread pool. Moreover, the libraries provide API(s), such as
ParallelFor(…) or ForEach(…), that take a task/function and an integer number
as the iterations to run. Upon being called, the libraries will distribute the
task to all threads in the pool. When the maximum iterations are reached and
all threads have completed the assigned iterations, ParallelFor(…) or
ForEach(…) will return to the caller. One such scenario is openmp [4]—a built-
in library for C++ compilers, such as GNU gcc [5] and LLVM [6]. intelTBB and a
recently published library—TaskFlow [7] serve similar purposes.

According to Amdahl’s law [8], a parallelized application could provide end-
to-end performance benefits as:

$SpeedUp(T)=1/((1-P)+P/T)$

where T is the number of threads and P is the parallelizable fraction of the
application. For ParallelFor, P is always 1; thus, we could expect the gain to
be:

$SpeedUp(T)=T$

## Problem statement

The measurement of performance gains should neither be limited to Amdahl’s
law, nor the assumption that n threads in total “should” bring down the
overall cost to total_cost/number_of_threads. The parallelism provided by
multit-hreading libraries leads to some nontrivial costs that could challenge
the estimation of end-to-end latency. Considering ParallelFor as an example,
its most representative implementations follow a simple semantic:

⬇

void ParallelFor(

function<void(int)>& task,

int N) {

atomic<int> counter{0};

int block_size{...};

function<void(void)> thread_task =

[&] () {

int begin{0};

while ((begin =

counter.FetchAndAdd(block_size))<N){

for (int iter = begin;

iter < min(N,begin+block_size);

iter++) {

task(iter);

}

}

};

for(Thread& thread: threadpool) {

thread.Enqueue(thread_task);

}

thread_task();

for (Thread& thread: threadpool) {

thread.wait(...)

}

}

As seen in this code snippet, the ParallelFor function first wraps up the
input task with a thread task, which utilizes atomic fetch-and-add (FAA) to
acquire a range of iterations for execution. The atomic component serves to
synchronize between threads to avoid a data race. Then, ParallelFor assigns
the thread task to all threads in the pool and waits for all the returns.
Based on the listed logic, the ParallelFor’s caller could be assured that the
input task will be called exactly N times, with an input iterating from 0 to
N-1.

Among all the listed details, “block_size” is a key variable that may
significantly affect the overall end-to-end latency. It decides for how many
iterations the thread should run each input task in the “for” loop.
Equivalently, “block_size” is a variant that determines the size by which “N”
could be divided.

The issue here is that the calling of atomic FAA results in nontrivial cost
because cache invalidation and resynchronization are required to ensure that
all threads visiting the atomic variable see the same value. [9] presented a
keen estimation on atomic overheads as follows:

$L(A,S)=R(S)+E(A)+O$

where A is the type of atomic operation, such as FAA, compare-and-swap (CAS),
or swap (SWP); S is the cache state among Modified, Owned, Exclusive, Shared,
Invalid [10], R(S) is the time-cost of acquiring ownership of the cache in S
state, E(A) is the cost of performing A on the cache, and O represents other
miscellaneous costs. In our case, A is always FAA and S is assumed to be
Shared; hence, a simplified version of our case is:

$L=R+E+O$

According to [9], R takes the most significant part of L, implying that
threads spent most of the time during the interval on acquiring ownership of
the cache. Furthermore, the number of threads and their locality also
influence the cost of R, and therefore, the overall L. For example, two
threads in the cores sharing the same L3 cache tend to spend less time on R
than when the threads are in cores across sockets.

Assuming that the total number of iterations N is to be divided into several
blocks of block size B, and the number of threads is T. Consequently, the
overall end-to-end latency of ParallelFor may be formulated as

$Cost(T,N,L)=N/B*L+O(N)/T$

Based on this formula, we could reasonably infer that Cost(T, N, L) is lower
when B is larger, i.e., a larger block size means less calling of FAA,
resulting in a lower total atomic overhead.

But what is the upper bound of B? We cannot assert that Cost(T, N, L) will
always decrease as the block sizes increase. For instance, considering that we
have T threads fully at our disposal, by setting B to exceed N/T, only fewer
than T threads are allowed the chance to run the input task—the potential of
parallelism is thereby jeopardized. The test that follows shows that the end-
to-end latency would begin falling before B reaches N/T because the threads
are scheduled to run on a physical CPU core at different times, and as the
load sharing among cores is occasionally imbalanced, the threads running time
may vary for a period, which implies that smaller sized blocks are more likely
to match the threads’ running quota perfectly. [11].

Hence, knowing that the block size is expected to be larger to avoid excessive
atomic FAA overhead, it should not exceed a certain limit. The problem lies in
how to determine the proper B value.

## Test and statistics

To address this problem, a series of tests was conducted to resolve the
problem of determining how FAA with varied block sizes would affect the end-
to-end latency of ParallelFor. Additionally, different “sized” tasks were
included, as a task that reads and writes 32 bytes of memory with simple
computations would not have the same performance as a more complex task.
Furthermore, a task that works mostly on IO should behave differently from one
that is more CPU intensive. To address these variants, we implemented a
configurable unit task function:

⬇

unit_task =

[unit_read, unit_write,

unit_computation, ...] (...) {

uint8_t* read_at = ...;

uint8_t* write_at = ...;

uint64_t per_read_computation =

unit_computation / unit_read;

uint64_t write_count = 0;

uint8_t integer = 0;

for (uint64_t i = 0; i < unit_read; ++i) {

integer = read_at[i];

for (uint64_t j = 0; j <

per_read_computation; ++j) {

integer += 1;

}

if (write_count < unit_write) {

write_at[write_count++] = integer;

}

}

while (write_count < unit_write) {

write_at[write_count++] = integer;

}

};

Note that unit_task will be sent to ParallelFor as an input argument. As
observed from the implementation, unit_task references three external
variables unit_read, unit_write, and unit_computation. Here, unit_read denotes
the number of bytes of memory to read; unit_write the number of bytes to
write; and unit_computation the number of computations that should occur along
with execution. By using these variables, we could run tests with tasks of
varied “sizes” to obtain unbiased conclusions.

Furthermore, we implemented a thread pool to provide the ParallelFor function,
following the semantic listed in the previous section. The thread pool allows
a number of threads with fixed affinity settings to be configured to restrict
the threads on certain cores. This helps to reduce the noise from thread
rescheduling between cores and to maintain load balancing.

Finally, to ensure that the test results are more generalized, we prepared a
set of platforms with diverse hardware specifications and computing
capabilities.

  * •

Dell M4 workstation with Intel Xeon® W-3225R @ 3.70 GHZ, Windows 10 Pro
18362.1171

  * •

AMD Ryzen Threadripper 3970X 32-Core Processor @ 3.69 GHz, Windows 10 Pro
19042.1165

  * •

Dell M4 workstation with two Intel® Xeon® Gold 5225R @ 2.20 GHZ, Windows 10
Pro 19042.1165

The W-3225R has one CPU of eight cores, each has its proprietary L1 and L2 but
share the same L3; the AMD 3970X has one CPU of 32 cores, every 4 cores share
an L3; the Gold 5225R has 2 CPUs sitting on separate sockets, each has 24
cores sharing the same L3, whereas L1 and L2 are core private. By using hwloc
[12], graphs of the internal hardware topology were created as follows:

Intel W-3225R

Intel Gold 5225R

AMD Ryzen Threadripper 3970X

With the task, thread pool, and platforms all implemented and ready, the end-
to-end ParallelFor performance was first tested with different block sizes,
varying unit computation, and thread pool sizes on the W-3225R. The latency
was measured using the CPU clocks:

unit read 1024, unit write 1024, unit comp 1024
---
block sizes |  2 threads |  4 threads |  8 threads
1 |  1394900 |  957700 |  569100
2 |  1291900 |  762200 |  445600
4 |  1240400 |  706200 |  430200
8 |  1112800 |  644700 |  462000
16 |  1078100 |  646900 |  437200
32 |  1060400 |  643700 |  447000
64 |  1082100 |  643000 |  494000
128 |  1081400 |  691700 |  558000
256 |  1192000 |  798200 |  632000
512 |  1179800 |  796900 |  800500
1024 |  1585000 |  799100 |  1309500

W-3225R: unit comp 1024, e2e latency in clocks

unit read 1024, unit write 1024, unit comp $1024^{3}$
---
block sizes |  2 threads |  4 threads |  8 threads
1 |  1159900 |  859900 |  465500
2 |  1062200 |  755600 |  419200
4 |  1048400 |  692200 |  4132000
8 |  1028100 |  698500 |  416200
16 |  979000 |  629200 |  418100
32 |  978500 |  633400 |  450500
64 |  997400 |  640300 |  474900
128 |  985900 |  691900 |  571100
256 |  1038200 |  698100 |  549700
512 |  1192700 |  785600 |  788800
1024 |  1386200 |  793300 |  819000

W-3225R: unit comp $1024^{3}$, e2e latency in clocks

unit read 1024, unit write 1024, unit comp $1024^{4}$
---
block sizes |  2 threads |  4 threads |  8 threads
1 |  1307100 |  689200 |  430600
2 |  1236200 |  638500 |  392900
4 |  1203300 |  604200 |  382900
8 |  1197900 |  594800 |  380300
16 |  1159000 |  607000 |  374800
32 |  1197300 |  594500 |  389800
64 |  1232400 |  643700 |  431800
128 |  1274800 |  609400 |  487100
256 |  1275100 |  698000 |  589800
512 |  1233500 |  785300 |  691400
1024 |  1402400 |  1178600 |  1091800

W-3225R: unit comp $1024^{4}$, e2e latency in clocks

For the listed cases, the best performance varies by block size. However,
noting the highlighted cells, it is apparent that mounting the unit
computation decreases the most preferred block size, and increasing the number
of threads that participate in computation produces a similar outcome. To
confirm the observation, we conducted the following tests on the G-5225R:

unit read 1024, unit write 1024, unit comp $1024^{3}$
---
block sizes |  4 threads |  8 threads |  16 threads
1 |  948300 |  555200 |  311700
2 |  900800 |  532700 |  272200
4 |  872500 |  516900 |  267300
8 |  868900 |  522600 |  269100
16 |  865200 |  505900 |  283100
32 |  864000 |  512300 |  302600
64 |  889200 |  502500 |  366500
128 |  874500 |  512200 |  341600
256 |  1023300 |  665100 |  511700
512 |  1041200 |  809700 |  1003300
1024 |  1332100 |  1334300 |  1584000

Gold 5225R: $1024^{3}$ unit comp

unit read 1024, unit write 1024, unit comp $1024^{5}$
---
block sizes |  4 threads |  8 threads |  16 threads
1 |  889300 |  545300 |  314700
2 |  847100 |  494100 |  269500
4 |  826500 |  495900 |  263700
8 |  822900 |  484400 |  288100
16 |  827500 |  489800 |  273500
32 |  839300 |  498900 |  296000
64 |  817400 |  513000 |  305600
128 |  898800 |  502500 |  336600
256 |  1025700 |  515600 |  389600
512 |  1009900 |  661400 |  674600
1024 |  1015400 |  1335000 |  1037500

Gold 5225R: $1024^{5}$ unit comp

unit read 1024, unit write 1024, unit comp $1024^{6}$
---
block sizes |  4 threads |  8 threads |  16 threads
1 |  913000 |  545000 |  313100
2 |  860600 |  521200 |  281000
4 |  830100 |  496800 |  263300
8 |  832000 |  503200 |  264500
16 |  827500 |  498200 |  273400
32 |  814300 |  512300 |  303400
64 |  827200 |  502000 |  294700
128 |  899600 |  517700 |  337200
256 |  1013100 |  671700 |  412000
512 |  1036000 |  660700 |  673700
1024 |  1013900 |  1337500 |  1022000

Gold 5225R: $1024^{6}$ unit comp

The Gold 5225R cases confirm that a larger unit computation reduces the
preferred block size. That there is a constant range of how much computation a
thread can handle in its average CPU quota is a possible explanation. This
means that the larger the unit computation, the smaller the block size should
be to keep the overall block computation in that range. Note:

$computation\\_of\\_block=block\\_size*unit\\_comp$

In addition, FAA overheads are low because threads in the tests are running on
cores sharing the same L3, thus by adding more threads, block size should be
kept smaller to allow for better parallelism. Contrastingly, by defining cores
that share the same L3 as a core group, the opposite trend was observed when
adding more core groups to the tests:

unit read 1024, unit write 1024, unit comp $1024^{2}$
---
block sizes |  24 threads |  36 threads |  48 threads
1 |  309600 |  325100 |  490600
2 |  269400 |  234400 |  498600
4 |  302000 |  228600 |  381200
8 |  264700 |  274800 |  376700
16 |  273700 |  235500 |  236100
32 |  296400 |  257900 |  212000
64 |  301900 |  257800 |  193600
128 |  337000 |  360400 |  420400
256 |  389100 |  406000 |  553600
512 |  701000 |  840800 |  1161600
1024 |  1066900 |  1744600 |  2402800

Gold 5225R: $1024^{2}$ unit comp

unit read 1024, unit write 1024, unit comp $1024^{4}$
---
block sizes |  24 threads |  36 threads |  48 threads
1 |  280000 |  552400 |  588200
2 |  238800 |  538000 |  514800
4 |  232700 |  475300 |  475300
8 |  268900 |  307600 |  358900
16 |  235600 |  226400 |  279100
32 |  259700 |  245400 |  360500
64 |  259400 |  290900 |  287600
128 |  350500 |  366900 |  282600
256 |  436300 |  610400 |  496100
512 |  816500 |  1221700 |  868500
1024 |  1686600 |  2222300 |  1472500

Gold 5225R: $1024^{4}$ unit comp

unit read 1024, unit write 1024, unit comp $1024^{4}$
---
block sizes |  8 threads |  16 threads |  32 threads
1 |  931700 |  550100 |  322000
2 |  718300 |  626700 |  388600
4 |  639200 |  487700 |  315700
8 |  601600 |  401500 |  236200
16 |  560300 |  351500 |  197200
32 |  535800 |  323600 |  174000
64 |  524200 |  322700 |  165800
128 |  546100 |  321100 |  166000
256 |  632600 |  316400 |  162900
512 |  623300 |  323200 |  320800
1024 |  640600 |  621600 |  625800

AMD 3970X: $1024^{4}$ unit comp

For the Gold 5225R, 24 threads were run on a single core group, whereas 36 or
48 threads required two core groups; for the AMD 3970X, every four cores form
a core group, therefore, the tests listed above covered two, four, and eight
core groups.

It is evident that the preferred block size increases by adding core groups,
indicating that the task of N iterations would be split into fewer pieces,
hence fewer FAA would be triggered. The explanation could be that the cache
resynchronizations among the core groups are via media that is markedly less
performant than shared L3, such as the hyper-transport link, therefore, FAA
overheads are considerably higher than previous cases, accordingly, block
sizes should be kept larger to reduce the number of FAA calls.

It has been established that the best block size is proportional to the number
of core groups and inversely proportional to the number of threads and size of
the unit computation. Further investigation commences on the unit read and
write test results:

unit read 64, unit write 1024, unit comp $1024^{6}$
---
block sizes |  4 threads |  16 threads |  24 threads
1 |  1053600 |  358800 |  497400
2 |  967600 |  335400 |  347500
4 |  937800 |  252100 |  280300
8 |  923400 |  245400 |  247400
16 |  912400 |  244100 |  240400
32 |  837600 |  284700 |  153100
64 |  511900 |  270300 |  197600
128 |  549800 |  436300 |  202500
256 |  612900 |  373100 |  276500
512 |  626900 |  717400 |  550800
1024 |  655100 |  687700 |  1124600

Gold 5225R: 64 unit read

unit read 256, unit write 1024, unit comp $1024^{6}$
---
block sizes |  4 threads |  16 threads |  24 threads
1 |  736900 |  352700 |  299200
2 |  695500 |  196200 |  202100
4 |  631600 |  209800 |  181300
8 |  636700 |  182000 |  178400
16 |  634900 |  200400 |  179100
32 |  621700 |  187000 |  192100
64 |  632200 |  238400 |  261800
128 |  683600 |  227500 |  253500
256 |  769800 |  426200 |  367200
512 |  790800 |  480800 |  781600
1024 |  787100 |  654200 |  1521700

Gold 5225R: 256 unit read

unit read 4096, unit write 1024, unit comp $1024^{6}$
---
block sizes |  4 threads |  16 threads |  24 threads
1 |  3511000 |  974500 |  797600
2 |  3436000 |  948600 |  766800
4 |  3433400 |  940300 |  767100
8 |  3581400 |  942900 |  742000
16 |  3841100 |  975600 |  794000
32 |  3845200 |  942100 |  808800
64 |  4071100 |  1069800 |  1065700
128 |  4644200 |  1110300 |  1069800
256 |  4661300 |  1088300 |  1760700
512 |  4638300 |  2215800 |  3464700
1024 |  4212500 |  3271700 |  7041200

Gold 5225R: 4096 unit read

From the numbers listed above, the best block size is clearly also inversely
proportional to the unit read. Notably, with more engaged threads, the block
size decreases accordingly, as was observed in the tests on unit computation.
Next, varied unit write statistics are considered:

unit read 1024, unit write $2^{12}$, unit comp $1024^{6}$
---
block sizes |  8 threads |  16 threads |  32 threads
1 |  1375600 |  457100 |  324900
2 |  1456100 |  639800 |  526100
4 |  1302800 |  487800 |  396400
8 |  1193800 |  422500 |  341700
16 |  1158400 |  383800 |  309400
32 |  1140500 |  378000 |  304800
64 |  1127600 |  362900 |  353200
128 |  1215500 |  362800 |  383700
256 |  1389300 |  365300 |  373100
512 |  1379700 |  690000 |  688800
1024 |  1384100 |  1383200 |  1379600

AMD 3970X: $2^{12}$ unit write

unit read 1024, unit write $2^{14}$, unit comp $1024^{6}$
---
block sizes |  8 threads |  16 threads |  32 threads
1 |  3818400 |  1259400 |  954400
2 |  3932900 |  2068000 |  1273700
4 |  3758100 |  2000000 |  1180800
8 |  3721500 |  1755200 |  1127300
16 |  3692200 |  1931600 |  1118500
32 |  3653800 |  1641100 |  1146200
64 |  3673800 |  1577100 |  1207800
128 |  3919200 |  1530900 |  1316300
256 |  4445700 |  1513100 |  2117700
512 |  4446400 |  2774100 |  2844900
1024 |  4503600 |  4421800 |  4490600

AMD 3970X: $2^{14}$ unit write

unit read 1024, unit write $2^{16}$, unit comp $1024^{6}$
---
block sizes |  8 threads |  16 threads |  32 threads
1 |  13781800 |  8311600 |  7729600
2 |  13626800 |  10221600 |  11584900
4 |  13509000 |  10178700 |  11673600
8 |  13542500 |  10186700 |  11597300
16 |  13703600 |  10284900 |  11546900
32 |  13749300 |  10498000 |  11570900
64 |  13714900 |  10178800 |  11541200
128 |  14650200 |  10367800 |  10099900
256 |  16670700 |  9950500 |  10291700
512 |  16645700 |  12600000 |  12558400
1024 |  16739400 |  16789600 |  16820400

AMD 3970X: $2^{16}$ unit write

Predictably, the unit-write tests suggest similar trends to those of unit
read; as unit write increases, the preferred block size for better performance
decreases. Combining the observations from unit computation as well as read
and write, we can assume that, when the task size is “larger,” the preferred
block size is smaller. Note that the total number of operations in one block
should be calculated as follows:

$complexity\\_of\\_block=block\\_size*task\\_size$
$task\\_size=unit\\_read+unit\\_write+unit\\_comp$

## Cost model and improvements

In summary, we have the following observations:

  * •

The best block size is proportional to the number of core groups (cores share
the same L3 in a core group);

  * •

The best block size is inversely proportional to the number of threads, unit
read, unit write, and unit computation.

This confirms that the distribution of the preferred block size varies
following fixed rules. Intuitively, the proposed cost model is formulated as
follows:

$B=\dfrac{\alpha*G+\delta_{0}}{\beta_{0}*T+\beta_{1}*R+\beta_{2}*W+\beta_{3}*C+\delta_{1}}$

where B is the expected block size; G is the number of core groups; and T, R,
W, and C respectively represent the number of threads, unit read, unit write,
and unit computation. and are unknown parameters that require tuning. To
determine the parameters and evaluate the model’s efficacy, we implemented a
linear regression model using Pytorch [13].

⬇

class CostModel(nn.Module):

def __init__(self):

super(CostModel, self).__init__()

self.power = nn.Linear(1,1)

self.cost = nn.Linear(4,1)

def forward(self, x):

power = self.power(x[:,:1])

cost = self.cost(x[:,1:])

return torch.div(power, cost)

where x is the batched input vectors of the core groups, threads, unit read,
unit write, and unit computation. The raw training input is the list of
previously collected numbers. Each training vector has six columns.

G |  T |  R |  W |  C |  B
---|---|---|---|---|---
1 |  2 |  1024 |  1024 |  1024 |  128
1 |  2 |  1024 |  1024 |  $1024^{2}$ |  64
1 |  2 |  1024 |  1024 |  $1024^{3}$ |  32
1 |  2 |  1024 |  1024 |  $1024^{4}$ |  16
1 |  2 |  1024 |  1024 |  $1024^{5}$ |  8
1 |  2 |  1024 |  1024 |  $1024^{6}$ |  4

Note that the last column is the preferred block size, which is excluded from
x. Next, owing to the overly sparsified inputs compared with the expected
output, we performed data normalization in case the training converges slowly,
albeit with acceptable losses [14]. Hence, we did the following:

  * •

Multiple core group with 100

  * •

Replace units read and write with n, such that $2^{n}$ = unit read/write

  * •

Replace unit computation with p, such that unit computation = $2^{10p}$

Thereby, we have better-shaped training data:

G |  T |  R |  W |  C |  B
---|---|---|---|---|---
100 |  2 |  10 |  10 |  1 |  128
100 |  2 |  10 |  10 |  2 |  64
100 |  2 |  10 |  10 |  3 |  32
100 |  2 |  10 |  10 |  4 |  16
100 |  2 |  10 |  10 |  5 |  8
100 |  2 |  10 |  10 |  6 |  4

Finally, the cost function is:

$loss=(y-y^{\prime})^{2}$

.

The training was then conducted on an NVidia Quadro M4000 with the Cuda
Toolkit 11.4 [15]. After 30 h and approximately $10^{7}$ epochs, the training
data loss on over 200 cases was reduced to 2001.48. Hence, for each input
data, on average, the loss was less than 10. Several examples are listed in
the following table:

G |  T |  R |  W |  C |  B |  Inferred B
---|---|---|---|---|---|---
100 |  2 |  10 |  10 |  1 |  128 |  125
100 |  2 |  10 |  10 |  3 |  64 |  51
100 |  2 |  10 |  10 |  4 |  32 |  39
100 |  2 |  10 |  10 |  6 |  16 |  27
100 |  8 |  10 |  10 |  2 |  32 |  36
100 |  8 |  10 |  10 |  3 |  32 |  30
100 |  8 |  10 |  10 |  5 |  16 |  22
100 |  8 |  10 |  10 |  5 |  16 |  22
100 |  4 |  6 |  10 |  6 |  64 |  80
100 |  4 |  8 |  10 |  6 |  32 |  37
100 |  4 |  12 |  10 |  6 |  16 |  17
100 |  4 |  16 |  10 |  6 |  16 |  11
100 |  8 |  8 |  10 |  6 |  16 |  27
100 |  8 |  10 |  10 |  6 |  16 |  19
100 |  8 |  16 |  10 |  6 |  4 |  10
200 |  8 |  10 |  10 |  1 |  128 |  108
200 |  8 |  10 |  10 |  2 |  64 |  85
200 |  8 |  10 |  6 |  6 |  64 |  112
200 |  8 |  10 |  8 |  6 |  64 |  65
200 |  8 |  10 |  10 |  6 |  64 |  46
200 |  8 |  10 |  14 |  6 |  32 |  29
200 |  8 |  10 |  16 |  6 |  16 |  24
400 |  16 |  6 |  10 |  6 |  128 |  126
400 |  16 |  8 |  10 |  6 |  128 |  92
800 |  32 |  6 |  10 |  6 |  128 |  136
800 |  32 |  10 |  10 |  6 |  64 |  98
800 |  32 |  16 |  10 |  6 |  64 |  69

The formula with trained weights thereby becomes:

$B=\dfrac{1558.31-61.84*G}{693.13-10.48*T-33.71*R-34.50*W-26.84*C}$

## Related work and comparison

A recently published multi-threading library with public access on Github
—Taskflow[7]—has implemented the ParallelFor semantic. According to the
corresponding paper, Taskflow provides a powerful interface that assembles
tasks in topological order and executes with maximum parallelism. Regarding
ParallelFor (under the name of for_each), atomic FAA synchronized threads
compete for the assigned iterations. Each time a thread attempts to acquire a
range of [begin, end), it intends to multiply a decimal constant as q
($=0.5/<numberofthreads>$) with the unfinished part of N, defined as r.
Thereafter, the end is equated to “begin + q * r,” implying that the block
size is “q * r.” Subsequently, when r is smaller than 4 * <number of threads>,
the block size will reduce to 1 until the execution ends. This approach,
though somewhat dynamic, is generally less performant than the one we have
implemented herein with the cost model. The performance data for comparison
are as follows:

unit_read |  Taskflow |  CostModel |  block sizes
---|---|---|---
$2^{6}$ |  3205000 |  257100 |  46
$2^{8}$ |  420400 |  259500 |  27
$2^{10}$ |  462600 |  390400 |  19
$2^{12}$ |  1364700 |  1242900 |  15
$2^{14}$ |  5822300 |  4470400 |  12
$2^{16}$ |  19203300 |  16524300 |  10

W-3225R: 8 T, 1024 unit_write,$2^{60}$ unit_comp, in clocks

unit_write |  Taskflow |  CostModel |  block sizes
---|---|---|---
$2^{6}$ |  580100 |  403400 |  48
$2^{8}$ |  673500 |  377000 |  28
$2^{10}$ |  1167500 |  430700 |  19
$2^{12}$ |  1077100 |  847600 |  15
$2^{14}$ |  3707600 |  3746300 |  12
$2^{16}$ |  15411800 |  15498900 |  10

W-3225R: 8 T, 1024 unit_read,$2^{60}$ unit_comp, in clocks

unit_comp |  Taskflow |  CostModel |  block sizes
---|---|---|---
1024 |  1334200 |  750500 |  46
$1024^{2}$ |  790100 |  744800 |  36
$1024^{3}$ |  496600 |  456000 |  30
$1024^{4}$ |  508500 |  412700 |  25
$1024^{5}$ |  527300 |  424900 |  22
$1024^{6}$ |  479000 |  435300 |  19

W-3225R: 8 T, 1024 unit_read/write, in clocks

unit_read |  Taskflow |  CostModel |  block sizes
---|---|---|---
$2^{6}$ |  420900 |  172200 |  17
$2^{8}$ |  459800 |  157100 |  13
$2^{10}$ |  764700 |  228400 |  11
$2^{12}$ |  797400 |  633500 |  9
$2^{14}$ |  3514300 |  3542800 |  8
$2^{16}$ |  16775400 |  14511900 |  7

G-5225R: 24 T, 1024 unit_write,$2^{60}$ unit_comp, in clocks

unit_write |  Taskflow |  CostModel |  block sizes
---|---|---|---
$2^{6}$ |  1187900 |  507100 |  17
$2^{8}$ |  909300 |  362500 |  13
$2^{10}$ |  537700 |  258000 |  11
$2^{12}$ |  1031500 |  593400 |  9
$2^{14}$ |  4200200 |  5229200 |  8
$2^{16}$ |  28460100 |  28978100 |  7

G-5225R: 24 T, 1024 unit_read,$2^{60}$ unit_comp, in clocks

unit_comp |  Taskflow |  CostModel |  block sizes
---|---|---|---
1024 |  604700 |  287000 |  17
$1024^{2}$ |  549700 |  272300 |  15
$1024^{3}$ |  439200 |  195100 |  14
$1024^{4}$ |  211390 |  192000 |  13
$1024^{5}$ |  367100 |  190100 |  12
$1024^{6}$ |  402900 |  186100 |  11

G-5225R: 24 T, 1024 unit_read/write, in clocks

unit_read |  Taskflow |  CostModel |  block sizes
---|---|---|---
$2^{6}$ |  312700 |  269600 |  13
$2^{8}$ |  348200 |  182100 |  11
$2^{10}$ |  367600 |  320000 |  9
$2^{12}$ |  819500 |  337500 |  8
$2^{14}$ |  1913400 |  1382500 |  7
$2^{16}$ |  7120100 |  4541800 |  6

AMD 3970X: 64 T, 1024 unit_write,$2^{60}$ unit_comp

unit_write |  Taskflow |  CostModel |  block sizes
---|---|---|---
$2^{6}$ |  354300 |  199000 |  13
$2^{8}$ |  339200 |  183500 |  11
$2^{10}$ |  374600 |  274100 |  9
$2^{12}$ |  514400 |  320300 |  8
$2^{14}$ |  1488600 |  1569900 |  7
$2^{16}$ |  8166500 |  8368800 |  6

AMD 3970X: 64 T, 1024 unit_read,$2^{60}$ unit_comp

unit_comp |  Taskflow |  CostModel |  block sizes
---|---|---|---
1024 |  413800 |  34500 |  13
$1024^{2}$ |  439100 |  315100 |  12
$1024^{3}$ |  413300 |  358900 |  11
$1024^{4}$ |  444500 |  340500 |  10
$1024^{5}$ |  5496700 |  352200 |  10
$1024^{6}$ |  398700 |  336800 |  9

AMD 3970X: 64 T, 1024 unit_read/write

As the listed results indicate, with the fine-tuned cost model included in
ParallelFor, a general performance boost of over 20% was observed. There are
also multiple cases in which ParallelFor with the cost model required less
than one-fifth of the time taken by Taskflow. Admittedly, there are also
several cases in which ParallelFor underperforms compared to Taskflow,
however, the lag in each case is relatively negligible. Moreover, we believe
that these issues could be solved by using fine-tuned training data that are
more representative; for example, the training data could be enriched with
more fine-grained case information on task size.

## Conclusion and future work

Based on the analysis and results presented in this paper, we demonstrated
that atomic FAA has a significant effect on the end-to-end latency of
ParallelFor on various platforms. Furthermore, by rigorously examining the
collected performance statistics on neutralizing the FAA overheads, the best
block size for splitting tasks within ParallelFor was found to be virtually
dependent on a few parameters, such as core groups, the number of threads, and
task size. Based on this information, a cost model is proposed. The training
and inferencing of the model confirmed that it was effective when applied to
the collected statistics and offers a significant advantage over existing
counterparts that employ different approaches.

In future work, the CPU frequency and cache latency parameters, which may
significantly promote cost model precision on general platforms, must be
further investigated.

## References

  * [1] D. Marr and F. Binns  “Hyper-Threading Technology Architecture and Microarchitecture 1 Hyper-Threading Technology Architecture and Microarchitecture”, 2002
  * [2] Akhter Jason Roberts  “Multi-Core Programming Increasing Performance through Software Multi-threading Shameem”, 2006
  * [3] N. Tuck and D.M. Tullsen  “Initial observations of the simultaneous multithreading Pentium 4 processor”  In _2003 12th International Conference on Parallel Architectures and Compilation Techniques_ , 2003, pp. 26–34  DOI: 10.1109/PACT.2003.1237999
  * [4] L. Dagum and R. Menon  “OpenMP: an industry standard API for shared-memory programming”  In _IEEE Computational Science and Engineering_ 5.1, 1998, pp. 46–55  DOI: 10.1109/99.660313
  * [5] Richard M. S Brian J. Gough  In _An Introduction to GCC_ , 2004
  * [6] Chris Lattner  In _LLVM and Clang: Next Generation Compiler Technology_ , 2008
  * [7] T. Huang, D. Lin, C. Lin and Y. Lin  “Taskflow: A Lightweight Parallel and Heterogeneous Task Graph Computing System”  In _IEEE Transactions on Parallel & Distributed Systems_ Los Alamitos, CA, USA: IEEE Computer Society, 5555, pp. 1–1  DOI: 10.1109/TPDS.2021.3104255
  * [8] Mark D. Hill and Michael R. Marty  “Amdahl’s Law in the Multicore Era”  In _Computer_ 41.7, 2008, pp. 33–38  DOI: 10.1109/MC.2008.209
  * [9] Hermann Schweizer, Maciej Besta and Torsten Hoefler  “Evaluating the Cost of Atomic Operations on Modern Architectures”, 2020  arXiv:2010.09852 [cs.DC]
  * [10] “MOESI Protocol”, 2021  URL: en.wikipedia.org/wiki/MOESI_protocol
  * [11] Mohan Rajagopalan, Brian T Lewis and Todd A Anderson  “Thread Scheduling for Multi-Core Platforms.”  In _HotOS_ , 2007
  * [12] “Portable Hardware Locality”, 2021  URL: open-mpi.org/projects/hwloc
  * [13] “PyTorch”, 2021  URL: pytorch.org
  * [14] Rob Goot, Barbara Plank and Malvina Nissim  “To Normalize, or Not to Normalize: The Impact of Normalization on Part-of-Speech Tagging”, 2017  arXiv:1707.05116 [cs.CL]
  * [15] “NVidia Cuda Toolkit”, 2021  URL: developer.nvidia.com