Multicore আর cache coherence — MESI আর memory consistency

১ · কেন multicore — power wall আর ILP-এর দেয়াল

২০০০-এর দশকের শুরু পর্যন্ত প্রতি প্রজন্মে CPU দ্রুত হতো মূলত দুই উপায়ে: clock বাড়িয়ে, আর একটি core-কে আরও চতুর করে — গভীর pipeline, superscalar, out-of-order. দুটো পথই প্রায় একই সময়ে দেয়ালে ঠেকে।

প্রথম দেয়াল power wall (পর্ব ০২): CMOS-এ dynamic power মোটামুটি C·V²·f-এর সমানুপাতিক (পর্ব ০৮). Dennard scaling-এর যুগে transistor ছোট হলে voltage-ও কমত, তাই বাড়তি clock-এর খরচ পুষিয়ে যেত। ২০০৫-এর আশেপাশে voltage আর কমানো কঠিন হয়ে পড়ল (leakage বেড়ে যায়), আর chip-এর তাপ ঠান্ডা রাখার সীমা ছুঁয়ে ফেলল। ফলে desktop chip-এর clock মোটামুটি কয়েক GHz-এ থেমে আছে প্রায় দুই দশক।

দ্বিতীয় দেয়াল ILP-এর দেয়াল (পর্ব ৩৯): একটি সাধারণ প্রোগ্রামে একসাথে চালানো যায় এমন instruction সীমিত। Core-কে ৪-wide থেকে ৮-wide করলে register port, dependence-পরীক্ষা আর bypass-এর খরচ প্রায় বর্গের হারে বাড়ে, কিন্তু IPC বাড়ে সামান্য।

অথচ Moore-এর সূত্র মেনে transistor তখনো বাড়ছিল। সেই বাড়তি transistor দিয়ে কী করা যায়? উত্তর: একটি বিশাল core-এর বদলে কয়েকটি মাঝারি core — multicore. দুটি ধীর core একটি দ্রুত core-এর চেয়ে কম বিদ্যুতে বেশি কাজ করতে পারে — যদি সফটওয়্যার কাজ ভাগ করতে পারে; ভাগ না হওয়া অংশ লাভ সীমিত করে (Amdahl, পর্ব ০৩).

২ · Shared-memory multiprocessor — নিজের L1/L2, ভাগ করা L3

আজকের ফোন, ল্যাপটপ আর সার্ভারের প্রায় সব chip একটি symmetric multiprocessor (SMP): সব core সমান, সবাই একই physical address space দেখে, একই OS চালায়। Core-সংখ্যা কম হলে যেকোনো core থেকে যেকোনো ঠিকানায় যেতে মোটামুটি একই সময় লাগে — একে বলে UMA. বড় সার্ভারে, যেখানে কয়েকটি socket-এর প্রত্যেকটির নিজের মেমরি, সময় ঠিকানাভেদে আলাদা — NUMA, যা পর্ব ৫৪-এর বিষয়।

কেন সবাই একটি L1 ভাগ করে না? L1-কে কয়েক cycle-এ উত্তর দিতে হয়, তাই সেটি ছোট আর core-এর একদম পাশে (পর্ব ৪৪); চারটি core-এর ভিড়ে port আর তারের দৈর্ঘ্যে তা ধীর হয়ে যেত। তাই প্রতিটি core-এর private cache, আর তার নিচে একটি বড়, তুলনায় ধীর, ভাগ করা L3. আর এখানেই সমস্যার বীজ: একই ঠিকানার কপি একাধিক private cache-এ থাকতে পারে।

৩ · Coherence-এর সমস্যা — stale value, আর সমাধানের সংজ্ঞা

পর্ব ৪৭-এ (cache-এর পারফরম্যান্স) দেখেছেন, আধুনিক cache প্রায় সবসময় write-back: লেখা প্রথমে শুধু cache-এ হয়, line-টি dirty চিহ্নিত থাকে, আর মেমরিতে যায় অনেক পরে, line সরানোর সময়। একটি core-এর জন্য এটি দারুণ — মেমরির ট্রাফিক অনেক কমে। কিন্তু দুটি core হলে? নিচের stepper-এ প্রথমে কোনো coherence ছাড়া, তারপর MSI protocol দিয়ে একই ঘটনা দেখুন।

Coherence-এর সংজ্ঞা

“সবাই সর্বশেষ মান দেখবে” — শুনতে সহজ, কিন্তু “সর্বশেষ” কথাটাই multicore-এ ঝাপসা, কারণ আলাদা core-এর ঘটনার একটি সার্বজনীন ঘড়ি নেই। তাই cache coherence-কে একটি ঠিকানা ধরে দুটি শর্তে সংজ্ঞায়িত করা হয় (Hennessy–Patterson-এর পাঠ্যবইয়ের ধাঁচে):

1. Write propagation: কোনো core X-এ লিখলে, যথেষ্ট সময় পরে অন্য core X পড়লে সেই নতুন মান (বা তার পরের কোনো মান) পাবে। কেউ চিরকাল পুরোনো কপিতে আটকে থাকবে না। (আর একটি core নিজের লেখার পরে নিজে পড়লে নিজের মান পাবে, মাঝে অন্য কেউ না লিখলে।)
2. Write serialization: একই ঠিকানায় দুটি লেখা — ধরুন P1 লেখে ১, P2 লেখে ২ — সব core একই ক্রমে দেখবে। কেউ “১ তারপর ২” আর কেউ “২ তারপর ১” দেখবে না।

Coherence বনাম consistency — দুটি আলাদা প্রশ্ন

