Zero-Aware Low-Precision RNS Scaling Scheme

Abstract

Scaling is one of the complex operations in the Residue Number System (RNS). This operation is necessary for RNS-based implementations of deep neural networks (DNNs) to prevent overflow. However, the state-of-the-art RNS scalers for special moduli sets consider the 2^k modulo as the scaling factor, which results in a high-precision output with a high area and delay. Therefore, low-precision scaling based on multi-moduli scaling factors should be used to improve performance. However, low-precision scaling for numbers less than the scale factor results in zero output, which makes the subsequent operation result faulty. This paper first presents the formulation and hardware architecture of low-precision RNS scaling for four-moduli sets using new Chinese remainder theorem 2 (New CRT-II) based on a two-moduli scaling factor. Next, the low-precision scaler circuits are reused to achieve a high-precision scaler with the minimum overhead. Therefore, the proposed scaler can detect the zero output after low-precision scaling and then transform low-precision scaled residues to high precision to prevent zero output when the input number is not zero.

1. Introduction

Residue Number Systems (RNSs) have been used in different applications such as digital signal processing (DSP) [1] and deep learning systems [2] to provide low-power, high-speed and fault-tolerant computations [3]. The main feature of an RNS is fast and parallel implementation of addition and multiplication based on separate modular arithmetic circuits. However, detection of multiplication overflow is one of the difficult RNS problems, since the multiplication of any two operands larger than half of the dynamic range results in overflow. Therefore, the high probability of overflow occurrence in multiplication has motivated researchers to develop overflow prevention mechanisms for an RNS. Scaling (i.e., division of the RNS number by a constant number) is one of the ways to reduce the size of the operands to prevent overflow in RNS operations. However, scaling is a difficult process, since the division operation in an RNS cannot be performed in parallel modular channels like multiplication and addition [4]. Therefore, usually one of the modulo of the moduli set is selected as the scaling factor to reduce the complexity [5].

The scaling for general moduli sets is usually realized using look-up tables (LUTs) [6], while the adder-based implementations can be achieved based on special moduli sets with higher performance. Due to this, there is a variety of works focusing on designing scalers for the well-known RNS three-moduli set {2ⁿ − 1, 2ⁿ, 2ⁿ + 1} [7,8,9]. The authors of [7,8] considered the modulo 2ⁿ as the scaling factor. Using 2ⁿ as the scaling factor resulted in simplified scalers with high-precision output. However, using only one modulo as the scaling factor is mostly applicable for addition operations, since it cannot drastically reduce the size of the numbers to prevent multiplication overflow. Due to this, the authors of [9] proposed two-moduli scaling based on 2ⁿ (2ⁿ + 1) as the scaling factor, which led to a low-precision output. Although this scaling factor can significantly reduce the size of the operands, the limited 3n-bit dynamic range of the three-moduli set {2ⁿ − 1, 2ⁿ, 2ⁿ + 1} is not suitable for two-moduli scaling factors because in this three-moduli RNS system, the values of most numbers are less than the scaling factor (i.e., 2ⁿ (2ⁿ + 1)), which results in a zero output for the scaler, consequently making the next operation faulty. This is a significant problem which indicates the importance of a zero-aware scaling mechanism, which is not covered by previous research.

Therefore, two-moduli scaling factors together with the large dynamic range four- or five-moduli sets, such as {2^k, 2ⁿ − 1, 2ⁿ + 1, 2^{n + 1} − 1} [10], {2ⁿ − 1, 2ⁿ, 2ⁿ + 1, 2^{2n + 1} − 1} [11] and {2ⁿ − 1, 2ⁿ + 1, 2²ⁿ, 2²ⁿ + 1} [12], {2ⁿ − 1, 2ⁿ + 1, 2²ⁿ, 2^{2n + 1} − 1} [13] and {2^{2n + p}, 2ⁿ − 1, 2ⁿ + 1, 2ⁿ − 2^{(n + 1)/2} +1, 2ⁿ + 2^{(n + 1)/2} +1} [14], should be used. However, there is a limited number of works that consider the scaling for four-moduli sets. The authors of [15] designed a scaler based on a two-level architecture with the single-modulo scaling factor 2^{n + k}. The first level of this scaler performs scaling based on the three-moduli set {2ⁿ − 1, 2^{n + x}, 2ⁿ + 1}, where 0 ≤ x ≤ n, and then the second level computes the final four-moduli scaling using the composite set {2^{n + k} (2²ⁿ − 1), m₄} [15]. This two-level architecture requires high hardware requirements due to the multiple uses of modular adders. Furthermore, scaling by the 2^k modulo is not sufficient for large dynamic range four-moduli sets to avoid overflow. In other words, the regular modulo 2ⁿ scaling of the numbers based on the three-moduli set {2ⁿ − 1, 2ⁿ, 2ⁿ + 1} is not equivalent to modulo 2ⁿ scaling in the four-moduli set {2ⁿ − 1, 2ⁿ, 2ⁿ + 1, 2^{n + 1} − 1}, since the dynamic ranges of these moduli sets are 3n- and (4n + 1)-bit, respectively. Therefore, two-moduli scaling must be used to prevent multiplication overflow for large dynamic range RNS systems.

