Instruction-level parallelism — superscalar আর VLIW

১ · ILP কী — একসাথে চালানো যায় এমন instruction খোঁজা

একটি রেস্তোরাঁর রান্নাঘর ভাবুন। এক বাবুর্চি যদি একটার পর একটা কাজ করেন — আগে ভাত, ভাত হলে ডাল, ডাল হলে ভাজি — তাহলে প্রতিটি পদ শেষ হতে পুরো সময় লাগে। কিন্তু চুলা চারটি থাকলে ভাত, ডাল আর মাংস একসাথে চড়ানো যায়, কারণ এই তিনটি রান্না একে অপরের জন্য অপেক্ষা করে না। শুধু ভাজির আগে সবজি কাটতেই হবে — সেখানে অপেক্ষা অনিবার্য।

প্রসেসরেও একই প্রশ্ন। একটি প্রোগ্রামের instruction-গুলো লেখা থাকে একটি সারিতে, কিন্তু তাদের অনেকেই একে অপরের ফল ব্যবহার করে না। এমন স্বাধীন instruction একই সময়ে চালানোর সুযোগকে বলে instruction-level parallelism বা ILP. পর্ব ৩৫-এর pipeline-ও এক ধরনের ILP — সেখানে পাঁচটি instruction পাঁচটি ভিন্ন stage-এ একসাথে থাকে। কিন্তু সেখানে প্রতি cycle-এ সর্বোচ্চ একটি instruction শেষ হয়: ideal CPI = ১.

এই পর্বের প্রশ্ন আরও এক ধাপ বড়: প্রতি cycle-এ একাধিক instruction শুরু আর শেষ করা যায় কি? তখন আমরা CPI-এর বদলে তার উল্টো সংখ্যাটি ব্যবহার করি — IPC (instructions per cycle):

পর্ব ০৩-এর লৌহসূত্র মনে করুন: CPU time = instruction সংখ্যা × CPI × clock cycle time. গতি বাড়ানোর তিনটি রাস্তা — কম instruction, ছোট CPI, দ্রুত clock. Pipeline গভীর করা (superpipelining) clock বাড়ায়; ILP-এর মূল লক্ষ্য CPI কমানো, প্রতি cycle-এ বেশি কাজ করিয়ে। ১৯৯০-এর দশক থেকে ২০০০-এর দশকের শুরু পর্যন্ত প্রসেসরের গতির বড় একটি অংশ এসেছে এই দুই কৌশলের মিলন থেকে।

২ · ILP-এর সীমা — তিন রকম dependence

পর্ব ৩৬-এ data dependence-এর তিন রূপ দেখেছেন — RAW, WAR আর WAW — আর প্রমাণ করেছেন যে in-order ৫-stage pipeline-এ শুধু RAW বিপদ। একাধিক instruction একসাথে চালাতে গেলে ছবিটা বদলায়: এখন instruction-এর ক্রমই আমরা বদলাতে চাই, তাই তিনটি dependence-ই সীমা হয়ে দাঁড়ায়। সাথে যোগ হয় চতুর্থ একটি — branch-এর কারণে।

মেমরির ক্ষেত্রেও dependence আছে: একটি sw আর পরের একটি lw যদি একই ঠিকানা ছোঁয়, তাদের ক্রম বদলানো যায় না। সমস্যা হলো, ঠিকানা প্রায়ই compile-এর সময় জানা থাকে না — দুটি pointer একই জায়গা দেখাচ্ছে কি না (aliasing), compiler নিশ্চিত হতে না পারলে সাবধানে পুরোনো ক্রমই রাখে।

কয়েকটি গুরুত্বপূর্ণ পর্যবেক্ষণ। এক, সাধারণ integer প্রোগ্রামে প্রায় প্রতি চার থেকে সাতটি instruction-এ একটি branch আসে বলে বহু পাঠ্যবইয়ে উল্লেখ আছে। তাই দুই branch-এর মাঝের একটানা কোড — basic block — খুব ছোট, আর তার ভেতরে স্বাধীন instruction খুব বেশি থাকে না। দুই, বড় ILP পেতে হলে branch পেরিয়ে, অর্থাৎ কয়েকটি basic block মিলিয়ে, instruction খুঁজতে হয়। তিন, compiler বা hardware যত বেশি instruction-এর একটি “জানালা” দেখতে পায়, তত বেশি স্বাধীন কাজ খুঁজে পায় — কিন্তু জানালা বড় করার দামও তত বেশি।

৩ · Dataflow limit — dependence graph আর critical path

একটি কোডে কতটা ILP আছে, মাপার সবচেয়ে পরিষ্কার উপায় হলো তার dependence graph আঁকা। প্রতিটি instruction একটি node. i থেকে j-তে একটি তীর মানে j-কে i-এর পরে চলতে হবে। তীরের গায়ে লেখা থাকে কত cycle পরে: RAW-এ i-এর latency (এই পর্বে lw-এর ২ cycle, বাকি সবার ১ cycle); WAR-এ ০ (একই cycle-এ চলতে পারে, কারণ পড়া হয় শুরুতে আর লেখা পরে); WAW-এ ১.

এখন ধরুন hardware অসীম — যত খুশি ALU, যত খুশি memory port, আর branch নেই। তাহলে প্রতিটি instruction শুরু হবে তার সব পূর্বসূরির শর্ত মিটলেই:

