EFFICIENT OVERLAPPED FFT ALGORITHMS FOR HYPERCUBE-CONNECTED MULTICOMPUTERS*
作者:
CEVDET AYKANAT,
ARGUN DERVIŞ,
期刊:
Parallel Algorithms and Applications
(Taylor Available online 1994)
卷期:
Volume 4,
issue 1-2
页码: 91-110
ISSN:1063-7192
年代: 1994
DOI:10.1080/10637199408915457
出版商: Taylor & Francis Group
关键词: hypercubc;multicomputer;overlapping communication and computation;parallel computing;perfect load balance;C.1.2;D.1.3;F.l.2;G.1.0;G.4
数据来源: Taylor
摘要:
In this work, we propose parallel FFT algorithms, for medium-to-coarse grain hypercube-connected multicomputers, which are more elegant and efficient than the existing ones. The proposed algorithms achieve perfect load-balance for the efficient simplified-butterfly scheme, minimize the communication overhead by decreasing both the number and the volume of concurrent communications. Communication and computation cannot be overlapped easily due to the strong data dependencies in the FFT algorithm. In this paper, we propose a restructuring for the FIT algorithm which enables overlapping each communication with one fifth of the local computations involved in a stage. Two of the proposed parallel FFT algorithms achieve overlapping by exploiting this restructuring while using the efficient table-lookup scheme for complex coefficients. The proposed algorithms are implemented on an Intel's 32-node iPSC/2 hypercube multicomputer. High efficiency values are obtained even for small size FFT problems.
点击下载:
PDF (409KB)
返 回