On the other hand, to have a zero-aware scaler, the operands should be compared with the scaling constant before operation to prevent scaling with zero output. However, magnitude comparison is a difficult RNS operation, and its realization increases hardware complexity [4]. Here, we address this problem without using an RNS magnitude comparator based on a method for deriving two different scaling outputs from the same circuit.

In the proposed work, first, a low-precision scaler based on two moduli is proposed for RNS four-moduli sets. Then, we reuse the hardware architecture of a low-precision scaler for producing high-precision scaled output that can be used when the low-precision scaler generates zero for non-zero operands. It is shown how new Chinese remainder theorem 2 (New CRT-II) can be used to achieve simplified two-moduli scaling for four-moduli sets. The proposed approach (i.e., a double-output scaler with both low- and high-precision outputs) has two main advantages. First, the high-precision output can be applied to addition operands, while the low-precision output can be used for multiplication operations to prevent overflow by considerably reducing the operands’ size. Second, in the case of using a low-precision output for multiplication, if the low-precision output becomes zero, the high-precision output can be used to prevent overflow, resulting in a zero-aware scaling approach. Moreover, derivation of the proposed general approach for two special large dynamic range four-moduli sets {2ⁿ − 1, 2ⁿ + 1, 2²ⁿ, 2²ⁿ + 1} and {2ⁿ − 1, 2ⁿ + 1, 2²ⁿ, 2^{2n + 1} − 1} is presented, and its performance is compared with the conventional method.

In the rest of the paper, the mathematical formulation and proof of the proposed scaling approach for both general and special four-moduli sets are described in Section 2. Next, Section 3 presents the fully adder-based hardware design of the proposed scalers. Moreover, a performance comparison is presented in Section 4. Finally, Section 5 concludes the paper.

2. Low-Precision Scaling with Two-Moduli Scaling Factor: Mathematical Formulation

This section presents the proposed approach to design scalers for RNS using the New CRT-II [11]. In the rest of this section, a brief introduction about the scaling concept and new CRT-II is first described. Then, mathematical formulations of the proposed approach in general form and for two sample special forms will be presented.

2.1. Scaling Concept and CRT-II

The scaling of the weighted number X by the constant factor K according to the scaling operator defined in [16] and is as follows:

$$X=SK+{\left|X\right|}_K$$

(1)

This formula shows that any weighted number can be formed as a summation of its remainder with scaling factor K and the multiplication of the scaling result (i.e., S) and K. In other words, S is the integer quotient of dividing X by K, and it can be expressed as follows [5,7]:

$$S=\lfloor \frac{X}{K}\rfloor$$

(2)

Note that Equations (1) and (2) are based on weighted numbers. However, they should be implemented inside RNS using residues. Therefore, consider the following residue representations for X and S based on the four-moduli set {m₁, m₂, m₃, m₄}:

$$X\stackrel{RNS}{\to }\left(x_1, x_2, x_3, x_4\right)$$

(3)

$$S=\lfloor \frac{X}{K}\rfloor \stackrel{RNS}{\to }\left(s_1, s_2, s_3, s_4\right)$$

(4)

where the scale factor m₁ is one of the moduli. Aside from that, also consider

$$s_i={\left|S\right|}_{m_i} for i=1\dots 4$$

(5)

Second, consider the RNS number (x₁, x₂, x₃, x₄), which can be converted into its corresponding weighted number X using the New CRT-II conversion formulas for the generic four-moduli set {m₁, m₂, m₃, m₄} as follows [11]:

$$X=Z+m_1{m}_2{\left|k_1\left(Y-Z\right)\right|}_{m_3{m}_4}$$

(6)

$$Z=x_1+m_1{\left|k_2\left(x_2-x_1\right)\right|}_{m_2}$$

(7)

$$Y=x_3+m_3{\left|k_3\left(x_4-x_3\right)\right|}_{m_4}$$

(8)

where the required multiplicative inverses can be achieved by considering the following relations:

$${\left|k_1{m}_1{m}_2\right|}_{m_3{m}_4}=1$$

(9)

$${\left|k_2{m}_1\right|}_{m_2}=1$$

(10)

$${\left|k_3{m}_3\right|}_{m_4}=1$$

(11)

Equations (6)–(8) can be rewritten as follows:

