Sorting on a mesh-connected parallel computer

DOI10.1145/359461.359481zbMath0349.68020MaRDI QIDQ4120129

H. T. Kung, Clark D. Thompson

Publication date: 1977

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

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

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q45: Formal languages and automata

68N01: General topics in the theory of software

68W99: Algorithms in computer science

Related Items

Branch-and-bound and backtrack search on mesh-connected arrays of processors, A faster algorithm for sorting on mesh-connected computers with multiple broadcasting using fewer processors, Robust algorithms for packet routing in a mesh, An efficient selection algorithm on the pyramid, Randomized multipacket routing and sorting on meshes, Integer sorting on a mesh-connected array of processors, Computing convexity properties of images on a pyramid computer, Computational geometry algorithms for the systolic screen, Optimal routing algorithms for mesh-connected processor arrays, Indexing functions and time lower bounds for sorting on a mesh-connected computer, Efficient algorithms for parallel sorting on mesh multicomputers, Packet Routing on grids of processors, Sloping-and-shaking, A \(2n-2\) step algorithm for routing in an \(n \times n\) array with constant-size queues, A unified \(O(\log N)\) and optimal sorting vector algorithm, Fast deterministic selection on mesh-connected processor arrays, A neural sorting network with O(1) time complexity, Scalable algorithms for the mesh with buses: merging, sorting and selection