কেন এটিই সর্বনিম্ন সময়? যেকোনো একটি পথ i₁ → i₂ → … → i_k নিন। প্রতিটি তীর বলে পরেরটি অন্তত w cycle পরে শুরু হবে, তাই পুরো পথটি শেষ হতে অন্তত তীরগুলোর ওজনের যোগফল আর শেষ instruction-এর নিজের latency লাগে — যত ALU-ই থাকুক। অর্থাৎ যেকোনো schedule-এর সময় ≥ সবচেয়ে ভারী পথের দৈর্ঘ্য। উল্টোদিকে, অসীম hardware-এ উপরের “যত তাড়াতাড়ি সম্ভব” schedule ঠিক সেই দৈর্ঘ্যেই শেষ হয় (প্রতিটি instruction-এর start তার সবচেয়ে ভারী আগমন-পথের দৈর্ঘ্য, induction দিয়ে প্রমাণ)। তাই সবচেয়ে ভারী পথ — critical path — হলো সময়ের নিখুঁত নিম্নসীমা। একে বলে dataflow limit.

একটি ছোট উদাহরণ নিই। C-তে y = (a + b) & (c − d), যেখানে a, b, c, d, y মেমরিতে x10 থেকে ০, ৪, ৮, ১২ আর ১৬ bytes দূরে। একজন অসাবধান programmer (বা register কম থাকা compiler) x5 আর x6 দুবার ব্যবহার করেছে:

I1: lw  x5, 0(x10)     # x5 = a
I2: lw  x6, 4(x10)     # x6 = b
I3: add x7, x5, x6     # x7 = a + b
I4: lw  x5, 8(x10)     # x5 = c   (x5 আবার!)
I5: lw  x6, 12(x10)    # x6 = d   (x6 আবার!)
I6: sub x8, x5, x6     # x8 = c - d
I7: and x9, x7, x8     # x9 = (a + b) & (c - d)
I8: sw  x9, 16(x10)    # y = x9

নিচের stepper-এ graph-টি ধাপে ধাপে গড়ে তুলে critical path বের করি:

হাতে এভাবে হিসাব করা ছোট কোডে চলে, কিন্তু বড় কোডে ভুল হবেই। নিচের analyser একই কাজ করে: instruction-এর তালিকা পড়ে, সব RAW, WAR, WAW জোড়া খোঁজে (মাঝখানে অন্য লেখক থাকলে বাদ দেয়), তারপর দুইভাবে start cycle হিসাব করে — সব তীর মেনে, আর শুধু RAW মেনে (renaming-এর পরে যা থাকে)। Run চাপুন, তারপর নিজের কোড বসিয়ে দেখুন:

// Dependence-graph analyser: RAW / WAR / WAW, critical path and ideal IPC
const prog = ["lw  x5, 0(x10)", "lw  x6, 4(x10)", "add x7, x5, x6", "lw  x5, 8(x10)",
              "lw  x6, 12(x10)", "sub x8, x5, x6", "and x9, x7, x8", "sw  x9, 16(x10)"];
const LAT = { lw: 2 };                                // load: 2 cycles, everything else: 1
const I = prog.map(s => {
  const [op, ...a] = s.replace(/[(),]/g, " ").trim().split(/\s+/);
  const r = a.filter(t => /^x\d+$/.test(t)).map(t => +t.slice(1)).filter(x => x);
  const st = op === "sw";                             // sw rs2, imm(rs1): writes no register
  return { op, rd: st ? 0 : r[0], src: st ? r : r.slice(1), lat: LAT[op] || 1 };
});
const between = (i, j, r) => I.slice(i + 1, j).some(q => q.rd === r);   // another writer of r?
const edges = [];                                      // [from, to, type, reg]
I.forEach((b, j) => I.slice(0, j).forEach((a, i) => {
  if (a.rd && b.src.includes(a.rd) && !between(i, j, a.rd)) edges.push([i, j, "RAW", a.rd]);
  for (const r of new Set(a.src)) if (b.rd === r && !between(i, j, r)) edges.push([i, j, "WAR", r]);
  if (a.rd && a.rd === b.rd && !between(i, j, a.rd)) edges.push([i, j, "WAW", a.rd]);
}));
for (const t of ["RAW", "WAR", "WAW"])
  console.log(t + ": " + edges.filter(e => e[2] === t).map(([i, j, , r]) => `I${i + 1}->I${j + 1}(x${r})`).join("  "));
function earliest(types) {                             // unlimited hardware: start = max over edges
  const s = [];
  I.forEach((q, j) => {
    s[j] = 1;
    for (const [a, b, t] of edges) if (b === j && types.includes(t))
      s[j] = Math.max(s[j], s[a] + (t === "RAW" ? I[a].lat : t === "WAW" ? 1 : 0));
  });
  const len = Math.max(...I.map((q, k) => s[k] + q.lat - 1));
  console.log(`\n${types.join("+")}: start cycles ${s.join(" ")}`);
  console.log(`  critical path = ${len} cycles, ideal IPC = ${I.length}/${len} = ${(I.length / len).toFixed(2)}`);
}
earliest(["RAW", "WAR", "WAW"]);                       // registers as written
earliest(["RAW"]);                                     // after renaming: true dependences only

RAW: I1->I3(x5)  I2->I3(x6)  I4->I6(x5)  I5->I6(x6)  I3->I7(x7)  I6->I7(x8)  I7->I8(x9)
WAR: I3->I4(x5)  I3->I5(x6)
WAW: I1->I4(x5)  I2->I5(x6)

RAW+WAR+WAW: start cycles 1 1 3 3 3 5 6 7
  critical path = 7 cycles, ideal IPC = 8/7 = 1.14

RAW: start cycles 1 1 3 1 1 3 4 5
  critical path = 5 cycles, ideal IPC = 8/5 = 1.60

