CSC 8400-002

Examination E2

April 19, 2000

 

PROBLEM 1 [12%] List the 3 types of cache misses. For each of them, indicate one way to reduce misses of this type and the backside of that way.

No explanations are required in this problem.

 

PROBLEM 2 [8%] Assume the base CPI (also called the ideal CPI, or CPI execution)) is 1 cycle, the cache miss rate is 10% and the miss penalty is 20 cycles. If 20% of all instructions are memory access instructions (loads or stores), what is then the real CPI?

 

PROBLEM 3 [18%]

  1. There are three components to average memory access time. What are they? (Just list their names.)

  2. Write a formula for calculating the average memory access time from those three components.

  3. Which one of those three components would be reduced by adding a write buffer to a write through cache?

  4. Which one of those three components would be reduced by adding a write buffer to a write back cache?

  5. Which one of those three components would be reduced by adding a second-level cache to the memory hierarchy?

  6. Write the average memory access time formula for a 2-level cache.

 

 

PROBLEM 4 [7%] What is the difference between pages and segments? Indicate one disadvantage and one advantage of having pages over having segments.

 

 

PROBLEM 5 [20%] Assume the virtual memory size is 16 GB, the physical memory size is 512 MB, and the page size is 512 KB.

a) How many entries would a page table have?

b) How many entries would an inverted page table have?

c) Assume this is what the TLB contains:

Virtual page number Physical page number

1010 1010 1010 101

0000 0000 00

0000 0000 0000 000

0110 1000 00

1000 0100 0000 000

1111 1111 11

0000 1111 0000 111

0101 0101 01

If the virtual address of a word W is 1000 0100 0000 0001 0000 0100 1101 0100 00, what would be its physical address?

d) Further assume that the cache block size is 1 KB. The cache is direct mapped with 128 block frames (numbered 0,1,...,127) in it, and the word W from (c) is in the cache. In which block frame would it be?

PROBLEM 6 [16%] Assume we have the following characteristics for a hard disk:

 

a) How long would it take to read one sector from the disk?

b) How long would it take to read 100 sectors? (Don't assume that these sectors are consecutive. Rather, assume that they are randomly spread over the disk).

 

 

PROBLEM 7 [7%] Indicate one disadvantage and one advantage of having long-payload messages over having short-payload messages.

 

 

PROBLEM 8 [12%] Assume we have a switched interconnection network. An average message passes through 10 switches before it reaches the destination. Each switch has a delay of 30 m s (1 m s = 0.000,001 sec). In other words, every switch adds 30 m s to the time of flight. Also assume the following:

What is, approximately, the average total latency of sending a message from one node to another?

Note: "node" means "host". Switches are NOT nodes.