TY - GEN
T1 - On the scalability of FFT on parallel computers
AU - Gupta, Anshul
AU - Kumar, Vipin
PY - 1990
Y1 - 1990
N2 - The scalability of the parallel fast Fourier transform (FFT) algorithm on mesh- and hypercube-connected multicomputers is analyzed. The hypercube architecture provides linearly increasing performance for the FFT algorithm with an increasing number of processors and a moderately increasing problem size. However, there is a limit on the efficiency, which is determined by the communication bandwidth of the hypercube channels. Efficiencies higher than this limit can be obtained only if the problem size is increased very rapidly. Technology-dependent features, such as the communication bandwidth, determine the upper bound on the overall performance that can be obtained from a P-processor system. The upper bound can be moved up by either improving the communication-related parameters linearly or increasing the problem size exponentially. The scalability analysis shows that the FFT algorithm cannot make efficient use of large-scale mesh architectures. The addition of such features as cut-through routing and multicasting does not improve the overall scalability on this architecture.
AB - The scalability of the parallel fast Fourier transform (FFT) algorithm on mesh- and hypercube-connected multicomputers is analyzed. The hypercube architecture provides linearly increasing performance for the FFT algorithm with an increasing number of processors and a moderately increasing problem size. However, there is a limit on the efficiency, which is determined by the communication bandwidth of the hypercube channels. Efficiencies higher than this limit can be obtained only if the problem size is increased very rapidly. Technology-dependent features, such as the communication bandwidth, determine the upper bound on the overall performance that can be obtained from a P-processor system. The upper bound can be moved up by either improving the communication-related parameters linearly or increasing the problem size exponentially. The scalability analysis shows that the FFT algorithm cannot make efficient use of large-scale mesh architectures. The addition of such features as cut-through routing and multicasting does not improve the overall scalability on this architecture.
UR - http://www.scopus.com/inward/record.url?scp=0025549950&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0025549950&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:0025549950
SN - 0818620536
T3 - Proc 3 Symp Front Massively Parallel Comput Frontiers 90
SP - 69
EP - 74
BT - Proc 3 Symp Front Massively Parallel Comput Frontiers 90
PB - Publ by IEEE
T2 - Proceedings of the 3rd Symposium on the Frontiers of Massively Parallel Computation - Frontiers '90
Y2 - 8 October 1990 through 10 October 1990
ER -