Cache Organization — বিশাল ঠিকানাকে ছোট array-তে গুঁজে দেওয়া

Address-কে তিন ভাগে ভাঙা — tag, index, offset

প্রতিটা cache design একটা memory address-কে তিনটা অংশে ভাগ করে দেখে:

• Offset — cache line-এর ভেতরে কোন বাইট, সেটা নির্দেশ করে।
• Index — cache-এর কোন slot (বা slot-এর group) এই ঠিকানা ব্যবহার করবে, সেটা নির্দেশ করে।
• Tag — সেই slot-এ ঠিক কোন memory ঠিকানার ডেটা আছে, সেটা নিশ্চিত করার জন্য বাকি সব বিট।

একটা concrete উদাহরণ দিয়ে derive করা

ধরুন 32-বিট address, cache আকার 4 KB (4096 বাইট), line আকার 64 বাইট, direct-mapped (প্রতি address-এর জন্য ঠিক একটা সম্ভাব্য line — এই লেসনের পরের অংশে বিস্তারিত)।

ধাপ ১ — Offset বিট: একটা line-এ 64 বাইট আছে, তাই সেই 64টা বাইটের মধ্যে একটাকে চিহ্নিত করতে লাগবে: $\log_2(64) = 6 \text{ বিট}$

ধাপ ২ — মোট line সংখ্যা, তাই index বিট: cache-এ মোট line সংখ্যা: $\frac{\text{cache আকার}}{\text{line আকার}} = \frac{4096}{64} = 64 \text{টা line}$

64-টা line-এর একটাকে চিহ্নিত করতে লাগবে: $\log_2(64) = 6 \text{ বিট}$

ধাপ ৩ — বাকি সব বিট tag: $32 - 6 (\text{offset}) - 6 (\text{index}) = 20 \text{ বিট}$

যাচাই: 20 + 6 + 6 = 32 — ঠিক address-এর প্রস্থের সমান। ✓

   বিট:  31                      12  11        6  5         0
        ┌──────────────────────────┬────────────┬────────────┐
        │      tag (20 বিট)         │ index (6)  │ offset (6) │
        └──────────────────────────┴────────────┴────────────┘
         "কোন memory location"      "কোন line"    "line-এর কোন বাইট"

Direct-mapped cache — প্রতি ঠিকানার একটাই সম্ভাব্য বাড়ি

Direct-mapped cache-এ প্রতিটা memory address-এর জন্য ঠিক একটা cache line সম্ভব — index বিট সরাসরি বলে দেয় কোনটা। Lookup প্রক্রিয়া:

1. Address-কে tag/index/offset-এ ভাঙা হয়।
2. Index দিয়ে সরাসরি (কোনো তুলনা ছাড়াই) সেই একটা line select করা হয় — এটাই decoder-এর কাজ, ঠিক DRAM row-select-এর মতো।
3. সেই line-এ সংরক্ষিত tag-এর সাথে address-এর tag তুলনা করা হয় — একটা মাত্র comparator।
4. যদি মেলে এবং সেই line “valid” (একটা valid bit থাকে, cold-start-এ সব line invalid) — তাহলে hit, offset দিয়ে সঠিক বাইট বের করা হয়।
5. না মিললে — miss। নিচের memory স্তর থেকে পুরো line আনতে হয়, cache-এ বসাতে হয় (পুরনো যা ছিল তা মুছে), তারপর data দেওয়া হয়।

                 address (32 বিট)
        ┌──────────┬──────────┬──────────┐
        │   tag     │  index   │  offset  │
        │ (20 বিট)  │ (6 বিট)  │ (6 বিট)  │
        └────┬─────┘└────┬─────┘└────┬────┘
             │            │            │
             │      ┌─────▼─────┐      │
             │      │  index দিয়ে │     │
             │      │  ঠিক ১টা    │     │
             │      │  line select│     │
             │      └─────┬─────┘      │
             │            │            │
             │     ┌──────▼──────┐     │
             │     │ line-এ সংরক্ষিত │  │
             │     │ tag + valid বিট │  │
             │     └──────┬──────┘     │
             │            │            │
             └───►[ = ? ]◄┘            │
                    │ comparator (১টা)  │
              ┌─────▼─────┐            │
              │ match+valid│           │
              │  → HIT     │           │
              │  না মিললে   │           │
              │  → MISS    │           │
              └────────────┘           │
                                   line-এর ভেতরে
                                   offset দিয়ে বাইট বাছাই

