cache-miss-analyzer

Valid-Checking LRU — a preallocated block management approach

The Valid-Checking LRU (Least Recently Used) cache is a set-associative cache implementation that pre-allocates all cache blocks at initialization. Unlike dynamically allocated caches, this approach marks blocks as valid=false when they are not in use.

Features

• Pre-allocated Blocks: All cache blocks are created at startup and stored in a fixed-size structure.

• Valid Bit Tracking: Each block has a valid flag to indicate whether it contains a tag.

Implementation Details

• Each Set contains a HashMap (tag -> Node) and a doubly linked list for LRU tracking.

• Pre-allocated fixed-size cache blocks (valid = false initially).

• Upon accessing a block:

  1. If the block exists in the cache (Hit), it is moved to the front of the list.

  2. If it does not exist (Miss), an invalid block is reused if available.

  3. If all blocks are valid=true, the least recently used (LRU) block is evicted. Then, the new block is created and moved to the front of the list.

Step-by-Step Explanation

Initial State

Empty but Preallocated Blocks.

Unlike Dynamic-Way LRU, all blocks are initialized with valid=false at the start.

First Access: A1115550

Miss! But there are still invalid blocks available.

Instead of evicting, use an invalid block.

Mark it valid=true and move it to the front.

Second Access: A1115551

Miss! But still, there are invalid blocks available.

Use an invalid block, mark it valid, move it to the front.

Third Access - A1115550

Hit! A1115550 is already in the set.

Move it to the front (most recently used).

Filling Up the Set (Set is Full)

After accessing A1115552 and A1115553, the set is full.

Every block is now valid=true, so next miss must trigger an eviction.

Access A1115560 (Eviction required)

Miss! No invalid blocks remain.

Evict LRU block (A1115551, closest to Dummy Tail).

Replace it with A1115560 and move to the front.

Another Hit – A1115550

Hit! A1115550 is in the set.

Move it to the front (MRU).

Time Complexity Analysis

Lookup (Hit/Miss Checking)

• Using HashMap<tag, Node>, checking if a block is present takes O(1).

Insert New Block (On Miss)

Two scenarios for handling a miss:

1. Use an invalid block: O(N), worst-case requires searching all set entries.
   
2. Evict LRU block (if all are valid): O(1).
   
   

Case 1: Use an invalid block Search for a valid=false block: O(N) (N = set_degree, worst case is that all blocks are valid). Update block’s tag and set valid=true: O(1). Move block to head (most recently used): O(1).

Overall: O(N) + O(1) + O(1) = O(N) (Worst case: scanning all blocks in the set to find an invalid one.)

Case 2: Evict LRU block (All blocks are valid=true) Find LRU block (always at the tail): O(1). Replace with new block, update tag, set valid=true: O(1). Move to head (most recently used): O(1).

Overall: O(1) + O(1) + O(1) = O(1)

Move Block to Head (On Hit)

• Find in HashMap: O(1).

• Remove from current position: O(1).

• Insert at the front: O(1).

Overall: O(1) + O(1) + O(1) = O(1).

Eviction (When the set is full)

• Identify LRU block (always at the tail): O(1).

• Remove from doubly linked list: O(1).

• Remove from HashMap: O(1).

• Insert new block at head: O(1).

Overall: O(1) + O(1) + O(1) + O(1) = O(1).

Summary

Operation	Complexity
Lookup	O(1)
Insert	O(N)
Move to Head	O(1)
Eviction	O(1)

Overall Complexity: O(N).

---

Getting Started

Prerequisites

• Rust (recommended 1.84.1 or higher)
• A terminal or command prompt to run cargo
  
  —

Building and Running

Clone the repository

git clone https://github.com/mellivorandy/cache-miss-analyzer.git

From the project root, run:

cargo build

To execute the program with custom arguments, use the following command:

cargo run -p valid_checking_lru -- <trace_file_name> <cache_size> <block_size> <set_degree>

• : The path of the trace file to be analyzed.
• : The total size of the cache (in KByte).
• : The size of each block (in Words).
• : The associativity (number of blocks per set).

In this project structure, the trace.txt file is located in cache-miss-analyzer/data, change the path if the trace file is moved or new trace files are added.

Note: If the file path remains unchanged, use the path as given. Simply copy and paste the following command into your terminal:

Example command

cargo run -p valid_checking_lru -- ./data/trace.txt 128 4 1

---

Test

A [cfg(test)] test module is included, referencing a trace.txt file for unit tests. To run them:

cargo test -p valid_checking_lru -- --nocapture

This prints the non-empty sets.

• Change arguments at valid_checking_lru/src/main.rs:69:39 for different cache configurations.

• Remove if expressions at valid_checking_lru/src/main.rs:92:13 as you want to print all sets.

Acknowledgments

I sincerely appreciate the incredible work behind Mermaid.js, an open-source diagramming tool that makes visualizing complex ideas effortless. Huge thanks to the developers and contributors who maintain and improve this fantastic project!

This site is open source. Improve this page.