MeNTT: A Compact and Efficient Processing-in-Memory Number Theoretic Transform (NTT) Accelerator

Let the pair of vectors (a,b) be related by the equation ${b=a*s+e}$, where a is a randomly sampled vector from $R_{q}$, e is a error vector sampled from a Gaussian distribution. Here $R_{q}=Z_{q}[x]/(x^{n}+1)$ is a ring of polynomial where n is a power of 2 [13], q is a prime number. Ring LWE [14] states that it is difficult to find secret vector $\textbf{s}\in R_{q}$ given the pair (a,b). Here, a*s is a polynomial multiplication, and is performed by transforming both a and b in NTT domain (Fig. 2).

Let a,s are two polynomials sampled from $R_{q}$, whose coefficients are in range [0,q) where q is prime number. We denote NTT coefficients of polynomial $(a=a_{n-1}x^{n-1}+a_{n-2}x^{n-2}+...+a_{0})$ as $\hat{a}_{n-1},\hat{a}_{n-2},..,\hat{a}_{0}$ respectively.

Polynomial multiplication of b=a*s is done using eq 1.After transforming both vectors a and s in NTT domain, NTT coefficients of b are calculated by coefficient wise multiplication of a and s. Original coefficients are calculated back by transforming $\hat{b}$ using Inverse NTT.

There are two popular variants of butterfly optimizations for the acceleration of polynomial multiplication: Cooley-Tukey [15] and Gentleman-Sande. The former is adopted in MeNTT and described in Algorithm 1. INTT computation is similar to NTT except that the twiddle factors are $w^{-n}$ instead of $w^{n}$.

Like many other memory-centric computation problems, such as deep learning, NTT computing faces the “memory walls” because of the energy and throughput bottleneck between logic and memory [16]. To alleviate this problem, a new computing paradigm with in- and near-memory computing emerged to reduce data movement, amortize memory access energy, and energy-efficient mixed-signal logic operation within a memory array [11].

In cryptographic computing, the requirement on PIM is different from that of machine learning applications because of its zero tolerance to compute errors. Thus, bit-parallel and bit-serial operations are more suitable than the lossy computing mechanisms in current, charge, or voltage domains [17, 18, 19, 20]. Recent Digital in-SRAM architectures [21, 22] have been designed to compute with full precision and high parallelism. However, these architectures are designed to compute MAC operations and are not suitable to output multiple modular arithmetic in parallel. Bit-serial in-SRAM logic performed by accessing two words simultaneously (Fig. 3) is first utilized to modern cryptography accelerators by [23], which performs very wide word bitwise logic and finite field arithmetic in memory. However, it does not provide the high parallelism expected for NTT acceleration. Performing arithmetic in bit-serial fashion was introduced in [24], which is promising for NTT and modular arithmetic because it achieves full accuracy computing with massive parallelism, by spending more clock cycles in each arithmetic operation. [12] leveraged a similar technique with projected high-performance and high-density ReRAM devices. It employs an unfolded architecture with straightforward control and routing schemes, which is possible with high-density ReRAM devices and slim peripherals, but will lead to an unacceptably large area if implemented on SRAM. On the other hand, recent ASIC NTT accelerator [10] has tried computing multiple butterfly operations in parallel and moving buffers closer to the computing units. However,the extensive use of registers for local buffering comes with a high area overhead. Thus, achieving the desired in-memory computing performance and efficiency gains with compact physical footprint and cost is the primary goal of this work.

We execute addition or accumulation from LSB to MSB in our bit-serial arithmetic operation. In order to keep the final result within field range, our reduction scheme utilizes the bit-serial comparator (Fig. 6) to keep track of the overflow condition of the result from the last operation. The comparison between temporary result and field limit ‘q’ starts from LSB to MSB cycle by cycle as bit-serial addition, subtraction or multiplication takes place. Reduction is applied based on the comparison result (Fig. 4) by applying a subtraction logic together with the adder. Only when reduction is required, the subtraction of q is enabled. For addition and subtraction, a ’raw’ result is calculated initially to evaluate an overflow. Then a ’real’ step is done to calculate the actual result with reduction. For multiplication, the partial sum is compared with q, while reduction is applied in the next round of accumulation with proper scaling.

The proposed modular addition and subtraction consist of a regular round of addition/subtraction with overflow/underflow detection called ”Trial Add and Compare Phase”, and a round of modular reduction called ”Modular Addition Phase”, as depicted in (Fig. 7). The WL driver activates corresponding bits of two operands A and B sequentially. The value on BL will be A AND B, while the value on BLB will be A NOR B. These values are read using traditional sense-amplifier and given as inputs to near-memory. The peripheral maintains one bit Carry for the addition, and acts like a full adder which adds A and B up sequentially and writes back to the array. In “Trial Add and Compare Phase”, in the meantime of addition, the peripheral reads one bit of q, and makes a comparison sequentially. An overflow bit is set if the sum of A and B is larger than q. In that case, column will calculate A+B-q during ”Modular Addition Phase”. Otherwise, column only calculates A+B to avoid timing side-channel leakage

Modular subtraction is done similar to modular addition by transforming one of the input B into it’s 2’s complement first. This can be done by setting the initial carry to 1 and using the value from BLB as input. During ”trial add and compare” phase after 2’s complement, an underflow bit is recorded. Based on the underflow bit value, addition of q is done during second-round subtraction to keep the result value correct. Addition requires 2*(N+1) cycles while the subtraction requires an extra N+1 cycles for 2’s complement calculation.