৪ · Multiple issue — CPI যখন ১-এর নিচে নামে

কোডে ILP আছে জানলাম। এখন hardware-কে প্রতি cycle-এ একাধিক instruction শুরু (issue) করতে দিতে হবে — একে বলে multiple issue. প্রতি cycle-এ সর্বোচ্চ কয়টি instruction issue হতে পারে, তাকে বলে issue width; প্রতিটি জায়গাকে বলে একটি issue slot. ২-way প্রসেসরে প্রতি cycle-এ ২টি slot, ৪-way-তে ৪টি। কোনো slot-এ কাজ না পেলে সেটি নষ্ট হয় — আর এই নষ্ট slot-ই multiple issue-এর আসল শত্রু।

কোন instruction কোন cycle-এ একসাথে যাবে — এই সিদ্ধান্ত কে নেয়, তার ওপর ভিত্তি করে দুটি বড় পরিবার:

Superscalar-এর ভেতরেও দুটি ধরন আছে। In-order superscalar প্রোগ্রামের ক্রম ঠিক রাখে: পরপর instruction-গুলো থেকে যতগুলো একসাথে যেতে পারে পাঠায়, প্রথম যে আটকায় সেখানেই থামে। Out-of-order superscalar আটকে থাকা instruction-কে পাশ কাটিয়ে পরের স্বাধীন instruction আগে চালায় — এর বিস্তারিত (Tomasulo, renaming, reorder buffer) আছে পর্ব ৪০-এ। এই পর্বে আমরা in-order superscalar আর VLIW নিয়ে কাজ করব, যেখানে ভালো ফলের জন্য compiler-এর scheduling সবচেয়ে জরুরি।

৫ · দুই-পথের in-order superscalar RISC-V — issue packet-এর নিয়ম

Patterson–Hennessy-র বইয়ের পরিচিত উদাহরণের ধাঁচে একটি সরল dual-issue RISC-V pipeline নিই। প্রতি cycle-এ দুটি instruction একসাথে fetch, decode আর issue হয় — এই জোড়াকে বলে issue packet. নিয়মগুলো:

1. Slot ১: ALU বা branch (add, addi, sub, bne …); slot ২: load বা store (lw, sw). দুটি ALU instruction বা দুটি load একসাথে যেতে পারে না।
2. একই packet-এর মধ্যে RAW চলবে না: packet-এর দুটি instruction একই সময়ে register পড়ে, তাই একটি অন্যটির ফল চাইলে তাকে পরের cycle-এ যেতে হবে। একই packet-এ WAR চলে — পড়া হয় শুরুতে, লেখা পরে।
3. Latency: ALU-র ফল forwarding দিয়ে পরের cycle-এর packet পায় (latency ১)। lw-এর ফল এক cycle দেরিতে আসে (latency ২) — অর্থাৎ load-use-এর একটি ফাঁকা cycle.
4. Branch packet শেষ করে: লুপের branch লুপের শেষ packet-এ বসে। ধরে নেওয়া হচ্ছে branch prediction নিখুঁত, তাই branch-এর জন্য বাড়তি penalty নেই (পর্ব ৩৭-এর বিষয় আলাদা রাখছি)।

Hardware-এর দাম: port, adder আর forwarding-এর তার

একসাথে একটি ALU instruction আর একটি store চালাতে register file-কে এক cycle-এ চারটি register পড়তে হয় — ALU-র জন্য দুটি (rs1, rs2), store-এর জন্য দুটি (base আর data). আর একটি ALU ফল ও একটি load ফল একই cycle-এ লিখতে হতে পারে। তাই লাগে ৪টি read port আর ২টি write port, যেখানে scalar pipeline-এ ছিল ২ আর ১. Register file-এর আয়তন port-এর সংখ্যার সাথে দ্রুত বাড়ে, কারণ প্রতিটি bit cell-এ প্রতিটি port-এর জন্য আলাদা তার আর transistor লাগে। Load/store-এর ঠিকানা হিসাবের জন্য আলাদা একটি adder লাগে, কারণ ALU-টি তখন অন্য instruction-এর কাজে ব্যস্ত। আর forwarding-এর পথ প্রায় দ্বিগুণ: দুটি pipeline-এর ফল এখন চারটি operand ইনপুটের যেকোনোটিতে পৌঁছাতে পারে।

Latency-র অর্থও বদলায়। Scalar pipeline-এ load-use মানে একটি instruction-এর জায়গা নষ্ট; dual-issue-এ এক cycle ফাঁকা মানে দুটি issue slot নষ্ট। ALU-র ফল scalar pipeline-এ পরের instruction-ই পেত; এখন একই packet-এর সঙ্গী সেটি পায় না, তাই নির্ভরশীল load/store-কে পরের packet-এ যেতে হয়। অর্থাৎ width বাড়লে একই latency “বেশি instruction-এর সমান” হয়ে যায় — scheduling তাই আরও জরুরি।

একটি লুপ cycle ধরে সাজানো

C-তে for (p = a; p != end; p++) *p += s; — প্রতিটি উপাদানের সাথে একটি সংখ্যা যোগ। x10 = p, x11 = s, x12 = end. RV32I-এ লুপের body:

Loop: lw   x5, 0(x10)      # x5 = *p
      add  x5, x5, x11     # x5 = *p + s
      sw   x5, 0(x10)      # *p = x5
      addi x10, x10, 4     # p++ (৪ bytes)
      bne  x10, x12, Loop  # p != end হলে আবার

