Out-of-order execution — Tomasulo, register renaming আর reorder buffer

১ · একজন আটকে গেলে সবাই দাঁড়িয়ে — in-order stall-এর দাম

পর্ব ৩৫-এ পাঁচ ধাপের pipeline দেখেছেন, আর পর্ব ৩৬-এ দেখেছেন একটি instruction তার আগের instruction-এর ফলের জন্য অপেক্ষা করলে stall লাগে। সেখানে অপেক্ষা ছিল এক-দুই cycle-এর। কিন্তু বাস্তবের কিছু instruction অনেক ধীর। Floating point-এর ভাগ কয়েক ডজন cycle নিতে পারে। আর যে load-এর ডেটা cache-এ নেই, তাকে main memory থেকে আনতে শত cycle-এর বেশিও লাগতে পারে (cache-এর হিসাব আসবে পর্ব ৪৪ থেকে ৪৭-এ)। In-order core-এর নিয়ম কড়া: পেছনের কেউ সামনের জনকে টপকাতে পারে না। ফলে একটি ধীর instruction আটকালে তার পেছনের সবাই দাঁড়িয়ে থাকে — এমনকি যাদের ওই ফলের কোনো দরকারই নেই।

একটি worked example — ছয়টি instruction

পুরো পর্বে আমরা একটিই ছোট floating point প্রোগ্রাম ব্যবহার করব (RISC-V-এর double-precision instruction; নিয়মের খুঁটিনাটি অংশ ৩-এ)। প্রতিটি instruction-এর execute ধাপের দৈর্ঘ্য ধরা হলো: fld ২ cycle (ঠিকানা হিসাব আর মেমরি পড়া), fadd.d/fsub.d ২ cycle, fmul.d ৬ cycle, fdiv.d ১২ cycle. এগুলো শেখানোর জন্য বেছে নেওয়া সংখ্যা, কোনো নির্দিষ্ট chip-এর নয়।

I1  fld    f2, 0(x1)        # f2 = মেমরি থেকে
I2  fdiv.d f0, f2, f4       # f0 = f2 / f4     (I1-এর ওপর নির্ভর, ১২ cycle)
I3  fadd.d f6, f0, f8       # f6 = f0 + f8     (I2-এর ওপর নির্ভর)
I4  fsub.d f8, f10, f14     # f8 = f10 - f14   (স্বাধীন!)
I5  fmul.d f6, f10, f8      # f6 = f10 * f8    (I4-এর ওপর নির্ভর)
I6  fadd.d f12, f6, f4      # f12 = f6 + f4    (I5-এর ওপর নির্ভর)

প্রথমে dependence-গুলো আলাদা করি (পর্ব ৩৬-এর ভাষায়):

• সত্যিকারের data dependence (RAW): I1 → I2 (f2), I2 → I3 (f0), I4 → I5 (f8), I5 → I6 (f6). এখানে সত্যিই একটি মান এক instruction থেকে আরেকটিতে যায়।
• WAR: I3 f8 পড়ে, পরে I4 f8-এ লেখে। I4 যদি I3-এর আগে লিখে ফেলে, I3 ভুল f8 পাবে।
• WAW: I3 আর I5 দুজনেই f6-এ লেখে; শেষে I5-এর মান থাকতে হবে।

এবার একটি সরল in-order মেশিন ধরুন: প্রতি cycle-এ সর্বোচ্চ একটি instruction issue (চালানোর জন্য পাঠানো), প্রোগ্রামের ক্রমে; কোনো source এখনো লেখা না হলে issue থেমে থাকে (stall-on-use), আর পেছনের সবাইও থামে। Execution unit-গুলো pipelined, তাই একাধিক instruction একসাথে চলতে পারে; ফল লেখার পথ একটি। অংশ ৪-এর simulator যে হিসাব দেবে, তার in-order অংশ এই:

মোট ৩১ cycle. লক্ষ করুন I4-কে: তার ইনপুট f10 আর f14 শুরু থেকেই তৈরি, তবু সে cycle ১৮ পর্যন্ত অপেক্ষা করল, শুধু কারণ সামনের I3 ভাগের ফলের জন্য দাঁড়িয়ে। I4 আটকে থাকায় I5, আর I5 আটকে থাকায় I6 — পুরো শৃঙ্খলটি ভাগের পেছনে সারি দিল। অথচ I4 → I5 → I6 শৃঙ্খলটি ভাগের সাথে সম্পূর্ণ সম্পর্কহীন; সেটি cycle ৫ থেকেই চলতে পারত, ভাগের সমান্তরালে।

২ · Dynamic scheduling-এর ছক — সামনে ক্রমে, মাঝে ক্রমের বাইরে, পেছনে আবার ক্রমে

আধুনিক out-of-order execution-এর প্রায় সব নকশা মোটামুটি তিন ভাগে সাজানো (মূল Tomasulo-তে তৃতীয় ভাগটি ছিল না, তা অংশ ৪-এর শেষে দেখবেন)। এই ছকটি মনে রাখলে পর্বের বাকি সব যন্ত্রাংশ কোথায় বসে, তা পরিষ্কার হয়ে যাবে।

মাঝের অংশে দুটি বিপদ। এক, সত্যিকারের dependence (RAW) — ফল তৈরি না হলে চালানো যাবে না; এটি কেউ দূর করতে পারে না, শুধু অপেক্ষা করা যায়। দুই, name dependence (WAR আর WAW) — ক্রম ভেঙে চালালে এরা সত্যিকারের ভুল ঘটাতে পারে। পর্ব ৩৬-এ দেখেছেন, এরা আসলে নামের সংঘাত: register-এর সংখ্যা কম বলে compiler একই নাম বারবার ব্যবহার করে। দুটি সমাধান ইতিহাসে এসেছে — অপেক্ষা করানো, নয়তো নাম বদলে ফেলা।

Scoreboard বনাম Tomasulo — সংক্ষেপে

১৯৬৪ সালের CDC 6600-এর scoreboard (পর্ব ৩৬-এ পরিচয় হয়েছে) প্রথম পথ নিয়েছিল: একটি কেন্দ্রীয় টেবিল হিসাব রাখে কোন unit ব্যস্ত আর কোন register কে লিখবে, আর hazard দেখলে instruction-কে অপেক্ষা করায়। ১৯৬৭ সালে IBM-এর Robert Tomasulo System/360 Model 91-এর floating point unit-এর জন্য যে পদ্ধতি প্রকাশ করেন, তা দ্বিতীয় পথ নিল: নাম বদলে দেওয়া। দুটির তুলনা (সাধারণভাবে বইয়ে যেভাবে বর্ণিত; দুই মেশিনের সব খুঁটিনাটি এখানে নেই):

