Robust shearsort on incomplete bypass meshes

An incomplete 2-D bypass mesh is a rectangular m×n grid of p processing elements (PEs) in which faulty PEs have been bypassed in their respective rows and columns. Thus, two PEs that are separated only by faulty PEs in the same row or column become neighbors. We show that given O(log m) PE faults in each column, a robust version of the sorting scheme known as shearsort has the same O(m+n log m) asymptotic time complexity on such an incomplete mesh as on a complete mesh. We also demonstrate how the ability to compute on incomplete meshes is relevant to fault tolerance by presenting reconfiguration schemes to convert meshes with faulty PEs into incomplete bypass meshes