Control hazard আর branch prediction — static, ২-bit আর আধুনিক predictor

১ · Control hazard — শাখার ফল জানার আগেই পরের instruction আনতে হয়

পর্ব ৩৫-এ (Pipelining) দেখেছেন, RISC-V-এর ৫ ধাপের pipeline-এ একটি instruction পাঁচটি ধাপ পার হয়: IF (instruction আনা), ID (decode আর register পড়া), EX (ALU-র কাজ), MEM (মেমরি) আর WB (register-এ লেখা)। প্রতি cycle-এ একটি নতুন instruction ঢোকে, তাই আদর্শ অবস্থায় CPI = 1. পর্ব ৩৬-এ (Pipeline hazard) data hazard আর forwarding-এর কথা — মান তৈরি হওয়ার আগেই দরকার পড়লে কী হয়। এই পর্বের সমস্যাটি অন্য রকম: পরের instruction কোনটি, সেটাই জানা নেই।

একটি সাধারণ instruction-এর পরে PC + 4. কিন্তু conditional branch-এর পরে PC + 4 নাকি branch target, তা ঠিক হয় দুটি register তুলনা করার পরে। সরল নকশায় তুলনা হয় EX ধাপের ALU-তে। অথচ শাখাটি যখন ID-তে, তখনই IF-কে পরের instruction আনতে হচ্ছে; শাখা EX-এ পৌঁছালে IF আরেকটি এনে ফেলেছে। এই সমস্যার নাম control hazard (বা branch hazard).

Penalty কত cycle?

শাখা নেওয়া (taken) হলে, শাখার পরে আর target-এর আগে যতগুলো instruction ভুল পথে আনা হয়ে গেছে, ততগুলো cycle নষ্ট — একে বলে branch penalty. শাখা IF-এ cycle ১-এ ঢুকলে:

২ · চারটি পুরোনো সমাধান — stall, ID-তে শাখা, not-taken অনুমান আর delay slot

(ক) ফল জানা পর্যন্ত থামা

সবচেয়ে নিরাপদ উপায়: decode-এ শাখা চিনলেই IF থামিয়ে দেওয়া (stall), ফল জানা গেলে সঠিক ঠিকানা থেকে আনা। থামার সময় pipeline-এ যা ঢোকে তা bubble — কোনো কাজ করে না। দাম: প্রতিটি শাখায় পুরো penalty, শাখা নেওয়া হোক বা না হোক। ২০% instruction শাখা আর penalty ২ হলে CPI = 1 + 0.2 × 2 = 1.4 — আদর্শের চেয়ে ৪০% ধীর।

(খ) শাখার সিদ্ধান্ত ID-তে আনা

RISC-V-এর শাখার তুলনাগুলো সরল: সমান কি না, বা signed/unsigned ছোট কি না। পুরো ALU লাগে না। তাই ID ধাপে, register file পড়ার ঠিক পরে, একটি ছোট comparator আর target-এর জন্য একটি আলাদা adder (PC + imm) বসানো যায়। একে বলে early branch resolution — penalty ২ থেকে ১-এ নামে। দুটি দাম আছে:

• নতুন data hazard: তুলনার register-গুলো এখন ID-তেই দরকার, EX-এ নয়। ঠিক আগের ALU instruction যদি সেই register লেখে (যেমন add x1, … তারপর beq x1, x3, L), ফল তখনো EX-এ — তাই ১ cycle stall, তারপর forwarding ID-তে। আগের instruction load হলে (lw x1 তারপর beq x1) ২ cycle stall. Forwarding-এর নতুন পথও লাগে ID-তে।
• ID ধাপ লম্বা হয়: register পড়া, তারপর তুলনা — একই cycle-এ। ID যদি critical path হয়ে যায়, পুরো clock ধীর হয় (পর্ব ১৮-এর critical path).

(গ) “শাখা নেওয়া হবে না” ধরে এগোনো, আর ভুল হলে flush

থামার বদলে সবচেয়ে সস্তা অনুমান: predict not-taken — শাখা নেওয়া হবে না ধরে PC + 4 থেকে আনতেই থাকা। শাখা সত্যিই না নেওয়া হলে কোনো ক্ষতি নেই। নেওয়া হলে অনুমানটি ভুল (branch misprediction), আর ভুল পথে আনা instruction-গুলোকে মুছে দিতে হয় — একে বলে flush. কীভাবে মোছা হয়? ভুল instruction-টি যে pipeline register-এ বসে আছে (ID-তে সিদ্ধান্ত হলে IF/ID), তার instruction-এর ঘরটি শূন্য করে দেওয়া হয় (পাঠ্যবইয়ের সরল নকশায়; RISC-V-এ সব-শূন্য word আসলে একটি অবৈধ বা illegal instruction, তাই অনেক নকশা বরং একটি valid বিট ০ করে), বা ঘরটিকে nop বানানো হয় — RISC-V-এ addi x0, x0, 0. সঙ্গে নিয়ন্ত্রণ সংকেতগুলো (RegWrite, MemWrite) ০, তাই সেটি পরের ধাপগুলোয় গিয়েও কোনো register বা মেমরিতে কিছু লেখে না। ভুল instruction কখনো কিছু লিখতে পারার আগেই মোছা হয় — এটাই অনুমানকে নিরাপদ করে।

নিচের stepper-এ ৫ ধাপের pipeline, ID-তে শাখার সিদ্ধান্ত, not-taken অনুমান। beq x1, x3, L-এ x1 = x3, তাই শাখা নেওয়া হয় — অনুমান ভুল। প্রতিটি ধাপ একটি clock cycle. “পরে” চাপুন:

1# predict not-taken; x1 = 7, x3 = 7 (branch will be taken)20x40      sub  x10, x4, x830x44      beq  x1, x3, L      # L = 0x6040x48      and  x12, x2, x5    # wrong path50x4C      or   x13, x2, x6    # wrong path60x60  L:  lw   x4, 8(x7)70x64      add  x14, x2, x6

