IEEE Transactions on Computers · 1997 · 26 citations · 19 references
ComputingComputer EngineeringComputer ScienceComputer ArchitectureParallel AlgorithmsParallel ComputingData ParallelismMesh ModelingMesh NetworksMesh ProcessingMesh TopologyParallel SortingMesh SortingParallel Sorting AlgorithmsParallel Time Complexity
The shear-sort algorithm on an SIMD mesh model requires 4/spl radic/N+o(/spl radic/N) time for sorting N elements arranged on a /spl radic/N/spl times//spl radic/N mesh. In this paper, we present an algorithm for sorting N elements in time O(N/sup 1/4/) on an SIMD multi-mesh architecture, thereby significantly improving the order of the time complexity. The multi-mesh architecture is built around n/sup 2/ blocks, where each block is an n/spl times/n mesh with n=N/sup 1/4/, so that each processor will uniformly have four neighbors in the final topology.
19
Sorting networks and their applications
Kenneth E. Batcher · 1968 · 2.4K citations
Miklós Ajtai, János Komlós, Endre Szemerédi · 1983 · 671 citations
Sorting on a mesh-connected parallel computer
Clark D. Thompson, H. T. Kung · Communications of the ACM · 1977 · 476 citations · Full text
Richard Cole · 1986 · 363 citations