$$X=Z+m_1{m}_{2}T$$

(12)

$$Z=x_1+m_{1}H$$

(13)

$$Y=x_3+m_{3}P$$

(14)

where

$$T={\left|k_1\left(Y-Z\right)\right|}_{m_3{m}_4}$$

(15)

$$H={\left|k_2\left(x_2-x_1\right)\right|}_{m_2}$$

(16)

$$P={\left|k_3\left(x_4-x_3\right)\right|}_{m_4}$$

(17)

2.2. General Formulations

Now, we choose the scaling factor as the product of the first and second modulo (i.e., m₁m₂). Therefore, scaling of X by m₁m₂ can be performed by considering k = m₁m₂ and substituting Equation (6) into Equation (4) as follows:

$$S_L=\lfloor \frac{X}{K}\rfloor =\lfloor \frac{Z+m_1{m}_{2}T}{m_1{m}_2}\rfloor =\lfloor \frac{Z}{m_1{m}_2}+T\rfloor$$

(18)

where x₁ is a residue in modulo m₁ and the maximum value of H in Equation (16) is m₂ − 1. Therefore, the maximum value of Z in Equation (13) can be computed as follows:

$$Z_{Max}=m_1-1+m_1\left(m_2-1\right)=m_1{m}_2-1$$

(19)

It is clear that the floor of the division of Z_Max by m₁m₂ is zero. Therefore, by considering this point and taking into account that T is an integer number, Equation (18) can be simplified as follows:

$$S_L=\lfloor \frac{Z}{m_1{m}_2}+T\rfloor =\lfloor \frac{Z}{m_1{m}_2}+T=T\rfloor$$

(20)

Now, according to Equation (5), the residues of T based on the moduli should be computed to achieve the residues of the scaled number as follows:

$$s_{L-i}={\left|S_L\right|}_{m_i}={\left|T\right|}_{m_i} for i=1\dots 4$$

(21)

Therefore, scaling of Z by m₁m₂ is reduced to T, and the full reverse conversion (i.e., full computing of Equation (6)) is not needed.

Now, we are going to achieve a single-modulo scaler for the same moduli set, (i.e., {m₁, m₂, m₃, m₄}) but with the aim of reusing the two-moduli scaler formulas to reduce the overhead. Hence, considering k = m₁ and the main CRT-II formula of Equation (6) in Equation (4) results in

$$S_H=\lfloor \frac{X}{K}\rfloor =\lfloor \frac{Z+m_1{m}_{2}T}{m_1}\rfloor =\lfloor \frac{Z}{m_1}+m_{2}T\rfloor$$

(22)

Insertion of Equation (13) into Equation (22) leads to

$$S_H=\lfloor \frac{x_1+m_{1}H}{m_1}+m_{2}T\rfloor =\lfloor \frac{x_1}{m_1}+H+m_{2}T\rfloor$$

(23)

Therefore, since x₁ is less than m₁, and H and T are integer numbers, Equation (23) can be simplified as follows:

$$S_H=\lfloor \frac{x_1+m_{1}H}{m_1}+m_{2}T\rfloor =\lfloor \frac{x_1}{m_1}\rfloor +H+m_{2}T=H+m_{2}T$$

(24)

Now, according to Equation (5), we have

$$s_{H-i}={\left|S_{Single}\right|}_{m_i}={\left|H+m_{2}T\right|}_{m_i} for i=1\dots 4$$

(25)

According to the residue arithmetic properties [6], Equation (25) can be rewritten as

$$s_{H-i}={\left|{\left|H\right|}_{m_i}+{\left|m_2\right|}_{m_i}{\left|T\right|}_{m_i}\right|}_{m_i} for i=1\dots 4$$

(26)

However, from Equation (21), we know the remainders of T in moduli m_i are the two-moduli scaling residues. Therefore, we have

$$s_{H-i}={\left|{\left|H\right|}_{m_i}+{\left|m_2\right|}_{m_i}{s}_{L-i}\right|}_{m_i} for i=1\dots 4$$

(27)

Therefore, by using Equation (21), the single-modulo scaling residues can be achieved from the previously computed two-moduli scaling residues with the minimum overhead. It should be mentioned that more simplifications of Equation (21) can be performed using the exact value of the moduli as shown in the next subsections.

2.3. Case Study: Moduli Set {2²ⁿ + 1, 2²ⁿ,2ⁿ + 1, 2ⁿ − 1}

The moduli set has a 6n-bit dynamic range, and its reverse converters are all designed based on the New CRT-I [11]. However, in contrast to the reverse converters of this moduli set, here, we use the New CRT-II to derive efficient two-moduli scaling formulas. First, consider the moduli set {m₁, m₂, m₃, m₄} = {2²ⁿ + 1, 2²ⁿ, 2ⁿ + 1, 2ⁿ − 1}. According to Equation (20), we must compute T in Equation (15), and then its residues are the low-precision scaling residues. First, the following lemma computes the required multiplicative inverses.