Coherence শুধু একটি ঠিকানার কথা বলে। কিন্তু প্রোগ্রাম সাধারণত কয়েকটি ঠিকানা একসাথে ব্যবহার করে: thread A লেখে data = 42, তারপর flag = 1; thread B flag ১ দেখলে data পড়ে। B কি নিশ্চিত ৪২ পাবে? এটি ভিন্ন ঠিকানার ক্রমের প্রশ্ন, যার উত্তর দেয় memory consistency model — অংশ ৭-এর বিষয়। মনে রাখার সূত্র: coherence = একটি ঠিকানার সব লেখা সবাই একভাবে দেখে; consistency = আলাদা ঠিকানার access-গুলো অন্যদের চোখে কোন ক্রমে দেখা দিতে পারে। একটি সিস্টেম পুরোপুরি coherent হয়েও দুর্বল consistency দিতে পারে — আজকের ARM আর RISC-V chip ঠিক তাই।

৪ · Snooping আর MSI protocol — state, event আর transition

কম core-এর chip-এ coherence-এর সবচেয়ে পুরোনো আর সরল উপায় snooping: সব cache একটি ভাগ করা bus-এ (বা এমন কোনো পথে, যেখানে প্রতিটি বার্তা সবাই একই ক্রমে শোনে) যুক্ত। প্রতিটি cache-এর controller দুই দিকে কান পাতে — নিজের core-এর অনুরোধ, আর bus-এ অন্যদের অনুরোধ। Bus-এর একটি গুরুত্বপূর্ণ গুণ: একবারে একজনই bus পায়, তাই সব অনুরোধ একটি নির্দিষ্ট ক্রমে ঘটে — write serialization বিনা খরচে।

দুই নীতি: write-invalidate আর write-update

ছোট হিসাব। P1 একটি ঠিকানায় পরপর ১০ বার লেখে, P2-এর কাছে তার কপি আছে, আর P2 শেষে একবার পড়ে। Write-update: ১০টি broadcast. Write-invalidate: প্রথম লেখায় ১টি invalidation, শেষে P2-এর ১টি miss — মোট ২টি। উল্টো ধরন — producer-consumer, যেখানে প্রতিটি লেখার পরেই অন্যজন পড়ে: update-এ প্রতি লেখায় ১টি, invalidate-এ প্রতি লেখায় ২টি (বাতিল + miss). বাস্তবে প্রথম ধরন বেশি — তাই invalidate জিতেছে।

MSI-এর তিন অবস্থা

MSI-এ প্রতিটি cache-এর প্রতিটি line-এর সঙ্গে দুটি বাড়তি bit, যা তিনটি অবস্থার একটি বোঝায়:

এবার event দুই ধরনের। Processor event — নিজের core থেকে: PrRd (পড়া), PrWr (লেখা)। Bus event — অন্য cache থেকে শোনা bus transaction: BusRd (“পড়ার জন্য line চাই”), BusRdX (“লেখার জন্য line চাই — সবাই বাতিল করুন”; X = exclusive), BusUpgr (“line আমার কাছে S-এ আছে, শুধু অন্যরা বাতিল করুন” — ডেটা আনতে হয় না, তাই BusRdX-এর চেয়ে সস্তা; কিছু পাঠ্যবই এখানেও BusRdX লেখে)। আর একটি উত্তর: Flush — M কপির মালিক নিজের হালনাগাদ ডেটা bus-এ তুলে দেয়।

শেষ ঘরটি SWMR-এর সরাসরি ফল: কেউ M-এ থাকলে আর কারও কাছে বৈধ কপি নেই, তাই কেউ S থেকে BusUpgr পাঠাতে পারে না। একই তথ্য ছবিতে:

৫ · MESI — Exclusive অবস্থা কী বাঁচায়, আর একটি পূর্ণ trace

MSI-তে একটি অপচয় খুব সাধারণ: একটি thread নিজের ব্যক্তিগত ডেটা (যেমন নিজের stack বা নিজের array) পড়ে, তারপর লেখে। পড়ায় BusRd → S; লেখায় BusUpgr → M. অথচ আর কারও কাছে কপি ছিলই না — BusUpgr-টি বৃথা, আর কম্পাইলারের তৈরি x = x + 1-এর মতো load-তারপর-store প্রোগ্রামে প্রতি মুহূর্তে ঘটে।

MESI একটি চতুর্থ অবস্থা যোগ করে: E (Exclusive) — পরিষ্কার কপি (মেমরির সাথে মিল), কিন্তু শুধু এই cache-এর কাছেই. BusRd-এর সময় bus-এ একটি “shared” সংকেত থাকে: অন্য কোনো cache-এর কাছে কপি থাকলে তারা সংকেতটি চালু করে। চালু হলে line S-এ আসে, না হলে E-তে। E থেকে লেখায় কোনো bus transaction লাগে না — নিঃশব্দে M. আর E-তে থাকা line অন্য কেউ BusRd করলে → S; সরিয়ে দেওয়ার সময় মেমরিতে লিখতে হয় না, কারণ ডেটা পরিষ্কার। (এই protocol প্রায়ই “Illinois protocol” নামে পরিচিত, ১৯৮৪ সালের দিকে University of Illinois-এর Papamarcos আর Patel-এর প্রস্তাব থেকে।)

এবার তিনটি core আর দুটি ঠিকানা (X ভাগ করা, Y শুধু P3-এর) নিয়ে একটি পূর্ণ trace. প্রতিটি ধাপে ভাবুন — কোন অবস্থা, কোন bus transaction, ডেটা কোথা থেকে — তারপর “পরে” চাপুন। ডান দিকের গণনায় একই trace MSI-তে চালালে কত bus transaction হতো, তাও দেখানো হয়েছে।

