heFFTe: Scaling FFT for Exascale

By Jack Dongarra and Stanimire Tomov

July 15, 2020

In this contributed feature, Jack Dongarra (Director of the Innovative Computing Laboratory at The University of Tennessee) and Stanimire Tomov (Research Director in the Innovative Computing Laboratory) introduce their work on the heFFTe (Highly Efficient FFT for Exascale) library, which they are developing in preparation for the coming class of exascale supercomputers.

Exascale computing aspires to provide breakthrough solutions addressing today’s most critical challenges in scientific discovery, energy assurance, economic competitiveness, and national security. This has been the main target of the US Department of Energy (DOE) Exascale Computing Initiative (ECI). Formed in 2016, ECI aims to accelerate research, development, acquisition, and deployment projects to deliver exacale-computing capability to the DOE labs by the early to mid 2020s. ECI’s main component, the Exascale Computing Project (ECP), was launched to bring together research, development, and deployment activities as part of a capable exascale computing ecosystem to ensure an enduring exascale computing capability for the nation.

Exascale computing aims to meet the increasing demands from large scientific applications. Software targeting exascale is typically designed for heterogeneous architectures; henceforth, it is not only important to develop well-designed software, but also make it aware of the hardware architecture and efficiently exploit its power. Currently, several ECP applications rely on efficient computation of the Fast Fourier Transform (FFT); thus, one of the ECP-supported software technology efforts is the design and implementation of a Highly Efficient FFT for Exascale (heFFTe) library that targets the upcoming exascale supercomputers.

FFT LIBRARIES

Considered one of the top 10 algorithms of the 20th century, the FFT is widely used by applications in science and engineering. This includes applications and diverse numerical software ranging from molecular dynamics to spectrum estimation, fast convolution and correlation, signal modulation, wireless multimedia applications, and machine learning. For all these applications, it is critical to have access to a heterogeneous, fast and scalable parallel FFT library, with an implementation that can take advantage of novel hardware components, and efficiently exploit their benefits.

Highly efficient implementations to compute FFT on a single node have been developed for a long time. One of the most widely used libraries is FFTW, which has been tuned to optimally perform in several architectures. Vendor libraries for this purpose have also been highly optimized; such is the case of MKL (Intel), ESSL (IBM), CUFFT (NVIDIA) and clFFT (AMD). Novel libraries are also being developed to further optimize single node FFT computation, e.g., FFTX. Most of the previous libraries have been extended to distributed-memory versions, some by the original developers, and others by different authors.

However, the current state-of-the-art FFT libraries are not scalable on large heterogeneous machines with many nodes or even on one node with multiple high-performance GPUs. Furthermore, these libraries require large FFTs in order to deliver acceptable performance on one GPU. Efforts to simply enhance classical and existing FFT packages with optimization tools and techniques—like autotuning and code generation—have so far not been able to provide the efficient, high-performance FFT library capable of harnessing the power of supercomputers with heterogeneous GPU-accelerated nodes. In particular, ECP applications that require FFT-based solvers might suffer from the lack of fast and scalable 3-D FFT routines for distributed heterogeneous parallel systems, which is the very type of system that will be used in upcoming Exascale machines.

heFFTe METHODOLOGY AND ALGRORITHMIC DESIGN

HeFFTe (pronounced “hefty”), provides very good (linear) scalability for large node count. It is open-source and consists of C++ and CUDA kernels with (CUDA-aware) MPI and OpenMP interface for communication. It has a user-friendly interface and does not require any commercial compiler. Wrappers to interface with C, Fortran and Python are available. Its main objective is to become the standard for large FFT computations on the upcoming exascale systems. Fig. 1 shows how heFFTe is positioned on the ECP software stack, and some of its target exascale applications (gray boxes).

Fig. 1. heFFTe in ECP software stack.

Multidimensional FFTs can be performed by a sequence of low-dimensional FFTs. Typical approaches used by parallel libraries are the “pencil” and “slab” decompositions. Fig. 2 illustrates the pencil decomposition approach, which computes 3D FFTs by means of three batched 1D FFTs. The original domain is given on the left, spread on a 4x3x3 processor grid. Next is a communication step that redistributes the domain into 1D vectors (pencils) spreading entirely through one of the (3D) directions. Then, in parallel, each processor performs 1D FFTs on the pencils that it holds, followed by communication to form pencils in the next direction, 1D FFTs for that direction, repeat the same for the last direction, followed by final domain redistribution to the original domain.  On the other hand, slab decomposition relies on computing sets of 2D and 1D FFTs.

