The input/output complexity of sorting and related problems
Open accessAbstract
We provide tight upper and lower bounds, up to a constant factor, for the number of inputs and outputs (I/OS) between internal memory and secondary storage required for five sorting-related problems: sorting, the fast Fourier transform (FFT), permutation networks, permuting, and matrix transposition. The bounds hold both in the worst case and in the average case, and in several situations the constant factors match. Secondary storage is modeled as a magnetic disk capable of transferring P blocks each containing B records in a single time unit; the records in each block must be input from or output to B contiguous locations on the disk. We give two optimal algorithms for the problems, which are variants of merge sorting and distribution sorting. In particular we show for P = 1 that the standard merge sorting algorithm is an optimal external sorting method, up to a constant factor in the number of I/Os. Our sorting algorithms use the same number of I/Os as does the permutation phase of key sorting, except when the internal memory size is extremely small, thus affirming the popular adage that key sorting is not faster. We also give a simpler and more direct derivation of Hong and Kung's lower bound for the FFT for the special case B = P = O(1).
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
A missing principle for attention algorithms is IO-awareness-accounting for reads and writes between levels of GPU memory.
“We argue that a missing principle is making attention algorithms IOaware -accounting for reads and writes between levels of GPU memory.”
From FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness (2022) · cites this paper as [1]
The Introduction describes studying algorithms by the number of I/Os, and Section 3 models transfers between disk and internal memory. That supports the general principle of accounting for data movement, but the paper does not address attention algorithms or transfers between levels of GPU memory. (LLM, conf=0.85)
Experimental — accuracy not yet measuredFlashAttention requires O(N^2 d^2 M^{-1}) HBM accesses where d is head dimension and M is SRAM size, compared to Ω(Nd + N^2) of standard attention.
“We analyze the IO complexity [1] of FlashAttention , proving that it requires 𝑂 𝑁 2 𝑑 2 𝑀 1 HBM accesses where 𝑑 is the head dimension and 𝑀 is the size of SRAM, as compared to Ω 𝑁𝑑 𝑁 2 of standard attention.”
From FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness (2022) · cites this paper as [1]
FlashAttention requires fewer HBM accesses than standard attention.
“We analyze the IO complexity of FlashAttention , showing that it requires fewer HBM accesses than standard attention, and is optimal for a range of SRAM sizes.”
From FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness (2022) · cites this paper as [1]
The Introduction and Section 3 describe I/O bounds for sorting-related problems and transfers between disk and internal memory. A search of our copy for FlashAttention, HBM, SRAM, and attention found no passage comparing FlashAttention with standard attention, so it cannot verify the claimed reduction in HBM accesses. (LLM, conf=0.78)
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
No references could be resolved yet.
Research works printed but not linked: 8
- Floyd, R.W. Permuting info;mati& in ideaiized'two-:evel storage. In Complexity of Computer Calculations, R. Miller and J. Thatcher, Eds. Plenum, New York, 1972, pp. 105-109.
- Hong, J.W., and Kung, H.T. I/O complexity: The red-blue pebble game. In Proceedingsof the 13th Annual ACM Symposimn on Theory of Computing (Milwaukee, Wisconsin, Oct.). pp. 326-333. 1981.
- Knuth, D.E. The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley, Reading, Mass., 1973.
- Kwan, S.C., and Baer, J.L. The I/O performance of multiway merge- sort and tag sort. IEEE Trans. Compuf. C-34,4 (Apr. 1985), 383-387.
- Leighton, F.T. Tight bounds on the complexity of parallel sorting. IEEE Trans. Comput. C-34,4 (Apr. 1985).
- Lindstrom. E.E., and Vitter, J.S. The design and analysis of Bucket- Sort for bubble memory secondary storage. IEEE Trans. Comput. C-34, 3 (Mar. 1985), 218-233.
- Savage. J.E., and Vitter, J.S. Parallelism in space-time tradeoffs. In Advances in Computing Research, Volume 4: Special issue on Parallel and Disfributed Computing. JAI Press, Greenwich, Corm., 1987, pp. 117-146.
- Wu, CL.. and Feng, T.Y. The universality of the shuffle-exchange network. IEEE Trans. Comput. C-30, 5 (May 1981), 324-332.
Cited by
Sorted by citations
FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness
Dao, T., Fu, D. Y., Ermon, S., Rudra, A., & Ré, C. (2022) · arXiv · doi:10.48550/arxiv.2205.14135 · Cited by 1,214 · see citing works
“We draw the most direct connection to the literature of analyzing I/O complexity in this work [1], but concepts of memory hierarchies are fundamental and has appeared in many forms, from the working set model [23], to data locality [90], to the Roofline model of arithmetic intensity [89], to…”
Method
- Authors
- Aggarwal, A., & Vitter, J.
- Affiliations
- IBM (United States) (US)
- Brown University (US)
- Venue
- Communications of the ACM
- Published
- 1988-09
- Volume
- 31
- Issue
- 9
- Pages
- 1116-1127
- ISSN
- 0001-0782 (ISSN-L)
- 1557-7317
- OpenAlex
- W2038142281
- Cited by
- 1,220
- References
- 0
- Citations by year
- 2026: 13 · 2025: 14 · 2024: 9 · 2023: 21 · 2022: 33 · 2021: 37 · 2020: 30 · 2019: 41 · 2018: 51 · 2017: 28 · 2016: 44 · 2015: 65 · 2014: 60 · 2013: 64 · 2012: 75
- FWCI
- 4.52
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- Communications of the ACM (publishedVersion)
- OpenGrey (Institut de l'Information Scientifique et Technique) (submittedVersion)
- HAL (submittedVersion, other-oa)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Algorithms and Data Compression
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Physical Sciences › Computer Science › Hardware and Architecture › Parallel Computing and Optimization Techniques
- Keywords
- I/O complexity, external memory algorithms, sorting, fast Fourier transform, permutation networks, matrix transposition, lower bounds, average-case analysis, worst-case analysis
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
