Question

1. What is the function of a replacement algorithm?  Do you need a replacement algorithm for direct mapping?  
2. Define the two write policies in about ten sentences total. Discuss the relative merits of the policies.  
3. Describe a simple way of implementing an LRU replacement algorithm in a 4-way set associative cache.
4. What is the impact of the design decision of line size on hit ratio?  Discuss the various approaches of cache coherency in a multiprocessor system (in about 10 sentences).  Discuss the relative merits of unified vs. split (code/data) cache design.    

Answer 1

1) Firstly let us see about the Cache Replacement algorithm. This concept is mainly used to optimize the instructions or algorithm in which a computer program or hardware structure can leverage of managing a cache of computer's information stored.

Direct mapping is one of the method in mapping techniques which is used to transfer the data from main memory to cache memory. The function is very straight forward, K mod N = i

K - Main memory block number
N - Number of cache lines
i - Cache memory line number

Of course, Replacement algorithm can be used in Direct mapping.

2) There are different write policies exist in cache policies. Let's see the below two write policies in detail.

i) Write-Through Policy: It is a central caching policies is known as write-through. Here the data is stored and written into the cache and to the primary storage device at the same time. We can leverage of this policy which ensures information will be stored safely without risk of data loss. If the computer crashes or the power goes out, data can still be recovered without issue. To keep data safe, this policy has to perform every write operation twice. The program or application that is being used must wait until the data has been written to both the cache and storage device before it can proceed. This comes at the cost of system performance but is highly recommended for sensitive data that cannot be lost. Many businesses that deal with sensitive customer information such as payment details would most likely choose this method since that data is very critical to keep intact.

ii) Write-Back Policy: This is most common policy in cache policy. This is applicable only when processing of data saving. very few instances the information will be written to the storage. This policy has some drawback over Write-Through Policy. This is no guarantee to save the data safe hence data loss is very common here. System performance is quite good since it is not storing the data in cache and storage device. Data recoverability is exchanged for system performance making this idela for applications or program. so it requires low latency and high throughput.

Please let me know if you have any questions. Happy learning!