Register Renaming ও Reorder Buffer — মিথ্যা নির্ভরতা ভাঙা

আগে এটা বুঝি

আগের লেসনে আমরা দেখেছি out-of-order execution কীভাবে independent instruction-গুলোকে program order ভেঙে চালায় — যে instruction-এর operand তৈরি, সে-ই আগে যায়। কিন্তু একটা প্রশ্ন ইচ্ছাকৃতভাবে খোলা রেখে দিয়েছিলাম।

দুইটা instruction দেখুন:

I1:  R1 = R2 + R3
I2:  R1 = R4 + R5

এই দুইটার মধ্যে কি কোনো নির্ভরতা আছে? সরল চোখে মনে হতে পারে হ্যাঁ — দুটোই R1 ছুঁচ্ছে। কিন্তু থামুন আর ভাবুন: I2-এর ফলাফল কি I1-এর ফলাফলের উপর নির্ভর করে? না। I2 সম্পূর্ণভাবে R4 আর R5 থেকে হিসাব হয় — R2, R3, বা I1-এর সাথে তার কোনো সম্পর্কই নেই।

তাহলে সমস্যাটা কোথায়? সমস্যা হলো নামের সংঘর্ষ। দুটো instruction দুর্ঘটনাক্রমে একই architectural register-এর নাম আবার ব্যবহার করছে। যদি hardware I2-কে I1-এর আগে চালিয়ে ফেলে, আর তারপর কেউ I1-এর ফলাফল পড়তে চায় (assuming আরেকটা instruction পরে R1 পড়ে I1-এর মান আশা করছিল) — তাহলে ভুল মান পাবে।

এটাকে বলে WAW hazard (Write-After-Write) — I1 আর I2 দুজনেই R1-এ লেখে, তাই লেখার ক্রম উল্টে গেলে shorobhabotoভাবে I1-এর লেখাটাই শেষে “জেতা” উচিত (যদি I2 আসলে program order-এ পরে থাকে, I2-এর মানটাই architecturally শেষ মান হওয়া উচিত) — কিন্তু hardware যদি এলোমেলো ক্রমে চালায়, ভুল মান শেষ পর্যন্ত R1-এ থেকে যেতে পারে।

আরেকটা রূপ দেখুন:

I1:  R3 = R1 + R2
I2:  R1 = R4 + R5

এখানে I1 R1 পড়ে, আর I2 R1-এ লেখে। যদি I2 আগে চলে (register renaming ছাড়া naive out-of-order hardware-এ), তাহলে I1 যখন পরে R1 পড়তে যাবে, সে পাবে I2-এর নতুন মান — অথচ program order অনুযায়ী তার পুরনো মানটা পড়া উচিত ছিল। এটা WAR hazard (Write-After-Read)।

দুটোই — WAR আর WAW — লেসন ১০-এ hazard-এর যে তৃতীয় পরিবার নিয়ে কথা হয়েছিল তারই সদস্য, কিন্তু pipeline-এর গল্পে এরা গৌণ ছিল কারণ in-order pipeline-এ read সবসময় write-এর আগে ঘটে একই pipeline stage ক্রমে। Out-of-order-এ সেই গ্যারান্টি নেই — তাই এরা হঠাৎ গুরুত্বপূর্ণ হয়ে ওঠে।

মূল পার্থক্যটা মনে রাখুন: RAW (Read-After-Write) একটা সত্যিকারের dependency — আসল data value একটা instruction থেকে আরেকটায় প্রবাহিত হয়। WAR আর WAW কোনো value প্রবাহিত করে না — এরা শুধু নাম পুনর্ব্যবহারের কাকতালীয় ফল। এই লেসন দেখাবে hardware কীভাবে এই নকল বাধাগুলো সম্পূর্ণ মুছে ফেলে, আর তারপর কীভাবে সেই এলোমেলো execution থেকে একটা পরিষ্কার, program-order commit পুনর্গঠন করে।

মূল ধারণা

তিন ধরনের dependency — একটা আসল, দুইটা নকল

Out-of-order execution বোঝার জন্য এই তিনটা আলাদা করা অপরিহার্য।

নাম	পূর্ণ রূপ	উদাহরণ	আসল না নকল?
RAW	Read-After-Write	`I1: R1=...` তারপর `I2: ...=R1+...`	আসল — data সত্যিই প্রবাহিত হয়
WAR	Write-After-Read	`I1: ...=R1+...` তারপর `I2: R1=...`	নকল — শুধু নাম সংঘর্ষ
WAW	Write-After-Write	`I1: R1=...` তারপর `I2: R1=...`	নকল — শুধু নাম সংঘর্ষ

RAW-কে বলা হয় true dependency কারণ এটা algorithm-এর নিজস্ব ধর্ম — I2-এর হিসাব শুরুই করা যায় না I1-এর ফলাফল ছাড়া। এটা কখনো ভাঙা যায় না, শুধু লুকানো যায় (speculation দিয়ে, যা আমরা branch prediction-এর লেসনে দেখেছি)।

WAR আর WAW-কে বলা হয় false dependency বা name dependency — কারণ এরা algorithm সম্পর্কে কিছুই বলে না। Compiler বা programmer যদি I2-এর জন্য R1-এর বদলে একটা সম্পূর্ণ ভিন্ন, অব্যবহৃত register বেছে নিতেন, dependency-টাই অদৃশ্য হয়ে যেত। সমস্যাটা algorithm-এ নেই — সমস্যাটা এই যে ISA মাত্র একটা নির্দিষ্ট সংখ্যক নাম দেয় (x86-64-এ ১৬টা general-purpose register, RISC-V-এ ৩২টা), আর compiler বাধ্য হয়ে সেগুলো বারবার পুনর্ব্যবহার করে।

কেন কম্পাইলার এমনিতেই register পুনর্ব্যবহার করে

একটা function-এ হাজারটা variable থাকতে পারে, কিন্তু ISA দেয় মাত্র ১৬-৩২টা register। Compiler-এর register allocator (graph coloring বা linear scan অ্যালগরিদম দিয়ে) বাধ্য হয়ে একই register বারবার বিভিন্ন, সম্পূর্ণ অসম্পর্কিত variable-এর জন্য পুনর্ব্যবহার করে — যেই একটা variable-এর জীবনকাল শেষ, সেই register free ধরে নেওয়া হয় পরের ব্যবহারের জন্য।

এই recycling-ই compiled code-কে WAR/WAW hazard-এ ঠাসা করে দেয় — এটা কোনো খারাপ কোডিং না, এটা সীমিত register-সংখ্যার স্বাভাবিক ফলাফল।

সমাধান: architectural নাম থেকে physical storage আলাদা করা

মূল অন্তর্দৃষ্টিটা সহজ, কিন্তু গভীর। ISA যে ১৬ বা ৩২টা register নাম প্রকাশ করে (architectural register, যেমন x86-64-এর RAX, RBX, RISC-V-এর x0-x31), সেগুলো শুধু একটা নাম। এর পেছনে আসল সিলিকনে থাকতে পারে আরও অনেক বেশি storage location — physical register।

আধুনিক CPU-তে সংখ্যাটা বিশাল পার্থক্য দেখায়:

CPU	Architectural GP register	Physical integer register (আনুমানিক)
x86-64 (ISA)	১৬	—
Intel Skylake	১৬ visible	~১৮০
Intel Golden Cove (12th gen)	১৬ visible	~২৮০
Apple M1/M2	৩১ visible (ARM64)	~৩৫০+
AMD Zen 4	১৬ visible	~২২৪

প্রতিটা CPU-ই বাইরে ঠিক ISA যতগুলো register প্রতিশ্রুতি দেয় ততগুলোই দেখায় — একটা প্রোগ্রাম কখনো এই লুকানো অতিরিক্ত register-গুলো সরাসরি address করতে পারে না। কিন্তু ভেতরে, hardware প্রতিটা write-কে একটা তাজা, unused physical register-এ পাঠায়।

Register renaming কীভাবে কাজ করে

দুটো কাঠামো লাগে।

১. Rename table (Register Alias Table, RAT) — একটা mapping: প্রতিটা architectural register এই মুহূর্তে কোন physical register-এ “বাস করছে” তার হিসাব। প্রতিবার একটা instruction কোনো architectural register-এ লেখে, RAT আপডেট হয় — সেই architectural নামটা এখন একটা নতুন physical register নির্দেশ করে।

