CSE378 Midterm Exam
Answer all questions.
Show your work.
1. Imagine a computer with a 16 bit word. The computer is
unique in that all of the customary features of 32 bit words are present, just
smaller: For example, the exponent
field for floating point is not 8 bits, it is 6 bits.
a) What signed magnitude number is: 0000 1010
0000 1010
211 + 29 + 23 + 21
= (23 + 21)(28 + 1) = 10 x 257 = 2570
b) What two-s complement number is: 1111 0101
1111 0101
The most significant bit is a 1, so the number is negative.
Complement the bits: 0000
1010 0000 1010
Add 1: 0000
1010 0000 1011 = -2571
c) What is the 8-bit ASCII representation of: 0100
0001 0100 0010
26 + 20 = 65, which is the ASCII code
for A
26 + 21 = 66, which is the ASCII code
for B
d) What is the floating point number of: 0100
0001 0100 0010
Sign bit is 0, so the number is positive
Exponent is 26 in excess-31
notation = 1
Mantissa is normalized = 1.101000010
Number is 21 x (1 + 1/2 +
1/8 + 1/256) = 3 33/128
8 points total:
For each part:
1 point for working.
1 point for a correct answer. For part c, this included any reasonable characters if they were one apart in the ASCII code. So 'B' and 'C' would get credit, as would 'E' and 'F' etc.
2. If the short floating point numbers in the last question
followed the IEEE 754 standard, but using its smaller exponent field, show the
representation for +/- infinity that they would use?
Positive
infinity 0111 1110 0000 0000
Negative
infinity 1111 1110 0000 0000
2 points total:
1 point for showing that infinity has a positive and negative form.
1 point for the rest of the bit pattern.
3. The instruction
mul $t0, $t1, $t2
is
multiply without overflow. It is a pseudo instruction. What equivalent
code will the assembler probably generate for this instruction?
mult
$t1, $t2 OR multu $t1, $t2
mflo
$t0
2 points total:
1 point for a multiply instruction (not mul).
1 point for moving the result from the lo register.
4. Did the people who invented the MIPS ISA leave out Subtract
Immediate to save opcodes or what?
Explain.
Yes,
they did. addi with a negative immediate operand does the same task.
1 point.
5. Give a 1-bit ALU design for a machine with the following
features:
a) Bitwise AND operation, i.e.
AND(a,b)
b) Bitwise NOT operation, i.e.
NOT(a)
c) Binary addition using a "ripple adder"
d) Shift the a
operand right by one bit position, i.e. DivBy2(a)
There
is no need to handle overflow. The design should use the standard logic gates: and, or and not. Label all inputs and outputs.
16 points total:
4 points for AND
4 points for NOT
4 points for the adder
4 points for the shift
6. In twos complement binary addition what property or
properties of the operands will assure that there will be no overflow?
If
the operands have opposite signs, overflow cannot occur
1 point
7. Write a MIPS assembly language procedure to determine how
many bytes two null-terminated strings have in common before they are
differ. Specifically, in $a0 and $a1
are the addresses of two null-terminated strings. Return in $v0 the number of bytes, starting at the beginning,
that match. Recall that the strings
could both be empty, they could completely match and one could be the prefix of
the other.
addi $t0, $a0, 0 #
Copy address of first string
addi $t1, $a1, 0 #
Copy address of second string
addi $v0, $zero, 0 #
Initialize matched characters count
loop: lb $t2, 0($t0) # Load character from first
string
beq $t2, $zero, exit #
Exit if it is a null character
lb $t3, 0($t1) # Load character from second
string
bne $t2, $t3, exit #
Exit if the characters don’t match
addi $v0, $v0, 1 #
Increment matched characters count
addi $t0, $t0, 1 #
Increment first string pointer
addi $t1, $t1, 1 #
Increment second string pointer
j loop #
Start the loop body again
exit: jr $ra #
Exit from the procedure
10 points total:
2 for setting up the function (stack manipulation - if you needed to save any registers)
2 for loading the characters from memory with lb
2 for correct termination conditions (empty strings, non-equal characters)
2 for incrementing the pointers, registers
2 for returning the correct value and reseting the stack (again only if you needed to restore registers)
8. The following binary sequence is a load word
instruction
1001 1100 0100 0001 0000 0000 0000 1100
And the following
binary sequence is a branch on equal instruction
0001 0000 0100 0001 0000 0000 0000 1100
After the opcodes,
they look identical. In what way are
they not identical? Explain.
The main difference
is in the interpretation of the offset/displacement field. In the load
instruction, it is in bytes. In the branch instruction, it is in words.
2 points total:
1 for identifying the difference is in the displacement field.
1 for mentioning byte versus word offsets.
8. Write a 5 instruction sequence that takes the word whose
address is given in $a0 and changes its "endianness", i.e. switches
if from big-endian to little-endian.
This question was dropped from the midterm due to an error in the question.
9. Registers are very useful, but modern
computers tend only to have 32 general purpose registers. Explain why architects do not increase that
number.
A smaller number of
registers is faster. Increasing the registers beyond 32 slows the CPU down too
much.
1 point.