Department of Electrical and Computer Engineering

The University of Texas at Austin

EE 460N, Spring 2015
Study Questions
Due date: Mar. 9
Yale N. Patt, Instructor
Ben Lin, Kishore Punniyamurthy, Will Hoenig, TAs
  1. The following problem was postponed from PS2:

    An ISA supports an 8-bit, byte-addressable virtual address space. The corresponding physical memory has only 128 bytes. Each page contains 16 bytes. A simple, one-level translation scheme is used and the page table resides in physical memory. The initial contents of the frames of physical memory are shown below.

    Frame NumberFrame Contents
    0 empty
    1 Page 13
    2 Page 5
    3 Page 2
    4 empty
    5 Page 0
    6 empty
    7 Page Table

    A three-entry Translation Lookaside Buffer that uses LRU replacement is added to this system. Initially, this TLB contains the entries for pages 0, 2, and 13. For the following sequence of references, put a circle around those that generate a TLB hit and put a rectangle around those that generate a page fault. What is the hit rate of the TLB for this sequence of references? (Note: LRU policy is used to select pages for replacement in physical memory.)

    References (to pages): 0, 13, 5, 2, 14, 14, 13, 6, 6, 13, 15, 14, 15, 13, 4, 3.

    1. At the end of this sequence, what three entries are contained in the TLB?
    2. What are the contents of the 8 physical frames?
  2. A computer has an 8KB write-through cache. Each cache block is 64 bits, the cache is 4-way set associative and uses a victim/next-victim pair of bits for each block for its replacement policy. Assume a 24-bit address space and byte-addressable memory. How big (in bits) is the tag store?

  3. An LC-3b system ships with a two-way set associative, write back cache with perfect LRU replacement. The tag store requires a total of 4352 bits of storage. What is the block size of the cache? Please show all your work.

    Hint: 4352 = 212 + 28.

  4. Based on Hamacher et al., p. 255, question 5.18. You are working with a computer that has a first level cache that we call L1 and a second level cache that we call L2. Use the following information to answer the questions.

    1. What is the average access time per instruction (assume no interleaving)?
    2. What is the average access time per instruction if the main memory is 4-way interleaved?
    3. What is the average access time per instruction if the main memory is 8-way interleaved?
    4. What is the improvement obtained with interleaving?
  5. Hamacher, pg.255, question 5.13. A byte-addressable computer has a small data cache capable of holding eight 32-bit words. Each cache block consists of one 32-bit word. When a given program is executed, the processor reads data from the following sequence of hex addresses:

    200, 204, 208, 20C, 2F4, 2F0, 200, 204, 218, 21C, 24C, 2F4

    This pattern is repeated four times.

    1. Show the contents of the cache at the end of each pass throughout this loop if a direct-mapped cache is used. Compute the hit rate for this example. Assume that the cache is initially empty.

    2. Repeat part (a) for a fully-associative cache that uses the LRU-replacement algorithm.

    3. Repeat part (a) for a four-way set-associative cache that uses the LRU replacement algorithm.

  6. Below, we have given you four different sequences of addresses generated by a program running on a processor with a data cache. Cache hit ratio for each sequence is also shown below. Assuming that the cache is initially empty at the beginning of each sequence, find out the following parameters of the processor's data cache:

    Assumptions: all memory accesses are one byte accesses. All addresses are byte addresses.

    Address traces
    NumberAddress SequenceHit Ratio
    10, 2, 4, 8, 16, 320.33
    20, 512, 1024, 1536, 2048, 1536, 1024, 512, 00.33
    30, 64, 128, 256, 512, 256, 128, 64, 00.33
    40, 512, 1024, 0, 1536, 0, 2048, 5120.25
  7. This problem has been postponed to Problem Set 4

    Determine the decimal value of the following IEEE floating point numbers.

    1. 1 10000000 10100000000000000000000
    2. 0 00000000 01010000000000000000000
    3. 1 11111111 00000000000000000000000
  8. Using a residue number system with two moduli, represent all of the decimal values between 0 and 11 inclusive when the moduli are

    1. 4 and 3
    2. 6 and 2
  9. This problem has been removed from the problem set, as we did not cover Hamming code in class.
  10. Using the Booth Multiplication Algorithm, multiply the two unsigned 10-bit numbers 0011011110 and 0001110010. Show the intermediate results after each step.

  11. From Tanenbaum, 4th edition, Appendix B, 4.

    The following binary floating-point number consists of a sign bit, an excess 63, radix 2 exponent, and a 16-bit fraction. Express the value of this number as a decimal number.

    0 0111111 0000001111111111

  12. From Tanenbaum, 4th edition, Appendix B, 5.

    To add two floating point numbers, you must adjust the exponents (by shifting the fraction) to make them the same. Then you can add the fractions and normalize the result, if need be. Add the single precision IEEE floating-point numbers 3EE00000H and 3D800000H and express the normalized result in hexadecimal. ['H' is a notation indicating these numbers are in hexadecimal]

  13. From Tanenbaum, 4th edition, Appendix B, 6.

    The Tightwad Computer Company has decided to come out with a machine having 16-bit floating-point numbers. The model 0.001 has a floating-point format with a sign bit, 7-bit, excess 63 exponent and 8-bit fraction. Model 0.002 has a sign bit, 5-bit, excess 15 exponent and a 10-bit fraction. Both use radix 2 exponentiation. What are the smallest and largest positive normalized numbers on both models? About how many decimal digits of precision does each have? Would you buy either one?

  14. This problem has been postponed to Problem Set 4

    The following numbers are represented exactly with a 9-bit floating point representation, in the format of the IEEE Floating Point standard:

    -infinity, -1, 0, 5/16, 19.5, 48.

    1. How many bits are needed for the fraction?
    2. What is the bias?
    3. Write each number in in the 9-bit floating point representation, below:
      Value Representation
      48                                                 
      19.5  
      5/16  
      0  
      -1  
      -infinity