Optimal sorting algorithms on incomplete meshes with arbitrary fault patterns
Chi‐Hsiang Yeh, Behrooz Parhami · 2002
In this paper we propose simple and efficient algorithms for sorting on incomplete meshes. No hardware redundancy is required and no assumption is made about the availability of a complete submesh. The proposed robust sorting algorithms are very efficient when only a few processors are faulty and degrade gracefully as the number of faults increases. In particular we show that 1-1 sorting (1 key per healthy processor) in row-major or snakelike row-major order can be performed in 3n+o(n) communication and comparison steps on an n/spl times/n incomplete mesh that has an arbitrary pattern of o(/spl radic/n) faulty processors. This is the fastest algorithm reported thus far for sorting in row-major and snakelike row-major orders on faulty meshes and the time complexity is quite close to its lower bound.