We show how to compute the elements of a sequence $x_t = a_t x_{t-1} + b_t$
in parallel, given $t = (1, 2, \dots, n)$, $a_t \in \mathbb{R}^n$, $b_t \in
\mathbb{R}^n$, and initial value $x_0 \in \mathbb{R}$. On $n$ parallel
processors, the computation of $n$ elements incurs $\mathcal{O}(\log n)$ time
and $\mathcal{O}(n)$ space. Sequences of this form are ubiquitous in science
and engineering, making their parallelization useful for a vast number of
applications. We implement parallelization in software, test it on parallel
hardware, and verify that it executes faster than sequential computation by a
factor of $\frac{n}{\log n}$.

计算序列中的元素在并行计算中的应用

普适串行计算的并行化

Parallelization of an Ubiquitous Sequential Computation

A practical issue of edge AI systems is that data distributions of trained
dataset and deployed environment may differ due to noise and environmental
changes over time. Such a phenomenon is known as a concept drift, and this gap
degrades the performance of edge AI systems and may introduce system failures.
To address this gap, retraining of neural network models triggered by concept
drift detection is a practical approach. However, since available compute
resources are strictly limited in edge devices, in this paper we propose a
fully sequential concept drift detection method in cooperation with an
on-device sequential learning technique of neural networks. In this case, both
the neural network retraining and the proposed concept drift detection are done
only by sequential computation to reduce computation cost and memory
utilization. Evaluation results of the proposed approach shows that while the
accuracy is decreased by 3.8%-4.3% compared to existing batch-based detection
methods, it decreases the memory size by 88.9%-96.4% and the execution time by
1.3%-83.8%. As a result, the combination of the neural network retraining and
the proposed concept drift detection method is demonstrated on Raspberry Pi
Pico that has 264kB memory.

本文提出一种边缘 AI 系统中的概念漂移检测方法，通过序列计算实现神经网络的重新训练和检测概念漂移，降低计算和内存使用，实现在 Raspberry Pi Pico 等资源受限的设备上的应用。