Implementation of Parallel
Number-Theoretic Transform
on Manycore Clusters
Daisuke Takahashi
Center for Computational Sciences
University of Tsukuba, Japan
2023/2/22

2022 CCS-KISTI Workshop

1Outline• Background• Objectives• Number-theoretic Transform (NTT)• Six-Step NTT Algorithm• Parallel Implementation of NTT• Performance Results• Conclusion

2023/2/22

2022 CCS-KISTI Workshop

2

Background• The fast Fourier transform (FFT) is an algorithm
that is widely used today in scientific andengineering computing.
• FFTs are often computed using complex or real
numbers, but it is known that these transforms
can also be computed in a ring and a finite field[Pollard 1971].
• Such a transform is called the number-theoretictransform (NTT).
• The NTT is used for homomorphic encryption,
polynomial multiplication, and multiple-precisionmultiplication.
2023/2/22

2022 CCS-KISTI Workshop

3

Related Works (1/2)• The number theory library (NTL) [Shoup et al.]is a C++ library for performing number-theoretic
computations and implements NTT.
– Although the NTL is thread-safe, the parallel NTT is notsupported.

• Spiral-generated modular FFTs have been
proposed [Meng et al. 2010 and 2013].
– Experiments were performed using 32-bit integers and16-bit primes with Intel SSE4 instructions.

2023/2/22

2022 CCS-KISTI Workshop

4

Related Works (2/2)• An implementation of NTT using the Intel
AVX-512IFMA (Integer Fused Multiply-Add)
instructions has been proposed [Boemer et al. 2021].
– This implementation is available as the Intel Homomorphic
Encryption (HE) Acceleration Library.
– Intel HEXL targets the typical data size 𝑛𝑛 = 210 , 217 ofNTTs used in homomorphic encryption and is notparallelized.

• An Implementation of Parallel Number-Theoretic
Transform Using Intel AVX-512 Instructions has been
proposed [Takahashi 2022].
– NTT kernels are vectorized using the Intel AVX-512
instructions.
– Six-step NTT is parallelized using OpenMP.

2023/2/22

2022 CCS-KISTI Workshop

5Objectives• We consider accelerating NTT for larger data
sizes by parallelization, targeting polynomial
multiplication and multiple-precision multiplication.
• We parallelize the six-step NTT using MPI andOpenMP.

2023/2/22

2022 CCS-KISTI Workshop

6Number-Theoretic Transform (NTT)• The number-theoretic transform (NTT) can be
expressed in a field 𝐅𝐅𝑝𝑝 = 𝐙𝐙/𝑝𝑝𝐙𝐙, where 𝑝𝑝 is a prime
number:𝑛𝑛−1

𝑗𝑗𝑗𝑗

𝑦𝑦 𝑘𝑘 = � 𝑥𝑥 𝑗𝑗 𝜔𝜔𝑛𝑛 mod 𝑝𝑝, 0 ≤ 𝑘𝑘 ≤ 𝑛𝑛 − 1,
𝑗𝑗=0in which 𝜔𝜔𝑛𝑛 is the primitive 𝑛𝑛-th root of unity.
• The 𝑛𝑛-point NTT is directly computed by 𝑂𝑂 𝑛𝑛2
arithmetic operations, but by applying an algorithm
similar to FFT, the number of arithmetic operations
can be reduced to 𝑂𝑂 𝑛𝑛 log 𝑛𝑛 .
2023/2/22

2022 CCS-KISTI Workshop

7

Stockham Radix-2 NTT Algorithm2023/2/22

2022 CCS-KISTI Workshop

8Modular Arithmetic in NTT• The butterfly operation of the NTT can be performed
using modular addition, subtraction, and multiplication.
• The modular addition 𝑐𝑐 = 𝑎𝑎 + 𝑏𝑏 mod 𝑁𝑁 for 0 ≤ 𝑎𝑎, 𝑏𝑏 <𝑁𝑁 can be replaced by the addition 𝑐𝑐 = 𝑎𝑎 + 𝑏𝑏 and theconditional subtraction 𝑐𝑐 − 𝑁𝑁 when 𝑐𝑐 ≥ 𝑁𝑁.
• Modular multiplication includes modulo operations,which are slow due to the integer division process.
• However, Montgomery multiplication[Montgomery 1985] and Shoup’s modularmultiplication [Harvey 2014] are known to avoid thisproblem.
2023/2/22

2022 CCS-KISTI Workshop

9

Shoup’s Modular Multiplication
Algorithm [Harvey 2014]

The upper half of 𝐴𝐴𝐴𝐴𝐴

Subtraction of the lower half of
𝑞𝑞𝑞𝑞 from the lower half of 𝐴𝐴𝐴𝐴

2023/2/22

2022 CCS-KISTI Workshop