Fig. 2. Schematic view of a 3D FFT with pencil decomposition using 4x3x3 processor grid.

Communications at Exascale

The current bottleneck for many applications is communication costs. On the Summit pre-exascale supercomputer at ORNL for example, a computational node can perform about 13,440 double precision floating-point (FP64) operations for the time it can receive (or send) a single FP64 value. Thus, if an algorithm does not perform about 13,440 operations per value sent (or received), the node will idle, waiting for data. The FFT does not provide this high value of data reuse. In fact, for a vector of size N, the number of FFT floating point operations is only O(N log2N), making FFTs memory-bound operations. A typical profile is shown on Figure 3, Right, where the MPI communications take more than 97% of the total time. A corresponding run on multi-core CPUs is given on Figure 3, Left. The local FFT operations are memory bound and take about 50% of the time. The other 50% are in MPI communications. heFFTe accelerates the local operations 43× using GPUs. However, MPI communications remained about the same, using CUDA-Aware MPI doing GPUDirect communication.

Fig. 3. Profile of a 3D FFT of size 10243 on 4 CPU Summit nodes – using 128 MPI processes, 32 MPIs per node, 16 MPIs per socket (Left) and 4 GPU Summit nodes – using 24 MPI processes, 6 MPIs per node, 3 MPI per socket, 1 GPU per MPI (Right).

Scalable Performance 

Fig. 4 illustrates the strong (Left) and weak (Right) scalability of heFFTe, also compared to the FFTE library. HeFFTe overcomes FFTE in performance by a factor of two and has better scalability. Scalability is very important for large-scale systems. In the strong scaling, the same problem is solved on increasing number of nodes, and the time to solution is ideally supposed to go down, proportional to the compute resources used. In weak scaling, both problem sizes and compute resources are proportionally increased, so ideally the time to solution will be a flat line, e.g., as achieved by heFFTe on Fig. 4, Right.

Fig. 4. Strong scalability for a 10243 FFT (left), and weak scalability comparison (right) on Summit pre-exascale supercomputer.

Read the full paper, published in Computational Science – ICCS 2020, to learn more about heFFTe, its performance on current supercomputers and use in ECP applications.

 

Subscribe to HPCwire's Weekly Update!

Be the most informed person in the room! Stay ahead of the tech trends with industy updates delivered to you every week!

HPC Career Notes: October 2020 Edition

October 1, 2020

In this monthly feature, we'll keep you up-to-date on the latest career developments for individuals in the high-performance computing community. Whether it's a promotion, new company hire, or even an accolade, we've got Read more…

By Mariana Iriarte

David Patterson Kicks Off AI Hardware Summit Championing Domain Specific Chips

September 30, 2020

The 2020 AI Hardware Summit kicked off yesterday with long-time computer luminary David Patterson digging into all things TPU and extolling on how they outrun GPUs for AI needs. After presenting data in which the TPUv3 b Read more…

By John Russell

D-Wave Delivers 5000-qubit System; Targets Quantum Advantage

September 29, 2020

D-Wave today launched its newest and largest quantum annealing computer, a 5000-qubit goliath named Advantage that features 15-way qubit interconnectivity. It also introduced the D-Wave Launch program intended to jump st Read more…

By John Russell

What’s New in Computing vs. COVID-19: AMD, Remdesivir, Fab Spending & More

September 29, 2020

Supercomputing, big data and artificial intelligence are crucial tools in the fight against the coronavirus pandemic. Around the world, researchers, corporations and governments are urgently devoting their computing reso Read more…

By Oliver Peckham

Global QC Market Projected to Grow to More Than $800 million by 2024

September 28, 2020

The Quantum Economic Development Consortium (QED-C) and Hyperion Research are projecting that the global quantum computing (QC) market - worth an estimated $320 million in 2020 - will grow at an anticipated 27% CAGR betw Read more…

By Staff Reports

AWS Solution Channel

EFA-enabled C5n instances to scale Simcenter STAR-CCM+

