Parallel Prefix Computation
From MaRDI portal
Publication:3890136
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
Boolean circuitscombinational complexitybinary additionprefix problemfinite-state transducerssequential adder
Related Items
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, Matrix inversion in RNC\(^ 1\), Algebraic structure of some stochastic discrete event systems, with applications, An optimal parallel adaptive sorting algorithm, Efficient algorithms for the minimum weighted dominating clique problem on permutation graphs, Parallel restructuring and evaluation of expressions, Optimal parallel algorithms for point-set and polygon problems, Optimal parallel algorithms for path problems on planar graphs, Independent sets versus perfect matchings, Mapping a functional notation for parallel programs onto hypercubes, Parallel rectilinear shortest paths with rectangular obstacles, Line-segment intersection reporting in parallel, A parallel algorithm for minimum weighted colouring of triangulated graphs, Fast prefix adders for non-uniform input arrival times, Circuits over monoids: A fault model, and a trade-off between testability and circuit delay, An optimal parallel algorithm for the domatic partition problem on an interval graph given its sorted model, A note on the reconstruction of a binary tree from its traversals, Optimal parallel time bounds for the maximum clique problem on intervals, An efficient algorithm for multiple simultaneous broadcasts in the hypercube, Recognition of DFS trees: Sequential and parallel algorithms with refined verifications, Testing a simple polygon for monotonicity optimally in parallel, Parallel recognition of series-parallel graphs, Parallel methods for visibility and shortest-path problems in simple polygons, Non-associative parallel prefix computation, Parallel prefix computation with few processors, Constructing the Voronoi diagram of a set of line segments in parallel, Matching parentheses in parallel, Efficient parallel recognition of some circular arc graphs. I, Limited width parallel prefix circuits, Fast computation of divided differences and parallel Hermite interpolation, A note on adaptive parallel sorting, Matrix exponentials and parallel prefix computation in a quantum control problem, Constructing arrangements optimally in parallel, Massively time-parallel, approximate simulation of loss queueing systems, Efficient parallel algorithms for graph problems, A parallel algorithm for finding a blocking flow in an acyclic network, Optimal parallel algorithms on circular-arc graphs, Fast computation of continued fractions, A nearly optimal deterministic parallel Voronoi diagram algorithm, Optimal circular arc representations: Properties, recognition, and construction, Truly efficient parallel algorithms: 1-optimal multisearch for an extension of the BSP model, A recursive doubling algorithm for solution of tridiagonal systems on hypercube multiprocessors, Computing Prüfer codes efficiently in parallel, Faster optimal parallel prefix sums and list ranking, Parallel construction and query of index data structures for pattern matching on square matrices, Simulation of one-way cellular automata by Boolean circuits, On computing the determinant in small parallel time using a small number of processors, Removing randomness in parallel computation without a processor penalty, A simple optimal parallel algorithm for the minimum coloring problem on interval graphs, On parallel integer sorting, Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs, Parallel solutions to geometric problems in the scan model of computation, 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 Km,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