লেখা ক্রমেই packet বানালে: cycle ১-এ lw; add-কে load-এর জন্য cycle ৩ পর্যন্ত অপেক্ষা করতে হয়, তাই cycle ২ পুরো ফাঁকা; cycle ৪-এ sw আর addi জোড়া বাঁধে (ভিন্ন slot, আর তাদের মধ্যে শুধু WAR); cycle ৫-এ bne. ৫টি instruction ৫ cycle-এ — IPC ১.০০, dual-issue-এর কোনো লাভই হলো না! এবার compiler একটি কৌশল করে: addi-কে ওপরে তুলে প্রথম packet-এ lw-এর ঠিক পরে বসায়, আর তার পরে যে sw চলবে তার offset ০ থেকে −৪ করে দেয়, যাতে ঠিকানা একই থাকে। নিচের stepper-এ নতুন schedule দেখুন (শুরুতে x10 = 1000, x11 = 3, Mem[1000] = 7):

নিচের scheduler এই নিয়মগুলো মেনে প্রতিটি cycle-এর packet সাজায়। reorder = false হলে hardware-এর মতো লেখা ক্রমে চলে — প্রথম যে instruction আটকায়, সেখানেই সেই cycle শেষ। reorder = true হলে compiler-এর মতো list scheduling করে: যে instruction-এর পরের পথ সবচেয়ে লম্বা, তাকে আগে বসায়, আর pointer-এর addi-এর পরে বসা load/store-এর offset ঠিক করে দেয়। চারটি সংস্করণ চলবে — মূল ক্রম, ক্রম বদলানো, ৪ বার unroll করা কিন্তু শুধু x5 দিয়ে, আর ৪ বার unroll করে নাম বদলানো:

// 2-way superscalar: per cycle one ALU/branch + one load/store slot; latency ALU 1, lw 2
function run(name, body, reorder) {
  const P = body.map(s => { const [op, ...a] = s.replace(/[(),]/g, " ").trim().split(/\s+/);
    const r = a.filter(t => /^x\d+$/.test(t)).map(t => +t.slice(1)), none = op === "sw" || op === "bne";
    return { s, op, mem: op === "lw" || op === "sw", rd: none ? 0 : r[0], src: none ? r : r.slice(1) }; });
  const ptr = P.findIndex(q => q.op === "addi"), imm = +body[ptr].split(",")[2], E = []; // [i, j, gap]
  P.forEach((b, j) => P.slice(0, j).forEach((a, i) => {
    if (b.op === "bne") E.push([i, j, 0]);                                   // branch closes the body
    if (a.rd && b.src.includes(a.rd)) E.push([i, j, a.op === "lw" ? 2 : 1]); // RAW
    if (b.rd && a.src.includes(b.rd) && !(reorder && j === ptr && a.mem)) E.push([i, j, 0]); // WAR
    if (a.rd && a.rd === b.rd) E.push([i, j, 1]);                            // WAW
  }));
  const h = P.map(() => 0); for (let j = P.length - 1; j >= 0; j--) for (const [i, k, d] of E) if (k === j) h[i] = Math.max(h[i], h[j] + d);
  const order = P.map((_, j) => j).sort((x, y) => reorder ? h[y] - h[x] || x - y : x - y);
  const at = [], rows = []; for (let c = 1; at.filter(Boolean).length < P.length; c++) {
    const row = {};
    for (const j of order) {
      if (at[j]) continue;
      const slot = P[j].mem ? "mem" : "alu", inOrder = reorder || P.slice(0, j).every((_, i) => at[i]);
      if (inOrder && !row[slot] && E.every(([i, k, d]) => k !== j || (at[i] && c >= at[i] + d))) {
        at[j] = c;  // a load/store issued after the pointer bump gets its offset corrected
        row[slot] = reorder && at[ptr] < c ? P[j].s.replace(/(-?\d+)\(/, (m, o) => `${o - imm}(`) : P[j].s;
      } else if (!reorder) break;                               // in-order: nobody may overtake
    }
    rows.push(row);
  }
  console.log(`${name}: ${P.length} instructions, ${rows.length} cycles, IPC = ${(P.length / rows.length).toFixed(2)}`);
  rows.forEach((r, c) => console.log(`  ${String(c + 1).padStart(2)}  ${(r.alu || "-").padEnd(19)}${r.mem || "-"}`));
}
const loop = ["lw x5, 0(x10)", "add x5, x5, x11", "sw x5, 0(x10)", "addi x10, x10, 4", "bne x10, x12, Loop"];
const unroll = rename => [0, 1, 2, 3].flatMap(k => { const r = rename ? 5 + k : 5;
  return [`lw x${r}, ${4 * k}(x10)`, `add x${r}, x${r}, x11`, `sw x${r}, ${4 * k}(x10)`]; })
  .concat(["addi x10, x10, 16", "bne x10, x12, Loop"]);
run("A) original order", loop, false);  run("B) reordered", loop, true);
run("C) unrolled x4, only x5", unroll(false), true);  run("D) unrolled x4, renamed", unroll(true), true);

A) original order: 5 instructions, 5 cycles, IPC = 1.00
   1  -                  lw x5, 0(x10)
   2  -                  -
   3  add x5, x5, x11    -
   4  addi x10, x10, 4   sw x5, 0(x10)
   5  bne x10, x12, Loop -
B) reordered: 5 instructions, 4 cycles, IPC = 1.25
   1  addi x10, x10, 4   lw x5, 0(x10)
   2  -                  -
   3  add x5, x5, x11    -
   4  bne x10, x12, Loop sw x5, -4(x10)
