The last assignment of the course was to implement a cache simulation in C++. Caches, as we know, are primarily used to access data faster than the main data storage hardware components. So some small amount of data which we need to access frequently are stored here so that lesser clock cycles are wasted on data access from main memory.

The concepts of temporal and spatial locality are important to decide which blocks of data to store in cache for it to be useful for future accesses. Temporal locality dictates that programs tend to use previously accessed memory locations frequently so we should store previously accessed data on cache so that future accesses are faster. The spatial locality dictates that we should store the data elements near the last accessed element as various constructs like loops tend to access nearby data elements frequently. A good approach to a cache implementation should take both these localities into consideration.

Cache memory needs to be fast hence its size is limited. So any implementation of cache has to be memory-efficient to cater to the needs of program in the shortest possble time. Here the concepts of hit and miss are important as they quantify the effectiveness of cache. A hit is the situation when data element to be accessed is found on cache while a miss refers to data element not found on the cache and hence has to be fetched from the main memory. For any program we have to reduce the misses to the minimum. Considering both the localities mentioned above and the fact that the cache memory is limited, we have to be memory-efficient and will have to evict less accessed memory elements to give way to frequently accessed memory elements. Thus we have follow some replacement policy to decide how to evict elements when they are not accessed frequently. This wikipedia link has various replacement policies and their applicabilities.

This replacement policy is inspired from the Adaptive Replacement Cache and uses the algorithm CLOCK to do eviction based on the setting of a page-reference bit. CLOCK is considered an approximation of LRU while also considering the frequency of accesses. The cache is divided into two lists T1 and T2 which store cache blocks based on recency and frequency. It also has two 'ghost' lists which are used to adaptively maintain the size of lists. Further information can be found from the original paper of CAR whose co-author Sorav Bansal is a professor at IIT-Delhi which sort of gives 'context' to the assignment.