Lemma 1.

The multiplicative inverses required in Equations (15)–(17) are k₁ = 2^{2n − 1}, k₂ = 1 and k₃ = 2^{n − 1}.

Proof of Lemma 1.

Verification can be performed by substituting the values of the multiplicative increases and moduli in Equations (9)–(11) as follows:

$${\left|2^{2n-1}\times \left(2^{2n}+1\right)2^{2n}\right|}_{2^{2n}-1}={\left|2^{2n-1}\times 2\times 1\right|}_{2^{2n}-1}=1$$

(28)

$${\left|1\times \left(2^{2n}+1\right)\right|}_{2^{2n}}=1$$

(29)

$${\left|2^{n-1}\times \left(2^n+1\right)\right|}_{2^n-1}=1$$

(30)

Now, inserting the values of the moduli and multiplicative inverses in Equations (13)–(17) leads to

$$Z=x_1+\left(2^{2n}+1\right)H$$

(31)

$$Y=x_3+\left(2^n+1\right)P$$

(32)

$$H={\left|x_2-x_1\right|}_{2^{2n}}$$

(33)

$$P={\left|2^{n-1}\left(x_4-x_3\right)\right|}_{2^n-1}$$

(34)

$$T={\left|2^{2n-1}\left(Y-Z\right)\right|}_{2^{2n}-1}$$

(35)

Equation (31) can be further simplified by substituting Equations (31) and (32) into it as follows:

$$T={\left|2^{2n-1}\left(x_3+\left(2^n+1\right)P-x_1-\left(2^{2n}+1\right)H\right)\right|}_{2^{2n}-1}$$

(36)

The following well-known residue arithmetic properties can be used to further simplify Equations (33)–(36).

Property 1.

${\left|2^P{v}_i\right|}_{2^k-1}$is equal to the P-bit circular left shifting of v_i if v_i is represented as a k-bit binary number [11].

Property 2.

${\left|-v_i\right|}_{2^k-1}$is equal to one’s complement of v_i (i.e.,$\overline{v_i}$) if v_i is represented as a k-bit binary number [11].

Property 3.

${\left|-v_i\right|}_{2^k}$is equal to $\overline{v_i+1}$ if v_i is represented as a k-bit binary number [17].

Property 4.

${\left|-v_i\right|}_{2^k+1}$is equal to $\overline{v_i+2}$ if v_i is represented as a k-bit binary number [17].

First, according to the moduli set {2²ⁿ + 1, 2²ⁿ, 2ⁿ + 1, 2ⁿ − 1}, x₁ and x₂ are (2n + 1)- and 2n-bit numbers, respectively. Therefore, Equation (33) can be simplified using Property 3 as follows:

$$\begin{gathered} H={\left|x_2-x_1\right|}_{2^{2n}}={\left|x_{2,\left(2n-1\right)\dots 0 }-\left(x_{1,2n}\times 2^{2n}+x_{1,\left(2n-1\right)\dots 0}\right)\right|}_{2^{2n}} \\ ={\left|x_{2,\left(2n-1\right)\dots 0 }+\overline{x_{1,\left(2n-1\right)\dots 0}}+1\right|}_{2^{2n}} \end{gathered}$$

(37)

where x_i,j means the j-th bit of the residue x_i and x₄ and x₃ are (n + 1)- and n-bit numbers, respectively. Therefore, Equation (34) can be rewritten as

$$P={\left|2^{n-1}\left(x_4-x_{3,n}\times 2^n-x_{3,\left(n-1\right)\dots 0}{}_{ }\right)\right|}_{2^n-1}$$

(38)

where x₃ is a residue in modulo 2ⁿ + 1. Therefore, when x_3,n is equal to one, the other bits will be surely be zero, and if the n low significant bits (LSBs) of x₃ are not equal to zero, then the most significant bit (MSB) of x₃ (i.e., x_3,n) should be zero [12]. Therefore, by considering this point and Properties 1 and 2, Equation (38) can be simplified as follows:

$$P={\left|P_1+P_2\right|}_{2^n-1}$$

(39)

where

$$P_1={\left|2^{n-1}{x}_4\right|}_{2^n-1}=\underset{n bits}{\underbrace{x_{4,0}{x}_{4,n-1\dots }{x}_{4,1}}}$$

(40)

