Cache Simulator
Cache Simulator
একটা memory access trace খেয়ে configurable size/line-size/associativity/replacement-policy অনুযায়ী hit-miss simulate করা — তারপর sequential, strided, আর random ট্রেস দিয়ে locality আর conflict miss নিজের চোখে সংখ্যায় দেখা।
কেন এই প্রজেক্ট
Cache organization আর cache policies লেসনে আমরা দেখেছি cache কেন কাজ করে (locality), কীভাবে একটা address-কে tag/index/offset-এ ভাঙা হয়, আর direct-mapped বনাম set-associative-এর মধ্যে trade-off কী। কিন্তু “conflict miss” শব্দটা পড়া, আর একটা প্রোগ্রামকে ইচ্ছাকৃতভাবে থ্র্যাশ করিয়ে নিজের চোখে hit rate শূন্যে নেমে যেতে দেখা — সম্পূর্ণ ভিন্ন অভিজ্ঞতা।
এই প্রজেক্টে একটা cache simulator বানাব যেটা কোনো real hardware লাগে না — শুধু একটা memory access trace (ঠিকানার একটা তালিকা) নেয়, আর বলে দেয় hit না miss। সহজ শোনালেও এই একটা simulator দিয়েই আমরা প্রমাণ করব:
- কেন sequential array access-এ hit rate প্রায় ৯৪% (locality কাজ করছে)
- কেন একটা নির্দিষ্ট stride-এ access করলে direct-mapped cache একদম শূন্য শতাংশ hit rate দেয় — cache-টা কার্যত অকেজো হয়ে যায়, যদিও পুরো working set cache-এর চেয়ে ছোট
- কেন সেই একই trace-এ associativity বাড়ালে hit rate নাটকীয়ভাবে বেড়ে যায়, কিন্তু একটা পয়েন্টের পরে আরও বাড়ালে কোনো লাভ হয় না (diminishing returns)
Address split — সূত্র
একটা cache-এর তিনটা প্যারামিটার থেকে সব বিট-সংখ্যা বের হয়:
num_lines = cache_size / line_size
num_sets = num_lines / associativity
offset_bits = log2(line_size) # লাইনের ভেতরে কোন বাইট
index_bits = log2(num_sets) # কোন সেট
tag_bits = বাকি সব উপরের বিট # সেই সেটে কোন লাইন, এটাই লাইনটাকে uniquely চেনায়associativity = 1 হলে direct-mapped (প্রতি সেটে ১টা লাইন, num_sets = num_lines)। associativity = num_lines হলে fully-associative (num_sets = 1, index_bits = 0 — সব লাইন এক সেটে)। এই দুটোই একই সূত্রের প্রান্তিক কেস, আলাদা কোড লাগে না।
উদাহরণ: 4KB cache, 64B line, direct-mapped। num_lines = 4096/64 = 64, offset_bits = log2(64) = 6, index_bits = log2(64) = 6, tag_bits = 32 - 6 - 6 = 20 (৩২-বিট ঠিকানা ধরে নিলে)।
address 0x1234-এর জন্য split হাতে-গণনা করলে:
0x1234 = 0001 0010 0011 0100 (বাইনারিতে)
offset = নিচের ৬ বিট = 110100 = 0x34 = 52
index = তার পরের ৬ বিট = 001000 = 8
tag = বাকি উপরের বিট = 0x1ধাপে ধাপে
১. log2 হেল্পার
Parameter-গুলো সবসময় ২-এর ঘাত (power of two) হবে ধরে নিয়ে একটা সাধারণ হেল্পার:
def log2(x):
n = 0
while x > 2 ** n:
n += 1
assert x == 2 ** n, f"{x} 2-এর ঘাত না"
return n২. Cache ক্লাস — কনস্ট্রাক্টর ও address split
class Cache:
def __init__(self, size_bytes, line_bytes, associativity):
self.line_bytes = line_bytes
self.num_lines = size_bytes // line_bytes
# associativity='fully' দিলে num_lines-ই associativity ধরা হয়
self.assoc = associativity if associativity != 'fully' else self.num_lines
assert self.num_lines % self.assoc == 0
self.num_sets = self.num_lines // self.assoc
self.offset_bits = log2(line_bytes)
self.index_bits = log2(self.num_sets)
# প্রতিটা সেট = একটা list, front=LRU (সবচেয়ে পুরনো), back=MRU (সবচেয়ে সাম্প্রতিক)
self.sets = [[] for _ in range(self.num_sets)]
self.hits = 0
self.misses = 0
def split(self, addr):
offset = addr & (self.line_bytes - 1)
index = (addr >> self.offset_bits) & (self.num_sets - 1)
tag = addr >> (self.offset_bits + self.index_bits)
return tag, index, offset৩. access() — LRU replacement সহ hit/miss
def access(self, addr):
tag, index, offset = self.split(addr)
line_set = self.sets[index]
if tag in line_set:
self.hits += 1
line_set.remove(tag)
line_set.append(tag) # MRU-তে সরিয়ে নেওয়া
return True
self.misses += 1
if len(line_set) >= self.assoc:
line_set.pop(0) # সেট ভর্তি হলে LRU (front) evict
line_set.append(tag)
return False
def hit_rate(self):
total = self.hits + self.misses
return self.hits / total if total else 0.0এই তিনটা মেথডই সম্পূর্ণ cache simulator — direct-mapped, N-way, fully-associative সবকিছু একই কোড, শুধু constructor-এ associativity প্যারামিটার বদলে দিলেই হয়।
৪. Trace generator — তিন ধরনের access pattern
import random
def sequential_trace(n, start=0, stride=4):
"""একটা array ধারাবাহিকভাবে হাঁটা — ভালো locality।"""
return [start + i * stride for i in range(n)]
def strided_conflict_trace(passes, addrs):
"""একগুচ্ছ ঠিকানা বারবার ঘোরানো — associativity-র উপর নির্ভরশীল।"""
return addrs * passes
def random_trace(n, addr_range):
"""কোনো locality নেই — baseline হিসেবে।"""
return [random.randrange(0, addr_range) for _ in range(n)]৫. Demo ১ — pathological direct-mapped, বনাম 4-way
৪টা ঠিকানা বেছে নিন যেগুলোর মধ্যে দূরত্ব ঠিক cache-সাইজের সমান (4096) — তাহলে direct-mapped cache-এ ওরা সবাই একই index-এ পড়ে:
CACHE_SIZE, LINE = 4096, 64
addrs = [0, 4096, 8192, 12288]
trace = addrs * 4 # ৪ পাস = ১৬টা access
for assoc, label in [(1, 'direct-mapped'), (4, '4-way')]:
c = Cache(CACHE_SIZE, LINE, assoc)
for a in trace:
c.access(a)
print(f"{label:15s} hits={c.hits:2d} misses={c.misses:2d} hit_rate={c.hit_rate():.3f}")আসল আউটপুট:
direct-mapped hits= 0 misses=16 hit_rate=0.000
4-way hits=12 misses= 4 hit_rate=0.750Direct-mapped-এ প্রতিটা access miss — কারণ ৪টা ঠিকানাই একই সেটে পড়ে আর সেই সেটে জায়গা মাত্র ১টা লাইনের; প্রতিবার নতুন ঠিকানা এলে আগেরটা evict হয়ে যায়, তাই পরের পাসে আবার miss। ৪-way-তে সেই একই সেটে ৪টা লাইনের জায়গা আছে — প্রথম পাসে ৪টা compulsory miss হয়ে সব ভরে যায়, তারপর বাকি ১২টা access-ই hit। এটাই conflict miss-এর সবচেয়ে পরিষ্কার প্রদর্শনী — cache-এর মোট আকার একই রেখে শুধু associativity বদলানোয় hit rate 0% থেকে 75%-এ চলে গেল।
৬. Demo ২ — Associativity sweep, diminishing returns
এবার ৮টা কনফ্লিক্টিং ঠিকানা, ৬ পাস, বিভিন্ন associativity-তে চালিয়ে দেখুন:
addrs8 = [i * CACHE_SIZE for i in range(8)]
trace8 = addrs8 * 6 # ৪৮টা access
for assoc in [1, 2, 4, 8, 16, 32, 'fully']:
c = Cache(CACHE_SIZE, LINE, assoc)
for a in trace8:
c.access(a)
print(f"assoc={c.assoc:2d} hit_rate={c.hit_rate():.3f}")আসল আউটপুট:
| associativity | num_sets | hit rate |
|---|---|---|
| 1 (direct-mapped) | 64 | 0.000 |
| 2 | 32 | 0.000 |
| 4 | 16 | 0.000 |
| 8 | 8 | 0.833 |
| 16 | 4 | 0.833 |
| 32 | 2 | 0.833 |
| fully (64-way) | 1 | 0.833 |
লক্ষ্য করুন এটা একটা মসৃণ বক্ররেখা না — একটা ধাপ। যতক্ষণ associativity কনফ্লিক্টিং ঠিকানার সংখ্যার (৮টা) চেয়ে কম, hit rate শূন্যই থাকে — একটা সেটে ৮টা distinct tag রাখার জায়গা নেই। associativity ৮-এ পৌঁছাতেই সব ঠিকানা একসাথে থাকার জায়গা পেয়ে যায়, hit rate লাফিয়ে 83.3%-এ ওঠে (৬ পাসের প্রথমটায় ৮টা compulsory miss বাদে বাকি ৪০টাই hit)। এরপর associativity আরও বাড়ালে — ১৬, ৩২, এমনকি fully-associative-এও — কোনো অতিরিক্ত লাভ নেই, কারণ working set ইতিমধ্যেই পুরোপুরি ধরে ফেলা হয়েছে। এটাই “diminishing returns” কথাটার আসল মানে — associativity একটা নির্দিষ্ট working-set সাইজের পরে বিনিয়োগ-অনুপাতে ফেরত দেওয়া বন্ধ করে দেয়, যে কারণে বাস্তব CPU-তে ৮-way বা ১৬-way-এর বেশি খুব একটা দেখা যায় না — hardware খরচ বাড়ে, বাস্তব প্রোগ্রামের জন্য লাভ প্রায় শূন্য।
৭. Demo ৩ — Sequential বনাম random বনাম strided-conflict
একই 4KB direct-mapped cache-এ তিন ধরনের trace:
c = Cache(CACHE_SIZE, LINE, 1)
seq = sequential_trace(2000, start=0, stride=4) # ৪-বাইট int অ্যারে হাঁটা
for a in seq: c.access(a)
print(f"sequential hit_rate={c.hit_rate():.3f}") # 0.938
c = Cache(CACHE_SIZE, LINE, 1)
rnd = random_trace(2000, 2 ** 20) # 1MB রেঞ্জে random
for a in rnd: c.access(a)
print(f"random hit_rate={c.hit_rate():.3f}") # 0.004
c = Cache(CACHE_SIZE, LINE, 1)
strided = strided_conflict_trace(500, addrs) # আগের ৪টা conflicting ঠিকানা
for a in strided: c.access(a)
print(f"strided hit_rate={c.hit_rate():.3f}") # 0.000| Trace | hit rate | ব্যাখ্যা |
|---|---|---|
| Sequential (stride 4) | 93.8% | একটা 64-বাইট লাইনে ১৬টা int ধরে — প্রতি লাইনে ১টা miss, বাকি ১৫টা hit (15/16 = 0.9375) |
| Random (1MB রেঞ্জে) | 0.4% | কোনো locality নেই — প্রতিটা access প্রায় নিশ্চিতভাবেই একটা নতুন লাইন |
| Strided-conflict | 0.0% | Demo ১-এর মতোই থ্র্যাশিং — worst-case locality-ও না, কিন্তু address pattern-টাই cache-এর index-mapping-এর সাথে সংঘর্ষে বাধে |
এই তিনটা সংখ্যা একসাথে দেখলে বোঝা যায় hit rate শুধু “কতটা locality আছে” তার উপর নির্ভর করে না — access pattern cache-এর geometry-র সাথে কীভাবে মেলে (বা সংঘর্ষ বাধায়) সেটার উপরও নির্ভর করে। Random trace-এর hit rate strided-conflict-এর চেয়ে সামান্য বেশি (0.4% বনাম 0.0%) কারণ random-এ মাঝে মাঝে কাকতালীয়ভাবে একই লাইনে দুইবার পড়ে যায়, কিন্তু strided-conflict-এ সেই সুযোগও নেই — প্রতিটা access ইচ্ছাকৃতভাবে ঠিক আগেরটাকে evict করা ঠিকানায় যায়।
নিজেকে চ্যালেঞ্জ করুন
- FIFO ও random replacement —
access()-এর eviction লজিক বদলে (হিট-এ move-to-back বাদ দিলেই FIFO হয়ে যায়) LRU-র সাথে তুলনা করুন একই trace-এ - Write policy — write-through বনাম write-back simulate করুন, একটা
dirtyবিট প্রতি লাইনে যোগ করে, আর মোট “memory-এ লেখা” event গুনে দুটোর পার্থক্য দেখান - Multi-level cache — L1 miss হলে L2-তে চেক করুন, L1 আর L2 উভয়ের hit rate আলাদাভাবে রিপোর্ট করুন
- বাস্তব trace —
valgrind --tool=lackey --trace-mem=yesদিয়ে একটা প্রকৃত প্রোগ্রামের memory trace জেনারেট করে সেটা এই simulator-এ চালান — synthetic pattern-এর বদলে বাস্তব প্রোগ্রামের locality দেখুন - AMAT (Average Memory Access Time) — hit rate-এর সাথে hit-latency আর miss-penalty যোগ করে
AMAT = hit_time + miss_rate × miss_penaltyসূত্রে বাস্তব cycle-cost হিসাব করুন
এটা যেখানে গিয়ে মিশবে
| এখানে যা শিখলেন | পরে কোথায় লাগবে |
|---|---|
| Address split (tag/index/offset), associativity trade-off | Level 11 — Advanced Architecture-এর cache coherence, NUMA আলোচনা |
| Conflict miss-এর সংখ্যাভিত্তিক প্রমাণ | Level 4 (OS)-এর page table/TLB — একই ধরনের ইনডেক্সিং সমস্যা, ভিন্ন প্রসঙ্গে |
| LRU replacement বাস্তবায়ন | Level 4 — page replacement policy (LRU, clock algorithm) |
| Diminishing-returns চিন্তাভাবনা (associativity বাড়ানো) | Level 11 — performance engineering-এ profiling ও bottleneck খোঁজা |
| Synthetic trace ডিজাইন করে নির্দিষ্ট behavior বের করা | Level 6 — algorithm-এর cache-friendliness বিশ্লেষণ (cache-oblivious algorithms) |