This is a an exam. You may consult your notes, any book, and the Internet. You may
not speak with any person other than Jeff Ondich, electronically or otherwise, about the content
of this exam. If you obtain relevant information from any source other than yourself,
cite your sources clearly.
Justify your answers. (Note that "justify your answers" implies "show your work.") Have fun.
(6 points) Consider our friend the datapath shown in
Figure 4.17 in Patterson and Hennessy, and imagine that we're
executing this instruction:
sw $a0, 16($sp)
Make the following assumptions:
- The sw instruction is located at address 0x04000000.
- For each k from 0 to 31, $k = 0x00001000 * k.
- For each address N in data memory, Mem[N] (i.e. the byte located at address N)
is equal to N % 256.
- When a 32-bit address is input to the data memory, the resulting 32-bit Read Data
consists of bytes in little-endian order. Similarly, 32-bit data submitted to Write Data
will be written to memory in little-endian form.
- Assume that we have executed the sw instruction up through the very end of
its clock cycle, but that the clock has not yet fallen to end the cycle.
Print (or edit as a PDF or JPG or...) Figure 4.17
and show the values of as many lines on the datapath as possible. This includes
control lines, lines whose values are used during this cycle, lines whose values
are not used during this cycle, etc. For lines where we don't have enough knowledge
of the circuitry to say, mark them as "DK" (for "don't know").
(6 points) Still using Figure 4.17, suppose the propagation delays
of the various elements are: 12 ns for memory, 6 ns for the ALU, 2 ns for the registers,
3 ns for the Control, 3 ns for the ALU Control, 2 ns for each of the multiplexors, 1 ns for
the shift left, 1 ns for the sign extend, and 1 ns for any individual gates. Also, assume that
the the PC shows the proper output immediately after the trailing clock edge.
Given these assumptions:
- How long after the trailing clock edge does it take for the
circuit's values to stabilize (i.e. before the PC input and the two Write Data values are
guaranteed to have their correct values)?
- What is the fastest clock speed (measured in clock cycles per second, or Hz)
this datapath can allow?
(6 points) Hey look, we're still using Figure 4.17. This time,
fill in this chart, with values for RegWrite and ALUSrc for each of the listed instructions:
| opcode | RegWrite | ALUSrc |
lw | 100011 | | |
sw | 101011 | | |
beq | 000100 | | |
bne | 000101 | | |
add | 100000 | | |
addi | 001000 | | |
Given this chart, and assuming these six instructions are the only ones you care about,
draw the portion of the Control that takes the opcode as input and produces RegWrite and ALUSrc
as output.
(4 points)
- Show the 32-bit IEEE 754 representation of the number -29.625.
- To what real number does the 32-bit IEEE 754 representation 0x40155555
correspond? (Hint: since the significand appears to have a repeating pattern, you
may find that extending that pattern infinitely gives you a simpler real number than
the rounded off version stored in this 32-bit float.)
(8 points) Unicode, UTF-8, and their pals.
- What is the difference between Unicode and UCS?
- Which standards organizations are responsible for Unicode and UCS?
- Who invented UTF-8, and when?
- What is the Unicode code point for the first letter in the Cherokee alphabet?
- What is the UTF-8 representation of the first letter in the Cherokee alphabet?
- Suppose you were receiving a stream of UTF-8 characters and the stream got
corrupted briefly, and then started appearing correctly again, possibly in the middle
of a character. Describe a procedure you could use to discard bytes until you were
sure you were at the beginning of a new character.
- Suppose you were receiving UCS-2 characters instead of UTF-8 characters in the
previous question? Could you reliably find the beginning of a character once the
stream started arriving correctly after the outage? Why or why not?
- If you store UTF-8 characters in a file on a big-endian system, and the same characters
on a little-endian system, will the order of bytes in the file differ? How about if
you store UCS-2 characters?
- (2 points) I just finished rereading one of my favorite books, the strange and wonderful
A Wild Sheep Chase by Haruki Murakami. What should I read next?
(6 points) Suppose you have:
- a thermometer T whose output consists of a 12-bit non-negative integer
representing the temperature in degrees Kelvin
- a clock line C
- a display device A that takes a 16-bit two's complement integer as input
and displays the result as a value in degrees Celsius (e.g. if the input is the
integer -14, then the display will show "-14°C")
- a display device B that takes a 2-bit input line and shows an up arrow (↑)
if the input is 00, a down arrow (↓) if the input is 01, a horizontal line (-)
if the input is 10, and a picture of "Bob"
if the input is 11
Draw a circuit that shows the current temperature in Celsius on A, and the temperature
trend on B, changing every time the clock line. The "trend" is defined
as "going up/up-arrow" if the current temperature is higher than the temperature during the
previous clock cycle; "going down/down-arrow" if the current temperature is lower than in the
previous clock cycle; and "steady/horizontal-line" if the previous and current temperatures
are the same.
Use the instructions from the
most recent homework assignment.
You may assume that a temperature N degrees Kelvin is equivalent to N - 273 degrees Celsius.