Online communication on circuit-switched fixed routing meshes

The paper addresses routing on the circuit-switched fixed routing n×n mesh M_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²) to run in n routing steps on M_n, and another self-routing algorithm that schedules in constant time any Ω- or ω¹-realizable permutation to run in 2n routing steps on M_n. Finally, it is shown that broadcasting and fan-in communication self-route in log N routing steps, that parallel prefix requires log²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