Abstract: This chapter demonstrates the use of different data distributions in different phases of a computation: both the block and cyclic distributions of a vector are used and the intermediates between them. Each data redistribution is a permutation that requires communication. By making careful choices, the number of such redistributions is kept to a minimum. This approach is demonstrated for the fast Fourier transform (FFT), a regular computation with a predictable but challenging data access pattern. The chapter shows how permutations with a regular pattern can be implemented more efficiently by packing the data. It discusses how to present the results of numerical experiments in a meaningful manner using the metrics of speedup and efficiency.

Keywords: block distribution, cyclic distribution, FFT, permutation, redistribution, speedup,