The DOI matches its Crossref record; 14 of the 14 references it cites were found in a registry or an index.
Scans as primitive parallel operations
Abstract
A study of the effects of adding two scan primitives as unit-time primitives to PRAM (parallel random access machine) models is presented. It is shown that the primitives improve the asymptotic running time of many algorithms by an O(log n) factor, greatly simplifying the description of many algorithms, and are significantly easier to implement than memory references. It is argued that the algorithm designer should feel free to use these operations as if they were as cheap as a memory reference. The author describes five algorithms that clearly illustrate how the scan primitives can be used in algorithm design: a radix-sort algorithm, a quicksort algorithm, a minimum-spanning-tree algorithm, a line-drawing algorithm, and a merging algorithm. These all run on an EREW (exclusive read, exclusive write) PRAM with the addition of two scan primitives and are either simpler or more efficient than their pure PRAM counterparts. The scan primitives have been implemented in microcode on the Connection Machine system, are available in PARIS (the parallel instruction set of the machine).>
Overview
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
Verification
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.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Data Structures and Network Algorithms
Tarjan, R. E. (1983) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611970265 · Cited by 2,057
Ladner, R. E., & Fischer, M. J. (1980) · Journal of the ACM · doi:10.1145/322217.322232 · Cited by 1,281
Parallel Processing with the Perfect Shuffle
Stone, H. S. (1971) · IEEE Transactions on Computers · doi:10.1109/t-c.1971.223205 · Cited by 1,245
Iverson, K. E. (1962) · Proceedings of the May 1-3, 1962, spring joint computer conference on - AIEE-IRE '62 (Spring) · doi:10.1145/1460833.1460872 · Cited by 1,067
Parallelism in random access machines
Fortune, S., & Wyllie, J. (1978) · Proceedings of the tenth annual ACM symposium on Theory of computing - STOC '78 · doi:10.1145/800133.804339 · Cited by 891
Hoare, C. A. R. (1962) · The Computer Journal · doi:10.1093/comjnl/5.1.10 · Cited by 764
The NYU Ultracomputer—Designing an MIMD Shared Memory Parallel Computer
Gottlieb, Grishman, Kruskal, McAuliffe, Rudolph, & Snir (1983) · IEEE Transactions on Computers · doi:10.1109/tc.1983.1676201 · Cited by 743
An O(logn) parallel connectivity algorithm
Shiloach, Y., & Vishkin, U. (1982) · Journal of Algorithms · doi:10.1016/0196-6774(82)90008-6 · Cited by 592
Sorting on a mesh-connected parallel computer
Thompson, C. D., & Kung, H. T. (1977) · Communications of the ACM · doi:10.1145/359461.359481 · Cited by 480
Parallel tree contraction and its application
Miller, G. L., & Reif, J. H. (1985) · 26th Annual Symposium on Foundations of Computer Science (sfcs 1985) · doi:10.1109/sfcs.1985.43 · Cited by 404
Cited by
MapReduce: simplified data processing on large clusters
Dean, J., & Ghemawat, S. (2008) · Communications of the ACM · doi:10.1145/1327452.1327492 · Cited by 18,476
MapReduce: Simplified Data Processing on Large Cluster
Senior Software Developer, A. U., & Dayalan, M. (2018) · International Journal of Research and Engineering · doi:10.21276/ijre.2018.5.5.4 · Cited by 2,948
LogP: towards a realistic model of parallel computation
Culler, D., Karp, R., Patterson, D., Sahay, A., Schauser, K. E., Santos, E., Subramonian, R., & von Eicken, T. (1993) · Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming - PPOPP '93 · doi:10.1145/155332.155333 · Cited by 1,496
Evaluating MapReduce for Multi-core and Multiprocessor Systems
Ranger, C., Raghuraman, R., Penmetsa, A., Bradski, G., & Kozyrakis, C. (2007) · 2007 IEEE 13th International Symposium on High Performance Computer Architecture · doi:10.1109/hpca.2007.346181 · Cited by 966
Compiler transformations for high-performance computing
Bacon, D. F., Graham, S. L., & Sharp, O. J. (1994) · ACM Computing Surveys · doi:10.1145/197405.197406 · Cited by 818
Metadata
- Authors
- Blelloch, G. E.
- Venue
- IEEE Transactions on Computers
- Published
- 1989
- Volume
- 38
- Issue
- 11
- Pages
- 1526-1538
- ISSN
- 0018-9340 (ISSN-L)
- OpenAlex
- W1605715232
- Cited by
- 538
- References
- 14
- FWCI
- 21.04
- Type
- journal article
- Language
- en
- Open access
- closed
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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Scans as primitive parallel operations. https://app.cochat.ai/papers/10.1109/12.42122
- The paper
- Blelloch, G. E. (1989). Scans as primitive parallel operations. IEEE Transactions on Computers. https://doi.org/10.1109/12.42122
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.