(ঘ) Branch delay slot — শাখার পরের instruction-টি সবসময় চলে

১৯৮০-র দশকের MIPS (আর SPARC, PA-RISC-এর মতো আরও কিছু RISC) অন্য পথ নিয়েছিল: penalty-র cycle-টিকে নষ্ট না করে ISA-র নিয়মই বদলে দেওয়া — শাখার ঠিক পরের instruction-টি শাখা নেওয়া হোক বা না হোক, সবসময় চলবে। এই জায়গাটির নাম branch delay slot. Compiler শাখার আগের কোনো স্বাধীন instruction সেখানে সরিয়ে বসায়; কিছু না পেলে nop.

# উদাহরণ — MIPS ধাঁচের delay slot (RISC-V-এ এমন কিছু নেই)
# আগে:                        # compiler সাজানোর পরে:
  add  $s1, $s2, $s3            beq  $t0, $t1, L
  beq  $t0, $t1, L              add  $s1, $s2, $s3   # delay slot: always runs
  nop                         # শাখার শর্ত add-এর ওপর নির্ভর করে না, তাই সরানো নিরাপদ

৫ ধাপের, ১ cycle penalty-র pipeline-এ এটি নিখুঁত খাপ খায়। কিন্তু নিয়মটি ISA-তে চিরকালের জন্য বাঁধা পড়ে যায়, অথচ microarchitecture (ISA-র নিচের আসল hardware নকশা) বদলায়। গভীর pipeline-এ penalty ১০ cycle-এরও বেশি — একটি slot সেখানে প্রায় কিছুই বাঁচায় না, তবু পুরোনো সব প্রোগ্রামের জন্য রাখতেই হয়। Superscalar CPU-তে (প্রতি cycle-এ কয়েকটি instruction, পর্ব ৩৯), exception-এ (slot-এর instruction-এ exception হলে কোথায় ফেরা হবে?), আর পরে যোগ হওয়া ছোট (compressed) instruction-এ এটি জটিলতা বাড়ায়। তাই RISC-V-এর নকশাকারেরা ইচ্ছা করে delay slot রাখেননি; MIPS-এর নতুন সংস্করণেও (MIPS32/64 Release 6-এ) delay slot ছাড়া “compact” শাখা যোগ করা হয়েছিল। শিক্ষা: একটি নির্দিষ্ট pipeline-এর খুঁটিনাটি ISA-তে ঢোকানো বিপজ্জনক।

৩ · শাখার দাম CPI-তে — সূত্র আর হাতে-কলমে অঙ্ক

পর্ব ০৩-এর (পারফরম্যান্স মাপা) iron law: CPU time = IC × CPI × cycle time. শাখা IC বদলায় না; বদলায় CPI. প্রতিটি ভুল (বা অপেক্ষা) একটি নির্দিষ্ট সংখ্যক bubble যোগ করে, তাই গড়ে প্রতি instruction-এ বাড়তি cycle = (শাখার অনুপাত) × (প্রতি শাখায় গড় বাড়তি cycle).

যুক্তি: N টি instruction-এ শাখা f·N টি। তাদের মধ্যে ভুল অনুমান m·f·N টি, আর প্রতিটি ভুলে P টি bubble. আদর্শ pipeline-এ (data hazard বাদ) প্রতি instruction-এ ১ cycle, তাই মোট cycle ≈ N + m·f·N·P, আর CPI = মোট cycle / N = 1 + f·m·P. Pipeline ভরতে প্রথম কয়েকটি cycle লাগে, কিন্তু N বড় হলে তা নগণ্য। দুটি বিশেষ ক্ষেত্র: stall-এ প্রতিটি শাখাই penalty দেয় (m = 1); predict not-taken-এ শুধু নেওয়া শাখাগুলো দেয় (m = taken-এর হার)। Data hazard-এর stall থাকলে (পর্ব ৩৬) সেগুলোও যোগ হয়: CPI = 1 + data-stall + branch-stall.

হাতে-কলমে তিনটি অঙ্ক

(ক) ৫ ধাপ, শাখা EX-এ (penalty 2), শাখা 20%, তার 60% taken
    stall           : CPI = 1 + 0.20 × 1.0 × 2 = 1.40
    predict-NT      : CPI = 1 + 0.20 × 0.6 × 2 = 1.24
    2-bit, 90% ঠিক  : CPI = 1 + 0.20 × 0.1 × 2 = 1.04

(খ) একই, কিন্তু শাখা ID-তে (penalty 1); 30% শাখার আগে ঠিক আগের ALU instruction
    তুলনার register লেখে (1 cycle stall):
    predict-NT      : CPI = 1 + 0.20 × (0.6 × 1 + 0.3 × 1) = 1.18
    -> hazard না থাকলে 1.12 হতো; নতুন data hazard লাভের অর্ধেক খেয়ে ফেলে (1.24 -> 1.18)

(গ) গভীর pipeline, penalty 20, শাখা 20%
    95% ঠিক: CPI = 1 + 0.20 × 0.05 × 20 = 1.20
    97% ঠিক: CPI = 1 + 0.20 × 0.03 × 20 = 1.12   -> speedup 1.20 / 1.12 ≈ 1.071 (প্রায় 7%)

(গ) গুরুত্বপূর্ণ শিক্ষা দেয়: নির্ভুলতা ৯৫% থেকে ৯৭% — শুনতে সামান্য, কিন্তু প্রতি ১০০টি শাখায় ভুল ৫টি থেকে ৩টি — ৪০% কম। গভীর pipeline-এ predictor-এর প্রতিটি শতাংশের দাম অনেক। নিচের calculator চারটি pipeline আর পাঁচটি কৌশলের পুরো টেবিল বানায় (শাখা ২০% আর taken ৬০% — দুটিই উদাহরণের জন্য ধরে নেওয়া মান), আর iron law দিয়ে ছোট বনাম গভীর pipeline-এর তুলনা করে:

