Pith. sign in

REVIEW 2 major objections 5 minor 23 references

A Parallel Scan Algorithm in the Tensor Core Unit Model

T0 review · 2 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Prefix sums—the running totals of a vector—can be computed in logarithmic depth on tensor core units, using only multiplications by two fixed matrices, this paper argues.

desk verdict The power-of-s scan analysis is solid and worth knowing; the arbitrary-n depth bound is overclaimed and should be corrected. read the letter →

arxiv 2411.17887 v1 pith:2757IYDL submitted 2024-11-26 cs.DC cs.DS

Anastasios Zouzias , William F. McColl This is my paper · ORCID
classification cs.DCcs.DS
keywords PrefixSumScanMatrixMultiplicationTensorCoreUnitModelParallelAlgorithmsWork-DepthAnalysisRadixSort
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper claims that prefix sums—the running totals of a vector—can be computed in logarithmic depth on hardware whose basic operation is multiplication of small square matrices, the Tensor Core Unit (TCU) model. The proposed MatMulScan algorithm performs the scan entirely through multiplications by two fixed constant matrices, one that computes local prefix sums and one that adds a broadcast scalar to a vector. For any input of size $n$, the paper argues the depth is at most $2\lfloor\log_s(n)\rfloor$, the number of $s\times s$ matrix multiplications is $O(n/s^2)$, and with $p$ tensor cores the runtime is $O(n(1+\ell/s^2)/p + (s^2+\ell)\log_s(n))$. The claimed bounds make prefix sums logarithmic-depth in the TCU model and, via the standard reduction, put radix sort on tensor core units.

What carries the argument

The load-bearing objects are two constant $s\times s$ matrices: $\mathbf{L}_s$, the lower-triangular all-ones matrix, whose product with a vector is its local prefix sum, and $\mathbf{B}_s$, the identity matrix with its first column set to all ones, whose product with a vector $[\alpha;\mathbf{q}]$ returns $\mathbf{q}+\alpha\mathbf{1}$. The batch procedure reshapes each strided subvector into an $s\times s$ column-major matrix (zero-padding as needed), multiplies all such matrices by the same constant matrix in a single batched tensor-core call, and flattens the result. The up-sweep uses $\mathbf{L}_s$ to form prefix sums on exponentially increasing strides; the down-sweep uses $\mathbf{B}_s$ to add each chunk's correct preceding total. For arbitrary input lengths, the base-$s$ decomposition into chunks of sizes $s^{k_i}$, together with the scan of the vector of chunk maxima, is what keeps the depth logarithmic.

What would settle it

Take an input length $n$ that is not a power of $s$ and count the matrix-multiplication rounds of the full procedure: if the chunk-maxima scan cannot be scheduled inside the largest chunk's down-sweep window—for instance at $s=2$, $n=31$—then the measured depth exceeds $2\lfloor\log_s(n)\rfloor$, and the advertised exact bound fails for that $n$.

Watch

Extended reading notes

Core claim

MatMulScan computes the inclusive prefix sum of an $n$-vector by alternating an up-sweep and a down-sweep. In the up-sweep, entries gathered with stride $s^t$ are multiplied by the lower-triangular all-ones matrix $\mathbf{L}_s$, giving local prefix sums on chunks of size $s$; in the down-sweep, the matrix $\mathbf{B}_s$ (the identity with first column all ones) broadcasts and adds the correct preceding total to each local block. For $n=s^k$ the depth is $2\log_s(n)-1$ and the number of scalar additions is $\lceil n(1+s/2)\rceil + O(s^3\log_s n)$. For arbitrary $n$, the paper writes $n$ in base $s$, runs the power-of-$s$ routine on each chunk, scans the vector of chunk maxima with the same algorithm, and adds the maxima back into the chunks, yielding depth at most $2\lfloor\log_s(n)\rfloor$ and $O(n/s^2)$ matrix multiplications overall. The paper gives a recursive correctness proof in the appendix and presents the result as resolving positively the question 'can TCU sort?', since radix sort reduces to prefix sums.