Conflict-এর সমস্যা — concrete উদাহরণ

Direct-mapped-এর সমস্যা তার নামেই লুকানো — প্রতিটা address-এর জন্য একটাই সম্ভাব্য line। দুইটা ভিন্ন, ঘনঘন-ব্যবহৃত ঠিকানা যদি একই index-এ পড়ে (কিন্তু আলাদা tag), তারা একে অপরকে বারবার উৎখাত (evict) করতে থাকবে — এটাকে বলে thrashing।

মনে করুন উপরের 4 KB, 64-বাইট-line cache-এ দুইটা int array আছে, প্রতিটাতে 1024 element (4096 বাইট করে):

int a[1024];  /* ঠিকানা শুরু হয় 0x10000 থেকে ধরুন */
int b[1024];  /* ঠিকানা শুরু হয় 0x11000 থেকে — a-এর ঠিক পরে */

0x11000 - 0x10000 = 0x1000 = 4096 — অর্থাৎ b-এর base ঠিকানা a-এর base ঠিকানা থেকে ঠিক cache আকারের সমান দূরত্বে। যেহেতু 4096 = 2^12 আর index+offset মিলিয়ে মাত্র 12 বিট (6+6), 4096 যোগ করলে সেই 12 বিটের কোনোটাই বদলায় না — শুধু tag বদলায়:

a[i]-এর ঠিকানা:  ... tag=T1 ... index=I ... offset=O
b[i]-এর ঠিকানা:  ... tag=T2 ... index=I ... offset=O   ← একই index, শুধু tag ভিন্ন!

এখন কল্পনা করুন একটা loop যা পালাক্রমে a[i] আর b[i] access করছে:

for (int i = 0; i \< 1024; i++) {
    sum += a[i] + b[i];
}

a[i] access করলে সেই index-এ a-এর line বসে (tag=T1)। পরের মুহূর্তেই b[i] access — একই index, কিন্তু tag=T2, মিলছে না — miss, a-এর line উৎখাত হয়ে b-এর line বসে। পরের iteration-এ a[i+1] — যদিও সেটা নতুন offset-এর জন্য হয়তো একই line-এই থাকত (spatial locality থাকলে), কিন্তু b ইতিমধ্যে সেই line দখল করে ফেলেছে — আবার miss। ফলাফল: প্রতিটা access-ই miss, যদিও প্রতিটা array আলাদা করে পুরোপুরি cache-এ আঁটত (4096 বাইট, cache-এর সমান আকার), আর দুটো মিলিয়েও (8192 বাইট) মাত্র 2× cache আকার — তুলনায় নগণ্য working set।

Fully-associative cache — যেকোনো জায়গায়, কিন্তু সবখানে খুঁজতে হয়

বিপরীত চরম ডিজাইন: fully-associative cache-এ কোনো index-ই নেই — একটা address যেকোনো line-এ থাকতে পারে। Address ভাগ হয় শুধু tag + offset-এ (উপরের উদাহরণে: tag 26 বিট, offset 6 বিট, 26+6=32 ✓ — index বিট শূন্য)।

সুবিধা: উপরের conflict সমস্যা সম্পূর্ণ অদৃশ্য — a আর b একই “index”-এর জন্য প্রতিদ্বন্দ্বিতা করছে না, কারণ কোনো নির্দিষ্ট index নেই যেখানে তাদের যেতেই হবে। যেকোনো দুটো ঠিকানা cache-এর যেকোনো দুইটা (বা একই সময়ে বেশি) ভিন্ন line-এ থাকতে পারে, যতক্ষণ পুরো cache না ভরে।

