A node-based approach to charm-FFT

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.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2019

Author dc:creator

• Lee, Dong Hun

Contributors dc:contributor

• Kalé, Laxmikant V

• Charm-FFT
• Parallel 3D FFT

Statement dc:rights

• Copyright 2018 Dong Hun Lee

Language dc:language

en

Handle dc:identifier

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

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/102849