For HPC workloads that use multiple nodes, the cluster setup including the network is at the heart of scalability concerns. Some of the most common concerns from CFD or HPC engineers are “how well will my application scale on AWS?”, “how do I optimize the associated costs for best performance of my application on AWS?”, “what are the best practices in setting up an HPC cluster on AWS to reduce the simulation turn-around time and maintain high efficiency?”. Read more…

Intel® HPC + AI Pavilion

Berlin Institute of Health: Putting HPC to Work for the World

Researchers from the Center for Digital Health at the Berlin Institute of Health (BIH) are using science to understand the pathophysiology of COVID-19, which can help to inform the development of targeted treatments. Read more…

DoE’s ASCAC Backs AI for Science Program that Emulates the Exascale Initiative

September 28, 2020

Roughly a year after beginning formal efforts to explore an AI for Science initiative the Department of Energy’s Advanced Scientific Computing Advisory Committee last week accepted a subcommittee report calling for a t Read more…

By John Russell

David Patterson Kicks Off AI Hardware Summit Championing Domain Specific Chips

September 30, 2020

The 2020 AI Hardware Summit kicked off yesterday with long-time computer luminary David Patterson digging into all things TPU and extolling on how they outrun G Read more…

By John Russell

D-Wave Delivers 5000-qubit System; Targets Quantum Advantage

September 29, 2020

D-Wave today launched its newest and largest quantum annealing computer, a 5000-qubit goliath named Advantage that features 15-way qubit interconnectivity. It a Read more…

By John Russell

DoE’s ASCAC Backs AI for Science Program that Emulates the Exascale Initiative

September 28, 2020

Roughly a year after beginning formal efforts to explore an AI for Science initiative the Department of Energy’s Advanced Scientific Computing Advisory Commit Read more…

By John Russell

NOAA Announces Major Upgrade to Ensemble Forecast Model, Extends Range to 35 Days

September 23, 2020

A bit over a year ago, the United States’ Global Forecast System (GFS) received a major upgrade: a new dynamical core – its first in 40 years – called the finite-volume cubed-sphere, or FV3. Now, the National Oceanic and Atmospheric Administration (NOAA) is bringing the FV3 dynamical core to... Read more…

By Oliver Peckham

Arm Targets HPC with New Neoverse Platforms

September 22, 2020

UK-based semiconductor design company Arm today teased details of its Neoverse roadmap, introducing V1 (codenamed Zeus) and N2 (codenamed Perseus), Arm’s second generation N-series platform. The chip IP vendor said the new platforms will deliver 50 percent and 40 percent more... Read more…

By Tiffany Trader

Oracle Cloud Deepens HPC Embrace with Launch of A100 Instances, Plans for Arm, More 

September 22, 2020

Oracle Cloud Infrastructure (OCI) continued its steady ramp-up of HPC capabilities today with a flurry of announcements. Topping the list is general availabilit Read more…

By John Russell

European Commission Declares €8 Billion Investment in Supercomputing

September 18, 2020