২. Free list — এখনো ব্যবহার না-হওয়া physical register-এর তালিকা। একটা instruction dispatch হওয়ার সময় তার destination-এর জন্য free list থেকে একটা physical register বরাদ্দ হয়।

আমাদের শুরুর উদাহরণে ফিরি:

I1:  R1 = R2 + R3
I2:  R1 = R4 + R5

Rename করার পর (ধরি physical register p1, p2, ... p10 আগে থেকে architectural R1..R5-কে ধরে আছে, আর p33, p34 free):

I1:  p33 = p1 + p2      # R1 → p33 (নতুন)
I2:  p34 = p4 + p5      # R1 → p34 (আরেকটা নতুন)

লক্ষ্য করুন: I1 আর I2 এখন সম্পূর্ণ আলাদা physical destination লেখে। তাদের মধ্যে আর কোনো সংঘর্ষ নেই — hardware এখন তাদের যেকোনো ক্রমে, এমনকি একসাথে (দুইটা ভিন্ন execution unit-এ) চালাতে পারে। WAW hazard সম্পূর্ণ অদৃশ্য।

আর WAR-এর উদাহরণ:

I1:  R3 = R1 + R2
I2:  R1 = R4 + R5

Rename-এর পর:

I1:  p35 = p33 + p2     # R1 পড়ে — pipeline-এ I1 dispatch হওয়ার সময়
                         # যা RAT-এ ছিল, সেই physical register (p33) থেকে পড়ে
I2:  p36 = p4 + p5       # R1 → p36 (নতুন)

I1 তার operand হিসেবে p33 পড়ে — যেটাই RAT-এ R1-এর জন্য ছিল যখন I1 renamed হয়েছিল। I2 সম্পূর্ণ ভিন্ন p36-এ লেখে। I1 এখন যত দেরিতেই চলুক না কেন, তার operand p33 কখনো I2 touch করে না — কারণ I2 কখনো p33-তে লেখেই না। WAR hazard-ও অদৃশ্য।

এখন RAW-এর সাথে তুলনা করুন — যেটা সত্যিকারের dependency, তাই renaming এটা ভাঙতে পারে না, ভাঙা উচিতও না:

I1:  R1 = R2 + R3        →   p33 = p1 + p2
I2:  R5 = R1 * 2          →   p34 = p33 * 2

I2 renaming-এর সময় দেখে R1 এখন p33, তাই সে সঠিকভাবেই p33-কে তার operand হিসেবে নেয়। I2 p33 লেখা শেষ না হওয়া পর্যন্ত অপেক্ষা করতেই হবে — এটাই আসল নির্ভরতা, renaming এটা শুধু সঠিকভাবে ট্র্যাক করে, মুছে দেয় না।

                    RAT (architectural → physical)
সময়     R1   R2   R3   R4   R5
t0       p1   p2   p3   p4   p5    ← শুরুর অবস্থা

I1: R1=R2+R3
t1       p33  p2   p3   p4   p5    ← R1 এখন p33 (নতুন লেখা)

I2: R1=R4+R5
t2       p34  p2   p3   p4   p5    ← R1 এখন p34 (আরেকটা নতুন লেখা,
                                      p33 আর কেউ নির্দেশ করে না)

I3: R5=R1*2   (এই R1 মানে p34, সাম্প্রতিকতম)
t3       p34  p2   p3   p4   p35   ← R5 এখন p35, operand ছিল p34

Rename table-এর মধ্য দিয়ে তিনটা instruction-এর মানচিত্র বদল।

Physical register কবে free হয়

p33-কে যখন RAT আর নির্দেশ করে না (উপরের t2-তে), তার মানে এই না যে সেটা সাথে সাথে পুনর্ব্যবহারযোগ্য। যদি এখনো কোনো in-flight instruction p33 পড়ার অপেক্ষায় থাকে (renaming-এর সময় তারা p33-কে operand হিসেবে capture করেছিল), সেটা মুক্ত করা যাবে না।

Physical register free হয় সাধারণত যখন সেটাকে প্রতিস্থাপনকারী instruction commit করে (যেমন I2 commit হলে p33 মুক্ত হতে পারে, কারণ তখন নিশ্চিত হয়ে যায় কোনো architecturally-visible instruction আর p33-কে চাইবে না)। এই commit-নির্ভর মুক্তিটাই পরের ভাগের বিষয় — reorder buffer।

এখন সমস্যা: এলোমেলো execution-কে সাজানো commit-এ ফেরানো

Register renaming false dependency ভাঙল, তাই এখন instruction-গুলো সত্যিই যেকোনো ক্রমে চলতে পারে — যখনই তাদের true dependency মেটে। কিন্তু একটা নতুন সমস্যা তৈরি হলো।

Program এখনও আশা করে তার architectural state — যা প্রোগ্রামার বা debugger দেখতে পায় — ঠিক program order অনুযায়ী আপডেট হবে। যদি I5 I3-এর আগে চলে আর সরাসরি architectural register আপডেট করে ফেলে, আর তারপর I3 কোনো কারণে বাতিল হয়ে যায় (একটা mispredicted branch-এর কারণে, বা একটা exception-এর কারণে), তাহলে I5-এর সেই আগাম আপডেট আর ফিরিয়ে নেওয়ার কোনো উপায় নেই — সিস্টেম একটা অসংগত অবস্থায় আটকে যায়।

সমাধান: reorder buffer (ROB)।

ROB-এর মূল ধারণা

ROB একটা circular buffer — প্রতিটা instruction, dispatch হওয়ার মুহূর্তে (তার execution শুরুরও আগে), ROB-এর লেজে (tail) একটা entry পায়, program order অনুযায়ী। এই entry-টা তার জন্য একটা “জায়গা সংরক্ষণ” — instruction-এর ফলাফল, তার destination register, আর একটা “সম্পন্ন হয়েছে কি না” flag রাখার জায়গা।

Execution unit-গুলো instruction-গুলো যেকোনো ক্রমে চালায় — operand ready হওয়া মাত্র। ফলাফল ফিরে এসে সরাসরি architectural state-এ যায় না — সেটা প্রথমে তার নিজের ROB entry-তে লেখা হয়, আর entry-টাকে “সম্পন্ন” (complete) চিহ্নিত করা হয়। এই মুহূর্তে মানটা speculative — এটা বিদ্যমান, কিন্তু এখনো “সত্য” (committed, architecturally visible) না।

Commit — ROB-এর মাথা থেকে, কঠোরভাবে সাজানো ক্রমে

প্রতি cycle-এ (বা একাধিক, superscalar CPU-তে), ROB-এর মাথা (head) — অর্থাৎ প্রোগ্রাম order-এ সবচেয়ে পুরনো, এখনো commit না-হওয়া instruction — পরীক্ষা করা হয়। যদি সেটা “সম্পন্ন” চিহ্নিত থাকে (তার execution শেষ), তাহলে সেটা commit হয়: তার ফলাফল সরকারিভাবে architectural state-এ লেখা হয় (rename table-এর সেই architectural register-এর “committed” mapping আপডেট হয়), আর সেই entry ROB থেকে সরে যায়।

গুরুত্বপূর্ণ কথা: মাথার instruction-টা “সম্পন্ন” না হলে, কেউ commit করতে পারে না — এমনকি যদি ROB-এর মাঝখানে বা লেজে অনেক instruction আগেই “সম্পন্ন” হয়ে বসে থাকে। commit কঠোরভাবে in-order, যদিও execution ছিল out-of-order।

ROB (মাথা থেকে লেজ, program order):

  ┌─────┬──────────┬──────────┐
  │  I1  │ সম্পন্ন   │ commit-এর অপেক্ষায় (মাথা) │
  ├─────┼──────────┼──────────┤
  │  I2  │ এখনো না  │ (একটা ধীর memory op-এ আটকে) │
  ├─────┼──────────┼──────────┤
  │  I3  │ সম্পন্ন   │ execution শেষ, কিন্তু commit-এর জন্য অপেক্ষা │
  ├─────┼──────────┼──────────┤
  │  I4  │ সম্পন্ন   │ execution শেষ, কিন্তু commit-এর জন্য অপেক্ষা │
  └─────┴──────────┴──────────┘

