---
title: "Prefix Sums and Their Applications — paper by Blelloch (1990)"
description: "This chapter presents the all-prefix-sums operation (called a scan ) as a basic building block for parallel algorithms. Cited by 82 papers here."
authors: ["Guy E. Blelloch"]
year: 1990
venue: "textbook"
source: "https://www.cs.cmu.edu/~guyb/"
licence: "author copy (cs.cmu.edu) — read only"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/blelloch-1990-prefix-sums-their-applications/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/blelloch-1990-prefix-sums-their-applications/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [1990](https://md.research.elamur.ai/free/en/papers/1990/) / Prefix Sums and Their Applications

# Prefix Sums and Their Applications

**Authors:** Guy E. Blelloch · **Year:** 1990 · **Venue:** textbook · **Licence:** author copy (cs.cmu.edu) — read only

**Links:** [Publisher's page](https://www.cs.cmu.edu/~guyb/papers/Ble93.pdf) · [PDF](https://www.cs.cmu.edu/~guyb/papers/Ble93.pdf)

**Citations:** [82](https://md.research.elamur.ai/free/en/papers/blelloch-1990-prefix-sums-their-applications/cited-by/) in our library, of the 149,439 papers whose bibliographies we read

## Summary
This chapter presents the all-prefix-sums operation (called a *scan*) as a basic building block for parallel algorithms. Given an associative operator and a sequence, a scan returns every running combination of the elements. A related *prescan* returns, at each position, the combination of all earlier elements only. Computing prefix sums looks inherently sequential, because each output depends on the previous one. Blelloch nevertheless gives a simple, work-efficient parallel algorithm for the vector version on an EREW PRAM. It uses two passes over a balanced binary tree: an up-sweep that computes partial sums (a reduce) and a down-sweep that spreads offsets back to the leaves. With p processors, each one first handles a block of n/p elements, which gives O(n/p + lg p) time. That is an optimal speedup whenever n/p ≥ lg p. The rest of the chapter shows how many problems reduce to scans, including line-of-sight, radix sort, quicksort, recurrence solving, processor allocation and line drawing. This makes the scan a reusable primitive that is also suitable for hardware.

## Key points
- **Requirements on the operator:** it must be associative but need not be commutative, because the tree preserves operand order.
- **Costs:** the tree reduce takes ⌈lg n⌉ steps with n/2 processors. The prescan down-sweep adds another lg n steps, for about 2⌈lg n⌉ in total.
- **Blocked version:** each processor sums its block, the processor sums are prescanned, and the results are used as per-block offsets. Total time is 2(⌈n/p⌉ + ⌈lg p⌉).
- **Correctness:** the down-sweep is proved correct by induction. After it finishes, every tree vertex holds the sum of all leaves that precede it in preorder.
- **Applications listed (13):** string comparison, multi-precision addition, polynomial evaluation, recurrences, radix sort, quicksort, tridiagonal systems, deleting marked elements, processor allocation, lexical analysis, regex search (grep), tree depths and image component labeling.

## Interesting ideas
- **Up-sweep/down-sweep pattern:** first build partial aggregates bottom-up, then push "everything to my left" top-down. This turns any associative aggregation into a parallel prefix computation, which could serve tasks such as cumulative token counts or running offsets in large corpora.
- **Prescan as an allocator:** an exclusive prefix sum over per-item sizes yields each item's start offset. This lets variable-length outputs be packed or allocated in parallel, as in the line-drawing example where each line gets a run of pixel slots.
- **In-place layout:** storing partial sums at the right child positions means the down-sweep can reuse them without extra memory. This careful memory layout matters for GPU and SIMD implementations.
- **Two-level blocking:** do sequential work locally, run the parallel tree only over the p block totals, then apply the offsets. This is a practical recipe for getting near-linear speedup on real machines with few cores.
- **Scans as a primitive:** treating scans as a unit-cost primitive, as the paper proposes for the PRAM, simplifies both the design and the analysis of algorithms. Tasks like marking comment spans or tokenizing text become a few scans.

*Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.*

📚 Shelves (1): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 18,614 works

## Cite

Cite as: Guy E. Blelloch. 1990. Prefix Sums and Their Applications. textbook.

The paper itself, not this page. BibTeX from the library's record of the work.

```bibtex
@book{blelloch1990prefix,
  title = {{Prefix Sums and Their Applications}},
  author = {Guy E. Blelloch},
  year = {1990},
  url = {https://www.cs.cmu.edu/~guyb/papers/Ble93.pdf}
}
```

- [← previous Using Test Suites in Evaluation of Machine Translation Systems](https://md.research.elamur.ai/free/en/papers/king-1990-test-suites-evaluation-machine-translation/)
- [next → Performatives in a Rationally Based Speech Act Theory](https://md.research.elamur.ai/free/en/papers/cohen-1990-performatives-rationally-based-speech-act/)
- [↑ back to papers of 1990](https://md.research.elamur.ai/free/en/papers/1990/)

*Updated 2 November 2026*