// CPI with branch penalties:  CPI = 1 + (branch fraction) x (misprediction rate) x (penalty in cycles)
const fBranch = 0.20, takenRate = 0.60;     // assumed workload: 20% branches, 60% of them taken
const pipes = [["5-stage, branch in ID", 1], ["5-stage, branch in EX", 2], ["deep, penalty 15", 15], ["deep, penalty 20", 20]];
const schemes = [["stall", 1], ["predict-N", takenRate], ["90%", 0.10], ["95%", 0.05], ["99%", 0.01]]; // miss rate
const cpi = (pen, miss) => 1 + fBranch * miss * pen;
console.log("pipeline".padEnd(23) + schemes.map(([s]) => s.padStart(10)).join(""));
for (const [name, pen] of pipes)
  console.log(name.padEnd(23) + schemes.map(([, m]) => cpi(pen, m).toFixed(3).padStart(10)).join(""));
// Iron law: a deeper pipeline pays a bigger penalty but may run a faster clock.
const t5 = cpi(1, 0.10) / 1.0, tDeep = cpi(15, 0.05) / 3.0;   // ns per instruction at 1 GHz and 3 GHz
console.log(`5-stage @1 GHz, 90%: ${t5.toFixed(3)} ns/instr   deep @3 GHz, 95%: ${tDeep.toFixed(3)} ns/instr`);
// How much does going from 95% to 97% accuracy help the 20-cycle pipeline?
const a = cpi(20, 0.05), b = cpi(20, 0.03);
console.log(`penalty 20: CPI ${a.toFixed(2)} -> ${b.toFixed(2)}, speedup ${(a / b).toFixed(3)}`);

pipeline                    stall predict-N       90%       95%       99%
5-stage, branch in ID       1.200     1.120     1.020     1.010     1.002
5-stage, branch in EX       1.400     1.240     1.040     1.020     1.004
deep, penalty 15            4.000     2.800     1.300     1.150     1.030
deep, penalty 20            5.000     3.400     1.400     1.200     1.040
5-stage @1 GHz, 90%: 1.020 ns/instr   deep @3 GHz, 95%: 0.383 ns/instr
penalty 20: CPI 1.20 -> 1.12, speedup 1.071

৪ · Static prediction — always taken, BTFN আর compiler-এর ইঙ্গিত

Branch prediction-এর প্রথম ধাপ: চলার আগেই ঠিক করা একটি নিয়ম, যা প্রোগ্রাম চলার সময় বদলায় না — static branch prediction. তিনটি প্রচলিত নিয়ম:

কেন BTFN কাজ করে: পর্ব ২৯-এ (লুপ আর loop rotation) দেখেছেন, compiler লুপের শর্ত নিচে বসায়, আর সেখান থেকে শুরুতে ফেরার শাখা পেছনমুখী। n বার ঘোরা লুপে সেই শাখা n − 1 বার taken, একবার not-taken — n = 100 হলে ৯৯% ঠিক। আর সামনের দিকের শাখা সাধারণত if-এর “then-অংশ টপকানো” বা error-এর পথ — প্রায়ই কম ঘটে। একটি পরীক্ষার ধাঁচের হিসাব: একটি লুপ-শাখা (পেছনমুখী) ১০০০ বার চলে, ৯০% taken; সামনের শাখা A ৫০০ বার, ৩০% taken; সামনের শাখা B ৫০০ বার, ৮০% taken. BTFN-এর ঠিক = 900 + 350 + 100 = 1350, অর্থাৎ ১৩৫০/২০০০ = ৬৭.৫%. সবসময় taken-এর ঠিক = 900 + 150 + 400 = 1450, অর্থাৎ ৭২.৫% — এখানে B-এর কারণে BTFN হেরে গেল। সমাধান compiler-এর হাতে: B-এর শর্ত উল্টে কোড এমনভাবে সাজানো যাতে বেশি ঘটা পথটি fall-through হয় (শাখা না নিয়ে সোজা পরের instruction-এ চলে যাওয়া; তখন B ২০% taken) — BTFN তখন (900 + 350 + 400)/2000 = ৮২.৫%.

Compiler-এর ইঙ্গিত

কোন পথ বেশি ঘটে, প্রোগ্রামার বা compiler জানতে পারে দুইভাবে। এক, branch hint: GCC/Clang-এর __builtin_expect(x, 0) (Linux kernel-এ likely()/unlikely() macro), বা C++20-এর [[likely]]/[[unlikely]]. দুই, profile-guided optimization (PGO): আগে একবার চালিয়ে আসল আচরণ মেপে নেওয়া (gcc -fprofile-generate, তারপর -fprofile-use). আজকের CPU-তে এই তথ্যের প্রধান ব্যবহার কোড সাজানো — সম্ভাব্য পথ fall-through-এ, কম-ঘটা পথ দূরে — যাতে static নিয়ম আর instruction cache দুটিই খুশি থাকে। কিছু ISA-তে শাখার encoding-এ hint বিট ছিল (যেমন PowerPC-তে); x86-এর Pentium 4-এ শাখার আগে hint prefix ছিল, যা পরের বেশিরভাগ core উপেক্ষা করে বলে জানা যায়। RISC-V-এর শাখায় কোনো hint বিট নেই; spec শুধু পরামর্শ দেয়, software যেন ধরে নেয় পেছনমুখী শাখা taken আর সামনের শাখা not-taken অনুমান হবে (অন্তত প্রথমবার) — বাকিটা hardware-এর দায়িত্ব।

৫ · Dynamic prediction — ১-বিট আর ২-বিট saturating counter