I3, I4 আগেই execute হয়ে গেছে — কিন্তু I2 এখনো "সম্পন্ন" না,
তাই I3, I4 কেউই commit করতে পারবে না যতক্ষণ না I2 শেষ হয় আর
মাথায় পৌঁছায়। commit ক্রম: I1 → I2 → I3 → I4, ঠিক প্রোগ্রামের
লেখা ক্রমে — এমনকি যদিও ভেতরে I3, I4 আগে চলে গিয়েছিল।

Execution এলোমেলো, কিন্তু commit সবসময় সারিবদ্ধ।

কেন এটাই precise exception সম্ভব করে

এই in-order commit নিয়মটাই আসলে পুরো ব্যবস্থার আসল কারণ। যদি কোনো instruction-এ exception ঘটে (পরের লেসনে বিস্তারিত — divide by zero, page fault, illegal instruction), CPU-কে জানতে হবে ঠিক কোন পর্যন্ত architectural state বৈধ।

ROB থাকলে এটা তুচ্ছ: exception-যুক্ত instruction ROB-এর মাথায় পৌঁছালে, CPU ঘোষণা করতে পারে — “এই instruction পর্যন্ত সব commit হয়েছে, এর পর থেকে কিছুই হয়নি (এমনকি যেগুলো ভেতরে আগেই speculatively execute হয়ে গিয়েছিল, তাদের ফলাফল ROB থেকে বাতিল/flush করে দেওয়া হয়, কখনো architectural state-এ পৌঁছায়নি)।” এটাকে বলে precise exception — exception ঠিক এমনভাবে দেখা যায় যেন CPU সরল, in-order ক্রমেই instruction চালিয়েছিল, ঠিক exception-এর instruction পর্যন্ত।

ROB ছাড়া (বা তার সমতুল্য কোনো mechanism ছাড়া) এটা অসম্ভব — কিছু “পরের” instruction হয়তো আগেই architectural state আপডেট করে ফেলেছে, আর সেই আপডেট ফিরিয়ে নেওয়ার কোনো clean উপায় থাকবে না। এই যোগসূত্রটা পরের লেসনে interrupt আর exception নিয়ে আলোচনার সময় সরাসরি কাজে লাগবে।

ভেতরে কী ঘটছে

Reservation station, issue queue, আর ROB-এর মধ্যে সম্পর্ক

আগের লেসনে superscalar আর out-of-order execution-এর ধারণাগত পরিচয় হয়েছিল। এখন পুরো pipeline-টা কীভাবে একসাথে বসে সেটা দেখা যাক।

একটা instruction-এর জীবনচক্র — dispatch থেকে commit

FetchInstruction memory থেকে আনা হয়, program order অনুযায়ী
DecodeOperand, opcode চেনা হয়
RenameSource operand-এর জন্য RAT lookup, destination-এর জন্য free list থেকে নতুন physical register
Dispatch to ROB + issue queueROB-এ program-order entry তৈরি হয়; issue queue-তে operand ready হওয়ার অপেক্ষা
Issue (out-of-order)Operand ready মাত্র, execution unit-এ পাঠানো — ক্রম এলোমেলো
ExecuteALU/FPU/load-store unit-এ প্রকৃত হিসাব
Write-backফলাফল physical register file-এ লেখা হয়, ROB entry "সম্পন্ন" চিহ্নিত হয়
Commit (in-order)ROB-এর মাথা থেকে, প্রোগ্রাম order অনুযায়ী architectural state আপডেট

লক্ষ্য করুন rename ধাপটা কতটা কেন্দ্রীয় — এটাই সেই মুহূর্ত যেখানে false dependency ভাঙা হয়, আর true dependency সঠিকভাবে capture করা হয় (কোন physical register operand হবে সেটা এখানেই ঠিক হয়)।

Speculative রাষ্ট্র বনাম committed রাষ্ট্র

এই ব্যবস্থায় CPU-র কার্যত দুই স্তরের সত্য থাকে:

Speculative/physical state — সব physical register-এর বর্তমান মান, কিছু হয়তো এখনো commit হয়নি, কিছু হয়তো ভুল branch prediction-এর কারণে বাতিল হয়ে যাবে
Architectural/committed state — শুধু সেই মান যেগুলো ROB থেকে commit হয়ে গেছে, program order-এ, নিশ্চিতভাবে বৈধ

একটা branch misprediction ধরা পড়লে (branch prediction লেসনের সেই flush), CPU যা করে তা এখন পরিষ্কার বোঝা যায়: mispredicted branch-এর পরের সব ROB entry বাতিল হয়ে যায় (তারা কখনো commit হয় না), rename table পুনরুদ্ধার হয় সর্বশেষ known-good committed mapping-এ, আর fetch পুনরায় শুরু হয় সঠিক পথ থেকে। speculative execution-এর পুরো ফলাফল — সব ভুল পথে চলা instruction — এভাবে কার্যত কখনো ঘটেইনি বলে মুছে যায়, architectural state-এ কোনো দাগ না রেখে।

Tomasulo থেকে আধুনিক ROB পর্যন্ত

১৯৬৭ সালে Robert Tomasulo IBM System/360 Model 91-এর জন্য একটা অ্যালগরিদম ডিজাইন করেন — floating-point unit-কে দ্রুত করতে। তার reservation station ধারণাটাই আসলে register renaming-এর প্রথম বাস্তবায়ন, যদিও তিনি “renaming” শব্দটা ব্যবহার করেননি। কিন্তু Model 91-এ precise exception ছিল না — exception ঘটলে প্রোগ্রামের অবস্থা নির্ভরযোগ্যভাবে জানা যেত না, যা সেই সময় গ্রহণযোগ্য ছিল কারণ floating-point exception সচরাচর প্রোগ্রাম বন্ধই করে দিত।

১৯৮৫ সালে James Smith আর Andrew Pleszkun দেখান কীভাবে একটা reorder buffer যোগ করে precise exception পাওয়া যায় — Tomasulo-র speed রেখে দিয়েই। এই ধারণাটাই ১৯৯৫ সালে Intel-এর Pentium Pro (P6 microarchitecture)-তে প্রথম mainstream x86 chip হিসেবে বাস্তবায়িত হয় — আর তখন থেকে প্রতিটা high-performance CPU-ই (x86, ARM, POWER, RISC-V-এর OoO implementation) এই মৌলিক প্যাটার্ন অনুসরণ করে: rename দিয়ে false dependency ভাঙা, ROB দিয়ে in-order commit নিশ্চিত করা।

ROB আকার কেন গুরুত্বপূর্ণ

ROB-এর আকার সরাসরি নির্ধারণ করে CPU কত দূর “সামনে তাকিয়ে” কাজ খুঁজতে পারে — এটাই কার্যকর out-of-order window। একটা বড় ROB মানে CPU একটা ধীর instruction (যেমন একটা cache miss-এ আটকে থাকা load)-কে মাথায় রেখে তার পিছনের আরও বহু instruction আগেই execute করে ফেলতে পারে, যতক্ষণ তারা independent।

CPU	ROB আকার (আনুমানিক entry সংখ্যা)
Intel Pentium Pro (1995)	৪০
Intel Skylake (2015)	২২৪
Intel Golden Cove (2021)	৫১২
AMD Zen 4 (2022)	৩২০
Apple M1 (2020)	৬৩০

Apple M1-এর অস্বাভাবিক বড় ROB তখন ব্যাপক আলোচিত হয়েছিল — এটা memory latency লুকাতে অনেক বেশি সক্ষম, যদিও বড় ROB নিজেই বেশি power আর silicon area খরচ করে (প্রতিটা entry-র জন্য tracking hardware লাগে, আর মাথা থেকে commit খোঁজার logic জটিল হয়ে ওঠে)।

উদাহরণ

সম্পূর্ণ trace — rename থেকে commit পর্যন্ত

একটা বাস্তবঘেঁষা instruction sequence নিয়ে সম্পূর্ণ প্রক্রিয়া দেখি।

I1:  R1 = R2 + R3      # true add
I2:  R4 = R1 * 2        # R1-এর উপর নির্ভরশীল (RAW)
I3:  R1 = R5 - R6       # R1 আবার লেখা (WAW সাথে I1)
I4:  R7 = R1 + R4       # এই R1 মানে I3-এর নতুন মান (RAW সাথে I3)

ধাপ ১ — Rename। ধরি শুরুতে RAT: R1→p1, R2→p2, ..., R7→p7, আর free list-এ p10, p11, p12, p13 আছে।

Instr	নতুন mapping	Physical form
I1	R1 → p10	`p10 = p2 + p3`
I2	R4 → p11	`p11 = p10 * 2`
I3	R1 → p12	`p12 = p5 - p6`
I4	R7 → p13	`p13 = p12 + p11`

