1. (1 point) Do the following Mic-1 instructions perform exactly the same operation? Explain.

a := a + a; if n then goto 0;

a := lshift(a); if n then goto 0;

Remember that shifting left by 1 bit is the same as multiplying by 2.

Ans: Eventhough the instructions have the same effect on a, the jump will not be the same. The n flag is set by the ALU not the shifter, so the first will jump if a + a is negative, the second will jump if a is negative.

2. (1 point) A cache has a 90 percent hit ratio, an access time of 10 nsec on a cache hit and an access time of 80 nsec on a cache miss. What is the effective access time?

Ans: 10 + (10%)(80) = 10 + 8 = 18 nsec

3. (1 point) In the associative cache of figure 4-28(b), what is the address of the word in the cache with the value 2131?

Ans: Address = (Block Number) * (Block Size) = 600 * 4 = 2400

4. (2 ponits) In which slot would the following address be in the direct-mapped cache described in the book? What would be the tag if it were in the cache?

E87934 (hex)

Ans: E87934 hex = 1110 1000 0111 1001 0011 0100 binary

Placing this into the format for an address

111010000111 1001001101 00

Changing each of these to hex

E87 24C 0

Tag: E87 hex

Slot: 24C hex

The 0 is not used

5. (4 points) A cache is being designed for a computer with 2**32 bytes of memory. The cache will have 2K slots and use a 16 byte-block. Compute for both an associative cache and a direct-mapped cache how many bytes the cache will occupy.

Ans: Associative

16-byte block implies 28 bits for the block number: 2**32 / 2**4 = 2**28

16-byte block implies 128 bits for the value: 16 * 8 = 128

1 bit for the valid bit

Total per slot = 157 bits

Total for cache = 157 * 2048 = 321,536 bits = 40,192 bytes

Direct-mapped

2K slots implies 11 bits of address for slot: 2048 = 2**11

16-byte block implies 4 bits of address for block: 16 = 2**4

Bits for tag in address (and slot) = 32 - 11 - 4 = 17

Bits for block in slot is 128: 16 * 8 = 128

1 bit for valid bit

Total bits in slot: 146

Total in cache: 146 * 2048 = 299,008 bits = 37,376 bytes

6. (2 points) If the program of figure 4-16 of the book were implemented using a nanostore, how many bits would the control store and the nanostore require together. How many control store bits are in the original design?

Ans:

There are 63 unique instructions in the microporgram, so the nanostore would be 63 * 32 = 2,016 bits.

The control store would need to be 6 bits wide: log 64 = 6

The control store would be 79 * 6 = 474 bits

Size for new configuration: 2016 + 474 = 2490 bits

Size for old configuration: 79 * 32 = 2528

Savings: 38 bits - not worth the trouble!

7. (2 points) Consider a machine on which 20 percent of the instructions are conditional jumps and another 10 percent are loop jumps. The conditional jumps can be predicted with 60 percent accuracy and the loop jumps can be predicted with 90 percent accuracy. The jump penalty is 4 cycles. There is no penalty for unconditional jumps or correct guesses. What is the efficiency of the pipeline on this machine? (Hint: you can modify the formula from the book 1/(1 + bPwPj), except now there are two Pw's and two Pj's).

Ans: 1 / (1 + 4(40%)(20%) + 4(10%)(10%)) = 1 / (1 + 0.32 + 0.04) = 1 / 1.36 = 73.5 %

8. (4 points) A virtual memory has a page size of 1024 words, eight virtual pages and four physical page frames. The page table is as follows:

Virtual Page Page Frame

0 3

11

2 Not in main memory

3 Not in main memory

4 2

5 Not in main memory

6 0

7 Not in main memory

a. Make a list of all the VIRTUAL ADDRESSES (not the page number) that will cause page faults.

Ans:

2048 - 3071

3072 - 4095

5120 - 6143

7168 - 8191

b. What are the physical addresses for 1024 and 5000?

Ans:

1024 is in virtual page 1, the base address for the page is 1024
The offset for 1024 within this page is 1024 - 1024 = 0
Virtual page 1 is stored in physical page 1, the base address for physical page 1 is 1024
The physical address is then the base physical address plus the offset: 1024 + 0 = 1024

5000 is in virtual page 4, the base address for the page is 4095
The offset for 5000 within the page is 5000 - 4095 = 905
Virtual page 4 is stored in physical page 2, the base address for physical page 2 is 2048
The physical address is then the base physical address plus the offset: 2048 + 905 = 2143

9. (2 points) A computer has 16 pages of virtual address space but only 4 page frames. Initially, the memory is empty. A program references the virtual pages in the order:

0,7,2,7,5,8,9,2,4

a. Which references cause page faults using LRU?

* indicates a page fault

-, -, -, 0 *
-, -, 0, 7 *
-, 0, 7, 2 *
-, 0, 2, 7
0, 2, 7, 5 *
2, 7, 5, 8 *
7, 5, 8, 9 *
5, 8, 9, 2 *
8, 9, 2, 4 *

b. Which references cause page faults using FIFO?

* indicates a page fault

-, -, -, 0 *
-, -, 0, 7 *
-, 0, 7, 2 *
-, 0, 7, 2
0, 7, 2, 5 *
7, 2, 5, 8 *
2, 5, 8, 9 *
2, 5, 8, 9
5, 8, 9, 4 *

10. (1 point) What is your name?

Ans: Tim Downey

Grade: 100, excellent job!!!