Static নিয়ম প্রতিটি শাখার আসল আচরণ দেখে না। Dynamic branch prediction-এ hardware চলার সময় প্রতিটি শাখার অতীত মনে রাখে। সবচেয়ে সরল রূপ 1-bit predictor: প্রতিটি শাখার জন্য একটি বিট — “শেষবার নেওয়া হয়েছিল কি না”। অনুমান: শেষবার যা হয়েছিল, এবারও তাই।

১-বিটের দুর্বলতা — লুপে দুবার ভুল

১০ বার ঘোরা একটি লুপ ধরুন, শর্ত নিচে: শাখার ফল T T T T T T T T T N (৯ বার taken, শেষে বেরোনোর সময় not-taken). লুপটি বারবার চলে (যেমন একটি বাইরের লুপের ভেতরে)। আগের প্রবেশ শেষ হয়েছে N দিয়ে, তাই বিটটি এখন N:

• প্রথম ঘুর: অনুমান N, আসল T — ভুল ১. বিট হলো T.
• ২য় থেকে ৯ম ঘুর: অনুমান T, আসল T — ঠিক।
• ১০ম ঘুর (বেরোনো): অনুমান T, আসল N — ভুল ২. বিট হলো N — আর পরের প্রবেশের প্রথম ঘুরে আবার ভুল।

প্রতি প্রবেশে ১০টিতে ২টি ভুল: নির্ভুলতা ৮০% — অথচ শাখাটি ৯০% সময় taken; “সবসময় taken”-ও ৯০% পেত! একটিমাত্র ব্যতিক্রম (বেরোনো) বিটটি উল্টে দেয়, আর তার দাম দিতে হয় দুবার।

২-বিট saturating counter — একটি ব্যতিক্রমে মত বদলায় না

সমাধান: প্রতিটি শাখার জন্য ২ বিটের একটি counter, মান ০ থেকে ৩. Taken হলে ১ বাড়ে, not-taken হলে ১ কমে, কিন্তু ৩-এর ওপরে বা ০-র নিচে যায় না — তাই নাম 2-bit saturating counter (পর্ব ১৬-এর counter-এর একটি সীমাবদ্ধ রূপ)। মান ২ বা ৩ (উঁচু বিট ১) হলে অনুমান taken, ০ বা ১ হলে not-taken. চারটি state-এর নাম:

কেন লুপে শুধু একবার ভুল: লুপ চলার সময় counter থাকে 11 (strongly taken). বেরোনোর N-এ একবার ভুল, counter নামে 10 (weakly taken) — কিন্তু উঁচু বিট এখনো ১, অনুমান এখনো T. পরের প্রবেশের প্রথম T-তে অনুমান ঠিক, counter আবার 11. অর্থাৎ একটি ব্যতিক্রম অনুমান উল্টাতে পারে না — উল্টাতে পরপর দুটি লাগে। ১০ বারের লুপে প্রতি প্রবেশে ১টি ভুল: ৯০%. সাধারণভাবে n বারের লুপে ১-বিট (n − 2)/n আর ২-বিট (n − 1)/n — এটি এক ধরনের hysteresis, যেমন ঘরের থার্মোস্ট্যাটে তাপমাত্রা একটু ওঠানামায় বারবার চালু-বন্ধ হয় না। নিচে একই শাখায় দুটি predictor পাশাপাশি — একটি ৪ বারের লুপের বেরোনো আর আবার ঢোকা:

1# inner loop: 4 iterations per entry, branch at the bottom2loop:  ...body...3       addi t1, t1, 14       blt  t1, t2, loop    # T T T N5       ...other code, then the loop is entered again

Nested লুপে ভেতরের শাখার আচরণ ঠিক এমন। নিচের tracer একটি for i (3 বার) { for j (4 বার) }-এর ভেতরের শাখার প্রতিটি চলা দেখায় — counter শুরু 01 (weakly not-taken) থেকে, ১-বিট N থেকে — আর শেষে সাধারণ সূত্রটি দেয়:

// Inner-loop branch of  for (i = 0; i < 3; i++) for (j = 1; j <= 4; j++) {...}  (bottom-tested: blt j, 4 -> loop)
// Outcome per inner run: T, T, T, N.  2-bit counter starts at 01; 1-bit bit starts at N.
const NAME = ["00 strong-N", "01 weak-N", "10 weak-T", "11 strong-T"];
let s = 1, one = false, miss2 = 0, miss1 = 0;
console.log(" i  j   2-bit before  pred  actual  ok?   after       | 1-bit pred  ok?");
for (let i = 0; i < 3; i++)
  for (let j = 1; j <= 4; j++) {
    const taken = j < 4, p2 = s >= 2, p1 = one, before = s;
    if (p2 !== taken) miss2++;
    if (p1 !== taken) miss1++;
    s = taken ? Math.min(3, s + 1) : Math.max(0, s - 1);   // saturating update
    one = taken;                                            // 1-bit: remember last outcome
    const TN = b => (b ? "T" : "N");
    console.log(` ${i}  ${j}   ${NAME[before].padEnd(11)}  ${TN(p2)}      ${TN(taken)}     ${p2 === taken ? "yes" : "NO "}   ${NAME[s].padEnd(11)} |   ${TN(p1)}        ${p1 === taken ? "yes" : "NO"}`);
  }
