Evaluation of fast Fourier and Hartley transforms on a loosely coupled multiprocessor based on the Inmos transputer

The computation of fast Fourier and Hartley transforms on a transputer-based multiprocessor is discussed. The algorithms presented are based on the independent task parallelism (ITP) and process farm paradigms, for which statically scheduled algorithms have been developed. The generic process farm consists of a sequential controller process running on a single processor, in cascade with an ITP part running on the other p-1 processors. The controller process dispatches and gathers sub-problems to/from the ITP part of the algorithm. Scheduling efficiency is discussed and expressions given for how to partition the algorithm between a controller and a number of slave processes when the number of processors is fixed. Efficiency is related to the ratio of the problem size/machine size. This relationship is expressed as a function of a half-performance problem-size parameter. Finally, the theoretical models are compared to bench-marks obtained from Occam 2 implementations of some of the above algorithms