10Six-Step NTT Algorithm• If 𝑛𝑛 has factors 𝑛𝑛1 and 𝑛𝑛2 (𝑛𝑛 = 𝑛𝑛1 × 𝑛𝑛2 ), in thesame way as the six-step FFT algorithm[Bailey 1990], the following six-step NTT algorithm[Takahashi 2022] is derived:• Step 1: Transposition• Step 2: 𝑛𝑛1 individual 𝑛𝑛2 -point multicolumn NTTs
𝑗𝑗1 𝑘𝑘2
Step 3: Twiddle factor (𝜔𝜔𝑛𝑛 ) multiplication•• Step 4: Transposition• Step 5: 𝑛𝑛2 individual 𝑛𝑛1 -point multicolumn NTTs
• Step 6: Transposition
2023/2/22

2022 CCS-KISTI Workshop

11Parallel NTT Algorithm Based onSix-StepNTT
𝑁𝑁
2

𝑁𝑁1𝑃𝑃0𝑃𝑃1𝑃𝑃2 𝑃𝑃3

𝑁𝑁1GlobalTranspose

𝑁𝑁2 𝑃𝑃0 𝑃𝑃1 𝑃𝑃2 𝑃𝑃32023/2/22

𝑁𝑁1

𝑁𝑁2

GlobalTranspose

𝑁𝑁12022 CCS-KISTI Workshop

Perform
twiddle factor
𝐽𝐽 𝐾𝐾(𝜔𝜔𝑁𝑁1 2 )multiplication

𝑁𝑁2

GlobalTranspose

12

Parallelization of Six-Step NTT/* Step 1: transpose nx*ny to ny*nx */#pragma omp parallel for collapse(2) private(i, k)for (j = 0; j < nny; j++)for (k = 0; k < nproc; k++)for (i = 0; i < nnx; i++)b[i + j * nnx + k * (nnx * nny)] = a[i + k * nnx + j * (nnx * nproc)];
MPI_Alltoall(b, nn / nproc, MPI_UNSIGNED_LONG_LONG, a, nn / nproc,
MPI_UNSIGNED_LONG_LONG, MPI_COMM_WORLD);
trans(a, b, nnx, ny);/* Step 2: (nx / nproc) individual ny-point multicolumn NTTs */#pragma omp parallel forfor (j = 0; j < nnx; j++)nttsub(&b[j * ny], &a[j * ny], wy, wwy, ny, ipy, np);…
2023/2/22

2022 CCS-KISTI Workshop

13Performance Results• For performance evaluation, we measure the performanceof the proposed implementation of the six-step NTT with amodulus of 63 bits.
• The performance was measured on the Fujitsu
PRIMEHPC FX1000 at the University of Tokyo.
– 7680 nodes, Peak 25.9 PFlops– CPU: A64FX (48 cores + assistant 2 or 4 cores, 2.2 GHz)– Interconnect: Tofu interconnect D (Link bandwidth 6.8 GB/s)– Compiler: Fujitsu C/C++ Compiler 4.8.1– Compiler option: “-Nclang -Kfast -Kopenmp”• Each MPI process has 12 cores and 12 threads,i.e., 4 MPI processes per node.
• The giga-operations per second (Gops) values are eachbased on 3/2 𝑁𝑁 log 2 𝑁𝑁 for a transform of size 𝑁𝑁 = 2𝑚𝑚 .
2023/2/22

2022 CCS-KISTI Workshop

14Performance of Parallel NTTs
(𝑁𝑁 = 226 × MPI processes)

10000

Gops

1000

100

1011248163264 128 256
Number of MPI processes

512 1024 2048 4096

Proposed
2023/2/22

2022 CCS-KISTI Workshop

15

Discussion• The reason for the smaller performance growth when
the number of MPI processes is increased from 4 to 8
is that up to 4 MPI processes are communicating
within the node.
• For 238 -point NTT on 4096 MPI processes,
approximately 80% of the execution time is taken upby all-to-all communication.
• The Fujitsu PRIMEHPC FX1000 uses Tofuinterconnect D, a 6-dimensional torus network, but as
the number of nodes increases, the maximum
number of hops also increases, resulting in lower allto-all communication bandwidth.
2023/2/22

2022 CCS-KISTI Workshop

16

0.7

Performance of MPI_Alltoall(Fujitsu PRIMEHPC FX1000,1024 nodes, 4096 MPI processes)0.6

GB/s

0.5
0.4
0.3
0.2
0.108

163264128 256 512 1K 2K 4K
Message size (bytes)

8K 16K 32K 64K 128K

MPI_Alltoall
2023/2/22

2022 CCS-KISTI Workshop

17Conclusion• We proposed an implementation of the parallel
NTT on manycore clusters.
• The butterfly operation of the NTT can be
performed using modular addition, subtraction,and multiplication.
• We parallelized the six-step NTT using MPI andOpenMP.
• We successfully achieved a performance of over4831 Gops on a Fujitsu Supercomputer
PRIMEHPC FX1000 (1024 nodes) for a 238 -pointNTT with a modulus of 63 bits.
2023/2/22

2022 CCS-KISTI Workshop

18