Just under two years ago, the European Commission formalized the EuroHPC Joint Undertaking (JU): a concerted HPC effort (comprising 32 participating states at c Read more…

By Oliver Peckham

Google Hires Longtime Intel Exec Bill Magro to Lead HPC Strategy

September 18, 2020

In a sign of the times, another prominent HPCer has made a move to a hyperscaler. Longtime Intel executive Bill Magro joined Google as chief technologist for hi Read more…

By Tiffany Trader

Supercomputer-Powered Research Uncovers Signs of ‘Bradykinin Storm’ That May Explain COVID-19 Symptoms

July 28, 2020

Doctors and medical researchers have struggled to pinpoint – let alone explain – the deluge of symptoms induced by COVID-19 infections in patients, and what Read more…

By Oliver Peckham

Nvidia Said to Be Close on Arm Deal

August 3, 2020

GPU leader Nvidia Corp. is in talks to buy U.K. chip designer Arm from parent company Softbank, according to several reports over the weekend. If consummated Read more…

By George Leopold

Intel’s 7nm Slip Raises Questions About Ponte Vecchio GPU, Aurora Supercomputer

July 30, 2020

During its second-quarter earnings call, Intel announced a one-year delay of its 7nm process technology, which it says it will create an approximate six-month shift for its CPU product timing relative to prior expectations. The primary issue is a defect mode in the 7nm process that resulted in yield degradation... Read more…

By Tiffany Trader

Google Hires Longtime Intel Exec Bill Magro to Lead HPC Strategy

September 18, 2020

In a sign of the times, another prominent HPCer has made a move to a hyperscaler. Longtime Intel executive Bill Magro joined Google as chief technologist for hi Read more…

By Tiffany Trader

10nm, 7nm, 5nm…. Should the Chip Nanometer Metric Be Replaced?

June 1, 2020

The biggest cool factor in server chips is the nanometer. AMD beating Intel to a CPU built on a 7nm process node* – with 5nm and 3nm on the way – has been i Read more…

By Doug Black

HPE Keeps Cray Brand Promise, Reveals HPE Cray Supercomputing Line

August 4, 2020

The HPC community, ever-affectionate toward Cray and its eponymous founder, can breathe a (virtual) sigh of relief. The Cray brand will live on, encompassing th Read more…

By Tiffany Trader

Neocortex Will Be First-of-Its-Kind 800,000-Core AI Supercomputer

June 9, 2020

Pittsburgh Supercomputing Center (PSC - a joint research organization of Carnegie Mellon University and the University of Pittsburgh) has won a $5 million award Read more…

By Tiffany Trader

European Commission Declares €8 Billion Investment in Supercomputing

September 18, 2020

Just under two years ago, the European Commission formalized the EuroHPC Joint Undertaking (JU): a concerted HPC effort (comprising 32 participating states at c Read more…

By Oliver Peckham

Leading Solution Providers

Contributors

Oracle Cloud Infrastructure Powers Fugaku’s Storage, Scores IO500 Win

August 28, 2020

In June, RIKEN shook the supercomputing world with its Arm-based, Fujitsu-built juggernaut: Fugaku. The system, which weighs in at 415.5 Linpack petaflops, topp Read more…

By Oliver Peckham

Google Cloud Debuts 16-GPU Ampere A100 Instances

July 7, 2020

On the heels of the Nvidia’s Ampere A100 GPU launch in May, Google Cloud is announcing alpha availability of the A100 “Accelerator Optimized” VM A2 instance family on Google Compute Engine. The instances are powered by the HGX A100 16-GPU platform, which combines two HGX A100 8-GPU baseboards using... Read more…

By Tiffany Trader

DOD Orders Two AI-Focused Supercomputers from Liqid

August 24, 2020

The U.S. Department of Defense is making a big investment in data analytics and AI computing with the procurement of two HPC systems that will provide the High Read more…

By Tiffany Trader

Microsoft Azure Adds A100 GPU Instances for ‘Supercomputer-Class AI’ in the Cloud

August 19, 2020

Microsoft Azure continues to infuse its cloud platform with HPC- and AI-directed technologies. Today the cloud services purveyor announced a new virtual machine Read more…

By Tiffany Trader

Supercomputer Modeling Tests How COVID-19 Spreads in Grocery Stores

April 8, 2020

In the COVID-19 era, many people are treating simple activities like getting gas or groceries with caution as they try to heed social distancing mandates and protect their own health. Still, significant uncertainty surrounds the relative risk of different activities, and conflicting information is prevalent. A team of Finnish researchers set out to address some of these uncertainties by... Read more…

By Oliver Peckham

Japan’s Fugaku Tops Global Supercomputing Rankings

June 22, 2020

A new Top500 champ was unveiled today. Supercomputer Fugaku, the pride of Japan and the namesake of Mount Fuji, vaulted to the top of the 55th edition of the To Read more…

By Tiffany Trader

Joliot-Curie Supercomputer Used to Build First Full, High-Fidelity Aircraft Engine Simulation

July 14, 2020

When industrial designers plan the design of a new element of a vehicle’s propulsion or exterior, they typically use fluid dynamics to optimize airflow and in Read more…

By Oliver Peckham

Intel Speeds NAMD by 1.8x: Saves Xeon Processor Users Millions of Compute Hours

August 12, 2020

Potentially saving datacenters millions of CPU node hours, Intel and the University of Illinois at Urbana–Champaign (UIUC) have collaborated to develop AVX-512 optimizations for the NAMD scalable molecular dynamics code. These optimizations will be incorporated into release 2.15 with patches available for earlier versions. Read more…

By Rob Farber

  • arrow
  • Click Here for More Headlines
  • arrow
Do NOT follow this link or you will be banned from the site!
Share This