PARALLEL 1D-FFT COMPUTATION ON CONSTANT-VALENCE MULTICOMPUTERS

This paper addresses the problem of monodimensional (1D) FFT parallel computation on constant-valence multicomputers, i.e. on parallel syste ms made up of processing elements (PEs) which do not share memory and are connected to a bounded number of neighbours. After a qualitative a nalysis of several possible partitionings of the DIT FFT algorithm, a decomposition is introduced that has good scalability properties and m akes it possible to use sections of sequential code based on the most common 1D-FFT algorithms. If a computing architecture with indirect bi nary n-cube interconnection network is used, the proposed decompositio n guarantees strictly local communications and therefore requires no t hrough-routing support. These characteristics have a positive impact o n software development and also on overall performance. Furthermore, t hanks to a pipelined organization of the PEs, the resulting architectu re has high potentialities for real-time signal processing. As these u seful features are obtained at the 'expense' of an uneven workload dis tribution, computing efficiency is relatively low but does not signifi cantly change in a wide range of the number of processors. An implemen tation on a Transputer based system is presented along with the perfor mance results obtained. Finally a simple analytical model of the archi tecture is shown, that allows the values of the main performance param eters to be obtained as a function of the number of processors used an d of the elementary response times of the first stage of PEs.