ক্যাশ মেমরি বেসিকস — ডিরেক্ট ম্যাপড

১ · ক্যাশ কী — হিট, মিস, লাইন ও ট্যাগ

L37-এ দেখা মেমরি হায়ারার্কির ঠিক CPU-র সবচেয়ে কাছের হার্ডওয়্যার স্তর হলো ক্যাশ। CPU যখন কোনো মেমরি অ্যাড্রেস চায়, প্রথমে ক্যাশে খোঁজা হয় — পাওয়া গেলে সেটা ক্যাশ হিট (দ্রুত), না পাওয়া গেলে ক্যাশ মিস — তখন ধীর মেইন মেমরি থেকে আনতে হয়, এবং সাধারণত ভবিষ্যতের জন্য ক্যাশেও একটি কপি রাখা হয়। প্রতিবার এক বাইট নয়, বরং একটি গোটা ক্যাশ লাইন/ব্লকCache Line / Blockক্যাশ ও মেইন মেমরির মধ্যে একবারে স্থানান্তরিত ডেটার একক — একগুচ্ছ পরপর বাইট (পরপর কয়েকটি বাইটের গুচ্ছ) স্থানান্তরিত হয় — কারণ L37-এর স্পেশিয়াল লোকালিটি অনুযায়ী কাছাকাছি ডেটাও শীঘ্রই লাগতে পারে।

২ · ডিরেক্ট ম্যাপড ক্যাশ — সবচেয়ে সরল ম্যাপিং

একটি ক্যাশ সাধারণত মেইন মেমরির তুলনায় অনেক ছোট, তাই প্রশ্ন ওঠে — কোনো মেমরি ব্লক ক্যাশের কোন লাইনে বসবে? ডিরেক্ট ম্যাপড ক্যাশ-এ উত্তরটা সবচেয়ে সরল — প্রতিটি মেমরি ব্লক ঠিক একটিমাত্র সম্ভাব্য ক্যাশ লাইনে ম্যাপ হয়, যা গণনা হয়:

$\text{index} = \text{block\_address} \bmod \text{number\_of\_cache\_lines}$

যেহেতু একাধিক ভিন্ন মেমরি ব্লক একই ইনডেক্সে ম্যাপ হতে পারে (ভিন্ন সময়ে), প্রতিটি ক্যাশ লাইনে একটি ট্যাগTagক্যাশ লাইনে বর্তমানে কোন নির্দিষ্ট মেমরি ব্লক আছে তা নিশ্চিত করার জন্য সংরক্ষিত অতিরিক্ত তথ্য রাখা হয় — সেটাই নিশ্চিত করে ঠিক কোন ব্লকটি এখন ওই লাইনে আছে, যাতে ইনডেক্স মিলে গেলেও ট্যাগ না মিললে সেটা প্রকৃত হিট নয় বলে ধরা যায়।

৩ · কোডে — একটি ডিরেক্ট ম্যাপড ক্যাশ ও একটি প্রকৃত conflict

নিচের কোড সেলে ৮টি লাইনের একটি ডিরেক্ট ম্যাপড ক্যাশ বানানো হয়েছে। address ৩ ও ১১ — এই দুটোর দূরত্ব ঠিক ৮ (number_of_cache_lines-এর সমান) — তাই দুটোই ইনডেক্স ৩-এ ম্যাপ হবে, কিন্তু ভিন্ন ট্যাগ নিয়ে। এই দুটো address পালাক্রমে বারবার অ্যাক্সেস করলে কী হয় দেখা যাক।

NUM_CACHE_LINES = 8

class DirectMappedCache:
    def __init__(self, num_lines):
        self.num_lines = num_lines
        self.lines = [{"valid": False, "tag": None} for _ in range(num_lines)]

    def access(self, address):
        index = address % self.num_lines
        tag = address // self.num_lines
        line = self.lines[index]
        if line["valid"] and line["tag"] == tag:
            result = "HIT"
        else:
            result = "MISS"
            line["valid"] = True
            line["tag"] = tag
        return index, tag, result

cache = DirectMappedCache(NUM_CACHE_LINES)

# 3 ও 11 ঠিক NUM_CACHE_LINES (=8) দূরত্বে -- একই ইনডেক্সে ম্যাপ হবে, ভিন্ন ট্যাগ নিয়ে
conflict_sequence = [3, 11, 3, 11, 3, 11]

print("address | index | tag | ফলাফল")
print("-" * 34)
results = []
for addr in conflict_sequence:
    index, tag, result = cache.access(addr)
    results.append(result)
    print(f"{addr:>7} | {index:>5} | {tag:>3} | {result}")

miss_count = results.count("MISS")
print()
print(f"মোট {len(conflict_sequence)} বার অ্যাক্সেসে {miss_count} বার MISS হয়েছে -- প্রতিবারই!")
print("লক্ষ্য করুন: 3 ও 11 উভয়েই index=3-এ পড়ে (3 mod 8 = 3, 11 mod 8 = 3) কিন্তু ট্যাগ আলাদা")
print("(0 বনাম 1) -- তাই প্রতিবার একে অপরকে evict করছে -- এটাই direct-mapped cache-এর 'conflict' সমস্যা।")