Superscalar ও Out-of-Order Execution — যখন ক্রম নিজেই আলোচনার বিষয়

আগে এটা বুঝি

এখন পর্যন্ত এই module-এ pipelining মানে ছিল একটা জিনিস: বিভিন্ন instruction-এর বিভিন্ন স্টেজ একসাথে চলা (instruction ১ execute করছে যখন instruction ২ decode করছে যখন instruction ৩ fetch করছে) — কিন্তু প্রতিটা স্টেজে ঠিক একটামাত্র instruction।

আজ আমরা দুইটা নতুন প্রশ্ন তুলব। প্রথম: কেন একই cycle-এ একাধিক সম্পূর্ণ instruction execute না করে শুধু একটা? দ্বিতীয়, আরও গভীর: program-এ instruction-গুলো একটা নির্দিষ্ট ক্রমে লেখা আছে — কিন্তু হার্ডওয়্যারকে কি সেই ক্রম কঠোরভাবে মানতে হবে?

মূল ধারণা

Superscalar — সমান্তরাল Instruction, সমান্তরাল Hardware

একটা scalar pipeline (এখন পর্যন্ত আমরা যা দেখেছি) প্রতি cycle-এ সর্বোচ্চ একটা instruction fetch/decode/execute করে (যদিও pipelining-এর কারণে একই সময়ে বিভিন্ন instruction বিভিন্ন স্টেজে থাকে, প্রতি স্টেজে একটাই)।

একটা superscalar CPU একই cycle-এ একাধিক instruction একই স্টেজে ঢোকাতে পারে — কারণ এতে একাধিক copy of hardware আছে: একাধিক ALU (digital-logic/alu-design-এর সরাসরি সম্প্রসারণ, একটা না, কয়েকটা), একাধিক fetch/decode unit।

Cycle:      1        2        3        4
Instr 1:    IF       ID       EX       MEM/WB
Instr 2:    IF       ID       EX       MEM/WB
Instr 3:             IF       ID       EX
Instr 4:             IF       ID       EX

2-wide superscalar — একই cycle-এ দুইটা instruction একই stage-এ।

শর্ত: একই cycle-এ একসাথে যেতে পারা instruction-গুলো অবশ্যই স্বাধীন হতে হবে (একে অপরের ফলাফলের উপর নির্ভর না করা) — forwarding-and-stalling লেসনের data hazard বিশ্লেষণ এখানেও প্রযোজ্য, শুধু এখন প্রশ্নটা “পরের instruction-কে stall করতে হবে কি না” না, বরং “একই cycle-এ পাঠানো যাবে কি না”।

$\text{ADD R1, R2, R3} \qquad \text{SUB R4, R5, R6}$

এই দুইটা স্বাধীন (ভিন্ন register, কোনো dependency নেই) — একই cycle-এ পাঠানো যায় (যদি দুইটা ALU থাকে)।

$\text{ADD R1, R2, R3} \qquad \text{SUB R4, R1, R6}$

দ্বিতীয়টা প্রথমটার R1-এর উপর নির্ভরশীল — একই cycle-এ পাঠানো যায় না, এমনকি দুইটা ALU থাকলেও।

ভেতরে কী ঘটছে

In-Order-এর সীমা — যেখানে Out-of-Order জন্ম নেয়

Superscalar hardware থাকলেও, যদি CPU কঠোরভাবে program order মেনে চলে (in-order issue — instruction-গুলো ঠিক লেখা ক্রমেই pipeline-এ ঢুকতে হবে), একটা বাস্তব সমস্যা দেখা দেয়।

1: LOAD  R1, [addr]      ; মেমরি থেকে লোড — cache miss হলে ~২০০ cycle লাগতে পারে!
2: ADD   R2, R3, R4       ; R1-এর উপর নির্ভর করে না, সম্পূর্ণ স্বাধীন
3: SUB   R5, R6, R7       ; এটাও স্বাধীন
4: MUL   R8, R1, R9       ; R1-এর উপর নির্ভরশীল — LOAD শেষ না হলে চলতে পারে না