$$P_2=\left\{\begin{array}{c}\underset{n bits}{\underbrace{01\dots 11}} if x_{3,n}=1\\ \underset{n bits}{\underbrace{\overline{x_{3,0}} \overline{x_{3,n-1}}\dots \overline{x_{3,n-2}}}} if x_{3,n}=0\end{array}\right.$$

(41)

Finally, Equation (35) can be simplified using Properties 1 and 2 as follows:

$$T={\left|T_1+T_2+T_3+T_4+T_5\right|}_{2^{2n}-1}$$

(42)

where

$$T_1={\left|2^{2n-1}{x}_3\right|}_{2^{2n}-1}=x_{3,0}\underset{n-1 bits}{\underbrace{0\dots 00}}\underset{n bits}{\underbrace{x_{3,n}\dots x_{3,1}}}$$

(43)

$$\begin{gathered} T_2={\left|2^{2n-1}\left(2^n+1\right)P\right|}_{2^{2n}-1}={\left|2^{2n-1}\left(\underset{n bits}{\underbrace{p_{n-1}\dots p_0}}\underset{n bits}{\underbrace{p_{n-1}\dots p_0}}\right)\right|}_{2^{2n}-1} \\ =p_0\underset{n bits}{\underbrace{p_{n-1}\dots p_0}}\underset{n-1 bits}{\underbrace{p_{n-1}\dots p_1}} \end{gathered}$$

(44)

$$T_3={\left|-2^{2n-1}{x}_{1,\left(2n-1\right)\dots 0}\right|}_{2^{2n}-1}=\underset{2n bits}{\underbrace{\overline{x_{1,0}} \overline{x_{1,2n-1}}\dots \overline{x_{1,1}}}}$$

(45)

$$T_4={\left|-2^{2n-1}\times 2^{2n}\times x_{1,2n}\right|}_{2^{2n}-1}=\underset{2n bits}{\underbrace{\overline{x_{1,2n}}1\dots 11}}$$

(46)

$$T_5={\left|-2^{2n-1}\left(2^{2n}+1\right)H\right|}_{2^{2n}-1}={\left|-H\right|}_{2^{2n}-1}=\underset{2n bits}{\underbrace{\overline{H_{2n-1}}\dots \overline{H_1} \overline{H_0}}}$$

(47)

Note that P is an n-bit number, and due to this computation of Equation (44), it became a simple concatenation. Aside from that, the constant coefficient of H in Equation (47) was substituted with −1 since

$${\left|{\left|2^{2n-1}\right|}_{2^{2n}-1}{\left|2^{2n}+1\right|}_{2^{2n}-1}\right|}_{2^{2n}-1}={\left|2^{2n-1}\times 2\right|}_{2^{2n}-1}=1$$

(48)

Next, after calculation of T using Equation (42), we must compute the residues of T according to Equation (21) to achieve the two-moduli scaled residues. However, the largest value of T is 2²ⁿ − 2, and therefore, it is always less than the first and second moduli. Hence, we have

$$s_{L-1}={\left|T\right|}_{2^{2n}+1}=T$$

(49)

$$s_{L-2}={\left|T\right|}_{2^{2n}}=T$$

(50)

The third and fourth two-moduli scaled residues can be achieved as follows:

$$\begin{array}{c}{s}_{L-3}={\left|T\right|}_{2^n+1}={\left|T_{\left(2n-1\right)\dots n}\times 2^n+T_{\left(n-1\right)\dots 0 }\right|}_{2^n+1}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}={\left|T_{\left(n-1\right)\dots 0 }-T_{\left(2n-1\right)\dots \left(n-1\right)}\right|}_{2^n+1}\hfill \\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}={\left|T_{\left(n-1\right)\dots 0 }+\overline{T_{\left(2n-1\right)\dots \left(n\right)}}+2\right|}_{2^n+1}\hfill \end{array}$$

(51)

$$s_{L-4}={\left|T\right|}_{2^n-1}={\left|T_{\left(2n-1\right)\dots n}+T_{\left(n-1\right)\dots 0 }\right|}_{2^n-1}$$

(52)

Now, based on Equation (27), we can also achieve single-modulo scaling formulas from the two-moduli scaling residues as follows:

$$\begin{array}{c}{s}_{H-1}={\left|{\left|H\right|}_{2^{2n}+1}+{\left|2^{2n}\right|}_{2^{2n}+1}{\left|T\right|}_{2^{2n}+1}\right|}_{2^{2n}+1}\hfill \\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}={\left|{\left|H\right|}_{2^{2n}+1}+{\left|2^{2n}\right|}_{2^{2n}+1}{s}_{L-1}\right|}_{2^{2n}+1}\hfill \end{array}$$

(53)

We can simplify Equation (27) by substituting Equation (49) into it and considering that the maximum value of H in (37) is 2²ⁿ − 1. Therefore, we have

