lru.py

def cache_block_range(word_addresses, m, n, tag_width, address_width, K):
    block_size = 2 ** m
    index_mask = (1 << n) - 1
    tag_mask = (1 << tag_width) - 1
    
    # Cache: Dictionary of lists for each set (index), each with up to K ways
    cache = {i: [{'tag': None} for _ in range(K)] for i in range(1 << n)}

    # LRU tracking: LRU[index] keeps track of LRU order for K ways in that index
    LRU = [[j for j in range(K)] for _ in range(1 << n)]

    mv_count, mt_count, hit_count = 0, 0, 0
    
    print(f"{'Address':<10}{'Miss/Hit':<20}{'Index':<10}{'Tag':<10}{'Way':<10}{'Data (word)':<25}")
    print("=" * 80)
    
    for x in word_addresses:
        base_address = (x // block_size) * block_size
        ending_address = base_address + block_size - 1
        index = (x // block_size) & index_mask
        tag = (x // block_size) >> n & tag_mask
        data_range = f"Mem[{base_address}, {ending_address}]"
        
        hit = False
        way = -1

        # Check if tag is in any way for this index (hit detection)
        for i in range(K):
            if cache[index][i]['tag'] == tag:
                hit = True
                way = i
                break
        
        if hit:
            miss_hit = "Hit"
            hit_count += 1
        else:
            # Cache miss - Check for an empty way first (valid miss)
            empty_way = next((i for i in range(K) if cache[index][i]['tag'] is None), None)

            if empty_way is not None:  # Space available
                miss_hit = "Miss-Valid"
                mv_count += 1
                way = empty_way
            else:  # No space, evict LRU block
                miss_hit = "Miss-Tag"
                mt_count += 1
                way = LRU[index].index(0)  # Find way with LRU=0

            # Store new block in the selected way
            cache[index][way]['tag'] = tag

        # Update LRU order for this index
        accessed_LRU = LRU[index][way]  # Get current LRU position of the way
        for i in range(K):
            if LRU[index][i] > accessed_LRU:
                LRU[index][i] -= 1  # Shift older entries down
        LRU[index][way] = K - 1  # Set accessed way as most recently used

        print(f"{x:<10}{miss_hit:<20}{index:<10}{tag:<10}{way:<10}{data_range:<25}")

    print(f"Total Miss-Valid: {mv_count}")
    print(f"Total Miss-Tag: {mt_count}")
    print(f"Total Hits: {hit_count}")
    print(f"Hit Rate: {hit_count / len(word_addresses) * 100:.2f}%")

    
# Example Q9b

# Example usage:
word_addresses = [12,33,67,15,73,56,89,13,68,44,46,60,63,45,54,8,79]
m = 3  
n = 0  
tag_width = 23  
address_width = 28  
K = 4 

cache_block_range(word_addresses, m, n, tag_width, address_width, K)

print("\n\n\n")
    
# Example Q9c
word_addresses = [12,33,67,15,73,56,89,13,68,44,46,60,63,45,54,8,79]
m = 1 
n = 3  
tag_width = 22  
address_width = 28  
K = 2 

cache_block_range(word_addresses, m, n, tag_width, address_width, K)

Q9b

Address   Miss/Hit            Index     Tag       Way       Data (word)              
================================================================================
12        Miss-Valid          0         1         0         Mem[8, 15]               
33        Miss-Valid          0         4         1         Mem[32, 39]              
67        Miss-Valid          0         8         2         Mem[64, 71]              
15        Hit                 0         1         0         Mem[8, 15]               
73        Miss-Valid          0         9         3         Mem[72, 79]              
56        Miss-Tag            0         7         1         Mem[56, 63]              
89        Miss-Tag            0         11        2         Mem[88, 95]              
13        Hit                 0         1         0         Mem[8, 15]               
68        Miss-Tag            0         8         3         Mem[64, 71]              
44        Miss-Tag            0         5         1         Mem[40, 47]              
46        Hit                 0         5         1         Mem[40, 47]              
60        Miss-Tag            0         7         2         Mem[56, 63]              
63        Hit                 0         7         2         Mem[56, 63]              
45        Hit                 0         5         1         Mem[40, 47]              
54        Miss-Tag            0         6         0         Mem[48, 55]              
8         Miss-Tag            0         1         3         Mem[8, 15]               
79        Miss-Tag            0         9         2         Mem[72, 79]              
Total Miss-Valid: 4
Total Miss-Tag: 8
Total Hits: 5
Hit Rate: 29.41%

Q9c


Address   Miss/Hit            Index     Tag       Way       Data (word)              
================================================================================
12        Miss-Valid          6         0         0         Mem[12, 13]              
33        Miss-Valid          0         2         0         Mem[32, 33]              
67        Miss-Valid          1         4         0         Mem[66, 67]              
15        Miss-Valid          7         0         0         Mem[14, 15]              
73        Miss-Valid          4         4         0         Mem[72, 73]              
56        Miss-Valid          4         3         1         Mem[56, 57]              
89        Miss-Tag            4         5         0         Mem[88, 89]              
13        Hit                 6         0         0         Mem[12, 13]              
68        Miss-Valid          2         4         0         Mem[68, 69]              
44        Miss-Valid          6         2         1         Mem[44, 45]              
46        Miss-Valid          7         2         1         Mem[46, 47]              
60        Miss-Tag            6         3         0         Mem[60, 61]              
63        Miss-Tag            7         3         0         Mem[62, 63]              
45        Hit                 6         2         1         Mem[44, 45]              
54        Miss-Valid          3         3         0         Mem[54, 55]              
8         Miss-Tag            4         0         1         Mem[8, 9]                
79        Miss-Tag            7         4         1         Mem[78, 79]              
Total Miss-Valid: 10
Total Miss-Tag: 5
Total Hits: 2
Hit Rate: 11.76%