# PopSparse: Accelerated block sparse matrix
multiplication on IPU

Zhiyi Li, Douglas Orr*, Valeriu Ohan*, Godfrey Da costa, Tom Murray, Adam
Sanders, Deniz Beker &
Dominic Masters
Graphcore, UK
{zhiyil, douglaso<EMAIL_ADDRESS>
equal contriubtion

###### Abstract

Reducing the computational cost of running large scale neural networks using
sparsity has attracted great attention in the deep learning community. While
much success has been achieved in reducing FLOP and parameter counts while
maintaining acceptable task performance, achieving actual speed improvements
has typically been much more difficult, particularly on general purpose
accelerators (GPAs) such as NVIDIA GPUs using low precision number formats. In
this work we introduce PopSparse, a library that enables fast sparse
operations on Graphcore IPUs by leveraging both the unique hardware
characteristics of IPUs as well as any block structure defined in the data. We
target two different types of sparsity: static, where the sparsity pattern is
fixed at compile-time; and dynamic, where it can change each time the model is
run. We present benchmark results for matrix multiplication for both of these
modes on IPU with a range of block sizes, matrix sizes and densities. Results
indicate that the PopSparse implementations are faster than dense matrix
multiplications on IPU at a range of sparsity levels with large matrix size
and block size. Furthermore, static sparsity in general outperforms dynamic
sparsity. While previous work on GPAs has shown speedups only for very high
sparsity (typically 99% and above), the present work demonstrates that our
static sparse implementation outperforms equivalent dense calculations in FP16
at lower sparsity (around 90%). IPU code is available to view and run at
ipu.dev/sparsity-benchmarks, GPU code will be made available shortly.

##  1 Introduction

The topic of sparsity has gained significant attention in the field of deep
learning research due to its potential for increased computational efficiency,
reduced model size, and closer alignment with brain-like computation. The
notion of sparsity in deep learning most commonly refers to the idea of
sparsifying the model weights with the aim of reducing the associated storage
and compute costs. This is typically done through a single pruning step at the
end of training (Zhu & Gupta, 2017) or potentially through some sparse
training regime (Evci et al., 2019). These approaches have typically achieved
between 90-99$\%$ reduction in model weights while maintaining and acceptable
level of accuracy depending on the model and technique used (Hoefler et al.,
2021).

While the benefits to model size can be easily realised, increased
computational efficiency can often be more difficult to achieve as sparse
computation can be challenging to execute effectively on modern, highly
parallel deep learning accelerators (Qin et al., 2022). As such, sparse
training methods often fall into a gap between theoretical and practical
efficiency. For example Mostafa & Wang (2019) demonstrated FLOP efficient deep
residual CNN training with dynamic sparse reparameterisation techniques but
struggled to achieve speed ups in practice. A key reason behind this is that
unstructured sparsity patterns do not align well with the vectorised
instruction sets that have been so successful in accelerating highly parallel
operations. Therefore, one approach to improving sparse compute efficiency is
to enforce some degree of structure on the sparsity pattern to better align it
with the hardware architecture. This has motivated a wide range of structured
pruning techniques such as neuron (Ebrahimi & Klabjan, 2021), channel-wise (He
et al., 2017), block (Gray et al., 2017), 2:4 (Mishra et al., 2021). These
methods however almost always pay some task performance penalty compared to
equivalent unstructured methods leading to a trade-off between model size and
execution speed which is still not guaranteed to achieve practical performance
benefits.

In this work we present PopSparse, a library for the effective acceleration of
sparse matrix multiplication (matmul) on Graphcore IPUs (Graphcore, 2022b).
IPUs have a number of architectural features that help accelerate sparse
operations, firstly they have a large amount of high bandwidth on-chip SRAM
which drastically improves performance for communication heavy, low arithmetic
efficiency operations. This is critical for sparse operations as the increased
ratio of communication to compute is a natural consequence of weight
sparsification. Furthermore, they use a fine grained MIMD processing model
that partitions work over 1472 independent compute units, here on described as
tiles. This means high degrees of parallelism can be exploited from operations
even if they cannot be structured as a single large matrix multiplication.
Finally, the IPU uses an ahead-of-time compilation model that allows further
optimisations to be employed if computational details, like the structure of
the sparsity, are known at compile time. PopSparse leverages these advantages
to accelerate sparse matrix multiplications on IPU and allows further
performance improvements to be realised by enforcing algorithmic constraints
to the block size and ensuring sparsity patterns are available at compile
time.

We benchmark PopSpare performance on sparse-dense matmul (SpMM) across a range
of problem specifications and compare performance to dense matmul
implementations on IPU as well as GPU baselines.

###  1.1 Contributions

The present work makes the following contributions:

  * •

We introduce the PopSparse library for sparse tensor operations on IPU. The
library supports two flavours of sparse operations: static, where the sparsity
pattern for the sparse operand is fixed; and dynamic, where sparsity pattern
for the sparse operand is updated at runtime.

  * •

We compare benchmark results for static and dynamic sparse modes with a single
sparse-dense SpMM against the dense implementation on IPU and both sparse
(cuSPARSE™, NVIDIA (2022b)) and dense (cuBLAS™, NVIDIA (2022a))
implementations on GPU, showing that PopSparse static sparsity outperforms
competitive dense implementations in FP16 with low sparsity (ranges from 97
$\%$ to 88 $\%$, depending on the matrix size and block size).

  * •

Reviewing the benchmark results, we answer the questions: 1) Under what
conditions do we expect to benefit from sparse operations on IPU? and 2) How
well does IPU performance compare to GPU in sparse operations?

###  1.2 Related work

Various algorithms have been proposed for SpMM acceleration on GPUs. Yang et
al. (2018) introduced novel algorithms (MergeSpMM) for sparse-dense matrix
multiplication on the GPU with merge-based load balancing and row-major
coalesced memory access. Hong et al. (2019) proposed an adaptive sparse tiling
(ASpT) technique and used it to enhance the performance of SpMM. They used
intra-row reordering to enable adaptive tiling. Gale et al. (2020) designed
high-performance SpMM kernels targeted specifically at deep learning
applications.

Using SpMM as the fundamental component, pruning has been used to optimally
sparsify the dense weight matrix in deep neural networks. Zhu & Gupta (2017)
pruned the large models in an unstructured way and compared the accuracy of
the models with their small-dense counterparts across a broad range of neural
network architectures (CNN, LSTM etc.) and found that large-sparse models to
consistently outperform small-dense models and achieve up to 10x reduction in
number of non-zero parameters. Yao et al. (2019) showed a novel fine-grained
unstructured sparsity approach and corresponding pruning method to fixing the
number of non-zeros in small regions of the sparse matrix in matrix row. Wang
(2020) presented SparseRT, a system to support efficient inference with
unstructured weight pruning on GPU.

However, unconstrained magnitude pruning resulting in unstructured sparsity
patterns is challenging to support on traditional hardware accelerators
(Narang et al., 2017; Yao et al., 2019; Wang, 2020). This discovery leads to
structured pruning methods that results in block sparsity. Anwar et al. (2015)
introduced structured sparsity at various scales (channel wise, kernel wise
and intra kernel strided sparsity) for convolutional neural networks. Focusing
on CNN area, a new channel pruning method of structured simplification to
accelerate very deep convolutional neural networks is introduced by He et al.
(2017). Gray et al. (2017) developed highly optimized GPU kernels for neural
network training and inference with block sparsity. Lin et al. (2019) proposed
structure sparsity regularized (SSR) filter pruning scheme to speedup the
computation and reduce the memory overhead of CNNs and it was deployed to a
variety of state of the art CNN structures. Mixture-of-Experts (MoE) training
computation in terms of block-sparse operations was employed by Gale et al.
(2022) and they also developed new block-sparse GPU kernels that efficiently
handle the dynamism present in MoEs.

##  2 IPU architecture

Intelligence Processing Unit (IPU) is an accelerator for machine intelligence,
made up of 1,472 independent compute cores called tiles which co-locate
hardware compute logic with local SRAM. Each tile has 625KB of local on-chip
SRAM memory, leading to 900MB in total for one IPU. High-bandwidth, low-
latency communication among the tiles is achieved through an all-to-all
exchange fabric. The IPU supports a bulk synchronous parallel (BSP) execution
model where each tile first does compute with the data available on its local
SRAM followed by a stage synchronizing with other tiles across all IPUs,
finally exchanging data with other tiles on the same IPU or on a different IPU
(Helal et al., 2022). The efficient communication, fine-grained independent
processing and high level of parallelism are the key factors that enable fast
sparse operations.

Programs run over a set of IPUs and follow a path of specified control flow.
They manipulate variables just like standard programs on a CPU. The variables
being manipulated are large arrays of data (tensors). The programs manipulate
these variables with a set of highly parallel tasks (called vertices) executed
on the threads of the tile processors. These sets of tasks are known as
compute sets (Graphcore, 2022d).

The vertices from the multiple compute sets, and the data they manipulate in
the programs form a computational graph. The computational graph, which we
call Poplar (Graphcore, 2022e) graph, holds the relationship between compute
sets and data. The computational graph gets compiled to binary code using
Poplar compilation tools on the host and then gets loaded onto the IPU. The
duration of converting the computational graph to binary code is called the
compile time. Once the programs are loaded and the IPU configured, a host can
then instruct the IPUs to run these programs. This is defined as runtime.

