05-10-12

1. Consider a machine with a byte addressable main memory of 2¹⁶ bytes and block size of 8 bytes. Assume that a direct mapped cache consisting of 32 lines is used with this machine.
   1. How is the 16-bit memory address divided into tag, line number, and byte number?
   2. Into what line would bytes with each of the following addresses be stored?

      0001 0001 1001 1011

      1100 0011 0010 0100

      1010 1010 0110 1010

   3. Suppose the byte with address 0001 0001 1001 1011 is stored in the cache.What are the addresses of the other bytes stored along with this?
   4. How many total bytes of memory can be stored in the cache?
   5. Why is the tag also stored in the cache?
2. In a cache-based memory system using FIFO for cache page replacement, it is found that the cache hit ratio H is unacceptedly low. The following proposals are made for increasing H:
   1. Increase the cache page size.
   2. Increase the cache storage capacity.
   3. Increase main memory capacity.
   4. Replace the FIFO policy by LRU.

   Analyse each proposal to determine its probable impact on H.

3. Consider a system containing a 128-byte cache. Suppose that set-associative mapping is used in the cache, and that there are four sets each containing four lines. The physical address size is 32-bits, and the smallest addressable unit is the byte.
   1. Draw a diagram showing the organization of the cache and indicating how physical addresses are related to cache addresses.
   2. To what lines of the cache can the address 000010AF₁₆ be assigned?
   3. If the addresses 000010A₁₆ and FFFF7Axy₁₆ are simultaneously assigned to the same cache set, what values can the address digits x and y have?
4. Discuss briefly the advantages and disadvantages of the following cache designs which have been proposed and in some cases implemented. Identify three nontrivial advantages or disadvantages (one or two of each) for each part of the problem:
   1. An instruction cache, which only stores program code but not data.
   2. A two-level cache, where the cache system forms a two level-memory hierarchy by itself. Assume that the entire cache subsystem will be built into the CPU.
5. A set associative cache comprises 64 lines, divided into four-line sets. The main memory contains 8K block of 64 words each. Show the format of main memory addresses.
6. A two-way set associative cache has lines of 16 bytes and a total size of 8 kbytes. The 64-Mbyte main memory is byte addressable. Show the format of main memory addresses.
7. Consider a 32-bit microprocessor that has an on-chip 16-Kbyte four-way set associative cache. Assume that the cache has a line size of four 32-bit words. Draw a block diagram of this cache showing its organization and how the different address field are used too determine a cache hit/miss. Where in the cache is the word from memory location ABCDE8F8₁₆ mapped?
8. Express the following numbers in IEEE 32-bit floating-point format:
9. a. -5 b. -1.5 c. 384 d. 1/16 e. -1/32
10. The following numbers use the IEEE 32-bit floating-point format. What is equivalent in decimal value?
    1. 1 10000110 11000000000000000000000
    2. 0 10000001 00000000000000000000000
11. What would be bias for value for
    1. A base-8 exponent (b=8) in a 5-bit field?
    2. A base-16 exponent (B=16) in a 6-bit field?
12. A new microprocessor is being designed with conventional architecture employing single-address instructions and 8-bit words. Due to physical size constraints, only eight distinct 3-bit opcodes are allowed. The use of modifiers or the address field to extend the opcode is forbidden.
    1. What eight instructions would you implement? Specify the operations performed by each instruction as well as the location of its operands.
    2. Demonstrate that your instruction set is functionally complete in some reasonable sense; or if it is not, describe an operation that cannot be programmed using your instruction set.