Fast Fourier Transformation (FFT) has been widely recognized as an effective method for reducing the computational density of convolutional neural networks (CNNs). However, existing FFT-based CNN accelerators fail to fully exploit the algorithmic advantages of FFT while introducing significant additional hardware overhead. Consequently, this paper tries to figure out how to fully implement the benefit of FFT while saving the transformation overhead. First, we propose a CirConv-based multiplication reduction (CMR) algorithm, which leverages circular convolution and Hermitian Symmetry to eliminate unnecessary padding and optimize FFT scale selection. Building upon this algorithm, we further design a partially pipelined transformation-computation (PPTC) dataflow to reduce the parallelism and hardware complexity of FFT transformation. With the aid of the proposed CMR algorithm and PPTC dataflow, a high throughput FFT-based CNN accelerator is implemented on a Xilinx VCU118 FPGA platform, operating at 250 MHz. The experimental results demonstrate that, by combining Hermitian symmetry and PPTC dataflow, the LUT overhead for FFT/IFFT operations can be reduced to only 12.14% of the original. Furthermore, while deploying VGG16, the inference performance of our designed accelerator is 6213 GOPS, achieving a 2.17× to 29.31× improvement in actual performance and a 1.11× to 6.97× enhancement in DSP efficiency compared to the current works.

Packet classification plays a crucial role in computer networking such as quality of service and routing. With the continuous development of the internet, the scale of rule sets in packet classification continues to rapidly expand, leading to significant resource challenges for FPGA-based classification schemes. To this end, we propose an algorithm/hardware codesign scheme named BloomTree, which leverages off-chip DDR to store large-scale rule sets and conserve memory resources on FPGAs. To alleviate the memory access latency caused by the introduction of off-chip DDR, we innovatively combined the decision tree algorithm with the Bloom filter to prune invalid DDR accesses. The FPGA implementation of the proposed BloomTree adopts a fully pipelined architecture and possesses a dynamic update mechanism for pipelines, enabling both fast packet classification and flexible online rule update. The experimental results show that the proposed hardware architecture achieves average classification throughputs of 452.9 and 420.4 MPPS for the 10k rule sets and 140.9 and 71.8 MPPS for the 100k rule sets in the IPv4 and IPv6 scenarios, respectively. In addition, the update throughput can reach 71.4 MUPS. Compared with other methods that support dynamic rule updating, the proposed BloomTree utilizes the least memory resources on FPGAs and achieves$8.6\times $to$64.7\times $improvements in the speed to memory ratio.