C) unrolled x4, only x5: 14 instructions, 16 cycles, IPC = 0.88
   1  addi x10, x10, 16  lw x5, 0(x10)
   2  -                  -
   3  add x5, x5, x11    -
   4  -                  sw x5, -16(x10)
   5  -                  lw x5, -12(x10)
   6  -                  -
   7  add x5, x5, x11    -
   8  -                  sw x5, -12(x10)
   9  -                  lw x5, -8(x10)
  10  -                  -
  11  add x5, x5, x11    -
  12  -                  sw x5, -8(x10)
  13  -                  lw x5, -4(x10)
  14  -                  -
  15  add x5, x5, x11    -
  16  bne x10, x12, Loop sw x5, -4(x10)
D) unrolled x4, renamed: 14 instructions, 8 cycles, IPC = 1.75
   1  addi x10, x10, 16  lw x5, 0(x10)
   2  -                  lw x6, -12(x10)
   3  add x5, x5, x11    lw x7, -8(x10)
   4  add x6, x6, x11    lw x8, -4(x10)
   5  add x7, x7, x11    sw x5, -16(x10)
   6  add x8, x8, x11    sw x6, -12(x10)
   7  -                  sw x7, -8(x10)
   8  bne x10, x12, Loop sw x8, -4(x10)

৬ · Loop unrolling আর compiler-এর register renaming

একটি উপাদানের কাজ একটি শিকল: load → add → store. শিকলের ভেতরে ILP নেই। কিন্তু ভিন্ন উপাদানের শিকলগুলো একে অপরের ওপর নির্ভর করে না — a[0]-এর হিসাব আর a[1]-এর হিসাব সম্পূর্ণ স্বাধীন। Loop unrolling লুপের body কয়েকবার পাশাপাশি লিখে এই স্বাধীন শিকলগুলোকে একই basic block-এ নিয়ে আসে, যাতে scheduler তাদের মিশিয়ে সাজাতে পারে। তবে D আর C-এর পার্থক্য দেখাল: unrolling একা যথেষ্ট নয়, সাথে register-এর নাম বদলাতে হবে।

এখানে register renaming করেছে compiler — compile-এর সময়, ISA-র দৃশ্যমান register দিয়ে। RV32I-এ মাত্র ৩২টি integer register, তার কিছু আবার stack pointer, return address, zero-র মতো নির্দিষ্ট কাজে বাঁধা। তাই compiler-এর renaming-এর একটি স্বাভাবিক সীমা আছে, যাকে বলে register pressure. Out-of-order hardware চলার সময় একই কাজ করে ISA-র চোখের আড়ালে, শতাধিক physical register দিয়ে — সেটি পর্ব ৪০-এর বিষয়।

Unrolling + renaming + instruction scheduling — এই তিনটি একসাথে static ILP-এর মূল অস্ত্র। Compiler-এর scheduler-টি আসলে পর্ব ৩৬-এর list scheduling-এরই প্রশস্ত রূপ: প্রতিটি cycle-এ প্রস্তুত instruction-গুলো থেকে slot অনুযায়ী বেছে নেওয়া, যার সামনের পথ সবচেয়ে লম্বা তাকে অগ্রাধিকার দিয়ে।

৭ · VLIW আর EPIC — compiler-ই যখন scheduler

Dual-issue-এর ধারণা চরমে নিলে পাওয়া যায় VLIW — very long instruction word. এখানে একটি “instruction” আসলে কয়েকটি operation-এর একটি লম্বা গুচ্ছ — bundle. প্রতিটি bundle-এ নির্দিষ্ট সংখ্যক slot, প্রতিটি slot একটি নির্দিষ্ট functional unit-এর জন্য। Compiler আগে থেকেই ঠিক করে কোন operation কোন bundle-এর কোন slot-এ যাবে। Hardware শুধু প্রতি cycle-এ একটি bundle তুলে সব slot একসাথে চালায় — dependence পরীক্ষার জটিল লজিক প্রায় নেই।

কিন্তু একটি slot-এ বসানোর মতো কাজ না পেলে? তখন সেখানে একটি nop বসাতে হয়। ক্লাসিক VLIW-এ hardware interlock না থাকায় latency-র ফাঁকটুকুও compiler-কে পুরো nop bundle দিয়ে ভরতে হয়। নিচের packer অংশ ৩-এর কোডটি (নাম বদলানো সংস্করণ) N টি একই রকম slot-এর bundle-এ সাজায় আর nop গোনে:

// VLIW bundle packer: N identical slots per bundle, no hardware interlocks,
// so every empty slot must be filled with an explicit nop by the compiler.
const block = ["lw  x5, 0(x10)", "lw  x6, 4(x10)", "add x7, x5, x6", "lw  x15, 8(x10)",
               "lw  x16, 12(x10)", "sub x8, x15, x16", "and x9, x7, x8", "sw  x9, 16(x10)"];
