The user has a memory machine. It has one layer for data storage and another layer for the cache. When the CPU needs data, it immediately checks in cache memory whether it has data or not. If data is present it results in CACHE HITS, else CACHE MISS, i.e., data is not in cache memory so it retrieves data from main memory

EXAMPLE:

In a direct-mapped cache, each memory address maps to exactly one cache line based on the formula address modulo cache_size. Here, the cache size is given as 16. So, to simulate this, follow these steps:

1. Initialize the cache: Create an array of size 16 to represent the cache.

2. Iterate through the sequence of memory addresses.

For each memory address:

* Calculate the cache index using the formula address modulo 16.

* Check if the cache line at the calculated index is empty or contains the same memory address. If it does, it's a cache hit. Otherwise, it's a cache miss.

* Update the cache line with the memory address.

3. Keep track of the total number of accesses, hits, and misses.

Let's simulate the direct-mapped cache with the given sequence of memory addresses: 1, 4, 8, 5, 20, 17, 19, 56, 9, 11, 4, 43, 5, 6, 9, 17.

We'll use the same cache initialization and simulation steps as before:

1. Initialization of Cache:

Cache: [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1]

2. Iterate through the sequence of memory addresses.

Accessing Memory Address 1:

Calculate cache index: 1 % 16 = 1

Cache: [-1, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1] (Cache Miss)

_ Accessing Memory Address 4:_

Calculate cache index: 4 % 16 = 4

Cache: [-1,1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1] (Cache Miss)

Accessing Memory Address 8:

Calculate cache index: 8 % 16 = 8

Cache: [-1, 1, -1, -1,4, -1, -1, -1, 8, -1, -1, -1, -1, -1, -1, -1] (Cache Miss)

Accessing Memory Address 5:

Calculate cache index: 5 % 16 = 5

Cache: [-1, 1, -1, -1, 4, 5, -1, -1, 8, -1, -1, -1, -1, -1, -1, -1] (Cache Miss)

Accessing Memory Address 20:

Calculate cache index: 20 % 16 = 4 (Collision with index 4)

Cache: [-1, 1, -1, -1, 20, 5, -1, -1, 8, -1, -1, -1, -1, -1, -1, -1] (Cache Miss)

Accessing Memory Address 17:

Calculate cache index: 17 % 16 = 1 (Collision with index 1)

Cache: [-1, 17, -1, -1, 4, 5, -1, -1, 8, -1, -1, -1, -1, -1, -1, -1] (Cache Miss)

Accessing Memory Address 19:

Calculate cache index: 19 % 16 = 3

Cache: [-1, 17, -1, 19, 4, 5, -1, -1, 8, -1, -1, -1, -1, -1, -1, -1] (Cache Miss)

Accessing Memory Address 56:

Calculate cache index: 56 % 16 = 8 (Collision with index 8)

Cache: [-1, 17, -1, 19, 4, 5, -1, -1, 56, -1, -1, -1, -1, -1, -1, -1] (Cache Miss)

Accessing Memory Address 9:

Calculate cache index: 9 % 16 = 9

Cache: [-1, 17, -1, 19, 4, 5, -1, -1, 56, 9, -1, -1, -1, -1, -1, -1] (Cache Miss)

Accessing Memory Address 11:

Calculate cache index: 11 % 16 = 11

Cache: [-1, 17, -1, 19, 4, 5, -1, -1, 56, 9, -1, 11, -1, -1, -1, -1] (Cache Miss)

Accessing Memory Address 4 (Second time):

Calculate cache index: 4 % 16 = 4

Cache: [-1, 17, -1, 19, 4, 5, -1, -1, 56, 9, -1, 11, -1, -1, -1, -1](Cache Hit)

Accessing Memory Address 43:

Calculate cache index: 43 % 16 = 11

Cache: [-1, 17, -1, 19, 4, 5, -1, -1, 56, 9, -1, 43, -1, -1, -1, -1] (Cache Miss)

Accessing Memory Address 5 (Second time):

Calculate cache index: 5 % 16 = 5

Cache: [-1, 17, -1, 19, 4, 5, -1, -1, 56, 9, -1, 43, -1, -1, -1, -1] (Cache Hit)

Accessing Memory Address 6:

Calculate cache index: 6 % 16 = 6

Cache: [-1, 17, -1, 19, 4, 5, 6, -1, 56, 9, -1, 43, -1, -1, -1, -1] (Cache Miss)

Accessing Memory Address 9 (Second time):

