A simple, quick and new design of scaling circuit for the modulo set

In this study a new and unique design of the residue number system scaling circuit for the 3moduli set which has a dynamic range over 5n is presented. Nowadays 5n dynamic range has proved to be of good performance. The relations in this study are obtained by Chinese Remainder Theorem which is one of the most important conversion algorithms in residue number system.

Designing scaling circuits was first discussed by Szabo & Tanaka in 1967. At that time calculation period was in a cycle as long as n clock that n resembled the number of modulo set members. Their suggested method was not error free though it was considered advancement in RNS [6]. In 1973 Okeefe & Wright designed a circuit for the modulo set which was more effective than Szabo’s but was also not error free as well, though it gave closer answers[7]. In 1978 Jullien managed to present an algorithm that needed fewer clocks but also accompanied some errors[8]. In 1981 Taylor & Huang made a design that despite all previous ones that were based on CRT algorithm, used MRC method in its calculations [9]. A year later these two presented a model that was an idea based on modulo sets and LUTs, but like others needed a long n clock of time [10]. In 1984 Polky & Miller presented a new algorithm that needed (N+1) clock of time and the value obtained from it was closer to real value. In fact it carried fewer errors than previous offers but claimed more time [11]. Five years later Shenoy & Kumarson offered a design for scaling that needed a period of log n that was much more considerable than the preceding offers [12]. Finally in 1993 Ulman wrote an essay based on SZabo’s work and promoted his method to a lot of extent [13]. From then on, a lot of suggestions were made in this field but the point is that there were errors in all algorithms but the value didn’t exceed 1.5 units [5]. At that time scaling circuits were applied bye ROM memory and this made the processes slow and power consumption high. Due to this reason researchers were always looking for a way to solve this. However ROM matrixes can be replaced by multiplexers, it increased the cost unacceptably. We would like to mention that there are two ways to design algorithms; one using LUTs and the other by accessing through full adders and almost in all designs based on memory, the cost increases as the number of modules do, while designs with full adders are faster and claim less area. In 2011 Chang could offer a new perspective in scaling circuits by modular full adders which resulted in speed increase and less power consumption[5]. It is necessary to mention that there are also other scaling circuits that benefit from both technologies of LUT and full adders, but in among these circuits, Chang’s is the fastest and the most efficient. A weakness for this circuit would be that it is a design for 3member modulo set with a dynamic range of 3n bit which does not suffice for today’s computer needs. Chang also surveyed scaling circuits for signed numbers in a paper in 2012.

As mentioned above there are two ways to do scaling algorithms, one using LUTs [14],[15]and the other access through full adders[16-19]. At first all algorithms used ROM but scaling algorithms their problem was high power consumption. However ROM matrixes can be replaced with modular multiplexers, this increases the cost unacceptably. This cost increase would be much more for greater modulo sets. As pointed before almost all designs based on memory increase the cost as the modules’ number increases, while if those designs are manipulated with full adders it would be faster and would claim less area[15]. In this study we surveyed designing a scaling circuit for the modulo set.

CRT algorithm is defined as below:


(1)



(2)
As we know dynamic range is obtained from multiplying modulo set members, so:




(3)
Here are some relationships that can be used for simplifying existing scaling relationships and designing offered circuits.


(4)



(5)



(6)





(7)
If z is an n bit number then:




(8)
Supposing, if k is an integer then always applies. For proving this rule we could use the below rules:

Considering rules (4) and (5) it can be inferred that:

If , and For calculating s we act as below:

Here we suppose (the second modulo). So y is:

Based on rule (10) for i=1, 2, 3 simplifying continues as below:

In the above statement we omit , to analyze this omission we can write:

If and و and also then:

Using rule (4-8) we could reconstitute the above statement as below:

In a way that is a non-negative digit. Without the replacements of, and rule (23) will be like:

If is named, then we can simplify the above relationship as follows:

Since, then we can write:

It can be concluded from the above relationships that:

Now using the above replacements and notes below, we derive formulas of preferred scaling circuits.

Note 1: if a k bite digit (such as v) is multiplied by a 2ⁿ and we want the result in modulo _, then the answer equals n-bit circular shift to the left of the desired digit.

