Parallel Prefix Computation

DOI10.1145/322217.322232zbMath0445.68066OpenAlexW2143462372WikidataQ59758694 ScholiaQ59758694MaRDI QIDQ3890136

Michael J. Fischer, Richard E. Ladner

Publication date: 1980

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/322217.322232

zbMATH Keywords

Boolean circuitscombinational complexitybinary additionprefix problemfinite-state transducerssequential adder

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items (only showing first 100 items - show all)

Parallel algorithms for the Hamiltonian cycle and Hamiltonian path problems in semicomplete bipartite digraphs ⋮ Selecting distances in the plane ⋮ Probabilistic parallel prefix computation ⋮ Two optimal parallel algorithms on the commutation class of a word ⋮ The delay of circuits whose inputs have specified arrival times ⋮ Parallel tree contraction and prefix computations on a large family of interconnection topologies ⋮ Functional Pearls ⋮ Fast Pseudorandom Functions Based on Expander Graphs ⋮ Improved parallel depth-first search in undirected planar graphs ⋮ An optimal parallel algorithm for planar cycle separators ⋮ OPTIMAL PARALLEL PREFIX ON MESH ARCHITECTURES ⋮ AN EFFICIENT ALGORITHM FOR MANAGING A PARALLEL HEAP∗ ⋮ PARALLEL METHOD FOR SOLVING SINGULARLY PERTURBED BOUNDARY VALUE PROBLEMS ⋮ Sweep methods for parallel computational geometry ⋮ Parallel complexity of algebraic operations ⋮ Parallelization strategy for elementary morphological operators on graphs: distance-based algorithms and implementation on multicore shared-memory architecture ⋮ A parallel algorithm for evaluating general linear recurrence equations ⋮ Conservative algorithms for parallel and sequential integer sorting ⋮ An optimal parallel algorithm for digital curve segmentation using hough polygons and monotone function search ⋮ Parallel time integration using batched BLAS (Basic Linear Algebra Subprograms) routines ⋮ Two parallel algorithms for finding all minimal maximum subsequences ⋮ Distributed computing with the Cloud ⋮ A generalized parallel prefix sums algorithm for arbitrary size arrays ⋮ Prefix graphs and their applications ⋮ A Parallel Algorithm for Computing the Eigenvalues of a Symmetric Tridiagonal Matrix ⋮ A parallel algorithm for channel routing ⋮ FACTORIZATIONS OF THE THOMPSON–HIGMAN GROUPS, AND CIRCUIT COMPLEXITY ⋮ Efficient string matching on packed texts ⋮ The average case complexity of the parallel prefix problem ⋮ Parallel discrete invariant embedding algorithm for singular pertubation problems ⋮ ARITHMETIC CODING IN PARALLEL ⋮ Functional and dynamic programming in the design of parallel prefix networks ⋮ Solving Random Ordinary Differential Equations on GPU Clusters using Multiple Levels of Parallelism ⋮ Generalized scans and tridiagonal systems ⋮ Parallel output-sensitive algorithms for combinatorial and linear algebra problems ⋮ Unnamed Item ⋮ Minimizing roundoff errors of prefix sums via dynamic construction of Huffman trees ⋮ Minimal parallel prefix circuits ⋮ Partial sums on the ultra-wide word RAM ⋮ A novel parallel prefix adder for optimized radix-2 FFT processor ⋮ On Parallel Implementations of Deterministic Finite Automata ⋮ Constructing depth-optimum circuits for adders and \textsc{And}-\textsc{Or} paths ⋮ The Queue-Read Queue-Write PRAM Model: Accounting for Contention in Parallel Algorithms ⋮ Fast Sequential and Parallel Vertex Relabelings of K_m,m ⋮ An efficient PRAM algorithm for maximum-weight independent set on permutation graphs ⋮ OPTIMAL BUCKET SORTING AND OVERLAP REPRESENTATIONS ⋮ Parallel prefix computation on extended multi-mesh network. ⋮ Parallelization of EM-Algorithms for Markovian Arrival Processes ⋮ Lambda calculus with algebraic simplification for reduction parallelisation: Extended study ⋮ ON THE POWER OF SOME PRAM MODELS ⋮ Determining Weak Visibility of a Polygon from an Edge in Parallel ⋮ A fast algorithm for scalar Nevanlinna-Pick interpolation ⋮ Finding level-ancestors in trees ⋮ A chained-matrices approach for parallel computation of continued fractions and its applications ⋮ Unbounded fan-in circuits and associative functions ⋮ Functional inversion and communication complexity ⋮ A faster parallel algorithm for \(k\)-connectivity ⋮ A theory of strict P-completeness ⋮ An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph ⋮ Almost fully-parallel parentheses matching ⋮ Parallel ear decomposition search (EDS) and st-numbering in graphs ⋮ Optimal computation of prefix sums on a binary tree of processors ⋮ An optimal speed-up parallel algorithm for triangulating simplicial point sets in space ⋮ Communication-efficient parallel algorithms for distributed random-access machines ⋮ Data structures and algorithms for approximate string matching ⋮ Parallel construction of a suffix tree with applications ⋮ Finding the convex hull of a sorted point set in parallel ⋮ A parallel bucket sort ⋮ Efficient massively parallel implementation of some combinatorial algorithms ⋮ Computing downwards accumulations on trees quickly ⋮ Efficient parallel circuits and algorithms for division ⋮ Delay optimization of linear depth Boolean circuits with prescribed input arrival times ⋮ Complexity theory of parallel time and hardware ⋮ An improved algorithm for the \(p\)-center problem on interval graphs with unit lengths ⋮ Transversal partitioning in balanced hypergraphs ⋮ Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\) ⋮ Formal proof of integer adders using all-prefix-sums operation ⋮ Techniques for parallel manipulation of sparse matrices ⋮ An optimal parallel algorithm for the minimum circle-cover problem ⋮ A new complete language for DSPACE(log n) ⋮ Parallel approximation algorithms for bin packing ⋮ Parallel Hermite interpolation: An algebraic approach ⋮ The \(p\)-Maxian problem on interval graphs ⋮ Formal proof of prefix adders ⋮ An optimal parallel algorithm for digital curve segmentation ⋮ Layouts for improved hierarchical parallel computations ⋮ Oblivious algorithms for multicores and networks of processors ⋮ Optimal algorithms for sensitivity analysis in associative multiplication problems ⋮ Sorting roughly sorted sequences in parallel ⋮ Distributed XML processing: theory and applications ⋮ Parallel models of computation: An introductory survey ⋮ Efficient parallel algorithms for linear recurrence computation ⋮ A parallel method for fast and practical high-order Newton interpolation ⋮ Subtree isomorphism is in random NC ⋮ Finding a minimal cover for binary images: An optimal parallel algorithm ⋮ Radix sort on the hypercube ⋮ Processor-efficient implementation of a maximum flow algorithm ⋮ Inverting a Vandermonde matrix in minimum parallel time ⋮ Computations over finite monoids and their test complexity ⋮ Planar orientations with low out-degree and compaction of adjacency matrices

This page was built for publication: Parallel Prefix Computation