Calculate cache index: 9 % 16 = 9

Cache: [-1, 17, -1, 19, 4, 5, 6, -1, 56, 9, -1, 43, -1, -1, -1, -1] (Cache Hit)

Accessing Memory Address 17:

Calculate cache index: 17 % 16 = 1

Cache: [-1,17, -1, 19, 4, 5, 6, -1, 56, 9, -1, 43, -1, -1, -1, -1] (Cache Hit)

Results after processing all memory addresses:

Total accesses: 16

Hits: 3

Misses: 13

#include <stdio.h>

#define CACHE_SIZE 16

int main() {
    int cache[CACHE_SIZE];
    for (int i = 0; i < CACHE_SIZE; i++) {
        cache[i] = -1; // Initialize cache with -1 indicating empty slots
    }

    int hits = 0;
    int misses = 0;
    int total_accesses = 0;

    // Sequence of memory addresses
    int memory_addresses[] = {1, 4, 8, 5, 20, 17, 19, 56, 9, 11, 4, 43, 5, 6, 9, 17};
    int num_addresses = sizeof(memory_addresses) / sizeof(memory_addresses[0]);

    for (int i = 0; i < num_addresses; i++) {
        int address = memory_addresses[i];
        int cache_index = address % CACHE_SIZE;

        if (cache[cache_index] == address) {
            hits++;
        } else {
            misses++;
            cache[cache_index] = address;
        }
        total_accesses++;
    }

    printf("Total accesses: %d\n", total_accesses);
    printf("Hits: %d\n", hits);
    printf("Misses: %d\n", misses);

    return 0;
}
 
}    
 

When the block size increases, it improves spatial locality, meaning that if data items close to each other in memory are accessed, they are more likely to be brought into the cache together. This can lead to additional hits if subsequent accesses reference data within the same block.

Consider

• We have a direct-mapped cache with a block size equal to 4.
• The cache is organized into blocks, where each block contains four cache lines.
• When an address is accessed, it's at the block level. Tags are stored per block.
• When a miss occurs, the entire block is fetched from main memory and stored in the cache.
• Here's a breakdown of the sequence of memory accesses and their impact on the cache:

Address 1: Miss, fills block 0

Address 4: Miss, fills block 1

Address 8: Miss, fills block 2

Address 5: Hit (within same block as 4)

Address 20: Miss, replaces block 1

Address 17: Miss

Address 19: Hit (within same block as 17)

Address 56: Miss, replaces block 2

Address 9: Miss, replaces block starting from 56

Address 11: Hit (within same block as 9)

Address 4 (again): Miss, replaces block 1

Address 43: Miss, replaces block starting from 8

Address 5 (again): Hit (within same block as 4)

Address 6: Hit (within same block as 5)

Address 9 (again): Miss, replaces block starting from 56

Address 17 (again): Hit (within same block as 1)

Results:

Total accesses: 16

Hits: 6 (including additional hits due to larger block size)

Misses: 10

#include <stdio.h>

#define NUM_BLOCKS 4
#define BLOCK_SIZE 4

typedef struct {
    int cache[NUM_BLOCKS];
    int hits;
    int misses;
} DirectMappedCache;

void init_cache(DirectMappedCache *cache) {
    for (int i = 0; i < NUM_BLOCKS; i++) {
        cache->cache[i] = -1; // Initialize cache with invalid tags
    }
    cache->hits = 0;
    cache->misses = 0;
}

void access_memory(DirectMappedCache *cache, int address) {
    int block_index = address / BLOCK_SIZE;
    int cache_index = block_index % NUM_BLOCKS;

    if (cache->cache[cache_index] == block_index) {
        printf("Address %d: Hit\n", address);
        cache->hits++;
    } else {
        printf("Address %d: Miss\n", address);
        cache->cache[cache_index] = block_index;
        cache->misses++;
    }
}

int main() {
    DirectMappedCache cache;
    init_cache(&cache);

    int memory_accesses[] = {
        1, 4, 8, 5, 20, 17, 19, 56, 9, 11, 4, 43, 5, 6, 9, 17
    };
    int num_accesses = sizeof(memory_accesses) / sizeof(memory_accesses[0]);

    for (int i = 0; i < num_accesses; i++) {
        access_memory(&cache, memory_accesses[i]);
    }

    printf("\nResults:\n");
    printf("Total accesses: %d\n", num_accesses);
    printf("Hits: %d\n", cache.hits);
    printf("Misses: %d\n", cache.misses);

    return 0;
}