console.log(`mispredictions in 12 executions: 2-bit = ${miss2}, 1-bit = ${miss1}`);
// General rule (same start states): an inner loop of n iterations entered m times
for (const [n, m] of [[4, 3], [10, 100]])
  console.log(`n=${n}, m=${m}: 2-bit ~ ${m + 1} misses (${(100 * (1 - (m + 1) / (n * m))).toFixed(1)}%), 1-bit ~ ${2 * m} (${(100 * (1 - 2 * m / (n * m))).toFixed(1)}%)`);

 i  j   2-bit before  pred  actual  ok?   after       | 1-bit pred  ok?
 0  1   01 weak-N    N      T     NO    10 weak-T   |   N        NO
 0  2   10 weak-T    T      T     yes   11 strong-T |   T        yes
 0  3   11 strong-T  T      T     yes   11 strong-T |   T        yes
 0  4   11 strong-T  T      N     NO    10 weak-T   |   T        NO
 1  1   10 weak-T    T      T     yes   11 strong-T |   N        NO
 1  2   11 strong-T  T      T     yes   11 strong-T |   T        yes
 1  3   11 strong-T  T      T     yes   11 strong-T |   T        yes
 1  4   11 strong-T  T      N     NO    10 weak-T   |   T        NO
 2  1   10 weak-T    T      T     yes   11 strong-T |   N        NO
 2  2   11 strong-T  T      T     yes   11 strong-T |   T        yes
 2  3   11 strong-T  T      T     yes   11 strong-T |   T        yes
 2  4   11 strong-T  T      N     NO    10 weak-T   |   T        NO
mispredictions in 12 executions: 2-bit = 4, 1-bit = 6
n=4, m=3: 2-bit ~ 4 misses (66.7%), 1-bit ~ 6 (50.0%)
n=10, m=100: 2-bit ~ 101 misses (89.9%), 1-bit ~ 200 (80.0%)

৬ · BHT, BTB আর RAS — কোন ঘরে মনে রাখা, কোথায় লাফ, কোথা থেকে ফেরা

Branch history table আর aliasing

প্রতিটি শাখার জন্য আলাদা counter রাখতে hardware শাখার PC-কে চাবি হিসেবে ব্যবহার করে। সস্তা উপায়: PC-র কয়েকটি নিচের বিট দিয়ে একটি ছোট টেবিলের ঘর বাছাই — branch history table (BHT; কোনো বইয়ে pattern history table). RV32I-এ instruction ৪ byte, তাই PC-র নিচের ২ বিট সবসময় 00 — সেগুলো বাদ দিয়ে PC[k+1:2] নেওয়া হয়। ১০২৪ ঘরের টেবিলে k = 10. টেবিলে কোনো tag (পুরো PC) রাখা হয় না, তাই দুটি শাখার PC-র ওই বিটগুলো মিলে গেলে তারা একই counter ভাগ করে — aliasing. দুই শাখা একই দিকে গেলে ক্ষতি নেই (এমনকি লাভ), বিপরীত দিকে গেলে একে অপরের অনুমান নষ্ট করে। এটি জেনেশুনে নেওয়া আপস: tag রাখলে টেবিল কয়েক গুণ বড় হয়, অথচ ভুল অনুমান শুধু গতি কমায়, ফল ভুল করে না — flush সব ঠিক করে দেয়।

Branch target buffer — দিক জানলেই হবে না, ঠিকানাও চাই

Counter বলে “taken”, কিন্তু কোথায়? ID-তে decode না করা পর্যন্ত জানাই যায় না যে instruction-টি শাখা, offset তো দূরের কথা। Taken অনুমানে penalty শূন্য করতে হলে IF-এই, শুধু PC দেখে, জানতে হবে (১) এটি কি শাখা, আর (২) target কত। এর জন্য branch target buffer (BTB): একটি ছোট cache, যার চাবি শাখার PC (tag সহ) আর মান আগের বার দেখা target. IF-এ instruction cache আর BTB একসাথে দেখা হয়। BTB-তে মিল পেলে আর predictor taken বললে পরের cycle-এই PC = সেই target; মিল না পেলে PC + 4. ভুল হলে (দিক বা ঠিকানা) সাধারণ flush, আর BTB হালনাগাদ। BTB-তে tag থাকে, কারণ এখানে ভুল ঘর মানে ভুল ঠিকানায় লাফ — খরচ বেশি।

Return address stack — function থেকে ফেরা

ret (jalr x0, 0(ra)) একটি indirect jump — গন্তব্য register-এ। BTB শেষবারের target মনে রাখে, কিন্তু একটি function অনেক জায়গা থেকে ডাকা হলে প্রতিবার ফেরার ঠিকানা ভিন্ন, তাই BTB প্রায়ই ভুল। সমাধান সুন্দর: call আর return-এর ক্রম একটি stack-এর মতো — শেষে ডাকা function আগে ফেরে। তাই hardware-এ একটি ছোট stack, return address stack (RAS): call-এ return address (PC + 4) ঠেলে রাখা, return-এ তুলে নিয়ে সেটিকেই target অনুমান করা। RISC-V spec নিজেই ইঙ্গিত দেয় কোন instruction call আর কোনটি return: rd = x1 (ra) বা x5 হলে jal/jalr push করার ইঙ্গিত; rs1 = x1 বা x5 আর rd = x0 হলে jalr pop. RAS ছোট (কয়েক থেকে কয়েক ডজন ঘর) — খুব গভীর recursion-এ উপচে পড়ে পুরোনো ঘর হারায়, তখন সেই return-গুলো ভুল অনুমান হয়।

৭ · Correlating predictor, gshare আর tournament — ইতিহাস দিয়ে অনুমান

এই কোডটি দেখুন: if (x == 0) a = 1; তারপর if (x == 0) b = 2; (বা if (a == 1)). দ্বিতীয় শাখার ফল প্রথমটির ফলের সমান। প্রতিটি শাখার নিজের counter এটি জানে না; x এলোমেলো হলে দুজনেই প্রায় ৫০%. কিন্তু “ঠিক আগের শাখা কী করেছিল” দেখলে দ্বিতীয়টি নিখুঁত অনুমান করা যায়। এই ধারণার নাম correlating predictor (বা two-level predictor).

