Practical Algorithms For Online Routing on SIMD Meshes

: The problem of online routing on SIMD meshes arises when these processors are used for real-time analysis of sensory input. Existing algorithms---ones not making unrealistic hardware assumptions---use sorting as a subroutine and so, while asymptotically optimal, have running times at least 3 times greater (for likely array sizes) than the lower bound of 4n \\Gamma 4 communication steps. Dedicated router networks address this problem, but are costly and not available on all processors. We present a greedy algorithm with very low overhead based on wormhole routing, which can be modified to use broadcast buses and reconfigurable broadcast buses to successively improve performance. While we prove a bad worst case, performance is usually at worst a small additive constant from optimal, and always within a factor of 2 for every communication pattern tried. We also show that preprocessing randomization can improve the reliabilty of this result. Other algorithms are presented: one takes adva...