Online communication on circuit-switched fixed routing meshes
A. Youssef · 2003
The paper addresses routing on the circuit-switched fixed routing n*n mesh M/sub n/ where paths follow the row-column rule. It first presents a self-routing algorithm that schedules any BPC permutation in L(logN) time (N=n/sup 2/) to run in n routing steps on M/sub n/, and another self-routing algorithm that schedules in constant time any Omega - or omega /sup 1/-realizable permutation to run in 2n routing steps on M/sub n/. Finally, it is shown that broadcasting and fan-in communication self-route in log N routing steps, that parallel prefix requires log/sup 2/N routing steps and that FFT requires O(n) routing steps. In all but the FFT case, the circuit-switched mesh delivers better performance than its packet-switched counterpart.>