• Global history register (GHR): শেষ m টি শাখার ফল (taken = 1) রাখা একটি m-বিটের shift register — প্রতিটি শাখার পরে বাঁয়ে সরে, নতুন ফল ডানে ঢোকে।
• (m, n) predictor: প্রতিটি PC-র জন্য 2^m টি n-বিট counter; GHR ঠিক করে কোনটি ব্যবহার হবে। যেমন (2, 2): শেষ দুই শাখার চার রকম ফলের জন্য চারটি আলাদা ২-বিট counter. সাধারণ ২-বিট BHT আসলে (0, 2) predictor. মোট বিট = 2^m × n × (PC-র ঘরের সংখ্যা) — যেমন (2, 2), ১০২৪ ঘর: 4 × 2 × 1024 = 8192 বিট।
• Local history: GHR সব শাখার মিলিত ইতিহাস; local history একটি নির্দিষ্ট শাখার নিজের শেষ কয়েকটি ফল। “৪ বার ঘুরে বেরোয়” ধরনের নিয়মিত লুপ local history দিয়ে ধরা যায়, যদি history অন্তত n − 1 বিট লম্বা হয় (n বার ঘোরা লুপে; ৪ বারের লুপে ৩ বিট)।

gshare — PC আর history-কে XOR

প্রতিটি PC-র জন্য আলাদা আলাদা 2^m টি counter রাখা ব্যয়বহুল। ১৯৯৩ সালে Scott McFarling (DEC-এর গবেষণাগারে) একটি প্রতিবেদনে একটি সস্তা কৌশল জনপ্রিয় করেন: gshare — একটি মাত্র counter-টেবিল, আর index = (PC-র বিট) ⊕ (GHR). একই শাখা ভিন্ন ইতিহাসে ভিন্ন ঘরে যায়; আর XOR দুই তথ্যকে টেবিল জুড়ে ছড়িয়ে দেয়, যাতে শুধু PC বা শুধু history-র চেয়ে aliasing কম হয়। নিচে ১৬ ঘরের টেবিল (৪-বিট index), ৪-বিটের GHR, সব counter শুরুতে 01:

এখন সব predictor একসাথে মেলানো যাক। নিচের simulator চার ধরনের শাখার trace চালায় — ১০ বারের লুপ ৩ বার (আর তুলনার জন্য ৩০ বার), T N পর্যায়ক্রম, একটি correlated if-জোড়া (দ্বিতীয় শাখা প্রথমটির ফল হুবহু অনুসরণ করে, প্রথমটি নির্দিষ্ট seed-এর pseudo-random ডেটায় চলে), আর এলোমেলো ডেটা-নির্ভর শাখা — ছয়টি predictor দিয়ে। BHT আর gshare দুটিই ১৬ ঘরের, gshare-এর history ৪ বিট:

// Branch-predictor simulator: 4 branch traces x 6 predictors. 2-bit counters start at 01 (weakly not-taken).
let seed = 2026;                                            // fixed seed: the "random" data is the same every run
const coin = () => ((seed = (Math.imul(seed, 1664525) + 1013904223) >>> 0) >>> 31) === 1;
const T = {};                                               // each event: [pc, backward branch?, taken?]
for (const reps of [3, 30]) { const L = T[`loop 10 x${reps}`] = [];        // loop branch: T x9, then N (exit)
  for (let e = 0; e < reps; e++) for (let j = 1; j <= 10; j++) L.push([0x40, true, j < 10]); }
T["alternating"] = []; for (let k = 0; k < 40; k++) T["alternating"].push([0x80, false, k % 2 === 0]);
T["if-pair"] = []; for (let k = 0; k < 200; k++) { const c = coin(); T["if-pair"].push([0x100, false, c], [0x10C, false, c]); }
T["random"] = []; for (let k = 0; k < 400; k++) T["random"].push([0x200, false, coin()]);
const sat = (v, k) => (k ? Math.min(3, v + 1) : Math.max(0, v - 1));   // 2-bit saturating counter
const P = {
  "always-T": () => ({ p: () => true, u() {} }),
  "always-N": () => ({ p: () => false, u() {} }),
  "BTFN": () => ({ p: (pc, back) => back, u() {} }),       // backward -> taken, forward -> not taken
  "1-bit": () => { const t = Array(16).fill(false), ix = pc => (pc >> 2) & 15;
    return { p: pc => t[ix(pc)], u: (pc, k) => { t[ix(pc)] = k === 1; } }; },
  "2-bit": () => { const t = Array(16).fill(1), ix = pc => (pc >> 2) & 15;
    return { p: pc => t[ix(pc)] >= 2, u: (pc, k) => { t[ix(pc)] = sat(t[ix(pc)], k); } }; },
  "gshare": () => { const t = Array(16).fill(1); let h = 0; const ix = pc => ((pc >> 2) ^ h) & 15;  // 4-bit history
    return { p: pc => t[ix(pc)] >= 2, u: (pc, k) => { t[ix(pc)] = sat(t[ix(pc)], k); h = ((h << 1) | k) & 15; } }; },
};
console.log("trace".padEnd(12) + "n".padStart(5) + "  " + Object.keys(P).map(s => s.padStart(11)).join(""));
for (const [name, tr] of Object.entries(T)) {
  let row = name.padEnd(12) + String(tr.length).padStart(5) + "  ";
  for (const make of Object.values(P)) {
    const pr = make(); let miss = 0;
    for (const [pc, back, taken] of tr) { if (pr.p(pc, back) !== taken) miss++; pr.u(pc, taken ? 1 : 0); }
    row += `${Math.round(100 * (tr.length - miss) / tr.length)}% (${miss})`.padStart(11);
  }
  console.log(row);
}
console.log("cell = accuracy (mispredictions)");

trace           n     always-T   always-N       BTFN      1-bit      2-bit     gshare
loop 10 x3     30      90% (3)   10% (27)    90% (3)    80% (6)    87% (4)   63% (11)
loop 10 x30   300     90% (30)  10% (270)   90% (30)   80% (60)   90% (31)   87% (38)
alternating    40     50% (20)   50% (20)   50% (20)    0% (40)    0% (40)    93% (3)
if-pair       400    51% (198)  50% (202)  50% (202)  53% (188)  49% (204)  70% (122)
random        400    49% (204)  51% (196)  51% (196)  50% (200)  50% (200)  44% (225)
cell = accuracy (mispredictions)