Load-bearing premise

The exact $2\lfloor\log_s(n)\rfloor$ depth bound for arbitrary $n$ depends on the assertion that the scan of the vector of per-chunk maximum values can be fully overlapped with the down-sweep of the largest chunks, an overlap the paper states for 'large enough $n$' without giving a size condition or schedule.

Editorial extensions

If this is right

  • With $p$ tensor core units, prefix sums of $n$ elements run in $O(n(1+\ell/s^2)/p + (s^2+\ell)\log_s(n))$ time, making the trade-off between matrix size $s$, latency $\ell$, and parallelism $p$ explicit.
  • Radix sort is implementable on tensor core units through the standard reduction of sorting to prefix sums, settling the 'can TCU sort?' question in the affirmative.
  • For $s=4$, the TCU depth is $\log_2(n)-1$, halving the depth of the $s=2$ case at the price of roughly $3n$ scalar additions rather than $2n$.
  • The total number of $s\times s$ matrix multiplications is $O(n/s^2)$, so for fixed $s$ the matrix-multiplication cost is linear in $n$ with a small constant.
  • Since the paper states the results extend from addition to any associative operator, the same depth and work picture applies to prefix computations under other associative operations.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The paper leaves implicit a schedule for the overlap claimed in Section 2.2; until one is given, the exact $2\lfloor\log_s(n)\rfloor$ bound for arbitrary $n$ rests on that scheduling assumption rather than on the code as written.
  • Because the down-sweep uses $\mathbf{B}_s$ mainly for a scalar-vector addition, an implementation could route that phase through a nearby vector unit, as the paper itself suggests, to avoid the very low tensor-core utilization of that phase.
  • The construction is self-similar, so one could recursively apply MatMulScan to the chunk-maximum vector instead of padding it to a power of $s$; a careful overlap analysis might then give an exact logarithmic depth for all $n$.
  • If tensor cores ever support matrix products over semirings other than ordinary arithmetic, the same $\mathbf{L}_s$ and $\mathbf{B}_s$ products would deliver prefix scans for min-plus or boolean associative operators.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper proposes MatMulScan, a parallel prefix-sum (scan) algorithm for the (s^2, ℓ)-TCU model, in which multiplication of two constant-size s×s matrices is the basic operation. For inputs of size n = s^k, the paper proves a depth of 2k−1, O(n/s^2) matrix multiplications, and O(n + ℓk) time. It then extends the algorithm to arbitrary n by decomposing n in base s, running Algorithm 1 independently on the resulting segments, scanning the vector w of segment maxima, and broadcasting the scanned values to later segments. The central claims, stated in the Abstract and Corollary 1, are that for every n the algorithm has depth at most 2⌊log_s n⌋, performs O(n/s^2) matrix multiplications, and runs in O(n(1 + ℓ/s^2)/p + (s^2 + ℓ) log_s n) time with p tensor core units.

Significance. If the central claim held, the paper would establish that prefix sums have logarithmic depth in the TCU model, generalize the Brent-Kung scan to a matrix-based setting, and support the claim that TCUs can be used for sorting. The power-of-s part of the analysis is clean and, as far as I can verify, correct: Lemma 1 and Theorem 1 are supported by a straightforward induction and by counting batched matrix multiplications. The paper also provides an end-to-end Python reference implementation and a recursive correctness proof, which are concrete strengths. The arbitrary-length extension in Section 2.2, however, has load-bearing gaps: the size bound on w is inaccurate and the overlap argument that produces the exact depth bound is not proved. The result remains plausible in an asymptotic form, but the advertised exact depth bound for all n is not supported by the described algorithm.

