এই পর্বে যা শিখবেন
- আর্কিটেকচারের ইন্টারভিউতে প্রশ্নের পাঁচ ধরন চেনা, আর প্রশ্ন পরিষ্কার করে, অনুমান বলে, সংখ্যায় আন্দাজ করে গুছিয়ে উত্তর দেওয়া
- pipeline, branch prediction, out-of-order, speculation, SIMD আর SMT-এর প্রশ্নে সংক্ষেপে শুরু করে প্রয়োজনে গভীরে যাওয়া
- cache, false sharing, MESI, memory ordering, TLB আর DRAM-এর প্রশ্নে সংখ্যা আর বাস্তব উদাহরণসহ উত্তর, আর “একটি load চালালে কী হয়” শুরু থেকে শেষ পর্যন্ত বলা
- bandwidth, cache miss, roofline, Amdahl আর Little-এর সূত্র দিয়ে মুখে মুখে হিসাব করে script-এ মিলিয়ে নেওয়া
- নকশার trade-off আর পারফরম্যান্স রহস্যের প্রশ্নে কাঠামো মেনে যুক্তি দেওয়া, আর কোন মাপ (performance counter) নেবেন তা বলা
১ · ইন্টারভিউ কীভাবে হয় — পাঁচ ধরনের প্রশ্ন আর উত্তরের চার ধাপ
পর্ব ৫৮–৬০-এ আপনি numerical, MCQ আর লিখিত-মৌখিক প্রশ্নের অনুশীলন করেছেন। চাকরির ইন্টারভিউ এর থেকে আলাদা। সেখানে “AMAT-এর সূত্র লিখুন” কম আসে; বেশি আসে “এই লুপটি দুই thread-এ কেন ধীর হলো?”, বা “২ GiB-এর একটি array যোগ করতে অন্তত কত সময় লাগবে?”। ইন্টারভিউয়ার দেখতে চান আপনি ধারণা থেকে সংখ্যায়, আর সংখ্যা থেকে সিদ্ধান্তে যেতে পারেন কি না। নিচের প্রশ্নগুলো এ ধরনের ইন্টারভিউতে প্রায়ই আসা ধাঁচের — কোনো নির্দিষ্ট প্রতিষ্ঠানের প্রশ্ন বা প্রক্রিয়া নয়; প্রতিষ্ঠানভেদে ধরন অনেক আলাদা হয়।
| পদ | সাধারণত যেদিকে জোর | এই পাতার যে অংশ বেশি কাজে লাগবে |
|---|---|---|
| Systems / backend performance engineer | cache-বান্ধব কোড, false sharing, latency বনাম bandwidth, মুখে মুখে হিসাব, profiling আর counter | অংশ ৪, ৫, ৬, ৮ |
| Hardware / CPU design verification | pipeline-এর hazard আর forwarding, branch আর exception-এর কোণার ঘটনা, coherence protocol-এর অবস্থা, memory ordering-এর litmus test | অংশ ২, ৩, ৪, ৭ |
| Embedded / firmware | ছোট in-order core, cache আর DMA-র সমন্বয়, interrupt latency, power — আর পর্ব ৬২-এর low-level প্রশ্ন | অংশ ২, ৪, ৫ |
| HPC / GPU | SIMD, roofline, bandwidth, NUMA, Amdahl ও Gustafson, memory coalescing | অংশ ৩, ৫, ৬, ৭ |
| Compiler engineer | instruction scheduling, register pressure, vectorization কেন আটকায়, aliasing, loop-এর ক্রম আর blocking | অংশ ২, ৩, ৬, ৮ |
প্রশ্নের পাঁচ ধরন
- ধারণার প্রশ্ন: “Write-back আর write-through-এর পার্থক্য কী?” — সংজ্ঞার পরে একটি কারণ আর একটি উদাহরণ চাই। শুধু মুখস্থ সংজ্ঞা দুর্বল শোনায়।
- মুখে মুখে হিসাব (back-of-envelope): “একটি core সেকেন্ডে কত GB মেমরি পড়তে পারে?” — নির্ভুল উত্তর নয়, সঠিক মাত্রা (order of magnitude) আর পরিষ্কার অনুমান চাই।
- “যখন … তখন কী হয়” walk-through: “একটি load instruction চালালে শুরু থেকে শেষ কী হয়?” — স্তর ধরে ধরে গল্প, প্রতিটি ধাপে কোন hardware কাজ করছে।
- নকশার trade-off: “একই chip area-য় বেশি core নেবেন, না বড় cache?” — কোনো একক সঠিক উত্তর নেই; কাজের ধরন জেনে নিয়ে যুক্তি দিয়ে সিদ্ধান্ত।
- পারফরম্যান্স রহস্য: “দুই thread একটির চেয়ে ধীর — কেন?” — অনুমানের তালিকা, প্রতিটি যাচাইয়ের মাপ, তারপর সমাধান।
উত্তরের চার ধাপ
- প্রশ্ন পরিষ্কার করা (clarifying question): আর্কিটেকচারের উত্তর প্রায়ই “কোন ISA, কোন ধরনের core, কোন কাজ” তার ওপর নির্ভর করে। “x86 সার্ভার ধরে নিচ্ছি?”, “in-order ছোট core, নাকি বড় out-of-order core?”, “ডেটা কি cache-এ আঁটে?” — একটি প্রশ্নে অর্ধেক পথ পরিষ্কার হয়।
- অনুমান জোরে বলা (think aloud): “DRAM-এর latency ১০০ ns-এর মাত্রায় ধরছি, line ৬৪ byte” — এভাবে বললে ইন্টারভিউয়ার ভুল অনুমান ধরিয়ে দিতে পারেন, আর আপনার যুক্তির পথ দেখতে পান।
- সংখ্যায় আন্দাজ: গোল সংখ্যা নিন (২৩০ ≈ ১০৯), একক লিখে রাখুন (bit না byte, GB না GiB, ns না cycle), আর শেষে বলুন উত্তরটি কোন সীমা — নিচের সীমা (lower bound), নাকি আনুমানিক মান।
- Trade-off আর যাচাই: “এর দাম হলো…”, “এটি ভুল হবে যদি…”, “নিশ্চিত হতে
perf statদিয়ে LLC miss মাপতাম” — শেষ বাক্যটিই অভিজ্ঞ প্রকৌশলীর চিহ্ন।
একজন অভিজ্ঞ রাজমিস্ত্রি নতুন বাড়ির দেয়াল দেখে মুখে মুখে বলে দেন কত ইট লাগবে: দেয়ালের দৈর্ঘ্য × উচ্চতা × প্রতি বর্গফুটে মোটামুটি কয়টি ইট, তারপর ভাঙা ইটের জন্য কিছু বাড়তি। তিনি ঠিক কতটি ইট তা জানেন না, কিন্তু ভুলও করেন না — পাঁচ হাজার লাগলে পঞ্চাশ হাজার বলেন না। আর্কিটেকচারের ইন্টারভিউতে মুখে মুখে হিসাব ঠিক এটাই: সঠিক সূত্র, পরিষ্কার অনুমান, সঠিক মাত্রা।
চার ধাপের একটি ছোট নমুনা
প্রশ্ন: “L1 cache আরও বড় করলেই তো miss কমে — তাহলে L1 কেন মাত্র কয়েক ডজন KiB?” নমুনা উত্তর: “ধরে নিচ্ছি একটি সাধারণ উঁচু clock-এর core-এর কথা হচ্ছে (প্রশ্ন পরিষ্কার)। L1-এর hit time প্রতিটি load-এর পথে, আর load-এর latency সরাসরি নির্ভরশীল instruction-এর গতি ঠিক করে (অনুমান)। L1 ৪ থেকে ৫ cycle-এ hit দেয়; আকার দ্বিগুণ করলে তার ও decoder লম্বা হয়, hit time হয়তো এক cycle বাড়ে — অথচ miss rate হয়তো সামান্য কমে। AMAT = hit time + miss rate × miss penalty-তে প্রথম পদটি প্রতিটি access-এ লাগে, তাই এক cycle বাড়া অনেক দামি (সংখ্যা)। তার ওপর ৪ KiB page-এ VIPT নকশায় L1-এর আকার way × page size-এর মধ্যে রাখতে হয়। তাই L1 ছোট আর দ্রুত, আর বড় ধারণক্ষমতা L2-L3-এর কাজ; একটি নির্দিষ্ট chip-এর জন্য নির্মাতার optimization manual দেখতাম (trade-off আর যাচাই)।”
যে ভুলগুলো সবচেয়ে বেশি চোখে পড়ে: নির্দিষ্ট chip-এর সংখ্যা বানিয়ে আত্মবিশ্বাসের সাথে বলা; GB আর GiB, bit আর byte, ns আর cycle গুলিয়ে ফেলা; x86-এর আচরণকে (যেমন TSO) সব CPU-র নিয়ম বলা; “thread বাড়ালেই দ্রুত” ধরে নেওয়া; আর না মেপে optimization প্রস্তাব করা। “নিশ্চিত নই, তবে মাত্রা এরকম, আর এভাবে যাচাই করব” — বানানো সংখ্যার চেয়ে অনেক ভালো শোনায়।
২ · Pipeline, hazard আর branch prediction
রিভিশন: পর্ব ৩৫ · Pipelining, পর্ব ৩৬ · Pipeline hazard, পর্ব ৩৭ · Branch prediction, পর্ব ২৯ · শাখা আর লুপ assembly-তে, পর্ব ৩৮ · Exception আর interrupt
প্র ০১Pipelining কি একটি instruction-কে দ্রুত করে? পাঁচ ধাপের pipeline কেন পাঁচ গুণ দ্রুত হয় না? (সহজ)
সংক্ষিপ্ত উত্তর: না। Pipeline একটি instruction-এর latency কমায় না — বরং register-এর overhead-এ একটু বাড়ায়; সে throughput বাড়ায়, আদর্শভাবে প্রতি cycle-এ একটি instruction শেষ হয়। পাঁচ গুণ হয় না তিন কারণে: ধাপগুলো সমান নয়, প্রতিটি ধাপে pipeline register-এর overhead, আর hazard-এর stall.
গভীর উত্তর: পর্ব ৩৫-এর সংখ্যা: ধাপগুলো ২০০/১০০/২০০/২০০/১০০ ps আর register overhead ২০ ps হলে cycle = সবচেয়ে ধীর ধাপ + overhead = ২২০ ps. Single-cycle নকশায় cycle ছিল ৮২০ ps, তাই সর্বোচ্চ speedup ৮২০ ÷ ২২০ ≈ ৩.৭৩, পাঁচ নয়। n টি instruction-এ মোট cycle k + n − ১, তাই speedup = n·k ÷ (k + n − ১), যা n বড় হলে k-এর কাছে যায় — শুধু সমান ধাপে আর hazard না থাকলে। বাস্তবে CPI = ১ + প্রতি instruction-এ গড় stall.
সম্ভাব্য ফলো-আপ: “তাহলে ৩০ ধাপ করি না কেন?” → প্র ০৪. “Latency বাড়লে কার ক্ষতি?” → নির্ভরশীল instruction-এর শৃঙ্খল আর branch-এর ভুলের দাম, কারণ দুটিই pipeline-এর গভীরতার সাথে বাড়ে।
প্র ০২Data hazard কী? Forwarding থাকলেও কোন ক্ষেত্রে stall লাগবেই? (মাঝারি)
সংক্ষিপ্ত উত্তর: Data hazard হয় যখন পরের instruction-এর দরকারি মান আগের instruction এখনো লেখেনি (RAW). Forwarding ALU-র ফল EX/MEM বা MEM/WB register থেকে সরাসরি পরের ALU-র ইনপুটে পাঠায়, তাই ALU-ALU নির্ভরতায় stall শূন্য। কিন্তু load-use-এ — lw-এর ঠিক পরের instruction তার ফল চাইলে — ১টি stall লাগবেই, কারণ মান আসে MEM ধাপের শেষে, আর পরেরটির EX তখনই শুরু হতে চায়।
গভীর উত্তর: ক্লাসিক in-order পাঁচ ধাপে শুধু RAW বিপদ, কারণ সবাই ID-তে পড়ে আর ক্রমানুসারে WB-তে লেখে — WAR আর WAW সমস্যা হয় না। Forwarding ছাড়া stall = max(০, ৩ − d), d = দুই instruction-এর দূরত্ব (পর্ব ৩৬)। হিসাবের নমুনা: ২৫% instruction load, তাদের ৪০%-এর ঠিক পরেই ফল ব্যবহার → CPI = ১ + ০.২৫ × ০.৪ × ১ = ১.১. Compiler স্বাধীন একটি instruction মাঝে বসিয়ে (instruction scheduling) এই stall অনেকটা সরায়। Hazard ধরা হয় ID ধাপে একটি hazard detection unit দিয়ে: ID/EX-এর instruction load হলে আর তার rd ID-র rs1 বা rs2-এর সমান হলে PC আর IF/ID আটকে রেখে একটি bubble ঢোকানো।
সম্ভাব্য ফলো-আপ: “Store-এর ডেটা load-এর ফল হলে?” → MEM ধাপে forward করা যায়, stall না-ও লাগতে পারে — নকশাভেদে। “Verification-এ কী পরীক্ষা করবেন?” → rd = x0 হলে forwarding বন্ধ থাকছে কি না, আর একই register-এ পরপর দুটি লেখা থাকলে নতুনটি (EX/MEM) প্রাধান্য পাচ্ছে কি না — দুটিই পরিচিত কোণার ঘটনা।
প্র ০৩একই লুপ sorted array-তে unsorted-এর চেয়ে কয়েক গুণ দ্রুত চলে — কাজ তো একই। কেন? (মাঝারি)
সংক্ষিপ্ত উত্তর: লুপের ভেতরে একটি ডেটা-নির্ভর শাখা আছে (“মান ১২৮ বা বেশি হলে যোগ”)। Sorted array-তে শাখাটি প্রথমে টানা not-taken, তারপর টানা taken — predictor প্রায় নিখুঁত। Unsorted array-তে শাখাটি মুদ্রা ছোঁড়ার মতো — প্রায় অর্ধেক অনুমান ভুল, আর প্রতিটি ভুল অনুমানে pipeline flush, গভীর core-এ প্রায় ১০–২০ cycle নষ্ট।
গভীর উত্তর: পর্ব ৩৭-এর সূত্র: CPI = ১ + শাখার অনুপাত × ভুলের হার × penalty. ধরা যাক ২০% instruction শাখা, penalty ১৫ cycle: sorted-এ ভুল প্রায় ০% → CPI ≈ ১; unsorted-এ ৫০% → CPI = ১ + ০.২ × ০.৫ × ১৫ = ২.৫ — প্রায় আড়াই গুণ ধীর। পর্ব ৩৭-এ একই C কোড এই runner-এ মেপে unsorted / sorted ≈ 2.7 পাওয়া গিয়েছিল (রানভেদে প্রায় ২ থেকে ৫)। সমাধান তিনটি: ডেটা sort করা (যদি sort-এর খরচ পোষায়), শাখাহীন কোড — x86-এর cmov, ARM-এর csel বা mask দিয়ে (পর্ব ২৯), আর compiler-কে vectorize করতে দেওয়া।
একটি গুরুত্বপূর্ণ সতর্কতা, যা বললে ইন্টারভিউয়ার খুশি হন: রহস্যটি compiler-নির্ভর। পর্ব ৩৭-এর মাপ ছিল -O0-তে; -O2 বা -O3-এ নতুন gcc বা clang প্রায়ই এই লুপকে নিজেই cmov বা SIMD কোডে বদলে দেয়, তখন sorted আর unsorted প্রায় সমান সময় নেয়। তাই দাবি করার আগে -S দিয়ে assembly দেখা আর perf stat -e branch-misses দিয়ে মাপা।
সম্ভাব্য ফলো-আপ: “শাখাহীন কোড কি সবসময় ভালো?” → না; শাখা অনুমানযোগ্য হলে শাখাওয়ালা কোড দ্রুত হতে পারে, কারণ cmov দুই পথের কাজই করে আর ডেটা-নির্ভরতার শৃঙ্খল লম্বা করে। “Predictor-কে কি সাহায্য করা যায়?” → __builtin_expect বা profile-guided optimization কোডের বিন্যাস বদলায়, কিন্তু এলোমেলো ডেটার শাখাকে অনুমানযোগ্য করতে পারে না।
প্র ০৪Pipeline আরও গভীর করলে clock বাড়ে। তাহলে ৩০–৪০ ধাপের pipeline সবসময় ভালো নয় কেন? (মাঝারি)
সংক্ষিপ্ত উত্তর: ধাপ বাড়লে প্রতিটি ধাপের যুক্তি ছোট হয়, কিন্তু pipeline register-এর overhead ধাপের সংখ্যার সাথে বাড়ে; আর branch-এর ভুলে আর load-use-এ নষ্ট cycle-এর সংখ্যা বাড়ে। একটা সময়ের পর প্রতি ধাপে লাভের চেয়ে ক্ষতি বেশি — তাই একটি সর্বোত্তম গভীরতা আছে। তার ওপর উঁচু clock-এ power বাড়ে (পর্ব ০২-এর power wall).
গভীর উত্তর: সময়ের হিসাব: cycle = Tlogic ÷ k + Toverhead; k বাড়ালে প্রথম পদ কমে, দ্বিতীয়টি স্থির — তাই speedup একসময় থেমে যায়। অন্যদিকে branch penalty প্রায় k-এর সমানুপাতিক, ফলে CPI = ১ + শাখা × ভুল × penalty বাড়তে থাকে। ২০০০-এর দশকের শুরুর খুব গভীর pipeline-ওয়ালা প্রসেসরগুলো (Pentium 4 পরিবার এর পরিচিত উদাহরণ) এই দুই দেয়ালে ধাক্কা খায়, আর শিল্প পরে কম গভীর, চওড়া (superscalar) আর একাধিক core-এর দিকে যায় বলে ব্যাপকভাবে বর্ণিত।
সম্ভাব্য ফলো-আপ: “Superscalar-এ ভুল অনুমানের দাম কি আরও বেশি?” → হ্যাঁ, প্রতি নষ্ট cycle-এ একাধিক instruction-এর slot নষ্ট হয়, আর ভুল পথে আনা instruction-এর সংখ্যা = width × penalty.
প্র ০৫একটি branch predictor আসলে কী কী অনুমান করে? শুধু taken বা not-taken? (কঠিন)
সংক্ষিপ্ত উত্তর: তিনটি জিনিস, আর তিনটিই instruction fetch-এর সময়, decode-এর আগে: (১) এটি আদৌ শাখা কি না আর গন্তব্য কোথায় — BTB; (২) শর্তযুক্ত শাখার দিক — BHT বা ২-bit counter-এর টেবিল, বা আরও উন্নত predictor; (৩) function return-এর ঠিকানা — RAS.
গভীর উত্তর: ১-bit predictor একটি লুপের প্রতিটি প্রবেশে দুবার ভুল করে (শেষের বার আর পরের প্রবেশের প্রথম বার), ২-bit একবার। Correlating predictor সাম্প্রতিক শাখাগুলোর ফল (global history) ব্যবহার করে; gshare index = PC ⊕ history. Tournament, TAGE আর perceptron-ধাঁচের predictor আরও এগিয়ে, সাধারণ কোডে নির্ভুলতা ৯০%-এর অনেক ওপরে। Indirect jump (virtual function, switch-এর jump table) আলাদা চ্যালেঞ্জ — একই PC থেকে অনেক গন্তব্য, তাই history-সহ indirect predictor লাগে। Fetch যেহেতু decode-এর আগে, BTB না থাকলে core জানতেই পারত না যে এটি শাখা।
সম্ভাব্য ফলো-আপ: “RAS কখন ভুল করে?” → খুব গভীর recursion-এ stack উপচে পড়লে, বা setjmp/longjmp ও exception-এর মতো অস্বাভাবিক ফেরায়। “Predictor-এর টেবিল কত বড় হবে?” → অংশ ৭-এর প্র ২২. “নিরাপত্তার সাথে সম্পর্ক?” → predictor ভাগ করা অবস্থা, যা Spectre-ধাঁচের আক্রমণে ব্যবহৃত হয়েছে (প্র ০৮)।
৩ · Out-of-order, speculation, SIMD আর SMT
রিভিশন: পর্ব ৩৯ · Superscalar আর VLIW, পর্ব ৪০ · Out-of-order execution, পর্ব ৪১ · Speculation আর নিরাপত্তা, পর্ব ৪২ · SIMD আর vector, পর্ব ৪৩ · Hardware multithreading
প্র ০৬Out-of-order core-এ instruction ক্রমের বাইরে চলে, অথচ শেষ (commit) হয় ক্রমে। কেন, আর reorder buffer এখানে কী করে? (মাঝারি)
সংক্ষিপ্ত উত্তর: Out-of-order চালানো হয় গতির জন্য — একটি ধীর load আটকে থাকলেও পেছনের স্বাধীন instruction চলে। কিন্তু প্রোগ্রাম আর OS দেখতে চায় যেন সব ক্রমে ঘটেছে: exception হলে তার আগের সব শেষ আর পরের কোনোটির ছাপ নেই (precise exception), আর ভুল branch অনুমানে ভুল পথের কাজ মুছে ফেলা যায়। Reorder buffer (ROB) এই দুইয়ের সেতু: ফল আগে ROB-এ জমে, মাথা থেকে একে একে commit হয়।
গভীর উত্তর: ছক: fetch-decode-rename ক্রমে, issue-execute ইনপুট তৈরি হওয়ামাত্র, commit আবার ক্রমে। পর্ব ৪০-এর উদাহরণে একই ৬টি instruction in-order-এ ৩১ cycle, out-of-order-এ ২০ cycle. Tomasulo-র নকশা (IBM 360/91, ১৯৬৭) reservation station আর tag দিয়ে শুরু; আধুনিক core-এ বড় physical register file, map table আর free list. Store শুধু commit-এর পরেই cache-এ লেখে — তার আগে store queue-তে থাকে, পরের load সেখান থেকে মান নিতে পারে (store-to-load forwarding).
সম্ভাব্য ফলো-আপ: “ROB ভরে গেলে কী হয়?” → নতুন instruction ঢোকা থামে; মাথায় একটি দীর্ঘ cache miss থাকলে ঠিক এটাই হয় — এজন্যই বড় ROB বেশি miss একসাথে চালাতে সাহায্য করে (memory-level parallelism). “ছোট core কেন in-order থাকে?” → OoO-এর power, area আর জটিলতা ছোট power বাজেটে পোষায় না।
প্র ০৭Register renaming কোন hazard মুছে দেয়, আর কোনটি কখনো পারে না? (মাঝারি)
সংক্ষিপ্ত উত্তর: Renaming WAR আর WAW মুছে দেয়, কারণ এগুলো আসল ডেটা-প্রবাহ নয় — শুধু একই register-এর নাম দুবার ব্যবহারের ফল (name dependence). প্রতিটি নতুন লেখাকে একটি নতুন physical register দিলে নামের সংঘাত থাকে না। RAW (true dependence) কখনো মোছে না — মান তৈরি না হলে কেউ তা ব্যবহার করতে পারে না।
গভীর উত্তর: উদাহরণ: add x5, x1, x2; sub x1, x3, x4 — দ্বিতীয়টি x1 লেখে, প্রথমটি x1 পড়ে (WAR). Rename-এর পরে sub লেখে, ধরা যাক, p40-এ, আর add পুরোনো p12 পড়ে — দুটি স্বাধীন। RAW-কে দ্রুত করার উপায় অন্য: forwarding/bypass, ছোট latency-র ALU, আর মেমরির ক্ষেত্রে value বা dependence prediction-এর মতো গবেষণা-ধাঁচের কৌশল। মেমরির ঠিকানার মধ্যে নির্ভরতা (একটি store আর পরের load একই ঠিকানা কি না) register renaming দেখে না — সেটা load/store queue আর memory dependence prediction-এর কাজ।
সম্ভাব্য ফলো-আপ: “Physical register কতগুলো লাগে?” → অন্তত architectural register + উড়ন্ত instruction-এর লেখার সংখ্যা; কম হলে rename থামে। “Free list-এ register কখন ফেরে?” → একই architectural register-এর পরের লেখা commit হলে পুরোনো physical register মুক্ত।
প্র ০৮Spectre কী, ধারণাগতভাবে বুঝিয়ে বলুন। একজন প্রকৌশলী হিসেবে প্রতিরক্ষা কী কী জানেন? (কঠিন)
সংক্ষিপ্ত উত্তর: ভুল অনুমানের পরে CPU register আর মেমরি (architectural state) নিখুঁতভাবে ফিরিয়ে আনে, কিন্তু cache-এ কোন line এল, predictor কী শিখল — এই microarchitectural state ফেরানো হয় না। Spectre predictor-কে ভুল পথে অনুমান করিয়ে বৈধ কোড দিয়েই, অনুমানের ছায়ায়, নিষিদ্ধ ডেটা ছুঁইয়ে নেয়; ডেটার ছাপ cache-এ থেকে যায়, আর সময় মেপে (side channel) তা আন্দাজ করা যায়। ২০১৮ সালের জানুয়ারিতে Spectre আর Meltdown প্রকাশিত হয়।
গভীর উত্তর (প্রতিরক্ষা, স্তরে স্তরে): (১) Bounds check-এর পরে speculation barrier (x86-এ lfence এই কাজে ব্যবহৃত), বা শাখাহীন index masking — Linux kernel-এর array_index_nospec ধাঁচ — যাতে অনুমানের পথেও index সীমার বাইরে না যায়। (২) Indirect branch-এর জন্য retpoline আর hardware-এর predictor-নিয়ন্ত্রণ। (৩) Meltdown-এর জন্য KPTI — kernel-এর আলাদা page table. (৪) Browser-এ site isolation আর মোটা timer. (৫) microcode, firmware, OS update আর নতুন hardware-এর সংশোধন। প্রতিটির কিছু গতির দাম আছে, কাজভেদে আলাদা।
ইন্টারভিউতে এখানে আক্রমণের ধাপ বা কোড নয়, ধারণা আর প্রতিরক্ষাই প্রত্যাশিত। ভালো উত্তরের শেষ বাক্য: “Cryptography-র কোডে গোপন ডেটার ওপর শাখা বা মেমরি-index রাখা যাবে না (constant-time code); নিজে না লিখে যাচাই করা crypto library ব্যবহার করব।”
সম্ভাব্য ফলো-আপ: “Spectre আর Meltdown-এর মূল পার্থক্য?” → Spectre বৈধ কোডকে ভুল পথে চালায় আর নকশা-নির্বিশেষে বহু CPU-তে প্রযোজ্য; Meltdown কিছু নকশায় অনুমতি-যাচাই retire-এর সময় কার্যকর হওয়ার সুযোগ নেয়, আর মূলত নির্দিষ্ট কিছু প্রসেসর পরিবারে দেখা গেছে। “SMT বন্ধ রাখার সাথে সম্পর্ক?” → প্র ১০.
প্র ০৯একটি সরল লুপ compiler vectorize করল না। সম্ভাব্য কারণ কী কী, আর কী করবেন? (মাঝারি)
সংক্ষিপ্ত উত্তর: SIMD একটি চওড়া register-কে কয়েকটি lane-এ ভাগ করে একসাথে কাজ করে — 128 bit = ৪টি float. Auto-vectorization আটকানোর পরিচিত কারণ: দুই pointer একই মেমরি ছুঁতে পারে (aliasing), এক ঘোরার ফল পরের ঘোরায় লাগে (loop-carried dependence), float যোগের ক্রম বদলালে ফল বদলায়, লুপের ভেতরে function call বা জটিল শাখা, আর অনিয়মিত মেমরি-access.
গভীর উত্তর: প্রথম কাজ compiler-কেই জিজ্ঞেস করা: gcc-তে -fopt-info-vec-missed, clang-এ -Rpass-missed=loop-vectorize জানিয়ে দেয় কেন হয়নি। তারপর: C-তে restrict দিয়ে aliasing নেই বলে প্রতিশ্রুতি, float reduction-এ ক্রম বদলের অনুমতি (যেমন OpenMP-এর simd reduction, বা সাবধানে -ffast-math-ধাঁচের flag — ফল একটু বদলাতে পারে, পর্ব ২৪), ডেটাকে AoS থেকে SoA-তে সাজানো, আর শেষ উপায় intrinsics. x86-এ SSE 128 bit, AVX 256 bit, AVX-512 512 bit; RISC-V Vector আর ARM SVE চওড়াটি hardware-এর হাতে ছাড়ে, তাই একই binary বিভিন্ন চওড়ায় চলে (পর্ব ৪২)।
সম্ভাব্য ফলো-আপ: “৮ lane মানেই কি ৮ গুণ?” → না; লুপ memory-bound হলে bandwidth-ই ছাদ (অংশ ৬-এর সমস্যা ক), আর Amdahl বলে vectorize না হওয়া অংশ শেষ পর্যন্ত সীমা। কিছু প্রসেসরে খুব চওড়া SIMD চালালে clock কমে যায় বলে জানা যায় — প্রজন্মভেদে আলাদা, তাই মেপে দেখা।
প্র ১০SMT (Hyper-Threading) চালু করলে কি দুটি core পাওয়া যায়? কখন SMT লাভ দেয়, কখন ক্ষতি? (মাঝারি)
সংক্ষিপ্ত উত্তর: না। SMT-তে একটি core-এর ভেতরে দুটি (বা বেশি) hardware thread — প্রত্যেকের নিজের PC আর register-অবস্থা, কিন্তু execution unit, cache আর predictor ভাগ করা। OS প্রত্যেককে একটি logical CPU দেখে। লাভ হয় যখন একটি thread cache miss বা নির্ভরতায় core-এর slot খালি রাখে; ক্ষতি হয় যখন দুটি thread একই resource (একই execution unit, L1, memory bandwidth) নিয়ে লড়ে।
গভীর উত্তর: মোট throughput বাড়ে, কিন্তু প্রতিটি thread একা চলার চেয়ে ধীর হতে পারে — latency-সংবেদনশীল কাজে এটি গুরুত্বপূর্ণ। লাভের পরিমাণ কাজভেদে খুব আলাদা, কখনো ঋণাত্মক; “SMT মানেই ৩০% লাভ” ধরনের নির্দিষ্ট সংখ্যা বলা ঠিক নয় (পর্ব ৪৩)। আলাদা core-এ সব resource আলাদা, তাই গতি প্রায় দ্বিগুণ হতে পারে যদি মেমরি আর shared cache-এর চাপ না থাকে — কিন্তু area আর power-ও প্রায় দ্বিগুণ; SMT-এর বাড়তি area তুলনায় অনেক কম বলে বর্ণিত। নিরাপত্তা: একই core-এর sibling thread-এর মধ্যে ভাগ করা resource side channel খুলতে পারে, তাই কিছু সিস্টেম SMT বন্ধ রাখে বা core scheduling ব্যবহার করে।
সম্ভাব্য ফলো-আপ: “Benchmark-এ ৮ logical CPU-তে ৮ thread চালিয়ে ৪ গুণ পেলেন — কেন?” → ৪টি physical core, প্রতিটিতে ২টি SMT thread; lscpu-তে “Thread(s) per core” দেখতাম, আর thread-দের physical core-এ বেঁধে (pinning) আবার মাপতাম।
৪ · Cache — associativity, write policy, inclusion, false sharing, coherence আর memory ordering
রিভিশন: পর্ব ৪৪ · মেমরি হায়ারার্কি, পর্ব ৪৫ · Direct-mapped cache, পর্ব ৪৬ · Set-associative cache, পর্ব ৪৭ · Cache-এর পারফরম্যান্স, পর্ব ৪৮ · Cache-বান্ধব প্রোগ্রাম, পর্ব ৫৩ · Multicore আর cache coherence
প্র ১১Associativity বাড়ালে কী লাভ, কী দাম? একটি ৩২ KiB, ৬৪ byte line-এর L1-এ direct-mapped থেকে 8-way করলে address-এর ভাগ কীভাবে বদলায়? (সহজ)
সংক্ষিপ্ত উত্তর: Associativity বাড়লে একটি block তার set-এর যেকোনো way-তে বসতে পারে, তাই conflict miss কমে। দাম: প্রতিটি access-এ n টি tag একসাথে পড়া, n টি comparator, একটি n:1 mux — hit time, area আর শক্তি বাড়ে। ৩২-bit address, ৩২ KiB, ৬৪ B line: offset সবসময় ৬ bit; direct-mapped-এ ৫১২টি set → index ৯, tag ১৭; 8-way-এ ৬৪টি set → index ৬, tag ২০; fully associative-এ index ০, tag ২৬ (পর্ব ৪৬)।
গভীর উত্তর: মোট আকার একই রেখে way দ্বিগুণ করলে set অর্ধেক — index এক bit কমে, tag এক bit বাড়ে। L1-এ সাধারণত মাঝারি associativity (প্রায়ই ৮-way) — কারণ hit time প্রতিটি load-এর পথে, আর VIPT নকশায় index আর offset মিলে page offset-এর মধ্যে থাকতে হয়: ৪ KiB page-এ ৩২ KiB L1 মানে অন্তত ৮-way (৩২ ÷ ৪ = ৮)। Replacement: নিখুঁত LRU-তে ⌈log2(n!)⌉ bit লাগে, তাই বাস্তবে pseudo-LRU tree (n − ১ bit) বা অন্য সস্তা নীতি।
সম্ভাব্য ফলো-আপ: “কোন access pattern-এ associativity-ও বাঁচাতে পারে না?” → ২-এর ঘাতের stride, যা একই set-এ বারবার পড়ে (অংশ ৬-এর সমস্যা খ-তে মাপা)। “চক্রাকারে cache-এর চেয়ে একটু বড় ডেটায় LRU কেমন?” → প্রতিবার miss; random replacement তখন ভালো করে।
প্র ১২Write-through আর write-back-এর পার্থক্য কী? Write miss-এ কী করা হয়? (সহজ)
সংক্ষিপ্ত উত্তর: Write-through প্রতিটি store cache-এর সাথে নিচের স্তরেও পাঠায় — মাঝে একটি write buffer রেখে, যাতে CPU অপেক্ষা না করে। Write-back শুধু cache-এ লেখে, dirty bit দিয়ে মনে রাখে, আর line সরানোর সময় একবারে নিচে লেখে। Write miss-এ write-allocate আগে block আনে, no-write-allocate সরাসরি নিচে লেখে; প্রচলিত জুটি WB + WA আর WT + NWA.
গভীর উত্তর: পর্ব ৪৭-এর হিসাব: একটি যোগফলের লুপে ৬৪টি store-এ write-through ২৫৬ byte লেখে, write-back মাত্র ১৬ byte. কিন্তু write-back সবসময় জেতে না — যে trace-এ dirty block একবার-দুবার লেখার পরই conflict-এ সরে যায়, সেখানে write-through কম লিখতে পারে। Write buffer-এর সীমা: store আসার গড় হার নিচের স্তরের লেখার হারের বেশি হলে buffer যত বড়ই হোক ভরবে। আরেকটি সূক্ষ্মতা: write-back L1-এ dirty ডেটার একমাত্র কপি L1-এ, তাই সেখানে ECC লাগে; write-through L1-এ শুধু parity রাখলেই চলে — কিছু পুরোনো নকশায় এই কারণে L1 write-through আর L2 write-back ছিল।
সম্ভাব্য ফলো-আপ: “DMA বা অন্য core-এর জন্য কোনটি সহজ?” → write-through, কারণ নিচের স্তর হালনাগাদ থাকে; write-back-এ coherence protocol বা cache flush লাগে (পর্ব ৫২)। “পুরো line লিখে ফেলবেন জানলে?” → কিছু ISA-তে non-temporal বা streaming store আছে, যা block আনা (allocate) এড়ায়।
প্র ১৩Inclusive, exclusive আর NINE cache hierarchy — কোনটি কখন? (কঠিন)
সংক্ষিপ্ত উত্তর: Inclusive: ভেতরের সব block বাইরের স্তরেও থাকবেই — L3 দেখেই বলা যায় কোনো core-এর কাছে কপি আছে কি না (snoop filtering সহজ), কিন্তু জায়গা নষ্ট হয় আর L3 থেকে সরালে ভেতরের কপিও বাতিল (back-invalidation). Exclusive: block যেকোনো একটি স্তরে — মোট ধারণক্ষমতা বেশি, কিন্তু স্তরের মধ্যে আদান-প্রদান বেশি। NINE: কোনো নিয়মই জোর করা হয় না।
গভীর উত্তর: সিদ্ধান্ত নির্ভর করে আকারের অনুপাতে। L3 যখন ভেতরের সব cache-এর যোগফলের চেয়ে বহু গুণ বড়, inclusion-এর অপচয় সামান্য। Core-প্রতি L2 বড় হতে থাকলে অপচয় বাড়ে — তখন non-inclusive L3 আর আলাদা snoop filter বা directory দিয়ে coherence-এর তথ্য রাখা হয়। বাস্তবে Intel-এর অনেক পুরোনো প্রজন্মের L3 inclusive বলে ব্যাপকভাবে বর্ণিত, পরের কিছু server প্রজন্মে non-inclusive; AMD-এর বেশ কিছু নকশায় L3 মূলত L2-এর victim cache বলে বর্ণিত। নির্দিষ্ট প্রজন্মের জন্য নির্মাতার নথি দেখতে হয় — এগুলো সময়ের সাথে বদলায়।
সম্ভাব্য ফলো-আপ: “Back-invalidation কেন বিপজ্জনক?” → একটি core কোনো block খুব ঘনঘন ব্যবহার করলেও L1-এ hit হওয়ায় L3 তা “দেখে না”; L3-এর LRU তাকে পুরোনো ভেবে সরায়, আর গরম ডেটা L1 থেকেও বাতিল হয়।
প্র ১৪False sharing কী? কীভাবে ধরবেন আর সারাবেন? (মাঝারি)
সংক্ষিপ্ত উত্তর: দুই thread দুটি আলাদা ভ্যারিয়েবলে লেখে, কোনো lock লাগে না, কিন্তু ভ্যারিয়েবল দুটি একই ৬৪ byte cache line-এ। Coherence চলে line ধরে, ভ্যারিয়েবল ধরে নয় — তাই প্রতিটি লেখায় line একটি core থেকে অন্যটিতে লাফায় (false sharing). ফল সঠিক থাকে, গতি কমে। সমাধান: padding বা alignas(64) দিয়ে আলাদা line-এ রাখা, বা প্রতি thread-এর নিজস্ব ভ্যারিয়েবলে জমিয়ে শেষে একবার যোগ।
গভীর উত্তর: নিচের stepper-এ MESI অবস্থার পালাবদল দেখুন। প্রতিটি যাতায়াত L1-এর কয়েক cycle-এর একটি লেখাকে core-থেকে-core অপেক্ষায় বদলে দেয় — chip-ভেদে কয়েক দশ থেকে শতাধিক cycle. ধরার উপায়: thread বাড়ালে গতি না বাড়া বা কমা; counter-এ বেশি coherence miss বা “HITM”-ধাঁচের event (একটি core-এর load অন্য core-এর modified line-এ পড়ল); Linux-এ perf c2c ঠিক কোন cache line নিয়ে টানাটানি তা দেখায়। পরিচিত জায়গা: প্রতি thread-এর counter-এর array (long hits[NTHREADS]), একটি queue-র head আর tail পাশাপাশি, একটি lock আর তার পাহারার ডেটা একই line-এ।
সম্ভাব্য ফলো-আপ: “True sharing হলে?” → দুই thread সত্যিই একই ভ্যারিয়েবল লেখে; padding সাহায্য করে না — কাজ ভাগ করে নিজস্ব অংশে জমানো বা atomic-এর সংখ্যা কমানো লাগে। “Line ১২৮ byte হলে?” → কিছু প্রসেসরে পাশের line একসাথে আনা হয় (adjacent-line prefetch) বলে কিছু লাইব্রেরি ১২৮ byte-এ pad করে — নিজের মেশিনে মেপে ঠিক করা ভালো। অংশ ৮-এর প্র ২৫-এ আসল C দিয়ে মাপা হয়েছে।
- শুরুa আর b একই line L-এ
- core 0: a++L আসে, E থেকে M
- core 1: b++L চলে যায় core 1-এ
- core 0: a++আবার ফেরত আনা
- লাখো বারping-pong
- paddingদুটি আলাদা line
| Core 0-এর কপি | |
| Core 1-এর কপি | |
| Interconnect-এ | |
| Coherence miss (মোট) |
- শুরু।
struct { long a, b; } P;— a আর b মাত্র ৮ byte দূরে, একই ৬৪ byte line L-এ। Thread 0 শুধু a বাড়ায় (core 0-এ), thread 1 শুধু b (core 1-এ)। যুক্তির দিক থেকে কিছুই ভাগাভাগি নেই। দুই core-এর কাছেই L নেই: অবস্থা I. - Core 0: a++. পড়ার miss: BusRd পাঠানো হলো, আর কেউ L রাখেনি, তাই L এল E (Exclusive) অবস্থায়। এরপর লেখা — E থেকে M নীরবে, কোনো bus transaction ছাড়াই; MESI-তে E থাকার লাভ ঠিক এটাই (প্র ১৫)। এটি সাধারণ cold miss.
- Core 1: b++. Core 1-এর কাছে L নেই। BusRd-এ core 0-এর M কপি ডেটা দেয় (আর নিচে লেখে বা সরাসরি পাঠায়), দুজনেই S. তারপর লেখার জন্য BusUpgr: core 0-এর কপি বাতিল (I), core 1-এ M. অনেক নকশা একবারে read-for-ownership (BusRdX) পাঠায় — ফল একই। Core 1-এর এটি প্রথম (cold) miss, কিন্তু এতেই core 0-এর কপি বাতিল হলো — অথচ core 1 a-কে ছোঁয়ইনি।
- Core 0: আবার a++. L এখন core 1-এ M. Core 0-এর miss, BusRdX: core 1 ডেটা দেয় আর নিজের কপি বাতিল করে। Core 0-এ M (a = 2), core 1-এ I. এটি প্রথম coherence miss — L core 0-এর কাছে ছিল, অন্যের লেখায় বাতিল হয়েছিল।
- লাখো বার। দুজনে একসাথে লিখতে থাকলে প্রায় প্রতিটি ++-এ line এদিক-ওদিক যায়। L1-এর কয়েক cycle-এর লেখা হয়ে যায় core-থেকে-core যাতায়াত — কয়েক দশ থেকে শতাধিক cycle. Coherence miss-এর সংখ্যা লেখার পালাবদলের সংখ্যার কাছাকাছি; ফল সঠিক, শুধু ধীর।
- Padding.
alignas(64)দিয়ে a যায় line L0-এ, b line L1-এ। প্রতিটি core প্রথম miss-এর পরে নিজের line-এর স্থায়ী M মালিক — আর কোনো যাতায়াত নেই। দাম: ১৬ byte-এর জায়গায় ১২৮ byte, counter-এর জন্য তুচ্ছ।
প্র ১৫MSI থাকতে MESI-তে E অবস্থা কেন? একটি write miss-এ snooping protocol কী করে? (মাঝারি)
সংক্ষিপ্ত উত্তর: Coherence-এর নিয়ম: একজন লেখক অথবা অনেক পাঠক, একসাথে দুটো নয়। MESI-তে E মানে “শুধু আমার কাছে, আর মেমরির সাথে মেলে”। কেউ ব্যক্তিগত ডেটা পড়ে তারপর লেখে — খুব সাধারণ ঘটনা — তখন MSI-তে পড়ায় S, তারপর লেখার জন্য আরেকটি bus transaction (BusUpgr) লাগত; MESI-তে E থেকে M নীরবে, একটি transaction বাঁচে।
গভীর উত্তর: Write miss (অবস্থা I): core BusRdX পাঠায় — “line চাই, লেখার জন্য”। অন্য কোনো cache-এ M থাকলে সে ডেটা দেয় (আর নিচে লেখে) এবং I হয়; S বা E-এর কপিগুলো I হয়; অনুরোধকারী M-এ যায়। S অবস্থায় লেখা হলে ডেটা আছে, শুধু অন্যদের বাতিল করতে BusUpgr. Snooping সব core-কে সব অনুরোধ শোনায় — কয়েকটি core-এ চলে, কিন্তু অনেক core-এ broadcast-এর চাপ বড়; তখন directory প্রতিটি block-এর কে কে রাখে তার হিসাব রাখে আর শুধু তাদেরই বার্তা পাঠায় (পর্ব ৫৪)। কিছু নকশায় MOESI বা MESIF-এর মতো আরও অবস্থা আছে — O বা F অবস্থা মেমরিতে না লিখে বা নির্দিষ্ট একজনকে দিয়ে ডেটা দেওয়ায়।
সম্ভাব্য ফলো-আপ: “Verification-এ কোন invariant পরীক্ষা করবেন?” → যেকোনো মুহূর্তে একটি line-এর M বা E কপি সর্বোচ্চ একটি, আর M বা E থাকলে অন্য কোনো বৈধ কপি নেই (single-writer, multiple-reader); আর প্রতিটি load সর্বশেষ লেখা মান দেখে।
প্র ১৬x86-এ ঠিকঠাক চলা একটি lock-free flag-ভিত্তিক কোড ARM বা RISC-V-এ মাঝে মাঝে ভুল ফল দেয়। কেন? coherence থাকলেও? (কঠিন)
সংক্ষিপ্ত উত্তর: Coherence একটি ঠিকানার প্রশ্ন; এখানে সমস্যা ভিন্ন ঠিকানার access-এর ক্রম — memory consistency. x86 মোটামুটি TSO: প্রায় সব ক্রম রক্ষা হয়, শুধু store-এর পরের ভিন্ন ঠিকানার load আগে চলে যেতে পারে (store buffer-এর কারণে)। ARM আর RISC-V (RVWMO) আরও ঢিলা — “ডেটা লিখি, তারপর flag = 1” অন্য core-এ উল্টো ক্রমে দেখা যেতে পারে। সমাধান: acquire/release বা fence, আর C/C++-এ প্রমিত atomic.
গভীর উত্তর: ক্লাসিক litmus test: thread 0: x = 1; r1 = y. Thread 1: y = 1; r2 = x. Sequential consistency-তে r1 = r2 = 0 অসম্ভব, কিন্তু x86-এও সম্ভব: দুই store নিজের store buffer-এ বসে থাকতেই দুই load পুরোনো ০ পড়ে (পর্ব ৫৩)। Message-passing ধাঁচের কোড (data, তারপর flag) x86-এ ঠিক চলে কারণ TSO store-store আর load-load ক্রম রাখে — কিন্তু compiler নিজেও ক্রম বদলাতে পারে, তাই x86-এও সাধারণ ভ্যারিয়েবল দিয়ে এটি নির্ভরযোগ্য নয়। সঠিক পথ: flag-এ release store আর acquire load (C11-এর memory_order_release/acquire); ARM64-এ এগুলো stlr/ldar, RISC-V-এ aq/rl bit বা fence-এ রূপ নেয়।
সম্ভাব্য ফলো-আপ: “volatile কি যথেষ্ট?” → না; C-তে volatile hardware-এর ক্রম বা atomicity দেয় না। “কেন hardware SC দেয় না?” → প্রতিটি store-এ line-এর মালিকানা পাওয়া পর্যন্ত core থামালে দশ থেকে শতাধিক cycle নষ্ট; store buffer সেই অপেক্ষা লুকায় — দাম, ঢিলা ক্রম।
৫ · TLB, huge page, DRAM আর latency-র সংখ্যা
রিভিশন: পর্ব ৪৪ · মেমরি হায়ারার্কি, পর্ব ৪৯ · Main memory, পর্ব ৫০ · Virtual memory-র hardware, পর্ব ৫৩ · MESI; OS-এর দিক: Operating Systems · TLB আর page table
এই অংশের সবচেয়ে বড় প্রশ্ন: “একটি load instruction চালালে শুরু থেকে শেষ কী হয়?” এক প্রশ্নে address translation, cache, coherence, DRAM আর out-of-order commit — সব যাচাই হয়ে যায়। আগে পুরো পথটি দেখে নিন। সময়গুলো পর্ব ৪৪-এর ধরে নেওয়া গোল সংখ্যা (৩ GHz; L1 ৪, L2 ১২, L3 ৪০ cycle, DRAM ~১০০ ns ≈ ৩০০ cycle), আর ধরে নেওয়া হয়েছে প্রতিটি স্তর একের পর এক দেখা হয়; বাস্তব chip-এ অনেক কাজ সমান্তরালে হয়।
- ১ · ঠিকানাAGU
- ২ · TLBL1 set-এর সাথে একসাথে
- ৩ · L1miss, MSHR
- ৪ · L2miss
- ৫ · L3 + coherenceকারো কাছে নেই
- ৬ · DRAMACT, READ, burst
- ৭ · fillE অবস্থায়
- ৮ · commitROB-এর মাথায়
| ঠিকানা | |
| কোথায় খোঁজা | |
| মোট সময় (cycle, ধরে নেওয়া) | |
| Line-এর অবস্থা (এই core) |
- ঠিকানা তৈরি।
lw x10, 8(x11), x11 = 0x7FFF2A40, তাই virtual address 0x7FFF2A48. Out-of-order core-এ load-টি load queue-তে একটি জায়গা পায়; আগের কোনো store একই ঠিকানায় লিখছে কি না তা store queue-তে দেখা হয় — মিললে মান সেখান থেকেই আসত (store-to-load forwarding). - TLB আর L1 একসাথে। ৪ KiB page: VPN = 0x7FFF2, page offset = 0xA48. L1 ৩২ KiB, ৮-way, ৬৪ B line → ৬৪টি set; set-এর ৬ bit আর offset-এর ৬ bit মিলে ঠিক ১২ bit — পুরোটাই page offset থেকে। তাই TLB অনুবাদ করার সময়েই L1-এর set 41-এর ৮টি tag পড়া যায় (VIPT). TLB hit: PPN 0x3C1D5. TLB miss হলে hardware walker page table হাঁটত — Sv32-এ ২টি PTE (VPN[1] = 0x1FF, VPN[0] = 0x3F2), Sv39-এ ৩টি, x86-64-এ ৪ বা ৫টি; PTE অবৈধ হলে page fault আর OS-এর handler.
- L1-এ miss. Physical address 0x3C1D5A48: tag 0x3C1D5, set 41, offset 8. ৮টি comparator-এর কোনোটিই মেলে না — miss. একটি MSHR খোলে (কোন line, কোন load অপেক্ষায়)। Core থামে না: পেছনের স্বাধীন instruction চলতে থাকে, আর তাদের miss-ও একসাথে উড়তে পারে।
- L2 — আরও ১২ cycle, miss. মোট ১৬ cycle. L2 সাধারণত প্রতি core-এ নিজস্ব। এখানে hit হলে গল্প শেষ হতো ১৬ cycle-এ।
- L3 আর coherence — আরও ৪০ cycle. L3 সব core-এর ভাগে। L3-এর সাথে রাখা coherence-এর তথ্য (inclusive L3-এর bit, snoop filter বা directory) বলে অন্য কোনো core-এর কাছে এই line নেই। থাকলে — বিশেষ করে অন্য core-এ M অবস্থায় — সেই core-ই ডেটা দিত আর তার অবস্থা বদলাত (প্র ১৫)। এখানে L3-তেও নেই: মোট ৫৬ cycle, এবার মেমরি।
- DRAM. Memory controller physical address-কে channel, bank, row আর column-এ ভাগ করে। Row বন্ধ থাকলে ACT (tRCD), তারপর READ (CL), তারপর burst: DDR4-3200 22-22-22-এ ১৩.৭৫ + ১৩.৭৫ + ২.৫ ≈ ৩০ ns, chip-এর ভেতরেই। On-chip পথ, controller-এর সারি আর ফেরার পথ মিলিয়ে load থেকে ডেটা পর্যন্ত ধরা হলো ~১০০ ns ≈ ৩০০ cycle; মোট ৩৫৬ cycle.
- Fill আর জাগানো। পুরো ৬৪ byte line (0x3C1D5A40–0x3C1D5A7F) ফিরে আসে, inclusion-নীতিমতো L3-L2-L1-এ বসে; অন্য কারো কাছে নেই বলে অবস্থা E — পরে এই core লিখলে নীরবে M, কোনো বার্তা লাগবে না। চাওয়া word x10-এর physical register-এ যায়, আর এর ওপর নির্ভরশীল instruction-গুলো জেগে ওঠে। Victim line dirty হলে তার write-back আলাদা।
- Commit. Load-টি ROB-এর মাথায় এলে, আর আগের কোনো শাখা ভুল বা exception না হলে, retire হয় — x10 এখন architectural অর্থে হালনাগাদ। অনুমানের ভুল পথে থাকলে এই load-এর ফল ফেলে দেওয়া হতো, কিন্তু আনা line cache-এ থেকে যেত — Spectre-এর মূল সূত্র এখানেই (প্র ০৮)।
প্র ১৭“একটি load instruction চালালে কী হয়?” — দুই মিনিটে উত্তর দিন, তারপর ইন্টারভিউয়ার যেখানে খুঁড়তে পারেন সেগুলো বলুন। (কঠিন)
সংক্ষিপ্ত উত্তর: “ঠিকানা তৈরি; TLB দিয়ে virtual থেকে physical — miss হলে page walk, অবৈধ হলে page fault; একই সাথে L1-এর set পড়া (VIPT); L1 hit হলে কয়েক cycle-এ শেষ; miss হলে MSHR খুলে L2, তারপর shared L3 — সেখানে coherence-এর তথ্য দেখে অন্য core-এর কপি থাকলে সেখান থেকে; না পেলে memory controller-এর মাধ্যমে DRAM — row খোলা, column পড়া, burst-এ পুরো line; ফেরার পথে cache-গুলোতে বসানো, নির্ভরশীল instruction জাগানো; শেষে ROB-এর মাথায় এলে commit.” উপরের stepper এই কথাগুলোরই ছবি।
গভীর উত্তর — যেখানে খোঁড়া হয়: (১) VIPT-এর শর্ত: cache-এর আকার ≤ way × page size; না মানলে একই physical line দুই set-এ বসতে পারে (synonym বা alias). (২) TLB miss-এর খরচ: Sv39-এ ৩টি PTE পড়া, page-walk cache থাকলে কম; virtualization-এ দ্বিমাত্রিক walk-এ সবচেয়ে খারাপ ক্ষেত্রে ২৪টি PTE (পর্ব ৫০)। (৩) Load আর আগের store: ঠিকানা না জানা store-এর আগে load চালানো হবে কি না — memory dependence prediction, ভুল হলে replay. (৪) Prefetcher হয়তো line আগেই এনে রেখেছে — তখন miss-ই হয় না। (৫) NUMA মেশিনে line অন্য socket-এর মেমরিতে থাকলে আরও দূরের পথ।
সম্ভাব্য ফলো-আপ: “Line যদি অন্য core-এ M অবস্থায় থাকত?” → সেই core snoop বা directory-র বার্তা পেয়ে ডেটা পাঠায়; read-এর জন্য দুজনেই S (MESI-তে), ফলে L3 থেকে পাওয়ার চেয়ে কিছুটা ধীর, কিন্তু DRAM-এর চেয়ে দ্রুত।
প্র ১৮TLB reach কী? Huge page কখন বড় লাভ দেয়, আর কখন সমস্যা করে? (মাঝারি)
সংক্ষিপ্ত উত্তর: TLB reach = TLB-র ঘর × page size — একসাথে কতটা মেমরির অনুবাদ TLB-তে আছে। ৬৪ ঘরের L1 TLB-তে ৪ KiB page: ২৫৬ KiB; ১৫৩৬ ঘরের L2 TLB: ৬ MiB. অথচ L3 নিজেই কয়েক ডজন MiB হতে পারে — ডেটা cache-এ, অনুবাদ TLB-তে নেই, এমন অবস্থা খুবই সম্ভব। একই ১৫৩৬ ঘরে ২ MiB huge page হলে reach ৩ GiB.
গভীর উত্তর: লাভ বেশি বড় working set আর এলোমেলো access-এ: ডেটাবেসের buffer pool, বড় hash table, graph, VM-এর অতিথি মেমরি (যেখানে প্রতিটি TLB miss দ্বিমাত্রিক walk). Huge page-এ walk-এ এক স্তর কম, আর page table নিজেই cache-এ কম জায়গা নেয়। সমস্যা: ভেতরের অপচয় (২ MiB-এর অল্প অংশ ব্যবহার), ভৌত মেমরিতে ২ MiB-এর টানা খালি জায়গা খুঁজে পাওয়া (fragmentation), আর OS-এর transparent huge page-এর পটভূমি-কাজে মাঝে মাঝে latency-র ঝাঁকুনি — কিছু ডেটাবেস নির্মাতা এ কারণে নির্দিষ্ট সেটিং প্রস্তাব করে। Linux-এর দিক Operating Systems কোর্সে।
সম্ভাব্য ফলো-আপ: “TLB miss হচ্ছে কি না কীভাবে বুঝবেন?” → perf stat -e dTLB-load-misses-ধাঁচের event (মেশিনভেদে নাম আলাদা), আর huge page চালু-বন্ধ করে একই কাজ মাপা। “Context switch-এ TLB?” → ASID বা PCID থাকলে মুছতে হয় না; অন্য core-এর TLB হালনাগাদে TLB shootdown — একটি দামি inter-processor interrupt.
প্র ১৯DRAM-এর bandwidth বহু গুণ বেড়েছে, latency প্রায় একই। কেন, আর প্রোগ্রামারের জন্য এর মানে কী? (মাঝারি)
সংক্ষিপ্ত উত্তর: Bandwidth বাড়ানো যায় চওড়া আর দ্রুত bus, বেশি channel আর prefetch দিয়ে — প্রতিটি প্রজন্মে interface-এর গতি বেড়েছে। Latency বাঁধা DRAM cell-এর পদার্থবিজ্ঞানে — capacitor-এর ছোট চার্জ sense amplifier-কে পড়তে হয়, row খুলতে হয় — তাই ns-এ প্রায় একই থেকেছে। প্রোগ্রামারের জন্য মানে: স্বাধীন অনেক access একসাথে চালালে (stream, prefetch, বড় batch) bandwidth পাওয়া যায়; একটির পর একটি নির্ভরশীল access (pointer chasing) প্রতিবার পুরো latency দেয়।
গভীর উত্তর: পর্ব ৪৯-এর হিসাব: সর্বোচ্চ bandwidth = MT/s × bus-প্রস্থ (byte) × channel; DDR4-3200, ৬৪ bit: ২৫.৬ GB/s, dual channel ৫১.২ GB/s. CAS latency (ns) = CL × ২০০০ ÷ MT/s: DDR4-3200 CL22 → ১৩.৭৫ ns; নতুন প্রজন্মে CL-এর সংখ্যা বড়, কিন্তু ns-এ প্রায় কাছাকাছি থাকে। Row hit = tCL, বন্ধ bank = tRCD + tCL, conflict = tRP + tRCD + tCL — তাই access-এর ধরন (ক্রমানুসারী বনাম এলোমেলো) latency-ও বদলায়। দুইয়ের সেতু Little-এর সূত্র: একসাথে উড়ন্ত byte = bandwidth × latency (অংশ ৬-এর সমস্যা ঙ)।
সম্ভাব্য ফলো-আপ: “HBM কেন GPU-তে?” → খুব চওড়া interface আর কাছাকাছি বসানো stack, তাই প্রচুর bandwidth — latency-তে বড় লাভ নয়। “Peak bandwidth কি পাওয়া যায়?” → বাস্তবে কম; refresh, row conflict আর read-write পালাবদলে কিছুটা হারায় — মেপে দেখার জন্য STREAM-ধাঁচের benchmark.
প্র ২০“Latency numbers every programmer should know” — কয়েকটি বলুন। এগুলো কতটা বিশ্বাসযোগ্য? (সহজ)
সংক্ষিপ্ত উত্তর: নির্ভুল সংখ্যা নয়, মাত্রা (order of magnitude) মনে রাখুন: L1 hit ~১ ns, L2 কয়েক ns, L3 ~১০–২০ ns, DRAM ~১০০ ns, SSD-র একটি এলোমেলো read কয়েক দশ µs, একই data center-এ network round trip মোটামুটি ০.১–১ ms, HDD-র একটি এলোমেলো read কয়েক ms, মহাদেশ পেরিয়ে round trip ১০০ ms-এর মাত্রায়। এগুলো যন্ত্র, প্রজন্ম আর অবস্থাভেদে কয়েক গুণ বদলায়; তাই “প্রায়” আর “মাত্রা” বলে বলাই সৎ।
গভীর উত্তর: সবচেয়ে কাজের হলো অনুপাতগুলো: একটি DRAM miss-এ প্রায় ৭৫টি L1 hit-এর সময়; SSD DRAM-এর চেয়ে কয়েকশো গুণ ধীর; HDD SSD-এর চেয়ে প্রায় ১০০ গুণ। নিচের script পর্ব ৪৪-এর সংখ্যাগুলোকে মানুষের মাপে আনে: এক cycle যদি এক সেকেন্ড হতো। নিজের মেশিনে আসল সংখ্যা মাপার উপায় পর্ব ৪৪-এর random-access staircase.
সম্ভাব্য ফলো-আপ: “Network কি কখনো লোকাল ডিস্কের চেয়ে দ্রুত?” → হ্যাঁ, একই data center-এ অন্য যন্ত্রের RAM থেকে পড়া একটি HDD seek-এর চেয়ে দ্রুত হতে পারে — এজন্যই distributed cache-এর ধারণা।
// "Latency numbers" as rough orders of magnitude -- ASSUMED round values (as in lesson 44), 3 GHz CPU
const GHZ = 3; // 1 cycle = 1/3 ns
const ev = [["register read", 1], ["L1 hit", 4], ["L2 hit", 12], ["L3 hit", 40],
["DRAM access", 300], ["SSD random read", 150e3], ["same-datacenter round trip", 1.5e6],
["HDD random read", 15e6], ["intercontinental round trip", 600e6]]; // in cycles
function human(s) { // seconds -> a readable human-scale string
if (s < 60) return s.toFixed(0) + " s";
if (s < 3600) return (s / 60).toFixed(1) + " min";
if (s < 86400) return (s / 3600).toFixed(1) + " hours";
if (s < 365 * 86400) return (s / 86400).toFixed(1) + " days";
return (s / (365 * 86400)).toFixed(1) + " years";
}
function ns(c) { const t = c / GHZ; return t < 1e3 ? t.toFixed(1) + " ns" : t < 1e6 ? (t / 1e3).toFixed(1) + " us" : (t / 1e6).toFixed(1) + " ms"; }
console.log("event time cycles if 1 cycle = 1 second");
for (const [name, c] of ev)
console.log(name.padEnd(28), ns(c).padStart(8), String(c).padStart(11), " ", human(c));
console.log("\nratios worth remembering:");
console.log(" DRAM / L1 =", 300 / 4, "x (one miss = about 75 L1 hits)");
console.log(" SSD / DRAM =", 150e3 / 300, "x");
console.log(" HDD / SSD =", 15e6 / 150e3, "x");আসল আউটপুট:
event time cycles if 1 cycle = 1 second
register read 0.3 ns 1 1 s
L1 hit 1.3 ns 4 4 s
L2 hit 4.0 ns 12 12 s
L3 hit 13.3 ns 40 40 s
DRAM access 100.0 ns 300 5.0 min
SSD random read 50.0 us 150000 1.7 days
same-datacenter round trip 500.0 us 1500000 17.4 days
HDD random read 5.0 ms 15000000 173.6 days
intercontinental round trip 200.0 ms 600000000 19.0 years
ratios worth remembering:
DRAM / L1 = 75 x (one miss = about 75 L1 hits)
SSD / DRAM = 500 x
HDD / SSD = 100 xএক cycle এক সেকেন্ড হলে L1 থেকে ডেটা আসে ৪ সেকেন্ডে, DRAM থেকে ৫ মিনিটে, SSD থেকে প্রায় ১.৭ দিনে, আর HDD-র একটি এলোমেলো read প্রায় ১৭৪ দিন — প্রায় ছয় মাস। মহাদেশ পেরিয়ে একটি round trip ১৯ বছর। তাই একটি cache miss-কে “মাত্র ১০০ ns” বলে উড়িয়ে দেওয়া যায় না: CPU-র চোখে সেটা পাঁচ মিনিট বসে থাকা, যখন প্রতি সেকেন্ডে কয়েকটি instruction শেষ করার ক্ষমতা ছিল। শেষের অনুপাতগুলো (৭৫, ৫০০, ১০০) ইন্টারভিউতে মুখে মুখে হিসাবের ভিত্তি — তবে মনে রাখবেন, সংখ্যাগুলো ধরে নেওয়া গোল মান, যন্ত্রভেদে আলাদা।
৬ · মুখে মুখে হিসাব — পাঁচটি back-of-envelope সমস্যা, script-এ যাচাই
রিভিশন: পর্ব ০৩ · পারফরম্যান্স আর Amdahl, পর্ব ৪৭ · AMAT আর MLP, পর্ব ৪৮ · Loop-এর ক্রম, পর্ব ৪৯ · DRAM bandwidth, পর্ব ৫৪ · Amdahl, Gustafson আর roofline
প্রতিটি সমস্যায় আগে কাগজে হাতে আন্দাজ করুন — গোল সংখ্যা, একক লিখে — তারপর script চালিয়ে মেলান। ইন্টারভিউতে script থাকবে না; কিন্তু অনুশীলনের সময় script বলে দেয় আপনার মুখের হিসাব কোথায় ভুল। সব মেশিন-সংখ্যা শেখানোর জন্য ধরে নেওয়া, কোনো নির্দিষ্ট chip-এর নয়; প্রশ্নে যা দেওয়া নেই, ইন্টারভিউতে তা নিজে অনুমান হিসেবে জোরে বলবেন।
সমস্যা ক · একটি ২ GiB array একবার যোগ করতে অন্তত কত সময়? (মাঝারি)
২২৮টি double (২ GiB) একটি array-তে আছে, cache-এ নেই। একটি ৩ GHz core এগুলোর যোগফল বের করবে। মেমরি DDR4-3200, দুই channel (peak ৫১.২ GB/s). ধরে নিন floating point যোগের latency ৪ cycle, আর SIMD দিয়ে core প্রতি cycle-এ সর্বোচ্চ ৮টি double যোগ করতে পারে। সময়ের নিচের সীমা কত, আর কে সীমা টানে — মেমরি না হিসাব?
হাতে হিসাব: byte = ২৩১ ≈ ২.১৫ × ১০৯; ÷ ৫১.২ × ১০৯ ≈ ০.০৪২ s — মেমরির মেঝে প্রায় ৪২ ms. হিসাবের দিক: ২২৮ ≈ ২.৭ × ১০৮টি যোগ। একটি মাত্র accumulator-এ (s += a[i]) প্রতিটি যোগ আগেরটির ফলের অপেক্ষা করে, তাই ২.৭ × ১০৮ × ৪ cycle ÷ ৩ × ১০৯ ≈ ০.৩৬ s. অর্থাৎ সরল লুপটি মেমরিতে নয়, যোগের নির্ভরতার শৃঙ্খলে আটকে। কয়েকটি আলাদা accumulator আর SIMD দিলে হিসাব ~১১ ms-এ নামে, আর তখন মেমরিই সীমা।
// Back-of-envelope: sum 2^28 doubles (2 GiB) once. Which limit wins? ALL machine numbers ASSUMED.
const n = 2 ** 28, bytes = n * 8; // 8 bytes per double
const GHZ = 3e9; // 3 GHz core
const peakBW = 3200e6 * 8 * 2; // DDR4-3200, 64-bit, 2 channels = 51.2 GB/s
const ADD_LAT = 4; // assumed FP-add latency (cycles)
const SIMD_ADDS = 8; // assumed: 2 SIMD units x 4 doubles per cycle
const gb = (x) => (x / 1e9).toFixed(1) + " GB";
const ms = (t) => (t * 1e3).toFixed(1).padStart(6) + " ms";
console.log(`data = ${n} doubles = ${gb(bytes)} (${bytes / 2 ** 30} GiB)`);
const tMem = bytes / peakBW;
const tChain = n * ADD_LAT / GHZ; // one accumulator: every add waits for the previous
const tScalar = n / GHZ; // 1 add per cycle (several accumulators, no SIMD)
const tSimd = n / SIMD_ADDS / GHZ; // many accumulators + SIMD
console.log("memory : bytes / 51.2 GB/s =", ms(tMem));
console.log("compute 1: one accumulator, 4-cycle add =", ms(tChain));
console.log("compute 2: 1 add per cycle =", ms(tScalar));
console.log("compute 3: SIMD, 8 adds per cycle =", ms(tSimd));
for (const [name, t] of [["one accumulator", tChain], ["1 add/cycle", tScalar], ["SIMD", tSimd]]) {
const total = Math.max(tMem, t); // the slower limit decides (ideal overlap)
console.log(`${name.padEnd(16)} -> at least ${ms(total)}, ${tMem >= t ? "memory-bound" : "compute-bound"},`
+ ` uses ${(100 * tMem / total).toFixed(0)}% of peak bandwidth`);
}আসল আউটপুট:
data = 268435456 doubles = 2.1 GB (2 GiB)
memory : bytes / 51.2 GB/s = 41.9 ms
compute 1: one accumulator, 4-cycle add = 357.9 ms
compute 2: 1 add per cycle = 89.5 ms
compute 3: SIMD, 8 adds per cycle = 11.2 ms
one accumulator -> at least 357.9 ms, compute-bound, uses 12% of peak bandwidth
1 add/cycle -> at least 89.5 ms, compute-bound, uses 47% of peak bandwidth
SIMD -> at least 41.9 ms, memory-bound, uses 100% of peak bandwidthতিনটি শিক্ষা। এক, একটি accumulator-এর লুপ অন্তত প্রায় ৩৫৮ ms নেয় আর peak bandwidth-এর মাত্র ১২% ব্যবহার করে — এটি latency-bound, তাই দ্রুত মেমরি কিনে লাভ নেই। দুই, gcc বা clang সাধারণ flag-এ এই float লুপ নিজে থেকে কয়েকটি accumulator-এ ভাঙে না, কারণ float যোগের ক্রম বদলালে ফল সামান্য বদলাতে পারে (প্র ০৯); হাতে কয়েকটি accumulator লিখলে বা reduction-এর অনুমতি দিলে খোলে। তিন, SIMD-এর পরে সীমা ~৪১.৯ ms, পুরোপুরি memory-bound — তবে একটি core একা আসলে ৫১.২ GB/s টানতে পারে কি না, সেটি সমস্যা ঙ-এর প্রশ্ন। ইন্টারভিউতে উত্তর হবে: “নিচের সীমা প্রায় ৪০ ms-এর মাত্রায়, যদি লুপ যথেষ্ট সমান্তরাল হয় আর একাধিক core বা যথেষ্ট উড়ন্ত miss থাকে; নইলে কয়েকশো ms.”
সমস্যা খ · একটি লুপে কতটি L1 miss? (মাঝারি)
double a[256][256] (row-major, প্রতিটি row ২০৪৮ byte, শুরু ৬৪-byte সীমায়)। L1 data cache ৩২ KiB, ৮-way, ৬৪ B line, LRU, শুরুতে খালি। পুরো array-র যোগফল দুইভাবে: row ধরে (ভেতরের লুপ j) আর column ধরে (ভেতরের লুপ i). প্রতিটিতে কতটি miss? এরপর প্রতিটি row ২৬৪ double লম্বা করে (padding) column ধরে চালালে কত?
হাতে হিসাব: এক line-এ ৮টি double. Row ধরে: প্রতি ৮টিতে একটি compulsory miss → ৬৫,৫৩৬ ÷ ৮ = ৮,১৯২ (১২.৫%). Column ধরে: L1-এ ৬৪টি set; a[i][j]-এর line নম্বর = ৩২i + j/৮, তাই set = (৩২i + j/৮) mod ৬৪ — জোড় i একটি set-এ, বিজোড় i আরেকটিতে। একটি column-এর ২৫৬টি line মাত্র ২টি set-এ, যেখানে ধরে মোট ২ × ৮ = ১৬টি line. পরের column আবার row 0-তে ফিরলে আগের line বহু আগে বেরিয়ে গেছে: প্রতিটি access miss, ৬৫,৫৩৬. অথচ একটি column-এর ২৫৬ line মাত্র ১৬ KiB — ধারণক্ষমতা যথেষ্ট ছিল; সমস্যাটি conflict. Row ২৬৪ double = ২১১২ byte = ৩৩ line; ৩৩ বিজোড়, তাই column-এর line-গুলো ৬৪টি set-এই ছড়ায়, প্রতি set-এ ৪টি — আঁটে; পরের ৭টি column hit. মোট আবার ৮,১৯২.
// How many L1 misses? 32 KiB, 8-way, 64 B lines, LRU (64 sets). double a[256][ROW], sum all 256 x 256.
const LINE = 64, WAYS = 8, SETS = 32768 / LINE / WAYS;
function run(rowLen, columnWise) {
const sets = Array.from({ length: SETS }, () => []); // each set: line numbers, most recent last
let misses = 0, accesses = 0;
for (let x = 0; x < 256; x++)
for (let y = 0; y < 256; y++) {
const [i, j] = columnWise ? [y, x] : [x, y]; // column-wise: inner loop walks down a column
const line = Math.floor((i * rowLen + j) * 8 / LINE);
const s = sets[line % SETS], k = s.indexOf(line);
accesses++;
if (k >= 0) s.splice(k, 1); // hit: move to most-recent position
else { misses++; if (s.length === WAYS) s.shift(); } // miss: evict least-recent if full
s.push(line);
}
return [accesses, misses];
}
console.log(`L1: ${SETS} sets x ${WAYS} ways x ${LINE} B; array rows of 256 doubles = 2048 B`);
for (const [name, rowLen, col] of [["row-wise, row 256", 256, false],
["column-wise, row 256", 256, true], ["column-wise, row 264 (padded)", 264, true]]) {
const [a, m] = run(rowLen, col);
const sUsed = new Set(Array.from({ length: 256 }, (_, i) => Math.floor(i * rowLen * 8 / LINE) % SETS)).size;
console.log(`${name.padEnd(30)} accesses ${a} misses ${String(m).padStart(5)}`
+ ` miss rate ${(100 * m / a).toFixed(1).padStart(5)}% sets used by one column: ${sUsed}`);
}আসল আউটপুট:
L1: 64 sets x 8 ways x 64 B; array rows of 256 doubles = 2048 B
row-wise, row 256 accesses 65536 misses 8192 miss rate 12.5% sets used by one column: 2
column-wise, row 256 accesses 65536 misses 65536 miss rate 100.0% sets used by one column: 2
column-wise, row 264 (padded) accesses 65536 misses 8192 miss rate 12.5% sets used by one column: 64Simulator হাতের হিসাব হুবহু মেলায়: row ধরে ৮,১৯২ miss (১২.৫%), column ধরে ৬৫,৫৩৬ (১০০%) — একটি column মাত্র ২টি set ব্যবহার করে। মাত্র ৮টি double-এর padding দিলে column ৬৪টি set-এই ছড়ায়, আর miss আবার ৮,১৯২. ইন্টারভিউতে এটি একটি প্রিয় ফাঁদ: ২-এর ঘাতের মাপের matrix (যেমন ১০২৪ × ১০২৪) column ধরে হাঁটলে associativity-ও বাঁচায় না। দুটি সমাধান বলবেন — loop-এর ক্রম বদলে row ধরে হাঁটা (loop interchange), আর না পারলে leading dimension-এ padding. মনে রাখবেন, এটি L1-এর মডেল; আসল যন্ত্রে prefetcher, L2 আর TLB-ও ভূমিকা রাখে।
সমস্যা গ · Roofline — এই kernel কত GFLOP/s পর্যন্ত যেতে পারে? (মাঝারি)
একটি মেশিনের peak ২০০ GFLOP/s (double) আর মেমরি bandwidth ৫০ GB/s. পাঁচটি kernel: যোগফল, dot product, daxpy (y[i] += a·x[i]), ২D ৫-point stencil (পাঁচটি মানের গড়: ৪টি যোগ আর ১টি গুণ; পাশের মান cache থেকে আসে, আর ফল লেখায় write-allocate-এর বাড়তি পড়া নেই), আর ৬৪ × ৬৪ tile-এ ভাগ করা matrix গুণ। প্রতিটির operational intensity আর attainable GFLOP/s কত? daxpy দ্বিগুণ দ্রুত করতে কোনটি কাজ করবে — core দ্বিগুণ, bandwidth দ্বিগুণ, নাকি একই y-তে দুটি daxpy (y += a·x, তারপর y += b·z) এক পাসে?
হাতে হিসাব: Roofline: attainable = min(peak, bandwidth × I), যেখানে operational intensity I = FLOP ÷ DRAM-এর byte. Ridge point = ২০০ ÷ ৫০ = ৪ FLOP/byte — এর নিচের সব kernel memory-bound. daxpy: প্রতি উপাদানে ২ FLOP (গুণ আর যোগ), byte ২৪ (x পড়া, y পড়া, y লেখা) → I ≈ ০.০৮৩ → ৫০ × ০.০৮৩ ≈ ৪.১৭ GFLOP/s, peak-এর মাত্র ২%. Tile করা matrix গুণে A আর B প্রতিটি N ÷ ৬৪ বার পড়া হয়, তাই প্রতি গুণ-যোগে ১৬ ÷ ৬৪ = ০.২৫ byte → I = ৮, ridge-এর ওপরে — compute-bound.
// Roofline bound: attainable = min(peak, bandwidth x intensity). ASSUMED machine: 200 GFLOP/s, 50 GB/s.
const PEAK = 200, BW = 50; // GFLOP/s, GB/s (double precision)
console.log(`ridge point = ${PEAK} / ${BW} = ${PEAK / BW} FLOP/byte`);
// [name, FLOPs per element (or per point), DRAM bytes per element] -- counted by hand, see the text
const kernels = [
["sum += a[i]", 1, 8],
["dot: s += x[i]*y[i]", 2, 16],
["daxpy: y[i] += a*x[i]", 2, 24], // read x, read y, write y
["2D 5-point stencil", 5, 16], // neighbours come from cache: read 1 new, write 1
["matmul, 64x64 tiles", 2, 0.25], // per multiply-add: A and B re-read N/64 times
];
console.log("kernel FLOP/B attainable GFLOP/s bound % of peak");
for (const [name, f, b] of kernels) {
const I = f / b, att = Math.min(PEAK, BW * I);
console.log(name.padEnd(25), I.toFixed(3).padStart(7), att.toFixed(2).padStart(14), " ",
(BW * I < PEAK ? "memory " : "compute"), (100 * att / PEAK).toFixed(1).padStart(10));
}
// what would make daxpy 2x faster? (a) 2x cores (b) 2x bandwidth (c) fuse two daxpy passes
const I = 2 / 24;
console.log(`\ndaxpy now ${(BW * I).toFixed(2)} | 2x cores: ${Math.min(PEAK * 2, BW * I).toFixed(2)}`
+ ` | 2x bandwidth: ${(2 * BW * I).toFixed(2)} | fused 2 passes (4 FLOP / 32 B): ${(BW * 4 / 32).toFixed(2)} GFLOP/s`);আসল আউটপুট:
ridge point = 200 / 50 = 4 FLOP/byte
kernel FLOP/B attainable GFLOP/s bound % of peak
sum += a[i] 0.125 6.25 memory 3.1
dot: s += x[i]*y[i] 0.125 6.25 memory 3.1
daxpy: y[i] += a*x[i] 0.083 4.17 memory 2.1
2D 5-point stencil 0.313 15.63 memory 7.8
matmul, 64x64 tiles 8.000 200.00 compute 100.0
daxpy now 4.17 | 2x cores: 4.17 | 2x bandwidth: 8.33 | fused 2 passes (4 FLOP / 32 B): 6.25 GFLOP/sপাঁচটির চারটি memory-bound: যোগফল আর dot product ৬.২৫, daxpy ৪.১৭, stencil ১৫.৬৩ GFLOP/s — peak-এর ২ থেকে ৮%. শুধু tile করা matrix গুণ ছাদ ছোঁয় (২০০)। শেষ লাইনই আসল শিক্ষা: daxpy-তে core দ্বিগুণ করলে কিছুই বদলায় না (৪.১৭), bandwidth দ্বিগুণে ৮.৩৩; আর একই y-তে দুটি daxpy এক পাসে করলে (৪ FLOP; x, z, y পড়া আর y লেখা মিলে ৩২ byte) ৬.২৫ — কোনো নতুন hardware ছাড়াই দেড় গুণ। ইন্টারভিউতে বলবেন: “memory-bound kernel-এ আগে I বাড়াই — fusion, blocking, ছোট data type — তারপর hardware.” Stencil-এর হিসাবে write-allocate ধরলে লেখার জন্যও একবার পড়া লাগে (byte ১৬-এর বদলে ২৪) — এই অনুমানটি জোরে বলা ভালো।
সমস্যা ঘ · একটি parallelisation পরিকল্পনা — কত core নেবেন? (মাঝারি)
একটি কাজ এক core-এ ১০০ s নেয়: ইনপুট পড়া ১০ s (serial), হিসাব ৮৫ s (পুরো সমান্তরাল করা যায়), ফল মেলানো ৫ s (serial). প্রতিটি বাড়তি core-এর জন্য সমন্বয়ের খরচ ০.১ s ধরুন। (ক) শুধু হিসাব সমান্তরাল করলে সর্বোচ্চ speedup কত, আর কত core-এ সবচেয়ে কম সময়? (খ) ইনপুট পড়া ৪টি সমান্তরাল stream-এ ভেঙে ১০ s থেকে ২.৫ s করলে কী বদলায়?
হাতে হিসাব: Amdahl: serial অংশ ১৫ s, তাই overhead ছাড়া সীমা ১০০ ÷ ১৫ ≈ ৬.৬৭ গুণ। Overhead-সহ T(N) = ১৫ + ৮৫/N + ০.১(N − ১); ন্যূনতম যেখানে ৮৫/N² = ০.১, অর্থাৎ N = √৮৫০ ≈ ২৯. পরিকল্পনা খ-তে serial ৭.৫ s, সীমা ১৩.৩ গুণ — একই core-সংখ্যায় অনেক বেশি লাভ।
// Parallelisation plan, Amdahl-style. 1-core job = 100 s: read input 10 s (serial), compute 85 s
// (parallel), merge 5 s (serial). ASSUMED coordination overhead: 0.1 s per extra core.
const T = (serial, par, N, ovh = 0.1) => serial + par / N + ovh * (N - 1);
const plans = [["A: parallelise compute only", 15, 85],
["B: A + read input with 4 parallel streams (10 s -> 2.5 s)", 7.5, 85]];
for (const [name, serial, par] of plans) {
console.log(`${name}\n Amdahl limit (no overhead) = 100 / ${serial} = ${(100 / serial).toFixed(2)}x`);
let best = [1, 100];
const row = [];
for (const N of [1, 2, 4, 8, 16, 32, 64]) {
const t = T(serial, par, N);
if (t < best[1]) best = [N, t];
row.push(`N=${N}: ${t.toFixed(1)} s (${(100 / t).toFixed(2)}x)`);
}
console.log(" " + row.slice(0, 4).join(" | ") + "\n " + row.slice(4).join(" | "));
const nOpt = Math.sqrt(par / 0.1); // d/dN (par/N + 0.1 N) = 0
console.log(` best of the list: N=${best[0]}; calculus optimum N = sqrt(${par}/0.1) = ${nOpt.toFixed(1)}`
+ ` -> ${T(serial, par, nOpt).toFixed(2)} s`);
}
// Gustafson view: grow the problem with N (serial part stays 15 s of a 100 s run on N cores)
const s = 0.15;
console.log(`Gustafson, s = ${s}: scaled speedup N - s(N - 1): N=8 -> ${(8 - s * 7).toFixed(2)}, N=64 -> ${(64 - s * 63).toFixed(2)}`);আসল আউটপুট:
A: parallelise compute only
Amdahl limit (no overhead) = 100 / 15 = 6.67x
N=1: 100.0 s (1.00x) | N=2: 57.6 s (1.74x) | N=4: 36.5 s (2.74x) | N=8: 26.3 s (3.80x)
N=16: 21.8 s (4.58x) | N=32: 20.8 s (4.82x) | N=64: 22.6 s (4.42x)
best of the list: N=32; calculus optimum N = sqrt(85/0.1) = 29.2 -> 20.73 s
B: A + read input with 4 parallel streams (10 s -> 2.5 s)
Amdahl limit (no overhead) = 100 / 7.5 = 13.33x
N=1: 92.5 s (1.08x) | N=2: 50.1 s (2.00x) | N=4: 29.1 s (3.44x) | N=8: 18.8 s (5.31x)
N=16: 14.3 s (6.99x) | N=32: 13.3 s (7.54x) | N=64: 15.1 s (6.61x)
best of the list: N=32; calculus optimum N = sqrt(85/0.1) = 29.2 -> 13.23 s
Gustafson, s = 0.15: scaled speedup N - s(N - 1): N=8 -> 6.95, N=64 -> 54.55পরিকল্পনা A-তে ৮ core-এ ৩.৮০ গুণ, ৩২-এ ৪.৮২ গুণ — আর ৬৪ core-এ উল্টো ধীর (৪.৪২ গুণ), কারণ সমন্বয়ের খরচ হিসাবের লাভকে ছাড়িয়ে যায়; গাণিতিক সর্বোত্তম N ≈ ২৯.২, সময় ২০.৭৩ s. পরিকল্পনা B-তে শুধু serial অংশ ১৫ থেকে ৭.৫ s করায় ৩২ core-এ ৭.৫৪ গুণ। ইন্টারভিউর উত্তর: “আগে serial অংশ কমাব — এখানে ইনপুট পড়া — কারণ ৩২ core-এ বাকি সময়ের বেশিরভাগই serial; core বাড়ানো তার পরে।” শেষ লাইনে Gustafson-এর দৃষ্টিভঙ্গি: core-এর সাথে কাজও বাড়ালে (weak scaling) ৬৪ core-এ scaled speedup ৫৪.৫৫ — কোন সূত্র প্রযোজ্য, তা নির্ভর করে কাজটি স্থির, নাকি core-এর সাথে বড় হয়।
সমস্যা ঙ · একটি core একা কত memory bandwidth টানতে পারে? (কঠিন)
DRAM latency ১০০ ns, line ৬৪ byte. (ক) ১০, ২৫.৬ আর ৫১.২ GB/s পেতে কতটি miss একসাথে উড়ন্ত থাকতে হবে? (খ) একটি core-এ একসাথে সর্বোচ্চ ১০টি L1 miss উড়তে পারলে সে কত GB/s পাবে? (গ) ১ কোটি node-এর একটি linked list-এ প্রতিটি node একটি miss হলে হাঁটতে কত সময় লাগবে, আর একই byte stream করলে কত?
হাতে হিসাব: Little-এর সূত্র: উড়ন্ত byte = bandwidth × latency. ৫১.২ GB/s × ১০০ ns = ৫১২০ byte = ৮০টি line. ১০টি উড়ন্ত miss → ১০ × ৬৪ ÷ ১০০ ns = ৬.৪ GB/s. Linked list-এ প্রতিটি load আগের load-এর ফলের ওপর নির্ভর করে, তাই একবারে একটিই miss: ১০৭ × ১০০ ns = ১ s; stream করলে ৬৪ × ১০৭ byte ÷ ৫১.২ GB/s = ১২.৫ ms.
// Little's law for memory: bytes in flight = bandwidth x latency. ASSUMED: 100 ns DRAM latency, 64 B lines.
const LAT = 100e-9, LINE = 64;
const gbs = (x) => (x / 1e9).toFixed(2) + " GB/s";
console.log("Misses that must be in flight to reach a bandwidth:");
for (const bw of [10e9, 25.6e9, 51.2e9]) {
const inflight = bw * LAT / LINE;
console.log(` ${gbs(bw).padStart(11)} needs ${bw * LAT} bytes in flight = ${inflight.toFixed(1)} lines`);
}
console.log("Bandwidth one core can pull with N outstanding misses (N x 64 B / 100 ns):");
for (const n of [1, 10, 16, 32, 48]) console.log(` N = ${String(n).padStart(2)} -> ${gbs(n * LINE / LAT).padStart(11)}`);
// pointer chase: every load depends on the previous one -> only 1 miss in flight
const nodes = 1e7;
console.log(`Pointer chase over ${nodes} nodes, all misses: ${nodes} x 100 ns = ${(nodes * LAT).toFixed(2)} s`);
console.log(`Same bytes streamed at 51.2 GB/s: ${(nodes * LINE / 51.2e9 * 1e3).toFixed(1)} ms`
+ ` -> ${(nodes * LAT / (nodes * LINE / 51.2e9)).toFixed(0)}x slower`);আসল আউটপুট:
Misses that must be in flight to reach a bandwidth:
10.00 GB/s needs 1000 bytes in flight = 15.6 lines
25.60 GB/s needs 2560 bytes in flight = 40.0 lines
51.20 GB/s needs 5120 bytes in flight = 80.0 lines
Bandwidth one core can pull with N outstanding misses (N x 64 B / 100 ns):
N = 1 -> 0.64 GB/s
N = 10 -> 6.40 GB/s
N = 16 -> 10.24 GB/s
N = 32 -> 20.48 GB/s
N = 48 -> 30.72 GB/s
Pointer chase over 10000000 nodes, all misses: 10000000 x 100 ns = 1.00 s
Same bytes streamed at 51.2 GB/s: 12.5 ms -> 80x slower৫১.২ GB/s-এর জন্য ৮০টি line একসাথে উড়তে হবে; ১০টি উড়ন্ত miss-এ একটি core পায় মাত্র ৬.৪ GB/s. তাই একক core-এর মেমরি-bandwidth প্রায়ই চ্যানেলের peak-এর অনেক নিচে — L2-এর prefetcher আর বেশি MSHR এই ফাঁক কমায়, আর পুরো bandwidth পেতে কয়েকটি core লাগে (সংখ্যাগুলো ধরে নেওয়া; আসল MSHR-সংখ্যা chip-ভেদে আলাদা)। Linked list-এর হাঁটা একই byte stream করার চেয়ে ৮০ গুণ ধীর — memory-level parallelism শূন্য। সমাধান: array-ভিত্তিক বিন্যাস, কয়েকটি স্বাধীন list একসাথে হাঁটা, বা software prefetch.
৭ · নকশার প্রশ্ন — cache controller, predictor-এর টেবিল আর core বনাম cache
রিভিশন: পর্ব ১৭ · Finite state machine, পর্ব ৪৫ · Cache-এর bit-হিসাব, পর্ব ৪৭ · Write policy আর MSHR, পর্ব ৩৭ · ২-bit predictor, পর্ব ৫৩ · Multicore, পর্ব ৫৬ · Power
নকশার প্রশ্নে সবচেয়ে বড় ভুল সরাসরি উত্তরে ঝাঁপ দেওয়া। কাঠামো: (১) প্রয়োজন আর সীমা জিজ্ঞেস করা — কাজের ধরন, clock, area, power; (২) একটি সরল প্রথম নকশা; (৩) তার দুর্বলতা আর সংখ্যা; (৪) উন্নতির ধাপ, প্রতিটির দাম; (৫) কীভাবে যাচাই (simulation, verification, মাপ)।
প্র ২১একটি সরল data cache-এর controller নকশা করুন। কোন অবস্থা লাগবে, আর পরে কী কী যোগ করবেন? (কঠিন)
প্রশ্ন পরিষ্কার করা: “একটি in-order core-এর L1 data cache ধরছি: ১৬ KiB, direct-mapped, ৬৪ B line, ৩২-bit physical address, write-back + write-allocate, আর প্রথম সংস্করণে blocking — একবারে একটি miss. ঠিক আছে?”
Datapath আর bit-হিসাব: ২৫৬টি line → offset ৬, index ৮, tag ১৮ bit. প্রতি line-এ ৫১২ bit ডেটা + ১৮ tag + valid + dirty = ৫৩২ bit; মোট ২৫৬ × ৫৩২ = ১,৩৬,১৯২ bit ≈ ১৩৩ Kibit — ডেটার চেয়ে প্রায় ৪% বেশি। একটি tag comparator, hit = valid AND (tag মেলে)।
Controller — চার অবস্থার FSM: Idle — CPU-র বৈধ অনুরোধের অপেক্ষা। Compare Tag — hit হলে পড়া বা লেখা (লেখায় dirty = 1), CPU-কে ready, ফিরে Idle; miss আর victim clean হলে Allocate; miss আর victim dirty হলে Write-Back. Write-Back — পুরোনো block মেমরিতে লেখা, মেমরি ready হলে Allocate. Allocate — নতুন block আনা, এলে আবার Compare Tag (এবার hit). এই ধাঁচটি Patterson–Hennessy-এর বইয়ের সরল controller-এর মতো, আর পর্ব ১৭-এর Moore/Mealy নকশার একটি প্রয়োগ।
উন্নতির ধাপ, প্রতিটির দাম: (১) Write-back buffer — dirty victim একটি buffer-এ রেখে আগে নতুন block আনা, miss penalty থেকে write-back-এর সময় সরে। (২) Critical word first আর early restart — চাওয়া word আগে। (৩) Non-blocking — MSHR দিয়ে কয়েকটি miss একসাথে, hit-under-miss; জটিলতা বাড়ে, একই line-এর দ্বিতীয় miss জুড়তে হয়। (৪) Multicore-এ valid/dirty-র বদলে MESI-র অবস্থা আর snoop-এর পথ।
যাচাই: dirty victim-এর লেখা নতুন block আনার আগে বা buffer থেকে ঠিক ক্রমে যাচ্ছে কি না; একই set-এ পরপর দুটি অনুরোধ; miss চলাকালে একই line-এ store; reset-এর পরে সব valid = 0; আর একটি reference model (যেমন একটি সরল C বা Python cache simulator)-এর সাথে random trace মিলিয়ে দেখা।
সম্ভাব্য ফলো-আপ: “Hit কি এক cycle-এ?” → direct-mapped-এ tag আর data একসাথে পড়ে hit time কম; set-associative-এ way-mux-এর দেরি যোগ হয়। “Write-through হলে কোন অবস্থা লাগত না?” → Write-Back অবস্থা; কিন্তু write buffer আর তার ভরে যাওয়ার stall লাগত।
typedef enum logic [1:0] {IDLE, COMPARE, WRITEBACK, ALLOCATE} state_t;
state_t state, next;
always_ff @(posedge clk) begin
if (rst) state <= IDLE;
else state <= next;
end
always_comb begin
next = state;
case (state)
IDLE: if (cpu_req_valid) next = COMPARE;
COMPARE: if (hit) next = IDLE; // hit: data ready this cycle
else if (victim_dirty) next = WRITEBACK; // old block must go first
else next = ALLOCATE;
WRITEBACK: if (mem_ready) next = ALLOCATE; // old block written to memory
ALLOCATE: if (mem_ready) next = COMPARE; // new block arrived: retry, now a hit
default: next = IDLE;
endcase
endএটি শুধু state register আর next-state যুক্তি; tag/data array লেখা, cpu_ready আর মেমরির read/write সংকেত প্রতিটি অবস্থার output যুক্তিতে আসে (Moore ধাঁচে)। এখানে চালানো হয়নি — এটি উদাহরণ।
প্র ২২একটি ২-bit counter-এর branch predictor-এর টেবিল কত বড় হবে? বড় করলেই কি ভালো? (মাঝারি)
সংক্ষিপ্ত উত্তর: টেবিল ছোট হলে অনেক শাখা একই ঘরে পড়ে (aliasing) — একটি taken-ঝোঁকা আর একটি not-taken-ঝোঁকা শাখা একই counter ভাগ করলে দুজনেই ভুল করে। বড় করলে aliasing কমে, কিন্তু লাভ একসময় থেমে যায় (শাখাগুলোর নিজস্ব অনিশ্চয়তা থেকেই যায়), আর টেবিল বড় হলে area, শক্তি আর — সবচেয়ে গুরুত্বপূর্ণ — পড়ার সময় বাড়ে; predictor-কে এক cycle-এ উত্তর দিতে হয়, কারণ fetch প্রতি cycle-এ চলে।
গভীর উত্তর: নিচের simulator-এ ৬০০টি শাখা, প্রত্যেকে ৯৫% একদিকে ঝোঁকা, PC-র নিচের bit দিয়ে টেবিলের index. দেখুন কোথায় লাভ থামে। বাস্তব নকশায় এর পরের ধাপ আকার বাড়ানো নয়, তথ্য বাড়ানো: global history (gshare), কয়েক আকারের history একসাথে (TAGE), আর একটি ছোট দ্রুত predictor সামনে, বড় ধীরটি পেছনে (overriding predictor) — দ্রুতটির উত্তরে fetch চলে, বড়টি এক-দুই cycle পরে ভুল ধরলে সংশোধন।
সম্ভাব্য ফলো-আপ: “Index-এ PC-র কোন bit?” → নিচের দুই bit বাদ (৪-byte instruction, RV32I-এ সবসময় ০০; compressed extension থাকলে শুধু এক bit), তারপরের bit; উঁচু bit-এর সাথে XOR করে hash করলে aliasing কমে। “Tag রাখবেন?” → রাখলে aliasing ধরা যায়, কিন্তু জায়গা বাড়ে — সাধারণ BHT-তে tag থাকে না, BTB-তে থাকে।
// Branch predictor table size: 2-bit counters indexed by low PC bits. Aliasing vs storage.
let seed = 12345; // deterministic pseudo-random numbers (Park-Miller)
const rnd = () => (seed = (seed * 16807) % 2147483647) / 2147483647;
const B = 600; // 600 static branches in the hot code (assumed)
const br = Array.from({ length: B }, () => ({
pc: Math.floor(rnd() * 2 ** 20) * 4, // word-aligned PCs
pTaken: rnd() < 0.5 ? 0.95 : 0.05 })); // each branch is strongly biased one way
const trace = Array.from({ length: 200000 }, () => br[Math.floor(rnd() * B)]);
const outcomes = trace.map((b) => rnd() < b.pTaken);
console.log("entries storage accuracy CPI (20% branches, 15-cycle penalty)");
for (const E of [16, 64, 256, 1024, 4096, 16384, 65536]) {
const t = new Uint8Array(E).fill(1); // start weakly not-taken
let ok = 0;
trace.forEach((b, k) => {
const i = (b.pc >>> 2) % E, taken = outcomes[k];
if ((t[i] >= 2) === taken) ok++;
t[i] = taken ? Math.min(3, t[i] + 1) : Math.max(0, t[i] - 1);
});
const acc = ok / trace.length, cpi = 1 + 0.2 * (1 - acc) * 15;
console.log(String(E).padStart(7), `${(2 * E / 8 / 1024).toFixed(3)} KiB`.padStart(10),
`${(100 * acc).toFixed(2)}%`.padStart(9), cpi.toFixed(3).padStart(8));
}
console.log("best possible here (always guess the bias): 95.00%, CPI", (1 + 0.2 * 0.05 * 15).toFixed(3));আসল আউটপুট:
entries storage accuracy CPI (20% branches, 15-cycle penalty)
16 0.004 KiB 51.48% 2.456
64 0.016 KiB 57.18% 2.285
256 0.063 KiB 68.71% 1.939
1024 0.250 KiB 85.53% 1.434
4096 1.000 KiB 92.28% 1.232
16384 4.000 KiB 94.11% 1.177
65536 16.000 KiB 94.37% 1.169
best possible here (always guess the bias): 95.00%, CPI 1.150১৬ ঘরে নির্ভুলতা ৫১.৪৮% — মুদ্রা ছোঁড়ার কাছাকাছি, কারণ গড়ে প্রায় ৩৭টি শাখা একটি counter ভাগ করে। ১০২৪ ঘরে ৮৫.৫৩%, ৪০৯৬-এ ৯২.২৮%, ১৬৩৮৪-এ ৯৪.১১%, আর ৬৫৫৩৬-এ মাত্র ৯৪.৩৭% — সীমা ৯৫%, কারণ প্রতিটি শাখার নিজেরই ৫% অনিশ্চয়তা। CPI-র ভাষায় (২০% শাখা, ১৫ cycle penalty): ১৬ ঘরে ২.৪৬, ৪০৯৬ ঘরে (মাত্র ১ KiB) ১.২৩, আর ১৬ গুণ বড় টেবিলে ১.১৭ — শেষের ১৫ KiB প্রায় কিছুই দেয় না। নকশার সিদ্ধান্ত: হাঁটুর বাঁকে (এখানে কয়েক হাজার ঘর) থামা, আর বাকি নির্ভুলতা history-ভিত্তিক predictor থেকে খোঁজা। শাখার সংখ্যা আর ঝোঁক ধরে নেওয়া — আসল কাজের trace দিয়ে একই পরীক্ষা করাই শিল্পের পদ্ধতি।
প্র ২৩একই chip area-য় দুটি বিকল্প: ৮টি core আর ১৬ MiB L3, অথবা ৬টি core আর ৩২ MiB L3. কোনটি নেবেন? (কঠিন)
প্রশ্ন পরিষ্কার করা: “কোন কাজের জন্য — অনেক স্বাধীন অনুরোধের সার্ভার, একটি বড় ডেটাবেস, নাকি বৈজ্ঞানিক stream-ধাঁচের হিসাব? Throughput চাই, নাকি একটি কাজের latency? মেমরি bandwidth কত? Power-এর সীমা?” এই উত্তর ছাড়া যেকোনো সিদ্ধান্ত অনুমান।
যুক্তির কাঠামো: প্রতি core-এর CPI = CPIbase + (L3 miss / instruction) × miss penalty; মোট throughput = core × (১ ÷ CPI), যদি মেমরি bandwidth-এর ছাদ না ছোঁয়। Cache বড় করলে miss কমে কতটা, তা কাজের working set-এর ওপর নির্ভর করে — একটি প্রচলিত মোটা দাগের নিয়ম হলো miss rate মোটামুটি ১ ÷ √(আকার)-এর মতো কমে (“√২ নিয়ম”), কিন্তু এটি সব কাজে খাটে না: working set পুরো আঁটলে লাভ বিশাল, stream-ধাঁচের কাজে প্রায় শূন্য। নিচের মডেল তিন ধরনের কাজে দুই বিকল্প তুলনা করে।
সিদ্ধান্ত (মডেলের পরে): হিসাব-ভারী আর stream-ধাঁচের কাজে বেশি core; মেমরি-ভারী, বড় working set-এর কাজে বড় cache — পার্থক্য অনেক সময় ছোট, তাই আসল সিদ্ধান্ত আসে লক্ষ্য-কাজের trace বা benchmark simulation থেকে। বাড়তি বিবেচনা: বড় L3-এর hit time বেশি; বেশি core-এ license বা software খরচ; power আর তাপ; আর কিছু chip-এ বাড়তি stacked cache-এর মতো তৃতীয় পথ।
সম্ভাব্য ফলো-আপ: “Memory bandwidth যদি অর্ধেক হয়?” → বেশি core-এর বিকল্প আগে bandwidth-এর দেয়ালে ঠেকবে; বড় cache তখন আরও মূল্যবান, কারণ সে DRAM-এর ট্রাফিক কমায়।
// More cores or a bigger L3? Same area budget, two options. EVERY number is an ASSUMED teaching value.
const BASE_CPI = 1.0, PENALTY = 200; // cycles per L3 miss (DRAM), 3 GHz
const BW_CAP = 51.2e9, LINE = 64, HZ = 3e9; // dual-channel DDR4-3200
const options = [{ name: "A: 8 cores + 16 MiB L3", cores: 8, l3: 16 },
{ name: "B: 6 cores + 32 MiB L3", cores: 6, l3: 32 }];
// L3 misses per 1000 instructions when each core has 2 MiB of L3; "sqrt(2) rule" for other sizes
const loads = [{ name: "compute-heavy", mpki2: 1 }, { name: "memory-heavy", mpki2: 20 },
{ name: "streaming", mpki2: 40, flat: true }]; // streaming: bigger cache does not help
for (const w of loads) {
console.log(`-- ${w.name}`);
for (const o of options) {
const perCore = o.l3 / o.cores;
const mpki = w.flat ? w.mpki2 : w.mpki2 * Math.sqrt(2 / perCore);
const cpi = BASE_CPI + mpki / 1000 * PENALTY;
let ipc = o.cores / cpi; // total instructions per cycle, all cores
const need = ipc * HZ * mpki / 1000 * LINE; // DRAM bytes per second this would need
if (need > BW_CAP) ipc *= BW_CAP / need; // bandwidth wall: scale down
console.log(` ${o.name}: L3/core ${perCore.toFixed(2)} MiB, MPKI ${mpki.toFixed(2)}, CPI ${cpi.toFixed(3)},`
+ ` DRAM need ${(need / 1e9).toFixed(1)} GB/s, total IPC ${ipc.toFixed(2)}`);
}
}আসল আউটপুট:
-- compute-heavy
A: 8 cores + 16 MiB L3: L3/core 2.00 MiB, MPKI 1.00, CPI 1.200, DRAM need 1.3 GB/s, total IPC 6.67
B: 6 cores + 32 MiB L3: L3/core 5.33 MiB, MPKI 0.61, CPI 1.122, DRAM need 0.6 GB/s, total IPC 5.35
-- memory-heavy
A: 8 cores + 16 MiB L3: L3/core 2.00 MiB, MPKI 20.00, CPI 5.000, DRAM need 6.1 GB/s, total IPC 1.60
B: 6 cores + 32 MiB L3: L3/core 5.33 MiB, MPKI 12.25, CPI 3.449, DRAM need 4.1 GB/s, total IPC 1.74
-- streaming
A: 8 cores + 16 MiB L3: L3/core 2.00 MiB, MPKI 40.00, CPI 9.000, DRAM need 6.8 GB/s, total IPC 0.89
B: 6 cores + 32 MiB L3: L3/core 5.33 MiB, MPKI 40.00, CPI 9.000, DRAM need 5.1 GB/s, total IPC 0.67হিসাব-ভারী কাজে বিকল্প A (৮ core) স্পষ্ট জেতে: মোট IPC ৬.৬৭ বনাম ৫.৩৫ — miss এমনিতেই কম, বড় cache-এর লাভ সামান্য। মেমরি-ভারী কাজে B সামান্য এগিয়ে: ১.৭৪ বনাম ১.৬০ — বড় cache miss ২০ থেকে ১২.২৫ MPKI-তে নামিয়ে কম core-এর ক্ষতি পুষিয়ে দেয়। Stream-ধাঁচের কাজে cache কিছুই বদলায় না (MPKI দুই বিকল্পেই ৪০), তাই বেশি core-ই ভালো (০.৮৯ বনাম ০.৬৭)। এই মডেলে কোনো বিকল্পই bandwidth-এর ছাদ (৫১.২ GB/s) ছোঁয়নি, কারণ সরল CPI-মডেলে প্রতিটি miss পুরো ২০০ cycle অপেক্ষা করায়; prefetch আর MLP থাকলে stream-এর চাহিদা অনেক বেশি হতো, আর তখন বেশি core-এর লাভও ছাদে আটকাত। MPKI, √২ নিয়ম আর সব সংখ্যা ধরে নেওয়া — উত্তরের মূল্য সিদ্ধান্তে নয়, কাঠামোতে: কাজের ধরন জিজ্ঞেস করা, একটি মডেল, আর কোন অনুমান সিদ্ধান্ত উল্টে দিতে পারে তা বলা।
৮ · পারফরম্যান্স রহস্য — তিনটি debugging দৃশ্য
রিভিশন: পর্ব ০৩ · মাপা আর counter, পর্ব ৪৪ · Staircase, পর্ব ৪৮ · Loop-এর ক্রম আর false sharing, পর্ব ৫০ · TLB, পর্ব ৫৪ · NUMA; OS-এর দিক: Operating Systems · পারফরম্যান্স
রহস্যের প্রশ্নে ইন্টারভিউয়ার একটি উত্তর চান না, চান একটি পদ্ধতি: সমস্যাটি নির্ভরযোগ্যভাবে পুনরুৎপাদন আর মাপা → profile করে কোথায় সময় যায় → counter দিয়ে কারণের অনুমান যাচাই → একবারে একটি জিনিস বদলানো → আবার মেপে তুলনা, আর ফল সঠিক আছে কি না দেখা। নিচের কমান্ডগুলো Linux-এর perf-এর উদাহরণ — এখানে চালানো হয়নি, কারণ অনেক virtual machine আর container-এ performance counter পাওয়া যায় না বা অনুমতি বন্ধ থাকে; event-এর নাম CPU-ভেদে আলাদা, তাই আগে perf list দেখে নেবেন।
$ perf stat -e cycles,instructions,branches,branch-misses ./app # IPC আর শাখার ভুল
$ perf stat -e L1-dcache-load-misses,LLC-load-misses,dTLB-load-misses ./app # কোন স্তরে miss
$ perf record -g ./app && perf report # সময় কোন function-এ
$ perf c2c record ./app && perf c2c report # core-দের মধ্যে কোন line-এর টানাটানিপ্র ২৪ইনপুট ১০ গুণ বড় হতেই প্রোগ্রাম ৫০ গুণ ধীর। কোথা থেকে শুরু করবেন? (মাঝারি)
সংক্ষিপ্ত উত্তর: প্রথমে algorithm: সময় যদি n২-এর মতো বাড়ে (১০ গুণ ইনপুটে ১০০ গুণ), সমস্যাটি hardware নয় — complexity. তারপর hardware-এর সন্দেহ: working set কোনো একটি সীমা পেরিয়েছে — L2 বা L3 থেকে DRAM-এ, TLB reach ছাড়িয়ে, বা RAM ছাড়িয়ে swap-এ। এগুলো প্রতিটি সময়কে “সিঁড়ির ধাপে” লাফ দেওয়ায়, মসৃণভাবে নয়।
গভীর উত্তর — কী মাপবেন: (১) কয়েকটি ইনপুট-আকারে সময় মেপে log-log গ্রাফ: ঢাল ১ মানে রৈখিক, ২ মানে বর্গ; হঠাৎ লাফ মানে কোনো স্তর পার হলো। (২) perf stat-এ IPC: বড় ইনপুটে IPC অনেক কমলে মেমরির অপেক্ষা। (৩) প্রতি হাজার instruction-এ LLC miss আর dTLB miss — কোনটি লাফ দিল। (৪) OS-এর দিক: /usr/bin/time -v-এ major page fault বা swap. (৫) Hash table-এর resize বা data structure-এর বিন্যাস (pointer-ভরা গাছ বনাম array). সমাধান কারণভেদে: algorithm বদলানো, blocking বা ডেটা টুকরো করে প্রক্রিয়া, ছোট data type, huge page, বা আরও RAM.
সম্ভাব্য ফলো-আপ: “Working set কীভাবে জানবেন?” → ডেটা-কাঠামোর মোট আকার হিসাব করা, আর পর্ব ৪৪-এর staircase-এর মতো কয়েকটি আকারে মাপা; ধাপের কিনারা প্রায়ই L2, L3 আর TLB reach-এর কাছাকাছি পড়ে। “NUMA মেশিনে?” → ডেটা অন্য socket-এর মেমরিতে থাকলে আরও ধীর; first-touch নীতি আর thread-এর জায়গা দেখা।
প্র ২৫একটি কাজ দুই thread-এ ভাগ করার পরে একটি thread-এর চেয়েও ধীর হলো। সম্ভাব্য কারণ আর প্রমাণ কী? (মাঝারি)
সংক্ষিপ্ত উত্তর: সন্দেহের তালিকা, সম্ভাব্যতার ক্রমে: (১) false sharing — আলাদা ভ্যারিয়েবল, একই line; (২) true sharing — একই lock বা atomic counter নিয়ে কাড়াকাড়ি; (৩) দুই thread একই physical core-এর দুই SMT sibling-এ, বা container-এ আসলে মাত্র একটি CPU; (৪) মেমরি bandwidth আগেই ভরা — memory-bound কাজে thread বাড়ালে লাভ নেই; (৫) কাজ এত ছোট যে thread তৈরি আর join-এর খরচই বড়।
গভীর উত্তর — প্রমাণ: nproc আর lscpu (কতটি CPU, thread per core); perf c2c বা HITM-ধাঁচের counter (কোন line-এ টানাটানি); perf record-এ lock-এর function বা spin-এর সময়; একক thread-এর bandwidth মেপে peak-এর সাথে তুলনা। নিচের C প্রোগ্রাম কারণ ১ সরাসরি দেখায়: একটি thread দুটি counter বাড়ায়, তারপর দুই thread — একবার একই line-এ, একবার ৬৪ byte দূরে।
সম্ভাব্য ফলো-আপ: “Padding ছাড়া আর কী?” → প্রতি thread-এর স্থানীয় ভ্যারিয়েবলে জমিয়ে শেষে একবার লেখা — atomic আর coherence-ট্রাফিক দুটিই কমে। “Lock-এর কাড়াকাড়ি কমাবেন কীভাবে?” → lock ভেঙে ছোট অংশে (sharding), test-and-test-and-set ধাঁচের অপেক্ষা (পর্ব ৫৩), বা lock ছাড়া প্রতি-thread কাঠামো।
// Two threads slower than one? 1 thread does 2N increments vs 2 threads (same line / padded). Times vary.
#include <pthread.h>
#include <stdalign.h>
#include <stdio.h>
#include <time.h>
#define N 50000000L
static struct { volatile long a, b; } P; // 8 B apart: one cache line
static struct { alignas(64) volatile long a; alignas(64) volatile long b; } Q; // a line each
static volatile long s1, s2; // used by the 1-thread run
static void *bump(void *p) { volatile long *c = p; for (long i = 0; i < N; i++) (*c)++; return NULL; }
static double ms(void) { struct timespec t; clock_gettime(CLOCK_MONOTONIC, &t); return t.tv_sec * 1e3 + t.tv_nsec / 1e6; }
static double two(volatile long *x, volatile long *y) {
pthread_t ta, tb; double t0 = ms();
pthread_create(&ta, NULL, bump, (void *)x); pthread_create(&tb, NULL, bump, (void *)y);
pthread_join(ta, NULL); pthread_join(tb, NULL);
return ms() - t0;
}
int main(void) {
double t0 = ms(); bump((void *)&s1); bump((void *)&s2); double one = ms() - t0;
double same = two(&P.a, &P.b), padded = two(&Q.a, &Q.b);
int ok = s1 == N && s2 == N && P.a == N && P.b == N && Q.a == N && Q.b == N;
printf("all six counters = %ld: %s\n", N, ok ? "yes" : "no");
printf("1 thread, both counters : %5.0f ms\n", one);
printf("2 threads, same line : %5.0f ms = %.2f x the 1-thread time\n", same, same / one);
printf("2 threads, padded to 64 B: %5.0f ms = %.2f x the 1-thread time\n", padded, padded / one);
return 0;
}যাচাইয়ের সময় আসল আউটপুট (সময় প্রতিবার আর যন্ত্রভেদে অনেক বদলায়):
all six counters = 50000000: yes
1 thread, both counters : 186 ms
2 threads, same line : 275 ms = 1.48 x the 1-thread time
2 threads, padded to 64 B: 141 ms = 0.76 x the 1-thread timeছয়টি counter-ই ৫ কোটি — তিন সংস্করণেই ফল সঠিক। এই রানে একটি thread দুটি counter পরপর বাড়াতে নিল ১৮৬ ms. একই কাজ দুই thread-এ ভাগ করলে, counter দুটি একই line-এ থাকায়, লাগল ২৭৫ ms — একটি thread-এর চেয়েও প্রায় ১.৪৮ গুণ বেশি: প্রশ্নের রহস্যটি হুবহু। শুধু counter দুটি ৬৪ byte দূরে সরাতেই ১৪১ ms, অর্থাৎ একটি thread-এর ০.৭৬ গুণ — এবার সত্যিই সমান্তরাল লাভ। আদর্শ ০.৫ না হওয়ার কারণ thread তৈরির খরচ, দুই thread একই physical core-এর SMT sibling-এ পড়তে পারা, আর shared virtual machine-এ অন্যদের কাজ। Thread-এর সময় খুবই অস্থির — পর্ব ৪৮-এ একই ধাঁচের মাপে অনুপাত ১-এর কাছ থেকে ৪-এর বেশি পর্যন্ত এসেছিল — তাই একবারের সংখ্যা নয়, কয়েকবার চালিয়ে প্রবণতা দেখবেন, আর নিশ্চিত হতে perf c2c দিয়ে line-টি ধরবেন।
প্র ২৬Matrix গুণের তিনটি loop-এর ক্রম বদলাতেই প্রোগ্রাম অনেক দ্রুত হলো, অথচ গুণ-যোগের সংখ্যা একই। ব্যাখ্যা করুন, আর আরও দ্রুত করার পরের ধাপ কী? (সহজ)
সংক্ষিপ্ত উত্তর: C-তে array row-major. ijk ক্রমে ভেতরের লুপ k-তে B[k][j] column ধরে হাঁটে — প্রতিটি access নতুন line (৫১২ double-এর row = ৪ KiB stride), প্রায় প্রতিবার miss. ikj ক্রমে ভেতরের লুপ j-তে B[k][j] আর C[i][j] দুটিই row ধরে — প্রতি ৮টি double-এ একটি miss, আর prefetcher-ও খুশি। পর্ব ৪৮-এর হিসাবে ভেতরের লুপে প্রতি iteration-এ miss ijk-তে প্রায় ১.১২৫, ikj-তে ০.২৫.
গভীর উত্তর — পরের ধাপ: (১) Blocking (tiling): matrix-কে ছোট tile-এ ভাগ করা, যাতে A, B, C-এর একেকটি tile একসাথে cache-এ আঁটে — miss আরও কমে, operational intensity বাড়ে (অংশ ৬-এর সমস্যা গ)। (২) Compiler-কে -O2/-O3 আর লক্ষ্য-CPU-র SIMD ব্যবহার করতে দেওয়া। (৩) বাস্তবে নিজে না লিখে একটি টিউন করা BLAS library — এগুলো register-স্তর থেকে L3 পর্যন্ত কয়েক স্তরের blocking আর হাতে টিউন করা SIMD kernel ব্যবহার করে বলে বর্ণিত। ইন্টারভিউতে শেষ কথাটি পরিণত বিচারের চিহ্ন।
সম্ভাব্য ফলো-আপ: “Fortran-এ কোন ক্রম দ্রুত?” → Fortran column-major, তাই উল্টো — ভেতরের লুপে প্রথম সূচক বদলানো উচিত। “N = ১০২৪ হলে কী বিশেষ?” → ২-এর ঘাতের stride-এ conflict miss (সমস্যা খ) — padding সাহায্য করে।
// C = A x B, 512 x 512 double: loop order ijk vs ikj. Same arithmetic, different strides. Times vary.
#include <stdio.h>
#include <string.h>
#include <time.h>
#define N 512
static double A[N][N], B[N][N], C[N][N];
static double ms(void) { struct timespec t; clock_gettime(CLOCK_MONOTONIC, &t); return t.tv_sec * 1e3 + t.tv_nsec / 1e6; }
static double total(void) { double s = 0; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) s += C[i][j]; return s; }
int main(void) {
for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) { A[i][j] = (i + j) % 7; B[i][j] = (i * j) % 5; }
double t0 = ms();
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++) {
double s = 0;
for (int k = 0; k < N; k++) s += A[i][k] * B[k][j]; // B down a column: stride 4 KiB
C[i][j] = s;
}
double tijk = ms() - t0, c1 = total();
memset(C, 0, sizeof C);
t0 = ms();
for (int i = 0; i < N; i++)
for (int k = 0; k < N; k++) {
double a = A[i][k];
for (int j = 0; j < N; j++) C[i][j] += a * B[k][j]; // B and C along rows: stride 8 B
}
double tikj = ms() - t0, c2 = total();
printf("checksums: ijk %.0f, ikj %.0f (%s)\n", c1, c2, c1 == c2 ? "same" : "DIFFERENT");
printf("ijk: %6.0f ms ikj: %6.0f ms ijk / ikj = %.1f\n", tijk, tikj, tijk / tikj);
return 0;
}যাচাইয়ের সময় আসল আউটপুট (সময় প্রতিবার আর যন্ত্রভেদে বদলায়):
checksums: ijk 642353672, ikj 642353672 (same)
ijk: 691 ms ikj: 452 ms ijk / ikj = 1.5দুই ক্রমে checksum হুবহু এক (৬৪,২৩,৫৩,৬৭২) — একই অঙ্ক, শুধু ছোঁয়ার ক্রম আলাদা। এই রানে ijk ৬৯১ ms, ikj ৪৫২ ms — প্রায় ১.৫ গুণ পার্থক্য। “কয়েক গুণ” না হয়ে মাত্র দেড় গুণ কেন, সেটাও ইন্টারভিউর ভালো আলোচনা: runner কোনো -O flag ছাড়া (-O0) compile করে, তাই প্রতিটি iteration-এ loop-চলক stack থেকে পড়া-লেখার নিজস্ব খরচ বড়, আর মেমরির পার্থক্য তার আড়ালে কিছুটা ঢাকা পড়ে; তার ওপর ৫১২ × ৫১২ double-এর B মাত্র ২ MiB — পর্ব ৪৪-এ দেখা এই runner-এর ১৬ MiB L3-তে সহজেই আঁটে, তাই column-হাঁটার miss-গুলো DRAM নয়, L3 থেকে মেটে। Matrix বড় করলে (যেমন ২০৪৮) বা -O2-তে compile করলে loop-এর নিজস্ব খরচ কমে আর পার্থক্য সাধারণত বাড়ে — নিজের মেশিনে মেপে দেখবেন। মাপার আগে ঠিক এই দুটি অনুমান (কোন flag, কোন স্তরে ডেটা আঁটে) জোরে বলাই পরিণত উত্তর।
আরও গভীরে: শিল্পে পারফরম্যান্স বিশ্লেষণের একটি জনপ্রিয় কাঠামো হলো top-down পদ্ধতি — counter দিয়ে প্রথমে দেখা হয় pipeline-এর slot-গুলো কোথায় যায়: কাজে লাগল (retiring), ভুল অনুমানে নষ্ট (bad speculation), সামনের অংশ instruction দিতে পারল না (frontend bound), নাকি পেছনের অংশ মেমরি বা execution unit-এর অপেক্ষায় (backend bound) — তারপর যে ভাগ বড়, সেখানে আরও গভীরে। Intel-এর প্রকৌশলীদের প্রস্তাবিত এই পদ্ধতি বিভিন্ন টুলে বাস্তবায়িত বলে জানা যায়। অন্যদিকে বড় data center-এ এক মেশিনের মাপের বদলে হাজার মেশিন জুড়ে সবসময় চালু sampling-ভিত্তিক profiling-ও প্রচলিত বলে প্রকাশিত গবেষণায় বর্ণিত।
৯ · AI-এর যুগে — ইন্টারভিউ প্রস্তুতিতে AI, আর যাচাইয়ের অভ্যাস
AI একটি ভালো mock interviewer হতে পারে — অনবরত প্রশ্ন করে, ফলো-আপ দেয়, ধৈর্য হারায় না। কিন্তু আর্কিটেকচারের সংখ্যা আর কোণার ঘটনায় এর ভুল প্রায়ই চোখে পড়ে, আর ভুলগুলো আত্মবিশ্বাসের সাথে বলা হয়:
| AI-এর সাধারণ ভুল | কীভাবে ধরবেন |
|---|---|
| কোনো নির্দিষ্ট chip-এর cache-আকার, latency, ROB-এর মাপ বা inclusive কি না — বানিয়ে বলা | নির্মাতার optimization manual, বা নিজের মেশিনে /sys/devices/system/cpu/cpu0/cache/ আর lscpu |
| “কোন প্রতিষ্ঠানে কী জিজ্ঞেস করে” — বানানো তালিকা আর প্রক্রিয়ার বর্ণনা | এ ধরনের দাবি উপেক্ষা করুন; ধারণা আর পদ্ধতি অনুশীলন করুন |
| Cache-এর bit-ভাগ, pipeline-এর cycle-গোনা আর AMAT-এ local/global miss rate গুলিয়ে ফেলা | হাতে আর একটি ছোট script-এ আবার হিসাব; পর্ব ৪৫–৪৭-এর সূত্রের সাথে মেলানো |
| GB আর GiB, bit আর byte, ns আর cycle মিশিয়ে ফেলা | প্রতিটি সংখ্যার পাশে একক লিখে নিজে আবার গুনুন |
| x86-এর memory model-কে সব CPU-র নিয়ম বলা, বা MIPS আর RISC-V-এর নিয়ম মেশানো | ISA manual (RISC-V-এর RVWMO, ARM-এর memory model অধ্যায়) আর পর্ব ৫৩ |
| “SMT মানে দ্বিগুণ গতি”, “বড় cache সবসময় ভালো” — একমাত্রিক সিদ্ধান্ত | Trade-off আর কোন কাজে, তা জিজ্ঞেস করুন; নিজে মাপুন |
AI-কে mock interviewer বানাতে চাইলে নিয়মগুলো স্পষ্ট দিন — একবারে একটি প্রশ্ন, আপনার উত্তরের পরেই মূল্যায়ন:
AI-এর দেওয়া উত্তর বা হিসাব হাতে পেলে — চেকলিস্ট
নিজেকে যাচাই করুন
ইন্টারভিউর ধাঁচের হিসাব আর ধারণা। ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমএকটি প্রোগ্রাম হঠাৎ ধীর হয়েছে। তদন্তের ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- 🔁 সমস্যাটি পুনরুৎপাদন করে কয়েকবার নির্ভরযোগ্যভাবে মাপা
- 🔥 Profile করে দেখা সময় কোন function বা লুপে যায়
- 📊 Counter দিয়ে কারণের অনুমান যাচাই — IPC, cache miss, branch miss
- 🛠️ একবারে একটি জিনিস বদলানো
- ✅ আবার মেপে তুলনা, আর ফল এখনো সঠিক কি না দেখা
(সহজ) একটি প্রোগ্রামের ৮০% সময় পুরোপুরি সমান্তরাল করা যায়, বাকি ২০% serial. কোনো overhead না ধরলে ৮টি core-এ speedup কত?
- ৮ গুণ
- ৬.৪ গুণ
- প্রায় ৩.৩৩ গুণ
- ৫ গুণ
(মাঝারি) DRAM latency ১০০ ns, cache line ৬৪ byte. একটি core-এ একসাথে সর্বোচ্চ ১০টি cache miss উড়ন্ত থাকতে পারে। Little-এর সূত্র অনুযায়ী এই core সর্বোচ্চ কত memory bandwidth পাবে?
- ৬.৪ GB/s
- ০.৬৪ GB/s
- ৬৪ GB/s
- ৫১.২ GB/s
(সহজ) একটি L2 TLB-তে ১৫৩৬টি ঘর। সব ঘরে ২ MiB-এর huge page থাকলে TLB reach কত?
- ৬ MiB
- ১.৫ GiB
- ১৫৩৬ GiB
- ৩ GiB
(সহজ) দুটি thread দুটি আলাদা long counter বাড়ায় — কোনো lock নেই — কিন্তু counter দুটি একটি struct-এ পাশাপাশি (৮ byte দূরে)। দুই thread একটির চেয়ে ধীর। সবচেয়ে সরাসরি সমাধান কী?
- প্রতিটি ++-এর চারপাশে একটি mutex বসানো
- দুটি counter-কে padding বা alignas(64) দিয়ে আলাদা cache line-এ রাখা
- দুটি counter-কে volatile ঘোষণা করা
- Thread-এর সংখ্যা চার করা
(কঠিন) শুরুতে x = y = 0. Thread 0: x = 1; r1 = y; Thread 1: y = 1; r2 = x; (সাধারণ store আর load, কোনো fence নেই)। x86-এর TSO memory model-এ r1 = 0 আর r2 = 0 — দুটিই একসাথে — কি সম্ভব?
- হ্যাঁ, store buffer-এর কারণে সম্ভব
- না, x86 sequential consistency দেয়
- না, cache coherence এটি ঠেকায়
- শুধু ARM-এ সম্ভব, x86-এ কখনো নয়
(মাঝারি) একটি মেশিনের peak ২০০ GFLOP/s, মেমরি bandwidth ৫০ GB/s. একটি kernel-এর operational intensity ০.২৫ FLOP/byte. Roofline model অনুযায়ী সর্বোচ্চ কত GFLOP/s, আর kernel কোন ধরনের?
- ২০০ GFLOP/s, compute-bound
- ৫০ GFLOP/s, memory-bound
- ১২.৫ GFLOP/s, memory-bound
- ৪ GFLOP/s, memory-bound
(মাঝারি) একটি লুপে ২০% instruction শাখা, base CPI ১, ভুল অনুমানের penalty ১৫ cycle. Sorted ডেটায় শাখার ভুল প্রায় ০%, এলোমেলো ডেটায় ৫০%. এলোমেলো ডেটায় লুপটি মোটামুটি কত গুণ ধীর?
- প্রায় ২ গুণ
- প্রায় ২.৫ গুণ
- প্রায় ১৫ গুণ
- প্রায় ৮.৫ গুণ
(সহজ) একটি ৪ GiB array একবার পুরো পড়তে হবে, মেমরি DDR4-3200 single channel (৬৪ bit, peak ২৫.৬ GB/s). শুধু bandwidth ধরলে সময়ের নিচের সীমা কত?
- প্রায় ০.১৫৬ s
- প্রায় ১.৩৪ s
- প্রায় ০.০৮৪ s
- প্রায় ০.১৬৮ s
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন — অর্থ দেখাবে। এই পর্বের সব শব্দ এখানে একসাথে:
মনে রাখুন
- উত্তরের চার ধাপ: প্রশ্ন পরিষ্কার করা, অনুমান জোরে বলা, একক-সহ সংখ্যায় আন্দাজ, trade-off আর যাচাইয়ের পথ। বানানো সংখ্যার চেয়ে “মাত্রা এরকম, এভাবে মাপব” অনেক ভালো।
- CPU: pipeline throughput বাড়ায়, latency নয়; load-use-এ forwarding-এর পরেও ১ stall; sorted array-র রহস্য = শাখার অনুমান (CPI = ১ + শাখা × ভুল × penalty); ROB ক্রমে commit করে precise exception দেয়; renaming WAR/WAW মোছে, RAW নয়; Spectre-এর প্রতিরক্ষা স্তরে স্তরে।
- Cache আর coherence: associativity conflict কমায়, hit time বাড়ায়; false sharing = আলাদা ভ্যারিয়েবল, একই line — padding দিয়ে সারে; MESI-র E একটি transaction বাঁচায়; coherence এক ঠিকানার, consistency ভিন্ন ঠিকানার ক্রমের প্রশ্ন — x86 TSO-তেও r1 = r2 = ০ সম্ভব।
- মেমরি: TLB reach = ঘর × page size (১৫৩৬ × ২ MiB = ৩ GiB); DRAM-এর bandwidth বেড়েছে, latency প্রায় একই; Little: উড়ন্ত byte = bandwidth × latency — ৫১.২ GB/s-এ ৮০টি line; DRAM miss ≈ ৭৫টি L1 hit.
- হিসাব আর রহস্য: roofline = min(peak, BW × I); Amdahl-এ আগে serial অংশ কমানো; ২-এর ঘাতের stride-এ conflict miss; রহস্যে পদ্ধতি — মাপা, profile, counter, একটি বদল, আবার মাপা।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ৬২ · Low-level ইন্টারভিউ — bit manipulation, memory আর embedded প্রশ্নপরবর্তী পর্বBit-কৌশল, memory layout আর embedded-এর প্রশ্ন।
- কম্পিউটার আর্কিটেকচার ও ডিজিটাল লজিক · কোর্স হোম৬২টি পর্বপুরো কোর্সের রোডম্যাপ।
- পর্ব ৫৮ · Numerical সমস্যা — সংখ্যা পদ্ধতি, K-map, CPI, pipeline আর cacheঅনুশীলনCPI, pipeline আর cache-এর হাতে-কলমে হিসাব।
- পর্ব ৬০ · লিখিত ও মৌখিক (ভাইভা) প্রশ্নঅনুশীলনলজিক, ISA, pipeline আর মেমরির লিখিত উত্তর।
- Operating Systems · OS ইন্টারভিউর প্রশ্নপাশের ট্র্যাকProcess, memory, I/O আর container-এর ইন্টারভিউ।
- C প্রোগ্রামিং · পারফরম্যান্স আর cacheপাশের ট্র্যাকযে C কোড cache-এর সাথে মানিয়ে চলে।