An optimal routing algorithm for mesh-connected Parallel computers
David Nassimi, Sartaj K. Sahni · Journal of the ACM · 1980
An opUmal algorithm to route data in a mesh-connected parallel computer is presented This algorithm can be used to perform any data routing that can be specified by the permutation and complementing of the bits in a PE address Matrix transpose, bit reversal, vector reversal, and perfect shuffle are examples of data permutations that can be specified in this way The algorithm presented uses the minimum number of unit distance routing steps for every data permutation that can be specified as above K~EV WORDS ANY PrmASES parallel algorithm, mesh-connected computer, ILLIAC IV, permutation, complexity, data routing CR CATEGORIES 5 25, 5 31, 6 22