##  3 PopSparse implementation

PopSparse and the equivalent GPU baselines implement multiple sparse
operations, however our focus will be on a sparse-dense matmul (SpMM),
written:

$\displaystyle Y$ $\displaystyle=(M\odot W)*X\,,$ $\displaystyle M_{ij}$
$\displaystyle=\hat{M}_{\lfloor i/b\rfloor,\lfloor j/b\rfloor}\,,$

where $\odot$ denotes elementwise multiplication, $*$ for inner product,
$Y\in\mathbb{R}^{m\times n}$, $X\in\mathbb{R}^{k\times n}$ are dense output
and input matrices respectively. The sparse weight matrix $(M\odot W)$ is
defined via $M\in\mathbb{B}^{m\times k}$ ($\mathbb{B}=\\{0,1\\}$), a mask that
represents the sparsity pattern, itself derived from
$\hat{M}\in\mathbb{B}^{\lceil m/b\rceil\times\lceil k/b\rceil}$, a block mask
and $W\in\mathbb{R}^{m\times k}$ defines weight values.

In this formulation, $(M\odot W)$ has a block-sparse structure, where
contiguous square blocks of weights of shape $b\times b$ contain all the non-
zero elements, given block-size $b$. The dimensions $m$ and $k$ are referred
to as output and input feature size and $n$ is referred to as batch size,
corresponding to their typical role in weight-sparse neural network
computation.

We define density, $d=\sum_{ij}M_{ij}/(m\cdot k)$, where the standard term
sparsity corresponds to $(1-d)$. We use floating point operation (FLOP) count
to quantify the amount of useful arithmetic work in an SpMM as: $2\cdot m\cdot
k\cdot n\cdot d$. Note that this only counts operations performed on non-zero
values and does not depend on block size $b$.

###  3.1 Overview

The PopSparse library supports unstructured (block size $b=1$) or structured
sparsity ($b=4,8,16$). Only blocks up to size $b=16$ are explicitly considered
as this already achieves the theoretical maximum FLOP rate for the on-tile
compute operations and we expect larger block sizes to negatively impact task
performance (Dietrich et al., 2021). Furthermore, larger blocks could be made
up of many 16x16 blocks if desired. Two sparsity modes, static and dynamic,
are available. Static sparsity has the sparsity pattern $M$ fixed at compile
time while with dynamic sparsity only the maximum density $d^{\mathrm{max}}$
is fixed. Consequently, additional planning is required for dynamic sparsity
during compilation and there is an overhead for partitioning based on a
specific sparsity pattern during runtime in order to balance the quantity of
sparse elements across tiles.

###  3.2 Static sparsity

With static sparsity, during compile time, the sparsity pattern and matrix
shapes ($m$, $k$ and $n$) are known to the partitioner, which splits the non-
zero elements (specific values not known yet) of the sparse matrix across $k$
dimension into $q^{k}$ partitions and the dense matrix across $n$ dimension
into $q^{n}$ partitions. Where the total number of partitions, $q^{k}\cdot
q^{n}$, is upper bounded by the number of tiles. Figure 1a illustrates the
distribution, computation and reduction of the sparse matrix in static sparse.
Splits over the $k$ dimension do not have to be evenly sized, and are chosen
to ensure a balanced distribution of the non-zero elements (denoted with
coloured small blocks in the figure). In the diagram, three distributed
partitions of non-zero elements are mapped onto three tiles. A Poplar
(Graphcore, 2022e) graph (compute graph) is then constructed based on the
partition information.

At runtime, the specific non-zero values of $W$ are provided by the host and
re-ordered to match the distribution of non-zero elements on tiles of the IPU.
As this distribution is known in advance, no extra exchange of data is needed.
Local dot product computation with the dense matrix is then executed and there
is a final reduction across tiles to give the output dense matrix. A flow
chart for static sparsity can be found in Figure 5a of the Appendix A.1.

###  3.3 Dynamic sparsity

With dynamic sparsity, the maximum number of non-zero elements for the sparse
operand is fixed, while the sparsity pattern is updated during runtime. To
minimise compute cycles, we employ a planner during compile time to optimise
the partitioning while accommodating for the full range of sparsity patterns
that can be defined by the host at runtime. Specifically, the planner
determines how many equal parts each dimension ($m,k,n$) should be divided
into with each tile being assigned to a single partition.

At runtime, as the sparsity pattern could change for each run, compared to
static sparsity, there is an additional distribution of sparse matrix indices
and non-zero values by the partitioner. This is demonstrated in Figure 1b.
Furthermore, as fixed sized partition over $m$ and $k$ dimension is required,
the number of non-zero elements in each partition may not be balanced. In
Figure 1b the B elements on the second partition of $k$ dimension do not fit
on $\mathrm{Tile1}$. Three of the B elements overflow to $\mathrm{Tile2}$.
However, the $\mathrm{Tile2}$ does not have all the partition information
(slices of $m,k,n$) corresponding with B elements to compute the result.
Consequentially, extra steps of propagation are induced to finish the
computation. A dynamic number of steps is required (depending on the sparsity
pattern) to propagate information and compute the final result.

Figure 5b in Appendix A.1 shows a diagram of the dynamic sparse-dense matmul
operation during compile time and runtime. More details about dynamic sparsity
can be found in Appendix A.2.

(a) Static

(b) Dynamic

Figure 1: Illustration of static and dynamic sparse partitioning of the input
feature dimension, $k$. Note that $m\\!=\\!k\\!=\\!9$ and we split work over 3
tiles with $q^{k}\\!=\\!3$, $q^{m}\\!=\\!q^{n}\\!=\\!1$. Static partitioning
can adapt the split positions to the known sparsity pattern, removing the need
for dynamic sparsity’s allocation overflow (b.1) and redistribution phase
(b.2). Static execution also allows optimal exchange of inputs, (a.1) vs (b.1)
and in output reduction, (a.2) vs (b.3).

Overall our dynamic sparse implementation has a number of additional costs
compared to the static case:

  * •

On-tile compute requires additional control flow which incurs some cost
overhead.

  * •

Exchange phases must account for the largest communication volume possible and
thus are less efficient.

  * •

When data is unbalanced, additional propagation and compute phases are
required to rebalance the data. The number of steps required is dependent on
the degree of the imbalance.

Table 1: APIs used for benchmarking. Device | Implementation | API | Block size | Dynamic | Datatype support
---|---|---|---|---|---
IPU | Dense | poplin::matMul | – | – | FP16, FP32
IPU | Static sparse (popsparse::) | static_::sparseDenseMatMul | 1,4,8,16 | ✗ | FP16, FP32
IPU | Dynamic sparse (popsparse::) | dynamic::sparseDenseMatMul | 1,4,8,16 | ✓ | FP16, FP32
GPU | Dense | cublasGemmEx | – | – | FP16, FP32
GPU | Compressed Sparse Row (CSR) | cusparseSpMM | 1 | ✓ | FP16∗, FP32
GPU | Block Sparse Row (BSR) | cusparseSbsrmm | $2^{b^{\prime}}$ | ✓ | FP32
$*$ compute in FP32, inputs/outputs in FP16 |  |  |

##  4 Benchmarks

Our microbenchmarking experiments explore a single sparse-dense matmul SpMM:
$Y=(M\odot W)*X$, on IPU and GPU. The APIs used for IPU experiments and GPU
baselines are shown in Table 1. The range of parameters that were benchmarked
is detailed in Table 2.

Table 2: Ranges of parameters swept for benchmarks. Parameter | Range (start:step:end or list of values)
---|---
feature size ($m=k$) | $2^{8:1:13}$
batch size ($n$) | $2^{2:2:16}$
block size ($b$) |  $1$ (unstructured), $4,8,16$
density factor ($d$) |  $1$ (dense), $1/4,1/8,1/16,1/32$
data type | FP16, FP16∗, FP32
$*$ compute in FP32, inputs/outputs in FP16

#### IPU

The operation is executed a single time on a single Bow IPU (Graphcore, 2022b)
in a Bow-2000 chassis, with randomly generated sparsity pattern and values. We
extract cycle count information and convert these cycle counts into TFLOP$/$s
values given a constant clock of 1.85 GHz (Graphcore, 2022c). Host transfers
are excluded from measured time.

#### GPU baselines

Sparse implementations on GPU are provided by the cuSPARSE library111cuSPARSE
version 11.6.2 (NVIDIA, 2022b). These are divided according to the sparse
format used, with no distinction between static and dynamic sparsity patterns.
We consider compressed sparse row (CSR) and block sparse row (BSR), for
unstructured and block sparsity respectively.222We skip the detailed
implementation here for brevity, referring to Yang et al. (2018) and Huang et
al. (2020) for a discussion of such considerations (although these do not
discuss the implementation of cuSPARSE directly). There are other vendor-
provided and third-party libraries for sparse computation, but we consider
these for sake of direct comparison against PopSparse (see Appendix B for more
information). Dense benchmarks used cuBLAS (NVIDIA, 2022a).