একটি ঐতিহাসিক কারণও প্রায়ই উল্লেখ করা হয়: System/360-এর ISA-তে floating point register ছিল মাত্র চারটি। এত কম নামে compiler-কে বারবার একই register ব্যবহার করতেই হতো, তাই WAR আর WAW ছিল সর্বত্র। Hardware-এ নাম বদলানো ছাড়া সমান্তরালতা পাওয়ার উপায় ছিল না।

৩ · Tomasulo-র যন্ত্রপাতি — reservation station, tag আর common data bus

Tomasulo-র algorithm-এ তিনটি যন্ত্রাংশ। প্রথমটি reservation station (RS) — প্রতিটি execution unit-এর সামনে কয়েকটি অপেক্ষার ঘর, প্রতিটির একটি নাম (Add1, Add2, Mult1 …)। এই নামটিই tag. প্রতিটি RS-এ এই ঘরগুলো:

দ্বিতীয় যন্ত্রাংশ register status — প্রতিটি register-এর জন্য একটি ঘর Qi, যা বলে “এই register-এর পরের মান কোন RS লিখবে”. ফাঁকা থাকলে register file-এর মানই ঠিক। তৃতীয়টি common data bus (CDB): কোনো unit কাজ শেষ করলে ফলটি নিজের tag-সহ এই bus-এ ঘোষণা করে। প্রতিটি RS আর register status নিজে শোনে — “আমি কি এই tag-এর অপেক্ষায় ছিলাম?” — আর মিললে মানটি তুলে নেয়।

তিনটি ধাপ

1. Issue: instruction queue-এর মাথা থেকে প্রোগ্রামের ক্রমে, প্রতি cycle-এ একটি। তার ধরনের একটি RS খালি না থাকলে issue থামে (structural hazard). প্রতিটি source-এর জন্য register status দেখা হয়: Qi ফাঁকা হলে register file থেকে মান Vj/Vk-তে কপি; নইলে সেই tag Qj/Qk-তে। তারপর destination register-এর Qi-তে এই RS-এর নাম বসে।
2. Execute: দুটি operand-ই মান হিসেবে হাতে এলে execution শুরু। অপেক্ষার সময় RS CDB শোনে। Load-এর ক্ষেত্রে প্রথমে কার্যকর ঠিকানা হিসাব হয়ে A-তে বসে, তারপর মেমরি পড়া।
3. Write result: ফল তৈরি হলে CDB-তে tag-সহ ঘোষণা। যে সব RS-এর Qj বা Qk এই tag, তারা মান পায়; যে register-এর Qi এই tag, register file-এ মান লেখা হয় আর Qi ফাঁকা হয়। RS-টি খালি হয়।

এই পর্বের হিসাবের নিয়ম (বইভেদে cycle গোনার নিয়ম সামান্য আলাদা হয়, তাই পরীক্ষায় প্রশ্নের নিয়ম আগে পড়ে নেবেন):

• Cycle t-তে issue হলে সবচেয়ে আগে execute শুরু t + ১-এ। কোনো operand cycle W-তে CDB থেকে এলে execute শুরু W + ১-এ। Latency L হলে execute চলে শুরু থেকে শুরু + L − ১ পর্যন্ত।
• Execute শেষের পরের cycle-এ write result, যদি CDB খালি থাকে। এক cycle-এ একটিই write; প্রতিযোগিতা হলে প্রোগ্রামে পুরোনোটি আগে।
• এক cycle-এর ভেতরে ক্রম: আগে write result (CDB), তারপর execute শুরু, তারপর issue. তাই একই cycle-এ CDB-তে আসা মান issue হওয়া instruction সরাসরি পায়, আর ওই cycle-এ খালি হওয়া RS নতুন instruction নিতে পারে।
• Unit-গুলো pipelined (বা যথেষ্ট সংখ্যায়), তাই operand তৈরি হলেই execute শুরু হতে পারে। RS: Load ২টি, Add ৩টি (যোগ-বিয়োগ), Mult ২টি (গুণ-ভাগ; ভেতরে আলাদা multiplier আর divider).

Tag কেন WAR আর WAW মুছে দেয় — একটি যুক্তি

WAR: ধরুন i একটি register R পড়ে, আর পরে j সেই R-এ লেখে। Issue প্রোগ্রামের ক্রমে, তাই i, j-এর আগে issue হয়। Issue-এর মুহূর্তে i R-এর মান কপি করে নেয়, নয়তো তখনকার লেখকের tag ধরে রাখে। পরে j যাই লিখুক, i আর register file থেকে R পড়বে না — তার মান বা tag আগেই ঠিক হয়ে গেছে। আর j-এর tag i-এর Q-তে কখনো বসে না, কারণ j পরে issue হয়েছে। অতএব j যত আগেই লিখুক, i-এর ইনপুট বদলায় না। WAW: i আর j দুজনেই R-এ লেখে, j পরে। j-এর issue-এর সময় Qi[R] = j-এর tag, i-এর tag মুছে গেল। পরে i-এর ফল CDB-তে এলে register status-এ তার tag আর নেই, তাই R-এ লেখা হয় না — i-এর ফল যায় শুধু যারা i-এর tag-এর অপেক্ষায় ছিল তাদের কাছে। ফলে R-এ শেষ পর্যন্ত j-এর মানই থাকে, i আর j যে ক্রমেই শেষ হোক। অর্থাৎ RS-এর tag-গুলো আসলে বাড়তি, অদৃশ্য register — register renaming, যা কোনো আলাদা টেবিল ছাড়াই ঘটে বলে একে implicit renaming বলা হয়। RAW অবশ্য থেকে যায় — তা থাকারই কথা, কারণ সেটি সত্যিকারের ডেটা-প্রবাহ।

এবার উদাহরণের প্রথম দিকের cycle-গুলো টেবিল ধরে দেখুন। প্রতিটি ছবি সেই cycle-এর শেষের অবস্থা; “5–…” মানে execute শুরু হয়েছে, শেষ হয়নি। প্রাথমিক মান: f4 = 2, f8 = 1.5, f10 = 5, f14 = 1, আর মেমরিতে 0(x1)-এ 6.

Instruction            Issue Exec  Write
I1 fld f2, 0(x1)       1     2–…
I2 fdiv.d f0, f2, f4   2
I3 fadd.d f6, f0, f8
I4 fsub.d f8, f10, f14
I5 fmul.d f6, f10, f8
I6 fadd.d f12, f6, f4

RS     Busy Op      Vj   Vk   Qj    Qk    A
Load1  yes  fld     —    —    —     —     0
Load2  no
Add1   no
Add2   no
Add3   no
Mult1  yes  fdiv.d  —    2    Load1 —
Mult2  no

Qi: f0=Mult1  f2=Load1  f6=—  f8=—  f12=—