এবার একই কাজ একটি simulator দিয়ে। নিচের JS কোড N-টি core-এর জন্য লেখা (এখানে ৩), একটি trace (core, R/W, ঠিকানা) নেয়, আর MSI ও MESI — দুই নিয়মে চালিয়ে প্রতিটি ধাপে প্রতিটি core-এর অবস্থা, bus transaction আর ডেটার উৎস ছাপে। Trace বদলে নিজের প্রশ্ন বানিয়ে দেখতে পারেন।

// MSI vs MESI snooping simulator: per step each core's state, bus transaction, data source
const CORES = 3, ids = Array.from({ length: CORES }, (_, i) => i + 1);
const trace = [[1,"R","X"],[1,"W","X"],[2,"R","X"],[3,"R","X"],[2,"W","X"],
  [3,"W","X"],[1,"R","X"],[3,"R","Y"],[3,"W","Y"]];          // (core, R/W, address)
function simulate(proto) {
  const st = {}, get = (c, a) => (st[a] ??= Array(CORES + 1).fill("I"))[c];
  let reqs = 0, flushes = 0;
  console.log(`${proto}
step  op      P1 P2 P3  bus      data from`);
  trace.forEach(([c, op, a], n) => {
    const s = get(c, a), row = st[a], others = ids.filter((o) => o !== c);
    const owner = others.find((o) => row[o] === "M"), anyCopy = others.some((o) => row[o] !== "I");
    let bus = "-", src = "own cache (hit)";
    if (op === "R" && s === "I") {
      bus = "BusRd"; src = owner ? `P${owner} cache (Flush)` : "memory";
      if (owner) flushes++;
      others.forEach((o) => { if (row[o] !== "I") row[o] = "S"; });  // M/E holders drop to S
      row[c] = proto === "MESI" && !anyCopy ? "E" : "S";
    } else if (op === "W" && s !== "M") {
      if (s === "E") { src = "own cache (E->M, silent)"; }
      else if (s === "S") { bus = "BusUpgr"; src = "own cache (others invalidated)"; }
      else { bus = "BusRdX"; src = owner ? `P${owner} cache (Flush)` : "memory"; if (owner) flushes++; }
      others.forEach((o) => { row[o] = "I"; });
      row[c] = "M";
    }
    if (bus !== "-") reqs++;
    const states = ids.map((o) => row[o].padEnd(2)).join(" ");
    console.log(`${String(n + 1).padStart(4)}  P${c} ${op} ${a}  ${states}  ${bus.padEnd(7)}  ${src}`);
  });
  console.log(`${proto}: ${reqs} bus requests, ${flushes} flushes
`);
  return reqs;
}
const msi = simulate("MSI"), mesi = simulate("MESI");
console.log(`MESI saves ${msi - mesi} of ${msi} bus requests on this trace`);

MSI
step  op      P1 P2 P3  bus      data from
   1  P1 R X  S  I  I   BusRd    memory
   2  P1 W X  M  I  I   BusUpgr  own cache (others invalidated)
   3  P2 R X  S  S  I   BusRd    P1 cache (Flush)
   4  P3 R X  S  S  S   BusRd    memory
   5  P2 W X  I  M  I   BusUpgr  own cache (others invalidated)
   6  P3 W X  I  I  M   BusRdX   P2 cache (Flush)
   7  P1 R X  S  I  S   BusRd    P3 cache (Flush)
   8  P3 R Y  I  I  S   BusRd    memory
   9  P3 W Y  I  I  M   BusUpgr  own cache (others invalidated)
MSI: 9 bus requests, 3 flushes

MESI
step  op      P1 P2 P3  bus      data from
   1  P1 R X  E  I  I   BusRd    memory
   2  P1 W X  M  I  I   -        own cache (E->M, silent)
   3  P2 R X  S  S  I   BusRd    P1 cache (Flush)
   4  P3 R X  S  S  S   BusRd    memory
   5  P2 W X  I  M  I   BusUpgr  own cache (others invalidated)
   6  P3 W X  I  I  M   BusRdX   P2 cache (Flush)
   7  P1 R X  S  I  S   BusRd    P3 cache (Flush)
   8  P3 R Y  I  I  E   BusRd    memory
   9  P3 W Y  I  I  M   -        own cache (E->M, silent)
MESI: 7 bus requests, 3 flushes

MESI saves 2 of 9 bus requests on this trace

MOESI আর MESIF — দুই বাস্তব রূপ

বাস্তব chip আরও একটি-দুটি অবস্থা যোগ করে। MOESI-তে O (Owned): dirty line অন্যের সাথে ভাগ করা যায় মেমরিতে না লিখেই — owner পরিবর্তিত ডেটা রাখে আর অনুরোধ এলে সেই-ই পাঠায়, অন্যরা S. MSI-তে ধাপ ৩-এর মতো জায়গায় মেমরিতে লেখা লাগত; O তা এড়ায়। এটি AMD-র অনেক processor-এর সঙ্গে পরিচিত। MESIF-এ F (Forward): কয়েকটি পরিষ্কার S কপির মধ্যে ঠিক একজন “উত্তরদাতা”, যাতে একটি অনুরোধে পাঁচটি cache একসাথে ডেটা না পাঠায়; Intel-এর point-to-point interconnect-এর (QuickPath) যুগ থেকে এটি তাদের সঙ্গে পরিচিত। ভেতরের আসল protocol এর চেয়ে জটিল আর সবটা প্রকাশ্য নয়।