To measure runtime, we generate a random sparsity pattern and values, copy to
device, execute 25 iterations of the operation and copy results to host for
validation. We start timing after 5 iterations, and measure wall clock time
using cudaEventRecord, at millisecond resolution, over all remaining
iterations. We use cudaDeviceSynchronize before the start and after the stop
of wall clock recording to ensure previous matmul operation is complete. All
experiments were performed on an A100 GPU running in a 4 x A100-SXM4-40G
chassis with CUDA version 11.3.

##  5 Results

In our benchmarking experiments, we explore the performance of static and
dynamic sparsity on IPU, compared with dense computation on IPU and both dense
and sparse computation on GPU.

For most results, we allow batch size $n$ to vary, choosing the batch size
leading to best performance for each configuration. This is appropriate for
batched inference in a weight sparse neural network, as batch size is a free
parameter (up to a memory limit) and the choice depends on the machine
learning application. Note that we consider only non-zero elements in the
sparse matrix to calculate FLOP$/$s, as defined in Section 3.

###  5.1 Dense baseline performance

Figure 2 shows dense matmul performance, as batch size and feature size vary
for FP16 and FP32. In FP16, we see chip-for-chip parity between IPU and GPU at
large batch size, while the IPU is more resilient to low batch size. This is
because lower arithmetic intensity operations leads to more data movement with
the same amount of compute. The SRAM on IPU enables more efficient data
movement.

In FP32, the IPU has a clear advantage due to Accumulating Matrix Product
(AMP) units (Graphcore, 2022a) being available in FP32, whereas Tensor Cores
(NVIDIA, 2022c) are only available in FP16.

Figure 2: Dense performance for large square matrices on IPU and GPU.

###  5.2 Static vs. dynamic sparsity on IPU

It has already been discussed in Section 3.3 that static sparse performance
should exceed dynamic. This is visible in Table 3, showing the speedup of
dynamic and static sparsity versus dense for a variety of configurations. Over
various block sizes and data types, static sparsity shows higher speedup than
dynamic. The sparse computation speedup also increases with block size. More
discussion can be found in Section 5.3. Moreover, we can see that the sparsity
speedup for FP32 is better than for FP16. This is because core arithmetic is
more expensive in FP32, so FLOP savings count more (versus sparse overhead).

Table 3: Dynamic sparse vs. static sparse on IPU, $m=k=4096$, density $d=1/16$, best over batch size $n$, throughput values compared with dense. Block size | Type | Dynamic/dense | Static/dense
---|---|---|---
1 | FP16 | 0.4 | 0.7
1 | FP32 | 0.9 | 1.4
4 | FP16 | 1.0 | 1.5
4 | FP32 | 2.7 | 3.2
16 | FP16 | 1.9 | 4.9
16 | FP32 | 3.8 | 5.6

###  5.3 When does a sparse implementation outperform dense on IPU?

Our results show that sparse implementations are faster than dense on IPU at
low density, with large block size and large feature size.

(a) IPU

(b) GPU

Figure 3: LABEL:sub@fig:ipu-density IPU FP16 and LABEL:sub@fig:gpu-density GPU
block-sparse matmul performance as density varies for various block size $b$,
square feature size $m=k=4096$, best over batch size $n$.

#### Low density

Since the purpose of sparse implementations is to take advantage of zeros, it
is unsurprising that decreasing non-zero density leads to a performance
advantage over dense. In Figure 3a, we show the plot of compute FLOP/s (in log
scale) vs. density with fixed feature size. This shows the density scaling
performance of dense, dynamic sparse and static sparse for block size
$b=1,16$. The dense implementation shows linear scaling with density — since
zeros are not counted in the FLOP/s calculation, the amount of useful work
decreases with $d$, while the runtime is unchanged. While on the other hand
for a sparse implementation, perfect scaling would predict constant FLOP/s as
density varies, with both work and runtime scaling with $d$. We see nearly-
perfect scaling from static sparsity in this range, whereas dynamic sparsity
shows higher overheads. In Figure 3a, unstructured ($b=1$) static sparsity
outperforms dense at a density of 5$\%$.

#### Large block size

Block sparsity speeds up sparse computation for two main reasons. First, there
is less overhead incurred to store and process the metadata that encode the
sparsity pattern. Second, it allows implementations to process non-zero
submatrices rather than just vectors, making more effective use of the
hardware. Figure 4a shows the magnitude of these improvements, which are
considerable: $2.1\times$ for blocks size $b=4$ and $6.6\times$ for $b=16$
(static sparsity). Despite this advantage, few sparsity techniques in the
literature consider block sparsity, so these results could motivate the field
to explore new ML algorithms for inducing blocks of zeros.

#### Large feature size

Figure 4b shows the effect of feature size on sparse performance. Sparse
performance improves more with feature size than dense performance. This is
because increasing feature size makes it easier to spread work evenly across
tiles.

#### Will my application speed up?

The multidimensional nature of our sweep makes it hard to summarise results on
a single plot. To make it easier to evaluate whether a particular problem can
be accelerated using PopSparse, we provide a grid of static sparse speedup
ratios in Figure 7. We also fit a power-law model to our static sparse
results, illustrated in Figure 4c. This predicts the condition for achieving a
speedup: $0.0013\cdot m^{0.59}\cdot d^{-0.54}\cdot b^{0.50}>1$. This is in
line with our main observations: large feature size, low density and large
block size all favour sparse implementations. We recommend using this for
interpolation only, as we do not expect good generalisation beyond the sweep
parameters of Table 2.

(a)

(b)

(c)

Figure 4: IPU block-sparse matmul performance as LABEL:sub@fig:ipu_block_size
block size or LABEL:sub@fig:ipu_feature_size feature size varies. Base
configuration: FP16, $m=k=4096$, density $1/16$, block size $16$, best over
$n$. Figure LABEL:sub@fig:ipu_model shows the fit of a power-law model for the
sparse speedup ratio (static sparse to dense TFLOP/s), for FP16, best over
$n$, for each $(m,d,b)$ tested.

###  5.4 How well does IPU perform compared to GPU in sparse operations?

Figure 3b shows GPU performance as density varies, showing that BSR sparsity
in FP32 is worse than the FP16 dense baseline, even below $2\%$ density.
However, we also observe that GPU sparse performance scales well as density
decreases. We suspect the main reason for the sparse-dense performance gap is
that the BSR implementation does not support FP16, and therefore cannot use
Tensor Cores to accelerate the arithmetic (see Figure 2 for the FP32 versus
FP16 dense performance). Note that FP16 sparsity is available in the blocked
ELL format, which we did not benchmark as it did not match the API of general
block sparsity and so would require explicit padding. However, it is probable
that the gains due to Tensor Core acceleration would negate any padding
overheads in this case, so we consider this for future work.

Since dense methods perform best on GPU, and GPU dense performs similarly to
IPU dense (see Figure 2), our previous comparisons already give an approximate
answer to the question of when sparse operations on IPU outperform GPU:
whenever sparse operations outperform dense operations on IPU. Therefore
Figure 7 in Appendix C can also be used as an approximate guide to compare IPU
sparsity with GPU.

##  6 Conclusions

In this work, we introduce the PopSparse library for sparse matrix
multiplication on IPU and show the benchmarks of SpMM on IPU with static
sparsity and dynamic sparsity. We also compare the sparse and dense results to
a GPU baseline.

We have found that there are configurations where sparse implementations on
IPU can outperform dense on IPU and all tested implementations on GPU
(cuSPARSE CSR and BSR APIs).

As an approximate guide, sparsity brings speedup over dense (FP16, large batch
size for both) when:

  * •

Static, block size $b=1$: features $(m=k)\geq 4096$, density $d\leq 1/32$.

  * •

Static, block size $b\geq 4$: features $(m=k)\geq 4096$, density $d\leq 1/8$.

  * •

Dynamic sparsity: block size $b\geq 8$, features $(m=k)\geq 4096$, density
$d\leq 1/32$.

The requirements for both static and dynamic sparsity to outperform dense on
IPU are much more modest in FP32, however FP16 is generally preferred for
weight-sparse deep learning models.

The ranges which show good performance are somewhat challenging to use today
in the context of weight sparse training and inference. Only a few deep
learning literature (for example the Pixelated Butterfly from Dao et al.
(2021) and Towards Structured Dynamic Sparse Pre-Training of BERT from
Dietrich et al. (2021)) explore effective schemes for block sparsity. This
might because finding block sparse patterns that do not degrade performance is
a hard problem, and that on theoretical efficiency metrics (per non-zero
FLOP), unstructured sparsity will always appear as good or better than block
sparsity. We hope that this work shows that block sparsity is a promising
method for achieving practical acceleration of sparse models and will motivate
further investigation into effective block sparse pruning algorithms.

For the next step, we aim to demonstrate the static block sparsity to
accelerate large model inference on IPU, achieving both high memory and high
compute efficiency.