Tournament predictor

কোনো শাখা local history-তে ভালো ধরা পড়ে, কোনোটি global-এ। Tournament predictor দুটিকেই পাশাপাশি চালায়, আর প্রতিটি শাখার (কোনো নকশায় প্রতিটি history-র) জন্য একটি “chooser” ২-বিট counter রাখে — কোনটি সম্প্রতি বেশি ঠিক বলেছে, তার দিকে সরে। McFarling-এর একই প্রতিবেদনে এই সমন্বয়ের ধারণাও ছিল। সবচেয়ে বিখ্যাত উদাহরণ DEC-এর Alpha 21264 (১৯৯০-এর দশকের শেষ দিকে): একটি local predictor (প্রতিটি শাখার নিজস্ব ইতিহাস), একটি global predictor (GHR দিয়ে index), আর একটি choice predictor — পাঠ্যবইয়ে tournament-এর আদর্শ উদাহরণ হিসেবে এটিই দেখানো হয়। এর টেবিলের সঠিক আকার নিয়ে বিভিন্ন উৎসে বিস্তারিত পাবেন; মূল ধারণাটুকুই এখানে জরুরি।

৮ · আধুনিক predictor, গভীর pipeline-এ ভুলের দাম আর sorted array-র রহস্য

TAGE আর perceptron — গবেষণা থেকে chip-এ

• TAGE (TAgged GEometric history length; André Seznec আর Pierre Michaud, ২০০৬): একটি সাধারণ ২-বিট টেবিল, তার সাথে কয়েকটি tag-যুক্ত টেবিল, যাদের history-র দৈর্ঘ্য জ্যামিতিক হারে বাড়ে (যেমন ৪, ৮, ১৬, ৩২ … বিট)। সবচেয়ে লম্বা history-র যে টেবিলে tag মেলে, তার অনুমান নেওয়া হয়। ফলে ছোট ধরন অল্প history-তে, দূরের correlation লম্বা history-তে — একসাথে। Branch prediction-এর গবেষণা প্রতিযোগিতায় (Championship Branch Prediction) TAGE-ভিত্তিক নকশা বহুবার শীর্ষে ছিল বলে জানা যায়।
• Perceptron predictor (Daniel Jiménez আর Calvin Lin, ২০০১): history-র প্রতিটি বিটের একটি ওজন; অনুমান = ওজন × (±1) এর যোগফলের চিহ্ন। ভুল হলে (বা যোগফল একটি সীমার চেয়ে ছোট হলে) ওজনগুলো একটু করে সংশোধন — একটি সরলতম neural network. সুবিধা: খুব লম্বা history-তেও টেবিল সূচকীয় হারে বাড়ে না।
• বাস্তব chip: AMD প্রকাশ্যে বলেছে তাদের Zen core-এ perceptron-ধাঁচের predictor ছিল, আর Zen 2 থেকে TAGE-ধাঁচের একটি অংশ যোগ হয়েছে বলে জানা যায়; Intel আর Apple সাধারণত বিস্তারিত প্রকাশ করে না। আধুনিক core-এ সাধারণ কোডে নির্ভুলতা ৯০%-এর অনেক ওপরে থাকে — সঠিক সংখ্যা workload আর chip-ভেদে আলাদা, তাই নির্দিষ্ট কোনো শতাংশ মুখস্থ না করাই ভালো।

গভীর pipeline-এ এক ভুলের দাম

আধুনিক বড় core-এ fetch থেকে শাখার নিষ্পত্তি পর্যন্ত অনেকগুলো ধাপ, আর প্রতি cycle-এ ৪–৮টি instruction একসাথে আনা হয় (পর্ব ৩৯)। ভুল অনুমানে penalty মোটামুটি ১০–২০ cycle (core-ভেদে) — আর প্রতি cycle-এ কয়েকটি instruction-এর সুযোগ, তাই একটি ভুল মানে কয়েক ডজন instruction-এর কাজ নষ্ট। Out-of-order core-এ (পর্ব ৪০) অনুমানের পথে instruction শুধু আনা নয়, আগেভাগে চালানোও হয় — speculative execution — আর ভুল হলে ফলগুলো ফেলে দেওয়া হয়। Intel-এর Pentium 4 (NetBurst, ২০০০-এর দশকের শুরু) প্রায় ২০ ধাপের pipeline নিয়ে উচ্চ clock-এর পেছনে ছুটেছিল, আর পরের প্রজন্মে আরও গভীর হয়েছিল — শাখার ভুলের বড় দাম আর শক্তি-খরচ তার দুর্বলতা হিসেবে প্রায়ই উল্লেখ করা হয়; পরের Core নকশা তুলনামূলক কম গভীর pipeline-এ ফেরে।

Sorted বনাম unsorted — একই কাজ, ভিন্ন গতি

