COMP3211/9211 04s2 Tutorial 3 (Weeks 06 & 07)
---------------------------------------------

The selection of tutorial questions is chosen to provide coverage of
topics relevant to this Session's presentation.

There are many more questions listed than it is possible to cover during
the tutorial hour. I will therefore label them as W = warmup exercise
(simple exercises that you should be able to do without coaching or
assistance - I would recommend you try these before the class); D =
discuss (these questions are prime candidates for further discussion -
you should prepare for these before the class); and F = followup (you
should attempt these as soon as possible after the tutorial class to
practice your skills, and get a different insight into tutorial questions
covered in class). Exam questions are more likely to be similar in style
to D and F type questions.

Key: SRQ = Stallings, Review Question; SP = Stallings Problem; P = Patterson &
     Hennessy Exercise (Note you will in general need to source the P problems
     in a copy of the Second Edition); Y = Yalamanchili


Hand-in Exercises
-----------------

These exercises will be marked and contribute to your final assessment
in the course.

PLEASE BE REMINDED THAT PLAGIARISM IS CONSIDERED A SERIOUS OFFENCE.
ALL STUDENTS ARE EXPECTED TO PREPARE THEIR OWN SOLUTION TO THESE
EXERCISES - COPIED WORK WILL BE PENALIZED AS DESCRIBED IN THE COURSE
OUTLINE. WHILE DISCUSSION AND EXCHANGE OF IDEAS IS PERMITTED, IN ORDER
TO AVOID PENALTIES, DO NOT SHARE, DISTRIBUTE, OR COPY WRITTEN SOLUTIONS.

PREPARE A PLAIN (ASCII) TEXT FILE AND HAND IN AT THE _START_ OF YOUR 
NEXT TUTE CLASS IN WEEKS 08/09:

Q01. In the context of a register such as the Program Counter, explain what
     is meant by 

        i) set-up time,
       ii) hold time, and
      iii) propagation delay.

     Explain also how they arise.



Warmup Exercises
----------------

Q02.  [P5.1] Describe the effect that a single stuck-at-0 fault (i.e., 
      regardless of what it should be, the signal is always 0) would have 
      on the multiplexors in the single-cycle datapath in Fig 5.19 on p. 360
      [similar to Slide 31 of Lecture L08 on Friday Week 5]. Which instructions
      [of those we based our design upon], if any, would still work? Consider
      each of the following faults separately: RegDst = 0, ALUSrc = 0,
      MemtoReg = 0, Zero [Equal] = 0.

Q03.  [P5.5]



Discussion Questions
--------------------

Q04.  During Lecture L08, on Friday of Week 5, the control for the JUMP 
      instruction was discussed. Modify the datapath in order to implement
      this instruction.

Q05.  [P5.12] Consider the following idea: Let's modify the instruction
      set architecture and remove the ability to specify an offset for memory
      access instructions. Specifically, all load-store instructions
      with non-zero offsets would become pseudoinstructions and would
      be implemented using two instructions. For example:
      
      	addi	$at, $t1, 104 	# add the offset to a temporary
	lw	$t0, $at 	# new way of doing lw $t0, 104 ($t1)

      What changes would you make to the single-cycle datapath and control
      if this simplified architecture were to be used?

Q06.  The efficiency of a single-cycle datapath was questioned during 
      lectures.

      On Slide 12 of Lecture L08 the timing for various datapath components
      was given. Let us assume the clock period is set to 11.5 ns (the 
      critical path length for a load instruction).  If loads constitute 
      24% of all instructions, 12% are stores, 44% R-format instructions, 
      and 20% are branches, compute the fraction of time a single cycle 
      datapath spends fetching and executing instructions. That is, what 
      fraction of time is the datapath _not_ simply waiting for the next 
      triggering clock edge?

Q07.  [P5.11]



Follow-up Questions
-------------------

Q08.  Read P&H pp. 373 - 375 on performance of single cycle machines.

      [P5.13] If the modifications described in Q05 are
      implemented, there are some definite trade-offs with regard
      to performance. Specifically, the cycle time may be affected,
      and all load-store instructions with nonzero offsets would now
      require an extra addi instruction (a good compiler might find
      ways to reduce the need for extra addi instructions, but you can
      ignore this). If there are too many load-store instructions with
      nonzero offsets, it is likely that the modification would not
      improve performance. Assuming delays as specified on page 373,
      what is the highest percentage of load-store instructions with
      offsets that could be tolerated (i.e., that would still result in
      the modification having a positive impact on performance)?