# A Parallel Scan Algorithm in the Tensor Core Unit Model

arXiv: https://arxiv.org/abs/2411.17887 · HTML: https://mlsanity.com/paper/2411.17887/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Nov 2024.

## Built on by (most cited first, 2 of 2)

- [An Adaptive Orthogonal Convolution Scheme for Efficient and Flexible CNN Architectures](https://mlsanity.com/paper/2501.07930/) (2025)
- [Fast and Stable Triangular Inversion for Delta-Rule Linear Transformers](https://mlsanity.com/paper/2605.21325/) (2026)

## Abstract (arXiv)

We present a parallel scan (prefix sum) algorithm in the Tensor Core Unit (TCU) model of computation. The TCU model assumes that multiplication between two square matrices of constant size s is a basic operation. In the (s2, ℓ)-TCU model, we show that for inputs of size n, the algorithm has depth at most 2lfloor logs (n)rfloor and runs in O(n(1 + ℓ /s2)/p + (s2 + ℓ) logs (n)) time assuming p tensor core units. Equivalently, the algorithm performs O(n/s2) multiplications of square matrices of size s.