লক্ষ্য করুন I2 তার operand হিসেবে p10 নিল (I1-এর নতুন mapping, RAT lookup-এর মুহূর্তে যা ছিল) — এটা RAW, সঠিকভাবেই সংরক্ষিত। I3 R1-কে আবার নতুন p12-এ renamed করল — এখন I1 আর I3 সম্পূর্ণ আলাদা physical register লেখে, WAW hazard অদৃশ্য। I4 p12 (I3-এর নতুন R1) পড়ে, p10 না — কারণ যখন I4 renamed হলো, RAT-এ R1 ততক্ষণে p12 নির্দেশ করছিল।

ধাপ ২ — ROB entry তৈরি (program order অনুযায়ী)।

ROB মাথা →  [I1: dest=p10, সম্পন্ন=না]
             [I2: dest=p11, সম্পন্ন=না]
             [I3: dest=p12, সম্পন্ন=না]
ROB লেজ →   [I4: dest=p13, সম্পন্ন=না]

ধাপ ৩ — Out-of-order execution। ধরি I3 কোনো dependency নেই (শুধু p5, p6 লাগে, যা আগে থেকেই ready), তাই I3 সবচেয়ে আগে execute হয়। I1-ও independent, তাই একসাথে বা কাছাকাছি সময়ে চলে। I2 I1-এর জন্য অপেক্ষা করে, I4 I3 আর I2 দুটোর জন্যই অপেক্ষা করে।

সম্ভাব্য execution ক্রম: I3, I1, I2, I4 — program order (I1,I2,I3,I4) থেকে সম্পূর্ণ ভিন্ন।

ধাপ ৪ — Write-back, ROB “সম্পন্ন” চিহ্নিত হয় (execution শেষ হওয়া মাত্র, ক্রম নির্বিশেষে):

t1: I3 সম্পন্ন   →  ROB: [I1:না][I2:না][I3:✓][I4:না]
t2: I1 সম্পন্ন   →  ROB: [I1:✓][I2:না][I3:✓][I4:না]
t3: I2 সম্পন্ন   →  ROB: [I1:✓][I2:✓][I3:✓][I4:না]
t4: I4 সম্পন্ন   →  ROB: [I1:✓][I2:✓][I3:✓][I4:✓]

লক্ষ্য করুন t1-এই I3 সম্পন্ন হয়ে গেছে, কিন্তু এটা তখনই commit করতে পারে না — কারণ এটা ROB-এর মাথায় নেই, I1 এখনো মাথায় বসে আছে।

ধাপ ৫ — Commit, কঠোরভাবে in-order:

t2-শেষে: I1 সম্পন্ন, মাথায় → commit! architectural R1 = p10-এর মান
         ROB: [I2:না][I3:✓][I4:না], মাথা এখন I2

t3-শেষে: I2 সম্পন্ন, মাথায় → commit! architectural R4 = p11-এর মান
         ROB: [I3:✓][I4:না], মাথা এখন I3

t3 (একই cycle বা পরের): I3 আগে থেকেই সম্পন্ন, এখন মাথায় → commit!
         architectural R1 = p12-এর মান (I1-এর পুরনো p10-mapping
         এখন প্রতিস্থাপিত — p10 free list-এ ফিরতে পারে)
         ROB: [I4:না], মাথা এখন I4

t4-শেষে: I4 সম্পন্ন, মাথায় → commit! architectural R7 = p13-এর মান
         ROB: খালি

Execution ক্রম ছিল এলোমেলো (I3, I1, I2, I4), কিন্তু commit ক্রম ঠিক program order (I1, I2, I3, I4)। বাইরে থেকে, কেউ যদি শুধু architectural register-এর পরিবর্তন observe করে, তার মনে হবে CPU সরল, in-order ক্রমেই instruction চালিয়েছে — যদিও ভেতরে ঠিক তার উল্টো ঘটেছিল।

নিজে চালিয়ে দেখুন

EXPERIMENT

False dependency ভাঙার প্রভাব IPC-তে মাপুন

Linux (x86-64), gcc, perf· ২৫ মিনিট

সরাসরি rename table বা ROB observe করার কোনো user-space উপায় নেই — এগুলো সম্পূর্ণভাবে hardware-এর ভেতরে লুকানো। কিন্তু আমরা পরোক্ষভাবে এর প্রভাব মাপতে পারি।

ধারণা: এমন একটা loop লিখব যেখানে বহু independent floating-point chain আছে (একে অন্যের উপর নির্ভর করে না)। একটা ভার্সনে প্রতিটা chain আলাদা variable (তাই compiler আলাদা register দেবে)। আরেকটা ভার্সনে ইচ্ছাকৃতভাবে কম variable ব্যবহার করব যাতে compiler বাধ্য হয় register পুনর্ব্যবহার করতে (WAR/WAW তৈরি করে)। যদি hardware renaming কাজ করে, দুটোর গতি প্রায় সমান হওয়া উচিত।

// dep_chains.c
#include <stdio.h>
#include <time.h>

#define N 200000000L

double many_registers(void) {
    // ৮টা independent accumulator, ৮টা আলাদা variable
    double a=1.0, b=2.0, c=3.0, d=4.0, e=5.0, f=6.0, g=7.0, h=8.0;
    for (long i = 0; i \< N/8; i++) {
        a = a * 1.0000001 + 0.1;
        b = b * 1.0000001 + 0.1;
        c = c * 1.0000001 + 0.1;
        d = d * 1.0000001 + 0.1;
        e = e * 1.0000001 + 0.1;
        f = f * 1.0000001 + 0.1;
        g = g * 1.0000001 + 0.1;
        h = h * 1.0000001 + 0.1;
    }
    return a+b+c+d+e+f+g+h;
}

int main(void) {
    struct timespec t0, t1;
    clock_gettime(CLOCK_MONOTONIC, &t0);
    double r = many_registers();
    clock_gettime(CLOCK_MONOTONIC, &t1);
    double dt = (t1.tv_sec - t0.tv_sec) + (t1.tv_nsec - t0.tv_nsec) / 1e9;
    printf("result=%f  time=%.4fs\n", r, dt);
    return 0;
}

gcc -O1 -fno-tree-vectorize -o dep dep_chains.c
./dep
perf stat -e instructions,cycles ./dep

-fno-tree-vectorize ইচ্ছাকৃতভাবে auto-vectorization বন্ধ রাখছি (পরের লেসনের বিষয়ে না গিয়ে scalar instruction-এই থাকতে)। -O1 ব্যবহার করছি যাতে compiler নিজে থেকেই বেশি register বরাদ্দ থেকে বিরত না হয়, কিন্তু register allocation-এর decision compiler-এর হাতেই — এখানে মূল পাঠ হলো IPC (instructions-per-cycle) সংখ্যা দেখা।

সাধারণ ফলাফল (Skylake-class CPU-তে):

instructions      1,800,000,143
cycles              620,000,921
IPC                 ≈ 2.90

৮টা independent chain থাকায় CPU একসাথে একাধিক multiply-add চালাতে পারছে — IPC ১-এর অনেক বেশি (যা একটা কঠোর sequential dependency chain-এ সীমাবদ্ধ থাকত)। এখন objdump -d dep দিয়ে দেখুন — compiler কয়টা distinct XMM register ব্যবহার করেছে (xmm0 থেকে xmm7 — ঠিক ৮টা, একটাও পুনর্ব্যবহার হয়নি এই সহজ loop-এ কারণ ৮টাই যথেষ্ট)।

দ্বিতীয় ধাপ — জোর করে register চাপ তৈরি করা। যদি একই কাজ আরও বেশি (যেমন ২০টা) independent chain দিয়ে করেন, compiler-কে বাধ্য হতে হবে register পুনর্ব্যবহার করতে (x86-64-এ মাত্র ১৬টা XMM register আছে সাধারণ ব্যবহারে)। তখনও দেখবেন IPC প্রায় একই রকম উচ্চ থাকছে — কারণ hardware renaming সেই পুনর্ব্যবহৃত register-গুলোর মধ্যে false dependency নিজে থেকেই ভেঙে দিচ্ছে। এটাই পরোক্ষ প্রমাণ: যদি renaming না থাকত, ২০-chain ভার্সনটা register পুনর্ব্যবহারের কারণে সিরিয়ালাইজড হয়ে যেত আর IPC হঠাৎ কমে যেত। বাস্তবে সেটা হয় না।