Instruction            Issue Exec  Write
I1 fld f2, 0(x1)       1     2–…
I2 fdiv.d f0, f2, f4   2
I3 fadd.d f6, f0, f8   3
I4 fsub.d f8, f10, f14
I5 fmul.d f6, f10, f8
I6 fadd.d f12, f6, f4

RS     Busy Op      Vj   Vk   Qj    Qk    A
Load1  yes  fld     —    —    —     —     0
Load2  no
Add1   yes  fadd.d  —    1.5  Mult1 —
Add2   no
Add3   no
Mult1  yes  fdiv.d  —    2    Load1 —
Mult2  no

Qi: f0=Mult1  f2=Load1  f6=Add1  f8=—  f12=—

Instruction            Issue Exec  Write
I1 fld f2, 0(x1)       1     2–3   4
I2 fdiv.d f0, f2, f4   2
I3 fadd.d f6, f0, f8   3
I4 fsub.d f8, f10, f14 4
I5 fmul.d f6, f10, f8
I6 fadd.d f12, f6, f4

RS     Busy Op      Vj   Vk   Qj    Qk    A
Load1  no
Load2  no
Add1   yes  fadd.d  —    1.5  Mult1 —
Add2   yes  fsub.d  5    1    —     —
Add3   no
Mult1  yes  fdiv.d  6    2    —     —
Mult2  no

Qi: f0=Mult1  f2=—  f6=Add1  f8=Add2  f12=—
RF: f2=6

Instruction            Issue Exec  Write
I1 fld f2, 0(x1)       1     2–3   4
I2 fdiv.d f0, f2, f4   2     5–…
I3 fadd.d f6, f0, f8   3
I4 fsub.d f8, f10, f14 4     5–…
I5 fmul.d f6, f10, f8  5
I6 fadd.d f12, f6, f4

RS     Busy Op      Vj   Vk   Qj    Qk    A
Load1  no
Load2  no
Add1   yes  fadd.d  —    1.5  Mult1 —
Add2   yes  fsub.d  5    1    —     —
Add3   no
Mult1  yes  fdiv.d  6    2    —     —
Mult2  yes  fmul.d  5    —    —     Add2

Qi: f0=Mult1  f2=—  f6=Mult2  f8=Add2  f12=—

Instruction            Issue Exec  Write
I1 fld f2, 0(x1)       1     2–3   4
I2 fdiv.d f0, f2, f4   2     5–…
I3 fadd.d f6, f0, f8   3
I4 fsub.d f8, f10, f14 4     5–6   7
I5 fmul.d f6, f10, f8  5
I6 fadd.d f12, f6, f4  6

RS     Busy Op      Vj   Vk   Qj    Qk    A
Load1  no
Load2  no
Add1   yes  fadd.d  —    1.5  Mult1 —
Add2   no
Add3   yes  fadd.d  —    2    Mult2 —
Mult1  yes  fdiv.d  6    2    —     —
Mult2  yes  fmul.d  5    4    —     —

Qi: f0=Mult1  f2=—  f6=Mult2  f8=—  f12=Add3
RF: f2=6  f8=4

Instruction            Issue Exec  Write
I1 fld f2, 0(x1)       1     2–3   4
I2 fdiv.d f0, f2, f4   2     5–…
I3 fadd.d f6, f0, f8   3
I4 fsub.d f8, f10, f14 4     5–6   7
I5 fmul.d f6, f10, f8  5     8–13  14
I6 fadd.d f12, f6, f4  6

RS     Busy Op      Vj   Vk   Qj    Qk    A
Load1  no
Load2  no
Add1   yes  fadd.d  —    1.5  Mult1 —
Add2   no
Add3   yes  fadd.d  20   2    —     —
Mult1  yes  fdiv.d  6    2    —     —
Mult2  no

Qi: f0=Mult1  f2=—  f6=—  f8=—  f12=Add3
RF: f2=6  f6=20  f8=4

Instruction            Issue Exec  Write
I1 fld f2, 0(x1)       1     2–3   4
I2 fdiv.d f0, f2, f4   2     5–16  17
I3 fadd.d f6, f0, f8   3
I4 fsub.d f8, f10, f14 4     5–6   7
I5 fmul.d f6, f10, f8  5     8–13  14
I6 fadd.d f12, f6, f4  6     15–16 (অপেক্ষা)

RS     Busy Op      Vj   Vk   Qj    Qk    A
Load1  no
Load2  no
Add1   yes  fadd.d  3    1.5  —     —
Add2   no
Add3   yes  fadd.d  20   2    —     —
Mult1  no
Mult2  no

Qi: f0=—  f2=—  f6=—  f8=—  f12=Add3
RF: f0=3  f2=6  f6=20  f8=4

Instruction            Issue Exec  Write
I1 fld f2, 0(x1)       1     2–3   4
I2 fdiv.d f0, f2, f4   2     5–16  17
I3 fadd.d f6, f0, f8   3     18–19 20
I4 fsub.d f8, f10, f14 4     5–6   7
I5 fmul.d f6, f10, f8  5     8–13  14
I6 fadd.d f12, f6, f4  6     15–16 18

RS     সব খালি

Qi: সব ফাঁকা
RF: f0=3  f2=6  f6=20  f8=4  f12=22

৪ · Simulator-এ Tomasulo, পাশে in-order — আর Tomasulo-র সীমা

হাতে যা মেলালেন, এবার একটি ছোট simulator-এ চালিয়ে দেখুন। কোডটি ঠিক উপরের নিয়ম মানে: প্রতি cycle-এ প্রথমে CDB-তে একটি write (পুরোনোটি আগে), তারপর execute শুরু, তারপর issue. RS-এর সংখ্যা আর latency উপরে বদলে নিজে পরীক্ষা করতে পারেন।

// Tomasulo: reservation stations (RS) + register status (Qi) + ONE common data bus (CDB)
const LAT = { "fld": 2, "fadd.d": 2, "fsub.d": 2, "fmul.d": 6, "fdiv.d": 12 };   // execute cycles
const UNIT = { "fld": "Load", "fadd.d": "Add", "fsub.d": "Add", "fmul.d": "Mult", "fdiv.d": "Mult" };
const NRS = { Load: 2, Add: 3, Mult: 2 };                                          // RS per unit type
const prog = [["fld", "f2", 0], ["fdiv.d", "f0", "f2", "f4"], ["fadd.d", "f6", "f0", "f8"],
              ["fsub.d", "f8", "f10", "f14"], ["fmul.d", "f6", "f10", "f8"], ["fadd.d", "f12", "f6", "f4"]];