৬ · Directory, coherence miss আর false sharing-এর ভেতরের কারণ

Directory-ভিত্তিক coherence — সংক্ষেপে

Snooping-এর দুর্বলতা: প্রতিটি miss সবাইকে শোনাতে হয়। ৪টি core-এ ঠিক আছে, কিন্তু ৬৪টি core-এ প্রতিটি miss ৬৩টি cache-এর tag খোঁজায় আর একটি ভাগ করা পথে ভিড় বাড়ায়। Directory-ভিত্তিক পদ্ধতিতে প্রতিটি line-এর জন্য একটি হিসাব থাকে তার home node-এ (প্রায়ই L3-এর যে slice বা যে socket-এর মেমরিতে ঠিকানাটি পড়ে): line-এর অবস্থা আর presence bits — প্রতি core-এ একটি bit, “এর কাছে কপি আছে কি না”। Miss হলে অনুরোধ যায় home-এ; home জানে ঠিক কাদের কাছে কপি, তাই শুধু তাদেরই invalidation বা forward পাঠায় — broadcast নেই।

খরচের হিসাব। ৬৪টি core-এর জন্য পূর্ণ presence vector = প্রতি line-এ ৬৪ bit. ৬৪-byte line = ৫১২ bit, তাই শুধু presence bit-এর বাড়তি জায়গা ৬৪ ÷ ৫১২ = ১২.৫% — core দ্বিগুণ হলে এটিও দ্বিগুণ। এজন্য বড় সিস্টেম নানা সংক্ষিপ্ত রূপ ব্যবহার করে (মোটা দাগের bit, সীমিত pointer, বা শুধু cache-এ থাকা line-এর হিসাব রাখা snoop filter). বিস্তারিত — NUMA, interconnect আর directory-র বড় পরিসর — পর্ব ৫৪-এ।

Coherence miss — চতুর্থ C

পর্ব ৪৫–৪৬-এ miss-এর তিনটি C দেখেছেন: compulsory, capacity, conflict. Multicore যোগ করে চতুর্থটি — coherence miss: line-টি cache-এ ছিল, জায়গাও ছিল, কিন্তু অন্য core লেখায় বাতিল হয়ে গেছে। Cache বড় করে এটি কমে না। এর দুই উৎস:

• True sharing miss: P2 সত্যিই সেই word পড়ছে, যা P1 লিখেছে। এটি অনিবার্য — তথ্য তো এক core থেকে আরেক core-এ যেতেই হবে।
• False sharing miss: P1 লিখেছে word A, P2 পড়ছে একই line-এর word B. B বদলায়ইনি, তবু P2-এর miss — কারণ coherence-এর হিসাব পুরো line ধরে, word ধরে নয়।

পর্ব ৪৮-এ আপনি প্রোগ্রামারের দিক থেকে false sharing মেপে দেখেছেন: দুই thread দুটি আলাদা counter বাড়ায়, counter দুটি একই ৬৪-byte line-এ, আর padding দিলেই গতি ফেরে। এখন তার যন্ত্রটা স্পষ্ট। প্রতিটি a++ একটি PrWr. Core 0 লিখতে চাইলে line-টি M-এ চাই — core 1-এর কাছে M থাকলে BusRdX, core 1-এর Flush আর I. তারপর core 1-এর b++ — উল্টো দিকে একই কাজ। MESI-র ভাষায় line-টি M → I → M → I করতে থাকে দুই cache-এ পালা করে, প্রতিটি লেখা একটি cache-থেকে-cache হস্তান্তর। প্রতিকার একটাই: দুটি ভ্যারিয়েবল আলাদা line-এ — তাহলে প্রতিটি line একজনের কাছে স্থায়ীভাবে M থাকে, আর আর কোনো bus transaction হয় না।

৭ · Memory consistency — store buffer, SC, TSO আর দুর্বল model

Coherence নিখুঁত হলেও একটি প্রশ্ন থেকে যায়। পরিচিত একটি mutual exclusion-এর কৌশল দেখুন — Dekker আর Peterson-এর algorithm-এর মূল ভাবনা (Operating Systems কোর্সের race condition আর Peterson-এর পর্ব):

/* শুরুতে x = 0, y = 0  (x = "thread 0 ঢুকতে চায়", y = "thread 1 ঢুকতে চায়") */
Thread 0:                    Thread 1:
    x = 1;                       y = 1;
    r1 = y;                      r2 = x;
    if (r1 == 0) critical();     if (r2 == 0) critical();

স্বাভাবিক বুদ্ধি বলে, দুজনে একসাথে critical section-এ ঢুকতে পারে না: যে পরে পড়ছে, সে অন্যের লেখা ১ দেখবেই। অর্থাৎ (r1, r2) = (0, 0) অসম্ভব। এই “স্বাভাবিক বুদ্ধি”-র একটি নাম আছে।

SC-তে উপরের দুই thread-এর ৪টি operation মোট ৬ ভাবে মেশানো যায়, আর প্রতিটিতে প্রথম operation-টি অবশ্যই কোনো একটি store — তাই অন্য thread-এর load, যা তার পরে চলে, সেই ১ দেখবে। (0, 0) অসম্ভব। কিন্তু আসল x86 যন্ত্রে এই প্রোগ্রাম চালালে (0, 0) দেখা যায়! কারণ store buffer.

Store buffer — কেন hardware SC ভাঙে