একটা in-order CPU-তে (যেমন পুরনো ARM Cortex-A53) একই experiment চালান

যদি হাতে একটা in-order core থাকে (Raspberry Pi-এর কিছু পুরনো মডেলে, বা QEMU-তে in-order মডেল simulate করে), এই একই কোড চালালে ২০-chain ভার্সনটায় IPC সত্যিই কমে যাবে — কারণ সেখানে renaming নেই, register পুনর্ব্যবহার সত্যিই একটা বাধা তৈরি করে। এই তুলনাটাই সবচেয়ে স্পষ্ট প্রমাণ যে renaming একটা বাস্তব, পরিমাপযোগ্য পার্থক্য তৈরি করে, শুধু একটা তাত্ত্বিক ধারণা না।

এটা কী প্রমাণ করে

একই সংখ্যক independent floating-point অপারেশন, শুধু কম না বেশি architectural register ব্যবহার করলেও, বাস্তব CPU-তে প্রায় একই গতিতে চলে — কারণ hardware register renaming ইতিমধ্যেই false dependency ভেঙে ফেলে। এটা renaming-এর অস্তিত্বের পরোক্ষ কিন্তু measurable প্রমাণ।

নিজে বানান

BUILD IT

Rename Table + Reorder Buffer সিমুলেটর

Python · ●●●●○

একটা simple instruction format ডিজাইন করুন: (dest, src1, src2) architectural register নাম দিয়ে
Rename table ও free list তৈরি করুন, dispatch-এর সময় প্রতিটা instruction rename করুন
ROB তৈরি করুন — প্রতিটা entry-তে dest physical register, সম্পন্ন কি না, আর program-order index থাকবে
একটা সরলীকৃত execution simulator লিখুন যেখানে প্রতিটা instruction র‍্যান্ডম বিলম্বে সম্পন্ন হয় (এলোমেলো ক্রম অনুকরণ করতে)
প্রতি cycle-এ ROB-এর মাথা পরীক্ষা করে in-order commit বাস্তবায়ন করুন
একটা WAR/WAW-ঘন instruction sequence দিয়ে যাচাই করুন commit ক্রম সবসময় program order মেনে চলে

মূল ধারণা: rename table একটা dict (architectural → physical), free list একটা queue, ROB একটা list যেখানে insert লেজে হয়, আর commit মাথা থেকে পরীক্ষা করে।

import random
from collections import deque

class RenameEngine:
    def __init__(self, n_arch=8, n_phys=32):
        self.rat = {f"R{i}": f"p{i}" for i in range(n_arch)}
        self.free_list = deque(f"p{i}" for i in range(n_arch, n_phys))
        self.committed_rat = dict(self.rat)  # commit-হওয়া, সত্য architectural mapping

    def rename(self, instr):
        """instr = (dest, src1, src2) architectural নামে। ফেরত: physical form।"""
        dest, src1, src2 = instr
        p_src1 = self.rat[src1] if src1 else None
        p_src2 = self.rat[src2] if src2 else None
        p_dest = self.free_list.popleft() if dest else None
        old_p_dest = self.rat.get(dest) if dest else None
        if dest:
            self.rat[dest] = p_dest
        return {
            "arch_dest": dest, "p_dest": p_dest,
            "p_src1": p_src1, "p_src2": p_src2,
            "old_p_dest": old_p_dest,   # commit-এর সময় free করার জন্য
        }


class ROB:
    def __init__(self):
        self.entries = deque()   # প্রতিটা: dict, program order-এ

    def dispatch(self, renamed, instr_id):
        self.entries.append({"id": instr_id, **renamed, "done": False})
        return self.entries[-1]

    def mark_done(self, instr_id):
        for e in self.entries:
            if e["id"] == instr_id:
                e["done"] = True
                return

    def try_commit(self, free_list, committed_rat, log):
        committed = []
        while self.entries and self.entries[0]["done"]:
            head = self.entries.popleft()
            if head["arch_dest"]:
                old = committed_rat.get(head["arch_dest"])
                committed_rat[head["arch_dest"]] = head["p_dest"]
                if old and old != head["p_dest"]:
                    free_list.append(old)   # পুরনো physical register মুক্ত
            committed.append(head["id"])
            log.append(f"COMMIT  I{head['id']}: arch {head['arch_dest']} = {head['p_dest']}")
        return committed


def simulate(program, seed=0):
    random.seed(seed)
    engine = RenameEngine()
    rob = ROB()
    log = []

    # ধাপ ১: সব instruction rename ও dispatch করি, program order বজায় রেখে
    dispatched = []
    for i, instr in enumerate(program):
        renamed = engine.rename(instr)
        entry = rob.dispatch(renamed, i)
        dispatched.append(i)
        log.append(f"RENAME  I{i}: {instr} -> dest={renamed['p_dest']} "
                    f"src1={renamed['p_src1']} src2={renamed['p_src2']}")

    # ধাপ ২: এলোমেলো ক্রমে "execute" (সম্পন্ন) হয় -- বাস্তব hardware-এর
    # dependency-চালিত ক্রম অনুকরণ করতে shuffle করছি
    exec_order = dispatched[:]
    random.shuffle(exec_order)
    for i in exec_order:
        log.append(f"EXEC    I{i} সম্পন্ন")
        rob.mark_done(i)
        # প্রতি ধাপে যতটা সম্ভব commit করার চেষ্টা করি
        rob.try_commit(engine.free_list, engine.committed_rat, log)

    # অবশিষ্ট (যদি থাকে) commit
    rob.try_commit(engine.free_list, engine.committed_rat, log)
    return log, engine.committed_rat


# WAW ও WAR-ঘন প্রোগ্রাম, যেমন লেসনের উদাহরণ
program = [
    ("R1", "R2", "R3"),   # I0: R1 = R2 + R3
    ("R4", "R1", None),   # I1: R4 = R1 (RAW)
    ("R1", "R5", "R6"),   # I2: R1 = R5 - R6 (WAW সাথে I0)
    ("R7", "R1", "R4"),   # I3: R7 = R1 + R4 (RAW সাথে I2)
]

log, final_rat = simulate(program, seed=42)
for line in log:
    print(line)
print("\nচূড়ান্ত committed architectural state:", final_rat)

যাচাই করার বিষয়: log-এর মধ্যে সব COMMIT লাইন খুঁজে বের করুন — তাদের I নম্বর সবসময় বাড়ন্ত ক্রমে (০,১,২,৩…) আসা উচিত, EXEC লাইনের ক্রম যতই এলোমেলো হোক না কেন। এটাই মূল invariant যা এই সিমুলেটরকে প্রমাণ করতে হবে।

নিজে বাড়ান:

একটা branch misprediction অনুকরণ করুন — একটা নির্দিষ্ট instruction-এর পরে সব ROB entry বাতিল করুন (flush), আর rename table পুনরুদ্ধার করুন committed_rat-এ
Free list শেষ হয়ে গেলে কী হওয়া উচিত? (বাস্তব CPU-তে dispatch থেমে যায়, একে বলে “rename stall”) — সেটা implement করুন
একটা exception অনুকরণ করুন: একটা নির্দিষ্ট instruction-এ “fault” flag যোগ করুন, আর দেখান commit precisely সেই instruction-এ থেমে যায়, তার পরের সব ROB entry বাতিল হয়ে যায়
একাধিক commit per cycle (superscalar) সমর্থন করুন — একই cycle-এ ROB-এর মাথা থেকে ধারাবাহিক কয়েকটা “সম্পন্ন” entry একসাথে commit করুন

বাস্তব সিস্টেমে

যেখানে register renaming ও ROB প্রতিদিন কাজ করে

Intel Pentium Pro (P6, 1995)। প্রথম mainstream x86 CPU যেখানে পূর্ণাঙ্গ out-of-order execution এসেছিল একটা ৪০-entry ROB সহ। এর ডিজাইন দর্শন — CISC x86 instruction-কে ভেতরে RISC-সদৃশ micro-op-এ ভেঙে renaming/ROB প্রয়োগ করা — আজও প্রতিটা আধুনিক x86 CPU-এর ভিত্তি।