## References

  * Anwar et al. (2015) Sajid Anwar, Kyuyeon Hwang, and Wonyong Sung.  Structured pruning of deep convolutional neural networks, 2015.  URL https://arxiv.org/abs/1512.08571.
  * Dao et al. (2021) Tri Dao, Beidi Chen, Kaizhao Liang, Jiaming Yang, Zhao Song, Atri Rudra, and Christopher Ré.  Pixelated butterfly: Simple and efficient sparse training for neural network models, 2021.  URL https://arxiv.org/abs/2112.00029.
  * Dietrich et al. (2021) Anastasia Dietrich, Frithjof Gressmann, Douglas Orr, Ivan Chelombiev, Daniel Justus, and Carlo Luschi.  Towards structured dynamic sparse pre-training of BERT, 2021.  URL https://arxiv.org/abs/2108.06277.
  * Ebrahimi & Klabjan (2021) Abdolghani Ebrahimi and Diego Klabjan.  Neuron-based pruning of deep neural networks with better generalization using kronecker factored curvature approximation, 2021.  URL https://arxiv.org/abs/2111.08577.
  * Evci et al. (2019) Utku Evci, Trevor Gale, Jacob Menick, Pablo Samuel Castro, and Erich Elsen.  Rigging the lottery: Making all tickets winners, 2019.  URL https://arxiv.org/abs/1911.11134.
  * Gale et al. (2020) Trevor Gale, Matei Zaharia, Cliff Young, and Erich Elsen.  Sparse GPU kernels for deep learning, 2020.  URL https://arxiv.org/abs/2006.10901.
  * Gale et al. (2022) Trevor Gale, Deepak Narayanan, Cliff Young, and Matei Zaharia.  Megablocks: Efficient sparse training with mixture-of-experts, 2022.  URL https://arxiv.org/abs/2211.15841.
  * Graphcore (2022a) Graphcore.  Mixed-precision arithmetic for AI: A hardware perspective, 2022a.  URL https://docs.graphcore.ai/projects/ai-float-white-paper/en/latest/ai-float.html#lower-precision-for-higher-power-efficiency.
  * Graphcore (2022b) Graphcore.  Bow IPU processor, 2022b.  URL https://www.graphcore.ai/bow-processors.
  * Graphcore (2022c) Graphcore.  Bow-2000 IPU-machine technical specifications, 2022c.  URL https://docs.graphcore.ai/projects/bow-2000-datasheet/en/latest/product-description.html#technical-specifications.
  * Graphcore (2022d) Graphcore.  IPU programmer’s guide, 2022d.  URL https://docs.graphcore.ai/projects/ipu-programmers-guide/en/latest/programming_model.html#loading-and-running-programsy.
  * Graphcore (2022e) Graphcore.  Poplar and poplibs user guide, 2022e.  URL https://docs.graphcore.ai/projects/poplar-user-guide/en/latest/index.html.
  * Gray et al. (2017) Scott Gray, Alec Radford, and Diederik P. Kingma.  GPU kernels for block-sparse weights.  2017\.
  * He et al. (2017) Yihui He, Xiangyu Zhang, and Jian Sun.  Channel pruning for accelerating very deep neural networks, 2017.  URL https://arxiv.org/abs/1707.06168.
  * Helal et al. (2022) Hatem Helal, Jesun Firoz, Jenna Bilbrey, Mario Michael Krell, Tom Murray, Ang Li, Sotiris Xantheas, and Sutanay Choudhury.  Extreme acceleration of graph neural network-based prediction models for quantum chemistry, 2022.  URL https://arxiv.org/abs/2211.13853.
  * Hoefler et al. (2021) Torsten Hoefler, Dan Alistarh, Tal Ben-Nun, Nikoli Dryden, and Alexandra Peste.  Sparsity in deep learning: Pruning and growth for efficient inference and training in neural networks, 2021.  URL https://arxiv.org/abs/2102.00554.
  * Hong et al. (2019) Changwan Hong, Aravind Sukumaran-Rajam, Israt Nisa, Kunal Singh, and P. Sadayappan.  Adaptive sparse tiling for sparse matrix multiplication.  _Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming_ , 2019.
  * Huang et al. (2020) Guyue Huang, Guohao Dai, Yu Wang, and Huazhong Yang.  Ge-spmm: General-purpose sparse matrix-matrix multiplication on GPUs for graph neural networks.  In _SC20: International Conference for High Performance Computing, Networking, Storage and Analysis_. IEEE, 2020.
  * Lin et al. (2019) Shaohui Lin, Rongrong Ji, Yuchao Li, Cheng Deng, and Xuelong Li.  Towards compact ConvNets via structure-sparsity regularized filter pruning, 2019.  URL https://arxiv.org/abs/1901.07827.
  * Mishra et al. (2021) Asit Mishra, Jorge Albericio Latorre, Jeff Pool, Darko Stosic, Dusan Stosic, Ganesh Venkatesh, Chong Yu, and Paulius Micikevicius.  Accelerating sparse deep neural networks, 2021.  URL https://arxiv.org/abs/2104.08378.
  * Mostafa & Wang (2019) Hesham Mostafa and Xin Wang.  Parameter efficient training of deep convolutional neural networks by dynamic sparse reparameterization, 2019.  URL https://arxiv.org/abs/1902.05967.
  * Narang et al. (2017) Sharan Narang, Erich Elsen, Gregory Diamos, and Shubho Sengupta.  Exploring sparsity in recurrent neural networks, 2017.  URL https://arxiv.org/abs/1704.05119.
  * NVIDIA (2022a) NVIDIA.  API reference guide for cuBLAS, 2022a.  URL https://docs.nvidia.com/cuda/cublas/.
  * NVIDIA (2022b) NVIDIA.  API reference guide for cuSPARSE, 2022b.  URL https://docs.nvidia.com/cuda/cusparse/.
  * NVIDIA (2022c) NVIDIA.  NVIDIA tensor cores, 2022c.  URL https://www.nvidia.com/en-gb/data-center/tensor-cores/.
  * Qin et al. (2022) Eric Qin, Raveesh Garg, Abhimanyu Bambhaniya, Michael Pellauer, Angshuman Parashar, Sivasankaran Rajamanickam, Cong Hao, and Tushar Krishna.  Enabling flexibility for sparse tensor acceleration via heterogeneity, 2022.  URL https://arxiv.org/abs/2201.08916.
  * Wang (2020) Ziheng Wang.  Sparsert: Accelerating unstructured sparsity on GPUs for deep learning inference, 2020.  URL https://arxiv.org/abs/2008.11849.
  * Yang et al. (2018) Carl Yang, Aydın Buluç, and John D Owens.  Design principles for sparse matrix multiplication on the GPU.  In _Euro-Par 2018: Parallel Processing: 24th International Conference on Parallel and Distributed Computing, Turin, Italy, August 27-31, 2018, Proceedings_ , 2018.
  * Yao et al. (2019) Zhuliang Yao, Shijie Cao, Wencong Xiao, Chen Zhang, and Lanshun Nie.  Balanced sparsity for efficient DNN inference on GPU.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 33(01):5676–5683, jul 2019.  doi: 10.1609/aaai.v33i01.33015676.  URL https://doi.org/10.1609%2Faaai.v33i01.33015676.
  * Zhu & Gupta (2017) Michael Zhu and Suyog Gupta.  To prune, or not to prune: exploring the efficacy of pruning for model compression, 2017.  URL https://arxiv.org/abs/1710.01878.

##  Appendix A More details about static and dynamic sparsity

###  A.1 Flow chart for static and dynamic sparsity

(a) Static

(b) Dynamic

Figure 5: Flow chart for static and dynamic sparsity.

###  A.2 Details about dynamic sparsity

With dynamic sparsity, the total number of non-zero elements for the sparse
operand is fixed (or has a known maximum) while the sparsity pattern is
updated during runtime.

There are three key components for the implementation of the dynamic sparsity
in PopSparse:

  * •

A planner which produces the plan for optimum partition and device operation.

  * •

A host utility which encodes a sparsity pattern to be uploaded to the device
and used by the device-side implementation.

  * •

The implementation on the device that is based on the plan produced by the
planner. This constructs the variables, compute sets and programs needed to
run the ops on the device.

The planner consists primarily of a partition between tiles and vertices of
the computation graph used on each tile. The partitioner determines how each
dimension ($m,k,n$) should be divided into when calculating the result of the
sparse-dense matmul. It is decided at compile time based on the matrix sizes
and density factor and does not change with sparsity pattern. All partitions
of each dimension are of equal size except the last which may be smaller if
the number of partitions in that dimension does not evenly divide. For
example, if $q^{m}$ is the number of partitions to divide the dimension $m$
into, there will be $q^{m}-1$ partitions of size $\lfloor m/q^{m}\rfloor$ and
the last partition with size $m-(q^{m}-1)\cdot\lfloor m/q^{m}\rfloor$. The
total number of partitions, $q^{\mathrm{total}}=q^{m}\cdot q^{k}\cdot q^{n}$.

Each tile will be assigned a single partition, for which it is responsible for
computing its portion of the partial result. Therefore the number of tiles
used is equal to $q^{\mathrm{total}}$.

The host utility encodes the sparse matrix row and column indices as
$\mathrm{metaInfo}$. The $\mathrm{metaInfo}$ along with the non-zero values of
the sparse matrix ($\mathrm{nzValues}$) are splits into buckets. The size of
these buckets is set by the planner based on the maximum density that was
fixed at compile time. The buckets are mapped to each of the
$q^{\mathrm{total}}$ number of partitions so that all partitions that are
assigned to tiles have equal and fixed size buckets with $\mathrm{metaInfo}$
and $\mathrm{nzValues}$. The bucket size is based on distributing the total
number of non-zero values for the sparse tensor across $q^{m}\cdot q^{k}$
partitions evenly:

$N_{\mathrm{non\mbox{-}zero}}=m\cdot k\cdot d^{\mathrm{max}}/(q^{m}\cdot
q^{k})\,,$

where $N_{\mathrm{non\mbox{-}zero}}$ is the average number of non-zero
elements in a single bucket on a single tile, based on maximum density
$d^{\mathrm{max}}$. The buckets are repeated over $q^{n}$ partitions. A
similar estimate is done for the size of $\mathrm{metaInfo}$ for a single
bucket but since we have a varied sparsity pattern, some extra headroom is
given in the size of these buckets.

With the device implementation, we have compute graph vertices created on each
tile with:

  * •

The slice of the dense input required to compute this partition’s result.

  * •

The bucket of the input sparse tensor mapped to this tile (both
$\mathrm{metaInfo}$ and $\mathrm{nzValues}$).

  * •

The slice of the dense output partials that will hold the results for this
partition.

The execution steps can be summarized as following:

  * •

Distribution phase: The tile reads through the $\mathrm{metaInfo}$ and
$\mathrm{nzValues}$ in the bucket on a tile that fall within the partition to
be processed on this tile. If all the non-zero values for all $q^{m}\cdot
q^{k}$ partitions are distributed in buckets on tiles assigned the same
partition, the calculation is complete. If not, a further series of dynamic
exchange + compute steps (propagation) are executed to complete the
calculation.

  * •

Propagation phase, use exchanges to move buckets between tiles. This phase
repeats until compute is complete.

A, Check information encoded in $\mathrm{metaInfo}$ to see if the calculation
is complete, exit if complete.

B, If not, exchange buckets to shift between tiles.

C, Compute, dense input is the same but the contents of the buckets on tiles
have changed.

  * •

Reduce partial results across $q^{k}$ to get the final output.

The distribution and propagation phases are done with the dynamically executed
steps where the number of steps are decided by the partitioner for a given
sparsity pattern.

To further illustrate the distribution and propagation phases, we use two
extreme cases. The best case scenario is when non-zero values in the sparse
operand are evenly spread among $q^{m}\cdot q^{k}$ partitions. In this
balanced case, the buckets mapped to tiles assigned each $q^{m}\cdot q^{k}$
partition should have space enough to hold all non-zero values falling within
that partition. Then we can complete the operation in the distribution phase
and no further propagation phases are needed. At the same time, each tile does
an equal share of the total FLOPs. The worst case scenario is when all non-
zero values in the sparse operand lie within a single $q^{m}\cdot q^{k}$
partition. The first tile in which all the non-zero values lie must do all the
FLOPs for the operation, and all the other tiles do no useful work. Moreover,
the bucket size could only take $1/(q^{m}\cdot q^{k})$ of the non-zero values.
As a result, all the non-zero elements must be spread between all the buckets.
This means we must exchange + compute up to $q^{m}\cdot q^{k}$ times to
complete the operation.

To give an example, in Figure 6a, the best scenario, there are two non-zero
values for each partition (in total four partitions). Each bucket contains two
$\mathrm{nzValues}$ and no further exchange is needed. With the worst
scenario, as denoted in Figure 6b, all the non-zero values lie within the
first tile and all the rest three tiles do no useful work.

(a)

(b)

Figure 6: Examples of the best (left) and worst (right) case scenarios for
distribution and propagation phases. Cells marked black denote non-zero values
and white denote zeros.

Somewhere in-between the two extremes described, there is a choice about how
to spill non-zero elements from buckets which become too full (due to non-
uniform distribution of sparsity pattern) to other buckets. When choosing a
bucket to spill elements to, we can define a concept of distance based on the
nested iteration (from innermost to outermost around the partitions of $n$,
$k$ and $m$) and attempt to minimise this distance for all elements.

##  Appendix B CUDA API that were not considered in the current work

We note that the CUDA libraries offer support for additional, more restrictive
sparsity patterns. We did not benchmark these, as there are no equivalent
implementations on the IPU, and it is hard to quantify the modelling cost of a
stricter sparsity constraint. Therefore, we only seek to compare identical
computations on IPU and GPU. The CUDA APIs that we discarded due to this
constraint were:

cusparseSpmm with cuSPARSE blocked ELL format. This format is a block-sparse
matrix format with a maximum non-zero blocks per row. It stores an array of
block column indices with a marker (-1) for missing blocks. Note that this is
one of the few CUDA SpMM formats that supports FP16 compute. It would be
possible to use this API to implement a static block-sparse pattern by padding
rows to the maximum number of non-zero blocks, but this would presumably have
a performance impact.

cuSPARSELt™ with N:M structured sparsity. This enforces a regular sparsity
rule, for example 2:4, which specifies that exactly 2 of every chunk of 4
contiguous weights are non-zero. This is a strong regularity constraint on
sparsity patterns and is hard to compare to block sparsity. This method has
explicit hardware support in NVIDIA A100 GPUs.

##  Appendix C Overview of the static sparse and dense results on IPU

Figure 7 shows a more complete view of the speedup ratio of static sparse to
dense, as density $d$, block size $b$, feature size $m=k$ and batch size $n$
all vary. Dark grey blocks indicate missing data (could not fit on single IPU
memory). Same conclusions can be drawn as those stated in Section 5.3. As GPU
dense performs similarly to IPU dense (see Figure 2), this figure can also be
used as an approximate guide to compare IPU sparsity with GPU.

(a)

(b)

Figure 7: Grid showing the speedup ratio of static sparse to dense.


# Manipulating Drivers’ Mental Workload: Neuroergonomic Evaluation of the
Speed Regulation N-Back Task Using NASA-TLX and Auditory P3a

Nikol Figalová<EMAIL_ADDRESS>0000-0001-7618-4852 Clinical and
Health Psychology, Inst. of Psychology and Education, Ulm UniversityAlbert-
Einstein-Allee 45UlmGermany ,  Jürgen Pichen<EMAIL_ADDRESS>0000-0003-2844-0465 Human Factors, Inst. of Psychology and Education, Ulm
UniversityAlbert-Einstein-Allee 45UlmGermany89081 ,  Vanchha Chandrayan
0000-0003-4242-5747 Human Factors, Inst. of Psychology and Education, Ulm
UniversityAlbert-Einstein-Allee 45UlmGermany ,  Olga Pollatos
0000-0002-0512-565X Clinical and Health Psychology, Inst. of Psychology and
Education, Ulm UniversityAlbert-Einstein-Allee 45UlmGermany ,  Lewis Chuang
0000-0002-1975-5716 Human and Technology, Inst. for Media Research, Faculty of
Humanities, Chemnitz University of TechnologyChemnitzGermany and  Martin
Baumann  0000-0002-2668-2527 Human Factors, Inst. of Psychology and Education,
Ulm UniversityAlbert-Einstein-Allee 45UlmGermany

(2023)

###### Abstract.

Manipulating MW in driving simulator studies without the need to introduce a
non-driving-related task remains challenging. This study aims to empirically
evaluate the modified speed regulation n-back task, a tool to manipulate
drivers’ MW. Our experiment involved 23 participants who experienced a 0-back
and 2-back driving condition, with task-irrelevant novel environmental sounds
used to elicit P3a event-related potentials. Results indicate that the 2-back
condition was perceived as more demanding, evidenced by higher NASA-TLX scores
(overall score, mental and temporal demand, effort, frustration). The mean P3a
amplitude was diminished during the 2-back condition compared to the 0-back
condition, suggesting that drivers experienced higher MW and had fewer
resources available to process the novel environmental sounds. This study
provides empirical evidence indicating that the speed regulation n-back task
could be a valid, effective, and reproducible method to manipulate MW in
driving research.

mental workload, driving, speed regulation n-back task, auditory P3a,
neuroergonomics

††journalyear: 2023††doi: 10.1145/3581961.3609887††copyright:
rightsretained††conference: 15th International Conference on Automotive User
Interfaces and Interactive Vehicular Applications; September 18–22, 2023;
Ingolstadt, Germany††booktitle: 15th International Conference on Automotive
User Interfaces and Interactive Vehicular Applications (AutomotiveUI ’23
Adjunct), September 18–22, 2023, Ingolstadt, Germany††doi:
10.1145/3581961.3609887††isbn: 979-8-4007-0112-2/23/09

Figure 1. The experimental setup: A participant is conducting the modified
speed regulation n-back task in a driving simulator while his
electroencephalography (EEG) is being recorded.

##  1\. Introduction

There are various methods to manipulate mental workload (MW) in the field of
driving research. Traditionally, researchers would ask participants to perform
a non-driving related task (NDRT) while driving or monitoring an automated
vehicle to manipulate the level of experienced MW. This approach can be
described as a dual-task approach. Contrary, a single-task approach requires
drivers to be involved only in one task, typically driving. In order to
increase or decrease the demands of driving, researchers would manipulate
environmental factors, such as traffic complexity (Teh et al., 2014).