Instruction ১ যদি cache miss করে (memory-hierarchy লেসনের বাস্তবতা — একটা DRAM access ~২০০ cycle), in-order hardware-এ instruction ২ আর ৩ — যেগুলো সম্পূর্ণ স্বাধীন, এখনই চলতে প্রস্তুত — তাদেরও অপেক্ষা করতে হয়, শুধু কারণ তারা প্রোগ্রামে instruction ১-এর পরে লেখা। এটা বিশাল অপচয় — প্রস্তুত কাজ অলসভাবে বসে থাকছে।

মূল অন্তর্দৃষ্টি

Program order একটা যোগাযোগের সুবিধা মানুষের জন্য (কোড পড়া সহজ হয় ধারাবাহিকভাবে), কিন্তু hardware-এর জন্য এটা একটা অপ্রয়োজনীয় বাধ্যবাধকতা — যতক্ষণ প্রকৃত data dependency (true RAW dependency, register-renaming-reorder-buffer লেসনে বিস্তারিত) সম্মান করা হচ্ছে, ইনস্ট্রাকশন যেকোনো ক্রমে চললে ফলাফল একই। Out-of-order execution ঠিক এই পর্যবেক্ষণ কাজে লাগায়।

Out-of-order-এ: instruction ১ (LOAD) memory থেকে ফলাফলের জন্য অপেক্ষা করার সময়ই, instruction ২ আর ৩ (স্বাধীন) আগেই execute হয়ে যায়। Instruction ৪ (যেটা সত্যিই LOAD-এর উপর নির্ভরশীল) LOAD সম্পূর্ণ হওয়া পর্যন্ত অপেক্ষা করে — কিন্তু ২ আর ৩ আর অপ্রয়োজনীয়ভাবে আটকে থাকে না।

$\text{Effective throughput} = \frac{\text{completed instructions}}{\text{cycles}}$

Out-of-order এই অনুপাতকে in-order-এর তুলনায় উল্লেখযোগ্যভাবে বাড়ায়, বিশেষত যখন long-latency operation (cache miss, division) মাঝেমধ্যে ঘটে — যা বাস্তব প্রোগ্রামে প্রায় সবসময়ই ঘটে।

উদাহরণ

Dependency Tracking — সমস্যার একটা আভাস

Out-of-order execution বাস্তবায়ন করতে হার্ডওয়্যারকে জানতে হবে প্রতিটা instruction-এর জন্য তার operand-গুলো প্রস্তুত কি না — প্রতি cycle-এ, গতিশীলভাবে।

একটা সরল ধারণা — scoreboard (CDC 6600, ১৯৬৪, James Thornton — out-of-order execution-এর প্রথম বাস্তব বাস্তবায়ন, আজকের অত্যাধুনিক CPU-রও ধারণাগত পূর্বপুরুষ): প্রতিটা register-এর জন্য একটা bit রাখুন যা বলে “এই register-এর মান লেখার জন্য এখনও কোনো pending instruction আছে কি না”।

Scoreboard বিট (সরলীকৃত):

instruction issue হওয়ার সময়:
  - সব source operand-এর scoreboard bit চেক করুন — কোনোটা "pending" হলে অপেক্ষা করুন
  - destination register-এর bit "pending" সেট করুন

instruction সম্পূর্ণ হলে:
  - destination register-এর bit clear করুন (এখন "ready")
  - অপেক্ষমান instruction-গুলো আবার চেক করুন — এখন কেউ প্রস্তুত হলো কি না

প্রতি cycle-এ hardware সব pending instruction-এর মধ্যে কোনগুলো এখন প্রস্তুত তা খুঁজে বের করে, আর প্রস্তুতগুলোকে execute-এ পাঠায় — program order অগ্রাহ্য করে, শুধু readiness অনুযায়ী।

একটা জটিলতা যা এখানে শুধু নাম দেওয়া হচ্ছে