Apple M1/M2 (2020-)। অস্বাভাবিক বড়, ৬৩০-entry ROB নিয়ে আলোচিত — প্রচলিত x86 CPU-এর চেয়ে প্রায় তিনগুণ বড়। এই বিশাল out-of-order window-ই memory-bound কোডে M1-কে অসাধারণ ভালো পারফরম্যান্স দেয়, কারণ একটা cache miss-এ আটকে থাকা load-এর পিছনে অনেক দূর পর্যন্ত independent কাজ খুঁজে execute করে ফেলতে পারে।

AMD Zen আর্কিটেকচার। প্রতিটা প্রজন্মে ROB আকার আর physical register file আকার বেড়েছে (Zen থেকে Zen 4 পর্যন্ত)। AMD-র নিজস্ব optimization guide-এ renaming-conscious কোডিং প্যাটার্ন নিয়ে সরাসরি পরামর্শ থাকে — যেমন “false dependency এড়াতে xor reg, reg দিয়ে একটা register শূন্য করুন mov reg, 0-এর বদলে,” কারণ CPU xor reg, reg-কে বিশেষভাবে চেনে (zero idiom) আর সেটাকে কোনো পুরনো মানের উপর নির্ভরতা ছাড়াই সরাসরি একটা নতুন “শূন্য” physical register বরাদ্দ করে দেয়।

RISC-V BOOM (Berkeley Out-of-Order Machine)। একটা open-source, শিক্ষামূলক out-of-order RISC-V core, বিশ্ববিদ্যালয়ে ব্যবহৃত হয় ঠিক এই ধারণাগুলো — rename table, free list, ROB — hands-on শেখাতে। এর সোর্স কোড পড়লে এই লেসনের ধারণাগুলো Chisel hardware-description ভাষায় হুবহু দেখা যায়।

IBM POWER ও mainframe লাইন। Tomasulo-র মূল কাজ IBM 360/91-এর জন্যই হয়েছিল; আধুনিক IBM POWER10 প্রসেসরে ৩০০-এর বেশি physical register সহ deep out-of-order pipeline আছে, একই বংশধারার সরাসরি উত্তরসূরি।

Meltdown (2018) — নিরাপত্তা যোগসূত্র। Meltdown আক্রমণ ঠিক এই speculative/committed state-এর ফাঁক ব্যবহার করেছিল — একটা illegal memory access-এর ফলাফল ROB-এ commit হওয়ার আগেই তার side-effect (cache-এর মধ্যে) সংবেদনশীল ডেটা রেখে যেত, exception আসলে raise হওয়ার আগে (“transient execution”)। এটা প্রমাণ করে ROB শুধু performance-এর জন্য না — architectural correctness আর নিরাপত্তা দুটোরই কেন্দ্রে আছে।

Compiler-এর instruction scheduling। যদিও hardware নিজেই reorder করে, compiler তবু ভালো instruction ordering বেছে দেওয়ার চেষ্টা করে — কারণ rename/ROB-এর সীমিত window-এর মধ্যে independent কাজ যত কাছাকাছি রাখা যায়, hardware তত সহজে সেগুলো খুঁজে পায়।

perf stat-এর IPC মেট্রিক। যেকোনো Linux সিস্টেমে perf stat চালালে যে IPC (instructions per cycle) সংখ্যা দেখায়, তার ১-এর বেশি হওয়া (আধুনিক CPU-তে সাধারণত ২-৪) সরাসরি এই renaming + ROB ব্যবস্থার ফসল — এটা ছাড়া superscalar issue করা সম্ভবই হতো না false dependency-র চাপে।

যে ভুলগুলো সবাই করে

“আরও বেশি architectural register থাকলে renaming-এর দরকারই পড়ত না।”

আংশিক সত্য, কিন্তু পুরোপুরি ভুল সিদ্ধান্ত। ISA-তে বেশি architectural register দিলে (যেমন RISC-V-এর ৩২টা x86-64-এর ১৬টার চেয়ে বেশি) false dependency-র সম্ভাবনা কমে, কিন্তু সম্পূর্ণ নির্মূল হয় না — কারণ একই function বারবার call হলে, বা একটা loop বারবার চললে, একই architectural register বারবার নতুন, সম্পূর্ণ ভিন্ন মানের জন্য পুনর্ব্যবহৃত হবেই। প্রতিটা loop iteration নিজেই একটা নতুন WAW সংঘর্ষের উৎস — সেখানে register সংখ্যা যতই বাড়ান না কেন, iteration-এর সংখ্যা সবসময় বেশি।

আর architectural register বাড়ানোর নিজস্ব খরচ আছে — instruction encoding-এ প্রতিটা register operand-এর জন্য বেশি bit লাগে (register index encode করতে log₂(সংখ্যা) bit), যা encoding ঘনত্ব কমায় (লেসন ৪-এর addressing mode-এর আলোচনার সাথে সরাসরি সম্পর্কিত)। তাই বাস্তব সমাধান architectural register বাড়ানো না — physical register hardware-এ লুকিয়ে রাখা, যেখানে encoding-এর কোনো প্রভাব পড়ে না।

“আপনি যে register-এ assembly লেখেন, CPU ঠিক সেই register-ই ব্যবহার করে।”

Assembly বা compiled machine code-এ যে register নাম (RAX, x0) দেখেন, সেগুলো সবসময় architectural নাম — এগুলোই ISA-র চুক্তি, প্রোগ্রামের বাইরের জগতের সাথে যোগাযোগের ভাষা। কিন্তু একটা out-of-order CPU-তে প্রতিটা dynamic instance (একটা loop হাজারবার চললে, প্রতিটা iteration আলাদা instance) নিজস্ব physical register পায়, dynamically, dispatch-এর সময়। একই static assembly instruction, চলার সময় প্রতিবার সম্পূর্ণ ভিন্ন physical register স্পর্শ করতে পারে।

এই কারণেই perf-এর মতো টুল বা CPU manual-এ physical register file-এর আকার উল্লেখ থাকলেও, কোনো ISA manual কখনো তাদের address করার কোনো উপায় দেয় না — এগুলো সম্পূর্ণভাবে implementation detail, ISA-র অংশ না। Intel তাদের Skylake থেকে Golden Cove-এ physical register সংখ্যা প্রায় ৫০% বাড়িয়েছে অথচ x86-64 ISA-র একটা bit-ও বদলায়নি।

“Out-of-order execution মানে প্রোগ্রামের ফলাফল অনির্ভরযোগ্য বা অনির্দিষ্ট হয়ে যায়।”

সম্পূর্ণ উল্টো — পুরো এই লেসনের বিষয়বস্তুই এই ভুল ধারণা ভাঙার জন্য। Renaming true dependency-কে অক্ষত রাখে (শুধু false dependency ভাঙে), আর ROB নিশ্চিত করে commit সবসময় program order মেনে চলে। ফলাফল: একটা single-threaded প্রোগ্রামের observable আচরণ ঠিক তেমনই থাকে যেমন CPU সরল, in-order ক্রমে instruction চালালে হতো — এই গ্যারান্টিটার নাম sequential consistency (একটা single core-এর মধ্যে)।

যা সত্যিই জটিল হয় তা হলো multi-core পরিস্থিতিতে, যেখানে বিভিন্ন core-এর memory operation-এর আপেক্ষিক দৃশ্যমানতা নিয়ে প্রশ্ন ওঠে (memory ordering, memory model) — কিন্তু সেটা একটা সম্পূর্ণ ভিন্ন বিষয়, single-core out-of-order correctness-এর সাথে গুলিয়ে ফেলা উচিত না। এই লেসনের সব আলোচনাই একটা single core-এর ভেতরের গল্প।

“বড় ROB মানেই সবসময় ভালো CPU।”

ROB আকার বাড়ানোর নিজস্ব খরচ আছে, আর ফলাফল সবসময় সমানুপাতিক না।

প্রতিটা ROB entry ট্র্যাক করতে hardware লাগে (dest register, সম্পন্ন কি না, exception status, ইত্যাদি), আর প্রতি cycle-এ মাথা থেকে commit-যোগ্য entry খোঁজার logic ROB-এর আকারের সাথে জটিলতা বাড়ায়। এছাড়া একটা বড় ROB শুধুই মূল্যবান যখন সত্যিই লম্বা latency-র operation (যেমন cache miss) থাকে যার পিছনে independent কাজ পাওয়া যায় — অনেক ধরনের কোডে (tight dependency chain-যুক্ত, branchy কোড) একটা বিশাল ROB কার্যত অব্যবহৃত থেকে যায়, কারণ CPU খুব বেশি দূর “সামনে তাকাতে” পারার আগেই একটা branch misprediction পুরো window flush করে দেয়।