Implementing MW manipulation within a single-task approach presents
significant challenges. Researchers often modify the difficulty of the task
based on their best understanding (for instance, by increasing traffic in the
simulated scenario or reducing visibility) and presume the manipulation yields
the intended effect. However, these manipulations are not standardized, making
it problematic to evaluate or replicate the effects. Conversely, applying a
standardized secondary NDRT to manipulate MW addresses issues of
reproducibility and subjectivity in experimental designs. Yet, accurately
estimating the distribution of participants’ mental resources between primary
and secondary tasks can be problematic. Moreover, it potentially undermines
the realism of the driving experience (Hock et al., 2018).

Acquiring controlled, standardized MW manipulation within a single-task
driving paradigm remains challenging. This paper aims to provide further
empirical evidence for the impact of a single-task MW manipulation using a
modified speed regulation n-back driving task proposed by Unni et al. (Unni et
al., 2017). In the present study, participants encountered a 0-back and 2-back
condition within a driving simulator. We analysed self-reported MW (using
NASA-TLX (Hart and Staveland, 1988)) and objective MW (measured via P3a
amplitude induced by task-irrelevant environmental sounds (Polich, 2007;
Scheer et al., 2016)). To our best knowledge, this study is the first attempt
to assess the speed regulation n-back task employing P3a event-related
potential (ERP). Moreover, no self-reported assessment of perceived MW induced
by the n-back task has been previously published.

Understanding the effect of MW manipulation via the speed regulation n-back
task on the perceived cognitive load and P3a amplitude will provide valuable
insights into the cognitive mechanisms underlying this task. Providing
empirical evidence combining objective and subjective measures of MW will help
to establish the speed-regulation n-back task as an objective, replicable way
of MW manipulation in driving simulator studies.

###  1.1. Related Work

Mental workload (MW) refers to the amount of cognitive resources required to
perform a specific task (Embrey et al., 2006). It’s a measure of the mental
effort expended, taking into account factors such as task complexity,
information processing demands, and the cognitive capabilities of the
individual. MW is measurable through various techniques, including self-
reporting, performance-based assessments, and physiological measurements (De
Waard and Brookhuis, 1996). Using event-related potentials (ERPs) evoked by
novel environmental auditory cues has been proposed to be an objective
physiological measure of MW (Polich, 2007; Escera et al., 1998; Kramer et al.,
1995). The authors of these studies jointly report that higher MW correlates
with a lower amplitude of the P3a ERP component and vice versa. This effect is
based on the multiple resources theory (Wickens, 2008), which suggests that
the environmental stimuli compete for limited processing resources. When a
high mental workload is induced, fewer attentional resources are left for
processing the environmental sounds (Chun et al., 2011). Higher MW, therefore,
leads to decreased P3a amplitude. There is a discussion about whether other
factors, such as arousal or top-down attention control, might be a factor
influencing the P3a amplitude (Cahn and Polich, 2009; Figalová et al., 2023);
nevertheless, robust empirical evidence supports the inversed relationship
between MW and P3a amplitude due to the competition for resources.

Several authors studied the P3a amplitude in the driving research. Wester et
al. compared the P3a amplitudes between stationary and driving conditions.
Scheer et al. studied the effect of steering demands on P3a amplitude. Van der
Heiden et al. compared the P3a amplitude in a stationary condition to manual
and automated driving. Figalová et al. studied the effect of different levels
of automation on the P3a amplitude. However, none of these studies used a
standardised single-task method to manipulate MW.

An n-back task is a continuous performance task designed to measure a part of
working memory and working memory capacity. The load factor n can be adjusted
to make the task more or less difficult and, therefore, to manipulate MW. In
the modified speed regulation n-back driving task proposed by Unni et al.
(Unni et al., 2017), participants manually drive while presented with a series
of speed signs. The task requires participants to continuously update,
memorise, and recall previous speed signs while adjusting their current speed
to match the sign displayed n-steps before. This paradigm has been used in
other studies (Unni et al., 2017; Held et al., 2022; Scheunemann et al., 2019)
and appears to be an efficient way to manipulate MW using a single-task
approach.

###  1.2. Hypotheses

Participants experienced a low MW condition (0-back) and a high MW condition
(2-back). Based on the inversed relationship between MW and P3a amplitude
discussed in section 1.1, we formulated the following hypotheses:

  * •

H1: The overall score of NASA-TLX is lower during the 0-back than during the
2-back condition.

  * •

H2: The mean P3a amplitude is higher during the 0-back than during the 2-back
condition.

##  2\. Methods

###  2.1. Particpants

Our sample consisted of 23 participants (11 males and 12 females) with an
average age of 23.83 years (SD = 3.61). All participants had normal or
corrected-to-normal vision, no known neurological or psychiatric disease, and
a valid German driving license (on average for M = 3.77 years, SD = 3.48).
Participants provided informed consent and received 50 Euros as compensation
to participate.

###  2.2. Apparatus and Procedure

The experiment took place in a highly immersive, fixed-base driving simulator
with a realistic car mock-up (see Figure 1). The EEG was recorded using 32
active channels (ActiCAP by Brain Products) placed according to the
international 10-20 system. We kept the impedance below $25k\Omega$. We also
recorded electrodermal activity and electrocardiogram; however, the data are
not presented here. The perceived cognitive workload was assessed using the
NASA Task Load Index scale (NASA-TLX; (Hart and Staveland, 1988)). Each of the
six dimensions was evaluated on a 100-point Likert scale. The total score was
obtained as the average of the six dimensions.

First, participants learned how to operate the driving simulator and conduct
the speed regulation n-back task. Afterwards, we installed the EEG and started
the experiment. Participants filled in the NASA-TLX at the end of each
condition. The order of the conditions was counterbalanced between
participants.

###  2.3. Experimental task

Participants experienced speed regulation 0-back and 2-back conditions
designed to manipulate MW using a within-subject design. Participants drove on
a rural road, and a speed sign (from 60 to 100 km/h) was presented in a random
order every 20 seconds on a head-up-like screen in front of them (see Figure
1). The position and size of the sign corresponded to a normal German speed
sign. The sign was shown for 3 seconds. For the 0-back task, participants were
instructed to adjust and maintain the speed according to the currently
presented sign. For the 2-back task, participants had to adjust and maintain
the speed that occurred two signs before and remember the sequence of the two
following speed signs. Each condition lasted for approximately 17 minutes, and
52 signs were shown in each condition. The task is visualised in Figure 2.

Figure 2. Example of the speed regulation n-back task.

###  2.4. Stimuli and Questionnaires

Participants were exposed to a passive oddball task, which consisted of three
types of task-irrelevant auditory stimuli:

  1. (1)

Frequent distractors, 450 presentations in each condition (probability of
presentation: 71.43%);

  2. (2)

infrequent distractors, 90 presentations in each condition (probability of
presentation: 14.29%);

  3. (3)

novel environmental distractors, 90 presentations in each condition
(probability of presentation: 14.29%).

The frequent and infrequent distractors consisted of two tones (pure 700 Hz
and 300 Hz tones); their presentation probability was counterbalanced across
participants. The novel environmental distractors consisted of 30 complex
sounds (e.g., human laughter, helicopter) (Fabiani et al., 1996). Each
stimulus was presented for 336 ms. The inter-stimulus interval was randomized
and ranged from 1300 to 1700 ms.

###  2.5. EEG Pre-processing and Analysis

Data preprocessing followed the BeMoBil pipeline (Klug et al., 2022). The data
were submitted for adaptive mixture independent component analysis (AMICA). We
classified the components using IClabel (Pion-Tonachini et al., 2019) and
retained the components that most likely originated from brain activity. Next,
we filtered the data between 0.1 and 30 Hz and extracted epochs from -200 to
800 ms relative to the stimulus onset. Artifactual epochs were rejected. The
preprocessed data were averaged for each channel and experimental condition. A
difference wave was computed as the difference between the ERP elicited by the
environmental distractor and the ERP elicited by the frequent distractor.
Statistical analysis was conducted focusing on the Fz electrode using JASP
0.16.4, with the general level of significance set to 0.05.

##  3\. Results

###  3.1. Self-reported Mental Workload

Using a paired samples t-test, we found a difference in the total NASA-TLX
score between 0-back (M = 42.464, SD = 15.187) and 2-back (M = 58.478, SD =
14.466) experimental conditions; t(22) = 7.326, p <.001, d = 1.528. Comparing
the six dimensions of NASA-TLX, we found a difference in mental demand (M =
36.957, SD = 21.253 for 0-back; M = 77.826, SD = 19.588 for 2-back; t(22) =
9.700, p <.001, d = 2.023), temporal demand (M = 39.348, SD = 21.443 for
0-back; M = 53.478, SD = 25.603 for 2-back; t(22) = 3.472, p = .002, d =
0.724), effort (M = 45.652, SD = 24.416 for 0-back; M = 73.261, SD = 20.204
for 2-back; t(22) = 6.260, p <.001, d = 1.305), and frustration (M = 29.565,
SD = 31.315 for 0-back; M = 47.391, SD = 27.214 for 2-back; t(22) = 3.790, p
<.001, d = 0.790). The results are visualised in 3a.

