# Research on High-Performance Fourier Transform Algorithms Based on the NPU
## 1 Introduction  
Smart wearable devices are playing an increasingly important role in the application scenario of field special operations. Among these devices, the backpack computer serves as the \"central nervous system\" for edge intelligence in the wearable device group. It collects a variety of measurement data from multiple devices, such as smartwatches, glasses, belts, helmets, and wristbands, for centralized processing. This organizational approach follows the edge computing paradigm [1, 2]. Consequently, the backpack computer requires high computing power to accelerate scientific calculations or intelligent inference. One common strategy to meet that need is the incorporation of additional hardware, such as graphics processing units (GPUs) or field programmable gate arrays (FPGAs). However, due to the limited size and battery capacity of backpack computers, adding extra hardware leads to adverse effects, including increased heat generation and reduced battery life. The system-on-chip (SoC) with high sampling performance emerges as the optimal solution that effectively balances performance and power consumption. For intelligent wearable applications, however, most on-chip GPUs currently exhibit poor compatibility with mainstream intelligent computing frameworks. Additionally, incorporating an external FPGA for intelligent inference is only suitable for specialized applications and presents challenges in development. Fortunately, SoC-containing NPUs have been developed rapidly in recent years, driven by the flourishing of smartphones [3, 4]. In intelligent applications, NPUs boost the computational speed of matrix and vector operations through data parallelism [5, 6]. This not only substantially accelerates intelligent inference but alsoenhances energy efficiency. Therefore, for most intelligent computing scenarios, the CPU + NPU architecture is sufficient and does not require additional heterogeneous computing hardware units [7; 8; 9; 10]. The computational demands for intelligent applications may not always be adequately addressed in the calculation phase of intelligent inference, as numerous data preprocessing tasks often require high computing power as well. In various application scenarios of wearable devices, such as heart rate estimation [11] and human activity recognition [12], it is necessary to apply the Fourier Transform (FT) to convert sensor sampling data from the time-domain signals into the frequency-domain signals before performing intelligent inference. Moreover, the two-dimensional Fourier Transform has been widely used in edge intelligence scenarios such as road object detection [13] and stroke detection [14]. With the advancement in signal sampling rate and resolution, the computational consumption of the FT has notably increased, especially for image Fourier Transforms. For a backpack computer with CPU + NPU architecture, executing two-dimensional or high-dimensional Fourier Transforms with CPUs can result in declines in real-time signal processing performance, potentially leading to performance bottlenecks in computing. Therefore, it is crucial to prioritize the research of accelerating FT on NPUs. Migrating existing FT algorithms directly to NPUs is infeasible due to the distinctive hardware architecture of NPUs. This is because the matrix and vector units of NPUs process data blocks in a serial manner, while GPUs and FPGAs process bytes with multiple threads in parallel [15]. Consequently, the conventional fast FT algorithm may not be suitable for NPUs. To address this issue, this paper investigates the design of acceleration algorithms for Fourier Transform utilizing NPU's distinctive architecture. It aims to explore the applicability of NPU in typical algorithms that preprocess data for AI and to identify methods for enhancing NPU efficiency. Two novel NPU algorithms are designed and implemented: the direct matrix multiplication-based DFT algorithm (MM-2 DFT) and the matrix-vector iterative operation-based Fast Fourier Transform (FFT) algorithm (MV-2 FFT).