IC20 Homework 4 Solved

Intensive Computation – Homework 4 

27 April 2020 

Exercise 1 

Write the function binary-toRNS that: 

-                      takes a radix-10 number X and a natural number n as input  

-                      computes the dynamic range M for the module set < m1=2n -1 ; m2=2n ; m3= 2n+1 - computes the RNS representation < x1 x2 x3 of X for the module set < m1=2n -1 ; m2=2n ; m3= 2n+1  

-                      gives as output the dynamic range M and the triple < x1 x2 x3  

Write the function Radix10-toRB that: 

-                      takes radix-10 number D as input

-                      computes the RB representation of D in canonical form as two binary strings N and R, one for normal bits and one for redundant bits

-                      gives as output the two binary strings N and R representing D   

Write the function RB-toRadix10 that: 

-                      takes two binary strings N and R representing an RB number as input

-                      computes the radix-10 associated value X  

-                      gives as output either X or an error message if an overflow occurs (with respect to the representation range corresponding to the number of bit considered) 

Write the function RB-Sum that:

-                      takes two RB numbers A and B as input  

-                      computes the sum S applying the RB table  

-                      gives as output S in RB representation

 

Write a script calling the functions above to compute the sum among a pairs of numbers randomly chosen in the range [0, M-1], where M is the dynamic range for the RNS representation with respect to a given n and module set < m1=2n -1 ; m2=2n ; m3= 2n+1 .

The script shows: i) The two random values X1 and X2, ii) the RNS representation of X1 and X2 and of the sum S=X1+X2, iii) the strings obtained with the two steps of the RB sum for the three digits of the RNS representation.  

 

Exercise 2 

Compute the time and area speedup with respect to a standard binary execution using a ripplecarry adder, when computing the sum among the K pairs of numbers randomly chosen in the range [0, M-1], (where M is the dynamic range for the RNS representation with respect to a given n and module set < m1=2n -1 ; m2=2n ; m3= 2n+1 ) in the following cases:

-                      Pipelined addition using an array adder for binary values

-                      RNS values with digits represented in binary and sum executed through ripple-carry adders for the single digits  

-                       RNS values with digits represented in RB and sum executed through application of the RB table, taking into account that the application of the table corresponds to the circuit in the picture.  

 

 

 

 

 

Show the results in two graphs: a first graph where n takes values 3, 4 and 5, and a second graph where K takes values 100, 500, 1000 (or more).

 

Remark This exercise requires only the computation of values, not the simulation of execution of the operations.