Modular multiplication is the most time-consuming part of the NTT. Traditionally, modular multiplication is performed by computing the raw product first, then going through a Barrett or Montgomery reduction(Fig. 9). In previous PIM works [24], this involves three normal multiplications and also takes extra redundant cycles as well as space. Although in some special cases [12] this reduction can be simplified, there is no general optimization for the modular multiplication using traditional reduction approaches.

This work proposes a fast bit-serial multiplication scheme to complete a modular multiplication in (N+1)² cycles (Fig. 8). The overall algorithm is described in Algorithm 5. The multiplication is decomposed into shift and add operations. There is a Tag bit which is similar to the approach of [24]. The shift is done by choosing a different address for rows in each round. The addition is controlled by the Tag bit from operand B and computed in the peripheral with carry and borrow. We take advantage of the bit-serial computation flow and compare every partial sum with q and 2*q. A reduction will be performed in the next cycle to make sure the partial sum is contained in the correct range. The reduction is enabled by the subtraction and borrow circuits, and controlled by the two overflow bits. In this way, the modular multiplication can be completed in parallel with the shift-and-add itself with very little space and time overhead. In order for the algorithm to be valid, operand A has to be smaller than q/2. Therefore we use 2*q instead of q as the field constant. Then MeNTT reduce the partial sum below q with an extra cycle. A switch is controlled by the Tag to separate the operand A from influencing the BL readout result. It decides whether the partial sum is added by an operand or kept the same. The reduction with q or 2q is done in peripheral with simple digital logic shown in Fig.  6.

Fig.  2 shows the CT radix-2 style NTT for the acceleration of polynomial multiplication in a ring. Each stage of NTT contains groups of butterfly operation which can be decomposed to a multiplication, an addition and a subtraction. Each stage has own grouping of points depending on the index.

As discussed in previous sections, traditional software implementation has an obvious bottleneck for Ring-LWE computations with the increase of polynomial order and coefficient’s bit width. The energy cost and latency are higher than hardware approaches by several orders. Under current Von-Neumann architecture, the highly parallel butterfly operations in NTT can only be executed in a serially. While modular arithmetic usually takes only one or few cycles each, the data transfer between memory and processor involves, cache and main memory read/write, which can cost 10s of cycles, making the whole process extremely expensive. From Table I, one can observe the significant energy and latency overhead in X86 based software approach. Despite the fact that a CPU can run at a higher speed than custom hardware, it is not the perfect solution for low-power and high-performance security applications. Also, software solutions are not well guarded against side-channel attacks. Since all operations are executed in ALU in serial, it is relatively easy for an attacker to retrieve power and timing information leaks for a side-channel attack. Due to the low efficiency of memory access in software approaches, hardware acceleration is widely desired and adopted for FFT and NTT applications.

FPGA-based hardware approaches exhibit improved performance, thanks to the customized architecture and datapath to elevate parallelism and efficiency for NTT computation. To support the modular arithmetic in NTT flow, DSP blocks [7] or custom multipliers are required to provide sufficient computing capability. Optimized datapaths are designed to accommodate the stage by stage NTT and INTT in a pipelined [26] approach which achieved higher throughput with a considerable area overhead. As shown in Table I, FPGA solutions outperform the software approach in throughput and latency, but their energy and area costs are significantly higher than custom hardware. Therefore FPGA is more generally more suitable for prototyping and deployment in the cloud.

The disadvantages of software and FPGA approaches inspired exploration in custom hardware solutions. ASIC implementations make use of standard SRAM or registers and compute modular arithmetic in digital circuits [8]. Although ASICs usually perform better than FPGAs in terms of speed, energy, and area, they come with much higher costs. Another major drawback for this approach is the amortized BL energy spent on reading data from SRAM. The processing speed is also limited by traditional memory bandwidth. While embedding registers for local storage in each computing unit increases throughput by increasing parallelism as in [10], the area overhead and limited scaling potential are the main drawbacks.

In terms of scalability to larger bit width and q, MeNTT executes modular arithmetic in bit-serial and word-parallel order while traditional software, FPGA, and ASIC approaches carry out butterfly unit operations word by word. Thus, MeNTT will achieve even higher throughput and energy efficiency than the other solutions, when the polynomial order gets higher.

ASIC solutions require higher design and fabrication cost, and need extra overhead to handle different schemes with different polynomial order, q and bit width. MeNTT  provides higher degree of configurability by providing general modular arithmetic in a highly parallel computing approach. The computation and data movement can be reprogrammed with minimal effort by changing WL accessing sequence and peripheral configurations. The SRAM rows and columns can be gated in different cryptography schemes for higher throughput and energy savings. MeNTT also provides higher normalized energy and area efficiency, as shown in Table I, mainly benefiting from in- and near-memory computation.

Compared to previous PIM studies that focus on leveraging parallel word-serial or bit-serial operation for general-purpose arithmetic in SRAM [23] and ReRAM [12, 24], optimized modular arithmetic and dataflow help MeNTT outperforms prior PIM works in energy and area efficiency as well as latency. MeNTT masks the inherent modular reduction cycles in the modular multiplication operation itself, whereas other designs use Barret or Montgomery reduction techniques which cause an extra area and latency overheads.

While  [12] achieved higher throughput by introducing multiple pipelines to break the data path into shorter pieces, our approach focuses on designing ultra-compact single SRAM bank implementation, which is more applicable to resource-constrained applications. Note that the reported latency for [12] is for specially selected q with very small hamming weight. The latency varies a lot with different choices of schemes and q. Other generic choices of q will incur high latency overhead. Last but not least, while the MeNTT design is implemented and evaluated with CMOS devices and SRAMs, the proposed modular arithmetic protocol and dataflow techniques are generic to any bit-serial PIM fabrics and can be easily adopted in PIM with emerging memories.