This exam paper of the solutions herein are provided to the students of HKUST’s Comp2611 students to check their results. It is not meant to be downloaded, printed, stored, or posted on any other media or form. Posting it on a web site other than the official course web constitute a breach of the copyright of the instructors and the University, and that implies the administrator of the web site agrees to pay the instructors and the University each US$10,000
Question 1 Multiple Choice Questions (10 points)
Please contact ZHANG Shanfeng for grade appealing
Circle all correct answers and only the correct answers as each wrong answer reduces 1 from the question’s score (until 0 is reached)
Student ID:
1.
2.
Which of the following is/are addressing mode(s) in MIPS:
A. Immediate addressing
s0
aEo
I I al53
0
B. Registeraddressing
0
C. Word addressing
D. Pseudo-random addressing
E. None of above
If array1, an array of words, stores the numbers 0, 1, 2, 3, 4, 5 (in this order). What will be final values in array1 after executing the following instructions?
baseadd ofarray 50 to to a647J
AID
3.
If the first instruction of the following sequence (i.e., addi $sp, $sp -4) is stored at memory address 0101 0000 0000 0000 1010 1011 0000 0000. What would be the value in the immediate field of the “j” instruction in binary format?
Exit:
A. 0101 0000 0000 0000 1010 1011 0000 0000
B. 0000 0000 0000 0010 1010 1100 0100
C. 00000000001010101100001000
D. 0000 0000 0000 1010 1011 0000 10
E. None of the above
A. 0, 1, 3, 3, 4, 5
B. 0, 1, 2, 3, 3, 5
C. 0,1,2,4,4,5
O
__
la $s0, array1
addi $t0, $s0, 16
lw $t1, 0($t0)
sw $t1, -4($t0)
D. 0, 1, 2, 3, 4, 4
E. None of the above
addi $sp, $sp, -4
sw $s0, 0($sp)
loop:
beq $s0,$zero, Exit
addi $s0,$s0, -1
j loop
2
This exam paper of the solutions herein are provided to the students of HKUST’s Comp2611 students to check their results. It is not meant to be downloaded, printed, stored, or posted on any other media or form. Posting it on a web site other than the official course web constitute a breach of the copyright of the instructors and the University, and that implies the administrator of the web site agrees to pay the instructors and the University each US$10,000
__
4.
5.
6.
11 11 5
When executing addi $t1, $t1, – 5, which of the following statements are correct?
A. The immediate field is extended from 16 bit to 32 bit wit zeros
B. The immediate field is extended from 16 bit to 32 bit wit ones
C. The ALU doesn’t cause an exception if an overflow occurs
D. The ALU will cause an exception if an overflow occurs
E. None of the above
Recall the refined version of the division algorithm. If we skip the final correction step which of the following statement(s) is/are correct?
A. The value of Quotient is still correct
B. The value of Quotient is doubled
C. The value of Remainder is still correct
D. The value of Remainder is doubled
E. None of above
What steps are NOT parts of the execution of an instruction?
A. Fetch the instruction
B. Encodetheinstruction
C. Resettheregisters
D. Perform an ALU operation
E. None of above
Question 2 MIPS procedure call (13 points)
Please contact WANG Keyu for grade appealing
The following C function accumulate() accumulates the elements of integer array A[] that satisfy a given condition. testfunc() is used to test the validity of such condition, and returns 1 if the condition is fulfilled and 0 otherwise.
int accumulate(int A[ ],int n) # n is size of array
{
int i;
int sum=0;
for(i=0; i
d) What is the expected output of this MIPS program? (4 points)
The total number of spaces in the null-terminated string “str”.
e) Modify line 31 (only) so that this segment of MIPS code would display the total number of ASCII characters in the string “str”. You can only use pure MIPS instructions. (5 points)
Replace “beq” by the unconditional jump “j” or replace the line with “addi $v0, $v0, 1”, etc.
Question 4 ALU design (15 points)
Please contact SU ZhiYang for grade appealing
Consider the 4-bit ALU shown below. Operations “00”, “01”, “10”, and “11” correspond respectively to “AND”, “OR”, “Result of the adder”, and “Less”.
6
Student ID:
__
This exam paper of the solutions herein are provided to the students of HKUST’s Comp2611 students to check their results. It is not meant to be downloaded, printed, stored, or posted on any other media or form. Posting it on a web site other than the official course web constitute a breach of the copyright of the instructors and the University, and that implies the administrator of the web site agrees to pay the instructors and the University each US$10,000
Student ID:
__
a) Draw the diagram of the circuit for the 1-bit ALU of bit-0. For simplification, use a black box to represent the “adder”. (5 points)
b) Draw the diagram of the circuit for the 1-bit ALU of bit-3. For simplification, use black boxes to represent the “adder” and the “overflow detection” unit. (5 points)
7
This exam paper of the solutions herein are provided to the students of HKUST’s Comp2611 students to check their results. It is not meant to be downloaded, printed, stored, or posted on any other media or form. Posting it on a web site other than the official course web constitute a breach of the copyright of the instructors and the University, and that implies the administrator of the web site agrees to pay the instructors and the University each US$10,000
c) Now assume that it takes certain time for the different logic components to generate the correct outputs based on the inputs as follows:
0.5 ns (nano second) for an inverter (NOT gate);
1 ns for a 2-input AND or OR gate;
2 ns for a 4-input AND or OR gate;
2 ns for any N-to-1 multiplexer;
3 ns for the adder to output both the result and the carryout;
5 ns for the overflow detection unit;
Finally you may assume that the propagation of a signal on wires takes no time (i.e., 0ns).
If Bnegate = 1, Operation = 10, A = 0110, and B = 0101. How long would it take for the zero output to settle (show your steps by completing the time diagram below and adding the explanation as given below)? (5 points)
E1 E2E3E4
2.5ns 3ns
3ns
3ns
E1: a0, (-b0), and CarryIn0 are ready for the adder of Bit-0 ALU. a1, (-b1) are ready for the adder of bit-1, …
E2: SumOut0 and CarryOut0 are ready;
E1-E2: Adder0
E2-E3: Mux
E3-E4: Adder1 E4-E-missing1: Mux E4-Elabelmissing: Adder2 Elabelmissing-Emissing2: Mux ElabelMissing-E5: Adder3 E5-E6: Mux
E6-E7: 4-1 OR + Not
Student ID:
__
2ns
2ns
2ns
Bit-0 ALU
Bit-1 ALU
Bit-2 ALU
Bit-3 ALU
E5E6 E7
2.5ns
3ns
2ns
8
This exam paper of the solutions herein are provided to the students of HKUST’s Comp2611 students to check their results. It is not meant to be downloaded, printed, stored, or posted on any other media or form. Posting it on a web site other than the official course web constitute a breach of the copyright of the instructors and the University, and that implies the administrator of the web site agrees to pay the instructors and the University each US$10,000
Question 5 Multiplication (15 points)
Please contact WANG Keyu for grade appealing
a) Consider the refined (last) version of the multiplication hardware is used for a 6-bit
multiplication. Given unsigned multiplicand 011110, and multiplier 010110, fill the blanks below to produce the multiplication result. (Write down the operations in the Remark column) (12 points)
Verify the solution from the blue text on
b) Suggest a simple approach to multiply signed numbers with the same hardware. (3 points)
We can add simple hardware to negate the multiplicand and the multiplier if they are negative then negate the result if the signs disagree.
9
Student ID:
__
Iteration
Multiplicand (M)
Product (P)
Remark
0
011110
000000 010110
Initial State
1
000000 010110 000000 001011
No operation P = P >> 1
2
011110 001011 001111 000101
Left(P) = Left(P) + M P = P >> 1
3
101101 000101 010110 100010
Left(P) = Left(P) + M P = P >> 1
4
010110 100010 001011 010001
No operation P = P >> 1
5
101001 010001 010100 101000
Left(P) = Left(P) + M P = P >> 1
6
010100 101000 001010 010100
No operation P = P >> 1
This exam paper of the solutions herein are provided to the students of HKUST’s Comp2611 students to check their results. It is not meant to be downloaded, printed, stored, or posted on any other media or form. Posting it on a web site other than the official course web constitute a breach of the copyright of the instructors and the University, and that implies the administrator of the web site agrees to pay the instructors and the University each US$10,000
Question 6 Single Cycle Datapath (12 points)
Please contact ZHANG Shanfeng for grade appealing
a) The following datapath is used to implement the instruction ‘or $t0, $s1, $s2’ in a single cycle. Connect the grey bullets A, B, C, D, E, and H appropriately. (2 points)
b) Using the reference card provided in appendices 1 and 2, write the binary format of the instruction or $t0, $s1, $s2 (2 points)
opcode $s1 $s2 $t0 shamt funct 000000 10001 10010 01000 00000 100101
c) Assume the values stored in registers $s1 and $s2 are 4 and 12 respectively. Fill the table below with binary values that correspond to the values available at points A, B, C, D, E, F, G and H when the Datapath above is used to execute the instruction. (8 points)
Student ID:
__
A
0000 0010 0011 0010 0100 0000 0010 0101
B
10001
C
10010
10
This exam paper of the solutions herein are provided to the students of HKUST’s Comp2611 students to check their results. It is not meant to be downloaded, printed, stored, or posted on any other media or form. Posting it on a web site other than the official course web constitute a breach of the copyright of the instructors and the University, and that implies the administrator of the web site agrees to pay the instructors and the University each US$10,000
Question 7: General Questions (15 Points)
Please contact ZHANG Shanfeng for grade appealing
Assume we want to design a pseudo-instruction “extc $s0, $s1, 5, 22” that takes two registers (e.g., $s0 and $s1) and two scalars (e.g., 5, and 22) and extracts the bits from 5 to 22 (inclusive) from $s1 and stores them in the least significant bits of $s0, filling the remaining bits with 0, as illustrated below.
31 ji0
31 j-i 0
a) Give the shortest sequences of MIPS instructions (two) that replaces
extc $s0, $s1, 5, 22 . (5 points for 2 instructions, 3 for 3 instructions, 0 for more) sll $s0, $s1, 9
srl $s0, $s0, 14
b) Given your understanding of PC-relative addressing, explain why the assembler might have problems directly implementing the branch instruction in the following code sequence
(5 points)
Here: beq $s0, $s2, There
…
There: add $s0, $s0, $s0
Student ID:
__
D
01000
E
0000 0000 0000 0000 0000 0000 0000 1100
F
0000 0000 0000 0000 0000 0000 0000 0100
G
0000 0000 0000 0000 0000 0000 0000 1100
H
0000 0000 0000 0000 0000 0000 0000 1100
field
00… 000
field
11
This exam paper of the solutions herein are provided to the students of HKUST’s Comp2611 students to check their results. It is not meant to be downloaded, printed, stored, or posted on any other media or form. Posting it on a web site other than the official course web constitute a breach of the copyright of the instructors and the University, and that implies the administrator of the web site agrees to pay the instructors and the University each US$10,000
Since label There fits on 16 bits only and is an offset with respect to ‘Here’, if the resulting address is too far away (16-bit is not able to describe it), the assembler might have problems replacing label There with an appropriate scalar when translating the program into binary. In other words, if there is more than 32KWords between Here+4 and There then the assembler will not be able to represent it
Show how the assembler might rewrite this code sequence to solve the problem and explain why. (5 points)
Here: bne $s0, $s2, Next j There
Next: …
There: add $s0, $s0, $s0
This will work as long as NextThere) is less than 256MB or 64KWords. The loader will be in charge also of positioning the program in memory such that both Next and There have the same upper 4 bits.
…
There: add $s0, $s0, $s0
This also may have a problem, There are other possibilities e.g. Jump register also
Student ID:
__
12
This exam paper of the solutions herein are provided to the students of HKUST’s Comp2611 students to check their results. It is not meant to be downloaded, printed, stored, or posted on any other media or form. Posting it on a web site other than the official course web constitute a breach of the copyright of the instructors and the University, and that implies the administrator of the web site agrees to pay the instructors and the University each US$10,000
Appendix 1 : MIPS instructions 1
13
Student ID:
__
This exam paper of the solutions herein are provided to the students of HKUST’s Comp2611 students to check their results. It is not meant to be downloaded, printed, stored, or posted on any other media or form. Posting it on a web site other than the official course web constitute a breach of the copyright of the instructors and the University, and that implies the administrator of the web site agrees to pay the instructors and the University each US$10,000
Appendix 2: MIPS instructions 2
14
Student ID:
__
This exam paper of the solutions herein are provided to the students of HKUST’s Comp2611 students to check their results. It is not meant to be downloaded, printed, stored, or posted on any other media or form. Posting it on a web site other than the official course web constitute a breach of the copyright of the instructors and the University, and that implies the administrator of the web site agrees to pay the instructors and the University each US$10,000
Appendix 3: ASCII Code Table
15
Student ID:
__