এই কারণে ROB আকার সবসময় একটা power/area/complexity বনাম বাস্তব-কোডে-লাভ trade-off — নকশাকারীরা real-world workload প্রোফাইল করে সিদ্ধান্ত নেন, “যত বড় তত ভালো” কোনো সরল নিয়ম না।

বুঝেছেন কি না দেখুন

নিচের instruction sequence-এ কোন কোন pair-এ RAW, WAR, এবং WAW dependency আছে চিহ্নিত করুন:

I1: R2 = R1 + R3
I2: R1 = R4 + R5
I3: R6 = R2 + R1

যুক্তি

প্রতিটা pair পরীক্ষা করি।

I1 → I2: I1 R1 পড়ে (operand), I2 R1-এ লেখে় (destination)। এটা WAR — I2 যদি I1-এর আগে লিখে ফেলে, I1 ভুল মান পড়বে।

I1 → I3: I1 R2-এ লেখে, I3 R2 পড়ে। এটা RAW — সত্যিকারের dependency, I3-এর হিসাব I1-এর ফলাফলের উপর নির্ভর করে।

I2 → I3: I2 R1-এ লেখে, I3 R1 পড়ে। এটাও RAW — I3 I2-এর নতুন R1 মান ব্যবহার করে।

I1 → I2 নিয়ে আরেকটা কোণ: I1 R2-এ লেখে, কোনো instruction R2-এ আবার লেখে না — তাই কোনো WAW এখানে নেই।

সারাংশ: I1→I2 WAR (নকল), I1→I3 RAW (সত্য), I2→I3 RAW (সত্য)। Renaming I1→I2-এর WAR ভাঙবে (তারা এখন যেকোনো ক্রমে চলতে পারবে), কিন্তু দুটো RAW অক্ষত থাকবে — I3 কে I1 আর I2 দুটোরই ফলাফলের জন্য সত্যিই অপেক্ষা করতে হবে।

প্রশ্ন ১-এর সিকোয়েন্সটা rename করুন। ধরুন rename-এর আগে R1→p1, R2→p2, ..., R6→p6, আর free physical register p10, p11 পাওয়া যাচ্ছে (ক্রমানুসারে বরাদ্দ হবে)।

প্রয়োগ

প্রতিটা instruction ক্রমানুসারে rename করি, RAT আপডেট করতে করতে।

I1: R2 = R1 + R3 Source: R1→p1, R3→p3 (এখনো অপরিবর্তিত)। Destination R2 নতুন p10 পায়। Renamed: p10 = p1 + p3 RAT আপডেট: R2 → p10

I2: R1 = R4 + R5 Source: R4→p4, R5→p5। Destination R1 নতুন p11 পায়। Renamed: p11 = p4 + p5 RAT আপডেট: R1 → p11

I3: R6 = R2 + R1 Source: R2 — RAT-এ এখন p10 (I1-এর নতুন mapping)। R1 — RAT-এ এখন p11 (I2-এর নতুন mapping)। Destination R6 — ধরি পরের free register p12। Renamed: p12 = p10 + p11

সম্পূর্ণ renamed sequence:

I1: p10 = p1 + p3
I2: p11 = p4 + p5
I3: p12 = p10 + p11

লক্ষ্য করুন I1 আর I2 এখন সম্পূর্ণ independent — কোনো shared physical register নেই, তাই hardware তাদের যেকোনো ক্রমে বা একসাথে চালাতে পারে। I3 সঠিকভাবেই p10 (I1-এর ফলাফল) আর p11 (I2-এর ফলাফল) দুটোর জন্যই অপেক্ষা করবে — এটাই আসল RAW dependency, renaming এটা ভাঙেনি, শুধু সঠিকভাবে physical register-এর মাধ্যমে ধরে রেখেছে।

একটা সহপাঠী বলছে, “ROB শুধু performance optimization — এটা থাকলে ভালো, না থাকলেও out-of-order CPU সঠিক ফলাফল দেবে, শুধু একটু ধীরে দিতে পারত।” এই দাবিটা মূল্যায়ন করুন।

যুক্তি

দাবিটা ভুল — ROB শুধু speed-এর জন্য না, correctness-এর জন্যও অপরিহার্য।

ROB ছাড়া, যদি hardware সত্যিই out-of-order execution করে (যা এই পুরো module-এর ভিত্তি), তাহলে সমস্যাটা speed-এর না — observable correctness-এর।

দুইটা নির্দিষ্ট সমস্যা:

১. Exception handling ভেঙে পড়ে। যদি I5 I3-এর আগে চলে আর architectural state সরাসরি আপডেট করে ফেলে, আর তারপর I3-এ একটা exception ধরা পড়ে (page fault, ধরুন), CPU-কে বলতে হবে কোন instruction পর্যন্ত program “সম্পন্ন” হয়েছে। কিন্তু I5 ইতিমধ্যেই তার প্রভাব ফেলে দিয়েছে, I4 হয়তো ফেলেনি — এই অবস্থা কোনো সরল, in-order execution-এর সাথে মেলে না। OS handler যদি program state পুনরুদ্ধার করতে চায় (যেমন page fault-এর পর page allocate করে instruction পুনরায় চালানো), সে জানবে না কী পুনরায় চালাবে।

২. Branch misprediction থেকে recovery অসম্ভব হয়ে পড়ে। Speculatively চলা instruction-গুলো যদি সরাসরি architectural state আপডেট করে ফেলে, misprediction ধরা পড়ার পর সেই আপডেটগুলো ফিরিয়ে নেওয়ার কোনো সাধারণ উপায় থাকে না — প্রতিটা instruction-এর জন্য আলাদা “undo” logic লিখতে হতো, যা জটিলতায় ROB-এর চেয়েও খারাপ।

যা ঠিক: ROB “ধীরে দিতে পারত” বলাটা ভুল ফ্রেমিং — ROB ছাড়া speculative, out-of-order CPU আদৌ সঠিক ফলাফল দিতেই পারবে না, নির্ভরযোগ্যভাবে। এটা optional optimization না, বরং out-of-order

speculation একসাথে সঠিকভাবে কাজ করার জন্য আবশ্যিক কাঠামো — precise exception, branch recovery, দুটোরই ভিত্তি।

একমাত্র বিকল্প হতো out-of-order execution সম্পূর্ণ বাদ দেওয়া (in-order-এ ফিরে যাওয়া) — কিন্তু তাহলে আগের লেসনগুলোর সব superscalar/OoO সুবিধাই হারাতে হতো।

একটা 4-entry ROB-এ instruction I0, I1, I2, I3 (program order) dispatch হয়েছে। Execution সম্পন্ন হওয়ার ক্রম: I2 (cycle ৩-এ), I0 (cycle ৪-এ), I3 (cycle ৪-এ), I1 (cycle ৭-এ)। প্রতি cycle-এ সর্বোচ্চ একটা commit সম্ভব ধরে নিয়ে, কোন cycle-এ কোন instruction commit হবে?

প্রয়োগ

নিয়ম মনে রাখুন: ROB-এর মাথা (সবচেয়ে পুরনো, program order-এ) “সম্পন্ন” না হলে কেউই commit হতে পারবে না, এমনকি তার পরের instruction আগে সম্পন্ন হলেও।

Program order (মাথা থেকে): I0, I1, I2, I3।

Cycle ৩: I2 সম্পন্ন হলো। কিন্তু মাথায় I0 — এখনো সম্পন্ন না। কোনো commit নেই।

Cycle ৪: I0 আর I3 সম্পন্ন হলো। এখন মাথায় I0, আর সেটা সম্পন্ন — I0 commit হয়। মাথা এখন I1, এখনো সম্পন্ন না (শুধু cycle ৭-এ হবে)। যদিও I2 আর I3 দুটোই এতক্ষণে সম্পন্ন, তারা commit করতে পারবে না — I1 পথ আটকে আছে (একে বলে head-of-line blocking)। এই cycle-এ শুধু I0 commit।

Cycle ৫, ৬: মাথায় এখনও I1, সম্পন্ন না। কোনো commit নেই। I2, I3 এখনও সম্পন্ন অবস্থায় বসে অপেক্ষা করছে ROB-এ।

