{'fraction_non_alphanumeric': 0.03098927294398093, 'fraction_numerical': 0.017878426698450536, 'mean_word_length': 4.912195121951219, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Research on the realization and optimization of FFTs in ARMv8 platform

Fast Fourier transform (FFT) is a basic algorithm in digital signal processing and has been widely used in engineering, science and mathematical calculation. With the wide application of ARMv8 processor, it is more and more important to study FFT algorithm to realize high performance on ARMv8 platform. In the current open source FFT library, FFTW packages are mainly suitable for ARMv8 platform, while FFTW and FFTs packages are mainly suitable for ARMv7 platform. This paper implements and optimizes FFTs software package on ARMv8 platform, making it suitable for ARMv8 processor. The experimental results show that the performance of FFTs is improved by about 18% compared with FFTW in ARMv8 platform.


Introduction
At present, in the field of digital signal processing, DFT (Discrete 'Fourier Transform) is one of the most used the Discrete Transform algorithm, and FFT (Fast Fourier Transform) algorithm is a Fast algorithm of DFT algorithm, is widely used in digital communication, image processing, radar signal processing, aerospace and other fields [1].
In recent years, in the field of High Performance Computing (HPC), the computational performance and power consumption ratio and the performance-to-cost ratio have attracted much attention. ARM's ARMv8 architecture with its compared with traditional high performance processor in the whole of their own performance with low power consumption and higher superiority has been in the field of high performance computing, such as NVIDIA ARM IP core was used to construct the prototypes system, Barcelona is super center built Tibidabo proof-of-concept system [2], the system contains 256 computing nodes, each compute node has two ARM kernel, and the whole system peak of 512 Gflops double-precision floating-point operation theory.
At present, there are relatively few FFT algorithm libraries on ARMv8 platform. However, with the wide application of ARMv8 processor, it is increasingly important to study FFT algorithm to achieve high performance on ARMv8 platform. In the current open source FFT library, FFTW[3] software package is mainly suitable for ARMv8 platform, while FFTW and FFTs[4] software packages are mainly suitable for ARMv7 platform.
In this paper, FFTs software package is implemented and optimized on ARMv8 platform to make it suitable for ARMv8 processor. The experimental results show that the performance of FFTs is improved by about 18% compared with FFTW in ARMv8 platform. The main contributions of this paper are as follows: (1) This paper introduces the NEON intrinsic instruction function and assembly instruction related (2) FFTs of ARMv8 platform was implemented and its performance was compared with FFTW.

FFT algorithm principle
At present, FFT algorithms are relatively good, including Cooley-Tukey algorithm, prim-factor algorithm, Rader algorithm, split-radix algorithm, etc. [5][6]. This paper mainly introduces Cooley-Tukey FFT algorithm. In 1965, Cooley and Tukey [7] published the butterfly algorithm, using the branching strategy to reduce the DFT calculation time from the original ( 2 ) to ( 2 ), where N is the number of calculated data points.
In the field of digital signal processing, the Fourier transform of continuous time signal ( ) can be expressed as: The spectrum of continuous signal ( ) can be calculated by using discrete signal ( )， Where, ( )is the spectrum of time series ( ), and = − 2 is the rotation factor. For the time-domain sampling value of N points, N spectral points can be obtained through the calculation of formula (2), which is the discrete Fourier transform (DFT).

Introduction to FFTW and FFTs
The full name of FFTW is the fast Fourier Transform in the West, which is a standard C language assembly for fast calculation of discrete Fourier Transform. It can calculate one-dimensional or multidimensional real and complex data and discrete Fourier Transform of arbitrary scale, and supports input of arbitrary length and multidimensional data [5], which solves the problem of large FFT operation.
FFTW decompositions sequences of length N into short sequences of length N1 and N2 for calculation. These short sequences are computed by a series of highly optimized C code snippets called solvers, which are independent methods of solving transformations. Solvers are managed and combined by the planner to perform the calculations. A combination is called a plan, which is a data structure that contains the calculated change path and Pointers to all input and output arrays.
For the same length N, there are many ways to decompose it. Different combination paths have different effects on the operation speed, and their performance will vary under different machines and platforms. Therefore, it is necessary to determine which combination has the best effect. FFTW selects the plan with the fastest execution speed by evaluating various combinations. Record this plan, and use only the corresponding plan for every transformation of the same length in the future, so that FFTW can adapt to the optimal operating environment [8].
FFTs, also known as the Fastest Fourier Transform in the South, was developed by Anthony Blake of Waikato university in New Zealand in 2012 as an open source project on GitHub. FFTs supports x86, x64, arm and other platforms, but currently does not support Aarch64. The last commit was on June 18, 2017.

Development platform and compiler
The development platform is an ARMv8 64-bit processor with a frequency of 2.4GHz and 64GB memory. ARMv8 64-bit processor supports FMA (Fused-Multiply-and-Add) operation, the peak value of single core double precision operation is 9.6Gflops, and the peak value of single core single precision operation is 19.2GFlops.
Each CPU core has 32 128-bit floating-point vector registers, which can only enjoy L1 data Cache of 32KB and L1 instruction Cache of 32KB. Every two CPU cores share a L2 Cache with a size of 256KB, which is composed of a module with a total of 4 modules connected by high-speed interconnection. All modules share the 8MB L3 Cache through high-speed interconnection. The high speed interconnection provides access to memory through two DDR memory controllers. The relationship between L1, L2, and L3 caches is Inclusive.
The compiler is GNU C compiler GCC, version 8.3.0. This version provides the "-march=armv8-a" compilation option for software compilation for the armv8 64-bit processor platform. On the ARMv8 64-bit processor platform, GCC8.3.0 provides support for NEON intrinsic instruction functions, including single-precision and double-precision floating-point operations and other intrinsic instruction functions.

Optimization of FFTs on ARMv8 platform
According to discrete Fourier transform (DFT) formula (2), the essence of Fourier transform is matrix vector multiplication (GEMV) between rotation factor matrix and input vector, namely We know that matrix vector multiplication (GEMV) is very suitable for improving computing performance through SIMD instructions [9].
In general, the implementation of Cooley-Tukey FFT algorithm involves two key calculations: rotation factor generation and butterfly calculation.
In FFTs, when the length of the input signal sequence is less than 32, the generation of the rotation factor is based on the look-up table method. The values of each phase are put into the code in a hard-coded form to reduce the generation time of the rotation factor; when the length of the input sequence is greater than 32, combined with the symmetry and periodicity of the rotation factor, the calculated rotation factor is put into a mapping index for the butterfly calculation.
In the part of butterfly calculation, this paper does not modify the algorithm of FFTs itself, but only replaces the ARMv7 instruction in the original FFTs package by introducing the NEON intrinsic instruction function of ARMv8 and assembly instruction, and modifies the name of the corresponding register. The main differences between ARMv8 and ARMv7 are shown in table 2. , replace the ARMv7 instruction and register name in the above file with the corresponding Armv8 instruction and register name. For example, replace vadd.f32 in neon.s with vadd.f64, vsub.f32 with vsub.f64, and so on.

Performance test, precision comparison and analysis
Based on FFTs, this paper presents FFT for ARMv8 processor. Table 3 shows the detailed configuration of ARMv8 64-bit multi-core processor test platform. In this paper, the test results of FFTW library are taken as the benchmark. In order to evaluate the accuracy and performance of FFTs under different calculation scales, the length of input data N is selected from 2 to 134,217,728 for testing, and the input data is random Numbers in [-1,1] interval. Table 4~ Table 6 are the results of C2C calculation of test data for different dimensions of FFTW library. In the table, N represents data size, SP represents single-precision performance, and DP represents double-precision performance, the performance unit is MFlops.   1 show the performance diagrams of C2C calculation at one-dimensional input scales with single precision. From this figure, we can see that the single-precision performance of FFTs is generally higher than FFTW, with a maximum improvement of 18.35%. FIG. 1 show the performance diagrams of C2C calculation at one-dimensional input scales with double precision. From this figure, we can see that the double-precision performance of FFTs is generally higher than FFTW, with a maximum improvement of 7.34%.  2 show the performance diagrams of C2C calculation at two-dimensional input scales with single precision. From this figure, we can see that the single-precision performance of FFTs is generally higher than FFTW, with a maximum improvement of 11.35%. FIG. 2 show the performance diagrams of C2C calculation at two-dimensional input scales with double precision. From this figure, we can see that the double-precision performance of FFTs is generally higher than FFTW, with a maximum improvement of 6.87%.

Accuracy comparison
To compute the accuracy of an FFT, we compare the transform of uniform pseudorandom numbers in [-0.5,0.5) with the output of an arbitrary-precision arithmetic FFT (with > 40 decimal places of accuracy) [11]. The same random inputs are used for all transforms of the same size and type.

5.2.1.
Comparison of single-precision FFTs accuracy. As shown in table 7, for single-precision C2C calculation, the accuracy of FFTW and FFTs calculation results is on the order of 10 −7 if the one-dimensional input scale and data are consistent.

Conclusion
Based on FFTs, this paper implements a version on ARMv8 platform, and compares its performance and accuracy with FFTW library. FFTs has higher performance than FFTW.

Acknowledgments
Thanks to my girlfriend Hui Huang for her support and encouragement!