The Optimal Uniform Schedules of Arbitrary Static Permutations on Superposed Parallel Buses

Abstract:

The paper is concerned with the optimal schedule for the permutation of n2 packetes on an nxn square grid of superposed, parallel time multiplexed buses. It is shown that the Uniform schedule (that is, all two-step transfers consistently row first or alternately column first) is optimal. Moreover, it requires n+1 bus transfers, or cycle times. Although n-cycle, non-uniform schedules exist for specific permutations, it is shown that n + 1 cycle, uniform schedule is optimal.