পর্ব ২৯-এর ভাবনার প্রশ্নে (শাখাহীন কোড) যে বিখ্যাত উদাহরণ এসেছিল, এবার মেপে দেখা যাক। একটি array-তে 0–255 এর মান; লুপ যোগ করে শুধু 128 বা তার বেশি মানগুলো। Unsorted array-তে শাখাটি মুদ্রা ছোঁড়ার মতো — কোনো predictor-ই এর চেয়ে ভালো পারে না (অংশ ৭-এর “random” সারি)। Sort করার পর প্রথম অর্ধেক টানা N, বাকি অর্ধেক টানা T — মাঝখানে একবার মত বদলানো ছাড়া প্রায় নিখুঁত। নিচের প্রোগ্রাম দুই অবস্থায় শাখাওয়ালা আর শাখাহীন (branchless, mask দিয়ে) — দুটি লুপের সময়ের অনুপাত ছাপে। প্রতিটি মাপ ৭ বার নিয়ে সবচেয়ে কমটি রাখা হয়, যাতে ভাগাভাগি করা সার্ভারের গোলমাল কম লাগে:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 32768
#define PASSES 100
static unsigned char a[N];
static int cmp(const void *p, const void *q) { return *(const unsigned char *)p - *(const unsigned char *)q; }
static double now(void) { struct timespec t; clock_gettime(CLOCK_MONOTONIC, &t); return t.tv_sec + t.tv_nsec * 1e-9; }
static long long with_branch(void) {          /* if (a[i] >= 128) sum += a[i]; */
    long long s = 0;
    for (int p = 0; p < PASSES; p++)
        for (int i = 0; i < N; i++)
            if (a[i] >= 128) s += a[i];
    return s;
}
static long long branchless(void) {           /* mask = 0 or all-ones: no branch on the data */
    long long s = 0;
    for (int p = 0; p < PASSES; p++)
        for (int i = 0; i < N; i++) { int m = -(a[i] >= 128); s += a[i] & m; }
    return s;
}
static double timed(long long (*f)(void), long long *s) {   /* best of 7 runs: less noise */
    double best = 1e9; for (int r = 0; r < 7; r++) { double t = now(); *s = f(); t = now() - t; if (t < best) best = t; }
    return best;
}
int main(void) {
    unsigned x = 2026u; long long s[4];
    for (int i = 0; i < N; i++) { x = x * 1664525u + 1013904223u; a[i] = (unsigned char)(x >> 24); }
    double ub = timed(with_branch, &s[0]), ul = timed(branchless, &s[1]);
    qsort(a, N, 1, cmp);                       /* same values, now in increasing order */
    double sb = timed(with_branch, &s[2]), sl = timed(branchless, &s[3]);
    printf("sums equal: %s (sum = %lld)\n", (s[0] == s[1] && s[1] == s[2] && s[2] == s[3]) ? "yes" : "NO", s[0]);
    printf("with branch: unsorted / sorted = %.1f\nbranchless : unsorted / sorted = %.1f\n", ub / sb, ul / sl);
    printf("unsorted   : branch / branchless = %.1f\n", ub / ul);
    return 0; }

sums equal: yes (sum = 315495400)
with branch: unsorted / sorted = 2.7
branchless : unsorted / sorted = 1.0
unsorted   : branch / branchless = 1.7

Indirect শাখার অনুমান

দিক নয়, গন্তব্যই যেখানে প্রশ্ন — indirect branch prediction. C++/Java-র virtual function call, function pointer, switch-এর jump table (পর্ব ২৯) আর Python/JavaScript-এর interpreter-এর dispatch লুপ (প্রতিটি bytecode opcode-এর জন্য একটি লাফ) — সবগুলোর target অনেক রকম হতে পারে। সরল BTB শুধু শেষ target মনে রাখে; আধুনিক core history দিয়েও target বাছাই করে (TAGE-এর ধারণায় তৈরি indirect predictor, যেমন ITTAGE, গবেষণায় পরিচিত)। পুরোনো interpreter-এ “প্রতিটি opcode-এর শেষে নিজস্ব লাফ” (threaded code) কৌশল শাখাকে বেশি অনুমানযোগ্য করত; নতুন predictor-এ এর সুবিধা কমে এসেছে বলে কিছু গবেষণা দেখিয়েছে।

Predictor আর নিরাপত্তা

Predictor-এর টেবিল একটি ভাগাভাগি করা অবস্থা: একই core-এ চলা ভিন্ন প্রোগ্রাম একই BTB আর counter ব্যবহার করতে পারে। ২০১৮ সালে প্রকাশিত Spectre দেখায়, কেউ predictor-কে ইচ্ছামতো “শিখিয়ে” অন্য প্রোগ্রামকে ভুল পথে অনুমান করাতে পারলে, সেই অনুমানের পথে চলা instruction-গুলো cache-এ চিহ্ন রেখে যায় — ফল ফেলে দিলেও। প্রতিরক্ষার মধ্যে আছে speculation-বাধা instruction, compiler-এর retpoline, context switch-এ predictor-এর অবস্থা মুছে ফেলা বা আলাদা রাখা, আর নতুন chip-এ hardware-স্তরের বিচ্ছিন্নতা। পুরো আলোচনা, শুধু প্রতিরক্ষার দিক থেকে, পর্ব ৪১-এ (Speculative execution আর নিরাপত্তা)।

৯ · AI-এর যুগে branch prediction

AI টুল branch prediction-এর ধারণা সুন্দর ব্যাখ্যা করে, কিন্তু সংখ্যার কাজে প্রায়ই ভুল করে — আর এই বিষয়ের প্রায় সব প্রশ্নই সংখ্যার। প্রচলিত ভুলগুলো:

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

• শুরুর state (00, 01, N…) প্রশ্নের সাথে মিলেছে — ভিন্ন শুরু মানে ভিন্ন উত্তর
• Trace-টি নিজে এই পর্বের simulator-এ বা একটি ছোট স্ক্রিপ্টে চালিয়ে ভুলের সংখ্যা মিলিয়েছি
• CPI-র সূত্রে শুধু ভুল অনুমান (বা stall-এ সব শাখা) গোনা হয়েছে, আর data hazard-এর stall আলাদা যোগ হয়েছে কি না দেখেছি
• gshare-এর index বিট ধরে ধরে হাতে XOR করেছি, PC-র নিচের ২ বিট বাদ দিয়ে
• Chip-এর কোনো নির্দিষ্ট সংখ্যা (penalty, টেবিলের আকার, নির্ভুলতা) থাকলে নির্মাতার প্রকাশনা বা নির্ভরযোগ্য পরিমাপে খুঁজেছি
• Performance-এর দাবি নিজের machine-এ perf stat (branch-misses) দিয়ে মেপে দেখেছি