major comments (2)
  1. [Section 2.2, Step 2/3] The bound |w| ≤ k1(s−1) is incorrect. For n = s^{k1+1}−1 the base-s expansion has k1+1 nonzero digits, each contributing up to s−1 segments. For example, for s = 3 and n = 26 (k1 = 2), the segments are 9, 9, 3, 3, 1, 1, and five offset values (totals of the first five segments) are needed, so |w| = 5, whereas k1(s−1) = 4. This invalidates the choice of q in Step 3 and consequently the depth calculation based on that q.
  2. [Section 2.2, Depth analysis] The claim that Steps 2 and 3 'can be overlapped with the 2nd phase of the execution of the first step for large enough n' is asserted without a schedule or a quantitative condition. The overlap fails for concrete inputs: for s = 3, n = 26, the largest segments have k1 = 2, so their down-sweep is only one round, while the scan of w (with q = 2, i.e., length 9) needs three rounds. Even with optimistic pipelining, the last broadcast cannot be completed within 2⌊log_3 26⌋ = 4 rounds. Thus Corollary 1's unqualified exact depth bound is not established for arbitrary n. The authors should either provide a precise schedule and a condition on k1 under which the overlap is complete, or weaken the depth claim to 2⌊log_s n⌋ + O(log_s log_s n).
minor comments (5)
  1. [Section 2.2, Step 3] The padding rule should be stated in terms of the actual number of entries in w, not the erroneous bound k1(s−1); after fixing the bound, the text should define q by |w| ≤ s^q.
  2. [Section 2.2, decomposition notation] The sums over i ≥ 1 use µ_i and k_i without a precise indexing convention for the base-s expansion; please define the digit indices explicitly so the reader can follow the bound on the number of segments.
  3. [Section 1, second page] The claim that the paper 'resolve[s] in the affirmative the open question “can TCU sort?”' is not backed by an explicit sorting theorem or a detailed reduction; consider softening this to a consequence of the scan result or providing a formal corollary.
  4. [Figure 3 and Section 2.2] The execution diagram would be much more convincing if it included a concrete round-by-round schedule for the overlap of the w-scan with the largest segments' down-sweep, together with the quantitative condition on k1.
  5. [References] Reference [1] contains a typo: 'Sythesis' should be 'Synthesis'.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: MatMulScan's bounds are derived directly from counting matrix multiplications in the TCU model; the arbitrary-n depth caveat is an unproven scheduling claim, not a circular step.

full rationale

The paper's central contribution is an algorithm design, not an empirical prediction. The depth, work, matrix-multiplication count, and TCU runtime bounds (Lemma 1, Theorem 1, Corollary 1) are obtained by counting loop iterations and matrix multiplications within the explicitly defined Algorithm 1. The correctness proof in Appendix A.1 is an induction on the recursive formulation; it does not assume the target result. No parameter is fitted to data, and no load-bearing result is imported from the authors' own prior work: the TCU model is attributed to Chowdhury et al. ([6,7]) and the scan work to Dakkak et al. ([8]), none of whom overlap with the present authors, and those citations supply model definitions/context rather than the paper's bounds. The phrase 'equivalently, the algorithm performs O(n/s^2) multiplications' restates the count derived in Section 2.1, so it is a derived simplification, not an input. The only notable weakness is the Section 2.2 assertion that the scan of the segment-maximum vector w 'can be overlapped with the 2nd phase of the execution of the first step for large enough n'; no schedule or quantitative condition is given, and the depth bound 2 floor(log_s n) for arbitrary n may fail for small n. That is an unproven scheduling assumption and a potential correctness/overclaim issue, but it is not circularity, because the claimed bound is not assumed in the derivation of the overlap; the overlap is asserted independently. Thus the paper is self-contained against external benchmarks and contains no significant circular step.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper adds no empirical parameters and no new entities. Its contribution is conditional on the TCU model abstraction and on two analysis simplifications: free gather/scatter/reshaping and an unproven overlap of the arbitrary-n steps. The first simplification is explicitly flagged; the second is not.

