Memory Hierarchy — দ্রুত, বড়, সস্তা: তিনটার মধ্যে দুটো বাছুন
Memory Hierarchy
একটা একক memory প্রযুক্তি দ্রুত, বড়, সস্তা — তিনটাই দিতে পারে না। তাই CPU একটা সিঁড়ি বানায় — register থেকে HDD পর্যন্ত, প্রতি ধাপে ধীর কিন্তু বড়। এই সিঁড়িটা কাজ করে শুধু একটা কারণে: locality of reference — প্রোগ্রাম যা এইমাত্র access করেছে বা যা কাছাকাছি, সেটাই আবার লাগবে।
আগে এটা বুঝি
গত লেসনে আমরা a = b + c সম্পূর্ণ fetch-decode-execute করেছি — instruction fetch হলো, register file থেকে b, c পড়া হলো, ALU যোগ করল, ফলাফল একটা register-এ গেল। প্রতিটা ধাপকে আমরা প্রায় instant ধরে নিয়েছিলাম। এখন সেই সরলীকরণটা ভাঙার সময়।
আসলে যদি b আর c register-এ না থেকে memory-তে থাকত (যেমন a = *p + *q), তাহলে সেই “read” ধাপটা কতটা সময় নিত? উত্তরটা লেসন ২-এর (digital-logic) SRAM/DRAM লেসনের শেষ টেবিলেই লুকানো ছিল — কিন্তু তখন আমরা শুধু cell-level physics দেখেছিলাম। এখন সেই সংখ্যাগুলোকে সরাসরি CPU performance-এর প্রশ্নে নিয়ে আসি।
একটা সহজ পাটিগণিত দিয়ে শুরু করা যাক। ধরুন আপনার কাছে টাকা আছে ১৬ GB DRAM কিনতে — সস্তা, প্রচুর জায়গা। অথবা আপনি সেই একই টাকায় হয়তো ৫০০ MB SRAM কিনতে পারতেন — দ্রুত, কিন্তু অনেক কম জায়গা (আগের লেসনে দেখেছি, SRAM cell DRAM cell-এর তুলনায় প্রায় ১৫-২০ গুণ বেশি জায়গা নেয়, তাই একই দামে অনেক কম বিট)। কোনটা নেবেন?
বাস্তব উত্তর: দুটোই, একসাথে, স্তরে স্তরে সাজিয়ে। কারণ কোনো একক প্রযুক্তি “দ্রুত + বড় + সস্তা” — এই তিনটা গুণ একসাথে দিতে পারে না। এটা কোনো manufacturing দুর্বলতা না — এটা physics-এর একটা কাঠামোগত সীমা, ঠিক যেমনটা আমরা SRAM-এর ৬ transistor বনাম DRAM-এর ১ transistor+১ capacitor-এর তুলনায় দেখেছিলাম। দ্রুত access পেতে হলে হয় খুব কাছাকাছি রাখতে হবে (physical distance = signal propagation delay), অথবা খুব সরল circuit ব্যবহার করতে হবে (SRAM-এর সরাসরি feedback push)। দুটোই মূল্য দাবি করে — area, আর area মানে খরচ।
তাই ইঞ্জিনিয়াররা একটা সিঁড়ি বানান — memory hierarchy। উপরে (CPU-র সবচেয়ে কাছে) ক্ষুদ্র, প্রচণ্ড দ্রুত, ব্যয়বহুল memory — register, L1/L2/L3 cache। নিচে বিশাল, সস্তা, ধীর memory — main memory (DRAM), তারপর SSD, তারপর HDD। এই লেসনের লক্ষ্য দুটো: (১) এই সিঁড়ির প্রতিটা ধাপের বাস্তব সংখ্যা মুখস্থ না করে বোঝা, আর (২) সবচেয়ে গুরুত্বপূর্ণ প্রশ্নের উত্তর — কেন এই সিঁড়িটা আদৌ কাজ করে? কারণ যদি প্রতিটা memory access সত্যিই random হতো, hierarchy একদম অকেজো হয়ে যেত — প্রতিবারই আপনাকে সবচেয়ে ধীর স্তর পর্যন্ত যেতে হতো। যে নীতিটা এটাকে কাজ করায়, তার নাম locality of reference — আর সেটাই এই লেসনের আসল হিরো।
মূল ধারণা
পুরো পিরামিডটা, সংখ্যাসহ
নিচের টেবিলে প্রতিটা স্তরের তিনটা জিনিস দেখানো হলো — আনুমানিক latency (cycle-এ, কারণ CPU নিজের clock-এ “গোনে”), আনুমানিক বাস্তব সময়, আর আনুমানিক আকার। ধরে নিচ্ছি CPU ~৩ GHz-এ চলছে (আধুনিক ডেস্কটপ/ল্যাপটপ প্রসেসরের জন্য একটা সাধারণ frequency) — তাহলে ১ cycle ≈ ০.৩৩ ns।
| স্তর | প্রযুক্তি | latency (cycle) | latency (আনুমানিক সময়) | আকার |
|---|---|---|---|---|
| Register | SRAM-based file, multi-port | ~1 cycle | ~0.3 ns | ~1 KB (পুরো register file) |
| L1 cache | SRAM | ~4 cycle | ~1.3 ns | 32–64 KB |
| L2 cache | SRAM | ~12 cycle | ~4 ns | 256 KB – 1 MB |
| L3 cache | SRAM (সাধারণত shared) | ~40 cycle | ~13 ns | কয়েক থেকে কয়েক-দশ MB |
| Main memory (DRAM) | DRAM | ~200 cycle | ~70 ns | কয়েক GB – কয়েক-শ GB |
| SSD (NVMe) | Flash | ~60,000 cycle | ~20 μs | কয়েক-শ GB – কয়েক TB |
| HDD | চুম্বকীয় ডিস্ক (seek + rotation) | ~24,000,000 cycle | ~8 ms | কয়েক TB |
একটা মানব-স্কেল রূপক — যদি register access ১ সেকেন্ড হতো
সংখ্যাগুলো ন্যানোসেকেন্ডে থাকলে অনুভব করা কঠিন — এত ছোট যে কোনো intuition কাজ করে না। তাই একটা ক্লাসিক trick: register access-কে ১ সেকেন্ড ধরে নিয়ে বাকি সবকিছু একই অনুপাতে বড় করি। যেহেতু register ১ cycle লাগে আর আমরা সেটাকে “১ সেকেন্ড” বলছি, বাকি প্রতিটা স্তরের scaled সময় সরাসরি তার cycle সংখ্যার সমান সেকেন্ডে পাওয়া যায় — হিসাবটা এতটাই সরল।
| স্তর | Cycle | “যদি register access = ১ সেকেন্ড” |
|---|---|---|
| Register | 1 | ১ সেকেন্ড |
| L1 cache | 4 | ৪ সেকেন্ড |
| L2 cache | 12 | ১২ সেকেন্ড |
| L3 cache | 40 | ৪০ সেকেন্ড (এক মিনিটেরও কম) |
| Main memory (DRAM) | 200 | ৩ মিনিট ২০ সেকেন্ড |
| SSD | ~60,000 | ~১৭ ঘণ্টা (প্রায় একটা পুরো দিন) |
| HDD | ~24,000,000 | ~২৭৮ দিন (প্রায় ৯ মাস!) |
কেন এই বিপরীত সম্পর্ক — দ্রুত মানেই ছোট আর দামি কেন
আগের লেসনে (SRAM/DRAM) আমরা দেখেছিলাম cell-level কারণ — SRAM-এর ৬ transistor cross-coupled feedback দিয়ে সরাসরি bit line push করে (দ্রুত), কিন্তু প্রতি bit-এ বেশি area লাগে (দামি, তাই অল্প রাখা যায়)। DRAM-এর ১ transistor + ১ capacitor অনেক ঘন (সস্তা, বেশি রাখা যায়), কিন্তু charge sharing আর rewrite-এর কারণে ধীর।
SSD আর HDD-এ আরও দুইটা নতুন কারণ যোগ হয়:
- SSD (flash memory): ডেটা একটা floating-gate transistor-এ electron আটকে রেখে সংরক্ষণ করা হয় — read নিজে দ্রুত, কিন্তু ডেটা bus-এর সাথে যোগাযোগ একটা controller আর protocol layer (NVMe/PCIe) দিয়ে হয়, যেটা DRAM-এর সরাসরি সংযোগের চেয়ে অনেক বেশি overhead যোগ করে। উপরন্তু flash কে block-এ (সাধারণত কয়েক KB) read/write করতে হয় — এক বাইট বদলাতে চাইলেও পুরো block নিয়ে কাজ করতে হয়।
- HDD (চুম্বকীয় ডিস্ক): এখানে সবচেয়ে বড় পার্থক্য — এটা একটা যান্ত্রিক (mechanical) ডিভাইস। ডেটা পড়তে read head-কে সঠিক track-এ সরে যেতে হয় (seek time,
~4-9 ms) আর তারপর ঘূর্ণায়মান platter-এর সঠিক sector আসা পর্যন্ত অপেক্ষা করতে হয় (rotational latency,7200 RPM-এ গড়ে~4.2 ms)। এই দুটো মিলিয়েই HDD-র millisecond-স্কেল latency — কোনো transistor বা capacitor delay না, বরং একটা ভৌত বস্তুর নড়াচড়ার সময়।
এই পুরো তালিকাটা একটা প্যাটার্নের ধারাবাহিকতা: যত কাছে, যত সরল প্রক্রিয়া, তত দ্রুত — কিন্তু তত কম জায়গায় (এবং তত বেশি দামে) সীমাবদ্ধ।
দাম দিয়ে দেখা — প্রতি GB কত
গতি আর আকারের বিপরীত সম্পর্কটা টাকায় রূপান্তর করলে সবচেয়ে স্পষ্ট হয়। নিচের সংখ্যাগুলো আনুমানিক, বাজারদর অনুযায়ী বদলায় (এখানে শুধু order-of-magnitude পার্থক্যটা গুরুত্বপূর্ণ, নির্দিষ্ট দাম না):
| স্তর | আনুমানিক দাম / GB | ১৬ GB-তে আনুমানিক দাম |
|---|---|---|
| SRAM (cache-এর মতো ডেডিকেটেড চিপে বানালে) | কয়েকশ থেকে কয়েক-হাজার ডলার | প্রায়োগিকভাবে অবাস্তব — বাজারে বিক্রি হয় না |
| DRAM | কয়েক ডলার | কয়েক-দশ ডলার |
| SSD (NVMe) | এক ডলারের কম | কয়েক ডলার |
| HDD | কয়েক সেন্ট | এক ডলারের কম |
এই টেবিলটাই ব্যাখ্যা করে কেন বাজারে কখনো “১৬ GB SRAM module” পাওয়া যায় না, অথচ “১৬ GB DRAM DIMM” বা “১ TB SSD” সাধারণ ভোক্তা-পণ্য — আগের লেসনে দেখা ৬T বনাম ১T1C cell area পার্থক্য (~১৫-২০×) সরাসরি এই দামের পার্থক্যে রূপান্তরিত হয়। speed, size, আর cost — এই তিনটা axis-ই একে অপরের সাথে বাঁধা; একটাতে জেতা মানে অন্য দুইটাতে ছাড় দেওয়া।
Locality of Reference — যে নীতিটা পুরো হায়ারার্কিকে বাঁচায়
যদি একটা প্রোগ্রামের memory access সত্যিই সম্পূর্ণ random হতো — প্রতিটা access সম্পূর্ণ ভিন্ন, আগের কোনো access-এর সাথে সম্পর্কহীন ঠিকানায় — তাহলে memory hierarchy সম্পূর্ণ অকেজো হয়ে যেত। ছোট, দ্রুত cache-এ যা রাখা আছে তার সাথে পরের access মিলবে এমন কোনো কারণ নেই — প্রতিবারই শেষ পর্যন্ত DRAM (বা তার চেয়েও খারাপ) পর্যন্ত যেতে হতো।
কিন্তু বাস্তব প্রোগ্রাম — প্রায় সবসময়ই — random না। তারা একটা পরিসংখ্যানগত (statistical) নিয়ম মেনে চলে, যার নাম locality of reference, দুইটা রূপে:
Temporal locality — সময়ে কাছাকাছি
যা এইমাত্র access হয়েছে, সেটাই আবার শীঘ্রই access হওয়ার সম্ভাবনা বেশি।
একটা loop-এর ভেতরের variable-এর কথা ভাবুন:
int sum = 0;
for (int i = 0; i \< n; i++) {
sum += arr[i];
}sum আর i — এই দুইটা variable প্রতিটা iteration-এই বারবার access হচ্ছে। প্রথমবার access করার পর সেগুলো যদি একটা দ্রুত জায়গায় (register বা L1 cache) রাখা থাকে, পরের হাজার হাজার access সেই দ্রুত জায়গা থেকেই সেবা পাবে — DRAM পর্যন্ত যেতে হবে না।
Temporal locality-র উৎস প্রায়ই খুব স্বাভাবিক প্রোগ্রামিং প্যাটার্ন থেকে আসে — loop counter, accumulator variable, function-এর ভেতরের local variable, একই function বারবার call হওয়া (recursion বা একই algorithm ভিন্ন data-তে চালানো), এমনকি একই instruction বারবার execute হওয়া (loop-এর body-র instruction-গুলো নিজেরাও temporal locality প্রদর্শন করে — instruction cache, বা I-cache, এই একই নীতির উপর দাঁড়িয়ে)।
Spatial locality — জায়গায় কাছাকাছি
যা access হয়েছে তার কাছাকাছি ঠিকানার ডেটাও শীঘ্রই access হওয়ার সম্ভাবনা বেশি।
একই loop-টা আবার দেখুন — arr[0], তারপর arr[1], তারপর arr[2]… প্রতিটা access আগেরটার ঠিক পাশের memory address। এটা কাকতালীয় না — array-এর সংজ্ঞাই এমন যে তার element-গুলো memory-তে contiguous (একটানা, পাশাপাশি) সাজানো থাকে।
গণিতের লেসন থেকে সরাসরি প্রমাণ — array বনাম linked list
Mathematics module-এর asymptotic-notation লেসনে আমরা একটা experiment দেখেছিলাম যেটা এই ঠিক এই নীতিটাই পরিমাপ করেছিল: array traversal আর linked-list traversal দুটোই Θ(n) — একই সংখ্যক element access, একই বিগ-ও জটিলতা। তবু বাস্তবে array ১০-৫০ গুণ দ্রুত ছিল। কেন?
- Array — element-গুলো contiguous, তাই একটা মাত্র cache line (সাধারণত ৬৪ বাইট) আনলেই
৮-১৬টাintএকসাথে পাওয়া যায় (spatial locality)। Hardware prefetcher pattern চিনে পরের cache line আগেই এনে রাখে। - Linked list — প্রতিটা node heap-এর যেকোনো এলোমেলো জায়গায় থাকতে পারে (কোনো spatial locality নেই)। প্রতিটা
node->nextএকটা নতুন, অপ্রত্যাশিত ঠিকানা — প্রতিটা access সম্ভবত একটা নতুন cache miss, DRAM পর্যন্ত যেতে হয়।
সেই লেসনের সংখ্যাগুলো এই লেসনের latency table দিয়েই ব্যাখ্যা করা যায়: প্রতিটা array access যদি L1-এ hit করে (~4 cycle) কিন্তু প্রতিটা linked-list access যদি DRAM পর্যন্ত যেতে হয় (~200 cycle), তাহলে 200/4 = 50× পার্থক্য — ঠিক সেই “১০-৫০ গুণ” পরিসরের মধ্যেই। এটাই এই লেসনের মূল দাবির সরাসরি, ইতিমধ্যে-পরিমাপ-করা প্রমাণ: locality না থাকলে hierarchy-র সুবিধা পুরোপুরি হারিয়ে যায়।
Working set — একটা প্রোগ্রামের “এখন যা লাগছে”
একটা প্রোগ্রামের working set হলো একটা নির্দিষ্ট সময়ের জানালায় (time window) সে যেই memory location-গুলো বারবার access করছে তার সেট। যদি পুরো working set কোনো একটা cache স্তরে (ধরুন L2) আঁটে, তাহলে সেই সময়ের প্রায় সব access সেই স্তর থেকেই hit পাবে — কার্যকরভাবে প্রোগ্রামটা “L2-গতিতে” চলছে বলে মনে হবে, যদিও তার মোট ডেটা DRAM-এ কয়েক GB। Working set যদি L2-এর সীমা ছাড়িয়ে যায়, বারবার L3/DRAM পর্যন্ত যেতে হবে — একটা স্পষ্ট, পরিমাপযোগ্য performance পতন। এই ধারণাটাই পরের লেসনে (cache organization) hit rate আর replacement policy আলোচনার ভিত্তি হবে, আর operating systems module-এ (Level 4) virtual memory-র paging আলোচনাতেও এই একই “working set” শব্দটা হুবহু ফিরে আসবে, শুধু cache-এর বদলে physical RAM-এর প্রেক্ষাপটে।
ভেতরে কী ঘটছে
কেন হায়ারার্কি গড়ে গড়ে দ্রুত মনে হয়
Locality থাকার একটা সরাসরি পরিণতি: একটা ছোট, দ্রুত memory (cache) যদি সাম্প্রতিক ও কাছাকাছি ডেটা ধরে রাখে, তাহলে বেশিরভাগ access সেই ছোট memory থেকেই সেবা পায় — এটাকে বলে hit। যখন চাওয়া ডেটা cache-এ নেই, সেটাকে বলে miss, আর তখনই পরের, ধীরতর স্তরে যেতে হয়।
┌─────────────┐
│ Register │ ~1 cycle, ~1 KB সবচেয়ে দ্রুত, সবচেয়ে ছোট
└──────┬──────┘
│ miss হলে নিচে যাও
┌──────▼──────┐
│ L1 cache │ ~4 cycle, 32-64 KB
└──────┬──────┘
┌──────▼──────┐
│ L2 cache │ ~12 cycle, 256KB-1MB
└──────┬──────┘
┌──────▼──────┐
│ L3 cache │ ~40 cycle, কয়েক-দশ MB (সাধারণত সব core-এর মধ্যে shared)
└──────┬──────┘
┌──────▼──────┐
│ Main memory │ ~200 cycle, কয়েক GB
│ (DRAM) │
└──────┬──────┘
┌──────▼──────┐
│ SSD │ ~60,000 cycle, কয়েক-শ GB
└──────┬──────┘
┌──────▼──────┐
│ HDD │ ~24,000,000 cycle, কয়েক TB
└─────────────┘
│
সবচেয়ে ধীর, সবচেয়ে বড়, সবচেয়ে সস্তা প্রতি বিটলক্ষ্য করুন — এই ছবিটা লেসন ৭-এর (fetch-decode-execute) সেই datapath diagram-এরই একটা সম্প্রসারণ। সেখানে “memory” একটা একক বাক্স ছিল; এখন আমরা সেই বাক্সটা খুলে দেখছি এটা আসলে সাতটা স্তরের একটা সিঁড়ি।
গড় access time কেন দ্রুত হয়ে যায়
ধরুন একটা loop বারবার একই কয়েকটা variable access করছে (temporal locality)। প্রথমবার সেগুলো DRAM থেকে আসে (~200 cycle) — কিন্তু সেই সাথে সেগুলোর একটা কপি L1 cache-এও থেকে যায়। দ্বিতীয়বার থেকে প্রতিটা access L1 থেকেই সেবা পায় (~4 cycle)। যদি একটা loop 1000 বার চলে, আর মাত্র প্রথমবারটাই DRAM miss হয়:
মোট cycle = ১টা DRAM access + ৯৯৯টা L1 access
= 200 + (999 × 4)
= 200 + 3996
= 4196 cycle
গড় প্রতি access = 4196 / 1000 ≈ 4.2 cycleগড়টা ৪.২ cycle — DRAM-এর ২০০ cycle-এর কাছাকাছিও না, বরং প্রায় L1-এর ৪ cycle-এরই কাছাকাছি! এটাই hierarchy-র আসল জাদু — 99.9% hit rate মানে গড় performance প্রায় সবচেয়ে দ্রুত স্তরের performance-এর সমান, যদিও সবচেয়ে ধীর স্তরও ব্যবহার হচ্ছে। পরের লেসনে (cache policies) আমরা এই “গড়” ধারণাটাকেই একটা আনুষ্ঠানিক সূত্রে (Average Memory Access Time, AMAT) রূপ দেব, আর দেখব hit rate সামান্য কমলে এই গড় কতটা নাটকীয়ভাবে খারাপ হয়ে যায়।
Memory wall — কেন এই সমস্যাটা বছরের পর বছর আরও খারাপ হয়েছে
Latency বনাম bandwidth — দুইটা ভিন্ন প্রশ্ন
এই লেসনে আমরা মূলত latency নিয়ে কথা বলছি — একটা একক request-এর উত্তর পেতে কত সময় লাগে। এর থেকে আলাদা একটা মাপ হলো bandwidth (বা throughput) — প্রতি সেকেন্ডে কত ডেটা transfer করা যায়, ধারাবাহিকভাবে অনেকগুলো request একসাথে চললে। DRAM-এর latency খারাপ (~200 cycle) কিন্তু bandwidth তুলনামূলক ভালো (আধুনিক DDR5-এ প্রতি সেকেন্ডে কয়েক-দশ GB) — কারণ একবার row activate হয়ে গেলে, একই row-এর ভেতরের একাধিক column দ্রুত, পাইপলাইন করে পড়া যায় (আগের লেসনের “page mode”)। এই পার্থক্যটা মনে রাখা জরুরি: একটা মেমরি প্রযুক্তি latency-তে খারাপ কিন্তু bandwidth-এ ভালো হতে পারে, একই সাথে — GPU memory (HBM/GDDR) এর একটা চরম উদাহরণ, যেখানে latency DRAM-এর মতোই বা তার চেয়েও বেশি, কিন্তু bandwidth বহুগুণ বেশি, কারণ GPU workload latency-sensitive না, বরং massively parallel, bandwidth-hungry।
Bandwidth-এর বাস্তব সংখ্যা — hierarchy জুড়ে
Latency table-এর পাশাপাশি bandwidth-এর একটা আনুমানিক টেবিলও দরকারি — কারণ দুইটা মাপ একই দিকে বাড়ে-কমে না:
| স্তর | আনুমানিক sequential bandwidth |
|---|---|
| L1 cache | কয়েকশ GB/s (per core) |
| L2 cache | ~100-200 GB/s |
| L3 cache | ~50-100 GB/s (shared, তাই একাধিক core ভাগ করে নেয়) |
| Main memory (dual/quad-channel DDR5) | ~30-70 GB/s |
| SSD (NVMe, PCIe 4.0) | ~5-7 GB/s |
| HDD | ~150-250 MB/s |
লক্ষ্য করুন — latency-তে L1 থেকে HDD পর্যন্ত পার্থক্য প্রায় আট কোটি গুণ (0.3 ns বনাম 8 ms), কিন্তু bandwidth-এ পার্থক্য মাত্র কয়েক হাজার গুণ (কয়েকশ GB/s বনাম কয়েকশ MB/s)। এই অসামঞ্জস্যটাই ব্যাখ্যা করে কেন disk-based system-এ sequential I/O প্রায় সবসময় random I/O-র চেয়ে বহুগুণ পছন্দনীয় — latency-র পার্থক্য bandwidth-এর পার্থক্যের চেয়ে অনেক বেশি নাটকীয়, তাই একটা বড়, sequential transfer-এ latency-র “fixed cost” ভাগ হয়ে যায় অনেক বাইটের মধ্যে, কিন্তু বহু ছোট random transfer-এ প্রতিটাই পূর্ণ latency-র দাম দেয়।
একটা ৪০ বছরের ব্যবধান — memory wall সংখ্যায়
উপরের “memory wall” গল্পটাকে concrete সংখ্যায় দেখা যাক — CPU clock speed আর DRAM latency (CPU cycle-এ প্রকাশিত) কীভাবে সময়ের সাথে আলাদা হয়ে গেছে তার একটা আনুমানিক, illustrative চিত্র:
| দশক | আনুমানিক CPU clock | আনুমানিক DRAM latency (real সময়) | DRAM latency (CPU cycle-এ) |
|---|---|---|---|
| ~1980 | ~5 MHz | ~200 ns | ~1 cycle |
| ~1990 | ~50 MHz | ~100 ns | ~5 cycle |
| ~2000 | ~1 GHz | ~70 ns | ~70 cycle |
| ~2020 | ~3-5 GHz | ~60 ns | ~200-300 cycle |
DRAM-এর real-time latency (ন্যানোসেকেন্ডে) মাত্র ~3× কমেছে চল্লিশ বছরে, কিন্তু CPU clock speed বেড়েছে প্রায় ~1000× — ফলে CPU cycle-এ প্রকাশ করা DRAM latency নাটকীয়ভাবে বেড়ে গেছে, ~1 cycle থেকে ~200-300 cycle-এ। এটাই সেই ক্রমবর্ধমান “wall” — CPU দ্রুততর হচ্ছে, কিন্তু DRAM প্রায় একই গতিতে আটকে আছে, তাই ফাঁকটা শুধু চওড়া হয়েছে। এই সংখ্যাগুলো আনুমানিক ও illustrative (নির্দিষ্ট চিপ প্রজন্মভেদে ভিন্ন হবে), কিন্তু trend-টা বাস্তব ও প্রামাণ্যভাবে নথিভুক্ত — আর ঠিক এই trend-ই বহু-স্তরের cache hierarchy-কে ঐচ্ছিক থেকে অপরিহার্য করে তুলেছে।
উদাহরণ
সংখ্যায় দেখা — একটা array যখন বড় হতে থাকে
ধরুন একটা প্রোগ্রাম একটা int array-এর যোগফল বের করছে, আর আমরা array-এর আকার ধীরে ধীরে বাড়াচ্ছি। প্রতিটা int ৪ বাইট।
| Array আকার | মোট বাইট | কোথায় আঁটে | প্রতি-access latency (আনুমানিক) |
|---|---|---|---|
4,096 element | 16 KB | L1-এ আঁটে (32-64 KB) | ~4 cycle |
65,536 element | 256 KB | L2-এ আঁটে (256KB-1MB) | ~12 cycle |
2,000,000 element | ~8 MB | L3-এ আঁটে (কয়েক-দশ MB) | ~40 cycle |
50,000,000 element | ~200 MB | L3 ছাড়িয়ে, DRAM-এ | ~200 cycle |
লক্ষ্য করুন — algorithm হুবহু একই (Θ(n) sum), input-এর সংখ্যাগত আকার ছাড়া কিছুই বদলায়নি। তবু চতুর্থ সারির প্রোগ্রামটা প্রথম সারির তুলনায় প্রতি-access প্রায় ৫০ গুণ ধীর হতে পারে — শুধুমাত্র সেই array-টা কোন memory hierarchy স্তরে “আঁটছে” তার উপর ভিত্তি করে। এটাই mathematics/asymptotic-notation লেসনের সতর্কবাণীর হুবহু বাস্তবায়ন: Big-O input-এর আকারের সাথে কাজের বৃদ্ধি বলে, কিন্তু memory hierarchy-র প্রভাব সম্পূর্ণ অদৃশ্য রাখে।
Base+offset addressing — একটা concrete instruction-স্তরের উদাহরণ
arr[i] access করতে কম্পাইলার একটা addressing mode ব্যবহার করে যা মূলত বলে “base register-এর মান + (i × element_size)”। ধরুন arr-এর base ঠিকানা 0x1000, element_size = 4:
i = 0 → address = 0x1000 + (0 × 4) = 0x1000
i = 1 → address = 0x1000 + (1 × 4) = 0x1004
i = 2 → address = 0x1000 + (2 × 4) = 0x1008
i = 3 → address = 0x1000 + (3 × 4) = 0x100Cপ্রতিটা পরপর ঠিকানা মাত্র ৪ বাইট দূরে — একটা ৬৪-বাইট cache line-এ ১৬টা int আঁটে, তাই প্রথম access-এই পুরো ০x1000-০x103F range-টা cache-এ চলে আসে (আমরা কীভাবে সেটা জানব তা লেসন ৮-এ)। পরের ১৫টা access — i=1 থেকে i=15 পর্যন্ত — সবগুলোই সেই একই cache line-এ hit করবে, DRAM পর্যন্ত না গিয়েই। এটা কোনো “স্মার্ট” software কৌশল না — এটা addressing mode আর cache line size-এর যান্ত্রিক মিথস্ক্রিয়ার সরাসরি ফলাফল।
তুলনায়, যদি একই loop arr[i]-এর বদলে arr[random_index()] ব্যবহার করত — প্রতিটা access সম্ভাব্য একটা সম্পূর্ণ ভিন্ন cache line দাবি করত, spatial locality সম্পূর্ণ হারিয়ে যেত।
- arr[0] accessঠিকানা 0x1000, cache miss (প্রথমবার) → পুরো 64-বাইট line DRAM থেকে আসে
- L1 cache-এ line জমা0x1000-0x103F পুরোটা এখন L1-এ — 16টা int
- arr[1] accessঠিকানা 0x1004 — একই line-এ, L1 hit (~4 cycle)
- arr[2]...arr[15] accessসবগুলো একই line-এ — সবগুলো L1 hit
- arr[16] accessঠিকানা 0x1040 — নতুন line, আরেকটা miss
নিজে চালিয়ে দেখুন
নিজের মেশিনে সম্পূর্ণ hierarchy-র speed jump মাপুন
আগে digital-logic/memory-sram-dram লেসনে আমরা এই একই ধরনের experiment করেছিলাম শুধু SRAM/DRAM সীমানা দেখতে। এবার একই কৌশল ব্যবহার করে পুরো hierarchy জুড়ে (L1 থেকে DRAM পর্যন্ত) latency জাম্পগুলো একসাথে মাপি এবং locality-র প্রভাবও যোগ করি — একই array আকারে sequential বনাম random access তুলনা করে।
import time
import random
def measure_sequential(size_bytes, iterations=3_000_000):
n_ints = size_bytes // 8
arr = list(range(n_ints))
total = 0
t0 = time.perf_counter()
idx = 0
for _ in range(iterations):
total += arr[idx]
idx = (idx + 1) % n_ints
dt = time.perf_counter() - t0
return dt / iterations
def measure_random(size_bytes, iterations=300_000):
n_ints = size_bytes // 8
arr = list(range(n_ints))
order = list(range(n_ints))
random.shuffle(order)
total = 0
t0 = time.perf_counter()
idx = 0
for _ in range(iterations):
total += arr[order[idx]]
idx = (idx + 1) % n_ints
dt = time.perf_counter() - t0
return dt / iterations
sizes_kb = [16, 64, 256, 1024, 8192, 65536]
print(f"{'আকার (KB)':>10} {'sequential (ns)':>18} {'random (ns)':>15}")
for kb in sizes_kb:
ts = measure_sequential(kb * 1024)
tr = measure_random(kb * 1024)
print(f"{kb:>10,} {ts*1e9:>18.1f} {tr*1e9:>15.1f}")সাধারণ (illustrative) ফলাফলের ধরন:
আকার (KB) sequential (ns) random (ns)
16 1.4 1.6 ← দুটোই L1-এ, পার্থক্য কম
64 2.9 5.2 ← L2 সীমানা, random এগিয়ে খারাপ হতে শুরু করে
256 3.5 11.0 ← L2-এর শেষ, spatial locality-র সুবিধা কমে যাচ্ছে
1024 9.0 28.0 ← L3-এ ঢুকল
8192 11.5 65.0 ← L3-এর কিনারা
65536 38.0 210.0 ← DRAM — sequential-ও 5× ধীর, random আরও খারাপযা লক্ষ্য করার: প্রতিটা সারিতেই random কলাম sequential-এর চেয়ে ধীর — সেটাই spatial locality-র সরাসরি প্রমাণ, একই array আকারে। আর দুই কলামই বড় আকারে বাড়ছে — সেটা hierarchy-র স্তর পরিবর্তনের প্রমাণ। দুটো effect স্বাধীন কিন্তু একসাথে কাজ করছে।
Array আকার L1 → L2 → L3 → DRAM-এর সীমা পার হওয়ার সাথে সাথে per-access latency ধাপে ধাপে বাড়ে — শুধু তত্ত্ব নয়, নিজের মেশিনেই পরিমাপযোগ্য।
Disk/SSD পর্যন্ত hierarchy সম্প্রসারণ — file I/O দিয়ে মাপুন
import os
import time
import random
FILE = "/tmp/hierarchy_test.bin"
SIZE_MB = 500
BLOCK = 4096 # সাধারণ filesystem block size
def make_file():
with open(FILE, "wb") as f:
f.write(os.urandom(1))
f.seek(SIZE_MB * 1024 * 1024 - 1)
f.write(b"\\0")
def sequential_read(n_blocks=2000):
with open(FILE, "rb") as f:
t0 = time.perf_counter()
for i in range(n_blocks):
f.seek(i * BLOCK)
f.read(BLOCK)
dt = time.perf_counter() - t0
return dt / n_blocks
def random_read(n_blocks=2000):
total_blocks = (SIZE_MB * 1024 * 1024) // BLOCK
offsets = [random.randint(0, total_blocks - 1) * BLOCK for _ in range(n_blocks)]
with open(FILE, "rb") as f:
t0 = time.perf_counter()
for off in offsets:
f.seek(off)
f.read(BLOCK)
dt = time.perf_counter() - t0
return dt / n_blocks
make_file()
os.system("sync && echo 3 | sudo tee /proc/sys/vm/drop_caches > /dev/null 2>&1") # OS page cache খালি করার চেষ্টা
print(f"sequential: {sequential_read()*1e6:.1f} μs/block")
print(f"random: {random_read()*1e6:.1f} μs/block")drop_caches কমান্ডটা root privilege লাগতে পারে বা সব সিস্টেমে কাজ নাও করতে পারে — উদ্দেশ্য হলো OS-এর নিজের memory-based file cache (page cache, যেটা operating-systems module-এ বিস্তারিত আসবে) এড়িয়ে সত্যিকারের disk/SSD access মাপা। SSD-তে sequential আর random-এর পার্থক্য তুলনামূলক কম (কয়েক μs), কারণ SSD-র কোনো যান্ত্রিক seek নেই। কিন্তু যদি একটা পুরনো spinning HDD-তে চালানো যায়, পার্থক্যটা নাটকীয় — random access-এ প্রতিটা block-এর জন্য মাথা নড়াচড়া করতে হয়, ~৫-১০ ms করে, sequential read-এর চেয়ে ১০০-১০০০ গুণ ধীর হতে পারে।
Memory hierarchy শুধু cache/DRAM-এ থেমে থাকে না — একই নীতি (sequential বনাম random access) disk পর্যন্ত প্রসারিত, আর সেখানে পার্থক্যটা মিলিসেকেন্ড-স্কেলে, cache-এর চেয়ে বহুগুণ বড়।
নিজে বানান
Latency Ladder — hierarchy-র সংখ্যাগুলো নিজে হিসাব করুন
- প্রতিটা memory স্তরের cycle-latency আর আকার একটা dictionary-তে সংরক্ষণ করুন
- প্রতিটা স্তরের latency-কে সেকেন্ডে রূপান্তর করুন (ধরে নিন 3 GHz clock)
- প্রতিটা স্তরকে register-এর সাপেক্ষে scale করুন (register = 1 সেকেন্ড ধরে)
- একটা সাধারণ টেক্সট বার-চার্ট আঁকুন যেখানে প্রতিটা bar-এর দৈর্ঘ্য log10(cycle count)-এর সমানুপাতিক
লক্ষ্য: এই লেসনের সংখ্যাগুলো মুখস্থ করার বদলে নিজে গণনা করে “অনুভব” করা — বিশেষ করে log-scale bar-chart দেখলে বোঝা যায় কেন linear scale-এ এই পার্থক্যগুলো আঁকাই অসম্ভব।
LEVELS = [
("Register", 1, "~1 KB"),
("L1 cache", 4, "32-64 KB"),
("L2 cache", 12, "256KB-1MB"),
("L3 cache", 40, "কয়েক-দশ MB"),
("DRAM", 200, "কয়েক GB"),
("SSD", 60_000, "কয়েক-শ GB"),
("HDD", 24_000_000, "কয়েক TB"),
]
CLOCK_HZ = 3e9
CYCLE_TIME_S = 1 / CLOCK_HZ
def format_scaled_time(seconds):
if seconds \< 60:
return f"{seconds:.1f} সেকেন্ড"
minutes = seconds / 60
if minutes \< 60:
return f"{minutes:.1f} মিনিট"
hours = minutes / 60
if hours \< 24:
return f"{hours:.1f} ঘণ্টা"
days = hours / 24
return f"{days:.0f} দিন"
print(f"{'স্তর':\<12}{'cycle':>12}{'সময়':>14}{'১ সে. হলে':>16} bar")
for name, cycles, size in LEVELS:
real_time_ns = cycles * CYCLE_TIME_S * 1e9
scaled_seconds = cycles * 1.0 # register = 1 cycle = 1 সেকেন্ড ধরে scale
import math
bar_len = int(math.log10(cycles + 1) * 8)
bar = "#" * bar_len
print(f"{name:\<12}{cycles:>12,}{real_time_ns:>12.1f}ns{format_scaled_time(scaled_seconds):>16} {bar}")প্রত্যাশিত আউটপুট (ধরন):
স্তর cycle সময় ১ সে. হলে bar
Register 1 0.3ns 1.0 সেকেন্ড #
L1 cache 4 1.3ns 4.0 সেকেন্ড ####
L2 cache 12 4.0ns 12.0 সেকেন্ড ######
L3 cache 40 13.3ns 40.0 সেকেন্ড #######
DRAM 200 66.7ns 3.3 মিনিট #########
SSD 60,000 20000.0ns 16.7 ঘণ্টা ############
HDD 24,000,000 8000000.0ns 278 দিন ###############log10 স্কেল ব্যবহার করার কারণটাই এই build-এর আসল শিক্ষা — যদি bar-এর দৈর্ঘ্য সরাসরি cycle সংখ্যার সমানুপাতিক হতো, HDD-র bar হতো Register-এর bar-এর চেয়ে ২ কোটি ৪০ লক্ষ গুণ লম্বা — কোনো স্ক্রিনেই আঁটত না। এটাই এই লেসনের সংখ্যাগুলোর প্রকৃত স্কেল — এতটাই বিশাল যে সরাসরি তুলনা করাই কঠিন, তাই log scale বা “human timescale” রূপকের প্রয়োজন হয়।
বাস্তব সিস্টেমে
বাস্তব সিস্টেমে memory hierarchy
১. আধুনিক CPU-র বাস্তব cache স্পেসিফিকেশন
Apple M-সিরিজ, Intel Core, AMD Ryzen — প্রায় সব আধুনিক CPU-তে ঠিক এই লেসনের L1/L2/L3 কাঠামো বাস্তবে আছে। উদাহরণ (আনুমানিক, প্রজন্মভেদে বদলায়): একটা modern desktop CPU-তে প্রতি core-এ ৩২ KB L1 data cache + ৩২ KB L1 instruction cache (আলাদা!), ৫১২ KB-১ MB L2 প্রতি core, আর সব core-এর মধ্যে shared ১৬-৩২ MB L3। lscpu বা cat /proc/cpuinfo (Linux-এ) দিয়ে নিজের মেশিনের প্রকৃত সংখ্যা দেখা যায়।
| CPU (আনুমানিক, প্রজন্মভেদে বদলায়) | L1 (প্রতি core) | L2 (প্রতি core) | L3 (shared) |
|---|---|---|---|
| একটা ~২০১০-এর দশকের desktop CPU | 32KB+32KB | 256KB | 8-12 MB |
| একটা আধুনিক desktop CPU (Intel/AMD) | 32-48KB+32KB | 1-2 MB | 16-32 MB |
| একটা আধুনিক Apple Silicon (M-সিরিজ) | 128-192KB+128-192KB | 4-16 MB (cluster-shared) | কয়েক-দশ MB (system-level cache) |
লক্ষ্য করার মতো — Apple-এর design-এ L1 তুলনামূলক অনেক বড় (~128-192KB, প্রতিদ্বন্দ্বীদের ~32-48KB-র তুলনায় কয়েক গুণ) — এটা এই লেসনের “বড় cache মানেই ধীর” নীতির সাথে সাংঘর্ষিক মনে হতে পারে, কিন্তু আসলে সেটা ভিন্ন ভিন্ন engineering trade-off পয়েন্ট বেছে নেওয়ার প্রমাণ — বড় L1 রাখতে হলে হয়তো সামান্য বেশি latency মেনে নিতে হয়, বিনিময়ে miss rate কমে। প্রতিটা vendor নিজের workload আর manufacturing process অনুযায়ী এই স্পেকট্রামে ভিন্ন বিন্দু বেছে নেয় — কোনো একটা “সঠিক” সংখ্যা নেই, শুধু trade-off।
২. Instruction cache আর data cache — কেন আলাদা
লক্ষ্য করুন উপরের উদাহরণে L1 আসলে দুইটা আলাদা cache — একটা instruction-এর জন্য (I-cache), একটা data-র জন্য (D-cache)। এটাকে বলে split cache (বনাম unified cache, যেখানে instruction ও data একই cache ভাগ করে নেয়)। কারণ: instruction fetch আর data access প্রায় প্রতি cycle-েই একসাথে দরকার হয় (fetch stage আর memory-access stage pipeline-এ সমান্তরালে চলে) — যদি একটাই cache port থাকত, প্রতি cycle-এ দুটোর মধ্যে conflict হতো। এই design decision-টা লেসন ৬-এর pipeline আলোচনার একটা সরাসরি পূর্বাভাস।
৩. Web browser-এর multi-layer cache
আপনার browser-এ একই hierarchy-র দর্শন বাস্তবায়িত: memory-তে একটা ছোট, দ্রুত image/resource cache, তারপর disk-এ একটা বড়, ধীরতর cache (~কয়েকশ MB), তারপর একটা CDN (আপনার শহরের কাছে), তারপর আসল origin server (হয়তো অন্য মহাদেশে)। প্রতিটা স্তর আগেরটার তুলনায় বড় কিন্তু ধীর — ঠিক এই লেসনের প্যাটার্ন, শুধু ন্যানোসেকেন্ডের বদলে মিলিসেকেন্ড স্কেলে। এই বিষয়টা networking module-এ বিস্তারিত আসবে।
৪. Database buffer pool
একটা database (PostgreSQL, MySQL) disk-এ থাকা table-এর “hot” page-গুলো RAM-এ একটা buffer pool-এ রাখে — যেটা কার্যত disk-এর জন্য একটা software-managed cache, এই লেসনের hardware cache-এর একই নীতিতে (locality — সাম্প্রতিক বা ঘনঘন query করা row-গুলো RAM-এ থাকে)। databases module-এ এই buffer pool-এর replacement policy বিস্তারিত পড়বেন — যেটা পরের লেসনের LRU-র সাথে হুবহু সম্পর্কিত।
৫. কম্পাইলার register allocation
কম্পাইলার (programming-languages/compilers module) সবচেয়ে ঘনঘন-ব্যবহৃত variable-গুলোকে register-এ রাখার চেষ্টা করে (register allocation), কারণ register hierarchy-র সবচেয়ে দ্রুত স্তর। যে variable কম ব্যবহার হয়, সেটাকে stack-এ (মূলত memory-তে) “spill” করে দেওয়া হয়। এটা এই লেসনের temporal locality নীতির একটা compile-time প্রয়োগ — যেটা বেশি বার লাগবে, সেটা সবচেয়ে দ্রুত জায়গায় রাখো।
৬. Hardware prefetcher
আধুনিক CPU spatial locality active-ভাবে exploit করে — যদি একটা প্রোগ্রাম ঠিকানা A, A+64, A+128 ক্রমাগত access করে, prefetcher pattern চিনে আগেই A+192 cache-এ এনে রাখে, যাতে actual access-এর সময় সেটা আর miss না হয়। এটাই আগের experiment-এ “stride access” ব্যবহারের কারণ ছিল — prefetcher-কে বিভ্রান্ত করে প্রকৃত cache miss আদায় করা।
৭. Virtual memory ও swap — hierarchy DRAM-এর পরেও চলে
operating-systems module-এ (Level 4) দেখবেন OS কীভাবে DRAM-কেও একটা “cache” হিসেবে ব্যবহার করে disk-এর জন্য — যখন RAM ভরে যায়, কম-ব্যবহৃত page disk-এ (swap) সরিয়ে দেওয়া হয়, প্রয়োজনে আবার ফিরিয়ে আনা হয় (demand paging)। এই লেসনের পুরো hierarchy — register থেকে disk — তাই শুধু hardware না, একটা software layer (OS) দিয়েও প্রসারিত হয়।
৮. Distributed system-এর caching layer
distributed-systems module-এ (Level 9) Redis/Memcached-এর মতো in-memory cache একটা ধীর database-এর সামনে বসানো হয় — একদম এই লেসনের একই যুক্তি, শুধু স্কেল আরও বড়: RAM (দ্রুত, ব্যয়বহুল, ছোট) বনাম disk-based database (ধীর, সস্তা, বড়)। “Cache invalidation” — cache আর আসল ডেটার মধ্যে সামঞ্জস্য রাখার সমস্যা — সেখানে একটা কেন্দ্রীয় বিষয়, আর লেসন ৯-এ আমরা এই একই সমস্যার হার্ডওয়্যার-স্তরের সংস্করণ (write policy) দেখব।
যে ভুলগুলো সবাই করে
“Cache একটা সম্পূর্ণ ভিন্ন, বিশেষ ধরনের hardware — সাধারণ memory থেকে আলাদা কিছু”
Cache আসলে সেই একই SRAM — গত লেসনে দেখা ৬-transistor cell। এটা “বিশেষ” কোনো প্রযুক্তি না, শুধু ছোট আর CPU-র কাছাকাছি বসানো একটা memory array, যেটা locality exploit করার জন্য নির্দিষ্ট addressing/lookup hardware (পরের লেসনে দেখব — tag/index/offset) দিয়ে ঘেরা। মূল storage mechanism হুবহু register file-এর মতোই।
“যত বড় cache, তত ভালো পারফরম্যান্স — তাই সব cache বড় করা উচিত”
বড় cache মানে বেশি physical area, যার মানে তারের দৈর্ঘ্য বাড়ে (signal propagation delay বাড়ে) আর addressing hardware জটিল হয় (বেশি entry-র মধ্যে খোঁজা)। তাই বড় cache প্রায়ই নিজেই ধীর — এই কারণেই L1 ছোট কিন্তু ~4 cycle, L3 বড় কিন্তু ~40 cycle। ইঞ্জিনিয়াররা তাই hierarchy বানান — একটা একক “যত বড় তত ভালো” cache-এর বদলে, ছোট-দ্রুত থেকে বড়-ধীর পর্যন্ত একাধিক স্তর, প্রতিটা তার নিজের trade-off point-এ optimal।
“Locality of reference শুধু array-এর মতো ডেটা structure-এর জন্য প্রযোজ্য”
Temporal ও spatial locality প্রায় সব বাস্তব প্রোগ্রামে দেখা যায় — শুধু array না। Instruction fetch নিজেই প্রবল spatial locality দেখায় (instruction-গুলো memory-তে ক্রমান্বয়ে সাজানো, আর loop-এর ভেতরের instruction বারবার fetch হয় — temporal locality)। Stack access (function call/return, local variable) সবসময় সাম্প্রতিক stack frame-এর কাছাকাছি হয়। এমনকি hash table lookup-ও যদি একই key বারবার query হয় temporal locality দেখায়, যদিও bucket-এর ঠিকানা এলোমেলো হতে পারে।
“যথেষ্ট register থাকলে cache-এর দরকার নেই”
একটা আধুনিক CPU-র architectural register file মাত্র ~১ KB (কয়েক ডজন register)। একটা বাস্তব প্রোগ্রামের working set — যে ডেটা সে বারবার ব্যবহার করছে — প্রায়ই কয়েক KB থেকে কয়েক MB, register file-এর চেয়ে বহুগুণ বড়। Register শুধু compiler-নির্বাচিত সবচেয়ে “hot” কয়েকটা variable ধরে রাখতে পারে; বাকি সবকিছুর জন্য cache প্রয়োজন — এটাই hierarchy-র মধ্যবর্তী স্তরগুলোর (L1/L2/L3) থাকার কারণ, শুধু register আর DRAM-এর মধ্যে সরাসরি লাফ না দিয়ে।
বুঝেছেন কি না দেখুন
1একটা প্রোগ্রাম তার পুরো জীবদ্দশায় exactly একবার প্রতিটা byte access করে, কখনো একই byte দুইবার access করে না, আর ধারাবাহিকভাবে সম্পূর্ণ random ঠিকানায় লাফায়। এই প্রোগ্রামের জন্য memory hierarchy কি কোনো সুবিধা দেবে? কেন বা কেন না?
যুক্তি
না, কোনো সুবিধা দেবে না — বরং সামান্য overhead-ই যোগ করবে। Memory hierarchy কাজ করে locality of reference-এর উপর ভিত্তি করে: temporal locality (একই ডেটা বারবার লাগা) আর spatial locality (কাছাকাছি ডেটা লাগা)। এই কাল্পনিক প্রোগ্রামে দুটোর একটাও নেই — প্রতিটা byte ঠিক একবার, এলোমেলো ঠিকানায়। প্রতিটা access-ই একটা cache miss হবে (কারণ চাওয়া ডেটা আগে কখনো আনা হয়নি এবং আবার লাগবেও না), তাই প্রতিটা access-ই কার্যত সবচেয়ে ধীর স্তর (DRAM বা তারও নিচে) পর্যন্ত যেতে বাধ্য হবে। বাস্তবে এমন প্রোগ্রাম প্রায় অস্তিত্বহীন — এমনকি “random” workload-ও (যেমন hash table) সাধারণত কিছু না কিছু locality রাখে।
2একটা loop 1,000,000 বার একটা 8 KB array বারবার (ক্রমান্বয়ে, শুরু থেকে শেষ, তারপর আবার শুরু থেকে) traverse করছে। প্রথম pass-এর প্রতিটা access DRAM থেকে আসবে ধরে নিন (~200 cycle), আর বাকি সব pass L1 থেকে (~4 cycle, কারণ 8 KB সহজেই L1-এ আঁটে)। যদি array-এ 2,000 element থাকে, মোট cycle সংখ্যা আর গড় প্রতি-access cycle আনুমানিক হিসাব করুন।
প্রয়োগ
1,000,000 বার একটা 8 KB array বারবার (ক্রমান্বয়ে, শুরু থেকে শেষ, তারপর আবার শুরু থেকে) traverse করছে। প্রথম pass-এর প্রতিটা access DRAM থেকে আসবে ধরে নিন (~200 cycle), আর বাকি সব pass L1 থেকে (~4 cycle, কারণ 8 KB সহজেই L1-এ আঁটে)। যদি array-এ 2,000 element থাকে, মোট cycle সংখ্যা আর গড় প্রতি-access cycle আনুমানিক হিসাব করুন।মোট access = 1,000,000 × 2,000 = 2×10⁹। প্রথম pass-এর 2,000 access DRAM থেকে: 2,000 × 200 = 400,000 cycle। বাকি (2×10⁹ − 2,000) access প্রায় সবগুলোই L1 থেকে: ≈ 2×10⁹ × 4 = 8×10⁹ cycle। মোট ≈ 8×10⁹ + 400,000 ≈ 8×10⁹ cycle (DRAM অংশ নগণ্য)। গড় প্রতি-access ≈ 8×10⁹ / 2×10⁹ = 4 cycle — কার্যত L1-এর গতি, যদিও ডেটা মূলত DRAM-এ “থাকে”। এটাই hierarchy-এর মূল সুবিধার সংখ্যাগত প্রমাণ (hood section-এর হিসাবের একটা বড়-স্কেল সংস্করণ)।
3লিঙ্ক-লিস্ট traversal আর array traversal দুটোই Θ(n) — একই বিগ-ও জটিলতা। তবু বাস্তবে array-ই দ্রুত। এই লেসনের কোন দুটো ধারণা দিয়ে এই পার্থক্যটা ব্যাখ্যা করবেন, আর কেন Big-O নিজে এটা ধরতে পারে না?
যুক্তি
Θ(n) — একই বিগ-ও জটিলতা। তবু বাস্তবে array-ই দ্রুত। এই লেসনের কোন দুটো ধারণা দিয়ে এই পার্থক্যটা ব্যাখ্যা করবেন, আর কেন Big-O নিজে এটা ধরতে পারে না?স্পেসিফিকভাবে spatial locality-র পার্থক্য — array-এর element-গুলো contiguous, তাই একটা cache line আনলেই একসাথে অনেকগুলো element পাওয়া যায়; linked-list-এর node-গুলো heap-এ এলোমেলোভাবে ছড়ানো, তাই প্রায় প্রতিটা access একটা নতুন cache miss। দ্বিতীয় ধারণা — memory hierarchy latency-র বিশাল পার্থক্য (L1 ~4 cycle বনাম DRAM ~200 cycle) — এটাই বলে দেয় miss-এর “দাম” কতটা বড়। Big-O ধরতে পারে না কারণ এটা শুধু operation-সংখ্যা গোনে (“কতগুলো ধাপ”), প্রতিটা ধাপের প্রকৃত physical cost (কোন memory স্তর থেকে সেবা পাচ্ছে) সম্পূর্ণ উপেক্ষা করে — এটা একটা ইচ্ছাকৃত abstraction, যেটা কখনো কখনো (এখানে যেমন) বাস্তব performance থেকে অনেক দূরে সরে যায়।
4একজন প্রোগ্রামার একটা 2D matrix M[row][col] কে row-order-এ traverse করছেন (প্রথমে সব col একটা row-এর জন্য, তারপর পরের row) বনাম column-order-এ (প্রথমে সব row একটা col-এর জন্য, তারপর পরের col)। C-তে 2D array row-major order-এ (একটা row-এর সব element পাশাপাশি) সংরক্ষিত হয়। কোন traversal দ্রুত হবে, আর কেন?
প্রয়োগ
M[row][col] কে row-order-এ traverse করছেন (প্রথমে সব col একটা row-এর জন্য, তারপর পরের row) বনাম column-order-এ (প্রথমে সব row একটা col-এর জন্য, তারপর পরের col)। C-তে 2D array row-major order-এ (একটা row-এর সব element পাশাপাশি) সংরক্ষিত হয়। কোন traversal দ্রুত হবে, আর কেন?Row-order traversal দ্রুত হবে। কারণ row-major storage-এ একটা row-এর element-গুলো memory-তে contiguous (পাশাপাশি) — row-order traversal তাই ক্রমান্বয়ে পাশাপাশি ঠিকানা access করে, শক্তিশালী spatial locality। Column-order traversal প্রতিটা access-এ পরের row-এ (memory-তে অনেক দূরে, row_width × element_size বাইট দূরে) লাফায় — প্রতিটা access সম্ভবত একটা নতুন cache line, spatial locality প্রায় শূন্য। এটা locality-র একটা বাস্তব, প্রতিদিনের প্রোগ্রামিং প্রভাব — অনেক ভাষায় (numpy, MATLAB-এর কিছু mode) এই loop-order পছন্দ পরিমাপযোগ্যভাবে কয়েক গুণ পার্থক্য তৈরি করে।
5কল্পনা করুন কেউ প্রস্তাব দিলেন — “L2, L3 বাদ দিয়ে শুধু একটা বিশাল, ৩২ MB L1 cache বানাই, সরাসরি register-এর পাশে।” এই ডিজাইনের সমস্যাটা এই লেসনের কোন নীতি দিয়ে ব্যাখ্যা করবেন?
ডিজাইন
৩২ MB L1 cache বানাই, সরাসরি register-এর পাশে।” এই ডিজাইনের সমস্যাটা এই লেসনের কোন নীতি দিয়ে ব্যাখ্যা করবেন?সমস্যাটা “দ্রুত + বড় একসাথে পাওয়া যায় না” নীতি। L1-কে ৩২ MB-এ বড় করলে সেটা আর “L1-এর মতো দ্রুত” থাকবে না — বড় SRAM array মানে বেশি row/column, দীর্ঘ bit line, ধীরতর sense amplifier, আর জটিল addressing hardware, যার সবগুলোই propagation delay বাড়ায় (যেমন আগের লেসনে row/column addressing-এ দেখা হয়েছিল বড় array কেন সবসময় বেশি ধাপ নেয়)। বাস্তবে এমন একটা cache হয়তো L3-এর মতো ~40 cycle latency পেত — কিন্তু তাহলে সেটা আসলে “L3” নামেই পরিচিত হতো, শুধু এখন ছোট, দ্রুত L1/L2 স্তরগুলো হারিয়ে গেছে যেগুলো সবচেয়ে ঘনঘন-ব্যবহৃত ডেটার জন্য ~4 cycle গতি দিত। Multi-level hierarchy তাই কোনো ঐচ্ছিক জটিলতা না — এটা speed-vs-size trade-off-এর প্রতিটা বিন্দুতে আলাদা optimal design পাওয়ার একমাত্র উপায়।
6DRAM-এর latency (L1-এর তুলনায়) খুবই খারাপ, তবু আধুনিক DDR5 memory-র bandwidth (প্রতি সেকেন্ডে কত বাইট) তুলনামূলকভাবে বেশ ভালো — L1-এর bandwidth-এর থেকে হয়তো ১০× কম, কিন্তু latency-র পার্থক্য ~৫০×-এরও বেশি। এই “latency খারাপ কিন্তু bandwidth অপেক্ষাকৃত ভালো” ঘটনাটা কীভাবে সম্ভব, আগের লেসনগুলোর কোন ধারণা দিয়ে ব্যাখ্যা করবেন?
যুক্তি
১০× কম, কিন্তু latency-র পার্থক্য ~৫০×-এরও বেশি। এই “latency খারাপ কিন্তু bandwidth অপেক্ষাকৃত ভালো” ঘটনাটা কীভাবে সম্ভব, আগের লেসনগুলোর কোন ধারণা দিয়ে ব্যাখ্যা করবেন?কারণ latency আর bandwidth দুইটা স্বাধীন মাপ — latency বলে একটা একক request-এর উত্তর পেতে কত সময় লাগে, bandwidth বলে একসাথে অনেক request/বাইট চালালে প্রতি সেকেন্ডে মোট কত পরিমাণ ডেটা পার হয়। DRAM-এর ক্ষেত্রে digital-logic/memory-sram-dram লেসনের “page mode”-এর কথা মনে করুন — একবার একটা row activate হয়ে গেলে (যেটাই সবচেয়ে বেশি সময় নেয়), সেই একই row-এর ভেতরের একাধিক column পরপর, দ্রুত, pipeline করে পড়া যায়, প্রতিটার জন্য নতুন করে পুরো row-activate latency দিতে হয় না। তাই একটা একক, বিচ্ছিন্ন (isolated) DRAM access ধীর (পুরো ~200 cycle latency), কিন্তু ধারাবাহিক, বড় sequential transfer-এ সেই fixed row-activate cost অনেক বাইটের মধ্যে ভাগ হয়ে যায় — ফলে bandwidth তুলনামূলকভাবে ভালো থাকে। এটাই ব্যাখ্যা করে কেন sequential access latency-sensitive random access-এর চেয়ে এত বেশি কার্যকর — শুধু cache hit-miss-এর গল্প না, এই একই row-activate/page-mode যুক্তি সরাসরি প্রযোজ্য।
এরপর কী
আমরা এখন জানি hierarchy কেন আছে — speed/size/cost trade-off, আর locality of reference কেন এটাকে বাস্তবে কার্যকর করে। কিন্তু একটা গুরুত্বপূর্ণ প্রশ্ন এখনও অনুত্তরিত: cache যখন বলে “এই ঠিকানার ডেটা hit না miss”, সেটা কীভাবে এত দ্রুত জানে? একটা 32 KB cache-এ একটা 64-বিট ঠিকানার জন্য পুরো memory স্ক্যান করা তো অসম্ভব ধীর হতো।
পরের লেসনে (Cache Organization) আমরা দেখব ঠিক এই প্রশ্নের উত্তর — কীভাবে একটা বিশাল address space-কে একটা ছোট cache array-তে map করা হয় tag/index/offset বিভাজন দিয়ে, direct-mapped থেকে fully-associative পর্যন্ত পুরো spectrum, আর কেন set-associative design বাস্তবে সবচেয়ে বেশি ব্যবহৃত হয়।
আরও পড়ুন
- Computer Organization and Design (RISC-V Edition), Chapter 5 — David A. Patterson, John L. Hennessy · Memory hierarchy-র প্রামাণ্য আলোচনা — এই লেসনের কাঠামোর মূল উৎস
- Computer Architecture: A Quantitative Approach, Chapter 2 — John L. Hennessy, David A. Patterson · Memory wall আর locality-র quantitative বিশ্লেষণ
- What Every Programmer Should Know About Memory — Ulrich Drepper · Locality আর hierarchy-র ব্যবহারিক, গভীর প্রকৌশল বিবরণ
- Latency Numbers Every Programmer Should Know — Jeff Dean (এবং কমিউনিটি সংকলন) · এই লেসনের latency table-এর ধরনের একটা জনপ্রিয়, ব্যাপক-উদ্ধৃত সংকলন