Problem #1 (a) Describe two key differences between write-through and write-back

Question

Problem #1
(a) Describe two key differences between write-through and write-back policy.
(b) Describe the function and differences between dirty bit, valid bit and replacement policy (such
as LRU) bits.
(c) What are the three types of cache misses? For each describe one technique for reducing the rate
of the miss type.
(d) Why are the first level caches usually split (instructions and data are in different caches) while
L2 is usually unified (instructions and data are both in the same cache)? Provide concise
reasoning.
(e) Consider a SEC (Single Error Correcting) code that protect 8 bit words with 4 parity bits. If we
read the value 375H, is there an error? If so, correct the error.
(f) Explain the given terms and their usefulness in evaluating the system reliability and
availability: Mean Time Between Failures (MTBF), Mean Time to Replacement (MTTR), and
Mean Time To Failure (MTTF).
(g) Describe the key design parameters of a cache.

Explanation / Answer

Answer)

a)

b) A dirty bit or modified bit is a bit that is associated with a block of computer memory and indicates whether or not the corresponding block of memory has been modified. The dirty bit is set when the processor writes to (modifies) this memory. The bit indicates that its associated block of memory has been modified and has not been saved to storage yet. When a block of memory is to be replaced, its corresponding dirty bit is checked to see if the block needs to be written back to secondary memory before being replaced or if it can simply be removed. Dirty bits are used by the CPU cache and in the page replacement algorithms of an operating system.

Dirty bits can also be used in Incremental computing by marking segments of data that need to be processed or have yet to be processed. This technique can be used with delayed computing to avoid unnecessary processing of objects or states that have not changed. When the model is updated (usually by multiple sources), only the segments that need to be reprocessed will be marked dirty. Afterwards, an algorithm will scan the model for dirty segments and process them, marking them as clean. This ensures the unchanged segments are not recalculated and saves processor time.

An instruction cache requires only one flag bit per cache row entry: a valid bit. The valid bit indicates whether or not a cache block has been loaded with valid data.

On power-up, the hardware sets all the valid bits in all the caches to "invalid". Some systems also set a valid bit to "invalid" at other times, such as when multi-master bus snooping hardware in the cache of one processor hears an address broadcast from some other processor, and realizes that certain data blocks in the local cache are now stale and should be marked invalid.

A data cache typically requires two flag bits per cache line – a valid bit and a dirty bit. Having a dirty bit set indicates that the associated cache line has been changed since it was read from main memory ("dirty"), meaning that the processor has written data to that line and the new value has not propagated all the way to main memory.

c)

1 Compulsory: On the first access to a block; the block must be brought into the cache; also called cold start misses, or first reference misses.

2 Capacity: Occur because blocks are being discarded from cache because cache cannot contain all blocks needed for program execution (program working set is much larger than cache capacity).

3 Conflict: In the case of set associative or direct mapped block placement strategies, conflict misses occur when several blocks are mapped to the same set or block frame; also called collision misses or interference misses.

Miss Rate Reduction Techniques:

* Increased cache capacity

* Larger block size

* Higher associativity

* Victim caches

* Hardware prefetching of instructions and data

* Pseudo-associative Caches

* Compiler-controlled prefetching

Cache Miss Penalty Reduction Techniques:

* Giving priority to read misses over writes

* Sub-block placement

* Early restart and critical word first

* Non-blocking caches

* Second-level cache (L2 )

Cache Hit Time Reduction Techniques:

* Small and simple caches

* Avoiding address translation during cache indexing

g)

There are a large number of cache implementations, but these basic design elements serve to classify cache architectures: cache size; mapping function; replacement algorithm; write policy; line size; number of caches.

Cache Size

There are several motivations for minimizing the cache size. The larger the cache, the greater the number of gates involved in addressing the cache is needed. The result is that larger caches end up being slightly slower than small ones. The available chip and board area also limits cache size.

Mapping Function

Mapping functions are used as a way to decide which main memory block occupies which line of cache. As there are less lines of cache than there are main memory blocks, an algorithm is needed to decide this. Three techniques are used, namely direct, associative and set associative, which dictate the organization of the cache.

Because the performance of the cache is very sensitive to the nature of the workload, it is impossible to arrive at a single optimum cache size.

Replacement Algorithms

For direct mapping where there is only one possible line for a block of memory, no replacement algorithm is needed. For associative and set associative mapping, however, an algorithm is needed. For maximum speed, this algorithm is implemented in the hardware. Four of the most common algorithms are: least recently used,first in first out,least frequently used, random replacement.

Write Policy

This is important because if changes were made to a line in cache memory, the appropriate changes should be made to the block in main memory before removing the line from the cache. The problems to contend with are more than one device may have access to main memory (I/O modules). If more than one processor on the same bus with its own cache is involved, the problem becomes more complex. Any change in either cache or main memory could invalidate the others.

Line Size

When a block of data is retrieved from main memory and put into the cache, the desired word and a number of adjacent words are retrieved. As the block size increases from a very small size, the hit ratio will at first increase due to the principle of locality of reference, which says that words in the vicinity of a referenced word are more likely to be referenced in the near future. As the block size increases, however, the hit ratio will decrease as the probability of reusing the new information becomes less than that of using the information that has been replaced.

Number of Caches

Two aspects of this are: Multilevel , Unified/Split

• The benefit of write-through to main memory is that it simplifies the design of the computer system. With write-through, the main memory always has an up-to-date copy of the line. So when a read is done, main memory can always reply with the requested data.

• If write-back is used, sometimes the up-to-date data is in a processor cache, and sometimes it is in main memory. If the data is in a processor cache, then that processor must stop main memory from replying to the read request, because the main memory might have a stale copy of the data. This is more complicated than write-through.

• write-through can simplify the cache coherency protocol because it doesn't need the Modifystate. The Modify state records that the cache must write back the cache line before it invalidates or evicts the line. In write-through a cache line can always be invalidated without writing back since memory already has an up-to-date copy of the line.

• a write-back architecture software that writes to memory-mapped I/O registers must take extra steps to make sure that writes are immediately sent out of the cache. Otherwise writes are not visible outside the core until the line is read by another processor or the line is evicted.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.