Note 2: if v is negative then the result equals the complementary of the digit v.

To calculate value of A using note (1) we have:

Also for B we can write:

Finally is gotten as below:

This shape below illustrates how value is designed.



Figure . Hardware of

3.2. Calculating

To prevent sophistication of calculation that has the below value, we can divide it into the 3 sub-formulas , , .

Now we can simplify for each part like this:

Using rule (4-6), we can simplify as below:

Using the simplification that resulted in (23), for we can have:

With the above rules and relationships we can also simplify as below:

Now with having the value of, , we can finally calculate.

Figure . Hardware of

Like the 2 previous parts, to calculate this part we use the mentioned rules and relationships.

Considering rule (7), for we can have:

And lastly for we can have:

We can define to organize the above rule as below.

And at last for we have:

And the shape resulted from the above rules is like this.

Figure . Hardware of

As it was explained in the beginning of the article, using the residue number system in computer systems is one of the imminent problems for the lack of efficient hardware necessary. This problem can be tackled with designing scaling circuits to a great extent. Needing to use modulo sets with larger dynamic ranges, we chose modulo set . This design caused the omission of division operation and the transforming reverse unit for calculating the overlap in residue number system. As we know in RNS we are supposed to take the residues resulted from preferred modulo set to the conventional number system with using the reverse transformer and then do de division on them and formerly transfer the digit to residue system and this can be costly and time consuming. While there is no need to do these operations in scaling circuits and we can get the division residues directly from the residues available in RNS system without need to use reverse transformer or division. As follows we prove scaling circuits improving role in residue number system with presenting an example.

Without using scaling:

Here as an example we assume that n=3, then modulo set will be {63,8,65}. If preferred numbers’ residues of this set are{24,5,51}, we should firstly transfer the preferred digit to conventional number system that is performed by Chinese residue algorithm:

Up to this step we have only developed preferred digit in residue system. Now we should divide it by the scale that is 8 here in this example (it is obvious that division operation in computer calculations is costly and time consuming), and again transfer the digit to residue number system.

Now we survey through the above calculations and relations with the use of scaling.

With using scaling:

It is concluded that using scaling can improve residue system’s efficiency in computer calculations to a great extent.

As a final point we survey the results of implementing scaling circuits for the presented modulo set. We would like to mention that designs were firstly transformed to VHDL codes and then using Modelsim software we plotted them in terms of design performance. After making sure of the accuracy of what we did before, they were simulated for various values using software ISE on different technologies (Virtex4 , Virtex5 & Virtex6).

Charts of implementation results in Area lines according to Slice, LUT and Latency are announced.

			Virtex 4
Latency (ns)	Area (LUT)	Area (Slice)
6.254	156	94	N=4
7.790	283	171	N=8
9.219	551	330	N=16
11.627	1086	639	N=32
16.441	2158	1308	N=64

			Virtex 5
Latency (ns)	Area (LUT)	Area (Slice)
5.371	110	44	N=4
7.054	230	84	N=8
7.628	447	164	N=16
8.012	820	322	N=32
8.961	1534	638	N=64

			Virtex 6
Latency (ns)	Area (LUT)	Area (Slice)
2.939	84	44	N=4
4.966	214	84	N=8
5.592	420	164	N=16
6.328	796	322	N=32
7.641	1492	638	N=64

In chart 1 average rate of Area (slice) column compared to Area (LUT) column is 1.6. It means the calculated area according to LUT equals 1.6 times the calculated area according to slice with the same n value.

In chart 2 increase in Area column values according to Slice compared to Area column according to LUT has an average rate of 2.56. Here again with increasing n value by 2 times, the area acquired from both Slice and LUT units has 1.93 times average rate and latency has had a growth 1.13 times average rate.

Values obtained from chart 3 show that the increase of Area column according to Alice compared to LUT is 2.32. Doubling n value, the area calculated from Slice and LUT columns have growth rate of 1.94. This value for Latency is 1.07.

With an overall look at the calculated numbers, it can be stated that in Virtex5 we observed the most average growth rate compared to areas resulting from Slice and LUT. The highest average growth rate belongs to Latency column of Virtaex6.