$$s_{H-1}={\left|H-T\right|}_{2^{2n}+1}={\left|H+\overline{T}+2\right|}_{2^{2n}+1}$$

(54)

Similarly, for other residues, we have

$$s_{H-2}={\left|{\left|H\right|}_{2^{2n}}+{\left|2^{2n}\right|}_{2^{2n}}{\left|T\right|}_{2^{2n}}\right|}_{2^{2n}}=H$$

(55)

$$\begin{array}{c}{s}_{H-3}={\left|{\left|H\right|}_{2^n+1}+{\left|2^{2n}\right|}_{2^n+1}{\left|T\right|}_{2^n+1}\right|}_{2^n+1}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}={\left|{\left|H_{\left(2n-1\right)\dots n }\times 2^n+H_{\left(n-1\right)\dots 0 }\right|}_{2^n+1}+s_{L-3}\right|}_{2^n+1}\hfill \\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}={\left|\overline{H_{\left(2n-1\right)\dots n }}+H_{\left(n-1\right)\dots 0 }+2+s_{L-3}\right|}_{2^n+1}\hfill \end{array}$$

(56)

$$\begin{array}{c}{s}_{H-4}={\left|{\left|H\right|}_{2^n-1}+{\left|2^{2n}\right|}_{2^n-1}{\left|T\right|}_{2^n-1}\right|}_{2^n-1}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}={\left|H_{\left(2n-1\right)\dots n }+H_{\left(n-1\right)\dots 0 }+s_{L-4}\right|}_{2^n-1}\hfill \end{array}$$

(57)

Therefore, we can compute H and T from Equations (37) and (42) just one time and then using them several times to compute both the single- and two-moduli scaling.

2.4. Case Study: Moduli Set {2ⁿ − 1, 2ⁿ + 1, 2²ⁿ, 2^{2n + 1} − 1}

This moduli set has the same moduli as {2ⁿ − 1, 2ⁿ + 1, 2²ⁿ, 2²ⁿ + 1} except for 2²ⁿ + 1 which is substituted with 2^{2n + 1} − 1. Due to this, it can lead to a faster RNS arithmetic unit. However, its reverse converter will be more complex. The overall process of designing the scaler for this moduli set is relatively the same as for the moduli set {2ⁿ − 1, 2ⁿ + 1, 2²ⁿ, 2²ⁿ + 1} described in the previous subsection.

First, consider the moduli order {m₁, m₂, m₃, m₄} = {2^{2n + 1} − 1, 2²ⁿ, 2ⁿ + 1, 2ⁿ − 1}. Then, according to Equations (15)–(17), the multiplicative inverses can be computed as k₁ = k₂ = 1, and k₃ = 2^{n − 1} (the proof is straightforward and similar to Lemma 1). Therefore, Equation (15) is a key formula in the scaling that can be calculated as follows:

$$\begin{array}{c}\hspace{1em}\hspace{1em}\hspace{1em}T={\left|Y-Z\right|}_{2^{2n}-1}\hfill \\ ={\left|x_3+\left(2^n+1\right)P-x_1-\left(2^{2n+1}-1\right)H\right|}_{2^{2n}-1}\hfill \\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}={\left|T_1+T_2+T_3+T_4+T_5\right|}_{2^{2n}-1}\hfill \end{array}$$

(58)

where

$$T_1={\left|x_3\right|}_{2^{2n}-1}=\underset{n bits}{\underbrace{0\dots 00}}\hspace{0.17em}\underset{n bits}{\underbrace{x_{3,n-1}\dots x_{3,0}}}$$

(59)

$$T_2={\left|\left(2^n+1\right)P\right|}_{2^{2n}-1}=\underset{n bits}{\underbrace{p_{n-1}\dots p_0}}\hspace{0.17em}\underset{n bits}{\underbrace{p_{n-1}\dots p_0}}$$

(60)

$$T_3={\left|-x_{1,\left(2n-1\right)\dots 0}\right|}_{2^{2n}-1}=\underset{2n bits}{\underbrace{\overline{x_{1,2n-1}}\dots \overline{x_{1,0}} }}$$

(61)

$$T_4={\left|-2^{2n}\times x_{1,2n}\right|}_{2^{2n}-1}=\underset{2n bits}{\underbrace{1\dots 11\overline{x_{1,2n}}}}$$

(62)

$$T_5={\left|-\left(2^{2n+1}-1\right)H\right|}_{2^{2n}-1}={\left|-H\right|}_{2^{2n}-1}=\underset{2n bits}{\underbrace{\overline{H_{2n-1}}\dots \overline{H_1} \overline{H_0}}}$$

(63)