Scoreboard true dependency (RAW) ঠিকভাবে ধরে, কিন্তু এটা একটা সমস্যায় পড়ে: যদি দুইটা ভিন্ন instruction একই register-এ লেখে (WAW) বা একটা read করার আগেই আরেকটা সেই একই register-এ নতুন কিছু লিখতে চায় (WAR) — এগুলো সত্যিকারের data dependency না, শুধু নাম পুনর্ব্যবহারের কাকতাল। পরের লেসনে (register-renaming-reorder-buffer) আমরা দেখব কীভাবে এই “মিথ্যা” dependency ভাঙা হয়, আর কীভাবে out-of-order-এ execute হওয়া ফলাফলগুলোকে আবার সঠিক program-order-এ “commit” দেখানো হয় — যা এই লেসন ইচ্ছাকৃতভাবে খোলা রাখল।

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

EXPERIMENT

একটা instruction sequence-এ dependency graph নিজে আঁকুন

কাগজ-কলম, অথবা Python· ১৫ মিনিট

instructions = [
    ("LOAD",  "R1", None, "addr1"),
    ("ADD",   "R2", "R3", "R4"),
    ("SUB",   "R5", "R6", "R7"),
    ("MUL",   "R8", "R1", "R9"),
    ("ADD",   "R9", "R2", "R5"),
]

def find_dependencies(instrs):
    deps = []
    writes = {}   # register -> কোন instruction সবশেষ লিখেছে
    for i, (op, dst, *srcs) in enumerate(instrs):
        for s in srcs:
            if s in writes:
                deps.append((writes[s], i, s))   # (আগেরটা, এইটা, কোন register)
        writes[dst] = i
    return deps

for producer, consumer, reg in find_dependencies(instructions):
    print(f"instruction {consumer} নির্ভরশীল instruction {producer}-এর উপর ({reg}-এর জন্য)")

প্রত্যাশিত output:

instruction 3 নির্ভরশীল instruction 0-এর উপর (R1-এর জন্য)
instruction 4 নির্ভরশীল instruction 1-এর উপর (R2-এর জন্য)
instruction 4 নির্ভরশীল instruction 2-এর উপর (R5-এর জন্য)

Instruction ১ (ADD) আর ২ (SUB) কোনো dependency ছাড়াই — এই দুইটা সম্পূর্ণ স্বাধীন, একই cycle-এ (superscalar) বা যেকোনো ক্রমে (out-of-order) চলতে পারে। Instruction ৪ (MUL) instruction ০-এর (LOAD) অপেক্ষায় থাকতে বাধ্য — কিন্তু সেই অপেক্ষার সময়ও ১ ও ২ এগিয়ে যেতে পারে।

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

একই কোড ব্লকেও কোন instruction একে অপরের সাথে সমান্তরালে চলতে পারে তা systematic ভাবে বের করা সম্ভব — এটাই hardware-এর dependency-tracking logic যা করে।

নিজে বানান

BUILD IT

একটা সরল Out-of-Order Issue Simulator

Python · ●●●●○

উপরের dependency-finder পুনর্ব্যবহার করুন
প্রতিটা instruction-কে একটা latency দিন (LOAD=200, MUL=5, বাকিগুলো=1)
একটা in-order simulator লিখুন — instruction ঠিক ক্রমে issue হয়, dependency থাকলে সম্পূর্ণ pipeline stall
একটা out-of-order simulator লিখুন — যেকোনো cycle-এ যেসব instruction-এর সব dependency মিটেছে তাদের execute করুন (readiness list বজায় রেখে)
দুইটার মোট completion time তুলনা করুন — একটা ভারী LOAD-সহ sequence-এ পার্থক্য কত বড়?

এই simulator-টাই এই লেসনের কেন্দ্রীয় দাবি সরাসরি সংখ্যায় প্রমাণ করবে — একটা একক ধীর LOAD কীভাবে in-order execution-এ পুরো pipeline-কে আটকে রাখে, যেখানে out-of-order-এ শুধু সেই একটা instruction (আর তার সত্যিকারের নির্ভরশীলরা) অপেক্ষা করে, বাকি সব এগিয়ে যায়।

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

Superscalar ও Out-of-Order যেখানে সত্যিকারের CPU-তে

