Spaces:
Runtime error
Runtime error
File size: 6,606 Bytes
6a8abde | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 | """
Simple Cache Simulator for Memory Access Pattern Analysis
Simulates a simple set-associative cache to analyze cache behavior
for different GEMM loop orderings.
"""
import numpy as np
from typing import List, Tuple, Dict
from collections import OrderedDict
class CacheSimulator:
"""Simulates a simple set-associative cache."""
def __init__(self, cache_size: int = 32768, line_size: int = 64,
associativity: int = 8, element_size: int = 8):
"""
Initialize cache simulator.
Args:
cache_size: Total cache size in bytes (default: 32KB)
line_size: Cache line size in bytes (default: 64B)
associativity: Set associativity (default: 8-way)
element_size: Size of each matrix element in bytes (default: 8B for double)
"""
self.cache_size = cache_size
self.line_size = line_size
self.associativity = associativity
self.element_size = element_size
# Calculate number of sets
self.num_lines = cache_size // line_size
self.num_sets = self.num_lines // associativity
# Cache storage: dict of sets, each set is an OrderedDict (LRU)
self.cache = {i: OrderedDict() for i in range(self.num_sets)}
# Statistics
self.hits = 0
self.misses = 0
self.accesses = 0
self.hit_rate_history = []
def reset(self):
"""Reset cache and statistics."""
self.cache = {i: OrderedDict() for i in range(self.num_sets)}
self.hits = 0
self.misses = 0
self.accesses = 0
self.hit_rate_history = []
def _get_address(self, matrix_base: int, row: int, col: int, n: int) -> int:
"""
Calculate memory address for matrix[row][col].
Args:
matrix_base: Base address of the matrix
row: Row index
col: Column index
n: Matrix dimension
Returns:
Memory address
"""
# Assume row-major layout
offset = (row * n + col) * self.element_size
return matrix_base + offset
def _parse_address(self, address: int) -> Tuple[int, int, int]:
"""
Parse address into tag, set index, and block offset.
Returns:
(tag, set_index, block_offset)
"""
block_offset = address % self.line_size
set_index = (address // self.line_size) % self.num_sets
tag = address // (self.line_size * self.num_sets)
return tag, set_index, block_offset
def access(self, address: int) -> bool:
"""
Simulate a cache access.
Args:
address: Memory address to access
Returns:
True if hit, False if miss
"""
tag, set_index, _ = self._parse_address(address)
cache_set = self.cache[set_index]
self.accesses += 1
hit = False
if tag in cache_set:
# Cache hit - move to end (most recently used)
cache_set.move_to_end(tag)
self.hits += 1
hit = True
else:
# Cache miss
self.misses += 1
# Add to cache
cache_set[tag] = True
# Evict if set is full (LRU)
if len(cache_set) > self.associativity:
cache_set.popitem(last=False) # Remove least recently used
# Record hit rate periodically
if self.accesses % 100 == 0:
self.hit_rate_history.append(self.get_hit_rate())
return hit
def simulate_accesses(self, tracks: List[Tuple], matrix_size: int,
matrix_bases: Dict[str, int] = None) -> Dict:
"""
Simulate cache behavior for a sequence of memory accesses.
Args:
tracks: List of access patterns from GEMMSimulator
matrix_size: Size of matrices (n x n)
matrix_bases: Base addresses for matrices A, B, C
Returns:
Dictionary with cache statistics
"""
if matrix_bases is None:
# Default base addresses (like in the original code)
matrix_bases = {
'A': 0x10000,
'B': 0x20000,
'C': 0x30000
}
self.reset()
for a_pos, b_pos, c_pos in tracks:
# Access A[i][k]
addr_a = self._get_address(matrix_bases['A'], a_pos[0], a_pos[1], matrix_size)
self.access(addr_a)
# Access B[k][j]
addr_b = self._get_address(matrix_bases['B'], b_pos[0], b_pos[1], matrix_size)
self.access(addr_b)
# Access C[i][j] (read-modify-write, count as 2 accesses)
addr_c = self._get_address(matrix_bases['C'], c_pos[0], c_pos[1], matrix_size)
self.access(addr_c)
self.access(addr_c)
return self.get_statistics()
def get_hit_rate(self) -> float:
"""Calculate current cache hit rate."""
if self.accesses == 0:
return 0.0
return (self.hits / self.accesses) * 100
def get_statistics(self) -> Dict:
"""
Get cache statistics.
Returns:
Dictionary containing cache performance metrics
"""
return {
'total_accesses': self.accesses,
'hits': self.hits,
'misses': self.misses,
'hit_rate': self.get_hit_rate(),
'miss_rate': 100 - self.get_hit_rate(),
'hit_rate_history': self.hit_rate_history.copy(),
'cache_config': {
'cache_size': self.cache_size,
'line_size': self.line_size,
'associativity': self.associativity,
'num_sets': self.num_sets
}
}
if __name__ == '__main__':
# Test the cache simulator
from gemm_simulator import GEMMSimulator
print("Testing Cache Simulator...")
# Create GEMM simulator
gemm = GEMMSimulator(n=16, block_size=4)
# Test different loop orders
cache = CacheSimulator(cache_size=32768, line_size=64, associativity=8)
for loop_order in ['ijk', 'kji']:
tracks = gemm.simulate(loop_order, blocked=True)
stats = cache.simulate_accesses(tracks, matrix_size=16)
print(f"\n{loop_order.upper()} Loop Order:")
print(f" Total accesses: {stats['total_accesses']}")
print(f" Hits: {stats['hits']}")
print(f" Misses: {stats['misses']}")
print(f" Hit rate: {stats['hit_rate']:.2f}%")
print("\n✓ Cache Simulator module working correctly!")
|