Parallel Scan on Ascend AI Accelerators

Bartłomiej Wróblewski, Gioele Gottardo, Anastasios Zouzias · 2025

Read Parallel Scan on Ascend AI Accelerators by Bartłomiej Wróblewski, Gioele Gottardo, Anastasios Zouzias (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-15112.txt.

Introduction

Prefix sums, the running totals of a list, hide inside sorting, sampling, and masking all over machine learning, and they must run fast on AI chips. Bartłomiej Wróblewski, Gioele Gottardo, and Anastasios Zouzias build scan algorithms in 2025 for Ascend accelerators that lean on the chips' matrix units, not just their vector units.

Feeding scans through the matrix engines gave five to nearly ten times the speed of vector-only code on long inputs in single-core tests. A multi-core version reached about three quarters of raw memory-copy bandwidth. Their radix sort, also matrix-driven, tripled its baseline. The paper is a case study in bending classic algorithms to fit new hardware shapes.

Catalog record

CREATORBartłomiej Wróblewski, Gioele Gottardo, Anastasios Zouzias
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE54 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-15112

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Parallel Scan on Ascend AI Accelerators Bartłomiej Wróblewski, Gioele Gottardo, Anastasios Zouzias Abstract We design and implement parallel prefix sum (scan) algorithms using Ascend AI accelerators. Ascend accelerators feature specialized computing units—the cube units for efficient matrix multiplication and the vector units for optimized vector operations. A key feature of the proposed scan algorithms is their extensive use of matrix multiplications and accumulations enabled by the cube unit. To showcase the effectiveness of these algorithms, we also implement and evaluate several scan-based operators commonly used in AI workloads, including sorting, tensor masking, and top- k k / top- p p sampling. Our single-core results demonstrate substantial performance improvements, with speedups ranging from 5 × 5\times to 9.6 × 9.6\times compared to vector-only implementations for sufficiently large input lengths. Additionally, we present a multi-core scan algorithm that fully utilizes both the cube and vector units of Ascend, reaching up to 74.9% of the memory bandwidth achieved by memory copy. Furthermore, our radix sort implementation, which utilizes matrix multiplications for its parallel splits, showcases the potential of matrix engines to enhance complex operations, offering up to 3.3 × 3.3\times speedup over the vector-only baseline. 1 Introduction Parallel scan is a fundamental parallel computing paradigm with many applications [ 7 , 30 ] . Due to its importance, parallel scan has been studied in several models of computation, including the circuit (work and depth) and the Parallel Random-Access Machine (PRAM) model [ 9 ] . In the circuit model, the depth and size trade-offs for parallel optimal prefix circuits are well-understood for binary operations [ 46 , 52 ] , but other models are yet to be explored, especially in the heterogeneous computing domain [ 13 , 53 ] . Despite many attempts, there is a large gap between abstract parallel machine models and the current state-of-the-art accelerators that contain heterogeneous computing units, see [ 37 ] and [ 2 , 45 , 27 ] . For example, hardware vendors have manufactured accelerators with specialized compute engines known as matrix engines or tensor core units . A list of such specialized hardware units includes Google’s TPUs [ 24 , 25 ] , Nvidia’s Tensor Cores [ 41 ] , AMD’s Matrix Cores [ 1 ] and Huawei’s Ascend Cube Unit [ 34 , 35 ] to name a few. Moreover, in the CPU domain, examples of such units (or extensions) are ARM’s Scalable Matrix Extension (SME) [ 3 ] , Intel’s Advanced Matrix Extensions (AMX) [ 22 ] and IBM’s POWER10 Matrix-Multiply Assist (MMA) [ 48 ] . Therefore, today’s high-performance processors contain matrix engines that allow efficient multiplication of constant-sized matrices, making ideas from the early 1980s [ 29 , 47 ] a reality and initiating fruitful debates within the community [ 14 ] . Given the presence of matrix engines in computing systems, a model of computation was recently proposed to capture matrix multiplication accelerators called the Tensor Core Unit (TCU) model [ 11 , 12 ] . The authors of [ 12 ] initiated the study of TCU algorithms and revisited classical paradigms in the TCU model. The study of accelerating prefix sum (and reduction) operations using matrix multiplication units was first initiated in the seminal paper of [ 13 ] . A follow-up work presented a logarithmic-depth parallel scan algorithm in the TCU model of computation, where only matrix multiplication operations are required [ 53 ] . Although the main algorithm in [ 53 ] offers stronger theoretical guarantees than that of [ 13 ] , its poor memory access patterns limit its practical performance. Here, we focus on simpler algorithms inspired by [ 13 ] that achieve performance close to hardware peak. Our top-performing multi-core scan kernels combine ideas from [ 13 , Alg. 6] , explicit software-managed asynchronous pipelining between matrix and vector cores, and a novel matrix-vector recomputation strategy in the up-sweep scan phase. Furthermore, we demonstrate that our proposed scan kernels can be easily composed to deliver the best-performing kernels for AI workloads on Ascend. In short, we draw inspiration from both these works [ 12 , 13 ] to advance the study of parallel scans on matrix multiplication accelerators. As a case study and an evaluation environment, we use Huawei’s Ascend AI accelerators and the Compute Architecture for Neural Networks (CANN) software ecosystem of Ascend to evaluate our proposals [ 33 ] . Our main contributions are listed below: • We design, implement, and evaluate parallel scan algorithms specialized for the Ascend AI accelerator. The distinguishing feature of the proposed algorithms is the extensive use of the Ascend matrix multiplication engines (“Cube cores”). In particular, we implement several scan variants, including single-core and multi-core scans, scans on multiple arrays (batched scan), inclusive/exclusive scans and specialized scan implementations for boolean (mask) inputs using the cube unit’s 8-bit integer capabilities. • We evaluated the proposed scan algorithms that use a single cube and vector units, demonstrating a 5\times up to 9.6\times speed-up compared to the baseline scan (vector unit only). • We present multi-core scan algorithms that fully utilize both the cube and vector units of the Ascend 910B4 accelerator, reaching up to 74.9% of the theoretical memory bandwidth of memory copy. Moreover, the MCScan algorithm ( Algorithm 3 ) attains a 15.2\times speedup over the corresponding single-cube variant when utilizing all 20 available AI cores. • We implement a list of computational kernels (operators), including parallel split, compress/compact and top- p (nucleus) sampling essential to AI workloads. In all of these cases, we demonstrate significant performance improvements. • Lastly, we implement radix sort, whose parallel splits take advantage of the cube units. The radix sort implementation provides up to 3.3\times speed-up over baseline sorting that does not utilize the cube units. Next, we briefly emphasize the key distinction between the above contributions and prior art. First, the multi-core scan algorithm is novel (to the best of our knowledge) since it performs partial recomputation of the reduction values on both the cube and vector units in its first phase. This recomputation strategy is different compared to all previously known scan strategies on accelerators, see Section 2.1 . Such a recomputation strategy could be of interest to other matrix multiplication accelerators as well. Second, our radix sort implementation yields an intriguing result: in practice, multiple small dense matrix multiplications can be leveraged to improve the end-to-end performance of parallel sorting. Although the algorithmic ideas and techniques underlying this result are well-established [ 10 ] , we believe that it paves the way for interesting research directions in the future. As an example, we pose the following question, see also the presentation of [ 11 ] . Is it possible to also utilize the multiple-add capabilities of the matrix multiplications units to improve further the performance of parallel sorting? It is important to note that, despite relying on the matrix multiplications for scan operations during parallel splits, our radix sort does not exploit the multiply-add capability of the matrix unit. 2 Background In this section, we give an overview of related work in computing parallel scans using accelerators, focusing mostly on matrix multiplication accelerators. We also present the Tensor Core Unit (TCU) model of computation, and we give

Read the complete text