const RF = { f0: 0, f2: 0, f4: 2, f6: 0, f8: 1.5, f10: 5, f12: 0, f14: 1 }, MEM = { 0: 6 }, x1 = 0;
const ALU = { "fadd.d": (a, b) => a + b, "fsub.d": (a, b) => a - b, "fmul.d": (a, b) => a * b, "fdiv.d": (a, b) => a / b };
const Qi = {}, RS = [], t = prog.map(() => ({}));       // Qi[reg] = name of the RS that will write reg
for (const u in NRS) for (let k = 1; k <= NRS[u]; k++) RS.push({ name: u + k, unit: u, busy: false });
const src = x => Qi[x] ? [null, Qi[x]] : [RF[x], null];  // value now, or the tag to wait for
for (let c = 1, next = 0; t.some(x => !x.w); c++) {
  const d = RS.filter(r => r.busy && r.end < c).sort((a, b) => a.i - b.i)[0];  // 1) WRITE: oldest gets the CDB
  if (d) {
    const v = d.op === "fld" ? MEM[d.A] : ALU[d.op](d.Vj, d.Vk);
    for (const r of RS) for (const [V, Q] of [["Vj", "Qj"], ["Vk", "Qk"]])            // every waiting RS listens
      if (r[Q] === d.name) { r[V] = v; r[Q] = null; r.rdy = c; }
    for (const reg in Qi) if (Qi[reg] === d.name) { RF[reg] = v; delete Qi[reg]; }  // only if still newest writer
    t[d.i].w = c; d.busy = false;
  }
  for (const r of RS) if (r.busy && !r.start && !r.Qj && !r.Qk && r.rdy < c) {  // 2) EXECUTE: operands ready earlier
    r.start = t[r.i].s = c; r.end = t[r.i].e = c + LAT[r.op] - 1; if (r.op === "fld") r.A += x1;  // A = address
  }
  const I = prog[next], r = I && RS.find(s => !s.busy && s.unit === UNIT[I[0]]); // 3) ISSUE in order, needs free RS
  if (r) {
    const [op, dst, j, k] = I, ld = op === "fld";
    Object.assign(r, { busy: true, op, i: next, rdy: c, start: 0, end: Infinity, A: ld ? j : null });
    [[r.Vj, r.Qj], [r.Vk, r.Qk]] = ld ? [[null, null], [null, null]] : [src(j), src(k)];
    Qi[dst] = r.name; t[next++].iss = c;                                        // rename: dst now waits for r
  }
}
const txt = I => I[0] === "fld" ? `fld ${I[1]}, ${I[2]}(x1)` : `${I[0]} ${I.slice(1).join(", ")}`;
console.log("instruction             issue  execute   write");
prog.forEach((I, i) => console.log(`${txt(I).padEnd(24)}${String(t[i].iss).padEnd(7)}${(t[i].s + "-" + t[i].e).padEnd(10)}${t[i].w}`));
console.log(`total: ${Math.max(...t.map(x => x.w))} cycles   final: ` + Object.entries(RF).map(([k, v]) => `${k}=${v}`).join(" "));

instruction             issue  execute   write
fld f2, 0(x1)           1      2-3       4
fdiv.d f0, f2, f4       2      5-16      17
fadd.d f6, f0, f8       3      18-19     20
fsub.d f8, f10, f14     4      5-6       7
fmul.d f6, f10, f8      5      8-13      14
fadd.d f12, f6, f4      6      15-16     18
total: 20 cycles   final: f0=3 f2=6 f4=2 f6=20 f8=4 f10=5 f12=22 f14=1

এবার একই প্রোগ্রাম পাশাপাশি দুই যন্ত্রে। নিচের কোড শুধু সময়ের হিসাব করে: in-order মেশিনে source তৈরি না হলে issue থামে (আর আগের কোনো লেখা একই register-এ বাকি থাকলেও, WAW এড়াতে); out-of-order মেশিনে issue একটানা, execute শুরু হয় source তৈরি হলেই। দুটিতেই ফল লেখার পথ একটি।

// Same program, two machines: in-order stall-on-use vs dynamic scheduling (Tomasulo timing, 1 CDB)
const LAT = { "fld": 2, "fadd.d": 2, "fsub.d": 2, "fmul.d": 6, "fdiv.d": 12 };
const prog = [["fld", "f2", []], ["fdiv.d", "f0", ["f2", "f4"]], ["fadd.d", "f6", ["f0", "f8"]],
              ["fsub.d", "f8", ["f10", "f14"]], ["fmul.d", "f6", ["f10", "f8"]], ["fadd.d", "f12", ["f6", "f4"]]];
function run(inOrder) {
  const W = {}, bus = new Set(), rows = []; let last = 0;   // W[reg] = cycle the newest value of reg is written
  for (const [op, d, src] of prog) {
    const ready = Math.max(0, ...src.map(r => W[r] || 0));  // cycle when the last source is written
    let issue = last + 1;                                   // one issue per cycle, in program order
    if (inOrder) issue = Math.max(issue, ready, W[d] || 0); // stall-on-use (RAW) and wait for older write (WAW)
    const start = Math.max(issue, ready) + 1, end = start + LAT[op] - 1;
    let w = end + 1; while (bus.has(w)) w++;                // one result bus: older instructions booked first
    bus.add(w); W[d] = w; last = issue; rows.push([op, d, issue, start, end, w]);
  }
  return rows;
}
const A = run(true), B = run(false);
console.log("instruction  dst  | in-order: issue exec  write | out-of-order: issue exec  write");
A.forEach((a, i) => { const b = B[i];
  console.log(`${a[0].padEnd(12)} ${a[1].padEnd(4)} |          ${String(a[2]).padEnd(5)} ${(a[3] + "-" + a[4]).padEnd(5)} ${String(a[5]).padEnd(5)} |              ${String(b[2]).padEnd(5)} ${(b[3] + "-" + b[4]).padEnd(5)} ${b[5]}`); });
const tA = Math.max(...A.map(a => a[5])), tB = Math.max(...B.map(b => b[5]));
console.log(`total cycles: in-order ${tA}, out-of-order ${tB}, speedup ${(tA / tB).toFixed(2)}x`);

instruction  dst  | in-order: issue exec  write | out-of-order: issue exec  write
fld          f2   |          1     2-3   4     |              1     2-3   4
fdiv.d       f0   |          4     5-16  17    |              2     5-16  17
fadd.d       f6   |          17    18-19 20    |              3     18-19 20
fsub.d       f8   |          18    19-20 21    |              4     5-6   7
fmul.d       f6   |          21    22-27 28    |              5     8-13  14
fadd.d       f12  |          28    29-30 31    |              6     15-16 18
total cycles: in-order 31, out-of-order 20, speedup 1.55x

Tomasulo-র সীমা