In the era of Big Data, enterprises and individuals often upload databases to the cloud for storage and querying, which involves the risk of data leakage. Encrypted databases based on fully homomorphic encryption (FHE) theoretically solve the leakage problem, but the actual deployment of such encrypted databases faces the challenge of high economic costs. Cloud service providers charge for data transfer volume and computation time. Unfortunately, FHE is very expensive in both aspects, with more than five orders of magnitude deterioration compared to directly transmitting and computing plaintext. In this paper, we present STEED, a low-cost encrypted database that tackles both bottlenecks simultaneously. In STEED, we first introduce a FHE framework called BatchPBS, a batch pro grammable bootstrapping framework that improves the recent Liu and Wang (ASIACRYPT 2023) amortised scheme from 6.7 ms to 3 msper ciphertext while adding multi-value bootstrapping (MVB) support. Based on BatchPBS, we propose efficient SQL algorithms in SIMD-style to reduce the computation time and a novel AES transcipher protocol to reduce the data transfer volume. Thus, STEED reduces query time by 13 × and data transfer amount by 165 to 534.9 × compared with SOTA work. Considering end-to-end economic cost of TPC-H query on a database with 1 million rows, STEED reduces the expense of deploying on AWS by $28444.8 per 100 queries. (The code can be found at https://github.com/alibaba-damo-academy/ctl-he)

To overcome the trilemma between application flexibility, high efficiency, and minimal area/power overhead in baseband processors, this article proposes an area-efficient and reconfigurable accelerator for massive multiple-input-multiple-output (MIMO) systems, integrating a reconfigurable and heterogeneous processing element (PE) array featuring customized mixed-precision floating-point units (FPUs) to enable high-accuracy execution of diverse baseband operations (i.e., general matrix computation, inversion, mixed-radix fast fourier transform (FFT), decomposition, etc.) on matrices ranging from$4\times 4$–$32\times 32$. Addressing challenges posed by irregular partitioning and unbalanced decomposition in complex operations, an efficient heterogeneous mapping (EHeM) technology is introduced, achieving over 75% PE array utilization by minimizing external data access and reconfiguration overhead. Furthermore, a multibank memory structure with a dynamic access strategy (DAS) eliminates access conflicts and synchronizes memory-PE bandwidth across varying operators. This accelerator, validated on Xilinx Virtex-7 XC7VX690T, supports multiple baseband algorithms and signal processing operations, such as minimum mean square error (MMSE), FFT, and filtering. Evaluations show up to$75.41\times $throughput improvement and$239.30\times $efficiency improvement over operator-specific designs, and$1.10\times $–$6.02\times $higher efficiency than prior works for full MIMO processing.

In order to reduce the multiplicative depth required by high-order polynomial evaluation for homomorphic encrypted data, we propose two novel and low multiplicative depth polynomial evaluation algorithms: an x4-step nesting algorithm based on parity extraction (x4-NAPE) and a parallel algorithm with high data utilization (PAHU). Compared with the conventional Schoolbook method and Horner's rule, x4-NAPE can reduce about 50% of the ciphertext-ciphertext multiplication (CCM) and 75% of the multiplicative depth in the ideal limiting case. While PAHU does not reduce CCM, it can achieve a logarithmic growth of multiplicative depth, with the increase of polynomial length, the growth rate is much slower than x4-NAPE, Schoolbook method, and Horner's rule. Moreover, the hardware architectures of the above polynomial evaluation algorithms for homomorphic encrypted data are investigated and proposed. The proposed hardware architectures are assessed on the FPGA-based reconfigurable hardware platform for FHE named ReMCA. The assessment results demonstrate that under a fixed upper limit of multiplicative depth, our proposed architectures of x4-NAPE and PAHU support 2.67× and 14.3× the range of polynomial lengths of Schoolbook and Horner's rule, respectively. For polynomial evaluation of the same length, compared with architectures of Schoolbook and Horner's rule, our proposed architectures of x4-NAPE and PAHU can achieve up to 1.13× improvement in execution time, up to 50% reduction in multiplicative depth, and up to 2.39× improvement in the depth-time product.

Convolutional neural networks (CNNs) are evolving as they are applied to more diverse environments and more difficult challenges. The evolving induces various convolution modes (e.g., 1×1 convolution, 2-stride convolution and rectangle convolution) in current CNNs and makes it difficult for the hardware accelerators to efficiently support such various convolution modes. In this paper, it is found that an important difference of these convolution modes is the computation density. Therefore, the above convolution modes are regarded as structured sparse and claims that sparse-based design methodology can be applied for the implementation of the reconfigurable CNN accelerator. Subsequently, two critical architectural parameters, including input tile size and convolution engine (CE) scale, are evaluated based on Standard deviation of calculations (SDC), unsupported convolution mode (UCM) and unsuitable IFM size (UIS), DSP utilization ratio (DUR) as well as hardware resource overhead (HRO), respectively. With the aid of the optimal parameters, a high-parallelism and flexible CE array and a high-performance and reconfigurable CNN architecture are designed. The accelerator was implemented on a Xilinx VC709 FPGA and ran at a clock frequency of 300 MHz, achieving 921.60 to 1382.40 GOPS while supporting various convolution modes. Compared with previous dense-/sparse-based works, the proposed accelerator can realize 1.35× to 10.77× improvements on performance and 1.22× to 2.84× improvements on DSP efficiency while deploying VGG16.

CNN acceleration algorithms, including Winograd, Fast Fourier Transform (FFT) and Number Theoretic transform (NTT), have demonstrated their potential in efficiently operating current Convolutional Neural Networks (CNNs). However, deploying FFT algorithm for CNN acceleration would introduce significant invalid elements, unnecessary computations and unacceptable transformation overhead. To address these issues, this paper proposes a series of improved methods along with an FFT-based architecture for efficient and simplified CNN acceleration. First, a novel mixed-radix FFT algorithm is proposed for the reduction of invalid elements. Moreover, Hermitian symmetry is utilized to further reduce the scale of FFT transformation and the number of multiplications. Furthermore, an efficient FFT-based CNN accelerator with a resource-efficient transformation component and a multiplication-reduced PE array is designed. Our proposed accelerator is implemented based on Xilinx XCVU440 with a running frequency of 238MHz, achieving actual performance of 2109-2797 GOPS and DSP efficiency of 1.37-1.82 GOPS/DSP. Compared to previous works based on Winograd, FFT and NTT, our proposed accelerator can realize up to$9.42\times $speedup on actual performance and$1.11\times -6.41\times $speedup on DSP efficiency.

Leveraging sparsity in convolutional neural networks (CNNs) has emerged as a promising technique for enhancing the performance of CNN accelerators. However, despite achieving significant improvements in multiplier efficiency, the current sparse-based methods always fail to achieve a competitive performance and runtime latency compared with the conventional dense-based methods. This study posits that, because of the extremely irregular workload distribution in the input feature maps (IFMs), attaining a simultaneous improvement of the performance and multiplier efficiency in sparse-based accelerators is challenging. To address the above challenge, this study proposes a novel framework for eliminating irregularities at multi-level (i.e., dataflow-algorithm-hardware). Specifically, combined with filter decomposition and Winograd algorithms, a computation-oriented dataflow is designed for theoretical workload balancing under different convolution tasks. Furthermore, by exploiting the near-structured characteristic of IFMs, an online tile-based regularization scheme and a hybrid computation reduction method are designed to achieve a decreased and regular workload distribution. Finally, a large-scale sparse CNN accelerator, which integrates a row-merging scheme as well as a workload remapping method, is implemented to further eliminate hardware-level irregularities. The evaluation results show that our proposed methods can achieve 45.93%~76.59% multiplication savings when applied to VGG16, ResNet-34, and ResNet-50. Moreover, our accelerator can accomplish 3.06 TOPS and 2.86 sparsity extraction efficiency (SEE) while deploying VGG16, achieving a 1.17× to 3.45× enhancement on SEE compared with the state-of-the-art sparse-based accelerators.

Out-of-place constant-geometry (CG) NTT usually has a simple and uniform memory access pattern. However, out-of-place CG NTT always requires ping-pong memory, resulting in a memory capacity requirement of$2N$. Therefore, we propose a novel radix-4 in-place CG (IPCG) NTT/INTT that reduces the capacity requirement from$2N$to N. An area-efficient and dynamical reconfigurable polynomial multiplier (RAEPM) based on IPCG NTT is proposed to speed up polynomial multiplication over rings. In RAEPM, a Barrett modular multiplier using area-efficient radix-4 booth multiplier is designed to reduce area. In addition, an odd-bank buffer structure is proposed to achieve conflict-free memory mapping independent of polynomial length N and NTT/INTT stage. Moreover, we also proposed an efficient modular reduction for specific numbers and introduced a division equivalent method to eliminate the odd number modular reduction and odd number division in addressing. RAEPM is implemented on Xilinx VC709 FPGA and runs at 294MHz clock frequency. Compared with the prior pure NTT accelerators, under the same parameters, RAEPM achieves a decrease of 39.02%$\sim ~57.63$% in area-time complexity of equivalent LUT, and a decrease of 15.97%$\sim ~49.24$% in area-time complexity of equivalent FF. Compared with the prior NTT-based polynomial multipliers, under the same parameters, RAEPM achieves a decrease of 35.48%$\sim ~90.81$% in area-time complexity of equivalent LUT, and a decrease of 24.24%$\sim ~88.41$% in area-time complexity of equivalent FF.

Transformer models have received widespread attention in recent years. They have gradually replaced recurrent neural networks (RNNs) in natural language processing (NLP) and are widely used in tasks such as machine translation, text generation, and language understanding. Similarly, transformers have shown impressive results in computer vision (CV). However, their unique attention mechanism places high demands on the computational and storage resources of the hardware. Deploying transformers on edge computing platforms is challenging due to their complex data flow, intensive matrix calculations, and the need for high-precision nonlinear functions. To address these challenges, we propose reconfigurable transformer accelerator (RTA), a transformer hardware accelerator that uses low-bit-width prediction to achieve dynamic sparsity. RTA reduces resource consumption by performing sparse matrix multiplications using low-bit-width operations, while its reconfigurable design allows the sparse module to be used for high-precision large-bit-width matrix multiplications. We have also optimized the RTA computing pipeline to reduce resource usage and improve computational efficiency. Additionally, we incorporate feature sharing to enhance the resource utilization efficiency of the hardware accelerator. Experimental results on the transformer-base model show that RTA achieves an average performance of 994 GOPS and a digital signal processor (DSP) efficiency of 1412. Compared to state-of-the-art transformer accelerators, RTA achieves$1.37\sim 11.03\times $DSP efficiency.

Efficient binary polynomial multiplication (BPM) implementations are crucial for the practical deployment of bit flipping key encapsulation (BIKE) postquantum cryptography (PQC) due to its computation-intensive nature. To speed up BPM, this brief proposes a scalable and efficient architecture. The proposed architecture employs a novel blockwise sparsity algorithm, which segments sparse polynomials into blocks and leverages interblock and inner block sparsity to eliminate invalid computations, thereby significantly reducing computational operations. Moreover, a scalable block-by-block pipeline structure, along with a multibank random access memory (RAM) for sparse polynomials, is designed to effectively process blocks, resulting in substantial enhancement in performance. Experimental results on Xilinx Artix-7 Field-Programmable Gate Arrays (FPGAs) demonstrate significant performance superiority on the proposed architecture, compared with existing approaches. Across different bandwidth settings of 16, 32, 64, or 128, our design can achieve$4.5\times \sim 35.1\times $,$4.9\times \sim 78.8\times $,$2.5\times \sim 112.7\times $, and$0.5\times \sim 164.2\times $speedup, respectively. Compared with state-of-the-art works, our design achieves$2.8\times \sim 152.0\times $improvements in area efficiency.

Convolutional neural network (CNN) pruning is an effective way to reduce the computation requirement and improve the inference performance of standard convolutional layers. However, as for the low-computation-density layers in lightweight CNNs, pruning not only fails to improve their processing efficiency but also exacerbates the underutilization problem when deploying them on the convolutional engine. To efficiently execute these pruning-ineffective layers and further accelerate lightweight CNNs, a sparsity-adjustable CNN pruning method, which allows the pruning ratio to be adjusted, is proposed to prune the nonpruning-ineffective layers while shielding the pruning-ineffective layers. As a result, it achieves an additional 40% pruning ratio for nonpruning-ineffective layers with only 0.09% accuracy loss. Furthermore, a dense/sparse mixed-mode convolution computation scheme is designed to efficiently process the pruning- and nonpruning-ineffective layers using multiple acceleration techniques. Finally, a lightweight CNN accelerator is implemented on the Xilinx VCU118 FPGA platform. The comparison results with current studies present that this work can realize 1004.2 performance and 0.98 DSP efficiency while deploying MobileNetV2, achieving$1.26\times $-$6.13\times $enhancement on DSP efficiency.

Polynomial multiplication is a significant bottleneck in mainstream postquantum cryptography (PQC) schemes. To speed it up, number theoretic transform (NTT) is widely used, which decreases the time complexity from${O}(n^{2})$to$O[n\log _{2}(n)]$. However, it is challenging to ensure optimal hardware efficiency in conjunction with scalability. This brief proposes a novel pipelined NTT/inverse-NTT (INTT) architecture on field-programmable gate array (FPGA). A group-based pairwise memory access (GPMA) scheme is proposed, and a scratchpad and reordering unit (SRU) is designed to form an efficient dataflow that simplifies control units and achieves almost$n/2$processing cycles on average for n-point NTT. Moreover, our architecture can support varying parameters. Compared to the state-of-the-art works, our architecture achieves up to$4.8\times $latency improvements and up to$4.3\times $improvements on area time product (ATP).

Polynomial multiplication over rings constitutes one of the most computationally expensive operations in lattice-based cryptography. To accelerate it, the algorithm based on divide-and-conquer has received extensive attention because it has no strict parameter restrictions compared with the number theoretic transform (NTT). Among divide-and-conquer algorithms, apart from algorithms like Karatsuba and Schoolbook, the Winograd-based method has emerged as a new approach. This is because it can reduce the amount of computation while maintaining the scalability of parallelism. However, the parameters of the existing Winograd-based polynomial multiplication algorithm are conservative, and there is potential for further reducing the computational load. Therefore, we propose a novel and efficient 2-D Winograd-based polynomial multiplication (2-D WPM) algorithm. In this algorithm, we adopt the 2-D Winograd to alleviate the large denominator divisions and large-number multiplications that occur in the conventional 1-D Winograd as the parameter increases. We also propose a division elimination method to eliminate the inevitable divisions in the 2-D Winograd. When the polynomial length is 1024, compared with Schoolbook, 2-D WPM (${m} =3$,${r} =3$) can reduce the number of basic multiplications by 69%. In addition, an efficient polynomial multiplication accelerator for lattice-based cryptography named EPMA is proposed. In EPMA, we design reconfigurable modular arithmetic units to support both prime moduli and power-of-2 moduli. Keeping the full pipelined structure of EPMA, we also fully reuse the input data and the Winograd transformation results to achieve the conservation of hardware resources. EPMA is implemented on Xilinx FPGAs. Compared with previous works on FPGAs, under the same platform and parameters, the area efficiency of EPMA achieves an improvement of$1.22\times $to$18.02\times $. Compared with previous works on CPUs and GPUs, the computing speed of EPMA achieves an improvement of 9.25 to$1294.51\times $.

General convolution acceleration, such as Winograd and FFT, is a promising direction to address the computational complexity of current convolutional neural networks (CNNs). However, the flexibility of these CNNs makes this kind of scheme always introduce massive redundant computations, damaging the acceleration effect. In this article, a two-stage splitting method for arbitrarily sized tensors and filters and a unified hardware architecture using layer-adaptive allocated Winograd units are proposed, achieving effective redundance elimination and unified architecture. First, a tensor adaptive presplitting method is proposed to divide the original tensors to match the rule of Winograd. Furthermore, a Winograd-based extended splitting scheme is designed to reduce the redundant calculations; therefore, a substantial reduction in multiplication operations in convolutional layers achieved 30.6%–75% savings. Finally, a unified hardware architecture with a layer-adaptive allocation method is proposed to evaluate and select the optimal Winograd F(${m}$,${r}$) units and input/output parallelisms. This architecture is evaluated based on the Xilinx XCVU9P platform and achieves 1.97/1.23/1.60/1.25 GOPS/DSP for AlexNet, VGG16, modified VGG16, and ResNet18, respectively. It achieves up to$5.81\times $improvements in DSP efficiency compared with previous FPGA-based designs.

The visual SLAM (vSLAM) algorithm is becoming a research hotspot in recent years because of its low cost and low delay. Due to the advantage of fitting irregular data input, random sample consensus (RANSAC) has become a commonly used method in vSLAM to eliminate mismatched feature point pairs in adjacent frames. However, the huge number of iterations and computational complexity of the algorithm make the hardware implementation and integration of the entire system challenging. This paper pioneeringly proposes an efficient hardware acceleration design with homography matrix as RANSAC hypothesis model, which achieves high speed and high precision. Through optimizing the direct linear transformation (DLT) method, the delay and resource consumption are reduced. The design is implemented on FPGA. Through the verification of Xilinx Zynq 7100 platform, the processing frame rate on EuRoc dataset is 709 fps, reaching an average speed up of$263.2\times $against ARM CPU, and a speed up of$1.2\sim 50.0\times $compared with the advanced implementations in RANSAC part, which fully meets the real-time requirements. In addition, the root-mean-square error (RMSE) based on an open-source SLAM system (ICE-BA) on the EuRoc dataset reached 0.105 m, achieving an improvement of 15.6% in precision compared to the original ICE-BA system.

Polynomial multiplication over rings is a significant bottleneck of ring learning with error (RLWE)-based encryption. To speed it up, the number theoretic transform (NTT) and Toom-Cook-4 (TC4) are commonly used algorithms. Compared with NTT, TC4 is less restrictive and more flexible. However, there is a large opportunity at the algorithm level to improve the Schoolbook algorithm and postprocessing of TC4. Therefore, we propose a novel and efficient Winograd-Schoolbook algorithm that reduces multiplication by 29.1% (N = 256). We also propose a fused and low-density postprocessing that simplifies the algorithm flow and reduces multiplication by 56.25%. In total, these two-part improvements reduce the multiplication of TC4 by 32.47%. A high throughput and efficiency TC4 polynomial multiplier (TCMW) is proposed to speed up polynomial multiplication over rings. In TCMW, a highly parallel full pipelined structure without data waiting between modules is designed to make the parallelism of each module match and avoid the storage of intermediate results. In addition, based on the improved TC4, data buffers with data reuse, elementwise vector multiplication (EWVM) arrays, and efficient interpolation arrays are all designed to improve the performance and efficiency of TCMW. Implemented on the Xilinx VC709 field programmable gate array (FPGA) platform, TCMW can perform a TC4-based$256\times 256$polynomial multiplication over rings with an unrestricted modulus (as long as its factors do not contain 3 or 5) every$1.89~\mu $s at a 385 MHz clock frequency. Compared with prior designs of TC4, under the same conditions, the throughput of TCMW achieves an improvement of$1.91\times \,\,\sim \,\,7.71\times $, and the efficiency of LUT and DSP achieve improvements of$1.31\times \,\,\sim \,\,3.67\times $and$1.87\times \,\,\sim \,\,4.92\times $, respectively.

The growing number of data privacy breaches and associated financial losses have driven the demand for private database queries. Clients typically submit queries that involve both search and computation operations, such as counting students under a certain age or calculating the BMI of employees above a specific age. Existing protocols often face limitations due to reliance on specific-purpose encryption schemes or multiple communication rounds between clients and servers. In this work, we present a unified framework utilizing fully homomorphic encryption techniques to efficiently and privately process queries with search and computation operations. Our contributions include a homomorphic encryption-based private comparison algorithm, called the layered comparison algorithm, which achieves a 2.6-6.6X performance improvement compared to algorithms from prior work; a fast Fourier transform-based preprocessing method enabling accurate large integer arithmetic operations in the encrypted domain; and a scalable database encoding method. Evaluation results demonstrate the practicality of our system, as it processes an aggregated query for a 1k-row encrypted database in approximately 4.53 seconds.

Sparsification for convolutional neural networks (CNNs) and convolution acceleration algorithms such as the Winograd algorithm are two efficient ways to reduce the intensive computations of existing CNNs. To better combine the sparsification and Winograd algorithm, a close integration method is proposed to dynamically reduce the invalid parameters following the Winograd transformation. To address the limitation of data bandwidth, a hierarchical two-level storage structure and corresponding data scheduling scheme are proposed, which can realize a conflict-free scheduling process. In addition, an algorithm-hardware codesign method is proposed to efficiently and flexibly reduce the invalid computations led by the previous filter decomposition method. The accelerator is evaluated on Xilinx XCVU9P FPGA, reaching 412-MHz clock frequency. Compared to state-of-the-art designs, WRA-SS can achieve 1.54–$5.33\times $and 1.17–$7.39\times $performance improvement for VGG-16 under 80% weight sparsity and 0% weight sparsity, respectively.

Optical flow is a highly efficient visual tracking algorithm, which is commonly used to estimate pixel movement between two consecutive images in a video sequence. However, its high computational complexity and large number of computations become a bottleneck that hinders the performance of embedded vision systems. When applied to simultaneous localization and mapping (SLAM), it is necessary to consider not only time consumption, but also the overall accuracy of the system, causing even greater difficulties. In this paper, a real-time multi-scale Lucas Kanade (LK) optical flow hardware accelerator with parallel pipeline architecture is proposed. The designed circuit meets the high precision and real-time performance required by SLAM while fully considering the limitations of hardware resources. It is deployed on Xilinx Zynq SoC and achieves a frame rate of 93 fps for feature tracking of continuous frame images at$752\times 480$resolution. Compared with the implementation on ARM CPU, the average speed is increased by$4.5\times $. Finally, the feasibility and applicability of the hardware accelerator system designed in this paper are verified on the SLAM system. Experimental results on a public dataset show that the average Root Mean Square Error (RMSE) of this work is 0.189 m, indicating that the hardware accelerator has comparable precision with existing state-of-the-art software algorithms, achieving a great balance of performance and precision.

To adapt to complex scenes and strict accuracy requirements, evolutions have unstoppably occurred in current convolutional neural networks (CNNs). However, these evolutions bring changes to filter size, convolution type, and sparsity, and such diversity leads to difficulties when adopting evolving CNNs in field-programmable gate array (FPGA)-based accelerators. This article proposes a dense-/sparse-aware CNN accelerator to achieve high PE utilization and configurability. First, a filter-based decomposition and clustering algorithm (FDCA) is proposed to change the various-sized filters into unified size filters. In addition, a sparse-aware filter transformation scheme (SFTS) is presented to dynamically eliminate invalid weights for sparse filters and accelerate dense filters. Based on the elimination of sparsity dependency, a hardware accelerator with a data–index decoupling workflow and an input channel schedule-distribution system is designed to take advantage of FDCA and SFTS. The proposed accelerator is implemented on a Xilinx ZCU102 platform at 300 MHz. With different CNN configurations, the digital signal processor (DSP) efficiencies for dense and unstructured sparse AlexNet and dense and structured sparse MobileNetV2 are 0.987, 2.025, 0.547, and 1.278 GOPS/DSP, respectively. Compared with previous dense- and sparse-based designs, the accelerator achieves up to a$4.263\times $speedup in DSP efficiency.

Polynomial multiplication over rings is a significant bottleneck of ring learning with error (RLWE)-based encryption. To speed it up, three algorithms are widely used, i.e., number theoretic transform (NTT), Schoolbook, and Toom-Cook. Compared with Schoolbook and NTT, Toom-Cook can achieve a better trade-off between performance and flexibility. However, in Toom-Cook postprocessing, there are many redundant steps and calculations that have not been eliminated. Therefore, we propose an efficient, compressed, and fused Toom-Cook postprocessing algorithm that reduces the number of steps and at least 33.33% of the arithmetic operations of postprocessing. A highly reconfigurable and efficient Toom-Cook-based polynomial multiplier (TCPM) is proposed to speed up polynomial multiplication over rings. In TCPM, a high-throughput and efficient heterogeneous processing element (PE) array is designed to exploit the parallelism of Toom-Cook, and based on the compressed algorithm, the PE array for postprocessing is scaled down. In addition, as it is provided with a reconfigurable evaluation module, a flexible polynomial data storage module and a universal PE array, TCPM can efficiently map and execute Toom-Cook-2, 3, and 4 on a unified hardware architecture. Implemented on the Xilinx VC709 field-programmable gate array (FPGA) platform, TCPM can perform a Toom-Cook-4-based$256\times256$polynomial multiplication over rings with a modulus of a power of two or a prime every 3.28$\mu \text{s}$at a 360-MHz clock frequency. It achieves a$2.47\times $to$50.11\times $speedup compared with the previous designs.

Mixed-radix fast Fourier transform (FFT) algorithms are widely adopted in high-performance communication systems, such as 5G systems. However, in the decimation-in-time (DIT) FFT algorithm, neither the input time-domain series nor the intermediate-stage data are fetched in natural order, which causes a mismatch between the processing element (PE) computation speed and the memory bandwidth. In addition, multiple duplicate interstage twiddle factor (TF) generation units are designed to provide interstage TFs in parallel, and such duplication results in considerable waste of computing and storage resources. In this article, we propose a flexible and reconfigurable architecture based on a mixed-radix FFT approach, supporting 61 different FFT sizes modes from 12 to 3240 points ($2^{\alpha }$or$12\times n$,$n \le270$, and$n$=$2^{\alpha } 3^{\beta } 5^{\gamma }$). A DIT-FFT-based multiple parallel changeable-radix butterfly unit (BU) is designed to improve hardware resource utilization. Around the PE array, a conflict-free access structure with a hardware-friendly address generating method is presented. In addition, a TF sharing and compression structure is designed to reduce the area and delay of the TF generation units. The FFT architecture is implemented in semiconductor manufacturing international corporation (SMIC) 40-nm CMOS technology with a working frequency of 483 MHz, performing at 654 MS/s for 2048-point and 1536-point FFTs. Compared to the state-of-the-art mixed-radix FFT designs, our architecture achieves improvements of up to$5.89\times $in throughput and area efficiency and supports more FFT modes.

Feature extraction is one of the performance bottlenecks in embedded vision like visual navigation because of its high computational intensity. However, when applying it to simultaneous localization and mapping (SLAM), it is important to consider not only the time consumption but also the accuracy of the system. The more homogeneous the extracted features are distributed, the more accurately the feature matching can represent the geometric relationships in 3D space. In this paper, we propose a new hardware architecture of feature extraction with the addition of mask operation and a mini-grid pipeline to achieve homogeneous distribution. This work is implemented on a Xilinx Zynq SoC. Compared with the Intel i5 and ARM v8.2 CPU implementation of this work, our feature extractor achieves up to 15× and 35× acceleration, and up to 453× and 23× energy efficiency improvement. The evaluation results on the EuRoC dataset show accuracy comparable to the software implementation of the related work. Our architecture is hardware-friendly and achieves a good balance of accuracy and performance.

Fully homomorphic encryption (FHE) allows arbitrary computation on encrypted data and thus has potential in privacy-preserving computing. However, efficiency is still the bottleneck. In this paper we present an area-efficient and highly unified reconfigurable multi-core architecture (named ReMCA) for full Residue Number System (RNS) variant of Fan-Vercauteren variant of Brakerski’s scheme (RNS-BFV), which employs a variable number of reconfigurable processing elements (PEs) and RNS channels. The PE unit can be flexibly configured as NTT, INTT or modular multiplier, thereby avoiding the need of other extra computational units. To reduce the computational complexity, ReMCA merges the pre/post-processing into NTT/INTT and unifies the read/write structure of NTT and INTT. Also, a conflict-free memory access pattern that doesn’t need separate bit-reversal operation is proposed to optimize the memory access. Furthermore, targeting different computational requirements, a unified hardware architecture mapping model and data memory organization model are introduced, and all the computing units that RNS-BFV involved are optimized and mapped on ReMCA. ReMCA is evaluated on a Xilinx Virtex-7 FPGA platform. Running at 250MHz, it can perform 2260 homomorphic multiplication per second. When normalized to the same parameter set, the throughput and Area-Time-Products (ATPs) of ReMCA achieve$1.45\times \sim 5.51\times $and$1.58\times \sim 5.12\times $improvements.

The ring learning with error (RLWE)-based fully homomorphic encryption (FHE) scheme has become one of the most promising FHE schemes. However, its performance is limited by the homomorphic multiplication, especially the polynomial multiplication which occupies major computing resources. Therefore, efficient implementation of polynomial multiplication is crucial for high-performance FHE applications. In this article, we present an area-efficient and highly unified reconfigurable multicore number theoretic transform (NTT)/inverse NTT (INTT) architecture (named MCNA), which employs NTT and INTT for polynomial multiplier with a variable number of reconfigurable processing elements. To reduce latency, MCNA merges the preprocessing and postprocessing into the constant-geometry NTT and INTT, respectively. Also, a reconfigurable modular multiplier based on digital signal processor (DSP) is proposed to speed up the modular multiplication. In order to avoid designing independent memory access pattern for INTT, a unified read/write structure of NTT/INTT is presented. Furthermore, a novel memory access pattern named “cyclic-sharing” is proposed to reduce 25% memory capacity. MCNA is evaluated on a Xilinx Virtex-7 field-programmable gate array (FPGA) platform. Running at 250-MHz clock frequency, the throughput of MCNA for NTT/INTT achieves$2.78\times \sim 9.32\times $improvements in comparison to prior works, while the area efficiency of lookup table (LUT) and flip-flop (FF) is improved by$1.25\times \sim 4.79\times $. For polynomial multiplication, the throughput of MCNA achieves$3.73\times \sim 7.69\times $enhancements, as well as$1.13\times \sim 14.8\times $area efficiency improvements.

Neural network pruning, which can be divided into unstructured pruning and structured pruning strategies, has been proven to be an efficient method to substantially reduce the number of computations of convolutional neural networks (CNNs). However, it remains difficult to combine the advantages of these two pruning strategies. This article proposes a high-performance accelerator for unstructured sparse CNNs. First, a convolution-based filter selection and clustering method (FSCM) is proposed to reorder unstructured sparse filters into uniform-size dense filters, eliminating redundant computations in the convolutional layers while maintaining a regular structure. In addition, a convolution and pooling calculation method (CPCM) is presented to reduce interlayers’ computational redundancy. Third, a hardware accelerator with high digital signal processing (DSP) efficiency is designed to take advantage of FSCM and CPCM. The proposed accelerator is implemented on a Xilinx XCVU9P platform at 300 MHz. With different CNN configurations, the performance and DSP efficiency for LeNet, AlexNet, and VGG16 are 1490.53 GOPS and 3.882, 913.85 GOPS and 1.785, and 862.16 GOPS and 1.68, respectively. Compared to previous field-programmable gate array (FPGA) and application-specific integrated circuit (ASIC) designs, the accelerator achieves up to$15.43\times $and$7.73\times $speedup in terms of performance and DSP efficiency.

Coarse-grained reconfigurable arrays (CGRAs) can be dynamically programmed by configuration contexts to concurrently run multiple operations on a processing elements array. This further widens the gap between off-chip memory bandwidth demand and the limited speed of off-chip memory access. Cache prefetching is widely used for mitigating off-chip memory latency. However, straightforwardly applying existing prefetching techniques (primarily focusing on instruction driven processors) to CGRA may induce inaccurate prefetching, thereby crippling CGRA performance. Based on repetitively executed context in CGRA computing, this paper proposes a context-directed pattern matching (CDPM) mechanism to improve prefetching accuracy for CGRAs. CDPM generates a prefetch pattern for an initially executed context, and then reuses the pattern to issue prefetch requests when the context is re-executed. In order to eliminate the outdated prefetch pattern, CDPM also evaluates the prefetching accuracy of the prefetch pattern at run-time by adding prefetch addresses to a Bloom filter. The distinguishing feature of CDPM is the employment of the CGRA configuration context as a guide to improving prefetching accuracy. Experimental results showed that CDPM prefetching averagely improved performance by 31.1% compared to tests without prefetching and by 7.7% compared to state-of-the-art cache prefetching techniques, while only incurring slight area and power overheads.

Multiple coarse-grained reconfigurable arrays (CGRA), which are organized in parallel or pipeline to complete applications, have become a productive solution to balance the performance with the flexibility. One of the keys to obtain high performance from multiple CGRAs is to manage the shared on-chip cache efficiently to reduce off-chip memory bandwidth requirements. Cache partitioning has been viewed as a promising technique to enhance the efficiency of a shared cache. However, the majority of prior partitioning techniques were developed for multi-core platform and aimed at multi-programmed workloads. They cannot directly address the adverse impacts of data correlation and computation imbalance among competing CGRAs in multi-CGRA platform. This paper proposes a correlation- and iteration- aware cache partitioning (CIACP) mechanism for shared cache partitioning in multiple CGRAs systems. This mechanism employs correlation monitors (CMONs) to trace the amount of overlapping data among parallel CGRAs, and iteration monitors (IMONs) to track the computation load of each CGRA. Using the information collected by CMONs and IMONs, the CIACP mechanism can eliminate redundant cache utilization of the overlapping data and can also shorten the total execution time of pipelined CGRAs. Experimental results showed that CIACP outperformed state-of-the-art utility-based cache partitioning techniques by up to 16 percent in performance.

This paper proposes a context directed pattern matching (CDPM) mechanism, which employs the context of the coarse-grained reconfigurable arrays (CGRAs) as a guide to improve cache prefetching accuracy. CDPM generates a prefetch pattern for an initially executed context, and reuses the pattern to issue prefetch requests when the context is again executed on CGRA. To eliminate the outdated prefetch pattern, CDPM also evaluates the prefetching accuracy of the prefetch pattern at run-time. Experiments showed that CDPM averagely improved performance by 31.1% compared to tests without any prefetching and by 7.7% compared to state-of-the-art prefetching techniques.

The memory architecture has a significant effect on the flexibility and performance of a coarse-grained reconfigurable array (CGRA), which can be restrained due to configuration overhead and large latency of data transmission. Multi-context structure and data preloading method are widely used in popular CGRAs as a solution to bandwidth bottlenecks of context and data. However, these two schemes cannot balance the computing performance, area overhead, and flexibility. This paper proposed group-based context cache and multi-level data memory architectures to alleviate the bottleneck problems. The group-based context cache was designed to dynamically transfer and buffer context inside CGRA in order to relieve the off-chip memory access for contexts at runtime. The multi-level data memory was designed to add data memories to different CGRA hierarchies, which were used as data buffers for reused input data and intermediate data. The proposed memory architectures are efficient and cost-effective so that performance improvement can be achieved at the cost of minor area overhead. Experiments of H.264 video decoding program and scale invariant feature transform algorithm achieved performance improvements of 19% and 23%, respectively. Further, the complexity of the applications running on CGRA is no longer restricted by the capacity of the on-chip context memory, thereby achieving flexible configuration for CGRA. The memory architectures proposed in this paper were based on a generic CGRA architecture derived from the characteristics found in the majority of existing popular CGRAs. As such, they can be applied to universal CGRAs.

This paper proposes three configuration approaches to improve computing efficiency of a coarse-grained reconfigurable array, including input data relocation, line-based context switching, and loop interval minimization. These proposed approaches fully exploit the parallelism and pipelining of the reconfigurable array, which reduce interval latency when switching the configuration contexts, and therefore greatly enhance computing efficiency. These proposed techniques are used in a coarse-grained reconfigurable multimedia system (REMUS). Measured results show that, owing to the proposed approaches, REMUS can achieve 1080p@30fps performance for H.264 high profile video decoding under 200MHz working frequency. When normalized to the same technology, REMUS outperforms XPP-III 6.98x in energy efficiency.