The two-moduli scaled residue formulas for the moduli set {2^{2n + 1} − 1, 2²ⁿ, 2ⁿ + 1, 2ⁿ − 1} are the same as those for the moduli set {2²ⁿ + 1, 2²ⁿ, 2ⁿ + 1, 2ⁿ − 1} (i.e., Equations (49)–(52)), since all of them are based on T. That aside, the single-modulo scaled residues are the same as in Equations (55)–(57) except for the first scaled residue, which is as follows:

$$\begin{array}{c}{s}_{H-1}={\left|{\left|H\right|}_{2^{2n+1}-1}+{\left|2^{2n}\right|}_{2^{2n+1}-1}{s}_{L-1}\right|}_{2^{2n+1}-1}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{0.17em}={\left|H+\underset{2n+1 bits}{\underbrace{s_{L-1,2n-1}\dots s_{L-1,0}{s}_{L-1,2n}}}\right|}_{2^{2n+1}-1}\hfill \end{array}$$

(64)

3. Low-Precision Scaling with Two-Moduli Scaling Factor: Hardware Design

This section presents the full adder-based and memory-free hardware design of the proposed RNS scaler. The overview of the proposed approach for a generic four-moduli set is depicted in Figure 1. First, P, H and T are computed using Equations (15)–(17), and then, the two-moduli scaled residues are computed using Equation (21). Afterward, the single-modulo scaled residues are obtained using the precomputed two-moduli scaled residues based on Equation (27). The important part of the scaler is the calculation of T that is shared between both kinds of scaling, resulting in a significant hardware reduction.

The scaler of Figure 1 is designed based on a general value of the moduli. However, for special RNS moduli sets with power-of-two moduli such as {2²ⁿ + 1, 2²ⁿ, 2ⁿ + 1, 2ⁿ − 1}, the design can be considerably simplified, as presented in Figure 2. First, the H in Equation (39) is implemented using a 2n-bit regular carry-propagate adder (CPA) where its carry-in is connected to one. Aside from that, P also requires a modulo 2ⁿ − 1 CPA, which can be implemented using an n-bit CPA with EAC [18] based on Equation (40).

The operand preparation unit performs the required inversions, shifting and multiplexing needed in Equation (41). Then, the important variable T in Equation (42) can be realized using three carry-save adders (CSAs) with EAC followed by a modulo 2²ⁿ − 1 CPA [18]. Then, according to Equations (49)–(52), the first and second two-moduli scaled residues are equal to T, and the third and fourth are only the reduction of T in moduli 2ⁿ − 1 and 2ⁿ + 1, which can be realized using an n-bit CPA with EAC and n-bit CPA with complement EAC (CEAC), respectively. Note that CPA-CEAC is a representation of the modulo 2ⁿ + 1 adder which can be realized using different methods [19]. Finally, the single-modulo scaled residues can be achieved using Equations (54)–(57). The CSAs are used to compress the three operands into two, and then a modulo adder produces the scaled residue. It can be seen that in the customized version of the scaler for the moduli set {2²ⁿ + 1, 2²ⁿ, 2ⁿ + 1, 2ⁿ − 1}, the units for m₁ and m₂ reduction in the two-moduli scaling part are removed, since the scaled residues are equal to T. Aside from that, the second single-modulo scaled residue is H, and hence, the required m₂ reduction unit is removed.

Finally, Algorithm 1 shows how the proposed hardware architecture can be used to provide zero-aware RNS scaling. If the low-precision scaled residues become zero, then the high-precision scaled residue should be used as the output, except in the case that they also become zero. In this case (i.e., both scaler outputs become zero), the number is very small and is less than both of the scaling constants. In this case, its original value can be used in the computations. Note that here we do not use any magnitude comparator which is a complex unit in RNS, and only by checking the scaled residues against zero we could evaluate the relative magnitude of the number (less or greater than the scaling coefficients).

Algorithm 1: Zero-Aware RNS Scaling.

Input:Non-Zero RNS Number (x1, x2, x3, x4)

Output:Non-Zero Scaled RNS Number (s1, s2, s3, s4)

1: Calculate the low-precision scaled residues (sl1, sl2, sl3, sl4)

2: If (sl1, sl2, sl3, sl4) ≠ (0, 0, 0, 0) Then return (sl1, sl2, sl3, sl4)

3: Calculate the high-precision scaled residues (sh1, sh2, sh3, sh4)

4: If (sh1, sh2, sh3, sh4) ≠ (0, 0, 0, 0) Then return (sh1, sh2, sh3, sh4)

5: Return original residues (x1, x2, x3, x4)

4. Performance Evaluation