• CDB-এর bandwidth. প্রতি cycle-এ একটিই ফল ঘোষণা — উপরে I6 এক cycle হারাল। একাধিক CDB দিলে প্রতিটি RS-এর প্রতিটি operand-কে প্রতিটি bus-এর tag মেলাতে হয়: তার আর তুলনাকারী সার্কিট দুটোই গুণে গুণে বাড়ে।
• RS-এর সংখ্যা. অপেক্ষারত instruction RS দখল করে বসে থাকে। Add RS মাত্র একটি হলে কী হয়, তা অনুশীলন ৪-এ দেখবেন — ফল চমকে দেওয়ার মতো।
• Imprecise exception. ফল CDB থেকে সরাসরি register file-এ যায়, শেষ হওয়ার ক্রমে। উপরের উদাহরণে cycle ১৪-তে f6 = 20 লেখা হয়ে গেছে, অথচ I2 (ভাগ) তখনো শেষ হয়নি। এখন যদি ভাগে কোনো exception হতো, register file-এ পরের instruction-এর ফল আগেই বসে আছে — পর্ব ৩৮-এর precise exception-এর শর্ত ভঙ্গ। Model 91-এর floating point exception তাই imprecise ছিল বলে পরিচিত (imprecise exception).
• Branch পার হওয়া যায় না। একই কারণে branch-এর পরের instruction-কে চালিয়ে register-এ লিখতে দেওয়া বিপজ্জনক — অনুমান ভুল হলে লেখা ফেরানোর উপায় নেই। তাই মূল Tomasulo-তে branch-এর পেছনের instruction ফল লেখে না, যতক্ষণ না branch নিষ্পত্তি হয়।

শেষ দুটি সমস্যার একটিই সমাধান: ফল সরাসরি register-এ না পাঠিয়ে মাঝে একটি সারিতে রাখা, যেখান থেকে প্রোগ্রামের ক্রমে চূড়ান্ত হবে।

৫ · Hardware speculation আর reorder buffer — ক্রমের বাইরে চালানো, ক্রমে চূড়ান্ত করা

পর্ব ৩৮-এ একটি প্রতিশ্রুতি ছিল: শত শত instruction ক্রমের বাইরে চললেও exception precise রাখা যায়, reorder buffer (ROB) দিয়ে। ধারণাটি ১৯৮০-এর দশকের মাঝামাঝি James Smith আর Andrew Pleszkun-এর গবেষণায় এসেছিল, আর Tomasulo-র সাথে মিলিয়ে speculative execution-এর ভিত্তি হয়েছে। ROB একটি বৃত্তাকার সারি (circular queue): issue-এর সময় প্রতিটি instruction প্রোগ্রামের ক্রমে লেজে একটি entry পায়, আর শুধু মাথা থেকেই বের হয়।

ROB যোগ হলে Tomasulo-র ধাপ চারটি হয়, আর একটি বদল আসে: tag এখন RS-এর নাম নয়, ROB entry-এর নম্বর। Register status-এর Qi-তেও ROB-এর নম্বর থাকে।

1. Issue: একটি খালি RS আর একটি খালি ROB entry লাগে — যেকোনোটি না থাকলে issue থামে। Operand register file-এ, নয়তো ROB-এ তৈরি অবস্থায় থাকলে সেখান থেকে, নয়তো ROB-নম্বরের tag.
2. Execute: আগের মতোই, operand এলে।
3. Write result: ফল CDB-তে ROB-নম্বরসহ — অপেক্ষারত RS আর ROB entry-তে, register file-এ নয়। Entry-র Ready = হ্যাঁ।
4. Commit: শুধু মাথার entry, আর শুধু Ready হলে। Register-লেখা instruction হলে মান register file-এ বসে; store হলে এখন, এবং কেবল এখনই, মেমরিতে লেখা হয়; ঠিকভাবে অনুমান করা branch হলে শুধু সরানো হয়। আর মাথার branch-এর অনুমান ভুল প্রমাণিত হয়ে থাকলে, বা মাথার instruction-এর exception থাকলে: ROB-এর বাকি সব entry flush, RS আর register status খালি, আর fetch শুরু সঠিক ঠিকানা থেকে (exception-এর ক্ষেত্রে handler থেকে, mepc = ওই instruction-এর PC).

Worked example: cache miss, ভুল branch আর squash

নিচের ছয়টি instruction ধরুন, প্রতি cycle-এ একটি করে ROB-এ ঢোকে। fld-এ cache miss, তাই তার ফল আসে cycle ৯-এ। beq-কে “not taken” অনুমান করা হয়েছিল, তাই fetch সোজা নিচে চলেছে; কিন্তু cycle ৪-এ execute করে দেখা গেল branch আসলে taken — #৪ থেকে #৬ ভুল পথের, এদের শেষে squash (বাতিল) করতে হবে। প্রাথমিক মান: x1 = 0, x5 = 0, f2 = 2, f10 = 9, f12 = 4; মেমরিতে M[0] = 3, M[8] = 0. প্রতি cycle-এ সর্বোচ্চ একটি commit. হিসাব সরল রাখতে এখানে অংশ ৩-এর মতো আলাদা write-result cycle ধরা হয়নি: কোনো ফল যে cycle-এ তৈরি হয়, তার পরের cycle থেকেই নির্ভরশীল instruction তা ব্যবহার করে, আর entry মাথায় থাকলে commit হয়।

#  Instruction          Dest  Value  Ready
1  fld    f6, 0(x1)    f6    ?      no    ← মাথা (cache miss)
2  fmul.d f4, f6, f2    f4    ?      no
3  beq    x5, x0, L     —     ?      no    (অনুমান: not taken)

Register file: f2=2  f4=0  f6=0  f8=0   M[8]=0

#  Instruction          Dest  Value  Ready
1  fld    f6, 0(x1)    f6    ?      no    ← মাথা
2  fmul.d f4, f6, f2    f4    ?      no
3  beq    x5, x0, L     —     taken  yes   ✗ ভুল অনুমান
4  fadd.d f8, f4, f4    f8    ?      no    (ভুল পথ)
5  fsub.d f2, f10, f12  f2    ?      no    (ভুল পথ)
6  fsd    f2, 8(x1)     M[8]  ?      no    (ভুল পথ)

Register file: f2=2  f4=0  f6=0  f8=0   M[8]=0

#  Instruction          Dest  Value  Ready
1  fld    f6, 0(x1)    f6    ?      no    ← মাথা
2  fmul.d f4, f6, f2    f4    ?      no
3  beq    x5, x0, L     —     taken  yes   ✗
4  fadd.d f8, f4, f4    f8    ?      no
5  fsub.d f2, f10, f12  f2    5      yes
6  fsd    f2, 8(x1)     M[8]  5      yes

Register file: f2=2  f4=0  f6=0  f8=0   M[8]=0

#  Instruction          Dest  Value  Ready
1  fld    f6, 0(x1)    f6    3      ✓ commit হয়েছে
2  fmul.d f4, f6, f2    f4    ?      no    ← মাথা (execute ১০–১৫)
3  beq    x5, x0, L     —     taken  yes   ✗
4  fadd.d f8, f4, f4    f8    ?      no
5  fsub.d f2, f10, f12  f2    5      yes
6  fsd    f2, 8(x1)     M[8]  5      yes