The results suggest that the overall perceived mental workload was lower in
the 0-back task than in the 2-back task. Moreover, this finding is consistent
with the differences observed in the single factors of NASA-TLX. Therefore, we
accept H1.

###  3.2. Mean P3a amplitude

We used the collapsed localizer method to quantify ERP component amplitudes. A
grand average peak (GA) was determined at 328 ms post-stimulus. The mean
amplitude was calculated between 303 and 353 ms post-stimulus (GA peak +/- 25
ms). Figure 3b presents the difference waves (environmental-frequent). We
found a difference in the mean amplitude between 0-back (M = 1.429
$\mathrm{\SIUnitSymbolMicro V}$, SD = 1.272) and 2-back (M = 2.471
$\mathrm{\SIUnitSymbolMicro V}$, SD = 2.471) experimental conditions; t(22) =
1.937, p = .033, d = 0.404.

The results suggest that the P3a amplitude elicited by the novel environmental
sounds was decreased with increased mental workload. Therefore, we accept H2.

Figure 3. a) The mean score of the six dimensions of NASA-TLX. The error bars
represent a 95% confidence interval. Significant differences are highlighted
(*** p $\leq$ .001, ** p $\leq$ .01).
b) Difference wave (environmental novel distractor-frequent distractor) ERPs
for the 0-back and 2-back experimental conditions at the Fz electrode. Mean
amplitudes in the yellow-highlighted area (303 to 353 ms) were submitted for
statistical comparisons.

##  4\. Discussion

This study investigated the effect of MW manipulation using the modified speed
regulation n-back task proposed by Unni et al. (Unni et al., 2017). We
conducted a driving simulator experiment with 23 participants who experienced
0-back and 2-back conditions. We analysed the self-reported MW (using NASA-TLX
(Hart and Staveland, 1988)). Moreover, we studied the mean amplitude of P3a
ERP components evoked by task-irrelevant novel sounds, which served as a proxy
measure of objective MW (Kramer et al., 1995; Scheer et al., 2016).

The subjective assessment of MW using the overall NASA-TLX suggests that
drivers perceived the 2-back condition as more demanding than the 0-back
condition. The mental and temporal demands were higher for the 2-back
condition. Moreover, participants felt more effort was required to complete
the 2-back condition and were more frustrated by the 2-back condition compared
to the 0-back condition. These results were anticipated. However, none of the
previous studies employing the speed regulation n-back task (Unni et al.,
2017; Held et al., 2022; Scheunemann et al., 2019) reported scores of NASA-TLX
or other comparable measures.

Moreover, this study was the first attempt to use an objective measure of MW,
namely the mean P3a amplitude evoked by novel environmental sounds, to assess
the speed regulation n-back task. The P3a results suggest that the different
levels of the n-back task had a significant effect on the amount of resources
used to process the novel environmental sounds. Employing the multiple
resources theory (Wickens, 2008), we argue that the 2-back condition required
more processing resources; therefore, fewer resources were left to process the
novel environmental sound. This effect can be observed as a decreased mean P3a
amplitude in the 2-back condition compared to the 0-back condition. This
effect was anticipated based on the literature review.

The differences in subjective MW between the two conditions suggest a large
effect (d = 1.528) for the overall score of NASA-TLX. Hence, we argue that
there were substantial differences in demands between the two conditions and,
therefore, the changes in the P3a amplitude can be explained in the light of
the multiple resources theory (Wickens, 2008) and resource competition (Chun
et al., 2011). However, we suggest that in the case of low-demanding tasks,
researchers could potentially observe a floor effect. This could be due to the
low demands of the task, which does not fully occupy the processing resources.
As plenty of free resources are available to process the auditory cues, the
P3a amplitude might not be in a direct reversed relationship with the demands
of the primary task, and could therefore be non-sensitive to the demands of
the primary task.

