CaltechAUTHORS
  A Caltech Library Service

Two approaches to the concurrent implementation of the prime factor algorithm on a hypercube

Aloisio, G. and Lopinto, E. and Veneziani, N. and Fox, G. C. and Kim, J. S. (1991) Two approaches to the concurrent implementation of the prime factor algorithm on a hypercube. Concurrency: Practice and Experience, 3 (5). pp. 483-495. ISSN 1040-3108. https://resolver.caltech.edu/CaltechAUTHORS:20180330-132951062

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20180330-132951062

Abstract

On sequential computers, the prime factor algorithm (PFA) allows the Computation of the discrete Fourier transform (DFT) with a higher efficiency than the traditional Cooley‐Tukey FFT algorithm (CTA). However, the PFA requires substantial data movement, which poses a challenging problem for distributed‐memory multi‐processor systems. In this paper, two approaches for a concurrent implementation of the PFA on these structures are presented. In the first approach, the concurrent PFA runs on all nodes of the multi‐processor system, which is inefficient on large configurations due to the large communication overhead. A second approach developed to reduce this bottleneck is also presented. These solutions have been benchmarked on Caltech hypercubes, and the performances achieved are reported. In both approaches, the crystal_router algorithm was exploited as a concurrent technique for communicating data among nodes.


Item Type:Article
Related URLs:
URLURL TypeDescription
https://doi.org/10.1002/cpe.4330030503DOIArticle
https://onlinelibrary.wiley.com/doi/abs/10.1002/cpe.4330030503PublisherArticle
Additional Information:© 1991 John Wiley & Sons, Ltd. Manuscript revised: 22 March 1991; Manuscript received: 10 August 1989. Funding Information: Italian Space Agency. Grant Numbers: ASI‐90‐RS‐69, ASI‐90‐RS‐102.
Funders:
Funding AgencyGrant Number
Agenzia Spaziale Italiana (ASI)ASI-90-RS-69
Agenzia Spaziale Italiana (ASI)ASI-90-RS-102
Issue or Number:5
Record Number:CaltechAUTHORS:20180330-132951062
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20180330-132951062
Official Citation:Aloisio, G. , Lopinto, E. , Veneziani, N. , Fox, G. C. and Kim, J. S. (1991), Two approaches to the concurrent implementation of the prime factor algorithm on a hypercube. Concurrency: Pract. Exper., 3: 483-495. doi:10.1002/cpe.4330030503
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:85538
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:30 Mar 2018 21:40
Last Modified:03 Oct 2019 19:32

Repository Staff Only: item control page