New data movement algorithms for processor arrays

The performance of a parallel algorithm relies heavily on the routing demands of the algorithm and how efficiently the parallel system copes with the demands. Highly parallel, bit-serial machines became most powerful when the application involves low precision or integer data. Lowering the precision results in an increase in algorithmic noise. Algorithms are presented that implement the noiseless data permutations required in the prime factor and Winograd´s discrete Fourier transform algorithms on a highly parallel processor array that has parallel access only to bit planes. The costs for both the conventional `twiddles´ and for the new algorithms are included using the ICL, 200 ns, distributed array processor (DAP)