একটি store-কে cache-এ লিখতে হলে line-টি M-এ থাকতে হয়। Line না থাকলে BusRdX পাঠিয়ে অপেক্ষা — দশ থেকে শতাধিক cycle. সেই সময় পুরো core থামিয়ে রাখা অপচয়, কারণ store-এর ফল কেউ সঙ্গে সঙ্গে চায় না। তাই প্রতিটি core-এ একটি ছোট FIFO সারি — store retire হয়ে সেখানে বসে, আর core পরের instruction-এ চলে যায়। Store buffer পরে, সুযোগমতো, ক্রম মেনে cache-এ লেখে (পর্ব ৪০-এর load-store queue আর পর্ব ৪৭-এর write buffer-এর আত্মীয়)। আর নিজের core-এর পরের load একই ঠিকানা চাইলে store buffer থেকেই মান নেয় — store-to-load forwarding.

এখন উপরের প্রোগ্রাম: core 0-এর x = 1 store buffer-এ বসে আছে, তখনো cache-এ যায়নি। Core 0-এর r1 = y ভিন্ন ঠিকানা — buffer-এ মিল নেই, তাই cache বা মেমরি থেকে পড়ে: ০. একই সময়ে core 1-এ উল্টো ছবি: y = 1 buffer-এ, r2 = x পড়ে ০. তারপর দুই buffer খালি হয়। ফল (0, 0) — যেন প্রতিটি core-এ store আর তার পরের load-এর ক্রম উল্টে গেছে। একে বলে store-buffering বা SB litmus test.

নিচের JS মডেল দুই ধরনের যন্ত্রে সব সম্ভাব্য interleaving গুনে দেখে। SC-তে store সঙ্গে সঙ্গে মেমরিতে যায়। TSO-তে প্রতিটি store আগে নিজের core-এর FIFO buffer-এ ঢোকে (S), পরে যেকোনো সময় মেমরিতে নামে (D, drain); load আগে নিজের buffer, তারপর মেমরি দেখে (L).

// Store-buffering (SB) litmus test: T0: x=1; r1=y   T1: y=1; r2=x   (x = y = 0 at start)
// SC : every store reaches memory at once.  TSO: a store waits in its core's FIFO store
// buffer and drains to memory later; a load first checks its own buffer, then memory.
function explore(tso) {
  const outcomes = new Map(); let runs = 0;
  const prog = [[["st", "x"], ["ld", "y", "r1"]], [["st", "y"], ["ld", "x", "r2"]]];
  function step(mem, pc, buf, regs, log) {
    let moved = false;
    for (let t = 0; t < 2; t++) {
      if (pc[t] < 2) {                                   // next instruction of thread t
        const [op, v, r] = prog[t][pc[t]], p2 = [...pc]; p2[t]++; moved = true;
        if (op === "st") {
          if (tso) { const b = buf.map((q) => [...q]); b[t].push(v); step(mem, p2, b, regs, log + ` S${t}`); }
          else step({ ...mem, [v]: 1 }, p2, buf, regs, log + ` S${t}`);
        } else {
          const val = buf[t].includes(v) ? 1 : mem[v];   // store-to-load forwarding
          step(mem, p2, buf, { ...regs, [r]: val }, log + ` L${t}`);
        }
      }
      if (tso && buf[t].length) {                        // drain oldest buffered store of t
        const b = buf.map((q) => [...q]), v = b[t].shift(); moved = true;
        step({ ...mem, [v]: 1 }, pc, b, regs, log + ` D${t}`);
      }
    }
    if (!moved) {
      runs++; const k = `(r1, r2) = (${regs.r1}, ${regs.r2})`;
      if (!outcomes.has(k)) outcomes.set(k, { n: 0, ex: log.trim() });
      outcomes.get(k).n++;
    }
  }
  step({ x: 0, y: 0 }, [0, 0], [[], []], {}, "");
  console.log(`${tso ? "TSO (store buffers)" : "SC"}: ${runs} interleavings`);
  for (const [k, o] of [...outcomes].sort()) console.log(`  ${k}  x${String(o.n).padStart(2)}  e.g. ${o.ex}`);
}
explore(false); explore(true);

SC: 6 interleavings
  (r1, r2) = (0, 1)  x 1  e.g. S0 L0 S1 L1
  (r1, r2) = (1, 0)  x 1  e.g. S1 L1 S0 L0
  (r1, r2) = (1, 1)  x 4  e.g. S0 S1 L0 L1
TSO (store buffers): 80 interleavings
  (r1, r2) = (0, 0)  x18  e.g. S0 L0 S1 L1 D0 D1
  (r1, r2) = (0, 1)  x22  e.g. S0 L0 D0 S1 L1 D1
  (r1, r2) = (1, 0)  x22  e.g. S0 S1 L1 D0 D1 L0
  (r1, r2) = (1, 1)  x18  e.g. S0 D0 S1 L1 D1 L0

TSO, আর তার চেয়েও ঢিলা model

x86-এর memory model-কে সাধারণত TSO (Total Store Order) বলা হয় — SPARC-এর একটি model-এর নাম থেকে; x86-এর এই আচরণ Intel আর AMD-র manual-এর নিয়ম থেকে গবেষকেরা ২০০৯–২০১০ সালের দিকে “x86-TSO” নামে আনুষ্ঠানিক রূপ দেন। সারকথা: store buffer FIFO, তাই store-store ক্রম অটুট; load-load আর load-store ক্রমও অটুট; ভাঙে শুধু store → পরের ভিন্ন ঠিকানার load. তাই x86-এ message passing — data = 42; flag = 1; আর অন্য দিকে if (flag) use(data); — fence ছাড়াই কাজ করে (অনুশীলন ৩-এ এর হিসাব)।