const B = block.map(s => {
  const [op, ...a] = s.replace(/[(),]/g, " ").trim().split(/\s+/);
  const r = a.filter(t => /^x\d+$/.test(t)).map(t => +t.slice(1));
  return { s, lat: op === "lw" ? 2 : 1, rd: op === "sw" ? 0 : r[0], src: op === "sw" ? r : r.slice(1) };
});
const pred = B.map((b, j) => B.slice(0, j).map((a, i) => i).filter(i => B[i].rd && b.src.includes(B[i].rd)));
const h = B.map(() => 0);                       // height: longest latency path to the end
for (let j = B.length - 1; j >= 0; j--) for (const i of pred[j]) h[i] = Math.max(h[i], h[j] + B[i].lat);
function pack(N) {
  const at = [], bundles = [];
  for (let c = 1; at.filter(Boolean).length < B.length; c++) {
    const ready = B.map((_, j) => j).filter(j => !at[j] && pred[j].every(i => at[i] && at[i] + B[i].lat <= c));
    const pick = ready.sort((x, y) => h[y] - h[x] || x - y).slice(0, N);
    pick.forEach(j => at[j] = c);
    bundles.push([...pick.map(j => B[j].s), ...Array(N - pick.length).fill("nop")]);
  }
  const nops = bundles.length * N - B.length;
  console.log(`N = ${N}: ${bundles.length} bundles, ${bundles.length * N} slots, ${nops} nops ` +
              `(${Math.round(100 * nops / (bundles.length * N))}% empty), IPC = ${(B.length / bundles.length).toFixed(2)}`);
  bundles.forEach((b, k) => console.log(`  ${k + 1}: { ${b.map(s => s.padEnd(16)).join(" | ")} }`));
}
[1, 2, 4].forEach(pack);

N = 1: 8 bundles, 8 slots, 0 nops (0% empty), IPC = 1.00
  1: { lw  x5, 0(x10)   }
  2: { lw  x6, 4(x10)   }
  3: { lw  x15, 8(x10)  }
  4: { lw  x16, 12(x10) }
  5: { add x7, x5, x6   }
  6: { sub x8, x15, x16 }
  7: { and x9, x7, x8   }
  8: { sw  x9, 16(x10)  }
N = 2: 6 bundles, 12 slots, 4 nops (33% empty), IPC = 1.33
  1: { lw  x5, 0(x10)   | lw  x6, 4(x10)   }
  2: { lw  x15, 8(x10)  | lw  x16, 12(x10) }
  3: { add x7, x5, x6   | nop              }
  4: { sub x8, x15, x16 | nop              }
  5: { and x9, x7, x8   | nop              }
  6: { sw  x9, 16(x10)  | nop              }
N = 4: 5 bundles, 20 slots, 12 nops (60% empty), IPC = 1.60
  1: { lw  x5, 0(x10)   | lw  x6, 4(x10)   | lw  x15, 8(x10)  | lw  x16, 12(x10) }
  2: { nop              | nop              | nop              | nop              }
  3: { add x7, x5, x6   | sub x8, x15, x16 | nop              | nop              }
  4: { and x9, x7, x8   | nop              | nop              | nop              }
  5: { sw  x9, 16(x10)  | nop              | nop              | nop              }

VLIW-এর দুর্বলতা

• Binary compatibility: latency আর slot-এর সংখ্যা ISA-তে প্রায় স্থায়ী হয়ে যায়। পরের প্রজন্মে একটি unit দ্রুত বা ধীর হলে, বা slot বাড়লে, পুরোনো binary হয় ভুল চলে, নয়তো সুবিধা পায় না — নতুন করে compile করতে হয়। পর্ব ৩৬-এর MIPS load delay slot-এর শিক্ষারই বড় রূপ।
• অজানা latency: compile-এর সময় compiler জানে না কোন load cache-এ পাবে আর কোনটি miss করবে। Miss হলে পুরো যন্ত্র থামে, কারণ পরের bundle ধরে নিয়েছে মান এসে গেছে। Out-of-order superscalar ঠিক এখানে এগিয়ে থাকে — miss-এর সময়ও সে অন্য স্বাধীন কাজ খুঁজে চালায়।
• Branch: basic block ছোট বলে compiler-কে branch পেরিয়ে schedule করতে হয় — trace scheduling, predication আর speculative load-এর মতো কৌশল লাগে, যা compiler-কে জটিল করে।

তবু VLIW মরে যায়নি। যেখানে কোড অনুমানযোগ্য — সংকেত প্রক্রিয়াকরণ, অডিও, ছবি, modem — সেখানে লুপ বড়, branch কম, আর latency জানা। অনেক DSP তাই VLIW ধাঁচের; Texas Instruments-এর C6000 পরিবার আর Qualcomm-এর Hexagon DSP-কে প্রায়ই এমন নকশার উদাহরণ হিসেবে উল্লেখ করা হয়। একটি নির্দিষ্ট ধরনের কাজের জন্য বানানো chip-এ compiler-এর পক্ষে কোড আগে থেকে সাজানো সহজ, আর hardware সরল থাকায় power কম লাগে — ব্যাটারিচালিত ডিভাইসে যা বড় সুবিধা।

৮ · Superscalar-এর front end — width বনাম আসল IPC

একটি আধুনিক superscalar core-কে কয়েকটি চওড়া ধাপ হিসেবে ভাবা যায়, আর প্রতিটির নিজস্ব width আছে:

যে অংশ পরের ঠিকানা অনুমান করে, instruction আনে আর decode করে, তাকে বলে front end. গড়ে IPC কখনো সবচেয়ে সরু ধাপের width ছাড়াতে পারে না — যেন চার লেনের মহাসড়ক, কিন্তু একটি সেতু দুই লেনের। আর আসল IPC সাধারণত width-এর চেয়ে অনেক কম। প্রকাশিত তথ্যমতে অনেক আধুনিক উচ্চ-পারফরম্যান্স core প্রতি cycle-এ ৪ থেকে ৮টি বা তারও বেশি instruction decode বা issue করতে পারে; অথচ সাধারণ প্রোগ্রামে মাপা গড় IPC প্রায়ই ১ থেকে ৩-এর মধ্যে থাকে বলে দেখা যায় — প্রোগ্রাম আর chip-ভেদে এটি অনেক বদলায়। কারণগুলো এই পর্বেই দেখেছেন: dependence শিকল, cache miss-এর লম্বা অপেক্ষা, branch-এর ভুল অনুমান, আর fetch-এর ভাঙন।