assumptions (4)
  • domain assumption The TCU model: multiplication of an s x s matrix by an s x m matrix (m >= s) takes O(ms + l) time, with s and l fixed model parameters.
    Invoked throughout Sections 1 and 2.1; the paper's results are stated in this model from [6,7].
  • ad hoc to paper Gather/scatter memory operations and vector/tensor reshaping operations have zero cost.
    Stated before Lemma 1: 'we ignore the cost of the gather-scatter memory operations and the cost of vector/tensor reshaping operations'. The runtime bounds depend on this assumption.
  • ad hoc to paper The scan of the segment-maximum vector w can be fully overlapped with the second phase of the largest segments for large enough n.
    Section 2.2, one-sentence assertion without proof; the exact depth 2*floor(log_s n) in Corollary 1 depends on it.
  • standard math Standard arithmetic and induction are valid in the correctness proof.
    The correctness proof in Appendix A.1 uses strong induction over the recursive formulation of the algorithm.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A Parallel Scan Algorithm in the Tensor Core Unit Model." pith.science (2026). https://pith.science/paper/2757IYDL

@misc{pith2026241117887,
  author       = {Pith},
  title        = {Pith review of: A Parallel Scan Algorithm in the Tensor Core Unit Model},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2757IYDL}},
  note         = {Machine review of arXiv:2411.17887}
}
abstract

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 $(s^2, \ell)$-TCU model, we show that for inputs of size $n$, the algorithm has depth at most $2\lfloor \log_s (n)\rfloor$ and runs in $O(n(1 + \ell /s^2)/p + (s^2 + \ell) \log_s (n))$ time assuming $p$ tensor core units. Equivalently, the algorithm performs $O(n/s^2)$ multiplications of square matrices of size s.

Figures

Figures reproduced from arXiv: 2411.17887 by the authors.