The majority of the available state-of-the-art RNS scalers are dedicatedly designed for three-moduli sets, and only [15] presents the first RNS scaler design for four-moduli sets. The RNS scaler for the moduli set {2^{2n + 1} − 1, 2²ⁿ, 2ⁿ + 1, 2ⁿ − 1} is fully designed in [15] based on the scaling factor 2²ⁿ as shown in Figure 3. To perform a technology-independent performance comparison, the unit-gate (U-G) model is used according to [15] for comparative assessment of the works. All the assumptions considered in [15] for estimation of the area and delay of modular adders are also considered here for a fair comparison, as shown in

Table 1. The area and delay formulas for different n-bit modulo adders based on the U-G model reported in [15].

Modulo	Adder	Area	Delay
$2^n-1$	CPA-EAC	$3n\lceil {\log }_{2}n-1\rceil +12n$	$2\lceil {\log }_{2}n-1\rceil +3$
	CSA-EAC	$7n$	4
$2^n$	CPA	$1.5n\lceil {\log }_{2}n\rceil +5n$	$2\lceil {\log }_{2}n\rceil +3$
$2^n+1$	CPA-CEAC	$4.5n\lceil {\log }_{2}n\rceil +0.5n+6$	$2\lceil {\log }_{2}n\rceil +3$
	CSA-CEAC	$7n$	4

.

Note that in the U-G model, each XOR or XNOR gate counts as two unit gates in the area and delay, and an AND or OR gate is considered one unit gate for both the area and delay. Therefore, the combinatorial circuits such as FAs, half adders (HAs) and one-bit 2×1 multiplexers count as 7, 3 and 3 unit gates in area and 4, 2 and 2 gates in the delay, respectively. Aside from that, the U-G area and delay estimations for each component of the proposed scaler is described in

Table 2. The area and delay formulas based on the U-G model for different components of the proposed double-modulo scaler.

Component	Area	Delay
2n-bit CPA	$3n\lceil {\log }_{2}n\rceil +13n$	$2\lceil {\log }_{2}n\rceil +5$
n-bit 2 × 1 MUX	$3n$	$2$
n-bit CPA-EAC	$3n\lceil {\log }_{2}n-1\rceil +12n$	$2\lceil {\log }_{2}n-1\rceil +3$
2n-bit Simplified CSA-EAC1	$10n+4$	$4$
2n-bit Simplified CSA-EAC2	$6n+4$	$4$
2n-bit CSA-EAC	$14n$	$4$
2n-bit CPA-EAC	$6n\lceil {\log }_{2}n\rceil +24n$	$2\lceil {\log }_{2}n\rceil +3$
n-bit CSA-CEAC	$7n$	$4$
n-bit CPA-CEAC	$4.5n\lceil {\log }_{2}n\rceil +0.5n+6$	$2\lceil {\log }_{2}n\rceil +3$

. Note that the gray lines in Table 2 are not on the critical delay path.

Finally, the overall area and delay estimations for scalers are presented in

Table 3. The total area and delay estimations for the RNS scalers based on the four-moduli set {2^{2n + 1} − 1, 2²ⁿ, 2ⁿ + 1, 2ⁿ − 1}.

Scaler	Scale Factor	Area	Delay
Proposed Low-Precision	22n (22n + 1 − 1)	$19.5n\lceil {\log }_{2}n\rceil +95.5n+14$	$6\lceil {\log }_{2}n\rceil +27$
Proposed High-Precision	22n	$31.5n\lceil {\log }_{2}n\rceil +160.5n+14$	$8\lceil {\log }_{2}n\rceil +34$
[15] High-Precision	22n	$\left(28.5n+6\right)\lceil {\log }_{2}n\rceil +150.5n+44$	$6\lceil {\log }_{2}n\rceil +25$

for a general value of n. It can be seen that while the proposed low-precision scaler is based on a two-moduli scaling factor, the hardware requirement is less than the single-modulo scaler for the same moduli set, while the delay is almost the same. That aside, the proposed scaler outperforms the design of [15] in terms of hardware requirements. Furthermore, as is expected, the high-precision single-modulo version requires a higher area and delay since it is computed based on the output of the two-moduli scaler.

5. Conclusions

Scaling is an overflow prevention mechanism that must be extensively used to prevent overflow by reducing the size of the operands before RNS addition and multiplication operations. However, high-precision single-modulo scaling is not suitable for overflow prevention in multiplication due to its inability to perform significant size reduction, but the low-precision scaling with two moduli can lead to a zero result for small numbers. Therefore, this work presents a novel zero-aware low-precision scaler based on the two-moduli scaling factor. Then, the proposed circuits are reused to derive a high-precision scaling output to use in situations where low-precision output is not usable, resulting in a zero-aware RNS scaler. Therefore, the proposed design is pushing forward the RNS into practical applications by providing an efficient mechanism for overflow prevention, which is one of the major challenges of RNS. On the other hand, the high latency of the scaler is one of the limitations of this approach which can be improved in the context of the final application.