CPSC 330 - Spring 2011 - Exam 2                     Name: ___________________

True/False.  Circle either T or F.  If you circle F, write an explanation
  about why you think the statement is false.  (3 pts. each)

1.  T / F  An internal bus used to move information within a datapath is a
             separate bus than the bus used by the MAR and MDR to communicate
             with main memory.






2.  T / F  A tri-state buffer is used for ternary (base-3) logic in an ALU.






3.  T / F  Control signals are used to adapt (or tailor) a general datapath
             into the specific circuits needed to perform one or more
             register transfers each clock cycle.






4.  T / F  A control store is used for hardwired control.







5.  T / F  Locality of reference is a property of the CPU on which a program is
             running (e.g., size of the cache, degree of set associativity).







6. Identify at least three difference between DRAM and SRAM.  (6 pts.)


Consider a block diagram (high-level circuit) showing the two-dimensional
organization of a RAM, and identify the components and signals required to
access the RAM.  Place the appropriate letter, a-j, of the correct component
or signal in the blanks numbered 7-16.  (1 pt. each)

  a. address                        f. read/write control signal
  b. column decoder                 g. row decoder
  c. column address strobe (CAS)    h. row buffer
  d. data bits                      i. row address strobe (RAS)
  e. memory cell array              j. sense/write circuitry


                               7) ______        8)______
                                   +-+       +-------------+
   9) ______ --------------------->| |------>|             |
                   .--------/----->| | ...   |   4K x 4K   |
                   |   high bits   | |------>|             |
  10) ______ --/--<                +-+       +-------------+
                   |                          | |  ...  | |
                   |                         +-------------+
                   |                         | 11) ______  |<-- 12) ______
                   |                         +-------------+
                   |                   +-+    | |  ...  | |
                   |   low bits        | |-->+-------------+
                   `-------/---------->| |...| 13) ______  |
  14) ______ ------------------------->| |-->+-------------+
                                       +-+         ^   ^
                                                   |...|
                                  15) ______       v   v

                                               16) ______

17. Explain what the memory burst notation 5-1-1-1 means.  (4 pts.)











18. If the complete burst transfer in question 17 provides 32 bytes, the bus
    is clocked at 100 MHz, and there is no bus arbitration overhead, what is
    the bus bandwidth?  (4 pts.)


19. For the MIPS instruction sequence below, identify the dependencies in
    a data dependency diagram.  (8 pts.)

      i1: add $1, $2, $3  // Reg[1] <- Reg[2] + Reg[3]
      i2: ld  $4, 0($1)   // Reg[4] <- Memory[ 0 + Reg[1] ]
      i3: sub $5, $1, $4  // Reg[5] <- Reg[1] - Reg[4]

20. For the instructions in question 19 above, show the pipeline cycle
    diagrams for the 5-stage pipeline without and with forwarding.  Assume
    register file writes occur in the first half cycle and reads in the
    second half cycle.  (8 pts.)



21. Consider the code segment

       for( i = 0; i < N; i++ ){
          sum = sum + a[i];
       }

    Identify and explain the types of locality of reference present when
    running this code segment.  (8 pts.)















22. Consider a 4 GB byte-addressable main memory with a level 1 data cache
    that is five-way set-associative, 40 KB in size, has a 16-byte line size,
    and implements write-through and write-allocate.

    a) How many total lines are there in cache? (not just per bank)  (3 pts.)









    b) Show how the main memory address is partitioned into fields for the
       cache access and give the bit lengths of those fields.  (8 pts.)












    c) How many total tag comparators are there in the cache?  (2 pt.)


23. Assume a 256-byte main memory and a four-line cache with four bytes per
    line.  The cache is initially empty.  For the byte address reference
    stream (reads) given below circle which of the references are hits for
    the different cache placement schemes.  Also, show the final contents
    of the cache.  (The byte addresses are in decimal.)

    a) direct-mapped  (8 pts.)

       0,  16,  1,  31,  2,  32,  3,  17,  4,  18














    b) two-way set associative with LRU replacement  (8 pts.)

       0,  16,  1,  31,  2,  32,  3,  17,  4,  18















    c) fully-associative with FIFO replacement  (8 pts.)

       0,  16,  1,  31,  2,  32,  3,  17,  4,  18

24. Explain why a 2-bit predictor is better than a 1-bit predictor.  (5. pts)

25. Explain how an adaptive branch predictor differs from a 2-bit predictor
    and why it would be better.  (5. pts)