Asee peer logo

Investigating Communication Patterns for Distributed Fast Fourier Transforms

Download Paper |

Conference

2019 ASEE Annual Conference & Exposition

Location

Tampa, Florida

Publication Date

June 15, 2019

Start Date

June 15, 2019

End Date

October 19, 2019

Conference Session

Computing Research II

Tagged Division

Computing and Information Technology

Page Count

14

DOI

10.18260/1-2--33024

Permanent URL

https://strategy.asee.org/33024

Download Count

194

Request a correction

Paper Authors

biography

Afrin Naz West Virginia University Institute of Technology.

visit author page

Dr. Afrin Naz is an assistant professor at the Computer Science and Information Systems department at West Virginia University Institute of Technology. She is working with high school teachers to inspire the K-12 students to the STEM fields. In last four years Dr. Naz and her team launched six workshops for high school teachers. Currently her team is training the high school teachers to offer online materials to supplement their face-to-face classroom.

visit author page

biography

Mardigon Max Toler West Virginia University Institute of Technology

visit author page

Mardigon Toler is a student of Computer Science and Mathematics at West Virginia University Institute of Technology, finishing a bachelor's degree in both fields in spring 2019. His interests include digital audio, digital signal processing, and distributed and parallel computing. His past projects have included applications of AI to real-time music accompaniment as well as real-time software-based audio synthesis using Fourier transforms.

visit author page

Download Paper |

Abstract

In this paper, we analyze the effectiveness of different communication patterns for performing a 1-dimensional Fast Fourier Transform on distributed memory computing clusters. The experimental communication pattern is intended to minimize time wasted by participant nodes being inactive during computation. Fast Fourier Transforms are a very computationally efficient signal processing technique for calculating the Discrete Fourier Transform of a complex-valued sequence of discrete samples. This Discrete Fourier Transform can be interpreted as a new signal that represents the original signal’s frequency content. Thus, they find the frequency components that make up a signal. Distributed memory computers are clusters of computers that may all work on a task simultaneously by passing relevant information about the problem’s current state to one another. They are suitable for highly parallelizable routines such as the Fast Fourier Transform, in which the different parts of the input data can be operationally isolated at predictable moments in time, allowing many different computers to independently work on these parts in parallel, ideally reducing the total running time of the algorithm. However, there are many ways that this algorithm can be parallelized. Of particular importance is the way information is initially distributed across the machines and the pattern that the machines use to communicated with each other and collect a final result on a host machine. We describe how these communication patterns differ and discuss details of their implementation. In addition, data will be presented that illustrates how these implementations differ on two different clusters.

Naz, A., & Toler, M. M. (2019, June), Investigating Communication Patterns for Distributed Fast Fourier Transforms Paper presented at 2019 ASEE Annual Conference & Exposition , Tampa, Florida. 10.18260/1-2--33024

ASEE holds the copyright on this document. It may be read by the public free of charge. Authors may archive their work on personal websites or in institutional repositories with the following citation: © 2019 American Society for Engineering Education. Other scholars may excerpt or quote from these materials with the same citation. When excerpting or quoting from Conference Proceedings, authors should, in addition to noting the ASEE copyright, list all the original authors and their institutions and name the host city of the conference. - Last updated April 1, 2015