A node-based approach to charm-FFT

Lee, Dong Hun

Permalink

https://hdl.handle.net/2142/102849 Copy

Description

Title

A node-based approach to charm-FFT

Author(s)

Lee, Dong Hun

Issue Date

2018-12-10

Director of Research (if dissertation) or Advisor (if thesis)

Kalé, Laxmikant V

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

M.S.

Degree Level

Thesis

Keyword(s)

• Charm-FFT
• Parallel 3D FFT

Abstract

Parallel 3D Fast Fourier Transform is a communication intensive algorithm that suffers from the unignorable communication overhead. Because the interconnect communication bandwidth is a static component, adjustments to reduce or hide the necessary communication overheads are performed to obtain the optimal performance with a FFT grid in a given environment. In this thesis, an alternative method to an existing Parallel 3D FFT library was explored. The FFT library, Charm-FFT empowered by Charm++, was redesigned to utilize larger number of nodes while aiming to reduce the number of necessary communications between its components during its computations. Instead of decomposing the input FFT grid into the fine-grained objects that are distributed to the available PEs, coarser-grained decomposition method that only distributes to the available nodes was applied. As there are less number of receivers that each decomposed object communicates during the state transposition, the overall number of communication is reduced at the cost of parallelism from using the finer decomposition method. This loss of parallelism is attempted to be mitigated by applying within-node parallelism using multi-threading or accelerators. Lastly, to maintain the usability of the modified library when multiple FFT grid computations are needed with given resource, each FFT grid is assigned to a subset of the resource to compute and communicate only within its subset rather than to use all resource for each grid's computation.

Graduation Semester

2018-12

Type of Resource

text

Permalink

http://hdl.handle.net/2142/102849

Copyright and License Information

Copyright 2018 Dong Hun Lee

Owning Collections