CDC 6600 (১৯৬৪) — প্রথম বাস্তব out-of-order machine, James Thornton-এর scoreboard ডিজাইন। তখনকার সবচেয়ে দ্রুত কম্পিউটার, Seymour Cray-র ডিজাইন।
আধুনিক x86/ARM high-performance core — Intel Core, AMD Zen, Apple M-সিরিজ — সবগুলোই deeply out-of-order, ৪-৮ instruction পর্যন্ত superscalar width, শত শত instruction “in-flight” (একসাথে বিভিন্ন পর্যায়ে) থাকতে পারে।
In-order CPU এখনও প্রাসঙ্গিক — সব CPU out-of-order না। Power-সীমিত embedded/mobile core (ARM Cortex-A55-এর মতো “little” core big.LITTLE ডিজাইনে) ইচ্ছাকৃতভাবে in-order — কম hardware জটিলতা, কম power, কম performance-প্রতি-watt খরচ — যেখানে সর্বোচ্চ performance না, battery life গুরুত্বপূর্ণ।
Instruction Level Parallelism (ILP)-এর সীমা — কোনো প্রোগ্রামেই সীমাহীন ILP নেই (Amdahl-এর মতো যুক্তি, Level 11-এ বিস্তারিত) — একটা নির্দিষ্ট বিন্দুর পর বেশি superscalar width বা deeper out-of-order window বাস্তব প্রোগ্রামে diminishing return দেয়, কারণ true dependency chain নিজেই একটা সীমা তৈরি করে।
Meltdown vulnerability (২০১৮) — out-of-order execution-এর একটা নিরাপত্তা পরিণতি: speculatively execute হওয়া (কিন্তু পরে বাতিল হওয়া) instruction-ও ক্ষণস্থায়ী cache-effect রেখে যেতে পারে, যা থেকে privileged memory-র তথ্য leak করা সম্ভব হয়েছিল — Level 10-এ বিস্তারিত।

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

“Out-of-order execution মানে প্রোগ্রামের ফলাফলও এলোমেলো ক্রমে আসতে পারে।”

সম্পূর্ণ ভুল, আর এটাই সবচেয়ে গুরুত্বপূর্ণ ভুল-ধারণা। Out-of-order শুধু ভেতরের execution ক্রম বদলায় — চূড়ান্ত, দৃশ্যমান ফলাফল (register/memory-এর শেষ অবস্থা, exception যদি ঘটে) সবসময় এমনভাবে উপস্থাপন করা হয় যেন প্রোগ্রাম ঠিক লেখা ক্রমেই চলেছে। এই গ্যারান্টির নাম program order semantics, আর এটা বজায় রাখাই পরের লেসনের reorder buffer-এর কাজ। প্রোগ্রামার/কম্পাইলারের কাছে CPU সবসময় in-order-এর মতোই “আচরণ” করে, ভেতরে যতই সমান্তরাল/এলোমেলো কাজ চলুক না কেন।

“বেশি superscalar width (একসাথে বেশি instruction) সবসময় সমানুপাতিক বেশি speed দেয়।”

বাস্তব প্রোগ্রামে true dependency chain (এক instruction আরেকটার ফলাফলের অপেক্ষায়) একটা কঠিন সীমা তৈরি করে — এটা asymptotic-notation লেসনের “তত্ত্ব বনাম বাস্তবতা” থিমের আরেকটা উদাহরণ। যদি গড়ে একটা প্রোগ্রামে প্রতি ৩টা instruction-এ মাত্র ২টা সত্যিকারের স্বাধীন, ৮-wide superscalar hardware-ও কার্যত ২-৩ গুণের বেশি লাভ দিতে পারবে না — বাকি hardware অলস বসে থাকবে (dependency-এর অপেক্ষায়)। এই কারণেই real-world CPU benchmark-এ superscalar width বাড়ানো একটা নির্দিষ্ট বিন্দুর পর ক্রমশ কম লাভজনক হয়ে ওঠে।

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

নিচের instruction sequence-এ কোন জোড়াগুলো একই cycle-এ (2-wide superscalar-এ) একসাথে issue হতে পারে?