We observed an inversed relationship between the task demands and the P3a
amplitude. This finding is in line with the majority of other studies (e.g.,
(Kramer et al., 1995; Polich, 2007; Escera et al., 1998). However, some
authors argue that other factors might be modulating the P3a amplitude as
well. The results of Cahn and Polich suggest that attentional withdrawal
during meditation leads to a decreased P3a amplitude evoked by novel auditory
stimuli. The results of Figalová et al. suggest a discrepancy between
perceived MW and mean P3a amplitude evoked by novel auditory stimuli during
automated driving in a realistic environment. These studies suggest that other
factors, namely top-down attention control, novelty, environment, or arousal,
might play an important role in modulating the P3a amplitude. These factors
should be addressed methodologically in future studies.

The empirical data support both H1 and H2 and provide further empirical
evidence for the reliability and validity of the speed regulation n-back task
to manipulate MW in driving research. Therefore, the speed-regulation n-back
task may be used to manipulate MW in a standardised way. Nevertheless, further
methodological recommendations must be derived in order to ensure the results
of different studies conducted in different environments utilising different
scenarios are directly comparable.

###  4.1. Limitations and Future Work

This study focused only on two levels of the n-back task (0-back and 2-back).
For a fine-grained evaluation of the task, we recommend measuring more levels
(e.g., 0, 1, 2, and 3 with each participant). Moreover, we recommend
validating the paradigm on a general adult sample, as our sample consisted
predominantly of young university students. Future studies should also address
the effect of other variables, such as arousal or top-down attention control,
on the auditory P3a amplitude.

###  4.2. Contribution and Novelty

This study evaluates the speed regulation n-back task, a novel approach to
manipulating MW in driving research. We used methods of estimating MW induced
by the speed regulation n-back task that have not been reported before in the
context of the task (NASA-TLX and mean P3a amplitude). We combined self-
reported and EEG-based estimates of mental workload that provide robust
evidence of the validity and reliability of the task. Moreover, our empirical
data help to comprehensively understand the cognitive mechanisms underlying
the task.

## Conclusion

The data suggest that drivers perceived the 2-back condition as more demanding
than the 0-back condition. We found differences in the mental and temporal
demand, effort, and frustration dimensions of NASA-TLX. Moreover, the P3a
amplitude was significantly decreased for the 2-back condition compared to the
0-back condition. The speed regulation n-back task appears to be a reliable,
valid, and reproducible method to manipulate MW in driving research.

###### Acknowledgements.

This project has received funding from the European Union’s Horizon 2020
research and innovation programme under the Marie Sklodowska-Curie grant
agreement 860410. The project was supported by the Deutsche
Forschungsgemeinschaft (DFG, German Research Foundation)-Project-ID
416228727-SFB 1410.

## References

  * (1)
  * Cahn and Polich (2009) B Rael Cahn and John Polich. 2009.  Meditation (Vipassana) and the P3a event-related brain potential.  _International journal of psychophysiology_ 72, 1 (2009), 51–60.
  * Chun et al. (2011) Marvin M Chun, Julie D Golomb, and Nicholas B Turk-Browne. 2011\.  A taxonomy of external and internal attention.  _Annual review of psychology_ 62 (2011), 73–101.
  * De Waard and Brookhuis (1996) Dick De Waard and KA Brookhuis. 1996.  The measurement of drivers’ mental workload.  (1996).
  * Embrey et al. (2006) David Embrey, Claire Blackett, Philip Marsden, and Jim Peachey. 2006.  Development of a human cognitive workload assessment tool.  _MCA Final Report, Lancashire_ (2006), 1–253.
  * Escera et al. (1998) Carles Escera, Kimmo Alho, István Winkler, and Risto Näätänen. 1998.  Neural mechanisms of involuntary attention to acoustic novelty and change.  _Journal of cognitive neuroscience_ 10, 5 (1998), 590–604.
  * Fabiani et al. (1996) Monica Fabiani, Victoria A Kazmerski, Yael M Cycowicz, and David Friedman. 1996.  Naming norms for brief environmental sounds: Effects of age and dementia.  _Psychophysiology_ 33, 4 (1996), 462–475.
  * Figalová et al. (2023) Nikol Figalová, Hans-Joachim Bieg, Julian Elias Reiser, Yuan-Cheng Liu, Martin Baumann, Lewis Chuang, and Olga Pollatos. 2023\.  From Driver to Supervisor: Comparing Cognitive Load and EEG-based Attention Allocation across Automation Levels.  _arXiv preprint arXiv:2306.08477_ (2023).
  * Hart and Staveland (1988) Sandra G Hart and Lowell E Staveland. 1988.  Development of NASA-TLX (Task Load Index): Results of empirical and theoretical research.  In _Advances in psychology_. Vol. 52. Elsevier, 139–183.
  * Held et al. (2022) Moritz Held, Jochem W Rieger, and Jelmer P Borst. 2022\.  Multitasking while driving: central bottleneck or problem state interference?  _Human factors_ (2022), 00187208221143857\.
  * Hock et al. (2018) Philipp Hock, Johannes Kraus, Franziska Babel, Marcel Walch, Enrico Rukzio, and Martin Baumann. 2018\.  How to design valid simulator studies for investigating user experience in automated driving: review and hands-on considerations. In _Proceedings of the 10th International Conference on Automotive User Interfaces and Interactive Vehicular Applications_. 105–117.
  * Klug et al. (2022) Marius Klug, Sein Jeung, Anna Wunderlich, Lukas Gehrke, Janna Protzak, Zakaria Djebbara, Andreas Argubi-Wollesen, Bettina Wollesen, and Klaus Gramann. 2022\.  The BeMoBIL Pipeline for automated analyses of multimodal mobile brain and body imaging data.  _bioRxiv_ (2022).
  * Kramer et al. (1995) Arthur F Kramer, Leonard J Trejo, and Darryl Humphrey. 1995\.  Assessment of mental workload with task-irrelevant auditory probes.  _Biological psychology_ 40, 1-2 (1995), 83–100.
  * Pion-Tonachini et al. (2019) Luca Pion-Tonachini, Ken Kreutz-Delgado, and Scott Makeig. 2019\.  ICLabel: An automated electroencephalographic independent component classifier, dataset, and website.  _NeuroImage_ 198 (2019), 181–197.
  * Polich (2007) John Polich. 2007\.  Updating P300: an integrative theory of P3a and P3b.  _Clinical neurophysiology_ 118, 10 (2007), 2128–2148.
  * Scheer et al. (2016) Menja Scheer, Heinrich H Bülthoff, and Lewis L Chuang. 2016\.  Steering demands diminish the early-P3, late-P3 and RON components of the event-related potential of task-irrelevant environmental sounds.  _Frontiers in human neuroscience_ 10 (2016), 73.
  * Scheunemann et al. (2019) Jakob Scheunemann, Anirudh Unni, Klas Ihme, Meike Jipp, and Jochem W Rieger. 2019.  Demonstrating brain-level interactions between visuospatial attentional demands and working memory load while driving using functional near-infrared spectroscopy.  _Frontiers in human neuroscience_ (2019), 542.
  * Teh et al. (2014) Evona Teh, Samantha Jamson, Oliver Carsten, and Hamish Jamson. 2014.  Temporal fluctuations in driving demand: The effect of traffic complexity on subjective measures of workload and driving performance.  _Transportation research part F: traffic psychology and behaviour_ 22 (2014), 207–217.
  * Unni et al. (2017) Anirudh Unni, Klas Ihme, Meike Jipp, and Jochem W Rieger. 2017\.  Assessing the driver’s current level of working memory load with high density functional near-infrared spectroscopy: A realistic driving simulator study.  _Frontiers in human neuroscience_ 11 (2017), 167.
  * Van der Heiden et al. (2018) Remo MA Van der Heiden, Christian P Janssen, Stella F Donker, Lotte ES Hardeman, Keri Mans, and J Leon Kenemans. 2018.  Susceptibility to audio signals during autonomous driving.  _PloS one_ 13, 8 (2018), e0201963.
  * Wester et al. (2008) Anne E Wester, Koen BE Böcker, Edmund R Volkerts, Joris C Verster, and J Leon Kenemans. 2008\.  Event-related potentials and secondary task performance during simulated driving.  _Accident Analysis & Prevention_ 40, 1 (2008), 1–7.
  * Wickens (2008) Christopher D Wickens. 2008\.  Multiple resources and mental workload.  _Human factors_ 50, 3 (2008), 449–455.


* [Ban19] Nikhil Bansal.  On a generalization of iterated and randomized rounding.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC, pages 1125–1135, 2019.
  * [BDHN19] Sébastien Bubeck, Nikhil R. Devanur, Zhiyi Huang, and Rad Niazadeh.  Multi-scale online learning: Theory and applications to online auctions and pricing.  J. Mach. Learn. Res., 20:62:1–62:37, 2019.
  * [BGSZ20] Domagoj Bradac, Anupam Gupta, Sahil Singla, and Goran Zuzic.  Robust algorithms for the secretary problem.  In 11th Innovations in Theoretical Computer Science Conference, ITCS, pages 32:1–32:26, 2020.
  * [BIKK18] Moshe Babaioff, Nicole Immorlica, David Kempe, and Robert Kleinberg.  Matroid secretary problems.  J. ACM, 65(6):35:1–35:26, 2018.
  * [Dyn63] Eugene B Dynkin.  The optimum choice of the instant for stopping a markov process.  In Soviet Math. Dokl, volume 4, 1963.
  * [EKM18] Hossein Esfandiari, Nitish Korula, and Vahab Mirrokni.  Allocation with traffic spikes: Mixing adversarial and stochastic models.  ACM Trans. Econ. Comput., 6(3-4), 2018.
  * [FKS21] Michal Feldman, Thomas Kesselheim, and Sahil Singla.  Tutorial on “Prophet Inequalities and Implications to Pricing Mechanisms and Online Algorithms”.  http://www.thomas-kesselheim.de/tutorial-prophet-inequalities, EC, 2021.
  * [FSZ15] Moran Feldman, Ola Svensson, and Rico Zenklusen.  A simple _O_(log log(rank))-competitive algorithm for the matroid secretary problem.  In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, pages 1189–1201, 2015.
  * [GKRS20] Paritosh Garg, Sagar Kale, Lars Rohwedder, and Ola Svensson.  Robust algorithms under adversarial injections.  In 47th International Colloquium on Automata, Languages, and Programming, ICALP, pages 56:1–56:15, 2020.
  * [GKT19] Anupam Gupta, Tomer Koren, and Kunal Talwar.  Better algorithms for stochastic bandits with adversarial corruptions.  In Proceedings of the Thirty-Second Conference on Learning Theory, COLT, pages 1562–1578, 2019.
  * [GM16] Anupam Gupta and Marco Molinaro.  How the experts algorithm can help solve lps online.  Math. Oper. Res., 41(4):1404–1431, 2016.
  * [GS20] Anupam Gupta and Sahil Singla.  Random-order models.  Beyond the Worst-Case Analysis of Algorithms, page 234, 2020.
  * [ISW20] Nicole Immorlica, Sahil Singla, and Bo Waggoner.  Prophet inequalities with linear correlations and augmentations.  In 21st ACM Conference on Economics and Computation, EC, pages 159–185, 2020.
  * [KKN15] Thomas Kesselheim, Robert D. Kleinberg, and Rad Niazadeh.  Secretary problems with non-uniform arrival order.  In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC, pages 879–888, 2015.
  * [Kle05] Robert D. Kleinberg.  A multiple-choice secretary algorithm with applications to online auctions.  In Proceedings of ACM-SIAM Symposium on Discrete Algorithms, SODA, 2005.
  * [KM20] Thomas Kesselheim and Marco Molinaro.  Knapsack secretary with bursty adversary.  In 47th International Colloquium on Automata, Languages, and Programming, ICALP, pages 72:1–72:15, 2020.
  * [KMZ15] Nitish Korula, Vahab Mirrokni, and Morteza Zadimoghaddam.  Online submodular welfare maximization: Greedy beats 1/2 in random order.  In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, pages 889–898. ACM, 2015.
  * [KRTV14] Thomas Kesselheim, Klaus Radke, Andreas Tönnis, and Berthold Vöcking.  Primal beats dual on online packing LPs in the random-order model.  In Proceedings of Symposium on Theory of Computing, STOC, pages 303–312, 2014.
  * [KS77] Ulrich Krengel and Louis Sucheston.  Semiamarts and finite values.  Bull. Am. Math. Soc, 1977.
  * [KW12] Robert Kleinberg and S. Matthew Weinberg.  Matroid prophet inequalities.  In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, pages 123–136, 2012.
  * [Lac14] Oded Lachish.  O(log log rank) competitive ratio for the matroid secretary problem.  In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 326–335, 2014.
  * [LMPL18] Thodoris Lykouris, Vahab S. Mirrokni, and Renato Paes Leme.  Stochastic bandits robust to adversarial corruptions.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC, pages 114–122, 2018.
  * [Luc17] Brendan Lucier.  An economic view of prophet inequalities.  SIGecom Exch., 16(1):24–47, 2017.
  * [Mey01] Adam Meyerson.  Online facility location.  In Foundations of Computer Science, 2001. Proceedings. 42nd IEEE Symposium on, pages 426–431. IEEE, 2001.
  * [MGZ12] Vahab S Mirrokni, Shayan Oveis Gharan, and Morteza Zadimoghaddam.  Simultaneous approximations for adversarial and stochastic online budgeted allocation.  In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pages 1690–1701, 2012.
  * [Mol17] Marco Molinaro.  Online and random-order load balancing simultaneously.  In Proceedings of ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1638–1650, 2017.
  * [Mol21] Marco Molinaro.  Robust algorithms for online convex problems via primal-dual.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 2078–2092, 2021.
  * [RS17] Aviad Rubinstein and Sahil Singla.  Combinatorial prophet inequalities.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017.
  * [Rub16] Aviad Rubinstein.  Beyond matroids: secretary problem and prophet inequality with general constraints.  In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC, pages 324–332, 2016.
  * [RWW20] Aviad Rubinstein, Jack Z. Wang, and S. Matthew Weinberg.  Optimal single-choice prophet inequalities from samples.  In Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference, ITCS, pages 60:1–60:10, 2020.
  * [SC84] Ester Samuel-Cahn.  Comparison of threshold stop rules and maximum for independent nonnegative random variables.  the Annals of Probability, pages 1213–1216, 1984.
  * [Ver18] Roman Vershynin.  High-dimensional probability, volume 47 of Cambridge Series in Statistical and Probabilistic Mathematics.  Cambridge University Press, Cambridge, 2018.