Register file: f2=2  f4=0  f6=3  f8=0   M[8]=0

#  Instruction          Dest  Value  Ready
2  fmul.d f4, f6, f2    f4    6      ✓ commit হয়েছে
3  beq    x5, x0, L     —     taken  yes   ✗ ← মাথা
4  fadd.d f8, f4, f4    f8    ?      no
5  fsub.d f2, f10, f12  f2    5      yes
6  fsd    f2, 8(x1)     M[8]  5      yes

Register file: f2=2  f4=6  f6=3  f8=0   M[8]=0

#  Instruction          Dest  Value  Ready
3  beq    x5, x0, L     → ভুল অনুমান, মাথায় পৌঁছাল
4  fadd.d f8, f4, f4    ✗ squash
5  fsub.d f2, f10, f12  ✗ squash (মান 5 ফেলে দেওয়া)
6  fsd    f2, 8(x1)     ✗ squash (মেমরি ছোঁয়নি)

Register file: f2=2  f4=6  f6=3  f8=0   M[8]=0
cycle 18: fetch শুরু L থেকে

একই ঘটনা একটি ছোট simulator-এ। প্রতিটি entry-র “done” মানে কোন cycle-এর শেষে তার ফল তৈরি; commit হয় মাথা থেকে, প্রতি cycle-এ একটি, আর মাথা তৈরি না হলে সবাই অপেক্ষা করে।

// Reorder buffer: results finish out of order, commit strictly in order from the head
// Each entry: text, dest, value, cycle its result is ready ("done"); beq was predicted NOT taken but IS taken
const rob = [
  { t: "fld    f6, 0(x1)",   dest: "f6",  val: 3,   done: 9  },   // cache miss: slow
  { t: "fmul.d f4, f6, f2",  dest: "f4",  val: 6,   done: 15 },   // waits for f6
  { t: "beq    x5, x0, L",   dest: "-",   val: "taken", done: 4, mispredict: true },
  { t: "fadd.d f8, f4, f4",  dest: "f8",  val: null, done: 17 },  // wrong path, waits for f4
  { t: "fsub.d f2, f10, f12", dest: "f2", val: 5,   done: 7  },   // wrong path, finishes early
  { t: "fsd    f2, 8(x1)",   dest: "M[8]", val: 5,  done: 8  }];  // wrong path store: waits in ROB
const show = c => rob.forEach((e, i) => console.log(`  #${i + 1} ${e.t.padEnd(20)} dest=${e.dest.padEnd(5)}` +
  ` value=${String(c >= e.done ? e.val : "?").padEnd(6)} ready=${c >= e.done ? "yes" : "no"}`));
console.log("ROB at the end of cycle 8 (head = #1):"); show(8);
const RF = { f2: 2, f4: 0, f6: 0, f8: 0 }, MEM = { 8: 0 };
let head = 0;
for (let c = 1; head < rob.length; c++) {          // commit at most one entry per cycle
  const e = rob[head];
  if (e.done >= c) continue;                       // head not ready: everyone behind it waits
  if (e.mispredict) {
    console.log(`cycle ${c}: commit #${head + 1} ${e.t} -> MISPREDICTED: squash ` +
      rob.slice(head + 1).map((x, k) => `#${head + 2 + k}`).join(" ") + `, fetch from L in cycle ${c + 1}`);
    break;
  }
  if (e.dest.startsWith("M")) MEM[8] = e.val; else RF[e.dest] = e.val;
  console.log(`cycle ${c}: commit #${head + 1} ${e.t} -> ${e.dest} = ${e.val}`);
  head++;
}
console.log("architectural state:", JSON.stringify(RF), "MEM[8] =", MEM[8]);
console.log(`early recovery (resolve at cycle ${rob[2].done}, checkpointed map): squash in cycle ${rob[2].done + 1}, fetch L in cycle ${rob[2].done + 1}`);