ARM (ARMv8) আর RISC-V-এর ডিফল্ট model, RVWMO, অনেক ঢিলা: ভিন্ন ঠিকানার প্রায় যেকোনো দুটি access-এর ক্রম উল্টে দেখা দিতে পারে — store-store, load-load সবই। এতে hardware-এর নকশা সহজ আর দ্রুত হয়; দাম — যেখানে ক্রম দরকার, সেখানে software-কে স্পষ্টভাবে চাইতে হয়। (RISC-V-এ ঐচ্ছিক “Ztso” extension আছে, যা TSO-র নিশ্চয়তা দেয় — যেমন x86 কোড অনুবাদ করে চালানোর সুবিধার জন্য।)

Fence, acquire আর release

ক্রম ফিরিয়ে আনার যন্ত্র fence (বা barrier): fence-এর আগের নির্দিষ্ট ধরনের access শেষ না হলে পরেরগুলো দেখা দেয় না। RISC-V-এ fence rw, rw (আগের সব read/write, পরের সব read/write-এর আগে); x86-এ mfence, বা যেকোনো lock-যুক্ত instruction; ARM-এ dmb ish. SB-তে দুই thread-এ store আর load-এর মাঝে একটি পূর্ণ fence দিলে store buffer খালি না হওয়া পর্যন্ত load অপেক্ষা করে — (0, 0) আর হয় না। দাম: প্রতি fence-এ কয়েক দশ cycle পর্যন্ত, chip-ভেদে।

পূর্ণ fence প্রায়ই দরকারের চেয়ে বেশি। Lock-এর জন্য লাগে একমুখী নিয়ম — acquire আর release: acquire (lock নেওয়া, বা flag পড়া) — এর পরের কোনো access এর আগে চলে যেতে পারবে না; release (lock ছাড়া, বা flag লেখা) — এর আগের কোনো access এর পরে যেতে পারবে না। Critical section-এর কাজ এভাবে দুই দেয়ালের মাঝে আটকে থাকে, অথচ বাইরের access ভেতরে ঢুকতে পারে — hardware-এর স্বাধীনতা কম কাটে। ARMv8-এ ldar/stlr, RISC-V-এ atomic instruction-এর .aq/.rl bit, আর C11-এ memory_order_acquire/memory_order_release. C-র ডিফল্ট memory_order_seq_cst race-মুক্ত প্রোগ্রামকে SC-র মতো আচরণের নিশ্চয়তা দেয় — compiler দরকারি fence বসিয়ে দেয় (x86-এ seq_cst store সাধারণত xchg, বা mov-এর পরে mfence).

এবার আসল hardware-এ SB litmus. দুটি thread প্রতিটি round-এ একটি খুদে barrier-এ মিলিত হয়ে একসাথে নিজের store আর load চালায়; প্রতিটি round-এর জন্য আলাদা নতুন x[i], y[i] (শুরুতে ০), আর শেষে চার রকম ফল গোনা হয়। প্রথমে memory_order_relaxed (compiler সাধারণ mov বসায়, hardware TSO-র স্বাধীনতা পুরো পায়), তারপর seq_cst.

// SB litmus on real hardware: T0: x=1; r1=y   T1: y=1; r2=x   -- count (0,0) outcomes
#include <pthread.h>
#include <stdatomic.h>
#include <stdio.h>
#define ROUNDS 200000
#define TEST(MO) if (id == 0) { atomic_store_explicit(&x[i], 1, MO); r1[i] = atomic_load_explicit(&y[i], MO); } \
                 else         { atomic_store_explicit(&y[i], 1, MO); r2[i] = atomic_load_explicit(&x[i], MO); }

static atomic_int x[ROUNDS], y[ROUNDS], arrived;   // fresh x[i] = y[i] = 0 for every round
static int r1[ROUNDS], r2[ROUNDS], relaxed;

static void *thr(void *arg) {
    long id = (long)arg;
    for (int i = 0; i < ROUNDS; i++) {
        atomic_fetch_add(&arrived, 1);              // tiny barrier: both start round i together
        while (atomic_load(&arrived) < 2 * (i + 1)) { }
        if (relaxed) { TEST(memory_order_relaxed) } else { TEST(memory_order_seq_cst) }
    }
    return NULL;
}
static void trial(int use_relaxed) {
    pthread_t a, b; int h[4] = {0}; relaxed = use_relaxed; atomic_store(&arrived, 0);
    for (int i = 0; i < ROUNDS; i++) { atomic_store(&x[i], 0); atomic_store(&y[i], 0); }
    pthread_create(&a, NULL, thr, (void *)0L); pthread_create(&b, NULL, thr, (void *)1L);
    pthread_join(a, NULL); pthread_join(b, NULL);
    for (int i = 0; i < ROUNDS; i++) h[r1[i] * 2 + r2[i]]++;     // index = r1 r2 in binary
    printf("%-8s (0,0) %6d   (0,1) %6d   (1,0) %6d   (1,1) %6d\n",
           use_relaxed ? "relaxed" : "seq_cst", h[0], h[1], h[2], h[3]);
}
int main(void) {
    printf("%d rounds each\n", ROUNDS);
    trial(1); trial(0);
    return 0;
}

200000 rounds each
relaxed  (0,0)    106   (0,1)  99978   (1,0)  99850   (1,1)     66
seq_cst  (0,0)      0   (0,1)  99932   (1,0)  99986   (1,1)     82

