CS1200 Assignment 3 Solved

Question 0. Submission instructions 
(a)      You have named your file with your student number, i.e., AxxxxxxxY.pdf.       (1 mark)

(b)     You have submitted your assignment as a single PDF file and no multiple copies. 

(c)      Your assignment submission has your tutorial group number, student number and name at the top of the first page of your file. (All three items must be present.) (1 mark) Question 1. MSI Devices 

Note:   

▪ Boolean constants (0 and 1) are always available; ▪ Complemented literals are not available.

(a)    Given the following circuit showing a 4:1 multiplexer and an AND gate, what is the simplified

        SOP expression of the function F(A,B,C,D)?                                                                 

(b)   Implement the following Boolean function using a single 4:1 multiplexer without any logic gate. Once you have chosen the 2 variables for the selector lines, those 2 variables are not to appear in the 4 multiplexer inputs.

       No mark will be awarded if any logic gate besides the multiplexer is used.

                                          H(A,B,C,D) = m(2, 7, 10, 12, 14, 15)

      The block diagram of a 4:1 multiplexer is given in part (a) above.                              [4 marks]

 

 

(c)    Implement the following Boolean function using a single 2×4 decoder with one-enable and active high outputs, and at most one logic gate.

                                          G(A,B,C,D) = m(2, 11)

     The block diagram of a 2×4 decoder with one-enable and active high outputs is shown below.

                                                                                                                                              [4 marks]

 

 

             

(d)   Below is a partial function table of an 8-to-3 priority encoder. It consists of 8 inputs (A7 to A0) and 3 outputs (F2 to F0). Ai has higher priority than Aj for i > j. The only invalid input combination occurs when all inputs are zeroes. ‘X’ represents don’t-care.   Write out the simplified SOP expressions for F2, F1 and F0. [5 marks]

 

 

 

             


Question 2. Sequential Circuit (14 marks)
Analyze the following sequential circuit with JK flip-flops, an input x and an output z. The states are represented by ABC.  

 

 

Complete the state diagram for the circuit below. States are shown in decimal and the labels are in x/z format, where x is the input and z the output. Two arrows have been drawn for you. For ease of tracing, place a label near the start of its associated arrow. Use the same positions of the states in the diagram below to ease grading.  

 

 

                                                                     

Question 3. Pipelining (7 marks)
(Past year’s exam question)

The following MIPS code reads an integer array A, whose base address is stored in $s0, and computes some answer in $s2. The register $s1 is associated with the integer variable cutoff.

        addi $s2, $zero, 0     # Inst1: count = 0         addi $t0, $s0, 40      # Inst2: $t0 pts to A[10]                                #        i = 9,8,...,0   Here: addi $t0, $t0, -4      # Inst3: $t0 pts to A[i]         lw   $t1, 0($t0)       # Inst4: $t1 = A[i]         slt  $t2, $t1, $s1     # Inst5: if (A[i]<cutoff)         beq  $t2, $zero, Skip  # Inst6: {          addi $s2, $s2, 1       # Inst7:   count++;  }   Skip: beq  $t0, $s0, Fin     # Inst8: $t0 pts to A[0]?         j    Here              # Inst9   Fin: 
 

For parts (a) to (c) below, you are to calculate the total number of cycles required to complete the first iteration of the above code in a 5-stage MIPS pipeline, that is, instruction 1 through instruction 9. You need to count until the last stage (WB stage) of instruction 9. You may assume that all elements in array A have values that are smaller than cutoff.

(a)      In an ideal pipeline with no delays, how many cycles are needed to complete the first iteration of the code?       (1 mark)

(b)     Assume without forwarding and branch is resolved at stage 4 (MEM) stage. No branch prediction is made and no delayed branching is used. What is the total number of cycles required to complete the first iteration of the code? (2 marks)

(c)      Assume with forwarding and branch is resolved at stage 2 (ID) stage. No branch prediction is made and no delayed branching is used. What is the total number of cycles required to complete the first iteration of the code? (2 marks)

(d)     For a general array (where the array elements have random values instead of all being smaller than cutoff), how would the choice of branch prediction (that is, choosing between “branch taken” and “branch not taken”) affect the performance of this code with respect to the beq instruction in instruction 6? (2 marks)