ALU নকশা — যোগ, বিয়োগ, লজিক আর flag

১ · ALU কী করে — CPU-র ক্যালকুলেটর আর তার interface

পর্ব ০১-এ (fetch–decode–execute চক্র) দেখেছেন, CPU বারবার তিনটি কাজ করে: মেমরি থেকে instruction আনে, সেটি বোঝে, তারপর কাজটি করে। এই “কাজটি করা” ধাপের বেশিরভাগ হিসাব যে অংশে হয়, তার নাম ALU — Arithmetic Logic Unit. add, sub, and, or, তুলনা — সবই ALU-র কাজ। এমনকি load বা store instruction-এও মেমরির ঠিকানা (base + offset) যোগ করে ALU.

ALU-র interface (বাইরের সংযোগ) মনে রাখুন এভাবে:

একটি গুরুত্বপূর্ণ কথা: ALU একটি combinational circuit — এতে কোনো মেমরি নেই, ঘড়ির (clock) অপেক্ষাও নেই। ইনপুট বদলালে কিছুক্ষণ পরে (gate-গুলোর delay পেরিয়ে) আউটপুট আপনা থেকে বদলে যায়। ফল ধরে রাখার কাজ register-এর, যা মডিউল ৩-এ আসবে। আর পুরো CPU-তে ALU কোথায় বসে, register file আর মেমরির সাথে কীভাবে জোড়া থাকে — সেই datapath দেখবেন পর্ব ৩২ আর ৩৩-এ।

২ · ১-বিটের ALU slice — AND, OR আর full adder, mux দিয়ে বাছাই

৩২-বিটের ALU সরাসরি আঁকা কঠিন। Patterson ও Hennessy-র পাঠ্যবইয়ের বিখ্যাত পদ্ধতি হলো আগে এক বিটের একটি ALU বানানো — একে বলে ALU slice বা bit-slice — তারপর সেটির ৩২টি কপি পাশাপাশি বসানো। গার্মেন্টস কারখানার লাইনে যেমন একই রকম অনেকগুলো মেশিন পাশাপাশি থাকে, প্রতিটি একটি করে অংশ সেলাই করে, এখানেও প্রতিটি slice একটি করে বিট সামলায়।

বিট i-এর slice-এ ইনপুট a_i, b_i আর ডান পাশের slice থেকে আসা CarryIn. ভেতরে তিনটি অংশ:

• AND gate: a_i · b_i
• OR gate: a_i + b_i (এই পর্বে Boolean-এ + মানে OR, ⊕ মানে XOR, আর A′ মানে NOT A; কোডে ~, |, ^)
• Full adder: sum = a ⊕ b ⊕ c_in, CarryOut = a·b + a·c_in + b·c_in — এর gate-স্তরের নকশা পর্ব ১১-এ (Adder)