1: ADD  R1, R2, R3
2: SUB  R4, R2, R3
3: MUL  R5, R1, R4
4: ADD  R6, R7, R8

প্রয়োগ

নির্ভরতা বিশ্লেষণ:

Instruction ১ ও ২: দুইটাই R2, R3 পড়ে, কেউ কারো output-এর উপর নির্ভর করে না → স্বাধীন
Instruction ৩: R1 (instr ১) ও R4 (instr ২) দুইটার উপরই নির্ভরশীল → ১ ও ২ দুইটাই শেষ হওয়ার আগে চলতে পারবে না
Instruction ৪: R7, R8 — সম্পূর্ণ ভিন্ন register, কারো সাথে সম্পর্ক নেই → সম্পূর্ণ স্বাধীন, যেকোনো সময় চলতে পারে

সম্ভাব্য জোড়া: (১, ২) একসাথে issue হতে পারে (cycle ১)। এরপরের cycle-এ (৩) চলতে পারে (১, ২ শেষ হওয়ার পর), আর (৪) — যেহেতু ৪ সম্পূর্ণ স্বাধীন — যেকোনো cycle-এ, এমনকি (১, ২)-এর সাথেও যদি hardware-এ তৃতীয় execution unit থাকে, অথবা (৩)-এর সাথে যদি 2-wide-ই সীমা হয়।

2-wide-এ সবচেয়ে ভালো schedule: Cycle ১: (১, ২)। Cycle ২: (৩, ৪)। মোট ২ cycle — in-order হলে ৪ cycle লাগত (প্রতি cycle-এ একটা)।

একজন বলছে “যেহেতু out-of-order execution independent instruction-কে আগে চালায়, dependency chain-এর length (একটার পর একটা সত্যিকারের নির্ভরশীল instruction-এর সারি) আর কোনো গুরুত্ব রাখে না।” এই দাবি ভুল কেন?

যুক্তি

ভুল — dependency chain এখনও একটা কঠিন নিম্নসীমা তৈরি করে, out-of-order সত্ত্বেও।

Out-of-order শুধু স্বাধীন instruction-কে সমান্তরালে চালাতে পারে — যদি instruction A, B, C, D একটা chain হয় (B নির্ভর A-র উপর, C নির্ভর B-র উপর, D নির্ভর C-র উপর), এদের কোনোভাবেই সমান্তরালে চালানো যায় না, কারণ প্রতিটাই আসল data dependency দিয়ে আগেরটার সাথে বাঁধা। এই chain-টা যত দীর্ঘ, ন্যূনতম সম্পূর্ণ হওয়ার সময় তত বেশি — যতই superscalar width বা out-of-order window বড় হোক না কেন।

$\text{ন্যূনতম সম্ভাব্য সময়} \geq \text{দীর্ঘতম dependency chain-এর length}$

এটা ঠিক mathematics/asymptotic-notation-এর critical-path চিন্তাধারার সমান্তরাল — parallelism critical path-কে ছোট করতে পারে না, শুধু non-critical কাজকে সমান্তরালে সরিয়ে ফেলতে পারে। এই কারণেই compiler optimization-এ “dependency chain ছোট করা” (যেমন associativity ব্যবহার করে একটা লম্বা যোগের chain-কে একটা balanced tree-তে পুনর্বিন্যাস করা) একটা বাস্তব, গুরুত্বপূর্ণ কৌশল — হার্ডওয়্যার যতই স্মার্ট হোক, algorithm-এর গঠনগত সীমা অতিক্রম করতে পারে না।

একটা low-power, battery-চালিত IoT ডিভাইসের জন্য CPU ডিজাইন করছেন, যেখানে ব্যাটারি লাইফ সবচেয়ে গুরুত্বপূর্ণ, raw performance কম গুরুত্বপূর্ণ। In-order না out-of-order ডিজাইন বাছবেন, আর কেন?

ডিজাইন

In-order — power-সীমিত প্রেক্ষাপটে প্রায় সবসময় সঠিক পছন্দ।