ROB at the end of cycle 8 (head = #1):
  #1 fld    f6, 0(x1)     dest=f6    value=?      ready=no
  #2 fmul.d f4, f6, f2    dest=f4    value=?      ready=no
  #3 beq    x5, x0, L     dest=-     value=taken  ready=yes
  #4 fadd.d f8, f4, f4    dest=f8    value=?      ready=no
  #5 fsub.d f2, f10, f12  dest=f2    value=5      ready=yes
  #6 fsd    f2, 8(x1)     dest=M[8]  value=5      ready=yes
cycle 10: commit #1 fld    f6, 0(x1) -> f6 = 3
cycle 16: commit #2 fmul.d f4, f6, f2 -> f4 = 6
cycle 17: commit #3 beq    x5, x0, L -> MISPREDICTED: squash #4 #5 #6, fetch from L in cycle 18
architectural state: {"f2":2,"f4":6,"f6":3,"f8":0} MEM[8] = 0
early recovery (resolve at cycle 4, checkpointed map): squash in cycle 5, fetch L in cycle 5

কেন এটা এত শক্তিশালী

ROB-এর ফলে branch-এর ওপারেও নির্ভয়ে চালানো যায়। একটি সূক্ষ্ম কথা মনে রাখবেন: flush হওয়া instruction register বা মেমরিতে কিছু রাখে না, কিন্তু তারা cache-এ কোনো লাইন এনে ফেলতে পারে — “ছাপহীন” ঠিক নয়। Spectre আর Meltdown-এর মতো দুর্বলতার শিকড় এখানেই; ধারণা আর প্রতিরক্ষা পর্ব ৪১-এ (speculation-security.html).

৬ · Explicit register renaming — physical register file, map table আর free list

H&P-ধাঁচের ROB-এ মান থাকে ROB-এর ভেতরে, আর commit-এ register file-এ কপি হয়। একে বলা যায় “ROB-value style”. বেশিরভাগ আধুনিক বড় core আরেকটি পথ নেয়, যার একটি পরিচিত প্রথম দিকের উদাহরণ ১৯৯০-এর দশকের মাঝামাঝি MIPS R10000: একটি বড় physical register file (PRF), যেখানে নিশ্চিত আর অনুমাননির্ভর সব মানই থাকে; ROB শুধু হিসাব রাখে, মান নয়।

• Architectural register: প্রোগ্রামারের চোখের নাম — RISC-V-এ x1 … x31.
• Map table (RAT): প্রতিটি architectural register এখন কোন physical register-এ আছে।
• Free list: খালি physical register-এর তালিকা।

প্রতিটি instruction rename ধাপে তিনটি কাজ করে, এই ক্রমে: (১) source-এর নাম map table দিয়ে অনুবাদ; (২) destination-এর জন্য free list থেকে একটি নতুন physical register; (৩) map table-এ destination-এর ঘরে নতুনটি বসানো, আর পুরোনো mapping-টি ROB entry-তে লিখে রাখা। পুরোনো physical register কখন ফেরত যাবে? যখন এই instruction commit করে — কারণ তখন নিশ্চিত যে পুরোনো মানের আর কোনো পাঠক বাকি নেই (সব পাঠক প্রোগ্রামে আগে, তাই আগেই commit করেছে), আর কোনো recovery তাকে আর ফিরিয়ে আনবে না।

একটি ছোট RISC-V integer উদাহরণ নিন। শুরুতে x1 … x8 আছে p1 … p8-এ; free list = p9 … p14.

I1  mul  x5, x1, x2
I2  add  x6, x5, x3     # RAW: x5 (I1)
I3  sub  x5, x4, x7     # WAR: I2 পড়ে x5, I3 লেখে · WAW: I1 আর I3 দুজনেই x5
I4  add  x8, x5, x6     # RAW: x5 (I3), x6 (I2)
I5  addi x6, x8, 1      # WAR: I4 পড়ে x6 · WAW: I2 আর I5 দুজনেই x6

1mul  x5, x1, x2  →  mul  p9,  p1,  p22add  x6, x5, x3  →  add  p10, p9,  p33sub  x5, x4, x7  →  sub  p11, p4,  p74add  x8, x5, x6  →  add  p12, p11, p105addi x6, x8, 1   →  addi p13, p12, 1

Renaming-এর আগে আর পরে WAR/WAW গুনে দেখুন একটি ছোট program দিয়ে:

// Register renaming with a map table (RAT) + free list of physical registers
const prog = [["mul", "x5", "x1", "x2"], ["add", "x6", "x5", "x3"], ["sub", "x5", "x4", "x7"],
              ["add", "x8", "x5", "x6"], ["addi", "x6", "x8", "1"]];
const map = {}; for (let i = 1; i <= 8; i++) map["x" + i] = "p" + i;   // start: xi lives in pi
const free = ["p9", "p10", "p11", "p12", "p13", "p14"];
const isReg = s => /^[xp]\d+$/.test(s);
function hazards(code) {                    // count WAR and WAW pairs (i before j)
  let war = 0, waw = 0;
  code.forEach((a, i) => code.slice(i + 1).forEach(b => {
    if (b[1] === a[1]) waw++;                                   // both write the same register
    if (a.slice(2).includes(b[1])) war++;                       // a reads what b later writes
  }));
  return `${war} WAR, ${waw} WAW`;
}
const out = [];
prog.forEach(([op, d, s1, s2], i) => {
  const p1 = isReg(s1) ? map[s1] : s1, p2 = isReg(s2) ? map[s2] : s2;   // 1) read sources through the map
  const pd = free.shift(), old = map[d];                                 // 2) new physical reg for the dest
  map[d] = pd; out.push([op, pd, p1, p2]);                               // 3) update the map
  console.log(`I${i + 1}  ${`${op} ${d}, ${s1}, ${s2}`.padEnd(17)} ->  ${`${op} ${pd}, ${p1}, ${p2}`.padEnd(20)}` +
              `map ${d}->${pd}  (old ${old} freed when I${i + 1} commits)   free: [${free.join(" ")}]`);
});
console.log(`\nbefore renaming: ${hazards(prog)}   after renaming: ${hazards(out)}`);
console.log("final map:", Object.entries(map).map(([a, p]) => `${a}=${p}`).join(" "));

I1  mul x5, x1, x2    ->  mul p9, p1, p2      map x5->p9  (old p5 freed when I1 commits)   free: [p10 p11 p12 p13 p14]
I2  add x6, x5, x3    ->  add p10, p9, p3     map x6->p10  (old p6 freed when I2 commits)   free: [p11 p12 p13 p14]
I3  sub x5, x4, x7    ->  sub p11, p4, p7     map x5->p11  (old p9 freed when I3 commits)   free: [p12 p13 p14]
I4  add x8, x5, x6    ->  add p12, p11, p10   map x8->p12  (old p8 freed when I4 commits)   free: [p13 p14]
I5  addi x6, x8, 1    ->  addi p13, p12, 1    map x6->p13  (old p10 freed when I5 commits)   free: [p14]

before renaming: 2 WAR, 2 WAW   after renaming: 0 WAR, 0 WAW
final map: x1=p1 x2=p2 x3=p3 x4=p4 x5=p11 x6=p13 x7=p7 x8=p12

দুই ধাঁচের তুলনা, আর ভুল branch-এ map table ফেরানো

ভুল branch-এ PRF-ধাঁচে কী ফেরাতে হয়? Map table — কারণ ভুল পথের instruction-গুলো এতে নতুন mapping বসিয়ে গেছে। দুটি উপায়: (১) ROB-এর লেজ থেকে উল্টো দিকে হেঁটে প্রতিটি entry-র “পুরোনো mapping” আবার বসানো আর তার নতুন register free list-এ ফেরত দেওয়া — সময় লাগে entry-র সংখ্যা অনুযায়ী; (২) প্রতিটি branch-এর সময় map table-এর একটি কপি (checkpoint) রেখে দেওয়া, যাতে ভুল ধরা পড়ামাত্র এক ধাপে ফেরানো যায় — ROB-এর মাথার অপেক্ষা ছাড়াই।

৭ · মেমরির ক্রম — load/store queue আর memory disambiguation

Register-এর নাম decode-এর সময়ই জানা, তাই rename করা সহজ। মেমরির ঠিকানা কিন্তু জানা যায় অনেক পরে — sw x5, 0(x10)-এর ঠিকানা x10 হিসাব না হওয়া পর্যন্ত অজানা। তাই মেমরির dependence আলাদাভাবে সামলাতে হয়, একটি load/store queue (LSQ) দিয়ে, যেখানে চলমান load আর store প্রোগ্রামের ক্রমে থাকে। তিনটি নিয়ম:

1. Store মেমরিতে লেখে কেবল commit-এর পরে। তার আগে ঠিকানা আর ডেটা store queue-তে বসে থাকে — ভুল পথের store যেন কখনো মেমরি না ছোঁয় (অংশ ৫-এর #৬)।
2. Load আগের store-গুলোর সাথে ঠিকানা মেলায়। কোনো আগের store একই ঠিকানায় থাকলে আর তার ডেটা তৈরি থাকলে, load cache-এ না গিয়ে সরাসরি সেই ডেটা নেয় — store-to-load forwarding. না মিললে cache থেকে পড়ে।
3. আগের কোনো store-এর ঠিকানা অজানা হলে? এটাই memory disambiguation-এর প্রশ্ন। সাবধানী পথ: অপেক্ষা। সাহসী পথ: ধরে নেওয়া যে ঠিকানা মিলবে না, আর load আগে চালিয়ে দেওয়া (speculative load). পরে store-এর ঠিকানা জানা গেলে hardware পরীক্ষা করে; মিলে গেলে load আর তার পরের সব instruction squash করে আবার চালায় — ভুল branch-এর মতোই।

একটি ছোট উদাহরণ, প্রোগ্রামের ক্রমে (x10 = 0x1000, x5 = 42):

বাস্তবে বেশিরভাগ load আগের অজানা store-এর ওপর নির্ভর করে না, তাই সাহসী পথ সাধারণত লাভজনক। কিন্তু কিছু নির্দিষ্ট load বারবার ধরা খায় (যেমন একটি লুপে প্রতিবার আগের ঘুরের লেখা পড়া)। এর জন্য memory dependence prediction: hardware মনে রাখে কোন load আগে কোন store-এর কাছে ধরা খেয়েছিল, আর শুধু সেগুলোকে অপেক্ষা করায়। ১৯৯০-এর দশকের শেষ দিকের “store sets” গবেষণা এই ধারণার একটি পরিচিত উদাহরণ; Intel ২০০৬ সালের দিকে Core microarchitecture-এ load-কে আগের অজানা store পেরিয়ে চালানোর ব্যবস্থাকে “memory disambiguation” নামেই প্রচার করেছিল বলে জানা যায়।

৮ · আধুনিক out-of-order core — ধাপ, আকার আর দাম

সব যন্ত্রাংশ এক জায়গায় বসালে আজকের একটি বড় core-এর pipeline মোটামুটি এমন দেখায় (নাম আর সীমারেখা নির্মাতাভেদে আলাদা):

একটি বিভ্রান্তি আগেই মিটিয়ে রাখুন: “issue” আর “dispatch” শব্দ দুটি বইভেদে উল্টো অর্থে ব্যবহৃত হয়। Hennessy–Patterson-এ Tomasulo-র “issue” হলো RS-এ বসানো; অনেক শিল্প-নথিতে সেটাকেই “dispatch” বলা হয়, আর “issue” মানে execution unit-এ পাঠানো। উত্তর লেখার সময় নিজের সংজ্ঞা লিখে দেবেন।

আকার কত বড়? আজকের বড় desktop, server আর ফোনের “performance” core-এ ROB আর issue queue মিলিয়ে একসাথে শত শত micro-op উড়ন্ত থাকতে পারে। একটি নির্দিষ্ট উদাহরণ দিলে: Intel ২০২১ সালে তার Golden Cove core-এর ROB ৫১২ entry-র বলে জানিয়েছিল। Physical register-ও কয়েকশো, architectural register-এর কয়েক গুণ। এর অর্থ — একটি cache miss হওয়া load-এর পেছনে core কয়েকশো instruction এগিয়ে কাজ খুঁজতে পারে, পরের cache miss-গুলোও আগেভাগে শুরু করে দিতে পারে। একে বলা হয় memory-level parallelism, আর বড় window-এর লাভের বড় অংশ আসে এখান থেকেই।

দাম — power, area আর জটিলতা

এই সমান্তরালতা বিনামূল্যে আসে না। প্রতি cycle-এ প্রতিটি ঘোষিত tag-কে issue queue-র প্রতিটি অপেক্ষারত source-এর সাথে মেলাতে হয়। উদাহরণ হিসেবে, ১০০ entry-র queue, প্রতি entry-তে ২টি source আর প্রতি cycle-এ ৪টি ফল হলে ১০০ × ২ × ৪ = ৮০০টি তুলনা — প্রতি cycle-এ। Wakeup আর select-কে এক cycle-এ শেষ করতে হয়, নইলে পরস্পর-নির্ভর দুটি যোগ পরপর চলতে পারে না; তাই এই সার্কিট clock-এর গতিও সীমিত করে। Rename-এ প্রতি cycle-এ কয়েকটি instruction-কে একে অপরের সাথে মেলাতে হয় (একই cycle-এ পরেরটি আগেরটির ফল পড়লে)। বড় PRF-এ অনেক read/write port, ROB আর LSQ-এর জন্য বিপুল হিসাব, ভুল অনুমানে ফেলে দেওয়া কাজের শক্তি — সব মিলিয়ে একটি বড় out-of-order core একটি সরল in-order core-এর চেয়ে কয়েক গুণ বেশি জায়গা আর শক্তি নিতে পারে, যেখানে গতি বাড়ে তার চেয়ে কম হারে। পর্ব ২-এর power wall-এর যুগে এই হিসাবটি গুরুত্বপূর্ণ।

তাই সবাই out-of-order নয়। ছোট microcontroller (ARM Cortex-M, অনেক RISC-V embedded core) প্রায় সবসময় in-order: সেখানে নির্ভরযোগ্য সময় আর অল্প শক্তিই মুখ্য। ফোনের chip-এ প্রায়ই বড় out-of-order core-এর পাশে ছোট “efficiency” core থাকে; ARM-এর Cortex-A53 আর A55-এর মতো বহুল ব্যবহৃত ছোট core in-order বলে পরিচিত (সব নির্মাতার efficiency core অবশ্য in-order নয়)। Intel-এর প্রথম Atom (২০০৮ সালের দিকে) in-order ছিল, পরের প্রজন্মে out-of-order-এ সরে যায় বলে জানা যায়।

৯ · AI-এর যুগে — Tomasulo-র টেবিলে AI, আর যাচাইয়ের অভ্যাস

Tomasulo, ROB আর renaming নিয়ে AI-এর ব্যাখ্যা সাধারণত মসৃণ, কিন্তু cycle-ধরা টেবিলে আর ঐতিহাসিক খুঁটিনাটিতে ভুল প্রায়ই চোখে পড়ে:

AI-এর দেওয়া Tomasulo বা ROB-এর উত্তর হাতে পেলে — চেকলিস্ট

• Cycle গোনার নিয়ম (issue থেকে execute, CDB থেকে execute, write-এর সময়) প্রশ্নের সাথে মিলিয়েছি
• Write কলামে CDB-এর সংখ্যার চেয়ে বেশি একই cycle নেই, আর প্রতিযোগিতায় পুরোনোটি জিতেছে
• WAW-এর ক্ষেত্রে register-এ শেষ পর্যন্ত প্রোগ্রামের শেষ লেখকের মান আছে কি না দেখেছি
• Rename-এ প্রতিটি destination আলাদা physical register পেয়েছে, আর পুরোনোটি free হচ্ছে commit-এ
• ROB-এ commit কঠোরভাবে মাথা থেকে, আর squash-এ মাথার পেছনের সব entry বাদ গেছে
• চূড়ান্ত register-এর মান ক্রমে (in-order) হাতে চালিয়ে বা simulator-এ মিলিয়েছি