তিনটির আউটপুট যায় একটি mux-এ। Mux-এর select লাইন হলো ২-বিটের Operation সংকেত: 00 হলে AND, 01 হলে OR, 10 হলে adder-এর sum. (Mux কীভাবে বানানো হয়, তা পর্ব ১২-এ — Multiplexer, decoder আর encoder.) পুরো slice-টি, পরের দুই অংশের বাড়তি অংশসহ, এক ছবিতে:

 Ainvert ─┐                      Operation (2 bits)
          ▼                               │
 a ──►[ a or a' ]──┬──►[ AND ]──► 0 ┐     ▼
                   │                ├──[ 4:1 ]──► Result
 b ──►[ b or b' ]──┼──►[ OR  ]──► 1 ┤  [ MUX ]
          ▲        │                │
 Binvert ─┘        └──►[ FULL ]──► 2 ┤
                CarryIn ─►[ADDER]   │
                           │  Less ► 3 ┘
                           ▼
                        CarryOut

এখনো এই slice শুধু তিনটি কাজ জানে: AND, OR আর যোগ। পরের দুটি অংশে মাত্র তিনটি ছোট সংযোজনে আমরা পাব বিয়োগ, NOR আর তুলনা।

৩ · বিয়োগ বিনা খরচে — Binvert আর CarryIn = 1

পর্ব ০৫-এ (two's complement) দেখেছেন, −B = B′ + 1, অর্থাৎ সব বিট উল্টে ১ যোগ করলে B-এর ঋণাত্মক পাওয়া যায়। তাহলে

এটি hardware-এ কতটা সস্তা, দেখুন। B′ পেতে প্রতিটি slice-এর b ইনপুটে একটি XOR gate বসানো হয়: b ⊕ Binvert. Binvert = 0 হলে b যেমন আছে তেমন যায়, Binvert = 1 হলে উল্টে যায়। আর “+ 1”? Adder-এর একদম ডানের slice (বিট ০)-এর একটি CarryIn ইনপুট আছে, যা যোগের সময় এমনিতেই ০ থাকে। সেখানে ১ দিলেই +1 হয়ে গেল — একটি বাড়তি adder-ও লাগল না।

তাই Patterson–Hennessy-র নকশায় একটিই সংকেত দুই জায়গায় যায়: Bnegate = সব slice-এর Binvert + বিট ০-এর CarryIn. Bnegate = 1 মানে “B-কে negate করা হবে”। বীজগণিতে যাচাই (n বিটে, mod 2ⁿ):

এখান থেকে একটি বাড়তি তথ্যও বেরোয়, যা অংশ ৬-এ খুব কাজে লাগবে: যোগফল 2ⁿ + (A − B). A ≥ B (unsigned) হলে এটি 2ⁿ-এর সমান বা বেশি, তাই MSB থেকে carry বেরোয় (CarryOut = 1). A < B হলে যোগফল 2ⁿ-এর কম, carry বেরোয় না (CarryOut = 0) — অর্থাৎ বিয়োগে borrow লেগেছে। বিয়োগের পর CarryOut = NOT borrow.

নিচের stepper-এ ৪-বিটের ALU-তে 5 − 3 ধাপে ধাপে চলছে। “পরে” চাপুন:

A        = 0101   (5)
B        = 0011   (3)
Ainvert  = 0
Bnegate  = 1   -> every Binvert = 1, CarryIn(bit 0) = 1
Operation= 10  -> mux picks the adder's sum

bit        3 2 1 0
b          0 0 1 1
b xor 1    1 1 0 0   = B' (one's complement of 3)
CarryIn(0) = 1

bit        3 2 1 0
carry-in   . . . 1
a          0 1 0 1
b'         1 1 0 0
result     . . . 0   carry to bit 1 = 1

bit        3 2 1 0
carry-in   . . 1 1
a          0 1 0 1
b'         1 1 0 0
result     . . 1 0   carry to bit 2 = 0

bit        3 2 1 0
carry-in   . 0 1 1
a          0 1 0 1
b'         1 1 0 0
result     . 0 1 0   carry to bit 3 = 1

bit        3 2 1 0
carry-in   1 0 1 1
a          0 1 0 1
b'         1 1 0 0
result     0 0 1 0   = 2     CarryOut = 1
V = Cin(bit3) xor Cout = 1 xor 1 = 0

৪ · Ainvert, NOR আর set-on-less-than — overflow-এর সূক্ষ্ম ফাঁদ

Ainvert দিয়ে NOR

B-এর মতো A-এর ইনপুটেও একটি XOR (বা ২:১ mux) বসানো হয়, যার সংকেতের নাম Ainvert. কেন? De Morgan-এর সূত্র (পর্ব ০৭) মনে করুন: (A + B)′ = A′ · B′. অর্থাৎ A আর B দুটিকেই উল্টে AND করলে পাওয়া যায় NOR. তাই Ainvert = 1, Bnegate = 1 আর Operation = 00 (AND) দিলে ALU NOR করে — নতুন কোনো gate ছাড়াই। একই কৌশলে Ainvert = 1, Binvert = 1, Operation = 01 (OR) দিলে পাওয়া যায় A′ + B′ = (A·B)′, অর্থাৎ NAND. (Bnegate একই সাথে CarryIn-এও ১ দেয়, কিন্তু AND বা OR বেছে নিলে adder-এর ফল mux-এ বাদ পড়ে, তাই এতে ক্ষতি নেই।)

Set-on-less-than — তুলনার ফল একটি সংখ্যা হিসেবে

MIPS আর RISC-V-তে একটি instruction আছে slt rd, rs1, rs2 — set-on-less-than: rs1 < rs2 (signed) হলে rd = 1, নাহলে rd = 0. এর ফল সবসময় 0000…0001 বা 0000…0000. অর্থাৎ উপরের ৩১টি বিট সবসময় ০, শুধু বিট ০-এ তুলনার উত্তর।

এটি ALU-তে বানানোর কৌশল চমৎকার। Mux-এর চতুর্থ ইনপুট (Operation = 11) হলো Less. বিট ১ থেকে ৩১-এর slice-এ Less-এ সরাসরি ০ বাঁধা থাকে। বিট ০-এর Less আসে MSB-র slice থেকে একটি তারে, যার নাম Set. আর ALU সেই সময় ভেতরে A − B হিসাব করে (Bnegate = 1). ভাবনাটা সরল: A < B হলে A − B ঋণাত্মক, তাই ফলের চিহ্ন-বিট (MSB) ১ — এটাই Set. সুতরাং slt-এর control: Ainvert 0, Bnegate 1, Operation 11 → 0111.

সঠিক নিয়ম: SLT = N ⊕ V — প্রমাণ

ধরুন n বিটের adder A − B-এর যে ফল দেয় তার চিহ্ন-বিট N, আর signed overflow flag V. আসল (অসীম নির্ভুল) পার্থক্য D = A − B. আমরা চাই: D < 0 হলে ১.

• V = 0 হলে: D সীমার ভেতরে, তাই adder-এর ফলই D-এর সঠিক two's complement রূপ। তখন D < 0 ⇔ N = 1. অর্থাৎ উত্তর = N = N ⊕ 0.
• V = 1 হলে: D সীমার বাইরে। পর্ব ০৫-এ দেখেছেন, overflow হয় কেবল তখনই যখন ফল ঠিক এক “পাক” (2ⁿ) ঘুরে উল্টো চিহ্নের অর্ধেকে পড়ে — তাই ফলের চিহ্ন আসল চিহ্নের ঠিক উল্টো। উত্তর = N′ = N ⊕ 1.

দুই ক্ষেত্র মিলিয়ে Less = N ⊕ V. Hardware-এ খরচ মাত্র একটি XOR gate: MSB slice-এর Set = sum_n−1 ⊕ V, আর V আসে V = c_n ⊕ c_n−1 থেকে (c_n = MSB থেকে বেরোনো carry, c_n−1 = MSB-তে ঢোকা carry). ARM আর x86-এর “signed less than” শর্তও ঠিক এটাই: N ≠ V (x86-এ SF ≠ OF) — অংশ ৭-এ আবার আসবে।

A  = 1000 0000   (-128)
B  = 0000 0001   (+1)
ALU computes A + B' + 1 inside

   1000 0000     A
 + 1111 1110     B'
 +         1     CarryIn
 -----------
 1 0111 1111     sum = +127 (wrapped), CarryOut = 1

carry into bit 7  c7 = 0
carry out of bit 7 c8 = 1
V = c8 xor c7 = 1     (overflow!)
N = sum bit 7  = 0

naive  Set = N       = 0   -> result 0000 0000  (WRONG)
correct Set = N xor V = 0 xor 1 = 1
result = 0000 0001   (-128 < 1 is true)

Unsigned তুলনা — sltu

RISC-V-তে sltu (set-on-less-than unsigned) দুটি সংখ্যাকে unsigned হিসেবে তুলনা করে। অংশ ৩-এর হিসাব মনে করুন: A + B′ + 1-এর CarryOut = 1 ঠিক তখনই, যখন A ≥ B (unsigned). তাই sltu-এর ফল = NOT CarryOut — অর্থাৎ borrow লেগেছে কি না। চিহ্ন-বিট বা V এখানে অপ্রাসঙ্গিক। একই বিট-প্যাটার্নে দুটি তুলনা ভিন্ন উত্তর দিতে পারে: ৮ বিটে 1111 1111 আর 0000 0001 — signed-এ −1 < 1 সত্য, unsigned-এ 255 < 1 মিথ্যা।

৫ · ৩২টি slice জুড়ে ৩২-বিট ALU আর ALU control-এর টেবিল

এবার slice-গুলো জোড়া যাক। বিট i-এর CarryOut যায় বিট i + 1-এর CarryIn-এ, ঠিক পর্ব ১১-এর ripple carry adder-এর মতো। সব slice-এর Ainvert একটি তারে, সব Binvert আরেকটি তারে (যা বিট ০-এর CarryIn-ও), আর Operation-এর দুটি তার সব slice-এ একসাথে যায়। শেষ slice (বিট ৩১) একটু বিশেষ: এতে বাড়তি থাকে Set আউটপুট আর overflow নির্ণয়ের gate.

Ainvert  Bnegate  Operation   (each goes to all 32 slices)
   │        │        │
 a0,b0 ─►[ ALU0  ]◄─ CarryIn = Bnegate     Less0 ◄── Set (from ALU31)
            │ c1                           ──► Result0
 a1,b1 ─►[ ALU1  ]    Less1 = 0            ──► Result1
            │ c2
   ...      ...       (carry ripples upward)
            │ c31
 a31,b31►[ ALU31 ]    Less31 = 0           ──► Result31
            │ c32       Set = sum31 xor V,  Overflow V = c32 xor c31
            ▼
         CarryOut
 Zero = NOR(Result31 ... Result0)

সমস্যা একটিই: গতি। CarryIn থেকে ফল পেতে carry-কে ৩২টি slice পেরোতে হয়। প্রতিটি full adder-এর carry পথে মোটামুটি দুই স্তর gate থাকলে সবচেয়ে খারাপ ক্ষেত্রে প্রায় ৬৪ স্তরের delay, তারপর mux আর Set-এর পথ। বাস্তব CPU তাই ripple ব্যবহার করে না; ব্যবহার করে carry-lookahead বা parallel-prefix adder, যেখানে carry প্রায় log₂ n স্তরে হিসাব হয় — বিস্তারিত পর্ব ১১-এ। ALU-র বাকি গঠন একই থাকে; শুধু adder অংশটি দ্রুত adder দিয়ে বদলানো হয়।

ALU control-এর টেবিল

চারটি control বিট (Ainvert, Bnegate, Operation₁, Operation₀) একসাথে একটি ৪-বিটের কোড। Patterson–Hennessy-র MIPS সংস্করণে এই কোডগুলোই ব্যবহার হয়, আর বিশ্ববিদ্যালয় ও চাকরির পরীক্ষায় এই টেবিল বারবার আসে:

নিচের simulator এই পুরো নকশাটি ৮ বিটে চালায়: প্রতিটি slice-এ দুটি XOR, AND, OR, full adder আর mux; প্রথমে carry chain চলে, তারপর MSB থেকে Set = sum₇ ⊕ V নিয়ে বিট ০-এর Less-এ দেওয়া হয়। তিন জোড়া operand-এ ছয়টি কাজ — Run চাপুন, তারপর নিজের সংখ্যা বসিয়ে দেখুন:

// 8-bit ripple ALU built from 1-bit slices (Patterson-Hennessy style).
// control = Ainvert, Bnegate, Operation (00 AND, 01 OR, 10 add, 11 less)
const OPS = { AND: "0000", OR: "0001", add: "0010", sub: "0110", slt: "0111", NOR: "1100" };
function slice(a, b, cin, less, ainv, bneg, op) {
  const x = a ^ ainv, y = b ^ bneg;               // the two inverters (XOR)
  const sum = x ^ y ^ cin, cout = (x & y) | (x & cin) | (y & cin);
  return { r: [x & y, x | y, sum, less][op], sum, cout };
}
function alu8(A, B, ctrl) {
  const ainv = +ctrl[0], bneg = +ctrl[1], op = parseInt(ctrl.slice(2), 2);
  let c = bneg, cins = [], sum7 = 0, res = [];   // CarryIn of bit 0 = Bnegate
  for (let i = 0; i < 8; i++) {                   // pass 1: the carry chain
    cins.push(c);
    const s = slice((A >> i) & 1, (B >> i) & 1, c, 0, ainv, bneg, op);
    sum7 = s.sum; c = s.cout;
  }
  const V = cins[7] ^ c, set = sum7 ^ V;          // corrected SLT bit
  for (let i = 0; i < 8; i++)                     // pass 2: mux picks result
    res.push(slice((A >> i) & 1, (B >> i) & 1, cins[i], i === 0 ? set : 0,
                   ainv, bneg, op).r);
  const R = res.reduce((v, bit, i) => v | (bit << i), 0);
  return { R, Z: +(R === 0), N: R >> 7, C: c, V, naive: sum7 };
}
const s8 = p => (p & 0x80 ? p - 256 : p), b8 = p => p.toString(2).padStart(8, "0");
for (const [x, y] of [[100, 50], [-128, 1], [5, 5]]) {
  console.log(`A=${x} (${b8(x & 255)})  B=${y} (${b8(y & 255)})`);
  for (const [name, ctrl] of Object.entries(OPS)) {
    const { R, Z, N, C, V, naive } = alu8(x & 255, y & 255, ctrl);
    const cv = ctrl[2] === "1" ? `C=${C} V=${V}` : "C=- V=-";  // adder ops only
    const note = name === "slt" ? `  naive sign bit=${naive}` : "";
    console.log(`  ${name.padEnd(3)} ${ctrl}  ${b8(R)} = ${String(s8(R)).padStart(4)}  Z=${Z} N=${N} ${cv}${note}`);
  }
}

A=100 (01100100)  B=50 (00110010)
  AND 0000  00100000 =   32  Z=0 N=0 C=- V=-
  OR  0001  01110110 =  118  Z=0 N=0 C=- V=-
  add 0010  10010110 = -106  Z=0 N=1 C=0 V=1
  sub 0110  00110010 =   50  Z=0 N=0 C=1 V=0
  slt 0111  00000000 =    0  Z=1 N=0 C=1 V=0  naive sign bit=0
  NOR 1100  10001001 = -119  Z=0 N=1 C=- V=-
A=-128 (10000000)  B=1 (00000001)
  AND 0000  00000000 =    0  Z=1 N=0 C=- V=-
  OR  0001  10000001 = -127  Z=0 N=1 C=- V=-
  add 0010  10000001 = -127  Z=0 N=1 C=0 V=0
  sub 0110  01111111 =  127  Z=0 N=0 C=1 V=1
  slt 0111  00000001 =    1  Z=0 N=0 C=1 V=1  naive sign bit=0
  NOR 1100  01111110 =  126  Z=0 N=0 C=- V=-
A=5 (00000101)  B=5 (00000101)
  AND 0000  00000101 =    5  Z=0 N=0 C=- V=-
  OR  0001  00000101 =    5  Z=0 N=0 C=- V=-
  add 0010  00001010 =   10  Z=0 N=0 C=0 V=0
  sub 0110  00000000 =    0  Z=1 N=0 C=1 V=0
  slt 0111  00000000 =    0  Z=1 N=0 C=1 V=0  naive sign bit=0
  NOR 1100  11111010 =   -6  Z=0 N=1 C=- V=-

৬ · Flag — Zero, Negative, Carry আর Overflow

ফলের পাশাপাশি ALU চারটি ১-বিটের তথ্য দেয়। ARM এদের একসাথে বলে NZCV; x86-এ নাম ZF, SF, CF, OF. এরা CPU-র একটি status flag register-এ জমা হতে পারে (x86, ARM), অথবা একদম না-ও জমতে পারে (RISC-V — অংশ ৭)। প্রতিটির circuit:

Z flag-এর circuit নিয়ে একটি কথা: ৩২টি বিটের NOR একটি বিশাল gate হিসেবে বানানো যায় না (CMOS-এ বেশি ইনপুটের gate ধীর, পর্ব ০৮)। তাই ২ বা ৪ ইনপুটের OR gate-এর একটি গাছ বানানো হয় — ৩২ বিটে ২-ইনপুট gate দিয়ে log₂ 32 = ৫ স্তর — শেষে একটি NOT. এবার একটি বিয়োগে চারটি flag একটি একটি করে তৈরি হতে দেখুন:

A  = 0111 0000   0x70  (unsigned 112, signed +112)
B  = 1001 0000   0x90  (unsigned 144, signed -112)
B' = 0110 1111
   0111 0000 + 0110 1111 + 1 = 1110 0000  (0xE0)
carries: c7 (into bit 7) = 1, c8 (out) = 0

result  1110 0000
OR of all bits = 1
Z = NOT 1 = 0      (result is not zero)

result  1110 0000
N = bit 7 = 1     (as signed: -32)

CarryOut c8 = 0
ARM  C  = 0   (0 = a borrow happened)
x86  CF = 1   (1 = a borrow happened)
unsigned check: 112 < 144, so a borrow is right

V = c8 xor c7 = 0 xor 1 = 1
signed check: 112 - (-112) = 224 > 127   -> overflow
result -32 is wrong as a signed answer

signed   A < B ?  N xor V = 1 xor 1 = 0  -> no  (112 > -112)
unsigned A < B ?  borrow (ARM C = 0)  = yes (112 < 144)

৭ · Flag দিয়ে শাখা — x86/ARM-এর condition code বনাম RISC-V-এর compare-and-branch

if (a < b) লিখলে CPU-কে দুটি কাজ করতে হয়: তুলনা আর শাখা (branch). x86 আর ARM-এ এই দুটি আলাদা instruction. প্রথমে cmp a, b — যা ভেতরে a − b হিসাব করে, ফল ফেলে দেয়, শুধু flag রাখে। তারপর একটি শর্তসাপেক্ষ লাফ, যা flag পড়ে সিদ্ধান্ত নেয়। শর্তগুলোকে বলে condition code:

লক্ষ করুন x86-এর নামকরণ: signed তুলনায় “less/greater” (jl, jg), unsigned-এ “below/above” (jb, ja). C কোডে int আর unsigned তুলনার জন্য compiler ঠিক এই দুই পরিবার থেকে instruction বাছে। নিচের simulator চারটি CMP চালিয়ে ছয়টি শর্ত হিসাব করে — দেখুন কোথায় signed আর unsigned উত্তর ভিন্ন হয়:

// CMP a, b = compute a - b, keep only the flags (ARM-style C = NOT borrow).
function cmp8(a, b) {
  const raw = a + ((~b) & 0xFF) + 1;              // a + ~b + 1
  const r = raw & 0xFF, C = raw >> 8;             // C = carry out = no borrow
  const sa = a >> 7, sb = b >> 7, sr = r >> 7;
  const V = +(sa !== sb && sr !== sa);            // signs differ, result flips
  return { r, Z: +(r === 0), N: sr, C, V };
}
const cond = {                                    // ARM name (x86 jump)
  "EQ (je)": f => f.Z === 1,
  "NE (jne)": f => f.Z === 0,
  "LT (jl)": f => f.N !== f.V,                    // signed less than
  "LO (jb)": f => f.C === 0,                      // unsigned lower = borrow
  "GT (jg)": f => f.Z === 0 && f.N === f.V,
  "HI (ja)": f => f.C === 1 && f.Z === 0,
};
const hex = v => "0x" + v.toString(16).toUpperCase().padStart(2, "0");
const pairs = [[0xFF, 0x01], [0x01, 0xFF], [0x80, 0x7F], [0x05, 0x05]];
for (const [a, b] of pairs) {
  const f = cmp8(a, b), sa = a > 127 ? a - 256 : a, sb = b > 127 ? b - 256 : b;
  console.log(`CMP ${hex(a)}, ${hex(b)}  (signed ${sa} vs ${sb}, unsigned ${a} vs ${b})`);
  console.log(`  a-b=${hex(f.r)}  Z=${f.Z} N=${f.N} C=${f.C} V=${f.V}  x86 CF=${1 - f.C}`);
  console.log("  " + Object.entries(cond).map(([k, t]) => `${k}:${t(f) ? "T" : "F"}`).join("  "));
}

CMP 0xFF, 0x01  (signed -1 vs 1, unsigned 255 vs 1)
  a-b=0xFE  Z=0 N=1 C=1 V=0  x86 CF=0
  EQ (je):F  NE (jne):T  LT (jl):T  LO (jb):F  GT (jg):F  HI (ja):T
CMP 0x01, 0xFF  (signed 1 vs -1, unsigned 1 vs 255)
  a-b=0x02  Z=0 N=0 C=0 V=0  x86 CF=1
  EQ (je):F  NE (jne):T  LT (jl):F  LO (jb):T  GT (jg):T  HI (ja):F
CMP 0x80, 0x7F  (signed -128 vs 127, unsigned 128 vs 127)
  a-b=0x01  Z=0 N=0 C=1 V=1  x86 CF=0
  EQ (je):F  NE (jne):T  LT (jl):T  LO (jb):F  GT (jg):F  HI (ja):T
CMP 0x05, 0x05  (signed 5 vs 5, unsigned 5 vs 5)
  a-b=0x00  Z=1 N=0 C=1 V=0  x86 CF=0
  EQ (je):T  NE (jne):F  LT (jl):F  LO (jb):F  GT (jg):F  HI (ja):F

RISC-V — flag ছাড়াই শাখা

RISC-V (আর তার আগে MIPS) ইচ্ছা করেই কোনো flag register রাখেনি। তুলনা আর শাখা একটি instruction-এ: beq, bne, blt, bge, bltu, bgeu — দুটি register সরাসরি তুলনা করে লাফ দেয়। এটাই compare-and-branch. আর তুলনার ফল সংখ্যা হিসেবে দরকার হলে slt/sltu, যার ফল একটি সাধারণ register-এ যায়।

উদাহরণ (হাতে লেখা, তুলনার জন্য; a ও b ৩২-বিট int, x86-64-এ Intel syntax-এ edi/esi, ARM64-এ w0/w1, RISC-V-তে x10/x11):

# if (a < b) goto L;
# x86-64              # ARM64              # RISC-V (RV32I)
cmp   edi, esi        cmp   w0, w1         blt   x10, x11, L
jl    L               b.lt  L
# unsigned a < b:
cmp   edi, esi        cmp   w0, w1         bltu  x10, x11, L
jb    L               b.lo  L

কেন flag বাদ? এতে প্রতিটি instruction-এর ফল শুধু তার গন্তব্য register-এ যায়, লুকোনো কোনো পার্শ্ব-ফল থাকে না — pipeline আর out-of-order CPU-তে নির্ভরতা খোঁজা সহজ হয় (পর্ব ৩৬, ৪০)। খরচও আছে: signed overflow জানতে বা বহু-শব্দের (multi-word) যোগে carry বের করতে বাড়তি instruction লাগে, যেমন যোগের পর sltu দিয়ে carry বের করা। শাখা ও লুপ assembly-তে কেমন দেখায়, তা পর্ব ২৯-এ বিস্তারিত।

৮ · Shifter — logical, arithmetic, rotate আর barrel shifter

বিট সরানো (shift) CPU-র সবচেয়ে বেশি ব্যবহৃত কাজগুলোর একটি: ২-এর ঘাতে গুণ-ভাগ, bitmask বানানো, field বের করা, আর পর্ব ২১-এর shift-add গুণে। তিন ধরনের shift, সাথে rotate:

• Left shift (sll): সব বিট বাঁয়ে, ডানে ০ ঢোকে; k ঘর মানে 2^k দিয়ে গুণ (বাঁয়ের বিট হারানো পর্যন্ত)।
• Logical right shift (srl): ডানে সরে, বাঁয়ে ০ ঢোকে — unsigned সংখ্যার 2^k দিয়ে ভাগ।
• Arithmetic right shift (sra): ডানে সরে, বাঁয়ে sign-বিটের কপি ঢোকে — signed সংখ্যার 2^k দিয়ে ভাগ, তবে নিচের দিকে গোল করে (floor): −74 >> 3 = −10, −9 নয়।
• Rotate: এক প্রান্ত দিয়ে বেরোনো বিট অন্য প্রান্তে ঢোকে, কিছু হারায় না। x86-এ rol/ror, ARM-এ ror; RV32I-এ নেই, তবে ঐচ্ছিক bit-manipulation extension (Zbb)-এ rol/ror আছে।

Barrel shifter — log₂ n স্তরের mux

সবচেয়ে সরল shifter প্রতি clock-এ এক ঘর সরায় (পর্ব ১৬-এর shift register) — ২৯ ঘর সরাতে ২৯ cycle. দ্রুত CPU-তে দরকার এক ধাপেই যেকোনো দূরত্ব। একটি উপায়: প্রতিটি আউটপুট বিটের জন্য একটি n:1 mux — n বিটে n টি বড় mux, তারের জঙ্গল। চতুর উপায় হলো barrel shifter: shift-এর পরিমাণকে binary-তে ভাঙুন। ৫ = 101₂ = 4 + 1. তাহলে “১ ঘর সরানো হবে কি না”, “২ ঘর সরানো হবে কি না”, “৪ ঘর সরানো হবে কি না” — তিনটি স্তর, প্রতিটি স্তরে n টি ২:১ mux, আর স্তর k-এর select হলো shift পরিমাণের বিট k.

Delay-ও মাত্র log₂ n স্তরের mux — ৩২ বিটে ৫টি। RV32I-এর sll/srl/sra shift পরিমাণের নিচের ৫টি বিটই শুধু দেখে (rs2-এর বিট ৪…০) — ঠিক পাঁচটি স্তরের select; x86-ও ৩২-বিট shift-এ count-কে ৫ বিটে mask করে। Arithmetic আর logical-এর পার্থক্য শুধু বাঁয়ে ঢোকা বিটে (sign না ০), আর left shift-এর জন্য হয় আলাদা স্তর, নয়তো ইনপুট-আউটপুটের বিটক্রম উল্টে একই right shifter ব্যবহার — দুটি কৌশলই প্রচলিত। নিচে ৮-বিটের sra 0xB6 by 5 তিন স্তরে:

x       = 1011 0110   (0xB6, signed -74)
shamt   = 5 = 101 (binary)
stage 1 (by 1): select = bit0 = 1
stage 2 (by 2): select = bit1 = 0
stage 3 (by 4): select = bit2 = 1

in      1011 0110
out     1101 1011   (shift by 1, fill = sign 1)

in      1101 1011
out     1101 1011   (pass: every mux picks its own bit)

in      1101 1011
out     1111 1101   (shift by 4, four sign bits enter)

result  1111 1101 = 0xFD = -3
check   -74 / 32 = -2.3125, floor = -3
srl 5 would give 0000 0101 = 5   (182 / 32 = 5.69 -> 5)

নিচের simulator তিন রকম shift (srl, sra, sll) ১, ৩ আর ৫ ঘরে চালায় এবং প্রতিটি স্তরের পরের মান ছাপে:

// 8-bit barrel shifter: 3 stages of 2:1 muxes (shift by 1, 2, 4).
// Stage k looks at bit k of the shift amount: 0 = pass, 1 = shift by 2^k.
const N = 8, b8 = v => v.toString(2).padStart(N, "0").replace(/(....)(....)/, "$1 $2");
function stage(x, dist, kind) {                   // one layer = 8 muxes
  let out = 0;
  for (let i = 0; i < N; i++) {                   // output bit i
    let bit;
    if (kind === "sll") bit = i - dist >= 0 ? (x >> (i - dist)) & 1 : 0;
    else if (i + dist < N) bit = (x >> (i + dist)) & 1;
    else bit = kind === "sra" ? (x >> (N - 1)) & 1 : 0;   // fill: sign or 0
    out |= bit << i;
  }
  return out;
}
function barrel(x, sh, kind) {
  let v = x; const trace = [];
  for (let k = 0; k < 3; k++) {                   // log2(8) = 3 stages
    const on = (sh >> k) & 1;
    if (on) v = stage(v, 1 << k, kind);
    trace.push(`s${1 << k}:${on ? "shift" : "pass "} ${b8(v)}`);
  }
  return { v, trace };
}
const x = 0xB6;                                   // 1011 0110 = 182 or -74
console.log(`input ${b8(x)} (unsigned ${x}, signed ${x - 256})`);
for (const kind of ["srl", "sra", "sll"])
  for (const sh of [1, 3, 5]) {
    const { v, trace } = barrel(x, sh, kind);
    const sv = v & 0x80 ? v - 256 : v;
    console.log(`${kind} ${sh} (${sh.toString(2).padStart(3, "0")}): ` +
                `${trace.join(" | ")} -> ${v} / ${sv}`);
  }

input 1011 0110 (unsigned 182, signed -74)
srl 1 (001): s1:shift 0101 1011 | s2:pass  0101 1011 | s4:pass  0101 1011 -> 91 / 91
srl 3 (011): s1:shift 0101 1011 | s2:shift 0001 0110 | s4:pass  0001 0110 -> 22 / 22
srl 5 (101): s1:shift 0101 1011 | s2:pass  0101 1011 | s4:shift 0000 0101 -> 5 / 5
sra 1 (001): s1:shift 1101 1011 | s2:pass  1101 1011 | s4:pass  1101 1011 -> 219 / -37
sra 3 (011): s1:shift 1101 1011 | s2:shift 1111 0110 | s4:pass  1111 0110 -> 246 / -10
sra 5 (101): s1:shift 1101 1011 | s2:pass  1101 1011 | s4:shift 1111 1101 -> 253 / -3
sll 1 (001): s1:shift 0110 1100 | s2:pass  0110 1100 | s4:pass  0110 1100 -> 108 / 108
sll 3 (011): s1:shift 0110 1100 | s2:shift 1011 0000 | s4:pass  1011 0000 -> 176 / -80
sll 5 (101): s1:shift 0110 1100 | s2:pass  0110 1100 | s4:shift 1100 0000 -> 192 / -64

৯ · তুলনা, যাচাই আর বাস্তবের ALU

সমান কি না — দুই পথ

A = B কি না জানার প্রথম পথ: A − B করে Z flag দেখা। এটি সহজ, কারণ ALU তো আছেই — কিন্তু পুরো carry chain পেরোতে হয়। দ্বিতীয় পথ দ্রুততর: প্রতিটি বিটে XNOR — (a_i ⊕ b_i)′, যা দুটি বিট সমান হলে ১ — তারপর সবগুলোর AND-এর গাছ। কোনো carry নেই, শুধু log₂ n স্তর। অনেক pipeline CPU-তে beq/bne-এর জন্য এমন আলাদা equality comparator রাখা হয়, যাতে শাখার সিদ্ধান্ত আগেভাগে নেওয়া যায় (পর্ব ৩৬–৩৭)।

পুরো নকশাটি C দিয়ে যাচাই — ৬৫,৫৩৬টি জোড়া

একটি নকশা কয়েকটি উদাহরণে ঠিক কাজ করলেই নিশ্চিত হওয়া যায় না। ৮ বিটে মোট জোড়া মাত্র 256 × 256 = ৬৫,৫৩৬টি, তাই সবগুলো পরীক্ষা করা যায় — একে বলে exhaustive testing. নিচের C প্রোগ্রাম gate-স্তরের ripple মডেলটিকে C-র নিজস্ব গণিতের সাথে মেলায়: ফল, C, V, আর slt (N ⊕ V) ও sltu (NOT C).

#include <stdio.h>
/* gate-level 8-bit ripple ALU: add when bneg = 0, sub when bneg = 1 */
static unsigned alu8(unsigned a, unsigned b, unsigned bneg, unsigned *C, unsigned *V) {
    unsigned c = bneg, r = 0, cin7 = 0;
    for (int i = 0; i < 8; i++) {
        unsigned x = (a >> i) & 1u, y = ((b >> i) & 1u) ^ bneg;
        if (i == 7) cin7 = c;
        r |= (x ^ y ^ c) << i;
        c = (x & y) | (x & c) | (y & c);
    }
    *C = c; *V = cin7 ^ c; return r;
}
static int s8(unsigned p) { return (int)(p ^ 0x80u) - 128; }   /* no UB */
static unsigned out8(int t) { return (unsigned)(t < -128 || t > 127); }

int main(void) {
    long bad_add = 0, bad_sub = 0, bad_slt = 0, bad_sltu = 0, naive_wrong = 0;
    for (unsigned a = 0; a < 256; a++) for (unsigned b = 0; b < 256; b++) {
        unsigned C, V, r = alu8(a, b, 0, &C, &V);
        if (r != ((a + b) & 0xFFu) || C != (unsigned)(a + b > 255u)
            || V != out8(s8(a) + s8(b))) bad_add++;
        r = alu8(a, b, 1, &C, &V);
        if (r != ((a - b) & 0xFFu) || C != (unsigned)(a >= b)
            || V != out8(s8(a) - s8(b))) bad_sub++;
        unsigned lt = (unsigned)(s8(a) < s8(b));
        if (((r >> 7) ^ V) != lt) bad_slt++;           /* SLT = N xor V */
        if ((r >> 7) != lt) naive_wrong++;             /* SLT = N only  */
        if ((C ^ 1u) != (unsigned)(a < b)) bad_sltu++; /* SLTU = NOT C  */
    }
    printf("pairs tested: %d\nadd mismatches: %ld, sub mismatches: %ld\n",
           256 * 256, bad_add, bad_sub);
    printf("slt (N xor V) mismatches: %ld\nsltu (NOT C) mismatches : %ld\n",
           bad_slt, bad_sltu);
    printf("naive slt (N only) wrong: %ld pairs\n", naive_wrong); return 0;
}

pairs tested: 65536
add mismatches: 0, sub mismatches: 0
slt (N xor V) mismatches: 0
sltu (NOT C) mismatches : 0
naive slt (N only) wrong: 16384 pairs

বাস্তবের ALU — অনেকগুলো execution unit

পাঠ্যবইয়ের CPU-তে একটি ALU. আধুনিক বড় core-এ কিন্তু একাধিক execution unit থাকে: কয়েকটি সরল integer ALU (প্রায়ই ৪ বা তার বেশি, যারা যোগ, লজিক, shift এক cycle-এ শেষ করে), আলাদা branch unit, আলাদা multiplier আর divider (গুণে কয়েক cycle, ভাগে আরও বেশি লাগে), load/store-এর ঠিকানা হিসাবের unit, আর floating-point ও SIMD unit. এক cycle-এ কয়েকটি instruction একসাথে আলাদা unit-এ পাঠানোর এই কৌশলই superscalar নকশা — পর্ব ৩৯-এ। রেস্তোরাঁর রান্নাঘরের মতো: একজন বাবুর্চি সব না করে আলাদা চুলা — ভাজা, তন্দুর, চা — একসাথে চলে।

১০ · AI-এর যুগে ALU নকশা

AI টুল ALU-র ছবি আর সংজ্ঞা সুন্দরভাবে বলতে পারে, কিন্তু ঠিক সেই কোণগুলোতে ভুল করে যেখানে hardware বাগ লুকিয়ে থাকে। প্রচলিত কয়েকটি ভুল:

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

• Width আর ISA (MIPS, RISC-V, x86, ARM) স্পষ্ট বলা আছে; MIPS-এর নিয়ম RISC-V-র নামে চালানো হয়নি
• অন্তত একটি বিয়োগ বিট ধরে কাগজে করেছি — B′, CarryIn = 1, প্রতিটি carry
• সীমানার মান দিয়ে পরীক্ষা করেছি: 0, −1, সর্বোচ্চ (0x7F), সর্বনিম্ন (0x80), সমান দুটি সংখ্যা
• slt-এ overflow-এর ক্ষেত্র (−128 slt 1) আর sltu-তে signed-unsigned ভিন্ন উত্তরের ক্ষেত্র (0xFF বনাম 0x01) চালিয়েছি
• C flag-এর অর্থ কোন ISA-র নিয়মে বলা, তা মিলিয়েছি; manual-এর লাইনটি নিজে পড়েছি
• Verilog হলে simulator-এ testbench চালিয়েছি, আর সম্ভব হলে exhaustive পরীক্ষা করেছি