Parallel Processing with the Perfect Shuffle

DOI10.1109/T-C.1971.223205zbMath0214.42703OpenAlexW1976284552MaRDI QIDQ5617294

Publication date: 1971

Published in: IEEE Transactions on Computers (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/t-c.1971.223205

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) General theory of computer systems (68M01)

Related Items (89)

An introduction to parallelism in combinatorial optimization ⋮ On recurrent and recursive interconnection patterns ⋮ A VLSI algorithm for sorting variable-length character strings ⋮ A chained-matrices approach for parallel computation of continued fractions and its applications ⋮ Routing, merging, and sorting on parallel models of computation ⋮ Algorithms for parallel memory, I: Two-level memories ⋮ A neural sorting network with O(1) time complexity ⋮ Fast parallel preconditioned conjugate gradient algorithms for robot manipulator dynamics simulation ⋮ Long edges in the layouts of shuffle-exchange and cube-connected cycles graphs ⋮ A hardware independent parallel programming model ⋮ Array processing machines: an abstract model ⋮ Optimal Parallel Algorithms For Multiselection On Mesh-Connected Computers ⋮ Work-preserving emulations of shuffle-exchange networks: An analysis of the complex plane diagram ⋮ Self-routing control algorithms and the passability of random inputs by the base-line network ⋮ A parallel algorithm for the generation of a permutation and applications ⋮ An approach to emulating separable graphs ⋮ Optimal book embeddings of the FFT, Benes, and barrel shifter networks ⋮ Topological properties of the recursive Petersen architecture ⋮ Synthesis and equivalence of concurrent systems ⋮ Permutation algorithms on optical multi-trees ⋮ Fault-tolerance VLSI sorters ⋮ PARALLEL POLYNOMIAL EVALUATION BY DECOUPLING ALGORITHM ⋮ Sloping-and-shaking ⋮ A parallel sorting scheme whose basic operation sortsN elements ⋮ A new policy to solve routing conflicts in shuffle-exchange networks ⋮ Interpolation between bases and the shuffle exchange network ⋮ Noisy sort, a memory-intensive sorting algorithm ⋮ Optimal parallel algorithms for computing convex hulls and for sorting ⋮ Cartesian products of graphs as subgraphs of de Bruijn graphs of dimension at least three ⋮ Parallel approximation algorithms for bin packing ⋮ The Half Cleaner Lemma: Constructing Efficient Interconnection Networks from Sorting Networks ⋮ FFT algorithms and their adaptation to parallel processing ⋮ Hypercomplete: A pancyclic recursive topology for large-scale distributed multicomputer systems ⋮ The shuffle exchange network has a Hamiltonian path ⋮ Real-time emulations of bounded-degree networks ⋮ Universality of iterated networks ⋮ Time-optimal simulations of networks by universal parallel computers ⋮ A method of batching conflict routings in shuffle-exchange networks ⋮ Matrix transpose on meshes with wormhole and XY routing ⋮ On the construction of balanced matrices ⋮ Graphs with the unique path property: Structure, cycles, factors, and constructions ⋮ Artificial Neural Networks Generated by Low Discrepancy Sequences ⋮ An optimal time bound for oblivious routing ⋮ A layout for the shuffle-exchange network with theta(\(N^ 2\) /log N) area ⋮ Small-diameter Cayley graphs for finite simple groups ⋮ Parallel algorithms for the connected components and minimal spanning tree problems ⋮ SHUFFLE-RING: A NEW CONSTANT-DEGREE NETWORK ⋮ Fast orthogonal derivatives on the STAR ⋮ Processor-time optimal parallel algorithms for digitized images on mesh- connected processor arrays ⋮ The shuffle exchange network has a Hamiltonian path ⋮ Trends in systolic and cellular computation ⋮ Data reduction and fast routing: A strategy for efficient algorithms for message-passing parallel computers ⋮ Growth in SL2 over finite fields ⋮ Product-shuffle networks: Toward reconciling shuffles and butterflies ⋮ Embedding meshes of trees into deBruijn graphs ⋮ Stride permutation networks for array processors ⋮ DESIGN OF A PARALLEL INTERCONNECT BASED ON COMMUNICATION PATTERN CONSIDERATIONS ⋮ Permutation-exchange graphs that emulate the binary cube ⋮ GSE: a full-access multistage interconnection network of arbitrary size ⋮ Permutations on the block PRAM ⋮ Layouts for the Shuffle-Exchange Graph Based on the Complex Plane Diagram ⋮ Systolic arrays for multidimensional discrete transforms ⋮ The 2D SEM: A novel high-performance and low-power mesh-based topology for networks-on-chip ⋮ Permuting data with the Omega network ⋮ Balanced permutations and multistage interconnection networks ⋮ A new approach to parallel computing ⋮ On vectorizing the fast fourier transform ⋮ Rotator design ⋮ Minimizing roundoff errors of prefix sums via dynamic construction of Huffman trees ⋮ Simulating the Bitonic Sort Using P Systems ⋮ Realization of graceful permutation by a shuffle-exchange network ⋮ Representing graph families with edge grammars ⋮ Solving the symmetric tridiagonal eigenvalue problem on hypercubes ⋮ Exposing graph uniformities via algebraic specification ⋮ A generalization of the zero-one principle for sorting algorithms ⋮ A methodology for designing, modifying, and implementing Fourier transform algorithms on various architectures ⋮ Better understanding of Batcher's merging networks ⋮ A mathematical abstraction of the rearrangeability conjecture for shuffle-exchange networks ⋮ An asymptotically optimal layout for the shuffle-exchange graph ⋮ Optimal three-dimensional VLSI layouts ⋮ Computing the cycles in the perfect shuffle permutation ⋮ A generalization of the perfect shuffle ⋮ The mathematics of perfect shuffles ⋮ A new parallel sorting algorithm based upon min-mid-max operations ⋮ A multiprocess network logic with temporal and spatial modalities ⋮ Space-efficient parallel merging ⋮ Deterministic sorting in nearly logarithmic time on the hypercube and related computers ⋮ Topological transformations as a tool in the design of systolic networks ⋮ A direct routing algorithm for the bit-reversal permutation on a shuffle- exchange network

This page was built for publication: Parallel Processing with the Perfect Shuffle