Out-of-order execution-এর জন্য যথেষ্ট বাড়তি hardware লাগে: dependency tracking logic (scoreboard বা তার আধুনিক সংস্করণ), একটা বড় instruction window (অনেক instruction একসাথে “in-flight” রাখার বাফার), আর পরের লেসনের register renaming/reorder buffer hardware। এই সবকিছুই transistor, এলাকা, আর — সবচেয়ে গুরুত্বপূর্ণ এই প্রেক্ষাপটে — স্থির (static) power খরচ করে, এমনকি যখন CPU তেমন কিছু করছে না তখনও (leakage current, digital-logic/what-is-a-transistor লেসনের scaling আলোচনার সরাসরি প্রাসঙ্গিকতা)।

IoT workload প্রায়ই simple, predictable, আর ILP কম (sensor read, সাধারণ গণনা, পাঠানো) — out-of-order-এর জটিলতার বিনিময়ে যে performance লাভ পাওয়া যেত, সেটা এই workload-এ কার্যকর হওয়ার সুযোগই কম, অথচ power খরচ নিশ্চিতভাবে বেশি।

বাস্তব উদাহরণ: ARM Cortex-M সিরিজ (microcontroller-focused, in-order, খুবই কম power) এই ঠিক কারণেই ব্যাপকভাবে ব্যবহৃত হয় IoT/embedded-এ, যেখানে ARM Cortex-A সিরিজ (out-of-order, বেশি performance, বেশি power) smartphone/laptop-এ ব্যবহৃত হয় — একই কোম্পানি, ভিন্ন workload-এর জন্য সচেতনভাবে ভিন্ন design point।

এরপর কী

আমরা দেখেছি out-of-order execution কীভাবে কাজ করে যেতে পারে — কিন্তু ইচ্ছাকৃতভাবে একটা প্রশ্ন এড়িয়ে গেছি: WAR আর WAW-এর মতো “মিথ্যা” dependency (সত্যিকারের data flow না, শুধু register নামের পুনর্ব্যবহার) কীভাবে ভাঙা হয়? আর execution এলোমেলো ক্রমে হলেও কীভাবে নিশ্চিত করা হয় যে চূড়ান্ত ফলাফল ঠিক program order-এই “ঘটেছে” বলে প্রতীয়মান হয়?

পরের লেসনে এই দুই প্রশ্নেরই সুনির্দিষ্ট হার্ডওয়্যার সমাধান দেখব — register renaming (মিথ্যা dependency ভাঙার কৌশল) আর reorder buffer (এলোমেলো execution-কে সাজানো commit-এ ফেরানোর কৌশল), যা একসাথে আধুনিক out-of-order CPU-র সত্যিকারের ইঞ্জিন গঠন করে।

Superscalar ও Out-of-Order Execution — যখন ক্রম নিজেই আলোচনার বিষয়

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

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

আগে এটা বুঝি

মূল ধারণা

Superscalar — সমান্তরাল Instruction, সমান্তরাল Hardware

ভেতরে কী ঘটছে

In-Order-এর সীমা — যেখানে Out-of-Order জন্ম নেয়

উদাহরণ

Dependency Tracking — সমস্যার একটা আভাস

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

একটা instruction sequence-এ dependency graph নিজে আঁকুন

নিজে বানান

একটা সরল Out-of-Order Issue Simulator

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

Superscalar ও Out-of-Order যেখানে সত্যিকারের CPU-তে

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

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

এরপর কী

আরও পড়ুন

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

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

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

◆মূল ধারণাCore concept

Superscalar — সমান্তরাল Instruction, সমান্তরাল Hardware

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

In-Order-এর সীমা — যেখানে Out-of-Order জন্ম নেয়

▶উদাহরণExample

Dependency Tracking — সমস্যার একটা আভাস

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

একটা instruction sequence-এ dependency graph নিজে আঁকুন

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

একটা সরল Out-of-Order Issue Simulator

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

Superscalar ও Out-of-Order যেখানে সত্যিকারের CPU-তে

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

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

→এরপর কীNext step

আরও পড়ুন

আগে এটা বুঝি

মূল ধারণা

ভেতরে কী ঘটছে

উদাহরণ

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

নিজে বানান

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

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

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

এরপর কী