Notes:
a) The purpose of this and future homework problem sets is to
help you test your understanding of the material covered in the class.
Recognizing the benefits of peer learning, discussion of homework
problems in groups is not only allowed by encouraged. However,
you must
write the solutions in your own words.
Any evidence of plagiarism will
be regarded as academic dishonesty and dealt with accordingly.
c) Unless otherwise specified, the problem numbers below refer to the
end-of-chapter problems in the textbook.
Problem 1 [20 points] Consider
the assignment statement A = A+B+C+D.
(a) (12 points) You are asked to
translate this statement into the fewest possible assembly language
instructions, using the fewest possible processor registers. Use only
the three types assembly instructions - Load, Store,
and Add - as done for the example in the class.
(b) (4 points) Determine the total number of memory accesses (read or
write) that will be required to execute your translated assembly
language instruction and also break this number down into the number of
reads and writes. Briefly justify your answers.
(c) (4 points) The number of memory acccesses in part (b) can also be
broken down into instruction fetches, data reads, and data writes. Show
and justify this breakdown.
Problem 2 [20 points] In
preparation for this problem, read Section 3, "Von Neumann Computers"
of the article
"Can
Programming be liberatated from the von-Neumann Style", by John
Backus, 1977 Turing Award lecture from CACM, August 1978. The author
calls the interconnect between the memory and the processor "a
connecting tube that can transmit a single word between the CPU and the
store". He goes on to say:
Before a word can be sent through the
tube its address must be in the CPU; hence it must either be sent
through the tube from the store or be generated by some CPU operation.
If the address is sent from the store, then its address must either
have been sent from the store or generated in the CPU, and so on. If,
on the other hand, the address is generated in the CPU, it must be
generated either by a fixed rule (e.g., "add 1 to the program counter")
or by an instruction that was sent through the tube, in which case its
address must have been sent ... and so on.
Based on this description, consider the traffic through the tube during
the hardware execution of the assembly language program you wrote in
answer to Problem 1. Each item that is transmitted over the tube can be
classified as either address or data. Now, analyze the traffic through
the tube during the execution of every assembly language instruction
for each item transmitted indicate whether it is an address or a data
item. Then express the traffic corresponding to the address items as a
fraction of the total traffic and indicate how well this particular
instance of execution supports the hypothesis about the
von Neumann bottleneck mentioned in
the article.
Problem 3 [20 points] In Section 1.9
(Solved Problems) of the textbook, the authors only list the steps
needed to execute
non-branching type
of instructions. For this problem, you are asked to extend the
solutions to a branching instruction. Specifically, you are asked to
list the steps need to execute the machine instruction:
Branch_if_[R2]>0 LOOP
which tests the value in Register R2 and if it is greater than zero,
the program branches to the location defined by the label LOOP.
Otherwise, the next instruction in sequence is executed. Provide your
solution in two forms:
a) (10 points) in the style of the
solved problems
b) (10 points) in the style of register-transfer notation (see class
overheads for an example).
Problem 4 [20 points]: Assume a total of
three digits (including the sign
digit) are available for representing signed decimal integers in
the 9's-complement (9C) and 10's-complement (10C) representations.
Consider the following decimal signed numbers: A = -89
B = +23 C = -23 D = -11.
a) (4 points) Represent A, B, C, and D in 9C, showing all the steps.
b) (6 points) Carry out the following arithmetic in 9C and indicate if
the result overflows; show all the steps:
A+B,
B+C,
A+D
(c) (6 points) Carry out the computation in part (b) but this time do
it in 10C; show all the steps.
(d) (4 points) Convert the unsigned numbers in the given radix to the
radix desired; show all the steps of your computation:
* 8910 to radix 7.
* 0111012 to hexadecimal (i.e. radix 16).
* AE5216 to radix 4.
* 625738 to binary (i.e. radix 2).
Problem 5 [20 points]:
a) (12 points) Problem 1.7 from the
textbook.
b) (8 points) Problem 1.9 from the textbook.