200000 rounds each
relaxed  (0,0)  22680   (0,1)  85474   (1,0)  87693   (1,1)   4153
seq_cst  (0,0)      0   (0,1)  93927   (1,0)  96296   (1,1)   9777

৮ · Hardware-এর atomic instruction আর spinlock

Lock বানাতে লাগে পড়া-বদলানো-লেখা এমনভাবে, যাতে মাঝখানে কেউ ঢুকতে না পারে — atomic read-modify-write. সাধারণ counter++ তা নয়: compiler এটিকে load, add, store — তিনটি instruction বানায়, আর দুই core-এর মধ্যে ছয়টি instruction মিশে গেলে একটি যোগ হারিয়ে যায়। নিচে দুটি thread একটি counter-কে ১ কোটি বার করে বাড়ায় — সাধারণ int আর C11-এর atomic_fetch_add দিয়ে।

// Shared counter, 2 threads: plain int (data race = undefined behaviour) vs C11 atomic
#include <pthread.h>
#include <stdatomic.h>
#include <stdio.h>
#include <time.h>
#define ITERS 10000000

static int plain;                       // NOT atomic: ++ is load, add, store
static atomic_int atom;                 // atomic_fetch_add: one indivisible RMW

static void *bump_plain(void *arg) { (void)arg; for (int i = 0; i < ITERS; i++) plain++; return NULL; }
static void *bump_atom(void *arg)  { (void)arg; for (int i = 0; i < ITERS; i++) atomic_fetch_add(&atom, 1); return NULL; }

static double run(void *(*fn)(void *)) {
    struct timespec t0, t1; pthread_t a, b;
    clock_gettime(CLOCK_MONOTONIC, &t0);
    pthread_create(&a, NULL, fn, NULL); pthread_create(&b, NULL, fn, NULL);
    pthread_join(a, NULL); pthread_join(b, NULL);
    clock_gettime(CLOCK_MONOTONIC, &t1);
    return (t1.tv_sec - t0.tv_sec) * 1e3 + (t1.tv_nsec - t0.tv_nsec) / 1e6;
}
int main(void) {
    double tp = run(bump_plain), ta = run(bump_atom);
    printf("expected      : %d\n", 2 * ITERS);
    printf("plain int     : %d  (lost %d)  %5.0f ms\n", plain, 2 * ITERS - plain, tp);
    printf("atomic_int    : %d  (lost %d)  %5.0f ms\n", atomic_load(&atom), 2 * ITERS - atomic_load(&atom), ta);
    printf("atomic / plain time = %.1f\n", ta / tp);
    return 0;
}

expected      : 20000000
plain int     : 12654418  (lost 7345582)    220 ms
atomic_int    : 20000000  (lost 0)    324 ms
atomic / plain time = 1.5

চার ধরনের atomic instruction

RISC-V-এর A extension-এর AMO (যেমন amoadd.w rd, rs2, (rs1): rd ← মেমরি[rs1]; মেমরি[rs1] ← পুরোনো মান + rs2) এক instruction-এই কাজ সারে; বড় chip-এ এগুলো এমনকি L3 বা মেমরির কাছাকাছি চালানো যায়, line core-এ না এনেই। LR/SC আরও নমনীয়: lr আর sc-এর মাঝে যেকোনো ছোট হিসাব (দুই মানের সর্বোচ্চ, একটি bit বসানো) করা যায়। কীভাবে কাজ করে? lr.w line-টির ওপর একটি reservation বসায়; অন্য কোনো core সেখানে লিখতে গেলে তার BusRdX/BusUpgr শুনে reservation মুছে যায় — coherence protocol-ই খবর দেয়। sc.w rd, rs2, (rs1) সফল হলে rd = ০, ব্যর্থ হলে rd ≠ ০ — তখন software আবার চেষ্টা করে।

একটি RISC-V spinlock (উদাহরণ; RISC-V unprivileged spec-এর lock-এর নমুনার ধাঁচে লেখা):

# a0 = lock-এর ঠিকানা (0 = খালি, 1 = কারও হাতে)
acquire:
        li      t1, 1
retry:  lr.w.aq t0, (a0)          # পড়া + reservation; aq = acquire
        bnez    t0, retry         # কারও হাতে: আবার পড়া (নিজের cache-এ)
        sc.w    t2, t1, (a0)      # reservation টিকে থাকলে 1 লেখা
        bnez    t2, retry         # t2 != 0: অন্য কেউ আগে লিখেছে, আবার
        ret
release:
        amoswap.w.rl x0, x0, (a0) # 0 লেখা; rl = release (আগের কাজ আগে)
        ret

# একই lock শুধু AMO দিয়ে (test-and-set):
        li      t0, 1
again:  amoswap.w.aq t0, t0, (a0) # t0 = পুরোনো মান, lock = 1
        bnez    t0, again

দুই core একসাথে lock নিতে চাইলে কী হয়, বাস্তব bus transaction সহ নিচে ধাপে ধাপে দেখুন (line-এর অবস্থা MESI-তে):

Cache-line bouncing আর test-and-test-and-set

সবচেয়ে সরল spinlock — while (test_and_set(&lock)) ; — অপেক্ষার সময় প্রতিটি চেষ্টায় একটি লেখা করে (ব্যর্থ হলেও, কারণ TAS সবসময় ১ লেখে)। প্রতিটি লেখার জন্য line-টি M-এ চাই, তাই প্রতিটি চেষ্টা একটি BusRdX আর আগের মালিকের Flush. তিনটি core অপেক্ষায় থাকলে line-টি তাদের মধ্যে অবিরাম লাফায় — cache-line bouncing. ক্ষতি দুটি: bus বা interconnect ভরে যায়, ফলে অন্য সব core-এর miss-ও ধীর হয়; আর lock-এর মালিক যখন ছাড়তে চায়, তাকেও line ফেরত পেতে লাইনে দাঁড়াতে হয়।