কিন্তু দাম: index না থাকায় hardware জানে না কোথায় খুঁজবে — তাই প্রতিটা line-এর tag-এর সাথে address-এর tag তুলনা করতে হয়, একযোগে (parallel), একটা cycle-এই। এর মানে N-টা line-এর cache-এ N-টা comparator লাগবে।

              address → tag (26 বিট) + offset (6 বিট)
                              │
        ┌──────────┬──────────┬──────────┬───┬──────────┐
        │  line 0  │  line 1  │  line 2  │...│  line 63 │
        │  tag=?   │  tag=?   │  tag=?   │   │  tag=?   │
        └────┬─────┴────┬─────┴────┬─────┴───┴────┬─────┘
             │           │           │              │
          [=?]        [=?]        [=?]     ...   [=?]     ← ৬৪টা comparator, একসাথে
             └───────────┴─────OR───┴──────────────┘
                              │
                    কোনো একটাতে match+valid → HIT

Set-associative cache — বাস্তবসম্মত মাঝামাঝি

এখানেই আসল ইঞ্জিনিয়ারিং সমাধান — N-way set-associative। ধারণাটা direct-mapped আর fully-associative-এর মধ্যে একটা spectrum তৈরি করে:

• Cache-এর line-গুলোকে ছোট ছোট group বা set-এ ভাগ করা হয়, প্রতিটা set-এ ঠিক N-টা line (N-কে বলে “way”)।
• একটা address-এর index বিট বলে দেয় সে কোন set-এ যাবে (direct-mapped-এর মতো — নির্দিষ্ট)।
• কিন্তু সেই set-এর ভেতরে address N-টা line-এর যেকোনো একটাতে থাকতে পারে (fully-associative-এর মতো — নমনীয়, তবে শুধু সেই set-এর মধ্যে)।
• Lookup-এ শুধু সেই একটা set-এর N-টা line-এর tag তুলনা করতে হয় — N-টা comparator, পুরো cache-এর সবগুলো না।

একটা concrete 4-way উদাহরণ

একই 4 KB cache, 64-বাইট line, কিন্তু এবার 4-way set-associative।

ধাপ ১ — মোট line সংখ্যা অপরিবর্তিত: $\frac{4096}{64} = 64 \text{টা line}$

ধাপ ২ — set সংখ্যা: প্রতিটা set-এ 4-টা line থাকলে: $\frac{64 \text{ line}}{4 \text{ way}} = 16 \text{টা set}$

ধাপ ৩ — index বিট: 16-টা set-এর একটা চিহ্নিত করতে: $\log_2(16) = 4 \text{ বিট}$

ধাপ ৪ — offset অপরিবর্তিত: 6 বিট (line আকার একই)।

ধাপ ৫ — tag বাকি সব বিট: $32 - 4 (\text{index}) - 6 (\text{offset}) = 22 \text{ বিট}$

যাচাই: 22 + 4 + 6 = 32 ✓। আর সঞ্চয় ক্ষমতাও মেলে: 16 set × 4 way × 64 বাইট = 4096 বাইট = 4 KB ✓।

Direct-mapped (1-way):    64 line,  64 set  → tag=20  index=6  offset=6
4-way set-associative:    64 line,  16 set  → tag=22  index=4  offset=6
Fully-associative (64-way): 64 line, 1 set  → tag=26  index=0  offset=6

                     tag বিট বাড়ছে ──────────►
   ◄────────── index বিট কমছে (associativity বাড়ার সাথে)

একই conflict উদাহরণ, এবার 4-way-তে

আগের a[i]/b[i] thrashing উদাহরণটা 4-way cache-এ ফিরিয়ে আনি। a-এর আর b-এর ঠিকানা এখনও 4096 বাইট দূরত্বে, তাই তারা এখনও একই set-এ পড়বে (কারণ 4096 = 2^12, আর index+offset মিলে এখনও 10 বিট (4+6), যা 2^10=1024-এর সীমার মধ্যে repeat করে — 4096-এর প্যাটার্ন এখনও index অপরিবর্তিত রাখে)। কিন্তু এবার সেই set-এ 4-টা line আছে — a[i] একটা way দখল করে, b[i] আরেকটা way দখল করে, দুটোই একই সাথে সেই set-এ থাকতে পারে, একে অপরকে উৎখাত না করেই। Thrashing সম্পূর্ণ চলে গেছে — শুধু associativity বাড়ানোর কারণে, কোনো code পরিবর্তন ছাড়াই।

Skew-associative — associativity-র সুবিধা, কম হার্ডওয়্যার খরচে