Fast Fourier transform (FFT) is the kernel and the most time-consuming algorithm in the domain of digital signal processing, and the FFT sizes of different applications are very different. Therefore, this paper proposes a variable-size FFT hardware accelerator, which fully supports the IEEE-754 single-precision floating-point standard and the FFT calculation with a wide size range from 2 to 2²⁰ points. First, a parallel Cooley-Tukey FFT algorithm based on matrix transposition (MT) is proposed, which can efficiently divide a large size FFT into several small size FFTs that can be executed in parallel. Second, guided by this algorithm, the FFT hardware accelerator is designed, and several FFT performance optimization techniques such as hybrid twiddle factor generation, multibank data memory, block MT, and token-based task scheduling are proposed. Third, its VLSI implementation is detailed, showing that it can work at 1 GHz with the area of 2.4 mm² and the power consumption of 91.3 mW at 25 $°C, 0.9 V. Finally, several experiments are carried out to evaluate the proposal's performance in terms of FFT execution time, resource utilization, and power consumption. Comparative experiments show that our FFT hardware accelerator achieves at most 18.89$x$ speedups in comparison to two software-only solutions and two hardware-dedicated solutions.

Matrix transposition plays a critical role in digital signal processing. However, existing matrix transposition implementations have significant limitations. A traditional design uses load and store instructions to accomplish matrix transposition. Depending on the amount of load/store units, this design typically transposes up to one matrix element per clock cycle. More seriously, this design cannot perform matrix transposition and data calculations in parallel. Modern digital signal processors (DSPs) integrate the support for matrix transposition into the direct memory access (DMA) controller; the matrix can be transposed during data movements. It allows the parallel execution of matrix transposition and data calculations. Yet, its bandwidth utilization is limited; it can only transfer one matrix element per clock cycle. To address the limitations of existing designs, we propose MT-DMA, to support efficient matrix transposition in DMA controllers. It can transpose multiple matrix elements per clock cycle to improve the bandwidth utilization. Compared with existing designs, MT-DMA achieves a maximum 23.9 times performance improvement for micro-benchmarks. It is also more energy efficient. Since MT-DMA effectively hides the latency of matrix transposition behind data calculations, it performs very closely to an ideal design for real applications.

CORDIC algorithm is suitable to implement sine/cosine function, but the large number of iterations lead to great delay and overhead. Moreover, due to finite bit-width of operands and number of iterations, the relative error of floating-point sine or cosine is terrible when the input angle is close to 0 or π/2, respectively. To overcome these shortcomings, TCORDIC algorithm, which combines low latency CORDIC and Taylor algorithm, is presented. After analyzing the latency of traditional CORDIC, low latency CORDIC is proposed, which adopts the technique of sign prediction, compressive iterations, and parallel iterations. Besides, the calculating boundary (N), which is used for determining whether Taylor algorithm is selected or not in TCORDIC algorithm, is evaluated to achieve a trade-off between area and delay. Truncated multipliers are used to reduce the area further. Finally, Using TCORDIC algorithm, pipelined and iterative structures are implemented for IEEE-754 double precision floating-point sine/cosine with the input Zϵ[0, π/2]. Under typical condition (1V, 25 °C), our designs are synthesized with 40 nm standard cell library. For a pipelined structure, the frequency is up to 1.70 GHz and area 194049.64 μm ² . Frequency decreases to 1.45 GHz for iterative structure, but the area requires only 110590.81 μm ² . TCORDIC is efficient in controlling relative error, and achieves the accuracy within one ulp (unit in the last place) for floating-point sine/cosine function.

Previous works have projected that the peak performance of FPGAs can outperform that of the general purpose processors. However, no work actually compares the performance between FPGAs and CPUs using the standard benchmarks such as the LINPACK benchmark. We propose and implement an FPGA-based hardware design of the LINPACK benchmark, the key step of which is LU decomposition with pivoting. We introduce a fine-grained pipelined LU decomposition algorithm that enables optimum performance by exploiting fine-grained pipeline parallelism. A scalable linear array of processing elements (PEs), which is the core component of our hardware design, is proposed to implement this algorithm. To the best of our knowledge, this is the first reported FPGA-based pipelined implementation of LU decomposition with pivoting. A total of 19 PEs can be integrated into an Altera Stratix II EP2S130F1020C5 on our self-designed development board. Experimental results show that the speedup up to 6.14 can be achieved relative to a Pentium 4 processor for the LINPACK benchmark.

In the paper, we present a design of FPGA SAR processor with four 1D FFT processing elements, double internal RAM buffers and double external SDRAM modules. Without traditional corner turn phase, we propose a data layout scheme mapping one row of logical matrix into a rectangular window in physical banks of SDRAM in order to increase the practical I/O throughout between SDRAM modules and SAR processing elements. In addition, we theoretically analyses the optimal window size to minimize the total number of opening/closing pages when performing 2D FFT by balancing the number of handling physical pages between row accesses and column accesses. The experimental results show our window layout approach achieves 650 MB/s of effective bandwidth, reaching nearly 82% of peak bandwidth, with 58.1% increases compared to traditional Corner Turn approaches. The proposed SAR processor has been implemented in an FPGA test-bed, outperforming related works in both of computing speed and image scale.