References

[1] Molahosseini, A. S.,Navi, K,Dadkhah, C., Kavehei, O.,Timarchi, S., (2010)." Efficient Reverse Converter Designs for the new 4-moduli SetsandBased on New CRTs". IEEE Trans. Circuits and Systems-I, 57, 823.

[2] Molahosseini, A. S., (2011). "Improving the Delay of Residue-to-Binary Converter for a Four-Moduli Set". Advances in Electrical and Computer Engineering, 11.

[3] Chang, C. H., Low, J., Y., S. (2011). "Simple,Fast and Exact RNS Scaler for the Three-Moduli Set ". IEEE Trans. Circuits and Systems-I, 58, 2686-2697.

[4] Safari, A., Cong, Y. (2012). "Simple,Fast and Synchronous Hybrid Scaling Scheme for the 8-bit Moduli Set ". Journal of Emerging Trends in Computing and Information Sciences.

[5] Anders Lindström, Michael Nordseth, Lars Bengtsson, Amos Omondi, "Arithmetic Circuits Combining Residue and Signed-Digit Representations," Proceedings of the Eighth Asia-Pacific Computer Systems Architecture Conference, vol. 2823, 2003.

[6]	G. A. Jullien, "Residue number scaling and other operations using ROM array," IEEE Transaction Coniputer, vol. 27, pp. 325-336, 1978.
[7]	F. J. Taylor and C. H. Huang, "A floating point residue arithmetic unit," vol. 311, pp. 33-43, 1981.
[8]	F. J. Taylor and C. H. Huang, "An autoscale residue multiplier," IEEE Trunsaction Computer, vol. 31, pp. 321-325, 1982.
[9]	D. D. Miller and J. W. Polky, "An implementation ol the LMS alalgorithms in residue number system," IEEE Trunsaction Circuits System, vol. 31, pp. 452-561, 1984.
[10]	A. P. Shenoy and R. Kumaresan, "Fast base extension using a redundant modulus in RNS," IEEE Transaction Computer, vol. 38, pp. 292-297, 1989.
[11]	Z. D. Ulman, M. Czyzak, J. M. Zurada, "Effective RNS scaling algorithm with the Chinese remainder theorem decomposition," IEEE Pacific Rim Confference Communication, Computer, Signal Process, pp. 528-531, 1993.
[12]	R. Zimmermenn, "Efficient VLSI Implementation of Modulo (2^n-1) Addition and Multiplication," Computer Arithmetic, pp. 158-167, Apr 1999.
[13]	R. Zimmermann, "Binary Adder Architectures for Cell-Based VLSI and their Synthesis," SWISS FEDERAL INSTITUTE OF TECHNOLOGY, ZURICH, 1997.

[14] Shenoy, M. A. P., Kumaresan, R. (1989) “A fast and accurate rns scaling technique for high speed signal processing,” IEEE Trans. Acoust, Speech, Signal Process, 37, 929–937.

[15] Ulman, M. C. Z. D., Zurada, J. M. (1993) “Effective rns scaling algorithm with the chinese remainder theorem decomposition,” IEEE Pacific Rim Conf. Commun., Computer, Signal Process, 528–531.

[16] Griffin, F. T. M., Sousa, M.( , 1988) “New scaling algorithm for the Chinese remainder theorem,” Proc. Conf. Rec. 22nd Asilomar Conf Signals, System., Computer , 375–378.

[17] Kong, Y. Phillips, B. (2009) “Fast scaling in the residue number system,”Very Large Scale Integration (VLSI) Systems, IEEE Transactions on, 17, 443 –447.

[18] Dasygenis, M., Mitroglou, K., Soudris, D., Thanailakis, D.(2008)“A full-adder-based methodology for the design of scaling operation inresidue number system,” Circuits and Systems I: Regular Papers, IEEE Transactions on. 55, 546 –558.

[19]Benardson, P. (1985) “Fast memoryless, over 64 bits, residue-to binary convertor,” Circuits and Systems, IEEE Transactions on, 32, 298 – 300.