Project - (Programming Project)

Topic - The indexing algorithm design for processor cache.

Goal:

i. Study and implement least recently used replacement policy (LRU).

ii. Design a cache indexing scheme to minimize cache conflict miss.

Introduction

In hierarchy memory system, the small memory, cache, is used to keep data temporarily for increasing the system performance. If the data is in cache, processor can get the data with high accessing speed. If the data is not in the cache, called cache miss, processor will read data from main memory. Accessing data form main memory is slower than from cache.

In set-associative or direct mapping scheme, when multiple frequently used data blocks compete for a same cache location, those data blocks will keep kick others out from cache, and results in lots of cache miss, this kind of cache misses is called the conflict misses.

Problem Definition

Give a cache with E entries and A-way set associativity. And, the addressing bus is M-bit. We need to select K = log₂E  bits among all address bits for indexing the cache.

There are totally possible valid solutions. Your job is to find a valid solution with minimal cache misses under LRU replacement policy. To facilitate this problem, we assume that the offset is 0-bit, i.e. the block size is 1 byte.

Attachment:- Assignment.zip