Cycle ৭: I1 সম্পন্ন হলো। মাথায় I1, এখন সম্পন্ন — I1 commit। মাথা এখন I2, যেটা আগে থেকেই (cycle ৩ থেকে) সম্পন্ন — একই cycle-এ (যদি hardware প্রতি cycle-এ একাধিক sequential commit সমর্থন করে) বা পরের cycle-এ I2 commit। তারপর মাথা I3, আগে থেকেই সম্পন্ন — I3 commit।

সারসংক্ষেপ (single-commit-per-cycle ধরে):

Cycle	Commit
৪	I0
৭	I1
৮	I2
৯	I3

মূল শিক্ষা: I2 execution cycle ৩-এই শেষ, কিন্তু commit হতে হতে cycle ৮ লেগে যায় — পাঁচ cycle “অপেক্ষা” শুধু I1-এর ধীরগতির কারণে। এটাই দেখায় কেন একটা একক ধীর instruction (যেমন একটা cache-miss করা load) পুরো ROB-কে কার্যত থামিয়ে দিতে পারে, এমনকি তার পিছনের সব কাজ আগেই সম্পন্ন হয়ে থাকলেও।

কেন একটা physical register শুধু commit-এর সময় free করা হয়, instruction-এর execution সম্পন্ন হওয়ার সাথে সাথে না?

ডিজাইন

কারণটা branch misprediction recovery-র সাথে সরাসরি জড়িত।

ধরুন I3 একটা register-এ লেখে (physical p20), আর I3 execute হয়ে যায় — কিন্তু এখনো commit হয়নি (তার আগের কোনো instruction ROB-এ আটকে আছে)। যদি এই মুহূর্তে p20-এর “পুরনো” mapping (যেটা I3 প্রতিস্থাপন করেছিল) free list-এ ফিরিয়ে দেওয়া হয়, আর সেটা তক্ষুনি আরেকটা instruction-এর জন্য পুনর্বরাদ্দ হয়ে যায় — তাহলে সমস্যা।

এখন কল্পনা করুন I3-এর আগে কোনো branch mispredicted বলে ধরা পড়ল। CPU-কে I3 সহ তার পরের সব instruction বাতিল করতে হবে, আর rename table-কে সেই পুরনো, “প্রতিস্থাপিত” mapping-এ ফিরিয়ে নিতে হবে (কারণ architecturally, I3 আসলে কখনো ঘটেইনি)। কিন্তু যদি সেই পুরনো physical register ইতিমধ্যে অন্য কোনো (misprediction-এর পরে dispatch হওয়া, তাই এমনিতেও বাতিল-যোগ্য, কিন্তু কালানুক্রমিকভাবে জটিল) instruction-এ পুনর্বরাদ্দ হয়ে গিয়ে থাকে, রোলব্যাক করাটা একটা জটিল সংঘর্ষে পরিণত হয়।

Commit-নির্ভর মুক্তি এই সমস্যা এড়ায়: যেহেতু commit নিজেই নিশ্চিত করে যে instruction-টা আর কখনো বাতিল হবে না (commit মানেই architecturally চূড়ান্ত, misprediction flush আর কখনো তাকে স্পর্শ করবে না), commit-এর মুহূর্তেই একমাত্র নিরাপদ সময় যখন নিশ্চিতভাবে জানা যায় পুরনো physical register আর কখনো লাগবে না — কোনো speculative instruction তাকে rollback-এর জন্য চাইবে না।

সংক্ষেপে: execution সম্পন্ন মানে “ফলাফল প্রস্তুত,” কিন্তু commit মানে “এই ফলাফল স্থায়ীভাবে সত্য, আর কখনো বাতিল হবে না।” Physical register free করার মতো একটা অপরিবর্তনীয় (irreversible) কাজের জন্য শুধু দ্বিতীয় গ্যারান্টিটাই যথেষ্ট নিরাপদ।

এরপর কী

Different axis of parallelism-এর দিকে

Register renaming আর reorder buffer মিলে out-of-order execution-এর শেষ বড় ফাঁকটা বন্ধ করল — এখন আমরা জানি hardware কীভাবে সততার সাথে এলোমেলো execution থেকে সাজানো, program-order-সঙ্গত ফলাফল বের করে আনে, false dependency-কে পথের বাধা হতে না দিয়ে।

এই পুরো module-এর এখন পর্যন্ত যত parallelism নিয়ে কথা হয়েছে — pipelining, superscalar issue, out-of-order execution — সবগুলোর একটা common থিম: ভিন্ন ভিন্ন instruction একসাথে বা কাছাকাছি সময়ে চালানো। পরের লেসনে আমরা সম্পূর্ণ ভিন্ন একটা অক্ষ দেখব — একই একটা instruction, কিন্তু একসাথে অনেকগুলো data element-এ প্রয়োগ করা। এর নাম SIMD — Single Instruction, Multiple Data। যেখানে out-of-order একসাথে বিভিন্ন কাজ করার কৌশল, SIMD একটাই কাজ বহুগুণ করার কৌশল — আর দুটো একসাথে, একই CPU-তে, পরস্পরের পরিপূরক হিসেবে কাজ করে।

Register Renaming ও Reorder Buffer — মিথ্যা নির্ভরতা ভাঙা

এই লেসন শেষে আপনি পারবেন

আগে যা বোঝা থাকা দরকার

আগে এটা বুঝি

মূল ধারণা

তিন ধরনের dependency — একটা আসল, দুইটা নকল

সমাধান: architectural নাম থেকে physical storage আলাদা করা

Register renaming কীভাবে কাজ করে

এখন সমস্যা: এলোমেলো execution-কে সাজানো commit-এ ফেরানো

ROB-এর মূল ধারণা

Commit — ROB-এর মাথা থেকে, কঠোরভাবে সাজানো ক্রমে

কেন এটাই precise exception সম্ভব করে

ভেতরে কী ঘটছে

Reservation station, issue queue, আর ROB-এর মধ্যে সম্পর্ক

Speculative রাষ্ট্র বনাম committed রাষ্ট্র

ROB আকার কেন গুরুত্বপূর্ণ

উদাহরণ

সম্পূর্ণ trace — rename থেকে commit পর্যন্ত

নিজে চালিয়ে দেখুন

False dependency ভাঙার প্রভাব IPC-তে মাপুন

নিজে বানান

Rename Table + Reorder Buffer সিমুলেটর

বাস্তব সিস্টেমে

যেখানে register renaming ও ROB প্রতিদিন কাজ করে

যে ভুলগুলো সবাই করে

বুঝেছেন কি না দেখুন

এরপর কী

Different axis of parallelism-এর দিকে

আরও পড়ুন

এই লেসন শেষে আপনি পারবেন

আগে যা বোঝা থাকা দরকার

◔আগে এটা বুঝিWhy this matters

◆মূল ধারণাCore concept

তিন ধরনের dependency — একটা আসল, দুইটা নকল

সমাধান: architectural নাম থেকে physical storage আলাদা করা

Register renaming কীভাবে কাজ করে

এখন সমস্যা: এলোমেলো execution-কে সাজানো commit-এ ফেরানো

ROB-এর মূল ধারণা

Commit — ROB-এর মাথা থেকে, কঠোরভাবে সাজানো ক্রমে

কেন এটাই precise exception সম্ভব করে

⚙ভেতরে কী ঘটছেUnder the hood

Reservation station, issue queue, আর ROB-এর মধ্যে সম্পর্ক

Speculative রাষ্ট্র বনাম committed রাষ্ট্র

ROB আকার কেন গুরুত্বপূর্ণ

▶উদাহরণExample

সম্পূর্ণ trace — rename থেকে commit পর্যন্ত

⌘নিজে চালিয়ে দেখুনExperiment

False dependency ভাঙার প্রভাব IPC-তে মাপুন

⚒নিজে বানানBuild it yourself

Rename Table + Reorder Buffer সিমুলেটর

◉বাস্তব সিস্টেমেReal-world usage

যেখানে register renaming ও ROB প্রতিদিন কাজ করে

⚠যে ভুলগুলো সবাই করেMisconceptions

?বুঝেছেন কি না দেখুনCheck understanding

→এরপর কীNext step

Different axis of parallelism-এর দিকে

আরও পড়ুন

আগে এটা বুঝি

মূল ধারণা

ভেতরে কী ঘটছে

উদাহরণ

নিজে চালিয়ে দেখুন

নিজে বানান

বাস্তব সিস্টেমে

যে ভুলগুলো সবাই করে

বুঝেছেন কি না দেখুন

এরপর কী