Figure 1
Figure 1. Examples of Algorithm 1 for input x = [1, 2, . . . , 16]. 2 MatMulScan: Parallel Scan in the TCU Model In this section, we present a parallel scan algorithm (Algorithm 1) designed to take advantage of the computational speedup offered by the matrix multipli￾cation circuit of the TCU model. All numerical operations of Algorithm 1 are multiplications between two square matrices of size s. Surprisingly enough, only two… view at source ↗
Figure 2
Figure 2. Execution of BatchMatMul(y = [1; 2; . . . ; 16], A2 = L2). The BatchMatMul procedure takes a vector y and a square matrix As of size s as input. BatchMatMul performs a multiplication between As and a reshaped tensor view of y. The vector/tensor reshaping operations of the Batch￾MatMul method (Lines 18 and 20) need more clarification. In Line 18, a vector is viewed as a three-dimensional tensor as follows. The zero-p… view at source ↗
Figure 3
Figure 3. Execution diagram of the general case leveraging Algorithm 1 as a building [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

23 extracted references · 12 canonical work pages

  1. [8]

    In: Proceedings of the ACM Inter- national Conference on Supercomputing

    Dakkak, A., Li, C., Xiong, J., Gelado, I., Hwu, W.m.: Accelerating reduc- tion and scan using tensor core units. In: Proceedings of the ACM Inter- national Conference on Supercomputing. p. 46–57. ICS ’19, ACM (2019). https://doi.org/10.1145/3330345.3331057 (Cited on pages 1, 9, 10 and 11)

    arXiv 2019

  2. [1]

    In: Sythesis of parallel algo- rithms, pp

    Blelloch, G.E.: Prefix sums and their applications. In: Sythesis of parallel algo- rithms, pp. 35–60. Morgan Kaufmann (1990) (Cited on pages 1, 2 and 10)

    work page 1990

  3. [2]

    IEEE Transactions on Comput- ers C-31(3), 260–264 (1982)

    Brent, Kung: A regular layout for parallel adders. IEEE Transactions on Comput- ers C-31(3), 260–264 (1982). https://doi.org/10.1109/TC.1982.1675982 (Cited on pages 9 and 10)

    work page arXiv 1982

  4. [3]

    In: Proceedings of the Symposium on Theory of Computing (STOC)

    Brent, R.P., Kung, H.T.: The chip complexity of binary arithmetic. In: Proceedings of the Symposium on Theory of Computing (STOC). p. 190–200. ACM (1980). https://doi.org/10.1145/800141.804666 (Cited on pages 2 and 10)

    work page arXiv 1980

  5. [4]

    Journal of the ACM 21(2), 201–206 (Apr 1974)

    Brent, R.P.: The parallel evaluation of general arithmetic expressions. Journal of the ACM 21(2), 201–206 (Apr 1974). https://doi.org/10.1145/321812.321815, https://doi.org/10.1145/321812.321815 (Cited on page 9)

    arXiv 1974

  6. [5]

    In: Proceedings of International Conference on Knowledge Discovery and Data Mining (KDD)

    Chen, T., Guestrin, C.: XGBoost: A scalable tree boosting system. In: Proceedings of International Conference on Knowledge Discovery and Data Mining (KDD). p. 785–794. ACM (2016). https://doi.org/10.1145/2939672.2939785 (Cited on page 2) 12 A. Zouzias and W. F. McColl

    arXiv 2016

  7. [6]

    In: Proceedings of Symposium on Parallelism in Algorithms and Architec- tures (SPAA)

    Chowdhury, R., Silvestri, F., Vella, F.: A computational model for tensor core units. In: Proceedings of Symposium on Parallelism in Algorithms and Architec- tures (SPAA). p. 519–521. ACM (2020). https://doi.org/10.1145/3350755.3400252 (Cited on pages 1 and 2)

    arXiv 2020

  8. [7]

    In: International Conference on Parallel and Distributed Computing (Euro-Par)

    Chowdhury, R., Silvestri, F., Vella, F.: Algorithm design for tensor units. In: International Conference on Parallel and Distributed Computing (Euro-Par). p. 353–367. Springer-Verlag (2021) (Cited on pages 1 and 2)

    work page 2021

Show all 23 references
  1. [9]

    Nature 585(7825), 357–362 (Sep 2020)

    Harris, C., et al.: Array programming with NumPy. Nature 585(7825), 357–362 (Sep 2020). https://doi.org/10.1038/s41586-020-2649-2 (Cited on page 13)

    2020 doi

  2. [10]

    In: The Thirty-Seventh Asilo- mar Conference on Signals, Systems & Computers, 2003

    Harris, D.: A taxonomy of parallel prefix networks. In: The Thirty-Seventh Asilo- mar Conference on Signals, Systems & Computers, 2003. vol. 2, pp. 2213–2217 (2003). https://doi.org/10.1109/ACSSC.2003.1292373 (Cited on page 1)

    2003 arXiv

  3. [11]

    Hillis, W.D., Steele, G.L.: Data parallel algorithms. Commun. ACM 29(12), 1170–1183 (Dec 1986). https://doi.org/10.1145/7902.7903 (Cited on page 10)

    1986

  4. [12]

    Morgan Kaufmann, fourth edn

    Hwu, W.W., Kirk, D.B., El Hajj, I.: Programming Massively Paral- lel Processors (Fourth Edition). Morgan Kaufmann, fourth edn. (2023). https://doi.org/https://doi.org/10.1016/B978-0-323-91231-0.00006-9 (Cited on pages 1, 7 and 9)

    2023 doi

  5. [13]

    In: Proceedings of International Symposium on Computer Architecture (ISCA)

    Jouppi, N.P., et al.: In-datacenter performance analysis of a tensor processing unit. In: Proceedings of International Symposium on Computer Architecture (ISCA). p. 1–12. ACM (2017). https://doi.org/10.1145/3079856.3080246 (Cited on page 2)

    2017

  6. [14]

    In: Proceedings of International Symposium on Computer Archi- tecture (ISCA)

    Jouppi, N.P., et al.: Ten lessons from three generations shaped google’s TPUv4i: In- dustrial product. In: Proceedings of International Symposium on Computer Archi- tecture (ISCA). pp. 1–14 (2021). https://doi.org/10.1109/ISCA52012.2021.00010 (Cited on page 2)

    2021

  7. [15]

    IEEE Transactions on Computers C-22(8), 786–793 (1973)

    Kogge, P.M., Stone, H.S.: A parallel algorithm for the efficient solution of a general class of recurrence equations. IEEE Transactions on Computers C-22(8), 786–793 (1973). https://doi.org/10.1109/TC.1973.5009159 (Cited on page 10)

    1973

  8. [16]

    In: Advances in Neural Information Processing Systems (NIPS)

    Krizhevsky, A., Sutskever, I., Hinton, G.E.: Imagenet classification with deep con- volutional neural networks. In: Advances in Neural Information Processing Systems (NIPS). p. 1097–1105 (2012) (Cited on page 2)

    2012

  9. [17]

    In: Proceedings of International Symposium on High-Performance Computer Architecture (HPCA)

    Liao, H., Tu, J., Xia, J., Liu, H., Zhou, X., Yuan, H., Hu, Y.: Ascend: a scalable and unified architecture for ubiquitous deep neural network com- puting: industry track paper. In: Proceedings of International Symposium on High-Performance Computer Architecture (HPCA). pp. 78...

    2021

  10. [18]

    In: Hot Chips Symposium on High-Performance Chips (HCS)

    Liao, H., Tu, J., Xia, J., Zhou, X.: DaVinci: A scalable architecture for neural net- work computing. In: Hot Chips Symposium on High-Performance Chips (HCS). pp. 1–44 (2019). https://doi.org/10.1109/HOTCHIPS.2019.8875654 (Cited on page 2)

    2019

  11. [19]

    NVIDIA Authors: NVIDIA DGX-1 with Tesla V100 system architecture. Tech. Rep. MSU-CSE-06-2, Nvidia Corporation (Dec 2017), https://images.nvidia.com/ content/pdf/dgx1-v100-system-architecture-whitepaper.pdf (Cited on page 2)

    2017

  12. [20]

    IRE Transactions on Electronic Computers EC-9(2), 226–231 (1960)

    Sklansky, J.: Conditional-sum addition logic. IRE Transactions on Electronic Computers EC-9(2), 226–231 (1960). https://doi.org/10.1109/TEC.1960.5219822 (Cited on page 10) Parallel Scan in the TCU Model 13

    1960

  13. [21]

    Journal of Algorithms 7(2), 185–201 (1986)

    Snir, M.: Depth-size trade-offs for parallel prefix computation. Journal of Algorithms 7(2), 185–201 (1986). https://doi.org/https://doi.org/10.1016/0196- 6774(86)90003-9 (Cited on page 1)

    1986 doi

  14. [22]

    ACM Trans

    Zhu, H., Cheng, C.K., Graham, R.: On the construction of zero-deficiency parallel prefix circuits with minimum depth. ACM Trans. Des. Autom. Electron. Syst. 11(2), 387–409 (Apr 2006). https://doi.org/10.1145/1142155.1142162, https://doi. org/10.1145/1142155.1142162 (Cited on page 1)

    2006

  15. [23]

    local” prefix sums on each chunk is precomputed, Recurse returns the prefix sum of z (postcondition). Indeed, by the definition of MatMulScan- Recursive in Line 2 the “local

    Zimmermann, R.V.: Binary adder architectures for cell-based VLSI and their syn- thesis. Ph.D. thesis, Swiss Federal Institute of Technology Zurich, Zurich (1997) (Cited on page 1) A Appendix We provide a functional end-to-end (but not high-performance) Python im- plementation ...

    1997

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.