এই পর্বে যা পাবেন
- আর্কিটেকচার আর ডিজিটাল লজিকের প্রতিটি ধরনের numerical-এর সূত্র, নিয়ম (convention) আর সাধারণ ফাঁদ — এক জায়গায়
- K-map-এর দল, QM-এর টেবিল, Booth আর ভাগের সারি, pipeline আর Tomasulo-র cycle-টেবিল, cache-এর hit/miss টেবিল এমনভাবে লেখার অভ্যাস, যাতে পরীক্ষক প্রতিটি ধাপ মেলাতে পারেন
- উল্টো দিকের প্রশ্ন সামলানো: “কত গুণ দ্রুত করতে হবে?”, “কত gate-স্তর রাখা যায়?”, “কোন hit rate লাগবে?”, “কত বিটের tag?”
- ছোট প্রোগ্রাম দিয়ে নিজের উত্তর মেলানো, আর AI-এর দেওয়া K-map বা cache-এর হিসাব সন্দেহের চোখে দেখা
১ · পাতার মানচিত্র, নিয়ম আর খাতায় উত্তর সাজানোর কৌশল
মডিউল ১০-এ স্বাগতম। প্রথম ৫৭টি পর্বে আপনি transistor আর gate থেকে শুরু করে pipeline, cache আর GPU পর্যন্ত একটি কম্পিউটারের ভেতরটা দেখেছেন। এই পাঁচটি পর্বে সেই জ্ঞান পরীক্ষার খাতায়, MCQ-এর ঘড়ির সামনে আর ইন্টারভিউর টেবিলে কাজে লাগানোর অনুশীলন। শুরু হচ্ছে numerical দিয়ে। বিশ্ববিদ্যালয়ের Digital Logic Design বা Computer Architecture কোর্সের লিখিত পরীক্ষা থেকে শুরু করে IT অফিসার বা hardware-firmware পদের লিখিত পরীক্ষা পর্যন্ত এ ধরনের প্রশ্ন প্রায়ই আসে — আর পদ্ধতি পরিষ্কার থাকলে এখানে পুরো নম্বর পাওয়া যায়।
এই বিষয়ের অঙ্কে ভুল সাধারণত সূত্রে হয় না, হয় একক আর নিয়মে। ৩২ KB cache-কে ৩২,০০০ byte ধরলে index-এর বিট ভগ্নাংশ আসে; forwarding আছে কি না না দেখে stall গুনলে cycle-সংখ্যা দ্বিগুণ হয়ে যায়; L2-এর local miss rate-কে global ধরে নিলে AMAT অনেক কম আসে। ক্যালকুলেটরের ভুলের মতোই এগুলো ছোট, কিন্তু উত্তর পুরো বদলে দেয়। তাই প্রতিটি প্রশ্নে নিয়ম লেখা আছে, আর আপনার খাতাতেও উত্তরের প্রথম লাইনে সেগুলো থাকা উচিত।
কোন ভাগে কী, কোন পর্ব ঝালাবেন
| ভাগ | কী আছে | মূল পর্ব |
|---|---|---|
| ২ | CPU time, CPI, MIPS, Amdahl; base আর ভগ্নাংশের রূপান্তর, two's complement, overflow, BCD, Gray, UTF-8, endianness | ০৩–০৬ |
| ৩ | Boolean সরলীকরণ, ৩ ও ৪ চলকের K-map, don't care, Quine-McCluskey, gate-সংখ্যা ও delay, ripple বনাম carry-lookahead, mux ও decoder দিয়ে function | ০৭–১৩ |
| ৪ | Flip-flop-এর excitation, next state, mod-N counter, FSM-এর state assignment, setup-hold আর fmax | ১৫–১৯ |
| ৫ | Booth-এর গুণ, restoring ও non-restoring ভাগ, IEEE 754 encode-decode, rounding, বিশেষ মান, float যোগ | ২০–২৪ |
| ৬ | RISC-V encoding ও decoding, branch offset, single-cycle-এর critical path, pipeline-এর cycle, data stall আর branch-এর CPI, ২-বিট predictor | ২৬–২৮, ৩২–৩৭ |
| ৭ | Tomasulo-র cycle-টেবিল, superscalar-এর IPC, SIMD-এর iteration | ৩৯–৪২ |
| ৮ | Cache-এর address ভাগ, মোট বিট, direct-mapped ও ২-way LRU trace, AMAT, stall-সহ CPI, DRAM, page table, TLB-এর EAT | ৪৪–৫০ |
| ৯ | Polling ও DMA-এর CPU-খরচ, Amdahl ও Gustafson, network-এর diameter ও bisection, warp divergence, dynamic power | ৫১–৫৬ |
এই পাতার নিয়ম (convention) — প্রশ্নে অন্য কিছু না বললে
| বিষয় | নিয়ম |
|---|---|
| একক | মেমরির আকার দুইয়ের ঘাতে: 1 KiB = 210 byte (পুরোনো বইয়ের “KB” এখানে KiB অর্থে)। Clock আর transfer rate দশমিকে: 1 GHz = 109 Hz, 1 MB/s = 106 byte/s, 1 GB/s = 109 byte/s |
| সংখ্যা | Signed মানে ৮ বা n বিটের two's complement; ভগ্নাংশ দরকার হলে রূপান্তর দশমিকের পরে নির্দিষ্ট অঙ্কে থামে |
| Boolean | Complement লেখায় A′ (প্রোগ্রামের আউটপুটে A'); minterm-এর ক্রমে A সবচেয়ে বড় বিট (m = 8A + 4B + 2C + D); minimum মানে আগে সবচেয়ে কম term, তারপর কম literal |
| Gate delay | প্রতিটি AND, OR, XOR = ১ gate delay, NOT ধরা হয় না, fan-in সীমা নেই; ripple-carry-র সবচেয়ে খারাপ 2n + 1, বহুস্তর CLA-তে স্তরপ্রতি ৪ (পর্ব ১১) |
| Timing | Setup: Tc ≥ tpcq + tpd + tsetup + tskew; hold: tccq + tcd ≥ thold + tskew — skew সবসময় সবচেয়ে খারাপ দিকে (পর্ব ১৮) |
| গুণ-ভাগ | Booth-এ A, Q, Q−1, M আর A:Q:Q−1-এর arithmetic right shift (পর্ব ২১); ভাগে A n + 1 বিট, প্রতি ধাপে আগে A:Q বাঁয়ে shift (পর্ব ২২) |
| Floating point | IEEE 754 single (১ + ৮ + ২৩ বিট, bias ১২৭), round to nearest, ties to even |
| Pipeline | RISC-V ৫ ধাপ (IF ID EX MEM WB); register file আগের অর্ধ-cycle-এ লেখে, পরের অর্ধে পড়ে; forwarding ছাড়া stall = max(0, 3 − d), forwarding থাকলে শুধু load-use-এ ১ stall (পর্ব ৩৬); branch-এর CPI = 1 + f × m × P (পর্ব ৩৭) |
| Tomasulo | Cycle t-তে issue হলে execute সবচেয়ে আগে t + 1-এ; CDB থেকে cycle W-তে operand এলে execute W + 1-এ; latency L হলে execute চলে L cycle; শেষের পরের cycle-এ write; CDB একটি, পুরোনো instruction আগে (পর্ব ৪০) |
| Cache ও মেমরি | Byte address; মোট বিট = line × (৮ × block + tag + valid [+ dirty]), LRU-এর বিট বাদ; replacement LRU; AMAT = HT + MR × MP, L2-এর miss rate local (পর্ব ৪৫–৪৭); EAT = tTLB + (1 − h) × L × tPTE + tmem (পর্ব ৫০) |
১. দেওয়া তথ্য আর একক এক লাইনে। “Cache = 32 KiB = 215 byte, block = 64 byte = 26, address = ৩২ বিট” — এই এক লাইনেই অর্ধেক কাজ শেষ, আর KB-KiB-এর ভুল সেখানেই ধরা পড়ে।
২. নিয়ম ঘোষণা করুন। “ধরে নিলাম forwarding আছে, branch EX-এ resolve হয়, L2-এর miss rate local.” প্রশ্নে স্পষ্ট না থাকলে এটাই আপনার রক্ষাকবচ।
৩. সূত্র আগে, মান পরে। “AMAT = HT1 + MR1 × (HT2 + MR2 × MP2)” লিখে তারপর সংখ্যা বসান। গণনায় ভুল হলেও সূত্রের নম্বর থাকে।
৪. টেবিলে উত্তর দিন। K-map, QM, Booth, ভাগ, pipeline, Tomasulo আর cache trace — সবই টেবিলের অঙ্ক। কলামের নাম আগে লিখুন, তারপর সারি ধরে ভরুন।
৫. একটি উল্টো চেক দিন। Booth-এর ফল সাধারণ গুণের সাথে, ভাগে ভাজক × ভাগফল + ভাগশেষ = ভাজ্য, K-map-এর উত্তর কয়েকটি minterm বসিয়ে, IEEE-র bit pattern আবার দশমিকে ফিরিয়ে।
৬. শেষ উত্তর আলাদা করুন, এক লাইনের মন্তব্যসহ। “CPI = ২.৪২৫; L2 যোগে প্রায় ১.৯৪ গুণ দ্রুত” — তুলনার প্রশ্নে এই এক লাইন অনেক সময় পূর্ণ নম্বর আনে।
২ · মডিউল ১ — পারফরম্যান্স আর ডেটার বিট-রূপ
ঝালিয়ে নিন: পর্ব ০৩ · পারফরম্যান্স মাপা, পর্ব ০৪ · সংখ্যা পদ্ধতি, পর্ব ০৫ · Integer-এর বিট-রূপ, পর্ব ০৬ · ডেটার বিট-রূপ.
Iron law: CPU time = IC × CPI × Tc = IC × CPI ÷ f. গড় CPI = Σ (ভাগi × CPIi). MIPS = f ÷ (CPI × 106) — একই কাজের instruction-সংখ্যা আলাদা হলে MIPS ধোঁকা দেয়।
Amdahl: Speedup = 1 ÷ ((1 − p) + p/s); s → ∞ হলে সীমা 1 ÷ (1 − p). উল্টো প্রশ্নে s = p ÷ (1/S − (1 − p)); হর ঋণাত্মক বা শূন্য হলে লক্ষ্য অসম্ভব।
রূপান্তর: পূর্ণ অংশ বারবার ভাগ (ভাগশেষ নিচ থেকে ওপরে), ভগ্নাংশ বারবার গুণ (পূর্ণ অংশ ওপর থেকে নিচে); binary ⇄ octal ৩ বিটের দল, binary ⇄ hex ৪ বিটের দল।
Two's complement: n বিটে পরিসর −2n−1 থেকে 2n−1 − 1; −x = বিট উল্টে + ১; sign extension-এ MSB কপি। যোগে V = ১ যখন দুই ইনপুটের চিহ্ন এক কিন্তু ফলের চিহ্ন আলাদা; C শুধু unsigned-এর overflow বলে।
পারফরম্যান্স
২.১(সহজ) একটি প্রোগ্রামে ২ × ১০৯টি instruction, গড় CPI ১.৫, clock ৩ GHz. CPU time কত?
CPU time = IC x CPI / f = 2 x 10^9 x 1.5 / (3 x 10^9) = 1.0 sলক্ষ করুন, গুণফলের এককগুলো কাটাকাটি হয়ে সেকেন্ড থাকে: instruction × (cycle/instruction) × (সেকেন্ড/cycle). উত্তর ১.০ সেকেন্ড।
২.২(মাঝারি) ১০৯টি instruction-এর মধ্যে A শ্রেণি ৫০% (CPI ১), B ৩০% (CPI ২), C ২০% (CPI ৩); clock ২.৫ GHz. গড় CPI, CPU time আর MIPS কত?
CPI = 0.5 x 1 + 0.3 x 2 + 0.2 x 3 = 0.5 + 0.6 + 0.6 = 1.7
time = 10^9 x 1.7 / (2.5 x 10^9) = 0.68 s
MIPS = 2.5 x 10^9 / (1.7 x 10^6) = 1470.6গড় CPI হলো ভারযুক্ত গড় — শ্রেণির CPI-গুলোর সরল গড় (২) নয়। CPI ১.৭, সময় ০.৬৮ সেকেন্ড, প্রায় ১৪৭০.৬ MIPS.
২.৩(মাঝারি) একই ISA-র দুটি প্রসেসর একই প্রোগ্রাম চালায়: P1 ২ GHz, CPI ১.৮; P2 ৩ GHz, CPI ২.৪. কোনটি কত গুণ দ্রুত?
time per instruction = CPI / f
P1: 1.8 / 2 GHz = 0.9 ns P2: 2.4 / 3 GHz = 0.8 ns
speedup = 0.9 / 0.8 = 1.125IC দুই দিকে একই, তাই তুলনায় বাদ যায়। বেশি CPI সত্ত্বেও দ্রুত clock P2-কে এগিয়ে রাখে। P2, ১.১২৫ গুণ দ্রুত। শুধু clock (৩ ÷ ২ = ১.৫) বা শুধু CPI দেখে সিদ্ধান্ত নেওয়া সাধারণ ভুল।
২.৪(মাঝারি) ১ GHz-এর একটি যন্ত্রে একই প্রোগ্রাম দুটি compiler-এ: A দেয় ১০৯টি instruction, CPI ১.২; B দেয় ১.৫ × ১০৯টি, CPI ১.০. কোনটির MIPS বেশি, আর কোনটি আসলে দ্রুত?
A: time = 10^9 x 1.2 / 10^9 = 1.2 s MIPS = 1000 / 1.2 = 833.3
B: time = 1.5 x 10^9 x 1.0 / 10^9 = 1.5 s MIPS = 1000 / 1.0 = 1000.0B-র MIPS বেশি, অথচ B ধীর — কারণ সে বেশি instruction চালায়। এজন্যই পর্ব ০৩-এ বলা হয়েছে, একমাত্র নির্ভরযোগ্য মাপ হলো পুরো কাজের সময়। MIPS-এ B এগিয়ে (১০০০ বনাম ৮৩৩.৩), সময়ে A এগিয়ে (১.২ বনাম ১.৫ সেকেন্ড)।
২.৫(কঠিন) একটি প্রোগ্রামের সময়ের ৪০% একটি ফাংশনে যায়। (ক) সেটিকে ৮ গুণ দ্রুত করলে মোট speedup কত, আর সর্বোচ্চ সীমা কত? (খ) মোট ২ গুণ speedup চাইলে ফাংশনটি সময়ের ৭০% হলে তাকে কত গুণ দ্রুত করতে হবে? ৪০% হলে?
(a) S = 1 / (0.6 + 0.4/8) = 1 / 0.65 = 1.538 limit = 1 / 0.6 = 1.667
(b) 1 / (1 - p + p/s) = 2 => s = p / (1/2 - (1 - p))
p = 0.7 : s = 0.7 / (0.5 - 0.3) = 3.5
p = 0.4 : s = 0.4 / (0.5 - 0.6) < 0 -> impossibleপ্রমাণের লাইন: নতুন সময় = (1 − p)T + pT/s, তাই S = T ÷ নতুন সময়। (খ)-তে p = ০.৪ হলে বাকি ৬০% একাই নতুন সময়ের সীমা টেনে দেয় — ফাংশনটিকে শূন্য সময়ে নামালেও speedup ১.৬৬৭-এর বেশি নয়। (ক) ≈ ১.৫৩৮, সীমা ≈ ১.৬৬৭; (খ) ৩.৫ গুণ, আর ৪০%-এ অসম্ভব।
// CPU time, CPI, MIPS and Amdahl calculator (iron law: time = IC x CPI / f).
const time = (IC, CPI, f) => IC * CPI / f;
const mips = (CPI, f) => f / (CPI * 1e6);
const amdahl = (p, s) => 1 / ((1 - p) + p / s);
const f3 = x => x.toFixed(3);
console.log("2.1 time =", f3(time(2e9, 1.5, 3e9)), "s");
const mix = [[0.5, 1], [0.3, 2], [0.2, 3]]; // [fraction, CPI] for classes A, B, C
const cpi = mix.reduce((s, [fr, c]) => s + fr * c, 0);
console.log("2.2 CPI =", f3(cpi), " time =", f3(time(1e9, cpi, 2.5e9)), "s MIPS =", mips(cpi, 2.5e9).toFixed(1));
const tP1 = time(1, 1.8, 2e9), tP2 = time(1, 2.4, 3e9); // same IC on both
console.log("2.3 ns/instr P1 =", f3(tP1 * 1e9), " P2 =", f3(tP2 * 1e9), " P2 faster by", f3(tP1 / tP2));
for (const [name, IC, c] of [["A", 1e9, 1.2], ["B", 1.5e9, 1.0]])
console.log(`2.4 compiler ${name}: time ${f3(time(IC, c, 1e9))} s, MIPS ${mips(c, 1e9).toFixed(1)}`);
console.log("2.5 Amdahl p=0.4 s=8:", f3(amdahl(0.4, 8)), " limit s->inf:", f3(1 / 0.6));
const need = (p, S) => p / (1 / S - (1 - p)); // part speedup for overall S
console.log("2.5 overall 2x with p=0.7 needs s =", f3(need(0.7, 2)), "; with p=0.4:", need(0.4, 2) < 0 ? "impossible" : f3(need(0.4, 2)));আউটপুট:
2.1 time = 1.000 s
2.2 CPI = 1.700 time = 0.680 s MIPS = 1470.6
2.3 ns/instr P1 = 0.900 P2 = 0.800 P2 faster by 1.125
2.4 compiler A: time 1.200 s, MIPS 833.3
2.4 compiler B: time 1.500 s, MIPS 1000.0
2.5 Amdahl p=0.4 s=8: 1.538 limit s->inf: 1.667
2.5 overall 2x with p=0.7 needs s = 3.500 ; with p=0.4: impossibleপ্রতিটি লাইন একটি প্রশ্নের উত্তর মেলায়: ১.০০০ সেকেন্ড; CPI ১.৭, ০.৬৮ সেকেন্ড, ১৪৭০.৬ MIPS; ০.৯ বনাম ০.৮ ns, অর্থাৎ ১.১২৫ গুণ; দুই compiler-এর ১.২ ও ১.৫ সেকেন্ড বনাম ৮৩৩.৩ ও ১০০০ MIPS; আর Amdahl-এর ১.৫৩৮, ১.৬৬৭ আর ৩.৫. need() ফাংশনটি উল্টো প্রশ্নের সূত্র — হর ঋণাত্মক হলে “impossible” লেখে।
সংখ্যা পদ্ধতি আর integer
২.৬(সহজ) দশমিক ২৩৭-কে binary, octal আর hexadecimal-এ লিখুন।
237 / 2 = 118 r1 118 / 2 = 59 r0 59 / 2 = 29 r1 29 / 2 = 14 r1
14 / 2 = 7 r0 7 / 2 = 3 r1 3 / 2 = 1 r1 1 / 2 = 0 r1
remainders bottom-up -> 1110 1101
octal : 11 101 101 -> 3 5 5 = 355
hex : 1110 1101 -> E D = EDযাচাই: E × ১৬ + D = ১৪ × ১৬ + ১৩ = ২৩৭. Octal-এ দল বাঁধা ডান দিক থেকে, বাঁয়ের অসম্পূর্ণ দলে সামনে শূন্য। 111011012 = 3558 = ED16.
২.৭(মাঝারি) (ক) ১৩.৩৭৫ আর ০.১-কে binary-তে লিখুন। (খ) 2B.C16 আর 1011.1012-এর দশমিক মান কত?
(a) 13 = 1101 ; .375 x 2 = 0.75 -> 0, 1.5 -> 1, 1.0 -> 1 => 1101.011
.1 x 2: 0.2 0 0.4 0 0.8 0 1.6 1 1.2 1 0.4 0 0.8 0 1.6 1 ...
=> 0.0001 1001 1001 ... (0011 repeats for ever)
(b) 2B.C (16) = 2x16 + 11 + 12/16 = 43.75
1011.101 (2) = 8 + 2 + 1 + 1/2 + 1/8 = 11.625০.১ কোনো সসীম binary ভগ্নাংশে ধরে না, কারণ হরে ৫ আছে (১/১০) আর binary-তে সসীম হয় শুধু ২-এর ঘাতের হর। ভাগ ৫-এর IEEE 754-এ এই কারণেই ০.১ একটু বেশি হয়ে জমা থাকে। ১৩.৩৭৫ = 1101.0112; ০.১ = 0.0(0011)2, বন্ধনীর অংশ চিরকাল পুনরাবৃত্ত; ৪৩.৭৫ আর ১১.৬২৫.
২.৮(মাঝারি) ৮ বিটের two's complement-এ (ক) পরিসর কত? (খ) −৪৫ লিখুন — binary আর hex দুই রূপে। (গ) 0xF3-এর মান কত, আর একে ১৬ বিটে sign-extend করলে কী দাঁড়ায়?
(a) -2^7 .. 2^7 - 1 = -128 .. 127
(b) +45 = 0010 1101 -> invert 1101 0010 -> +1 = 1101 0011 = 0xD3
(c) 0xF3 = 1111 0011 : MSB 1, so negative
invert 0000 1100, +1 = 0000 1101 = 13 -> value -13
sign-extend: copy the MSB -> 1111 1111 1111 0011 = 0xFFF3 (still -13)Zero-extend করলে 0x00F3 = ২৪৩ আসত — unsigned-এর জন্য ঠিক, signed-এর জন্য ভুল। −১২৮ থেকে ১২৭; −৪৫ = 1101 0011 = 0xD3; 0xF3 = −১৩, ১৬ বিটে 0xFFF3.
২.৯(মাঝারি) ৮ বিটের adder-এ চারটি signed যোগ: ১০০ + ৫০, (−১০০) + (−৫০), (−২০) + ৩০, ১২৭ + ১. প্রতিটির ৮ বিটের ফল, তার signed মান, C আর V কত?
a b 8-bit sum as int8 C V
100 50 1001 0110 -106 0 1 (+ plus + gave -)
-100 -50 0110 1010 106 1 1 (- plus - gave +)
-20 30 0000 1010 10 1 0 (signs differ: never overflows)
127 1 1000 0000 -128 0 1V আর C আলাদা প্রশ্নের উত্তর দেয়: −২০ + ৩০-এ C = ১ (unsigned হিসেবে ২৩৬ + ৩০ = ২৬৬ > ২৫৫) কিন্তু signed ফল ১০ সম্পূর্ণ ঠিক। প্রমাণের লাইন: চিহ্ন আলাদা হলে ফলের মান দুই ইনপুটের মাঝখানে, তাই পরিসর ছাড়াতে পারে না। V = ১, ১, ০, ১; C = ০, ১, ১, ০.
// Base converter (with fractions) + two's complement helper. Edit the values and Run.
function toBase(x, b, fracDigits = 8) { // x >= 0, fraction cut after fracDigits digits
let ip = Math.floor(x), fp = x - ip, s = ip.toString(b).toUpperCase(), f = "";
for (let k = 0; k < fracDigits && fp > 0; k++) { fp *= b; f += Math.floor(fp).toString(b).toUpperCase(); fp -= Math.floor(fp); }
return f ? s + "." + f + (fp > 0 ? "..." : "") : s;
}
const fromBase = (s, b) => { const [i, f = ""] = s.split(".");
return parseInt(i, b) + [...f].reduce((acc, d, k) => acc + parseInt(d, b) / b ** (k + 1), 0); };
for (const x of [237, 13.375, 0.1]) console.log(`${x} = ${toBase(x, 2, 12)} (2) = ${toBase(x, 8, 4)} (8) = ${toBase(x, 16, 4)} (16)`);
console.log("2B.C (16) =", fromBase("2B.C", 16), " 755 (8) =", fromBase("755", 8), " 1011.101 (2) =", fromBase("1011.101", 2));
const bits = (v, n) => (BigInt.asUintN(n, BigInt(v))).toString(2).padStart(n, "0");
const signed = (u, n) => Number(BigInt.asIntN(n, BigInt(u)));
for (const n of [8, 16]) console.log(`${n}-bit two's complement range: ${-(2 ** (n - 1))} .. ${2 ** (n - 1) - 1}`);
console.log("-45 in 8 bits =", bits(-45, 8), " 0xF3 as int8 =", signed(0xF3, 8), " sign-extended to 16 bits =", bits(signed(0xF3, 8), 16));
function add8(a, b) { // a, b given as signed values
const ua = Number(BigInt.asUintN(8, BigInt(a))), ub = Number(BigInt.asUintN(8, BigInt(b)));
const sum = (ua + ub) & 0xFF, C = (ua + ub) > 0xFF ? 1 : 0;
const V = ((ua ^ sum) & (ub ^ sum) & 0x80) ? 1 : 0; // both inputs same sign, result different
console.log(`${a} + ${b} -> ${bits(sum, 8)} = ${signed(sum, 8)} C=${C} V=${V}`);
}
add8(100, 50); add8(-100, -50); add8(-20, 30); add8(127, 1);আউটপুট:
237 = 11101101 (2) = 355 (8) = ED (16)
13.375 = 1101.011 (2) = 15.3 (8) = D.6 (16)
0.1 = 0.000110011001... (2) = 0.0631... (8) = 0.1999... (16)
2B.C (16) = 43.75 755 (8) = 493 1011.101 (2) = 11.625
8-bit two's complement range: -128 .. 127
16-bit two's complement range: -32768 .. 32767
-45 in 8 bits = 11010011 0xF3 as int8 = -13 sign-extended to 16 bits = 1111111111110011
100 + 50 -> 10010110 = -106 C=0 V=1
-100 + -50 -> 01101010 = 106 C=1 V=1
-20 + 30 -> 00001010 = 10 C=1 V=0
127 + 1 -> 10000000 = -128 C=0 V=1প্রথম তিন লাইন ২.৬ আর ২.৭: ২৩৭ = 11101101 = 355 = ED, ১৩.৩৭৫ = 1101.011, আর ০.১-এর পেছনে “...” মানে বারো অঙ্কেও ভগ্নাংশ শেষ হয়নি। তারপর 2B.C = ৪৩.৭৫, ৭৫৫৮ = ৪৯৩, 1011.101 = ১১.৬২৫. শেষ চার লাইন ২.৯-এর টেবিল হুবহু। V-এর শর্তটি এক লাইনে: (ua ^ sum) & (ub ^ sum) & 0x80 — দুই ইনপুটের সাথেই ফলের চিহ্ন-বিট আলাদা হলে overflow.
কোড, অক্ষর আর byte-এর ক্রম
২.১০(সহজ) (ক) ২০২৫-কে BCD-তে লিখুন; সাধারণ binary-র চেয়ে কত বিট বেশি লাগে? (খ) 1011-এর Gray code কত? (গ) Gray 1101-এর binary কত?
(a) BCD : 2 0 2 5 -> 0010 0000 0010 0101 16 bits
binary: 2025 = 111 1110 1001 11 bits -> 5 bits more
(b) g = b XOR (b >> 1): 1011 ^ 0101 = 1110
(c) b3 = g3 = 1, b2 = b3^g2 = 0, b1 = b2^g1 = 0, b0 = b1^g0 = 1 -> 1001Gray থেকে binary-তে ফেরার সময় প্রতিটি বিট আগের binary বিটের সাথে XOR — আগের Gray বিটের সাথে নয়, এটিই সাধারণ ভুল। BCD ১৬ বিট (৫ বিট বেশি); Gray 1110; binary 1001.
২.১১(মাঝারি) UTF-8-এ কত byte লাগে: (ক) “ABCL”, (খ) “বাংলা” (পাঁচটি code point: U+09AC, U+09BE, U+0982, U+09B2, U+09BE), (গ) emoji U+1F600? UTF-16-এ (খ) আর (গ)?
UTF-8 length: U+0000-007F 1 byte, U+0080-07FF 2, U+0800-FFFF 3, U+10000-10FFFF 4
(a) 4 ASCII letters -> 4 bytes
(b) 5 code points in U+0980-09FF, each 3 bytes -> 15 bytes (UTF-16: 5 x 2 = 10 bytes)
(c) U+1F600 > U+FFFF -> 4 bytes (UTF-16: surrogate pair D83D DE00 = 4 bytes)“বাংলা” পর্দায় তিনটি অক্ষরের মতো দেখায়, কিন্তু code point পাঁচটি (কার আর অনুস্বার আলাদা)। তাই “অক্ষর-সংখ্যা”, code point আর byte — তিনটি আলাদা সংখ্যা (পর্ব ০৬)। ৪, ১৫ আর ৪ byte; UTF-16-এ ১০ আর ৪ byte.
২.১২(মাঝারি) ৩২ বিটের 0x12345678 ঠিকানা 0x100 থেকে জমা হলো। (ক) little-endian আর big-endian-এ 0x100–0x103-এ কোন byte? (খ) এরপর 0x102 থেকে ১৬ বিট পড়লে দুই ক্ষেত্রে কী মান আসে?
address 0x100 0x101 0x102 0x103
little-endian 78 56 34 12 (least significant byte first)
big-endian 12 34 56 78
16-bit read at 0x102: LE -> bytes 34 12 -> 0x1234 BE -> bytes 56 78 -> 0x5678RISC-V, x86-64 আর বেশিরভাগ ARM সিস্টেম little-endian; network byte order big-endian. LE: 78 56 34 12, BE: 12 34 56 78; ১৬ বিটে 0x1234 (LE) আর 0x5678 (BE).
#include <stdio.h>
#include <string.h>
#include <stdint.h>
static void dump(const char *name, const void *p, size_t n) {
const unsigned char *b = p;
printf("%-22s", name);
for (size_t i = 0; i < n; i++) printf(" %02X", b[i]);
printf(" (%zu bytes)\n", n);
}
int main(void) {
uint32_t w = 0x12345678u;
dump("uint32 0x12345678", &w, sizeof w); /* lowest address first */
uint16_t half;
memcpy(&half, (unsigned char *)&w + 2, 2); /* 16-bit read at address +2 */
printf("16-bit at +2 = 0x%04X\n", half);
const char *bangla = "বাংলা"; /* the word "Bangla" in Bengali script */
dump("UTF-8 Bangla word", bangla, strlen(bangla));
dump("UTF-8 \"ABCL\"", "ABCL", 4);
dump("UTF-8 U+1F600", "\U0001F600", strlen("\U0001F600"));
float f = -12.625f;
uint32_t u;
memcpy(&u, &f, sizeof u); /* type punning without UB */
printf("-12.625f bits = 0x%08X\n", u);
dump("-12.625f in memory", &f, sizeof f);
return 0;
}আউটপুট (Linux x86-64, little-endian):
uint32 0x12345678 78 56 34 12 (4 bytes)
16-bit at +2 = 0x1234
UTF-8 Bangla word E0 A6 AC E0 A6 BE E0 A6 82 E0 A6 B2 E0 A6 BE (15 bytes)
UTF-8 "ABCL" 41 42 43 4C (4 bytes)
UTF-8 U+1F600 F0 9F 98 80 (4 bytes)
-12.625f bits = 0xC14A0000
-12.625f in memory 00 00 4A C1 (4 bytes)প্রথম লাইন ২.১২-এর little-endian সারি: সবচেয়ে নিচু ঠিকানায় 78. ঠিকানা +2 থেকে ১৬ বিট পড়ে 0x1234 এসেছে। তারপর ২.১১-এর byte গোনা: বাংলা শব্দটির ১৫টি byte, প্রতিটি অক্ষর E0 A6 দিয়ে শুরু (U+09xx-এর তিন-byte রূপ), “ABCL” ৪টি, emoji ৪টি। শেষ দুই লাইন ভাগ ৫-এর প্রশ্ন ৫.৫-এর আগাম যাচাই: −১২.৬২৫-এর বিট 0xC14A0000, আর মেমরিতে উল্টো ক্রমে 00 00 4A C1. memcpy দিয়ে float-এর বিট পড়া হয়েছে, যাতে C-র undefined behavior না হয়।
(সহজ) ৮ বিটের two's complement-এ 1110 0110-এর মান কত?
- 230
- −26
- −25
- −102
(মাঝারি) একটি প্রোগ্রামের সময়ের ৩০% অংশকে ৫ গুণ দ্রুত করা হলো, বাকিটা অপরিবর্তিত। মোট speedup প্রায় কত?
- 5.0
- 1.5
- ≈ 1.316
- ≈ 1.429
৩ · মডিউল ২ — Boolean, K-map, adder আর mux-decoder
ঝালিয়ে নিন: পর্ব ০৭ · Boolean algebra, পর্ব ০৮ · Logic gate আর transistor, পর্ব ০৯ · K-map দিয়ে সরলীকরণ, পর্ব ১০ · Quine-McCluskey, পর্ব ১১ · Adder, পর্ব ১২ · Multiplexer, decoder আর encoder, পর্ব ১৩ · ALU নকশা.
সূত্র: consensus AB + A′C + BC = AB + A′C; absorption A + AB = A; De Morgan (A + B)′ = A′B′, (AB)′ = A′ + B′.
K-map: সারি আর কলাম Gray ক্রমে (00, 01, 11, 10), কিনারা ঘুরে মেলে। দল ১, ২, ৪, ৮ ঘরের আয়তক্ষেত্র, যত বড় তত ভালো; don't care (X) শুধু দল বড় করতে কাজে লাগলে নিন। ধাপ: সব prime implicant → essential আগে → বাকি 1 সবচেয়ে কম দলে।
QM: minterm-কে ১-এর সংখ্যা ধরে দলে সাজানো, পাশের দলের এক-বিট-পার্থক্যের জোড়া মেলানো (– চিহ্ন), যেগুলো আর মেলে না তারাই prime; তারপর PI chart-এ essential খোঁজা।
Delay: two-level AND-OR বা NAND-NAND = ২ gate delay; ripple-carry 2n + 1; বহুস্তর CLA 4⌈log4 n⌉; ৪ বিটের CLA-ব্লক ripple করে জুড়লে n/2 + 2.
Boolean আর K-map
৩.১(সহজ) (ক) F = AB + A′C + BC সরল করুন আর কারণ দেখান। (খ) (A + B′C)′-কে De Morgan দিয়ে খুলুন।
(a) BC = BC(A + A') = ABC + A'BC
F = AB + ABC + A'C + A'BC = AB(1 + C) + A'C(1 + B) = AB + A'C
(b) (A + B'C)' = A' . (B'C)' = A'(B + C') = A'B + A'C'BC হলো consensus পদ — AB আর A′C-এর মধ্যে A আর A′ বাদ দিলে যা থাকে। সব আটটি ইনপুটে truth table মিলিয়ে দুটি উত্তরই যাচাই করা হয়েছে। (ক) AB + A′C; (খ) A′(B + C′).
৩.২(সহজ) F(A, B, C) = Σm(0, 2, 4, 5, 6)-এর minimum SOP আর minimum POS বের করুন।
A\BC 00 01 11 10
0 1 0 0 1 C' : m0 m2 m4 m6 (columns 00 and 10 wrap around)
1 1 1 0 1 AB' : m4 m5
SOP: F = C' + AB'
zeros m1 m3 m7: F' = A'C + BC -> F = (A + C')(B' + C')কিনারার দুই কলাম (00 আর 10) পাশাপাশি — K-map-এর সবচেয়ে বেশি ভুলে যাওয়া নিয়ম। POS পেতে 0-গুলোর দল করে F′ বের করুন, তারপর De Morgan. দুটি উত্তরই truth table-এ মেলানো। SOP: C′ + AB′; POS: (A + C′)(B′ + C′).
AB\CD 00 01 11 10
00 0 X 1 1
01 0 0 1 0
11 0 1 X 0
10 0 1 1 X
ones: m2 m3 m7 m9 m11 m13 X: m1 m10 m15
AB\CD 00 01 11 10
00 0 X [1] [1]
01 0 0 1 0
11 0 1 X 0
10 0 1 [1] [X]
B'C = m2 m3 m11 m10(X) rows 00+10, columns 11+10
AB\CD 00 01 11 10
00 0 X [1] 1
01 0 0 [1] 0
11 0 1 [X] 0
10 0 1 [1] X
CD = m3 m7 m15(X) m11 the whole column 11
AB\CD 00 01 11 10
00 0 X 1 1
01 0 0 1 0
11 0 [1] [X] 0
10 0 [1] [1] X
AD = m13 m15(X) m9 m11 rows 11+10, columns 01+11
m2 -> only B'C m7 -> only CD m13 -> only AD
all six 1s covered; X m1 left out (using it gives nothing)
B'D = m1 m3 m9 m11 is also prime, but redundant
F = B'C + CD + AD 3 terms, 6 literals
- Map ভরা। ছয়টি 1 (m2, m3, m7, m9, m11, m13) আর তিনটি X (m1, m10, m15). সারি AB, কলাম CD — দুটিই Gray ক্রমে, তাই m3-এর ঘর m2-এর পাশে, m11-এর ঘর m10-এর পাশে।
- B′C. m2-কে বড় দলে নেওয়ার একমাত্র উপায়: ওপরের আর নিচের সারি (কিনারা ঘুরে পাশাপাশি) আর ডানের দুই কলাম। X m10 এখানে কাজে লাগল — না নিলে দলটি ৪ ঘরের হতো না। m2 শুধু এই দলেই আছে, তাই B′C essential.
- CD. m7-এর পাশে ১ বা X আছে ওপরে-নিচে — পুরো কলাম 11-এ m3, m7, m15 (X), m11. m7-কে আর কোনো ৪-ঘরের দল ঢাকে না, তাই CD-ও essential.
- AD. m9 আর m13 এখনো বাকি। নিচের দুই সারি আর কলাম 01–11 মিলে m13, m15 (X), m9, m11 — একটি ২ × ২ বর্গ। m13-কে শুধু এটিই ঢাকে, তাই AD-ও essential (m9-কে B′D-ও ঢাকে)।
- যাচাই। ছয়টি 1-ই ঢাকা পড়েছে, তিনটি দলই essential, তাই উত্তর অনন্য। X m1 নেওয়া হয়নি — নিলে B′D নামের আরেকটি prime হয়, কিন্তু তার সব 1 আগেই ঢাকা। F = B′C + CD + AD.
৩.৩(মাঝারি) F(A, B, C, D) = Σm(2, 3, 7, 9, 11, 13) + d(1, 10, 15)-এর minimum SOP কত? কোন don't care ব্যবহার হলো?
ওপরের stepper-এ ধাপগুলো দেখুন। তিনটি essential দল: B′C (m2, m3, m11 আর X m10), CD (পুরো কলাম 11, X m15 সহ) আর AD (m9, m13, m11, X m15). X m1 অব্যবহৃত, কারণ তাকে নিয়ে কোনো নতুন 1 ঢাকা পড়ে না। F = B′C + CD + AD (৩টি term, ৬টি literal); m10 আর m15 = ১ ধরা হলো, m1 = ০.
৩.৪(কঠিন) Quine-McCluskey দিয়ে F(A, B, C, D) = Σm(0, 1, 2, 5, 6, 7, 8, 9, 10, 14) সরল করুন — দলের টেবিল আর PI chart দেখিয়ে।
column 1 (by number of 1s) column 2 (pairs) column 3 (quads)
0: 0000 (0) 000- (0,1) 00-0 (0,2) -00- (0,1,8,9) = B'C'
1: 0001 (1) 0010 (2) -000 (0,8) 0-01 (1,5) * -0-0 (0,2,8,10) = B'D'
1000 (8) -001 (1,9) 0-10 (2,6) --10 (2,6,10,14) = CD'
2: 0101 (5) 0110 (6) -010 (2,10) 100- (8,9)
1001 (9) 1010 (10) 10-0 (8,10) 01-1 (5,7) *
3: 0111 (7) 1110 (14) 011- (6,7) * -110 (6,14) 1-10 (10,14)
* = cannot merge further: A'C'D, A'BD, A'BC
PI chart 0 1 2 5 6 7 8 9 10 14
B'C' x x x x m9 only here -> essential
B'D' x x x x
CD' x x x x m14 only here -> essential
A'C'D x x
A'BD x x
A'BC x x
after B'C' + CD': left m5, m7 -> A'BD covers bothB′C′ আর CD′ বাদে বাকি থাকে m5 আর m7; A′BD একাই দুটিকে ঢাকে, অথচ A′C′D + A′BC নিলে দুটি term লাগত। ছয়টি PI-র সব সম্ভাব্য cover পরীক্ষা করে (নিচের প্রোগ্রাম) দেখা গেছে এটিই একমাত্র minimum. F = B′C′ + CD′ + A′BD (৩টি term, ৭টি literal).
৩.৫(মাঝারি) F(A, B, C, D) = Σm(4, 5, 11, 12, 13, 14, 15) + d(0, 2)-এর minimum SOP কত? Don't care-গুলো কি লাগে?
essential: BC' (4 5 12 13), AB (12 13 14 15), ACD (11 15)
X m0, m2 only make A'B'D' (0,2) and A'C'D' (0,4) - neither is needed
F = BC' + AB + ACDDon't care মানে “লাগলে নিন”, “নিতেই হবে” নয়। X নিয়ে বাড়তি term বানালে উত্তর minimum থাকে না। F = BC′ + AB + ACD; m0 আর m2 দুটিই ০ ধরা হলো।
৩.৬(মাঝারি) F(A, B, C) = Σm(0, 2, 3, 5, 7)-এর minimum SOP কি একটিই?
primes: A'C' (0,2) ess, AC (5,7) ess, A'B (2,3), BC (3,7)
m3 still uncovered -> A'B or BC (same cost)
F = A'C' + AC + A'B or F = A'C' + AC + BCনা — দুটি সমান খরচের উত্তর আছে, দুটিই ঠিক। খাতায় একটি দিন, পাশে লিখুন “BC নিলেও সমান”। MCQ-তে বিকল্পের যেকোনো একটি থাকতে পারে। দুটি minimum: A′C′ + AC + A′B আর A′C′ + AC + BC.
// Quine-McCluskey: prime implicants, essential ones and every minimum SOP. Term = [value, dashMask].
function minimize(n, ones, dcs = [], V = "ABCD".slice(0, n)) {
let terms = [...ones, ...dcs].map(m => [m, 0]), primes = [], key = t => t.join(",");
while (terms.length) { // merge terms that differ in exactly one bit
const next = new Map(), used = new Set();
for (const a of terms) for (const b of terms) {
const d = a[0] ^ b[0];
if (a[1] === b[1] && a[0] < b[0] && (d & (d - 1)) === 0) {
next.set(key([a[0] & ~d, a[1] | d]), [a[0] & ~d, a[1] | d]); used.add(key(a)); used.add(key(b)); }
}
primes.push(...terms.filter(t => !used.has(key(t)))); terms = [...next.values()];
}
const cov = (p, m) => (m & ~p[1]) === p[0];
const name = p => [...V].map((v, i) => { const bit = 1 << (n - 1 - i);
return p[1] & bit ? "" : v + (p[0] & bit ? "" : "'"); }).join("") || "1";
const ess = primes.filter(p => ones.some(m => cov(p, m) && primes.filter(q => cov(q, m)).length === 1));
console.log(`n=${n} ones=[${ones}] dc=[${dcs}]\n primes: ${primes.map(name).join(", ")} | essential: ${ess.map(name).join(", ") || "none"}`);
const cost = c => c.length * 100 + c.reduce((s, p) => s + n - p[1].toString(2).replace(/0/g, "").length, 0);
const sols = []; // brute force over subsets of primes (fine for 4 variables)
for (let mask = 1; mask < 1 << primes.length; mask++) {
const c = primes.filter((_, i) => mask >> i & 1);
if (ones.every(m => c.some(p => cov(p, m)))) sols.push(c); }
const best = Math.min(...sols.map(cost));
sols.filter(c => cost(c) === best).forEach(c => console.log(" minimum: F =", c.map(name).join(" + ")));
}
minimize(3, [0, 2, 4, 5, 6]); minimize(3, [1, 3, 7]); // 3.2 SOP, and its zeros for POS
minimize(4, [2, 3, 7, 9, 11, 13], [1, 10, 15]); // 3.3 (stepper)
minimize(4, [0, 1, 2, 5, 6, 7, 8, 9, 10, 14]); // 3.4 QM
minimize(4, [4, 5, 11, 12, 13, 14, 15], [0, 2]); // 3.5 are the don't-cares needed?
minimize(3, [0, 2, 3, 5, 7]); // 3.6 two minimum answersআউটপুট:
n=3 ones=[0,2,4,5,6] dc=[]
primes: AB', C' | essential: AB', C'
minimum: F = AB' + C'
n=3 ones=[1,3,7] dc=[]
primes: A'C, BC | essential: A'C, BC
minimum: F = A'C + BC
n=4 ones=[2,3,7,9,11,13] dc=[1,10,15]
primes: B'C, CD, AD, B'D | essential: B'C, CD, AD
minimum: F = B'C + CD + AD
n=4 ones=[0,1,2,5,6,7,8,9,10,14] dc=[]
primes: A'C'D, A'BD, A'BC, B'C', B'D', CD' | essential: B'C', CD'
minimum: F = A'BD + B'C' + CD'
n=4 ones=[4,5,11,12,13,14,15] dc=[0,2]
primes: ACD, A'C'D', A'B'D', BC', AB | essential: ACD, BC', AB
minimum: F = ACD + BC' + AB
n=3 ones=[0,2,3,5,7] dc=[]
primes: A'C', A'B, BC, AC | essential: A'C', AC
minimum: F = A'C' + A'B + AC
minimum: F = A'C' + BC + ACপ্রতিটি লাইন একটি প্রশ্নের উত্তর মেলায়: ৩.২-এর C′ + AB′ (term-এর ক্রম প্রোগ্রামের নিজের, অর্থ একই) আর 0-গুলোর A′C + BC, যা থেকে POS; ৩.৩-এর B′C + CD + AD আর অপ্রয়োজনীয় prime B′D; ৩.৪-এর ছয়টি prime, দুটি essential আর একমাত্র minimum; ৩.৫-এ don't care থেকে তৈরি দুটি prime অব্যবহৃত; ৩.৬-এ দুটি “minimum” লাইন — সমান খরচের দুই উত্তর। Prime খোঁজার লুপটি QM-এর কলাম ১ → ২ → ৩-এর হুবহু কাজ: একই dash-mask আর ঠিক এক বিটের পার্থক্য হলে জোড়া।
Gate, adder আর mux-decoder
৩.৭(মাঝারি) F = AB + CD + EF. (ক) AND-OR রূপে কয়টি gate আর কত gate delay? (খ) শুধু NAND দিয়ে? (গ) সব gate দুই-ইনপুটের হলে? প্রতি gate ২৫ ps ধরুন।
(a) 3 AND2 + 1 OR3 = 4 gates, 2 levels -> 50 ps
(b) 3 NAND2 + 1 NAND3 = 4 gates, 2 levels -> 50 ps (F = ((AB)'(CD)'(EF)')')
(c) 3 AND2 + 2 OR2 = 5 gates, 3 levels -> 75 ps (OR3 split into a tree)NAND-NAND রূপ AND-OR-এর হুবহু বদলি (De Morgan), তাই gate আর স্তর একই থাকে; CMOS-এ NAND সাধারণত AND-এর চেয়ে ছোট (পর্ব ০৮)। ৪টি gate, ৫০ ps; NAND-এ ৪টি, ৫০ ps; দুই-ইনপুটে ৫টি, ৭৫ ps.
৩.৮(মাঝারি) পর্ব ১১-এর unit-delay মডেলে ১৬, ৩২ আর ৬৪ বিটের ripple-carry, ৪ বিটের CLA-ব্লক ripple করা, আর বহুস্তর CLA-র সবচেয়ে খারাপ delay কত? প্রতি gate ২৫ ps হলে ৩২ বিটে ns-এ কত?
n ripple 2n+1 CLA blocks n/2+2 multi-level 4*ceil(log4 n)
16 33 10 8
32 65 18 12
64 129 34 12
32-bit: ripple 65 x 25 = 1625 ps = 1.625 ns multi-level CLA 12 x 25 = 300 psবহুস্তর CLA-তে প্রতিটি স্তরে ওঠা (G, P) আর নামা (carry) মিলে +৪; ৩২ বিটেও তিন স্তর লাগে, তাই ৬৪ বিটের সমান ১২. Ripple ৩৩/৬৫/১২৯, ব্লক-ripple ১০/১৮/৩৪, CLA ৮/১২/১২; ৩২ বিটে ১.৬২৫ ns বনাম ০.৩ ns.
৩.৯(মাঝারি) F(A, B, C) = Σm(1, 2, 6, 7)-কে একটি ৪:১ multiplexer দিয়ে বানান; select লাইন A আর B (A বড় বিট)। ডেটা ইনপুট I0–I3-এ কী দেবেন?
AB = 00 : m0 = 0, m1 = 1 -> F = C -> I0 = C
AB = 01 : m2 = 1, m3 = 0 -> F = C' -> I1 = C'
AB = 10 : m4 = 0, m5 = 0 -> F = 0 -> I2 = 0
AB = 11 : m6 = 1, m7 = 1 -> F = 1 -> I3 = 1পদ্ধতি: select যে চলকগুলো, তাদের প্রতিটি মানের জন্য বাকি চলক (এখানে C)-এর function লিখুন — 0, 1, C বা C′. ৮:১ mux হলে truth table-এর আটটি মান সরাসরি ইনপুটে বসে। I0 = C, I1 = C′, I2 = ০, I3 = ১.
৩.১০(সহজ) একটি ৩:৮ decoder আর কয়েকটি OR gate দিয়ে full adder বানাতে কোন আউটপুট কোন OR-এ যাবে?
inputs (A, B, Cin) -> decoder outputs D0..D7 (one minterm each)
S = sum of minterms with an odd number of 1s = m1 + m2 + m4 + m7 -> OR4(D1, D2, D4, D7)
Cout = majority = m3 + m5 + m6 + m7 -> OR4(D3, D5, D6, D7)Decoder প্রতিটি minterm-এর জন্য একটি লাইন দেয়, তাই যেকোনো function = তার minterm-লাইনগুলোর OR. S = D1 + D2 + D4 + D7, Cout = D3 + D5 + D6 + D7 — দুটি ৪-ইনপুটের OR.
(মাঝারি) F(A, B, C, D) = Σm(0, 2, 5, 7, 8, 10, 13, 15)-এর minimum SOP কোনটি?
- A′B′ + AB
- B′D′ + B′D
- B′C′D′ + B′CD′ + BC′D + BCD
- B′D′ + BD
(সহজ) প্রতি gate এক একক delay আর ripple-carry-র সবচেয়ে খারাপ ক্ষেত্র 2n + 1 ধরলে ১৬ বিটের ripple-carry adder-এর worst-case delay কত?
- 33
- 16
- 32
- 8
৪ · মডিউল ৩ — Flip-flop, counter, FSM আর timing
ঝালিয়ে নিন: পর্ব ১৫ · Latch আর flip-flop, পর্ব ১৬ · Register আর counter, পর্ব ১৭ · Finite state machine, পর্ব ১৮ · Timing আর clock, পর্ব ১৯ · Traffic light আর vending machine.
Excitation (Q → Q+): D = Q+; T = Q ⊕ Q+; JK: 0→0 (0, X), 0→1 (1, X), 1→0 (X, 1), 1→1 (X, 0); SR: 0→0 (0, X), 0→1 (1, 0), 1→0 (0, 1), 1→1 (X, 0).
Mod-N counter: ⌈log2 N⌉টি flip-flop; অব্যবহৃত state don't care, কিন্তু শেষে দেখুন সেখান থেকে counter গোনার চক্রে ফেরে কি না — একে বলে self-starting নকশা। State assignment: s টি state-এ binary ⌈log2 s⌉টি flip-flop, one-hot s টি।
Timing: Tc ≥ tpcq + tpd + tsetup + tskew, fmax = 1/Tc,min; hold: tccq + tcd ≥ thold + tskew — এতে Tc নেই, তাই clock ধীর করে hold ঠিক হয় না।
৪.১(সহজ) একটি flip-flop-এর Q পরপর চারটি clock edge-এ 0 → 1 → 1 → 0 → 0 হতে হবে। প্রতিটি রূপান্তরে D, T, JK আর SR flip-flop-এর ইনপুট কী?
transition D T J K S R
0 -> 1 1 1 1 X 1 0
1 -> 1 1 0 X 0 X 0
1 -> 0 0 1 X 1 0 1
0 -> 0 0 0 0 X 0 XJK-র X-গুলো আসে কারণ দুটি ভিন্ন ইনপুটই একই রূপান্তর দেয় (যেমন 0 → 1-এ J = ১, K = ০ মানে set, আর J = K = ১ মানে toggle — দুটিতেই ১)। এই X-গুলোই JK দিয়ে নকশায় K-map ছোট করে। D: ১ ১ ০ ০; T: ১ ০ ১ ০; JK: (১, X) (X, ০) (X, ১) (০, X).
৪.২(মাঝারি) দুটি D flip-flop A, B আর ইনপুট x: A+ = A ⊕ (xB), B+ = B ⊕ x. AB = 00 থেকে শুরু করে x = 1, 1, 0, 1, 1 দিলে state-এর ক্রম কী? সার্কিটটি কী কাজ করে?
AB x A+ = A ^ (x&B) B+ = B ^ x next
00 1 0 1 01
01 1 1 0 10
10 0 1 0 10 (x = 0: hold)
10 1 1 1 11
11 1 0 0 00 (wraps)x = ১ হলে AB এক করে বাড়ে, x = ০ হলে থেমে থাকে — এটি একটি enable-সহ ২ বিটের up counter. ক্রম 00 → 01 → 10 → 10 → 11 → 00.
৪.৩(কঠিন) তিনটি T flip-flop (Q2 Q1 Q0, Q2 বড় বিট) দিয়ে 0 থেকে 5 পর্যন্ত গোনা synchronous mod-6 counter বানান। T ইনপুটের সমীকরণ কী, আর ভুলে 6 বা 7-এ পৌঁছালে কী হবে?
Q2Q1Q0 -> next T2 T1 T0 (T = Q xor Q+)
000 -> 001 0 0 1
001 -> 010 0 1 1
010 -> 011 0 0 1
011 -> 100 1 1 1
100 -> 101 0 0 1
101 -> 000 1 0 1
110, 111 X X X (don't care)
K-map with X at 6, 7: T0 = 1, T1 = Q2'Q0, T2 = Q1Q0 + Q2Q0
check unused: 110 -> T = 001 -> 111 ; 111 -> T = 101 -> 010 (back in the count)X দিয়ে K-map ছোট হলো, কিন্তু X-এর ঘরে hardware আসলে কিছু একটা করে — তাই শেষ লাইনের যাচাই জরুরি। এখানে 6 → 7 → 2, অর্থাৎ counter নিজে থেকেই গোনার চক্রে ফেরে, অর্থাৎ নকশাটি self-starting. T0 = ১, T1 = Q2′Q0, T2 = Q1Q0 + Q2Q0; self-starting.
৪.৪(মাঝারি) (ক) Asynchronous (ripple) mod-10 counter-এ কয়টি flip-flop, আর কোন state-এ clear দিতে হবে? (খ) ৮ MHz clock-এ ৩ বিটের binary counter-এর MSB-এর frequency কত?
(a) ceil(log2 10) = 4 flip-flops; count 0..9, clear at 10 = 1010
detect Q3 = 1 and Q1 = 1 -> NAND(Q3, Q1) to active-low clear
(b) each stage divides by 2: 8 MHz -> Q0 4 MHz -> Q1 2 MHz -> Q2 1 MHz(ক)-তে শুধু Q3 আর Q1 দেখলেই চলে, কারণ 0–9-এর মধ্যে আর কোনো সংখ্যায় দুটি একসাথে ১ নয় (11–15-এ পৌঁছানোর আগেই clear হয়ে যায়)। এই ধরনের clear একটি ক্ষণস্থায়ী 1010 state তৈরি করে — glitch, তাই synchronous নকশা নিরাপদ (পর্ব ১৬)। ৪টি flip-flop, 1010-এ clear; MSB ১ MHz.
৪.৫(মাঝারি) একটি FSM-এ ৫টি state. (ক) Binary আর one-hot encoding-এ কয়টি flip-flop? (খ) ৩ বিটে কতভাবে state বসানো যায়, আর বিট উল্টানো ও বিটের ক্রম বদলানোকে এক ধরলে কত? (গ) “1011” overlapping sequence detector-এ Moore আর Mealy-তে কয়টি state?
(a) binary: ceil(log2 5) = 3 one-hot: 5
(b) all assignments: 8!/(8-5)! = 8 x 7 x 6 x 5 x 4 = 6720
distinct (up to complementing / permuting bits): (2^3 - 1)! / ((2^3 - 5)! x 3!) = 5040 / 36 = 140
(c) Mealy: states for "", "1", "10", "101" -> 4 Moore: also "1011" (output state) -> 5(খ)-এর দ্বিতীয় সূত্রটি McCluskey-এর বলে পরিচিত গণনা: বিট উল্টানো বা কলাম অদলবদল করলে logic-এর খরচ একই থাকে, তাই সেগুলো আলাদা ধরা হয় না। Moore-এ output state-এর সাথে বাঁধা, তাই “পুরো মিলেছে” বোঝাতে একটি বাড়তি state লাগে। ৩ আর ৫টি flip-flop; ৬৭২০ বা ১৪০টি assignment; Mealy ৪, Moore ৫টি state.
৪.৬(কঠিন) Flip-flop: tpcq = ৫০, tccq = ৩০, tsetup = ৪০, thold = ৫০ ps. দুই register-এর মাঝে ৩২ বিটের বহুস্তর CLA (১২ gate × ২৫ ps). (ক) Skew ০ আর ২০ ps-এ fmax? (খ) সবচেয়ে ছোট পথ tcd = ১৫ ps, skew ২০ ps — hold ঠিক আছে? (গ) Skew ছাড়া ২ GHz-এ কত gate-স্তর রাখা যায়?
(a) tpd = 12 x 25 = 300 ps
skew 0 : Tc = 50 + 300 + 40 = 390 ps -> fmax = 2.564 GHz
skew 20: Tc = 50 + 300 + 40 + 20 = 410 ps -> fmax = 2.439 GHz
(b) slack = tccq + tcd - (thold + skew) = 30 + 15 - 70 = -25 ps -> FAIL
need tcd >= 40 ps: add about 25 ps of buffers on the short path
(c) Tc = 500 ps: tpd <= 500 - 50 - 40 = 410 ps -> floor(410 / 25) = 16 levels(খ)-তে clock ধীর করলেও কিছু বদলায় না — সূত্রে Tc নেই। একই adder ripple হলে tpd = ৬৫ × ২৫ = ১,৬২৫ ps, fmax মাত্র ০.৫৮৩ GHz. (ক) ২.৫৬৪ আর ২.৪৩৯ GHz; (খ) hold slack −২৫ ps, ব্যর্থ; (গ) ১৬টি স্তর।
// Adder delays (unit gate model of lesson 11) + setup/hold timing (lesson 18). Times in ps.
const ripple = n => 2 * n + 1; // worst case carry-out
const cla = n => 4 * Math.ceil(Math.log(n) / Math.log(4) - 1e-9); // multi-level CLA: 4 per level
const blocks = n => n / 2 + 2; // 4-bit CLA blocks chained like ripple
console.log(" n ripple CLA-blocks-rippled multi-level-CLA (gate delays)");
for (const n of [4, 16, 32, 64])
console.log(String(n).padStart(3), String(ripple(n)).padStart(7), String(blocks(n)).padStart(19), String(cla(n)).padStart(16));
const gate = 25; // assumed delay of one gate, ps
const FF = { tpcq: 50, tccq: 30, tsetup: 40, thold: 50 };
function setup(tpd, skew) {
const Tc = FF.tpcq + tpd + FF.tsetup + skew;
return `Tc,min = ${FF.tpcq} + ${tpd} + ${FF.tsetup} + ${skew} = ${Tc} ps -> fmax = ${(1000 / Tc).toFixed(3)} GHz`;
}
console.log("32-bit ripple :", setup(ripple(32) * gate, 0));
console.log("32-bit CLA :", setup(cla(32) * gate, 0));
console.log("CLA + skew 20 :", setup(cla(32) * gate, 20));
const holdSlack = (tcd, skew) => FF.tccq + tcd - (FF.thold + skew);
for (const tcd of [15, 40]) console.log(`hold: tcd=${tcd}, skew=20 -> slack ${holdSlack(tcd, 20)} ps ${holdSlack(tcd, 20) >= 0 ? "PASS" : "FAIL"}`);
const Tc2 = 1000 / 2; // reverse question: logic budget at 2 GHz
console.log(`2 GHz, skew 0: tpd <= ${Tc2 - FF.tpcq - FF.tsetup} ps = ${Math.floor((Tc2 - FF.tpcq - FF.tsetup) / gate)} gate levels`);আউটপুট:
n ripple CLA-blocks-rippled multi-level-CLA (gate delays)
4 9 4 4
16 33 10 8
32 65 18 12
64 129 34 12
32-bit ripple : Tc,min = 50 + 1625 + 40 + 0 = 1715 ps -> fmax = 0.583 GHz
32-bit CLA : Tc,min = 50 + 300 + 40 + 0 = 390 ps -> fmax = 2.564 GHz
CLA + skew 20 : Tc,min = 50 + 300 + 40 + 20 = 410 ps -> fmax = 2.439 GHz
hold: tcd=15, skew=20 -> slack -25 ps FAIL
hold: tcd=40, skew=20 -> slack 0 ps PASS
2 GHz, skew 0: tpd <= 410 ps = 16 gate levelsটেবিলটি প্রশ্ন ৩.৮-এর হুবহু: ৪ বিটে তিন নকশারই ৪ (ripple ৯), আর ৬৪ বিটে ১২৯ বনাম ১২. পরের তিন লাইন ৪.৬(ক): ripple-এ ১,৭১৫ ps (০.৫৮৩ GHz), CLA-তে ৩৯০ ps, skew ২০-এ ৪১০ ps (২.৪৩৯ GHz). Hold-এর লাইন দুটি দেখায় tcd ১৫ থেকে ৪০ ps করলে slack −২৫ থেকে ঠিক ০ — সীমানায় PASS. শেষ লাইন ৪.৬(গ)-এর ১৬টি স্তর।
(সহজ) 0 থেকে 11 পর্যন্ত গোনা একটি mod-12 counter-এ ন্যূনতম কয়টি flip-flop লাগে, আর কয়টি state অব্যবহৃত থাকে?
- ৩টি, ৪টি অব্যবহৃত
- ১২টি, ০টি অব্যবহৃত
- ৪টি, ৪টি অব্যবহৃত
- ৪টি, ১২টি অব্যবহৃত
(মাঝারি) tpcq = ৪০ ps, সবচেয়ে লম্বা logic-পথ ৩৬০ ps, tsetup = ৫০ ps, clock skew ৩০ ps (সবচেয়ে খারাপ দিকে)। fmax প্রায় কত?
- 2.5 GHz
- ≈ 2.083 GHz
- ≈ 2.222 GHz
- ≈ 2.778 GHz
৫ · মডিউল ৪ — গুণ, ভাগ আর floating point
ঝালিয়ে নিন: পর্ব ২০ · Integer যোগ-বিয়োগ, পর্ব ২১ · গুণ আর Booth, পর্ব ২২ · ভাগ, পর্ব ২৩ · IEEE 754, পর্ব ২৪ · Floating point-এর হিসাব.
Booth: (Q0, Q−1) = 10 → A = A − M, 01 → A = A + M, 00/11 → কিছু নয়; তারপর A:Q:Q−1-এর arithmetic right shift; n ধাপ পরে A:Q = গুণফল। যোগ-বিয়োগের সংখ্যা = multiplier-এ (ডানে একটি ০ জুড়ে) পাশাপাশি বিট বদলের সংখ্যা।
ভাগ: Restoring: shift, A − M, ঋণাত্মক হলে q0 = ০ আর A + M. Non-restoring: A ≥ ০ হলে shift আর A − M, নইলে shift আর A + M; শেষে A < ০ হলে একবার A + M.
IEEE 754 single: মান = (−১)s × 1.f × 2e − 127; e = ০ আর f ≠ ০ হলে subnormal 0.f × 2−126; e = ২৫৫: f = ০ মানে ±∞, নইলে NaN. Rounding: nearest, tie হলে even.
step pair operation A Q Q-1 0 initial 0000 1011 0 -M = 1001 + 1 = 1010 first pair (Q0, Q-1) = (1, 0)
step pair operation A Q Q-1
1 10 A = A - M 1010 1011 0 (0000 + 1010)
shift 1101 0101 1
step pair operation A Q Q-1
2 11 none 1101 0101 1
shift 1110 1010 1
step pair operation A Q Q-1
3 01 A = A + M 0100 1010 1 (1110 + 0110 = 1 0100, carry dropped)
shift 0010 0101 0
step pair operation A Q Q-1
4 10 A = A - M 1100 0101 0 (0010 + 1010)
shift 1110 0010 1
A:Q = 1110 0010
= -128 + 64 + 32 + 2 = -30 (6 x -5 = -30)
check: invert 0001 1101, +1 = 0001 1110 = 30
add/sub operations: 3 (sub, add, sub)
- শুরু। M = 0110 (৬), Q = 1011 (−৫), A = 0000, Q−1 = 0. −M আগে থেকে বের করে রাখুন: 0110 উল্টে 1001, +১ = 1010. প্রথম জোড়া (Q0, Q−1) = (1, 0).
- ধাপ ১ — বিয়োগ। (1, 0) মানে multiplier-এ ১-এর একটি সারি শুরু, তাই A = 0000 + 1010 = 1010. তারপর পুরো A:Q:Q−1 ডানে এক ঘর, A-র চিহ্ন-বিট ১ বাঁয়ে কপি: A = 1101, Q = 0101, Q−1 = 1.
- ধাপ ২ — শুধু shift. জোড়া (1, 1) — সারির মাঝখান, যোগ-বিয়োগ নেই। Arithmetic shift-এ A = 1110, আর A-র শেষ বিট ১ Q-এর বাঁয়ে ঢুকে Q = 1010, Q−1 = 1.
- ধাপ ৩ — যোগ। জোড়া (0, 1) — সারি শেষ, তাই A = 1110 + 0110 = 1 0100; বাইরের carry বাদ দিয়ে 0100. Shift: A = 0010 (চিহ্ন-বিট ০), Q = 0101, Q−1 = 0.
- ধাপ ৪ — আবার বিয়োগ। জোড়া (1, 0): A = 0010 + 1010 = 1100. Shift: A = 1110, Q = 0010, Q−1 = 1. চারটি ধাপ শেষ।
- ফল। A:Q = 1110 0010; MSB ১, তাই ঋণাত্মক: −১২৮ + ৬৪ + ৩২ + ২ = −৩০. কোনো চিহ্ন-সংশোধন লাগেনি। মোট তিনটি যোগ-বিয়োগ — multiplier 1011-এর ডানে ০ জুড়ে (1011 0) বিট বদলায় তিনবার।
৫.১(মাঝারি) ৪ বিটের Booth-এ 6 × (−5) আর (−7) × 3-এর ধাপ-টেবিল করুন। প্রতিটিতে কয়টি যোগ-বিয়োগ?
প্রথমটি ওপরের stepper-এ: A:Q = 1110 0010 = −৩০, তিনটি কাজ। দ্বিতীয়টি (M = 1001, −M = 0111, Q = 0011):
step pair operation then shift -> A Q Q-1
1 10 A = A - M 0011 1001 1
2 11 none 0001 1100 1
3 01 A = A + M 1101 0110 0
4 00 none 1110 1011 0
A:Q = 1110 1011 = -21Multiplier 0011-এ ১-এর একটিই সারি, তাই একটি বিয়োগ (সারির শুরুতে) আর একটি যোগ (শেষে)। −৩০ (৩টি কাজ) আর −২১ (২টি কাজ)।
৫.২(মাঝারি) ৮ বিটের radix-2 Booth-এ multiplier 0011 1100 আর 0101 0101-এ কয়টি যোগ-বিয়োগ লাগে? সাধারণ shift-add-এ কয়টি যোগ?
append Q-1 = 0 and count changes between neighbouring bits (right to left)
0011 1100 0 : changes at bit 2 (0->1: sub) and bit 6 (1->0: add) -> 2 ops
0101 0101 0 : every neighbouring pair differs -> 8 ops
shift-add : one add per 1 bit -> 4 and 4লম্বা ১-এর সারিতে Booth সস্তা (চারটি ১ = একটি বিয়োগ আর একটি যোগ), কিন্তু পালাক্রমের 0101…-এ সবচেয়ে খারাপ — n টি কাজ। এজন্যই বাস্তবে radix-4 Booth ব্যবহৃত হয় (পর্ব ২১)। Booth: ২ আর ৮; shift-add: ৪ আর ৪.
৫.৩(মাঝারি) ৪ বিটে restoring division দিয়ে 1011 ÷ 0011 (১১ ÷ ৩) করুন; A ৫ বিটের। প্রতিটি iteration-এর শেষে A আর Q কী, আর মোট কয়টি যোগ-বিয়োগ?
start A = 00000, Q = 1011, M = 00011
iter shift: A A - M decision A end Q end
1 1 -2 (11110) restore, q0 = 0 00001 0110
2 2 -1 (11111) restore, q0 = 0 00010 1100
3 5 2 q0 = 1 00010 1001
4 5 2 q0 = 1 00010 0011
quotient 0011 = 3, remainder 00010 = 2 check: 3 x 3 + 2 = 11চারটি বিয়োগ আর দুটি restore — ভাগফলের যতগুলো ০, ঠিক ততগুলো restore. ভাগফল ৩, ভাগশেষ ২; মোট ৬টি যোগ-বিয়োগ।
৫.৪(মাঝারি) একই ১১ ÷ ৩ non-restoring পদ্ধতিতে করুন। কয়টি যোগ-বিয়োগ বাঁচল?
iter rule (A before) op A after q0 Q end
1 A = 0 >= 0 A - M 11110 (-2) 0 0110
2 A = -2 < 0 A + M 11111 (-1) 0 1100
3 A = -1 < 0 A + M 00010 (2) 1 1001
4 A = 2 >= 0 A - M 00010 (2) 1 0011
final A = 2 >= 0 -> no correctionউদাহরণ: iteration ২-এ A = −২; shift করলে −৪ + ০ (Q-এর বাঁয়ের বিট) = −৪, তারপর + ৩ = −১. এক restore আর পরের বিয়োগ মিলে একটি যোগে নেমে আসে: 2(A + M) − M = 2A + M. একই ভাগফল ৩, ভাগশেষ ২; মোট ৪টি কাজ — ২টি কম।
// Booth (radix-2) multiplication and restoring / non-restoring division tracers, n-bit registers.
const bin = (x, n) => (x & ((1 << n) - 1)).toString(2).padStart(n, "0");
function booth(m, q, n) { // m, q: signed values that fit in n bits
const mask = (1 << n) - 1; let A = 0, Q = q & mask, Q1 = 0, ops = 0;
console.log(`Booth ${m} x ${q}: M=${bin(m, n)} -M=${bin(-m, n)} A Q Q-1`);
for (let i = 1; i <= n; i++) {
const pair = `${Q & 1}${Q1}`;
if (pair === "10") { A = (A - m) & mask; ops++; } else if (pair === "01") { A = (A + m) & mask; ops++; }
const act = pair === "10" ? "A=A-M" : pair === "01" ? "A=A+M" : "none ";
Q1 = Q & 1; Q = ((Q >> 1) | ((A & 1) << (n - 1))) & mask; A = ((A >> 1) | (A & (1 << (n - 1)))) & mask;
console.log(` step ${i} pair ${pair} ${act} then shift -> ${bin(A, n)} ${bin(Q, n)} ${Q1}`);
}
const p = (A << n) | Q, v = p & (1 << (2 * n - 1)) ? p - (1 << 2 * n) : p;
console.log(` A:Q = ${bin(A, n)} ${bin(Q, n)} = ${v} (check ${m * q}), add/sub ops = ${ops}`);
}
function divide(dividend, M, n, restoring) { // unsigned; A is kept as a signed number (n+1 bits)
let A = 0, Q = dividend, ops = 0;
console.log(`${restoring ? "Restoring" : "Non-restoring"} ${dividend} / ${M}`);
for (let i = 1; i <= n; i++) {
const sub = restoring || A >= 0; // non-restoring: subtract if A >= 0, else add
A = 2 * A + (Q >> (n - 1) & 1); Q = (Q << 1) & ((1 << n) - 1);
A = sub ? A - M : A + M; ops++; let note = "";
if (A >= 0) Q |= 1; else if (restoring) { A += M; ops++; note = " restore"; }
console.log(` iter ${i}: ${sub ? "A-M" : "A+M"} -> q0=${Q & 1}${note} A=${bin(A, n + 1)} (${A}) Q=${bin(Q, n)}`);
}
if (A < 0) { A += M; ops++; console.log(` final correction A+M -> A=${bin(A, n + 1)}`); }
console.log(` quotient ${Q}, remainder ${A}, add/sub ops = ${ops}`);
}
booth(6, -5, 4); booth(-7, 3, 4);
divide(11, 3, 4, true); divide(11, 3, 4, false);আউটপুট:
Booth 6 x -5: M=0110 -M=1010 A Q Q-1
step 1 pair 10 A=A-M then shift -> 1101 0101 1
step 2 pair 11 none then shift -> 1110 1010 1
step 3 pair 01 A=A+M then shift -> 0010 0101 0
step 4 pair 10 A=A-M then shift -> 1110 0010 1
A:Q = 1110 0010 = -30 (check -30), add/sub ops = 3
Booth -7 x 3: M=1001 -M=0111 A Q Q-1
step 1 pair 10 A=A-M then shift -> 0011 1001 1
step 2 pair 11 none then shift -> 0001 1100 1
step 3 pair 01 A=A+M then shift -> 1101 0110 0
step 4 pair 00 none then shift -> 1110 1011 0
A:Q = 1110 1011 = -21 (check -21), add/sub ops = 2
Restoring 11 / 3
iter 1: A-M -> q0=0 restore A=00001 (1) Q=0110
iter 2: A-M -> q0=0 restore A=00010 (2) Q=1100
iter 3: A-M -> q0=1 A=00010 (2) Q=1001
iter 4: A-M -> q0=1 A=00010 (2) Q=0011
quotient 3, remainder 2, add/sub ops = 6
Non-restoring 11 / 3
iter 1: A-M -> q0=0 A=11110 (-2) Q=0110
iter 2: A+M -> q0=0 A=11111 (-1) Q=1100
iter 3: A+M -> q0=1 A=00010 (2) Q=1001
iter 4: A-M -> q0=1 A=00010 (2) Q=0011
quotient 3, remainder 2, add/sub ops = 4Booth-এর প্রথম টেবিল stepper-এর প্রতিটি সারি মেলায় (1101 0101 1 → 1110 1010 1 → 0010 0101 0 → 1110 0010 1), দ্বিতীয়টি প্রশ্ন ৫.১-এর −২১. ভাগের দুই টেবিল ৫.৩ আর ৫.৪: restoring-এ “restore” লেখা দুটি সারি আর মোট ৬টি কাজ, non-restoring-এ ঋণাত্মক A (−২, −১) রেখে দিয়ে পরের ধাপে যোগ, মোট ৪টি কাজ। Restoring-এর A-তে restore-এর পরের মান দেখানো হয়েছে।
৫.৫(মাঝারি) −১২.৬২৫-কে IEEE 754 single precision-এ লিখুন — বিট আর hex দুই রূপে।
sign : negative -> s = 1
magnitude : 12.625 = 1100.101 = 1.100101 x 2^3
exponent : 3 + 127 = 130 = 1000 0010
fraction : 100101 followed by zeros (23 bits)
bits : 1 | 1000 0010 | 1001 0100 0000 0000 0000 000
hex : 1100 0001 0100 1010 0000 ... = 0xC14A0000Hidden bit (১.) জমা হয় না — fraction-এ শুধু দশমিক বিন্দুর পরের বিট। 0xC14A0000. ভাগ ২-এর C প্রোগ্রাম মেমরিতে এর byte দেখিয়েছে: 00 00 4A C1.
৫.৬(সহজ) IEEE 754 single-এর 0x3F600000 আর 0x42F70000-এর দশমিক মান কত?
0x3F600000 = 0 | 0111 1110 | 110 0000 ... e = 126 -> 2^-1 ; 1.11 (2) = 1.75 -> 0.875
0x42F70000 = 0 | 1000 0101 | 111 0111 0 ... e = 133 -> 2^6 ; 1.1110111 (2) = 1.9296875 -> 123.5Hex থেকে বিট লিখে প্রথম বিট চিহ্ন, পরের আট বিট exponent — 0x3F6…-এর ক্ষেত্রে exponent-এর আটটি বিট হলো 3F-এর শেষ সাত বিট আর 6-এর প্রথম বিট। ০.৮৭৫ আর ১২৩.৫.
৫.৭(মাঝারি) Single precision-এ এগুলো কী: 0x7F800000, 0xFF800001, 0x00000001, 0x00800000, 0x7F7FFFFF?
0x7F800000 e = 255, f = 0 -> +infinity
0xFF800001 e = 255, f != 0 -> NaN (sign bit does not matter)
0x00000001 e = 0, f = 1 -> smallest subnormal 2^-149 ~ 1.401 x 10^-45
0x00800000 e = 1, f = 0 -> smallest normal 2^-126 ~ 1.175 x 10^-38
0x7F7FFFFF e = 254, f = all ones -> largest finite (2 - 2^-23) x 2^127 ~ 3.403 x 10^38Subnormal-এ hidden bit ০ আর exponent −১২৬ (−১২৭ নয়) — এজন্যই normal আর subnormal-এর মাঝে ফাঁক থাকে না — একে বলে gradual underflow. +∞, NaN, ক্ষুদ্রতম subnormal, ক্ষুদ্রতম normal, বৃহত্তম সসীম সংখ্যা।
৫.৮(কঠিন) Round-to-nearest-even ধরে single precision-এ: (ক) ০.১-এর bit pattern আর জমা থাকা আসল মান কী? (খ) ১,৬৭,৭৭,২১৭ (224 + 1) জমা করলে কী থাকে? (গ) 1 + 2−24?
(a) 0.1 = 1.1001 1001 1001 ... x 2^-4 ; e = 123
23 kept bits ...1001 1001 100 | next bits 1100... > half -> round up -> ...1101
pattern 0x3DCCCCCD ; stored value 0.100000001490116... (about 1.49 x 10^-9 too big)
(b) 2^24 + 1 needs 25 significant bits; it lies exactly halfway between 2^24 and 2^24 + 2
tie -> even significand -> 16777216
(c) 1 + 2^-24 is halfway between 1 and 1 + 2^-23 -> tie -> even -> 1Single-এ ২৪টি significant bit (hidden bit-সহ), তাই 224-এর পরে সব বিজোড় পূর্ণসংখ্যা হারায়। (খ) আর (গ) একই নিয়মের উদাহরণ: ঠিক মাঝখানে পড়লে যে দিকে শেষ বিট ০, সেদিকে। (ক) 0x3DCCCCCD ≈ ০.১০০০০০০০১৪৯; (খ) ১,৬৭,৭৭,২১৬; (গ) ১.
৫.৯(মাঝারি) Floating-point যোগের ধাপ দেখিয়ে ৯.৭৫ + ০.৫৬২৫ করুন, আর ফল single-এ লিখুন।
9.75 = 1001.11 = 1.00111 x 2^3
0.5625 = 0.1001 = 1.001 x 2^-1
align : shift the smaller right by 3 - (-1) = 4 -> 0.0001001 x 2^3
add : 1.0011100 + 0.0001001 = 1.0100101 x 2^3 (already normalised)
round : 7 fraction bits fit in 23 -> exact
result : 1010.0101 = 10.3125 ; e = 130 -> 0 | 1000 0010 | 0100 1010 0 ... = 0x41250000ক্রম: exponent মেলানো (ছোটটিকে ডানে সরানো) → significand যোগ → normalise → round → overflow/underflow যাচাই। সরানোর সময় যে বিট বেরিয়ে যায়, hardware সেগুলো guard, round আর sticky বিটে ধরে রাখে (পর্ব ২৪)। ১০.৩১২৫ = 0x41250000.
// IEEE 754 single precision: encode, decode, special values and rounding (float32 via DataView).
const dv = new DataView(new ArrayBuffer(4));
const hex = u => "0x" + u.toString(16).toUpperCase().padStart(8, "0");
function encode(x) {
dv.setFloat32(0, x); const u = dv.getUint32(0);
const s = u >>> 31, e = (u >>> 23) & 0xFF, f = u & 0x7FFFFF;
console.log(`${String(x).padEnd(12)} -> ${hex(u)} sign ${s} exp ${e.toString(2).padStart(8, "0")} (${e}, 2^${e - 127}) frac ${f.toString(2).padStart(23, "0")}`);
}
function decode(u) {
const s = u >>> 31, e = (u >>> 23) & 0xFF, f = u & 0x7FFFFF;
let kind = "normal";
if (e === 255) kind = f ? "NaN" : "infinity"; else if (e === 0) kind = f ? "subnormal" : "zero";
dv.setUint32(0, u);
console.log(`${hex(u)} -> ${kind.padEnd(9)} value ${dv.getFloat32(0)}`);
}
[-12.625, 0.1, 10.3125, 16777217, 1].forEach(encode);
[0x3F600000, 0x42F70000, 0x7F800000, 0xFF800001, 0x00000001, 0x00800000, 0x7F7FFFFF].forEach(decode);
const f32 = Math.fround;
console.log("0.1 stored exactly as", f32(0.1).toPrecision(20), " error", (f32(0.1) - 0.1).toExponential(3));
console.log("16777217 stored as", f32(16777217), " (2^24 + 1 needs 25 significant bits; tie -> even)");
console.log("9.75 + 0.5625 =", f32(f32(9.75) + f32(0.5625)), " 1 + 2^-24 =", f32(1 + 2 ** -24), " 1 + 2^-23 =", f32(1 + 2 ** -23));
console.log("1e38 * 10 =", f32(1e38 * 10), " 0 / 0 =", 0 / 0, " 1 / -0 =", 1 / -0);আউটপুট:
-12.625 -> 0xC14A0000 sign 1 exp 10000010 (130, 2^3) frac 10010100000000000000000
0.1 -> 0x3DCCCCCD sign 0 exp 01111011 (123, 2^-4) frac 10011001100110011001101
10.3125 -> 0x41250000 sign 0 exp 10000010 (130, 2^3) frac 01001010000000000000000
16777217 -> 0x4B800000 sign 0 exp 10010111 (151, 2^24) frac 00000000000000000000000
1 -> 0x3F800000 sign 0 exp 01111111 (127, 2^0) frac 00000000000000000000000
0x3F600000 -> normal value 0.875
0x42F70000 -> normal value 123.5
0x7F800000 -> infinity value Infinity
0xFF800001 -> NaN value NaN
0x00000001 -> subnormal value 1.401298464324817e-45
0x00800000 -> normal value 1.1754943508222875e-38
0x7F7FFFFF -> normal value 3.4028234663852886e+38
0.1 stored exactly as 0.10000000149011611938 error 1.490e-9
16777217 stored as 16777216 (2^24 + 1 needs 25 significant bits; tie -> even)
9.75 + 0.5625 = 10.3125 1 + 2^-24 = 1 1 + 2^-23 = 1.0000001192092896
1e38 * 10 = Infinity 0 / 0 = NaN 1 / -0 = -Infinityপ্রথম পাঁচ লাইন encoder: −১২.৬২৫ = 0xC14A0000 (৫.৫), ০.১ = 0x3DCCCCCD — fraction-এর শেষ বিট …1101, rounding-এ ওপরে ওঠা (৫.৮), ১০.৩১২৫ = 0x41250000 (৫.৯), আর 224 + 1-এর fraction সব শূন্য — অর্থাৎ ঠিক 224. পরের সাত লাইন decoder: ০.৮৭৫, ১২৩.৫, তারপর ৫.৭-এর বিশেষ মানগুলো। শেষ চার লাইনে rounding-এর প্রমাণ — 1 + 2−24 হারিয়ে যায়, 1 + 2−23 টিকে থাকে; আর overflow-এ Infinity, ০/০-তে NaN, ১/(−০)-তে −Infinity. Math.fround একটি double-কে নিকটতম float32-এ নামায়।
(মাঝারি) IEEE 754 single precision-এর 0xC0A00000-এর মান কত?
- +5.0
- −2.5
- −10.0
- −5.0
(মাঝারি) ৮ বিটের radix-2 Booth-এ multiplier 0111 1000 হলে কয়টি যোগ বা বিয়োগ হবে?
- 2
- 4
- 1
- 3
৬ · মডিউল ৫–৬ — RISC-V encoding, datapath আর pipeline
ঝালিয়ে নিন: পর্ব ২৬ · RISC-V-এর instruction, পর্ব ২৭ · Instruction format আর encoding, পর্ব ২৮ · Addressing mode, পর্ব ৩২ · Single-cycle datapath, পর্ব ৩৩ · Control unit, পর্ব ৩৫ · Pipelining, পর্ব ৩৬ · Pipeline hazard, পর্ব ৩৭ · Branch prediction.
Format (বিট ৩১ → ০): R: funct7 | rs2 | rs1 | funct3 | rd | opcode. I: imm[11:0] | rs1 | funct3 | rd | opcode. S: imm[11:5] | rs2 | rs1 | funct3 | imm[4:0] | opcode. B: imm[12] | imm[10:5] | rs2 | rs1 | funct3 | imm[4:1] | imm[11] | opcode. U: imm[31:12] | rd | opcode. J: imm[20] | imm[10:1] | imm[11] | imm[19:12] | rd | opcode.
Opcode: R 0110011, I-ALU 0010011, load 0000011, store 0100011, branch 1100011, lui 0110111, jal 1101111. Branch offset = target − PC (byte-এ, জোড়), পরিসর −৪০৯৬ থেকে +৪০৯৪; jal ±১ MiB.
Pipeline: k ধাপে n টি instruction = k + n − 1 cycle (stall ছাড়া); CPI = 1 + Σ(হার × stall); load-use forwarding-সহও ১ stall; branch: CPI = 1 + fbranch × m × penalty.
Instruction encoding
৬.১(সহজ) add x5, x6, x7-কে ৩২ বিটের machine code-এ লিখুন; add-এর funct7 = 0000000 আর funct3 = 000.
funct7 rs2 rs1 funct3 rd opcode
0000000 00111 00110 000 00101 0110011
-> 0000 0000 0111 0011 0000 0010 1011 0011 = 0x007302B3সাধারণ ভুল: rs1 আর rs2-এর জায়গা উল্টানো। Assembly-তে প্রথম উৎস rs1, কিন্তু বিটে rs2 বাঁয়ে বসে। 0x007302B3.
৬.২(মাঝারি) Encode করুন: addi x10, x10, -4, lw x6, -12(x2) আর sw x5, 20(x2); lw আর sw দুটিরই funct3 = 010.
addi: imm -4 = 1111 1111 1100 | rs1 01010 | 000 | rd 01010 | 0010011 -> 0xFFC50513
lw : imm -12 = 1111 1111 0100 | rs1 00010 | 010 | rd 00110 | 0000011 -> 0xFF412303
sw : imm 20 = 0000000 10100 -> imm[11:5] 0000000 | rs2 00101 | rs1 00010 | 010 | imm[4:0] 10100 | 0100011
-> 0x00512A23S-type-এ immediate দুই টুকরা, কারণ RISC-V সব format-এ rs1 আর rs2 একই জায়গায় রাখে — decoder register পড়া শুরু করতে পারে format জানার আগেই (পর্ব ২৭)। 0xFFC50513, 0xFF412303, 0x00512A23.
৬.৩(কঠিন) (ক) ঠিকানা 0x1000-এ beq x5, x6, L, আর L = 0x1010. Offset আর machine code কত? (খ) bne x10, x0, -8-এর code কত? (গ) beq কত দূর পর্যন্ত লাফাতে পারে?
(a) offset = 0x1010 - 0x1000 = +16 = 0 0000 0001 0000 (13-bit, bit 0 not stored)
imm[12]=0 imm[10:5]=000000 | rs2 00110 | rs1 00101 | 000 | imm[4:1]=1000 imm[11]=0 | 1100011
-> 0x00628863
(b) -8 = 1 1111 1111 1000 -> imm[12]=1 imm[10:5]=111111 | 00000 | 01010 | 001 | 1100 1 | 1100011
-> 0xFE051CE3
(c) 13-bit signed, even: -4096 .. +4094 bytesOffset গোনা হয় branch instruction-এর নিজের ঠিকানা থেকে (PC + 4 থেকে নয়, যা কিছু পুরোনো MIPS-এর বইয়ে দেখবেন)। বিট ০ সবসময় ০ বলে জমা হয় না, তাই ১২টি বিটে ১৩ বিটের পরিসর। (ক) +১৬, 0x00628863; (খ) 0xFE051CE3; (গ) −৪০৯৬ থেকে +৪০৯৪ byte.
৬.৪(মাঝারি) (ক) x5-এ ধ্রুবক 0x12345FFF আনতে lui আর addi-তে কোন মান দেবেন? (খ) jal x1, +2048-এর code কত?
(a) low 12 bits 0xFFF = -1 after sign extension, so add 1 to the upper part
lui x5, 0x12346 -> x5 = 0x12346000 code 0x123462B7
addi x5, x5, -1 -> x5 = 0x12345FFF code 0xFFF28293
(b) 2048 = imm[11] = 1, all other bits 0 -> bit 20 of the word = 1
imm[20]=0 imm[10:1]=0 imm[11]=1 imm[19:12]=0 | rd 00001 | 1101111 -> 0x001000EF(ক) পরীক্ষার প্রিয় ফাঁদ: lui 0x12345 আর addi 0xFFF লিখলে addi-র immediate −১ হয়ে ফল 0x12344FFF. lui 0x12346 + addi −১; jal = 0x001000EF.
৬.৫(মাঝারি) 0x40B50533 decode করুন।
0100 0000 1011 0101 0000 0101 0011 0011
opcode 0110011 -> R-type
funct7 0100000, rs2 01011 = x11, rs1 01010 = x10, funct3 000, rd 01010 = x10
funct7 0100000 + funct3 000 -> subadd আর sub-এর পার্থক্য শুধু funct7-এর বিট ৩০. sub x10, x10, x11.
// RV32I encoder for R/I/S/B/U/J formats + a field decoder. Immediates are signed byte offsets.
const b = (v, hi, lo) => (v >> lo) & ((1 << (hi - lo + 1)) - 1); // bits hi..lo of v
const hex = w => "0x" + (w >>> 0).toString(16).toUpperCase().padStart(8, "0");
const enc = {
R: (op, f3, f7, rd, rs1, rs2) => f7 << 25 | rs2 << 20 | rs1 << 15 | f3 << 12 | rd << 7 | op,
I: (op, f3, rd, rs1, imm) => (imm & 0xFFF) << 20 | rs1 << 15 | f3 << 12 | rd << 7 | op,
S: (op, f3, rs1, rs2, imm) => b(imm, 11, 5) << 25 | rs2 << 20 | rs1 << 15 | f3 << 12 | b(imm, 4, 0) << 7 | op,
B: (op, f3, rs1, rs2, imm) => b(imm, 12, 12) << 31 | b(imm, 10, 5) << 25 | rs2 << 20 | rs1 << 15 |
f3 << 12 | b(imm, 4, 1) << 8 | b(imm, 11, 11) << 7 | op,
U: (op, rd, imm20) => (imm20 & 0xFFFFF) << 12 | rd << 7 | op,
J: (op, rd, imm) => b(imm, 20, 20) << 31 | b(imm, 10, 1) << 21 | b(imm, 11, 11) << 20 | b(imm, 19, 12) << 12 | rd << 7 | op,
};
const sx = (v, bits) => (v << (32 - bits)) >> (32 - bits); // sign-extend
function decode(w) {
const op = b(w, 6, 0), rd = b(w, 11, 7), f3 = b(w, 14, 12), rs1 = b(w, 19, 15), rs2 = b(w, 24, 20);
const fmt = { 0x33: "R", 0x13: "I", 0x03: "I", 0x23: "S", 0x63: "B", 0x37: "U", 0x6F: "J" }[op];
const imm = { R: 0, I: sx(b(w, 31, 20), 12), S: sx(b(w, 31, 25) << 5 | rd, 12),
B: sx(b(w, 31, 31) << 12 | b(w, 7, 7) << 11 | b(w, 30, 25) << 5 | b(w, 11, 8) << 1, 13),
U: b(w, 31, 12), J: sx(b(w, 31, 31) << 20 | b(w, 19, 12) << 12 | b(w, 20, 20) << 11 | b(w, 30, 21) << 1, 21) }[fmt];
const f = { R: `rd=x${rd} rs1=x${rs1} rs2=x${rs2} f3=${f3} f7=${b(w, 31, 25)}`, I: `rd=x${rd} rs1=x${rs1} f3=${f3} imm=${imm}`,
S: `rs1=x${rs1} rs2=x${rs2} f3=${f3} imm=${imm}`, B: `rs1=x${rs1} rs2=x${rs2} f3=${f3} offset=${imm}`,
U: `rd=x${rd} imm20=0x${imm.toString(16).toUpperCase()}`, J: `rd=x${rd} offset=${imm}` }[fmt];
console.log(` ${(w >>> 0).toString(2).padStart(32, "0").replace(/(.{4})(?=.)/g, "$1 ")} -> ${fmt}: ${f}`);
}
const list = [["add x5,x6,x7", enc.R(0x33, 0, 0, 5, 6, 7)], ["sub x10,x10,x11", enc.R(0x33, 0, 0x20, 10, 10, 11)],
["addi x10,x10,-4", enc.I(0x13, 0, 10, 10, -4)], ["lw x6,-12(x2)", enc.I(0x03, 2, 6, 2, -12)],
["sw x5,20(x2)", enc.S(0x23, 2, 2, 5, 20)], ["beq x5,x6,+16", enc.B(0x63, 0, 5, 6, 16)],
["bne x10,x0,-8", enc.B(0x63, 1, 10, 0, -8)], ["lui x5,0x12346", enc.U(0x37, 5, 0x12346)],
["addi x5,x5,-1", enc.I(0x13, 0, 5, 5, -1)], ["jal x1,+2048", enc.J(0x6F, 1, 2048)]];
for (const [asm, w] of list) { console.log(asm.padEnd(16) + hex(w)); decode(w); }আউটপুট:
add x5,x6,x7 0x007302B3
0000 0000 0111 0011 0000 0010 1011 0011 -> R: rd=x5 rs1=x6 rs2=x7 f3=0 f7=0
sub x10,x10,x11 0x40B50533
0100 0000 1011 0101 0000 0101 0011 0011 -> R: rd=x10 rs1=x10 rs2=x11 f3=0 f7=32
addi x10,x10,-4 0xFFC50513
1111 1111 1100 0101 0000 0101 0001 0011 -> I: rd=x10 rs1=x10 f3=0 imm=-4
lw x6,-12(x2) 0xFF412303
1111 1111 0100 0001 0010 0011 0000 0011 -> I: rd=x6 rs1=x2 f3=2 imm=-12
sw x5,20(x2) 0x00512A23
0000 0000 0101 0001 0010 1010 0010 0011 -> S: rs1=x2 rs2=x5 f3=2 imm=20
beq x5,x6,+16 0x00628863
0000 0000 0110 0010 1000 1000 0110 0011 -> B: rs1=x5 rs2=x6 f3=0 offset=16
bne x10,x0,-8 0xFE051CE3
1111 1110 0000 0101 0001 1100 1110 0011 -> B: rs1=x10 rs2=x0 f3=1 offset=-8
lui x5,0x12346 0x123462B7
0001 0010 0011 0100 0110 0010 1011 0111 -> U: rd=x5 imm20=0x12346
addi x5,x5,-1 0xFFF28293
1111 1111 1111 0010 1000 0010 1001 0011 -> I: rd=x5 rs1=x5 f3=0 imm=-1
jal x1,+2048 0x001000EF
0000 0000 0001 0000 0000 0000 1110 1111 -> J: rd=x1 offset=2048প্রতিটি instruction দুবার যাচাই হয়েছে: encoder hex দেয়, আর decoder সেই hex থেকে field আবার তোলে — offset −৮ আর +১৬, imm −৪ আর −১২ ঠিকঠাক ফিরে এসেছে। B আর J format-এ বিটের এলোমেলো ক্রমই সবচেয়ে বেশি ভুলের উৎস; b(imm, 11, 11) << 7-এর মতো লাইনগুলো ওপরের কার্ডের ক্রমের হুবহু অনুবাদ।
Datapath আর pipeline
৬.৬(মাঝারি) Single-cycle datapath-এ unit-এর delay: instruction memory ২৫০, register পড়া ১৫০, ALU ২০০, data memory ৩০০, register-এ লেখা ৫০ ps (mux আর বাকি নগণ্য)। (ক) lw, sw, R-type আর beq-এর দরকারি সময় আর clock? (খ) একই unit দিয়ে ৫ ধাপের pipeline, প্রতিটি pipeline register-এ ২০ ps — clock আর দীর্ঘমেয়াদি speedup?
(a) lw = 250 + 150 + 200 + 300 + 50 = 950 ps (critical path)
sw = 250 + 150 + 200 + 300 = 900 ps
R = 250 + 150 + 200 + 50 = 650 ps
beq = 250 + 150 + 200 = 600 ps
Tc = 950 ps -> f = 1.053 GHz
(b) stage = slowest stage + overhead = 300 + 20 = 320 ps -> 3.125 GHz
speedup (one instruction per cycle, many instructions) = 950 / 320 = 2.969Speedup ৫ নয়, কারণ ধাপগুলো অসমান (৩০০ বনাম ৫০) আর register-এর খরচ আছে। (ক) ৯৫০/৯০০/৬৫০/৬০০ ps, Tc = ৯৫০ ps; (খ) ৩২০ ps, প্রায় ২.৯৭ গুণ।
৬.৭(সহজ) ৫ ধাপের আদর্শ pipeline-এ (hazard নেই) ১০০টি instruction-এ কত cycle? একই ধাপ-সময়ের non-pipelined যন্ত্রের (প্রতিটি instruction ৫ cycle) তুলনায় speedup কত, আর n → ∞-এ সীমা?
cycles = k + n - 1 = 5 + 100 - 1 = 104
speedup = n k / (k + n - 1) = 500 / 104 = 4.808 limit (n -> inf) = k = 5প্রথম instruction শেষ হতে ৫ cycle (pipeline ভরা), তারপর প্রতি cycle-এ একটি করে বাকি ৯৯টি। ১০৪ cycle, ≈ ৪.৮০৮ গুণ, সীমা ৫.
৬.৮(মাঝারি) ক্রম: lw x1,0(x2); add x3,x1,x4; sub x5,x3,x6; sw x5,4(x2). (ক) Forwarding ছাড়া আর (খ) পূর্ণ forwarding-সহ কয়টি stall আর মোট কত cycle? (গ) ৩০% instruction load, তার ৪০%-এর ঠিক পরেই ফল ব্যবহার হলে forwarding-সহ CPI?
each instruction uses the result of the one just before it (distance d = 1)
(a) no forwarding: stall = max(0, 3 - d) = 2 per pair, 3 pairs -> 6 stalls
cycles = 5 + 4 - 1 + 6 = 14
(b) forwarding: only lw -> add is a load-use hazard -> 1 stall
cycles = 5 + 4 - 1 + 1 = 9
(c) CPI = 1 + 0.30 x 0.40 x 1 = 1.12Forwarding ছাড়া ২ stall-এর কারণ: add-কে ID-তে x1 পড়তে হবে lw-এর WB-এর cycle-এ (প্রথম অর্ধে লেখা, পরের অর্ধে পড়া)। Forwarding থাকলে lw-এর ফল MEM-এর শেষে আসে, তাই add-এর EX এক cycle পেছায়। sw-এর x5 EX/MEM থেকে forward হয়, stall লাগে না। (ক) ৬ stall, ১৪ cycle; (খ) ১ stall, ৯ cycle; (গ) CPI ১.১২.
৬.৯(মাঝারি) ১৮% instruction branch, তার ৬৫% taken, branch MEM-এ resolve হয় (penalty ৩ cycle). (ক) সব branch-এ stall, (খ) predict-not-taken, (গ) ৯২% নির্ভুল ২-বিট predictor — প্রতিটিতে CPI কত (base CPI ১)?
CPI = 1 + f x m x P
(a) stall : 1 + 0.18 x 1.00 x 3 = 1.540
(b) predict-NT : 1 + 0.18 x 0.65 x 3 = 1.351
(c) 2-bit, 92% : 1 + 0.18 x 0.08 x 3 = 1.0432Predict-not-taken-এ শুধু taken branch-গুলো ভুল, তাই m = taken-এর হার। এর সাথে data hazard-এর stall থাকলে যোগ হয়: যেমন (খ)-তে ৬.৮(গ)-এর ০.১২ যোগে CPI ১.৪৭১. ১.৫৪, ১.৩৫১ আর ১.০৪৩২.
৬.১০(কঠিন) ভেতরের loop ৫ বার চলে, তাই তার branch-এর ফল T T T T N; বাইরের loop একে ৩ বার চালায় (মোট ১৫টি ফল)। ২-বিট saturating counter শুরু 01 (weakly not-taken) থেকে, আর ১-বিট predictor শুরু N থেকে। প্রতিটির ভুল কয়টি?
outcome T T T T N | T T T T N | T T T T N
2-bit state 01 10 11 11 11 |10 11 11 11 11 |10 11 11 11 11 (state before each branch)
2-bit pred N T T T T | T T T T T | T T T T T
x . . . x | . . . . x | . . . . x -> 4 misses
1-bit pred N T T T T | N T T T T | N T T T T
x . . . x | x . . . x | x . . . x -> 6 misses২-বিট counter বেরোনোর N-এ নামে 10-এ, কিন্তু তখনো T বলে — তাই পরের প্রবেশের প্রথম T ঠিক। শুধু একেবারে প্রথম T-তে (ঠান্ডা শুরু) বাড়তি একটি ভুল। ২-বিট ৪টি ভুল (নির্ভুলতা ১১/১৫ ≈ ৭৩.৩%), ১-বিট ৬টি, নির্ভুলতা ৯/১৫ = ৬০ শতাংশ।
// Single-cycle vs 5-stage pipeline, hazard stalls, branch CPI and a 2-bit predictor (lessons 32-37).
const st = { IF: 250, ID: 150, EX: 200, MEM: 300, WB: 50 }; // ps; WB = register write (setup)
const need = { lw: ["IF", "ID", "EX", "MEM", "WB"], sw: ["IF", "ID", "EX", "MEM"], R: ["IF", "ID", "EX", "WB"], beq: ["IF", "ID", "EX"] };
for (const [k, v] of Object.entries(need)) console.log(`single-cycle ${k.padEnd(3)} needs ${v.reduce((s, x) => s + st[x], 0)} ps`);
const Tsc = 950, Tp = Math.max(...Object.values(st)) + 20; // +20 ps pipeline-register overhead
console.log(`Tc single = ${Tsc} ps, pipelined stage = ${Tp} ps, long-run speedup = ${(Tsc / Tp).toFixed(3)}`);
const cycles = (k, n, stalls = 0) => k + n - 1 + stalls;
console.log(`k=5, n=100: ${cycles(5, 100)} cycles, speedup vs 5 cycles each = ${(500 / cycles(5, 100)).toFixed(3)}`);
// lw x1,0(x2); add x3,x1,x4; sub x5,x3,x6; sw x5,4(x2) : each depends on the one before (distance 1)
const deps = [{ d: 1, load: true }, { d: 1, load: false }, { d: 1, load: false }];
const noFwd = deps.reduce((s, x) => s + Math.max(0, 3 - x.d), 0); // write first half, read second half
const fwd = deps.reduce((s, x) => s + (x.load && x.d === 1 ? 1 : 0), 0);
console.log(`4 instr: no forwarding ${noFwd} stalls -> ${cycles(5, 4, noFwd)} cycles; forwarding ${fwd} -> ${cycles(5, 4, fwd)} cycles`);
console.log("load-use CPI = 1 + 0.30 x 0.40 x 1 =", (1 + 0.3 * 0.4).toFixed(2));
const bcpi = (f, miss, pen) => 1 + f * miss * pen;
console.log(`branch 18%, 65% taken, penalty 3: stall ${bcpi(0.18, 1, 3).toFixed(4)} predict-NT ${bcpi(0.18, 0.65, 3).toFixed(4)} 2-bit 92% ${bcpi(0.18, 0.08, 3).toFixed(4)}`);
function predict(outcomes, two, start) { // 2-bit counter 0..3 or 1-bit 0..1
let s = start, miss = 0, trace = "";
for (const t of outcomes) {
const p = two ? s >= 2 : s === 1; if (p !== t) miss++;
trace += (p === t ? "." : "x");
s = two ? (t ? Math.min(3, s + 1) : Math.max(0, s - 1)) : (t ? 1 : 0);
}
return `${miss} misses ${trace}`;
}
const inner = [...Array(3)].flatMap(() => [true, true, true, true, false]); // inner loop of 5, run 3 times
console.log("2-bit from 01:", predict(inner, true, 1), " 1-bit from N:", predict(inner, false, 0));আউটপুট:
single-cycle lw needs 950 ps
single-cycle sw needs 900 ps
single-cycle R needs 650 ps
single-cycle beq needs 600 ps
Tc single = 950 ps, pipelined stage = 320 ps, long-run speedup = 2.969
k=5, n=100: 104 cycles, speedup vs 5 cycles each = 4.808
4 instr: no forwarding 6 stalls -> 14 cycles; forwarding 1 -> 9 cycles
load-use CPI = 1 + 0.30 x 0.40 x 1 = 1.12
branch 18%, 65% taken, penalty 3: stall 1.5400 predict-NT 1.3510 2-bit 92% 1.0432
2-bit from 01: 4 misses x...x....x....x 1-bit from N: 6 misses x...xx...xx...xপ্রথম পাঁচ লাইন ৬.৬: ৯৫০, ৯০০, ৬৫০, ৬০০ ps আর ৩২০ ps-এর ধাপে ২.৯৬৯ গুণ। তারপর ৬.৭-এর ১০৪ cycle (৪.৮০৮), ৬.৮-এর ১৪ বনাম ৯ cycle আর CPI ১.১২, ৬.৯-এর তিনটি CPI. শেষ লাইনে predictor-এর ভুলের নকশা: “x” ভুল, “.” ঠিক — ২-বিটের x...x....x....x (৪টি) আর ১-বিটের x...xx...xx...x (৬টি), ওপরের টেবিলের সাথে হুবহু।
(মাঝারি) RISC-V-এ addi x1, x0, 5-এর ৩২ বিটের machine code কোনটি (opcode 0010011, funct3 000)?
- 0x00508013
- 0x00500093
- 0x005000B3
- 0x00A00093
(সহজ) Hazard ছাড়া একটি ৫ ধাপের pipeline-এ ২০০টি instruction শেষ হতে কত cycle লাগে?
- 1000
- 200
- 204
- 205
৭ · মডিউল ৭ — Tomasulo, superscalar আর SIMD
ঝালিয়ে নিন: পর্ব ৩৯ · Superscalar আর VLIW, পর্ব ৪০ · Out-of-order আর Tomasulo, পর্ব ৪২ · SIMD আর vector, পর্ব ৪৩ · Hardware multithreading.
৭.১(কঠিন) Tomasulo, ভাগ ১-এর cycle-নিয়ম, একটি CDB; প্রতি cycle-এ একটি issue; RS: Load ২, Add ৩, Mult ২ (কখনো ভরে যায় না)। Latency: fld ২, fadd.d/fsub.d ২, fmul.d ৬. প্রোগ্রাম: I1 fld f2,0(x1); I2 fmul.d f4,f2,f6; I3 fadd.d f8,f2,f10; I4 fsub.d f2,f8,f4; I5 fadd.d f6,f8,f10. প্রতিটির issue, execute আর write cycle বের করুন।
instr issue waits for execute write (CDB)
I1 fld f2,0(x1) 1 - 2-3 4
I2 fmul f4,f2,f6 2 f2 from I1 (4) 5-10 11
I3 fadd f8,f2,f10 3 f2 from I1 (4) 5-6 7
I4 fsub f2,f8,f4 4 f8 (7), f4 (11) 12-13 14
I5 fadd f6,f8,f10 5 f8 from I3 (7) 8-9 10
CDB writes at 4, 7, 10, 11, 14 -> no conflict; all done after cycle 14দুটি শিক্ষা। (১) I5 শেষ হয় I2-র আগে — পেছনের instruction সামনের ধীরজনকে টপকায়। (২) I5 f6-এ লেখে cycle ১০-এ, অথচ I2 f6 পড়ে; WAR ঝামেলা হয় না, কারণ I2 issue-এর সময়েই (cycle ২) f6-এর মান RS-এ কপি করে নিয়েছিল। I4-ও f2-এ লেখে (I1-এর সাথে WAW), কিন্তু register status-এ শেষ লেখক I4-এর tag, তাই f2-এ শেষে I4-এর মান থাকে। Write cycle: ৪, ১১, ৭, ১৪, ১০; মোট ১৪ cycle.
৭.২(মাঝারি) একটি ৪-wide superscalar প্রসেসর ১২০০টি instruction ৫০০ cycle-এ শেষ করল। IPC, CPI আর issue slot-এর ব্যবহার কত? আদর্শে ন্যূনতম কত cycle লাগত?
IPC = 1200 / 500 = 2.4 CPI = 500 / 1200 = 0.4167
slots used = 1200 / (4 x 500) = 60%
ideal (4 per cycle) = 1200 / 4 = 300 cyclesSuperscalar-এ CPI ১-এর নিচে নামে, তাই এখানে IPC-তে কথা বলা সুবিধাজনক। বাকি ৪০% slot dependence, branch আর cache miss-এ নষ্ট (পর্ব ৩৯)। IPC ২.৪, CPI ≈ ০.৪১৭, ৬০%; আদর্শ ৩০০ cycle.
৭.৩(মাঝারি) ১০০০টি করে float32-এর দুটি array উপাদান ধরে যোগ করতে (c[i] = a[i] + b[i]) ৫১২ বিটের (AVX-512) আর ২৫৬ বিটের (AVX) vector যোগের instruction কয়বার চালাতে হবে?
512-bit / 32-bit = 16 lanes : ceil(1000 / 16) = 63 (62 full + 1 tail of 8 elements)
256-bit / 32-bit = 8 lanes : 1000 / 8 = 125 (no tail)শেষের অসম্পূর্ণ অংশ (tail) mask দিয়ে বা আলাদা scalar লুপে সামলানো হয় (পর্ব ৪২)। ৬৩ আর ১২৫ বার।
(মাঝারি) Tomasulo-তে একটি fmul.d issue হলো cycle ৩-এ; তার একটি operand CDB থেকে আসে cycle ৭-এ; latency ৪. নিয়ম: CDB-তে cycle W-তে এলে execute W + 1-এ শুরু, শেষের পরের cycle-এ write. কোন cycle-এ এর ফল CDB-তে লেখা হবে?
- 7
- 11
- 8
- 12
(সহজ) একটি ৪-wide superscalar core ১২০০টি instruction ৫০০ cycle-এ চালাল। IPC কত?
- 2.4
- 0.417
- 4.0
- 0.6
৮ · মডিউল ৮ — Cache, AMAT, DRAM আর virtual memory
ঝালিয়ে নিন: পর্ব ৪৫ · Cache-এর মৌলিক কথা, পর্ব ৪৬ · Set-associative cache, পর্ব ৪৭ · Cache-এর পারফরম্যান্স, পর্ব ৪৯ · Main memory, পর্ব ৫০ · Virtual memory-র hardware.
Address-এর ভাগ: offset = log2(block), set = cache ÷ (block × way), index = log2(set), tag = address-বিট − index − offset. মোট বিট = line × (৮ × block + tag + ১ valid [+ ১ dirty]).
AMAT: HT + MR × MP; দুই স্তরে HT1 + MR1 × (HT2 + MR2,local × MP2); global = MR1 × MR2,local. CPI = CPIbase + Σ(access/instr × MR × MP).
DRAM আর VM: peak bandwidth = MT/s × bus-byte × channel; CAS (ns) = CL × ২০০০ ÷ MT/s. Flat page table = 2VA − offset × PTE; EAT = tTLB + (1 − h) × L × tPTE + tmem.
৮.১(মাঝারি) ৩২ বিটের byte address. (ক) ৩২ KiB direct-mapped, ৬৪ B block; (খ) একই কিন্তু ৪-way; (গ) ১৬ KiB direct-mapped, ১৬ B block, write-back (dirty bit-সহ) — tag | index | offset আর মোট SRAM বিট কত?
(a) lines = 2^15 / 2^6 = 512 ; offset 6, index 9, tag 32 - 9 - 6 = 17
total = 512 x (512 + 17 + 1) = 271,360 bits = 265 Kibit (data 256 Kibit)
(b) sets = 512 / 4 = 128 ; offset 6, index 7, tag 19
total = 512 x (512 + 19 + 1) = 272,384 bits = 266 Kibit
(c) lines = 2^14 / 2^4 = 1024 ; offset 4, index 10, tag 18
total = 1024 x (128 + 18 + 1 + 1) = 151,552 bits = 148 KibitAssociativity বাড়লে index-এর বিট কমে, tag-এর বিট বাড়ে — তাই মোট বিট একটু বাড়ে (LRU-এর বিট এখানে ধরা হয়নি)। (ক) ১৭|৯|৬, ২,৭১,৩৬০ বিট; (খ) ১৯|৭|৬, ২,৭২,৩৮৪ বিট; (গ) ১৮|১০|৪, ১,৫১,৫৫২ বিট।
৮.২(সহজ) ৮.১(ক)-এর cache-এ address 0x1234ABCD-এর tag, index আর offset কত?
0x1234ABCD = 0001 0010 0011 0100 1010 1011 1100 1101
offset = low 6 bits = 00 1101 = 13
index = next 9 bits = 0 1010 1111 = 175
tag = top 17 bits = 0x2469Hex-এর সীমানা বিটের সীমানার সাথে মেলে না (৬, ৯, ১৭), তাই আগে পুরো binary লিখুন, তারপর ডান থেকে কাটুন। Tag 0x2469, index ১৭৫, offset ১৩.
| এই access | |
| DM (index = b mod 8) | |
| DM line 2 │ line 5 | |
| ২-way (set = b mod 4) | |
| set 2 (LRU আগে) | |
| set 1 (LRU আগে) | |
| hit: DM / ২-way |
- Block 2. দুই cache-ই খালি। DM-এ index = ২ mod ৮ = ২ (tag ০), ২-way-এ set = ২ mod ৪ = ২ (tag ০)। দুটিতেই প্রথমবারের miss (compulsory).
- Block 10. DM-এ ১০ mod ৮ = ২ — একই line! Block 2 বের হয়ে 10 ঢোকে (tag ১)। ২-way-এ ১০ mod ৪ = ২, কিন্তু set 2-এ দুটি জায়গা, তাই 2 আর 10 পাশাপাশি থাকে; LRU এখন 2.
- Block 2 আবার। DM-এ line 2-এ এখন 10 — miss, 10 বের। এটি conflict miss: cache-এ জায়গা খালি থাকলেও দুটি block একই line-এর জন্য লড়ছে। ২-way-এ hit; LRU এখন 10.
- Block 10 আবার। DM-এ আবার miss — একে বলে ping-pong. ২-way-এ hit; set 2-এর LRU এখন 2.
- Block 5. DM-এ index ৫, ২-way-এ set ১ (৫ mod ৪ = ১) — দুটিতেই প্রথমবারের miss.
- Block 13. ১৩ mod ৮ = ৫ — DM-এ আবার একই line-এর লড়াই, 5 বের। ২-way-এ ১৩ mod ৪ = ১, set 1-এ দ্বিতীয় জায়গায় বসে।
- Block 2. DM-এ line 2-এ 10, তাই miss. ২-way-এ set 2-এ 2 আছে — hit, LRU এখন 10.
- Block 5 — ফল। DM-এ line 5-এ 13, miss. ২-way-এ hit. মোট: DM ০/৮ hit (৪টি compulsory + ৪টি conflict), ২-way ৪/৮ — একই মাপের cache, শুধু associativity বদলে hit-এর হার ০% থেকে ৫০%.
৮.৩(মাঝারি) ৮টি block-এর একটি cache, block address-এর ক্রম 2, 10, 2, 10, 5, 13, 2, 5. Direct-mapped, ২-way LRU আর fully associative LRU-তে hit কয়টি? DM-এর miss-গুলো কোন ধরনের?
ওপরের stepper-এ দুটি টেবিল পাশাপাশি। DM-এ 2 আর 10 একই index (২)-এর জন্য, 5 আর 13 index ৫-এর জন্য লড়ে — প্রতিটি access miss. ২-way-এ প্রতিটি জোড়া একটি set-এ একসাথে বসে। Fully associative-এ মাত্র চারটি আলাদা block, যা ৮টি জায়গায় সহজে ধরে, তাই ফল ২-way-এর সমান। DM ০টি hit (৪টি compulsory + ৪টি conflict miss); ২-way ৪টি; fully associative ৪টি।
// Cache address split, total storage bits, and a hit/miss trace with LRU (ways = 1 means direct-mapped).
const lg = x => Math.log2(x);
function split(addrBits, size, block, ways, dirty = 0) {
const sets = size / block / ways, off = lg(block), idx = lg(sets), tag = addrBits - idx - off;
const lines = size / block, total = lines * (8 * block + tag + 1 + dirty);
console.log(`${size / 1024} KiB, ${block} B, ${ways}-way: sets ${sets}, tag|index|offset = ${tag}|${idx}|${off}, ` +
`total ${total} bits = ${(total / 1024).toFixed(2)} Kibit (data ${lines * 8 * block / 1024} Kibit)`);
return { off, idx };
}
const s = split(32, 32 * 1024, 64, 1);
split(32, 32 * 1024, 64, 4);
split(32, 16 * 1024, 16, 1, 1);
const a = 0x1234ABCD;
console.log(`0x1234ABCD -> tag 0x${(a >>> (s.off + s.idx)).toString(16).toUpperCase()}, index ${(a >>> s.off) & ((1 << s.idx) - 1)}, offset ${a & ((1 << s.off) - 1)}`);
function trace(blocks, nBlocks, ways) { // blocks = block addresses
const sets = nBlocks / ways, cache = [...Array(sets)].map(() => []); // each set: most recent last
let hits = 0, line = "";
for (const b of blocks) {
const set = cache[b % sets], i = set.indexOf(b);
if (i >= 0) { hits++; set.splice(i, 1); line += ` ${b}:H`; }
else { if (set.length === ways) line += ` ${b}:M(out ${set.shift()})`; else line += ` ${b}:M`; }
set.push(b);
}
console.log(`${ways}-way, ${sets} sets:${line}\n hits ${hits}/${blocks.length}`);
}
const seq = [2, 10, 2, 10, 5, 13, 2, 5];
trace(seq, 8, 1); trace(seq, 8, 2); trace(seq, 8, 8);আউটপুট:
32 KiB, 64 B, 1-way: sets 512, tag|index|offset = 17|9|6, total 271360 bits = 265.00 Kibit (data 256 Kibit)
32 KiB, 64 B, 4-way: sets 128, tag|index|offset = 19|7|6, total 272384 bits = 266.00 Kibit (data 256 Kibit)
16 KiB, 16 B, 1-way: sets 1024, tag|index|offset = 18|10|4, total 151552 bits = 148.00 Kibit (data 128 Kibit)
0x1234ABCD -> tag 0x2469, index 175, offset 13
1-way, 8 sets: 2:M 10:M(out 2) 2:M(out 10) 10:M(out 2) 5:M 13:M(out 5) 2:M(out 10) 5:M(out 13)
hits 0/8
2-way, 4 sets: 2:M 10:M 2:H 10:H 5:M 13:M 2:H 5:H
hits 4/8
8-way, 1 sets: 2:M 10:M 2:H 10:H 5:M 13:M 2:H 5:H
hits 4/8প্রথম তিন লাইন ৮.১: ১৭|৯|৬ আর ২৬৫ Kibit, ১৯|৭|৬ আর ২৬৬ Kibit, ১৮|১০|৪ আর ১৪৮ Kibit. চতুর্থ লাইন ৮.২-এর tag 0x2469, index ১৭৫, offset ১৩. শেষের তিনটি trace stepper আর ৮.৩-এর হুবহু: “M(out 2)” মানে miss আর block 2 বের হলো। Set-এর array-তে সবচেয়ে পুরোনো ব্যবহার সামনে থাকে — shift() তাকেই বের করে, আর hit হলে block শেষে সরে যায়: এটাই LRU.
৮.৪(সহজ) Hit time ১ cycle, miss rate ৫%, miss penalty ৮০ cycle. AMAT কত?
AMAT = 1 + 0.05 x 80 = 1 + 4 = 5 cyclesHit time প্রতিটি access-এ লাগে, miss হলেও — তাই “০.৯৫ × ১ + ০.০৫ × ৮০ = ৪.৯৫” লেখা ভুল, যদি না প্রশ্নে বলা থাকে miss penalty-র মধ্যেই hit time ধরা। ৫ cycle.
৮.৫(মাঝারি) L1: hit time ১ cycle, miss rate ৪%. L2: hit time ১২ cycle, local miss rate ২৫%. Main memory ১৫০ cycle. AMAT আর L2-এর global miss rate কত?
L1 miss penalty = HT2 + MR2 x MP2 = 12 + 0.25 x 150 = 49.5
AMAT = 1 + 0.04 x 49.5 = 2.98 cycles
global L2 miss rate = 0.04 x 0.25 = 1% (1 in 100 accesses reaches memory)“২৫%” local — L2-তে যা পৌঁছায় তার ২৫%. একে global ধরলে AMAT = ১ + ০.০৪ × ১২ + ০.২৫ × ১৫০ = ৩৯ cycle-এর মতো অবাস্তব সংখ্যা আসে। AMAT ২.৯৮ cycle, global miss rate ১%.
৮.৬(কঠিন) CPIbase ১.২; প্রতি instruction-এ ১টি instruction fetch আর ০.৩টি data access; I-cache miss ২%, D-cache miss ৫%; memory-তে যেতে ১০০ cycle. (ক) CPI কত? (খ) একটি L2 যোগ হলো: L1 miss-এ ১৫ cycle, আর তার ২০% L2-তেও miss করে (আরও ১০০)। নতুন CPI আর speedup?
(a) I-stall = 1.0 x 0.02 x 100 = 2.0 D-stall = 0.3 x 0.05 x 100 = 1.5
CPI = 1.2 + 2.0 + 1.5 = 4.7
(b) L1 miss penalty = 15 + 0.2 x 100 = 35
I-stall = 1.0 x 0.02 x 35 = 0.7 D-stall = 0.3 x 0.05 x 35 = 0.525
CPI = 1.2 + 0.7 + 0.525 = 2.425 speedup = 4.7 / 2.425 = 1.938Clock আর IC একই, তাই CPI-র অনুপাতই speedup. (ক)-তে মেমরির অপেক্ষাই CPI-র ৭৪%-এর বেশি — CPU-র আসল কাজ মাত্র ১.২. (ক) ৪.৭; (খ) ২.৪২৫, প্রায় ১.৯৪ গুণ দ্রুত।
৮.৭(মাঝারি) (ক) DDR4-3200 আর DDR5-4800-এর একটি ৬৪ বিটের channel-এর peak bandwidth কত? DDR4-3200 dual channel? (খ) DDR4-3200 CL16 আর DDR5-4800 CL40-এর CAS latency কত ns? (গ) DDR4-3200-এ ৬৪ byte-এর line-এর burst কত সময় নেয়?
(a) 3200 x 10^6 x 8 byte = 25.6 GB/s ; dual channel 51.2 GB/s
4800 x 10^6 x 8 byte = 38.4 GB/s
(b) clock = MT/s / 2 ; CAS = CL / clock = CL x 2000 / (MT/s) ns
16 x 2000 / 3200 = 10 ns 40 x 2000 / 4800 = 16.67 ns
(c) 64 byte / 8 byte = 8 transfers ; 8 / (3200 x 10^6) = 2.5 ns“৩২০০” clock নয়, প্রতি সেকেন্ডে transfer — DDR-এ clock-এর দুই ধারে ডেটা যায়, তাই আসল clock ১৬০০ MHz. নতুন প্রজন্মে CL সংখ্যা অনেক বড় হলেও (১৬ → ৪০) ns-এ latency সেই হারে বাড়ে না (১০ → ≈ ১৬.৬৭), অথচ bandwidth বাড়ে (পর্ব ৪৯)। DDR5-এর একটি module-এ দুটি ৩২ বিটের sub-channel থাকে; এখানে দুটি মিলিয়ে ৬৪ বিট ধরা। ২৫.৬, ৫১.২ আর ৩৮.৪ GB/s; ১০ আর ≈ ১৬.৬৭ ns; ২.৫ ns.
৮.৮(মাঝারি) (ক) ৩২ বিটের VA, ৪ KiB page, ৪ byte PTE-তে এক স্তরের page table কত বড়? ৪৮ বিটের VA আর ৮ byte PTE-তে? (খ) Sv32-এ VA 0x12345678-এর VPN[1], VPN[0] আর offset কী?
(a) 2^(32-12) x 4 = 2^20 x 4 = 4 MiB per process
2^(48-12) x 8 = 2^36 x 8 = 512 GiB -> impossible flat, hence 4 levels of 9 bits
(b) Sv32 split 10 | 10 | 12
0x12345678 = 0001 0010 00 | 11 0100 0101 | 0110 0111 1000
VPN[1] = 0x048 (72), VPN[0] = 0x345 (837), offset = 0x678Sv32-এ প্রতিটি টেবিল ১০২৪টি ঘর × ৪ byte = ঠিক একটি ৪ KiB page — ইচ্ছাকৃত নকশা। Sv39-এর ভাগ 9 | 9 | 9 | 12, PTE ৮ byte, তাই সেখানেও প্রতি টেবিল ৫১২ × ৮ = ৪ KiB. ৪ MiB আর ৫১২ GiB; VPN[1] = 0x048, VPN[0] = 0x345, offset 0x678.
৮.৯(মাঝারি) Sv39 (walk-এ ৩টি PTE), TLB দেখতে ১ cycle, প্রতিটি PTE আর ডেটা মেমরি থেকে ১০০ cycle, TLB hit rate ৯৫%. EAT কত? প্রতিটি access-এ TLB miss হলে (h = ০)? আর ns-এ পুরোনো textbook-ধাঁচ: এক স্তরের টেবিল, TLB ১০ ns, মেমরি ১০০ ns, hit ৯০%?
EAT = tTLB + (1 - h) x L x tPTE + tmem
= 1 + 0.05 x 3 x 100 + 100 = 116 cycles
h = 0 (every access walks): 1 + 3 x 100 + 100 = 401 cycles
ns example: 10 + 0.10 x 1 x 100 + 100 = 120 ns
= 0.9 x (10 + 100) + 0.1 x (10 + 100 + 100) (same thing)দুই রূপ একই: textbook-এর h(t + m) + (1 − h)(t + 2m) গুণ খুললেই পর্ব ৫০-এর সূত্র আসে। ১১৬ cycle; h = ০-তে ৪০১ cycle; ns-এ ১২০ ns.
// AMAT, CPI with memory stalls, DRAM numbers, page tables and TLB effective access time (lessons 47-50).
const amat = (ht, mr, mp) => ht + mr * mp;
console.log("AMAT one level =", amat(1, 0.05, 80), "cycles");
const l2 = amat(12, 0.25, 150); // L2 hit time 12, LOCAL miss rate 25%, memory 150
console.log("AMAT two levels = 1 + 0.04 x", l2, "=", amat(1, 0.04, l2).toFixed(2), " global L2 miss rate =", (0.04 * 0.25 * 100).toFixed(1) + "%");
const cpi = (base, parts) => base + parts.reduce((s, [acc, mr, pen]) => s + acc * mr * pen, 0);
const c1 = cpi(1.2, [[1, 0.02, 100], [0.3, 0.05, 100]]);
const pen2 = 15 + 0.2 * 100; // L1 miss: 15 to L2, 20% of those also miss L2
const c2 = cpi(1.2, [[1, 0.02, pen2], [0.3, 0.05, pen2]]);
console.log(`CPI no L2 = ${c1.toFixed(3)}, with L2 = ${c2.toFixed(3)}, speedup ${(c1 / c2).toFixed(3)}`);
const bw = (mts, busBits, ch = 1) => mts * 1e6 * busBits / 8 * ch / 1e9; // GB/s, decimal
console.log("DDR4-3200 x64:", bw(3200, 64), "GB/s dual:", bw(3200, 64, 2), " DDR5-4800 x64:", bw(4800, 64), "GB/s");
const casNs = (cl, mts) => cl * 2000 / mts; // clock = MT/s / 2
console.log("CAS DDR4-3200 CL16 =", casNs(16, 3200), "ns DDR5-4800 CL40 =", casNs(40, 4800).toFixed(2), "ns");
const pt = (vaBits, pageBytes, pteBytes) => 2 ** (vaBits - Math.log2(pageBytes)) * pteBytes;
console.log("flat table 32-bit/4KiB/4B =", pt(32, 4096, 4) / 2 ** 20, "MiB; 48-bit/4KiB/8B =", pt(48, 4096, 8) / 2 ** 30, "GiB");
const va = 0x12345678; // Sv32: VPN[1] | VPN[0] | offset = 10 | 10 | 12
console.log(`Sv32 0x12345678 -> VPN1 0x${(va >>> 22).toString(16)}, VPN0 0x${((va >>> 12) & 0x3FF).toString(16)}, offset 0x${(va & 0xFFF).toString(16)}`);
const eat = (h, tTLB, levels, tPTE, tMem) => tTLB + (1 - h) * levels * tPTE + tMem;
console.log("EAT Sv39 h=95% =", eat(0.95, 1, 3, 100, 100).toFixed(1), "cycles; h=0 =", eat(0, 1, 3, 100, 100), "cycles");
console.log("EAT ns, 1 level, TLB 10 ns, mem 100 ns, h=90% =", eat(0.9, 10, 1, 100, 100).toFixed(1), "ns");আউটপুট:
AMAT one level = 5 cycles
AMAT two levels = 1 + 0.04 x 49.5 = 2.98 global L2 miss rate = 1.0%
CPI no L2 = 4.700, with L2 = 2.425, speedup 1.938
DDR4-3200 x64: 25.6 GB/s dual: 51.2 DDR5-4800 x64: 38.4 GB/s
CAS DDR4-3200 CL16 = 10 ns DDR5-4800 CL40 = 16.67 ns
flat table 32-bit/4KiB/4B = 4 MiB; 48-bit/4KiB/8B = 512 GiB
Sv32 0x12345678 -> VPN1 0x48, VPN0 0x345, offset 0x678
EAT Sv39 h=95% = 116.0 cycles; h=0 = 401 cycles
EAT ns, 1 level, TLB 10 ns, mem 100 ns, h=90% = 120.0 nsলাইন ধরে: ৮.৪-এর ৫ cycle, ৮.৫-এর ৪৯.৫ আর ২.৯৮ (global ১%), ৮.৬-এর ৪.৭ → ২.৪২৫ (১.৯৩৮ গুণ), ৮.৭-এর ২৫.৬, ৫১.২ আর ৩৮.৪ GB/s, ১০ আর ১৬.৬৭ ns, ৮.৮-এর ৪ MiB আর ৫১২ GiB আর Sv32-এর ভাগ, শেষে ৮.৯-এর ১১৬, ৪০১ আর ১২০. l2 চলকটিই L1-এর miss penalty — দুই স্তরের AMAT আসলে একটি AMAT-এর ভেতরে আরেকটি।
(মাঝারি) ৩২ বিটের byte address, ৬৪ KiB direct-mapped cache, ৩২ byte block. Tag | index | offset কত বিট?
- 17 | 10 | 5
- 16 | 10 | 6
- 16 | 11 | 5
- 15 | 11 | 5
(সহজ) Hit time ২ cycle, miss rate ১০%, miss penalty ৫০ cycle. AMAT কত?
- 5 cycle
- 7 cycle
- 6.8 cycle
- 52 cycle
৯ · মডিউল ৯ — I/O, সমান্তরালতা, GPU আর power
ঝালিয়ে নিন: পর্ব ৫১ · I/O আর bus, পর্ব ৫২ · Interrupt আর DMA, পর্ব ৫৩ · Multicore আর cache coherence, পর্ব ৫৪ · সমান্তরাল আর্কিটেকচার, পর্ব ৫৫ · GPU আর AI accelerator, পর্ব ৫৬ · Power আর embedded.
I/O খরচ: polling-এ CPU-অংশ = (poll/সেকেন্ড × cycle/poll) ÷ f; DMA-তে = (transfer/সেকেন্ড × setup-আর-interrupt-এর cycle) ÷ f.
সমান্তরালতা: Amdahl 1 ÷ ((1 − p) + p/N), efficiency = speedup ÷ N; Gustafson N − s(N − 1). Diameter = সবচেয়ে দূরের দুই node-এর hop; bisection = নেটওয়ার্ককে দুই সমান ভাগে কাটতে ন্যূনতম link.
GPU আর power: SIMD efficiency = Σ(সক্রিয় lane) ÷ (issue × warp-আকার); divergence-এ দুই পথের instruction যোগ হয়। Dynamic power P = αCV2f; একটি কাজের energy ∝ V2.
৯.১(মাঝারি) ১ GHz CPU, প্রতিটি poll ৪০০ cycle. (ক) Mouse সেকেন্ডে ৩০ বার poll. (খ) ১৬ MB/s-এর disk, প্রতি poll-এ ১৬ byte. (গ) একই disk DMA-তে, প্রতি transfer ৮০০০ byte, প্রতিটির setup আর interrupt মিলে ১৫০০ cycle. প্রতিটিতে CPU-র কত শতাংশ যায়?
(a) 30 x 400 = 12,000 cycles/s -> 12,000 / 10^9 = 0.0012%
(b) 16 x 10^6 / 16 = 10^6 polls/s x 400 -> 4 x 10^8 / 10^9 = 40%
(c) 16 x 10^6 / 8000 = 2000 transfers/s x 1500 -> 3 x 10^6 / 10^9 = 0.3%ধীর যন্ত্রে polling প্রায় বিনা খরচে চলে, দ্রুত যন্ত্রে CPU খেয়ে ফেলে; DMA প্রতি-byte-এর খরচ সরিয়ে শুধু প্রতি-transfer-এর খরচ রাখে (পর্ব ৫২)। ০.০০১২%, ৪০% আর ০.৩%.
৯.২(মাঝারি) একটি কাজের ৯০% সমান্তরাল। ১৬টি core-এ Amdahl-এর speedup আর efficiency কত, আর core অসীম হলে সীমা? Gustafson-এ (সমান্তরাল চালানোর সময় serial অংশ ১০%) scaled speedup কত?
Amdahl : 1 / (0.1 + 0.9/16) = 1 / 0.15625 = 6.4 efficiency 6.4 / 16 = 40%
limit : 1 / 0.1 = 10
Gustafson: N - s(N - 1) = 16 - 0.1 x 15 = 14.5দুটি সূত্র আলাদা প্রশ্নের উত্তর: Amdahl কাজ স্থির রেখে (strong scaling), Gustafson core-এর সাথে কাজ বাড়িয়ে (weak scaling) হিসাব করে। এখানে s হলো সমান্তরাল চালানোর মোট সময়ের serial অংশ, এক core-এর প্রোগ্রামের নয়। ৬.৪, ৪০%, সীমা ১০; Gustafson ১৪.৫.
৯.৩(মাঝারি) ১৬টি node: ring, ৪ × ৪ mesh, ৪ × ৪ torus আর ৪-মাত্রার hypercube — প্রতিটির diameter, link-সংখ্যা আর bisection কত?
topology diameter links bisection
ring 8 16 2 (N/2, N, 2)
4 x 4 mesh 6 24 4 (2(k-1), 2k(k-1), k)
4 x 4 torus 4 32 8 (2 floor(k/2), 2k^2, 2k)
4-cube 4 32 8 (log2 N, N log2 N / 2, N/2)সব সংখ্যা breadth-first search আর সব সমান ভাগ পরীক্ষা করে মেলানো। ১৬ node-এ torus আর hypercube হুবহু এক — ৪ × ৪ torus আসলে ৪-মাত্রার cube-এর সমান graph (পর্ব ৫৪)। Ring ৮/১৬/২, mesh ৬/২৪/৪, torus আর cube ৪/৩২/৮.
৯.৪(মাঝারি) ৩২-thread-এর একটি warp: শাখার আগে ৩টি instruction, if (tid % 4 == 0)-এর ভেতরে ১০টি, else-এ ৬টি, শেষে ৩টি। মোট issue আর divergence-এর পর SIMD efficiency কত?
if-path threads: 32 / 4 = 8 ; else-path: 24
issued = 3 + 10 + 6 + 3 = 22
active lane-slots = 3x32 + 10x8 + 6x24 + 3x32 = 96 + 80 + 144 + 96 = 416
efficiency = 416 / (22 x 32) = 416 / 704 = 59.09%Warp দুই পথই পালা করে চালায়, mask দিয়ে — তাই সময় ১০ + ৬, যেকোনো একটির নয়। সব thread একই পথে গেলে issue হতো ১৬ (if-পথে) বা ১২ (else-পথে)। ২২টি issue, ≈ ৫৯.০৯%.
৯.৫(সহজ) α = ০.২, C = ২০ nF, V = ১.১ V, f = ৩ GHz. Dynamic power কত? V আর f দুটিই ২০% কমালে power আর একটি কাজের energy কত গুণ হয়?
P = 0.2 x 20e-9 x 1.1^2 x 3e9 = 0.2 x 20e-9 x 1.21 x 3e9 = 14.52 W
V, f x 0.8 : P' = P x 0.8^2 x 0.8 = P x 0.512 = 7.434 W
energy per task = P x time ; time grows by 1/0.8 -> x 0.512 / 0.8 = x 0.64 (= 0.8^2)Power কমে ঘনফলের হারে, কিন্তু energy শুধু V2-এর হারে — কারণ কাজটি এখন বেশি সময় নেয়। শুধু f কমালে (V একই) power কমে, কিন্তু কাজপ্রতি dynamic energy একটুও কমে না (পর্ব ৫৬)। ১৪.৫২ W; ৭.৪৩৪ W (×০.৫১২); energy ×০.৬৪.
// I/O overhead, Amdahl/Gustafson, network diameter (BFS), warp efficiency, dynamic power (lessons 51-56).
const f = 1e9, pct = x => (100 * x).toFixed(4) + "%";
console.log("mouse poll 30/s x 400 cy:", pct(30 * 400 / f), " disk 16 MB/s in 16 B polls:", pct(16e6 / 16 * 400 / f),
" DMA 8000 B blocks, 1500 cy each:", pct(16e6 / 8000 * 1500 / f));
const amdahl = (p, n) => 1 / ((1 - p) + p / n), gustafson = (s, n) => n - s * (n - 1);
console.log(`p=0.9 N=16: Amdahl ${amdahl(0.9, 16).toFixed(3)} (efficiency ${(amdahl(0.9, 16) / 16 * 100).toFixed(1)}%), limit ${(1 / 0.1).toFixed(1)}; ` +
`Gustafson s=0.1: ${gustafson(0.1, 16).toFixed(2)}`);
function net(name, N, nbr, bisection) { // diameter by breadth-first search from every node
let diam = 0, links = 0;
for (let s = 0; s < N; s++) {
const d = Array(N).fill(-1), q = [s]; d[s] = 0; links += nbr(s).length;
while (q.length) { const u = q.shift(); for (const v of nbr(u)) if (d[v] < 0) { d[v] = d[u] + 1; q.push(v); } }
diam = Math.max(diam, ...d);
}
console.log(`${name.padEnd(12)} N=${N} diameter ${diam}, links ${links / 2}, bisection ${bisection}`);
}
const k = 4, xy = v => [v % k, Math.floor(v / k)], id = (x, y) => y * k + x;
net("ring", 16, v => [(v + 1) % 16, (v + 15) % 16], 2);
net("4x4 mesh", 16, v => { const [x, y] = xy(v); return [[x - 1, y], [x + 1, y], [x, y - 1], [x, y + 1]]
.filter(([a, b]) => a >= 0 && a < k && b >= 0 && b < k).map(([a, b]) => id(a, b)); }, 4);
net("4x4 torus", 16, v => { const [x, y] = xy(v); return [id((x + 1) % k, y), id((x + 3) % k, y), id(x, (y + 1) % k), id(x, (y + 3) % k)]; }, 8);
net("4-cube", 16, v => [1, 2, 4, 8].map(b => v ^ b), 8);
const W = 32, issued = 3 + 10 + 6 + 3, active = 3 * W + 10 * 8 + 6 * 24 + 3 * W; // if (tid % 4 == 0)
console.log(`warp: ${active} / (${issued} x ${W}) = ${(100 * active / (issued * W)).toFixed(2)}% SIMD efficiency`);
const P = (a, C, V, fr) => a * C * V * V * fr;
const p0 = P(0.2, 20e-9, 1.1, 3e9), p1 = P(0.2, 20e-9, 0.88, 2.4e9);
console.log(`P_dyn = ${p0.toFixed(2)} W; V and f x0.8 -> ${p1.toFixed(3)} W (x${(p1 / p0).toFixed(3)}), energy per task x${(0.8 ** 2).toFixed(2)}`);আউটপুট:
mouse poll 30/s x 400 cy: 0.0012% disk 16 MB/s in 16 B polls: 40.0000% DMA 8000 B blocks, 1500 cy each: 0.3000%
p=0.9 N=16: Amdahl 6.400 (efficiency 40.0%), limit 10.0; Gustafson s=0.1: 14.50
ring N=16 diameter 8, links 16, bisection 2
4x4 mesh N=16 diameter 6, links 24, bisection 4
4x4 torus N=16 diameter 4, links 32, bisection 8
4-cube N=16 diameter 4, links 32, bisection 8
warp: 416 / (22 x 32) = 59.09% SIMD efficiency
P_dyn = 14.52 W; V and f x0.8 -> 7.434 W (x0.512), energy per task x0.64প্রথম লাইন ৯.১-এর তিন শতাংশ, দ্বিতীয় লাইন ৯.২-এর ৬.৪, ৪০%, ১০ আর ১৪.৫০. মাঝের চার লাইনে diameter আর link সত্যিই BFS চালিয়ে বের হয়েছে (প্রতিটি node থেকে দূরত্ব মেপে সর্বোচ্চ); bisection-এর সংখ্যা সূত্র থেকে দেওয়া, আর আলাদা একটি স্ক্রিপ্টে সব ৬,৪৩৫টি সমান ভাগ পরীক্ষা করে মেলানো হয়েছে। শেষ দুই লাইন ৯.৪-এর ৫৯.০৯% আর ৯.৫-এর ১৪.৫২ W, ৭.৪৩৪ W, ×০.৫১২ আর ×০.৬৪.
(মাঝারি) একটি কাজের ৯৫% সমান্তরাল। ৮টি core-এ Amdahl-এর সূত্রে speedup প্রায় কত?
- 8.0
- 7.6
- 20.0
- ≈ 5.926
(সহজ) P = αCV2f-এ supply voltage আর clock frequency দুটিই ১০% কমালে dynamic power প্রায় কত শতাংশ কমে?
- প্রায় ২৭.১%
- ১০%
- ১৯%
- ২০%
১০ · AI-এর যুগে — numerical-এর উত্তর যাচাই
AI-কে একটি K-map বা cache-এর অঙ্ক দিলে উত্তর আসে পরিষ্কার টেবিলে, আত্মবিশ্বাসী গলায় — আর বেশ প্রায়ই ভুল। ভুলের ধরনও চেনা: K-map-এর কিনারা ঘুরে মেলানো ভুলে যাওয়া, don't care-কে বাধ্যতামূলক ধরা, two's complement-এ −১২৮-এর মতো সীমানার মান, IEEE 754-এ exponent-এর bias এক কম-বেশি, cache-এ KB-কে ১০০০ ধরা, pipeline-এর cycle গুনতে fill-এর ৪ cycle বাদ দেওয়া, RISC-V-এর প্রশ্নে MIPS-এর PC + 4-ভিত্তিক branch offset বসিয়ে দেওয়া। এই পাতার প্রোগ্রাম আর উল্টো চেক ঠিক এই কাজের জন্য।
AI সাধারণত যেখানে ভুল করে
| AI-এর ভুল | পরিণাম | কীভাবে ধরবেন |
|---|---|---|
| K-map-এ wrap-around দল না দেখা, বা অপ্রয়োজনীয় prime যোগ করা | সঠিক কিন্তু minimum নয়, বা ভুল function | কয়েকটি minterm বসিয়ে মেলান; QM প্রোগ্রাম চালান |
| Two's complement-এ C আর V গুলিয়ে ফেলা, sign extension-এর জায়গায় zero extension | Overflow-এর ভুল সিদ্ধান্ত | দুই ইনপুট আর ফলের চিহ্ন-বিট আলাদা করে লিখুন |
| IEEE 754-এ bias ১২৮ বা hidden bit জমা করা, rounding-এ সবসময় truncation | এক বিট বা পুরো exponent ভুল | Bit pattern আবার দশমিকে ফিরিয়ে দেখুন |
| RISC-V-এর B/J format-এ immediate-এর বিট সোজা ক্রমে বসানো; MIPS-এর নিয়মে offset | ভুল machine code, ভুল লাফ | Encode করে আবার decode করুন; ISA manual-এর টেবিল দেখুন |
| Pipeline-এ forwarding আছে কি না না জিজ্ঞেস করেই stall গোনা | Cycle-সংখ্যা দ্বিগুণ বা অর্ধেক | প্রম্পটে নিয়ম লিখে দিন; cycle-টেবিল হাতে আঁকুন |
| Cache-এ KiB-কে ১০০০ ধরা, local আর global miss rate মেশানো | ভগ্নাংশ বিট, অবাস্তব AMAT | tag + index + offset = address-বিট কি না দেখুন |
| বানানো chip-spec (“অমুক CPU-র L2 এত”) বা মনগড়া benchmark | ভুল তথ্য উদ্ধৃতি | Datasheet বা নির্মাতার আসল ডকুমেন্ট খুঁজুন |
AI-কে উত্তরদাতা নয়, যাচাইকারী আর প্রশ্ন-বানানোর সহকারী হিসেবে ব্যবহার করুন:
যাচাইয়ের চেকলিস্ট
নিজেকে যাচাই করুন
প্রতিটি প্রশ্নে খাতায় হিসাব করে তবে উত্তর বাছুন। ভুল হলে কারণসহ ব্যাখ্যা পাবেন।
ক্রমএকটি দশমিক সংখ্যাকে IEEE 754 single precision-এ লেখার ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- চিহ্ন দেখে sign বিট ঠিক করা
- মানের পূর্ণ অংশ আর ভগ্নাংশ binary-তে লেখা
- 1.f × 2E আকারে normalise করা
- E + ১২৭ থেকে ৮ বিটের exponent লেখা
- Fraction-এর ২৩ বিট ভরা, দরকারে round করা, তারপর hex-এ সাজানো
(সহজ) 0x3A7-এর দশমিক মান কত?
- 935
- 3107
- 919
- 1955
(সহজ) দশমিক ০.৬২৫-এর binary রূপ কোনটি?
- 0.011
- 0.101
- 0.10100101…
- 0.110
(মাঝারি) একটি ২-বিট saturating counter শুরু 11 (strongly taken) থেকে। একটি branch-এর ফল T, T, T, N, T, T, T, N. কয়টি ভুল অনুমান হবে?
- 0
- 4
- 2
- 3
(মাঝারি) ৪০ বিটের physical address, ২৫৬ KiB ৪-way set-associative cache, ৬৪ byte block. Tag | index | offset কত বিট?
- 22 | 12 | 6
- 16 | 10 | 6
- 26 | 8 | 6
- 24 | 10 | 6
(মাঝারি) ৩২ বিটের virtual address, ৮ KiB page, ৪ byte PTE. এক স্তরের page table কত বড়?
- 2 MiB
- 4 MiB
- 512 KiB
- 8 MiB
(মাঝারি) ৩২-thread-এর warp-এ if (tid < 8)-এর ভেতরে ৪টি আর else-এ ৪টি instruction, আর কোনো instruction নেই। SIMD efficiency কত?
- 25%
- 50%
- 75%
- 100%
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন — অর্থ দেখাবে। এই পর্বে আসা শব্দগুলো এখানে একসাথে:
মনে রাখুন
- নিয়ম আর একক আগে: KiB না KB, gate delay-এর মডেল, forwarding, local না global miss rate, LRU — উত্তরের প্রথম লাইনে লিখুন; নিয়ম বদলালে উত্তর বদলায়।
- বিট-রূপ আর লজিক: ভগ্নাংশে বারবার গুণ; two's complement-এ V মানে চিহ্নের গরমিল; K-map-এ কিনারা ঘুরে মেলে, X শুধু লাগলে; QM-এ PI chart থেকে essential আগে।
- সময় আর গাণিতিক: ripple 2n + 1, বহুস্তর CLA 4⌈log4 n⌉; Tc ≥ tpcq + tpd + tsetup + tskew, hold-এ Tc নেই; Booth-এ কাজের সংখ্যা = বিট বদলের সংখ্যা; IEEE-তে bias ১২৭, tie হলে even.
- ISA আর pipeline: B/J-এর immediate এলোমেলো ক্রমে, offset = target − PC; k + n − 1 cycle; forwarding ছাড়া max(0, 3 − d) stall, থাকলে শুধু load-use; CPI = 1 + f × m × P.
- মেমরি আর সমান্তরালতা: tag + index + offset = address-বিট; AMAT-এর ভেতরে AMAT; EAT = tTLB + (1 − h)L·tPTE + tmem; Amdahl-এর সীমা 1/(1 − p); divergence-এ দুই পথ যোগ; power ∝ V2f. শেষে প্রোগ্রামে মিলিয়ে নিন।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ৫৯ · MCQ প্রশ্নব্যাংক — কম্পিউটার আর্কিটেকচার ও ডিজিটাল লজিকপরবর্তী পর্বপুরো কোর্সের বহুনির্বাচনি প্রশ্ন, মডিউল ধরে।
- পর্ব ৪৭ · Cache-এর পারফরম্যান্সগভীরে যানWrite policy, stall-সহ CPI আর multi-level cache-এর পূর্ণ যুক্তি।
- পর্ব ০৯ · K-map দিয়ে সরলীকরণগভীরে যানকেন Gray ক্রম, কেন কিনারা মেলে, আর don't care-এর পূর্ণ নিয়ম।
- কম্পিউটার আর্কিটেকচার ও ডিজিটাল লজিক · কোর্স হোম৬২টি পর্বপুরো কোর্সের রোডম্যাপ — দশটি মডিউল।
- অপারেটিং সিস্টেম · Numerical সমস্যাপাশের ট্র্যাকScheduling, paging, TLB আর disk-এর অঙ্ক — একই খাতা-সাজানোর কৌশলে।
- কম্পিউটার নেটওয়ার্ক · Numerical সমস্যাপাশের ট্র্যাকDelay, CRC, Hamming আর subnetting-এর পূর্ণ সমাধান।
- C প্রোগ্রামিং · Bitwise operationপাশের ট্র্যাকMask, shift আর বিট বের করা — এই পাতার প্রোগ্রামগুলোর ভিত্তি।