প্রতিকার test-and-test-and-set (TTAS): আগে সাধারণ load দিয়ে দেখা, lock খালি মনে হলে তবেই TAS.

/* C11 দিয়ে TTAS spinlock (উদাহরণ) */
void lock(atomic_int *l) {
    for (;;) {
        while (atomic_load_explicit(l, memory_order_relaxed) != 0) { }   /* নিজের S কপিতে ঘোরা */
        if (atomic_exchange_explicit(l, 1, memory_order_acquire) == 0) return;  /* তবেই TAS */
    }
}
void unlock(atomic_int *l) { atomic_store_explicit(l, 0, memory_order_release); }

অপেক্ষার সময় প্রত্যেক অপেক্ষাকারী একবার BusRd করে S কপি নেয়, তারপর নিজের cache-এ hit-এর পর hit — bus শান্ত। মালিক ছাড়লে একটি invalidation, তারপর সবার একটি করে miss আর TAS-এর ছোট একটি ঝাঁক; একজন জেতে, বাকিরা আবার নিজের কপিতে ফেরে। হিসাবটি অনুশীলন ৪-এ। আরও বড় প্রতিযোগিতায় ব্যবহৃত হয় exponential backoff, ticket lock আর MCS lock-এর মতো queue-ভিত্তিক lock, যেখানে প্রত্যেকে নিজের আলাদা line-এ অপেক্ষা করে — software-এর দিক Operating Systems কোর্সের atomic instruction আর spinlock পর্বে।

৯ · কতদূর বাড়ানো যায় — bus-এর সীমা, ring আর mesh

Snooping bus-এর দুটি সীমা আছে। Bandwidth: সব core-এর সব miss একটি পথে। একটি খেলনা হিসাব: ধরুন প্রতিটি core গড়ে প্রতি ১০০ cycle-এ একটি bus transaction করে, আর bus প্রতি ৪ cycle-এ একটি সামলাতে পারে। তাহলে bus ১০০ ÷ ৪ = ২৫টি core-এর বেশি সামলাতে পারবে না — তার আগেই সারি লম্বা হয়ে প্রতিটি miss-এর অপেক্ষা বাড়তে থাকবে। (সংখ্যাগুলো কাল্পনিক; নীতিটি বাস্তব।) Snoop-এর চাপ: প্রতিটি অনুরোধ সব cache-এর tag খোঁজায়, তাই core দ্বিগুণ হলে মোট snoop-এর কাজ প্রায় চার গুণ (দ্বিগুণ অনুরোধ × দ্বিগুণ শ্রোতা)। আর chip বড় হলে লম্বা bus-এর তারের দেরিও বাড়ে (পর্ব ১৮).

তাই বড় chip-এ একক bus আর নেই। প্রচলিত ধারা (নির্দিষ্ট পণ্যের ভেতরের নকশা সবসময় প্রকাশ্য নয়, তাই মোটা দাগে): L3 কয়েকটি slice-এ ভাগ, প্রতিটি slice ঠিকানার একটি অংশের “home”; core আর slice জোড়া লাগে একটি on-chip interconnect-এ — কয়েক থেকে দশ-বারোটি core-এ একটি ring, আরও বেশি core-এ গ্রিডের মতো mesh (Intel-এর কিছু সার্ভার chip কয়েক প্রজন্ম আগে ring থেকে mesh-এ গেছে বলে প্রকাশিত)। Broadcast-এর বদলে L3-এর পাশে snoop filter বা directory রাখে কোন line কার কাছে, আর বার্তা যায় শুধু দরকারি core-এ। Chiplet দিয়ে বানানো processor-এ chiplet-এর মাঝেও একই হিসাব লাগে। পুরো ছবি — NUMA, topology আর directory-র স্কেল — পর্ব ৫৪-এ।

১০ · AI-এর যুগে — coherence আর memory ordering-এ AI, আর যাচাইয়ের অভ্যাস

এই বিষয়ের প্রশ্নে AI-এর উত্তর শুনতে খুব আত্মবিশ্বাসী, কিন্তু কয়েকটি ভুল বারবার দেখা যায়:

AI-এর দেওয়া coherence-ব্যাখ্যা বা concurrent কোড হাতে পেলে — চেকলিস্ট

• MESI/MSI trace-এর প্রতিটি ধাপ নিজে বা একটি simulator-এ মিলিয়েছি, আর SWMR কোথাও ভাঙেনি দেখেছি
• প্রশ্নটি এক ঠিকানার (coherence) না একাধিক ঠিকানার (consistency), তা আলাদা করেছি
• লক্ষ্য hardware কোনটি — x86 (TSO), ARM না RISC-V (দুর্বল) — জেনে নিয়ে fence বা acquire/release-এর দাবি যাচাই করেছি
• Lock-free কোডে প্রতিটি memory_order-এর কারণ লিখতে পেরেছি; না পারলে seq_cst রেখেছি
• ThreadSanitizer (-fsanitize=thread) চালিয়েছি, আর কয়েকশো বার বা বড় loop-এ চালিয়ে ফল দেখেছি
• ISA-র নির্দিষ্ট খুঁটিনাটি (sc-এর return মান, aq/rl-এর অর্থ, x86-এর lock prefix) manual থেকে মিলিয়েছি