Fetch-এর ভাঙন: taken branch

Instruction cache সাধারণত একটি সারিবদ্ধ টুকরো (যেমন ১৬ বা ৩২ bytes) একবারে দেয়। যদি টুকরোর মাঝখানে একটি taken branch থাকে, তার পরের instruction-গুলো কাজে লাগে না — পরের cycle-এ branch-এর লক্ষ্য থেকে নতুন করে আনতে হয়। ধরুন fetch width ৪, আর গড়ে প্রতি ৬টি instruction-এ একটি taken branch. তাহলে একটি fetch group গড়ে ৪-এর কম কাজের instruction আনবে — অর্থাৎ পেছনের ধাপগুলো যত চওড়াই হোক, front end তাদের পুরো খাওয়াতে পারে না। এজন্য উচ্চ-পারফরম্যান্স core-এ এক cycle-এ একাধিক branch অনুমান, decode করা micro-op জমিয়ে রাখা, আর ছোট লুপকে আলাদা buffer থেকে চালানোর মতো কৌশল দেখা যায়।

নিজে মেপে দেখুন: এক শিকল বনাম চার শিকল

ILP-এর প্রভাব চোখে দেখার সহজ পরীক্ষা: একটি array-এর যোগফল। দুটি লুপই হুবহু একই কাজ করে, একই রকম unroll করা — শুধু প্রথমটিতে সব যোগ একটি চলক s-এ (এক শিকল), দ্বিতীয়টিতে চারটি আলাদা চলকে (চারটি স্বাধীন শিকল)। এটি অংশ ৬-এর renaming-এর C-রূপ। Wandbox-এর gcc এখানে optimization ছাড়া (-O0-এর মতো) compile করে:

#include <stdio.h>
#include <time.h>
#define N 4096
#define REPS 10000
static double a[N];
static double now(void) {
    struct timespec t;
    clock_gettime(CLOCK_MONOTONIC, &t);
    return (double)t.tv_sec + (double)t.tv_nsec * 1e-9;
}
int main(void) {
    for (int i = 0; i < N; i++) a[i] = (double)(i % 7);   /* small whole numbers: sums stay exact */
    double s = 0, t0 = now();
    for (int r = 0; r < REPS; r++)
        for (int i = 0; i < N; i += 4) {    /* one chain: every add waits for the previous one */
            s += a[i]; s += a[i + 1]; s += a[i + 2]; s += a[i + 3];
        }
    double t1 = now(), p0 = 0, p1 = 0, p2 = 0, p3 = 0;
    for (int r = 0; r < REPS; r++)
        for (int i = 0; i < N; i += 4) {    /* four independent chains */
            p0 += a[i]; p1 += a[i + 1]; p2 += a[i + 2]; p3 += a[i + 3];
        }
    double t2 = now(), s4 = p0 + p1 + p2 + p3;
    printf("same sum      : %s (%.0f)\n", s == s4 ? "yes" : "NO", s);
    printf("1 accumulator : %6.1f ms\n", (t1 - t0) * 1e3);
    printf("4 accumulators: %6.1f ms\n", (t2 - t1) * 1e3);
    printf("ratio         : %.1f times faster with 4 chains\n", (t1 - t0) / (t2 - t1));
    return 0;
}

same sum      : yes (122850000)
1 accumulator :  199.2 ms
4 accumulators:   50.6 ms
ratio         : 3.9 times faster with 4 chains

৯ · ILP-এর দেয়াল — limit study, power আর multicore

কোডে আসলে কতটা ILP আছে? এই প্রশ্নের উত্তর খুঁজতে কয়েক দশক ধরে limit study করা হয়েছে: বাস্তব প্রোগ্রামের instruction trace নিয়ে একটি কাল্পনিক যন্ত্রে চালানো, যার কিছু বা সব সীমা তুলে দেওয়া — অসীম register (নিখুঁত renaming), নিখুঁত branch prediction, নিখুঁত memory-ঠিকানা জ্ঞান, অসীম জানালা। ইতিহাসটি মোটামুটি এমন (সংখ্যাগুলো পদ্ধতি আর benchmark-ভেদে অনেক আলাদা, তাই শুধু ধাঁচটুকু নিন):

• ১৯৭০ সালের দিকে Tjaden ও Flynn-এর একটি গবেষণায় basic block-এর ভেতরে গড়ে মাত্র দুইয়ের কাছাকাছি instruction একসাথে চালানো যায় বলে দেখা যায় — এই সীমাকে পরে কেউ কেউ “Flynn bottleneck” বলেছেন।
• ১৯৭২ সালের দিকে Riseman ও Foster দেখান, branch পেরিয়ে দেখতে পারলে অনেক বেশি ILP আছে — কিন্তু তা পেতে hardware অবাস্তব রকম বড় লাগে।
• ১৯৯১ সালে DEC-এর David Wall-এর বহুল উদ্ধৃত “Limits of Instruction-Level Parallelism” গবেষণা দেখায়, নিখুঁত যন্ত্রে ILP বিশাল হলেও বাস্তবসম্মত ধারণায় (সীমিত জানালা, বাস্তব branch prediction, সীমিত renaming) গড় ILP সাধারণত একক অঙ্কে নেমে আসে। Hennessy–Patterson-এর বইয়েও এমন হিসাবের আলোচনা আছে।

অর্থাৎ ILP আছে, কিন্তু তা তুলে আনার খরচ দ্রুত বাড়ে। কয়েকটি কারণ:

• জটিলতা width-এর চেয়ে দ্রুত বাড়ে: প্রতিটি নতুন instruction-কে একই cycle-এর বাকি সবার সাথে dependence-এর জন্য তুলনা করতে হয় — তুলনার সংখ্যা মোটামুটি width-এর বর্গের হারে বাড়ে। Register file-এর port, bypass network-এর তার আর out-of-order-এর অপেক্ষমাণ instruction-এর সারিও একইভাবে বাড়ে।
• Power: dynamic power ≈ α·C·V²·f. প্রতিটি অনুমান-ভিত্তিক কাজ, প্রতিটি তুলনা, প্রতিটি লম্বা তার energy খায় — অথচ IPC-র লাভ ক্রমশ কম। ২০০০-এর দশকের মাঝামাঝি Dennard scaling থেমে গেলে voltage আর কমানো যাচ্ছিল না, আর chip power wall-এ ঠেকে।
• ক্রমহ্রাসমান লাভ: width ৪ থেকে ৮ করলে transistor আর power অনেক বাড়ে, কিন্তু সাধারণ প্রোগ্রামে IPC বাড়ে সামান্য — কারণ কোডেই অতটা ILP নেই, আর memory-র অপেক্ষা সবকিছু থামিয়ে দেয়।

ফলে শিল্প দিক বদলায়। একটি বিশাল core-কে আরও চওড়া করার বদলে একই chip-এ কয়েকটি core বসানো — multicore. ২০০৫ সালে Intel আর AMD দুজনেই প্রথম dual-core desktop প্রসেসর বাজারে আনে। এতে সমান্তরালতার দায়িত্ব hardware থেকে আবার programmer-এর কাছে যায়: instruction-স্তরের বদলে thread-স্তরের সমান্তরালতা। একটি core-এর নষ্ট issue slot কাজে লাগানোর আরেকটি উপায় হলো একাধিক thread-এর instruction মিশিয়ে চালানো — পর্ব ৪৩-এর SMT; আর একই instruction দিয়ে অনেক ডেটা চালানো — পর্ব ৪২-এর SIMD. Multicore আর cache coherence-এর পুরো আলোচনা মডিউল ৯-এ, পর্ব ৫৩ থেকে। আর বেশি speculation-এর একটি অপ্রত্যাশিত দাম — নিরাপত্তার ফাঁক — দেখবেন পর্ব ৪১-এ।

তবে ILP-এর গল্প থেমে যায়নি। আজকের উচ্চ-পারফরম্যান্স core-গুলো এখনো চওড়া out-of-order নকশা, আর প্রতিটি নতুন প্রজন্মে IPC কিছুটা বাড়ানো হয় — কিন্তু সেই লাভ আসে ধীরে, অনেক transistor খরচ করে। ফোনের chip-এ তাই প্রায়ই দুই রকম core থাকে: কয়েকটি বড় চওড়া out-of-order core দ্রুত কাজের জন্য, আর কয়েকটি ছোট core (প্রায়ই in-order superscalar) কম power-এর কাজের জন্য।

১০ · AI-এর যুগে — ILP-এর হিসাব AI দিয়ে, যাচাই নিজে

Scheduling আর cycle গোনা এমন কাজ, যেখানে AI টুল আত্মবিশ্বাসের সাথে ভুল করে, কারণ উত্তর নির্ভর করে খুঁটিনাটি নিয়মের ওপর। এই বিষয়ে AI-এর সাধারণ ভুলগুলো:

• একই packet-এ নির্ভরশীল দুটি instruction বসিয়ে দেওয়া, বা slot-এর ধরন (ALU বনাম load/store) না মানা।
• Load-use latency ভুলে যাওয়া, বা dual-issue-এ এক cycle ফাঁকা মানে যে দুটি slot নষ্ট, তা না ধরা; IPC আর CPI উল্টে ফেলা।
• Unroll করে register-এর নাম না বদলেই বিশাল speedup দাবি করা; বা addi আগে তুলে load/store-এর offset ঠিক না করা — যা প্রোগ্রামকে ভুল ঠিকানায় পাঠায়।
• MIPS আর RISC-V-এর রীতি মেশানো ($t0-ধাঁচের register, branch delay slot), বা RV32-এর জায়গায় RV64-এর ld/sd আর ৮-byte offset লেখা।
• নির্দিষ্ট chip-এর width, latency বা Itanium-এর ইতিহাস নিয়ে বানানো সংখ্যা আর তারিখ দেওয়া।

AI-এর দেওয়া scheduling-উত্তর যাচাইয়ের চেকলিস্ট

• নিয়ম স্পষ্ট — কয়টি slot, কোন slot-এ কী যায়, latency কত, branch-এর জন্য কী ধরা হয়েছে
• প্রতিটি packet-এ দুটি instruction-এর মধ্যে RAW নেই, আর load-এর ফল অন্তত দুই cycle পরে ব্যবহার হয়েছে
• IPC = instruction ÷ cycle, আর cycle সংখ্যা অন্তত critical path আর (load/store সংখ্যা ÷ load/store slot)-এর চেয়ে বড়
• ক্রম বদলের পরে প্রতিটি offset হাতে হিসাব করে দেখেছি ঠিকানা আগের মতোই আছে
• উত্তরটি উপরের scheduler-এ (বা নিজের স্ক্রিপ্টে) বসিয়ে মিলিয়েছি; বাস্তব chip-এর width বা latency-র দাবি নির্মাতার manual-এ দেখেছি