Cache Policies — কাকে বিদায় করব, কখন লিখব, আর গড়ে কত সময় লাগে
Cache Policies — Replacement, Write Policy, and AMAT
Set পূর্ণ হলে কে যাবে (LRU/FIFO/random — সত্যিকারের LRU ব্যয়বহুল, তাই pseudo-LRU tree), আর write কখন memory পর্যন্ত পৌঁছাবে (write-through সরল কিন্তু bandwidth-ভারী, write-back দ্রুত কিন্তু dirty bit ও consistency জটিলতা আনে) — এই দুই সিদ্ধান্তই AMAT = hit_time + miss_rate × miss_penalty সূত্রে মিলে সিস্টেমের গড় গতি নির্ধারণ করে।
আগে এটা বুঝি
গত লেসনে আমরা দেখেছি একটা cache কীভাবে একটা address-কে দ্রুত hit বা miss-এ পরিণত করে — tag/index/offset বিভাজন দিয়ে, direct-mapped থেকে set-associative পর্যন্ত। কিন্তু দুইটা সিদ্ধান্ত ইচ্ছাকৃতভাবে ফাঁকা রেখে দিয়েছিলাম।
প্রথমটা: একটা N-way set-associative cache-এ, একটা set-এর সবগুলো way (N-টা) ইতিমধ্যে ভরা, আর একটা নতুন miss আসছে — নতুন line-টা জায়গা পাবে কীভাবে? কাউকে না কাউকে যেতে হবে। কাকে বিদায় করা হবে, সেই সিদ্ধান্তটাই replacement policy।
দ্বিতীয়টা: CPU যখন cache-এ কিছু লেখে (write করে), সেই নতুন মান কখন, কীভাবে নিচের memory স্তরে (DRAM) পৌঁছাবে? সাথে সাথে, নাকি পরে? এই সিদ্ধান্তটাই write policy।
দুটোই আলাদা প্রশ্ন, স্বাধীন সিদ্ধান্ত — একটা cache যেকোনো replacement policy-র সাথে যেকোনো write policy জোড়া লাগাতে পারে। কিন্তু দুটোই মিলে শেষ পর্যন্ত একটা একক প্রশ্নের উত্তর ঠিক করে, যেটা এই লেসনের শেষে আমরা একটা সূত্রে বাঁধব: গড়ে, একটা memory access-এ ঠিক কত সময় লাগে?
মূল ধারণা
Replacement Policy — set পূর্ণ হলে কে যাবে
যখনই associativity 1-এর বেশি (direct-mapped না), একটা set-এর একাধিক line-এর মধ্যে বাছাই করার প্রশ্ন আসে। লক্ষ্য: এমন একটা line বিদায় করা যেটা সবচেয়ে কম সম্ভাবনায় শীঘ্রই আবার লাগবে — যদি এটা ভুল হয়, নতুন miss তৈরি হবে অপ্রয়োজনে।
LRU — Least Recently Used
সবচেয়ে স্বজ্ঞাত পন্থা: যেই line সবচেয়ে বেশি সময় ধরে ব্যবহার হয়নি, তাকে বিদায় করো। এটা সরাসরি গত লেসনের temporal locality নীতির উপর বাজি ধরে — “সাম্প্রতিক ব্যবহৃত জিনিস আবার লাগবে” নীতির উল্টো দিক থেকে বলা: “দীর্ঘদিন অব্যবহৃত জিনিস সম্ভবত আর লাগবে না।”
সমস্যা: সত্যিকারের (exact) LRU ট্র্যাক করা ব্যয়বহুল। একটা N-way set-এ প্রতিটা access-এর পর N-টা line-এর সম্পূর্ণ ব্যবহারের ক্রম (কে সবচেয়ে সাম্প্রতিক, কে তার আগেরটা, …) আপডেট রাখতে হবে। একটা প্রচলিত hardware কৌশল — প্রতিটা জোড়া line-এর মধ্যে “কে বেশি সাম্প্রতিক” এই একটা করে বিট রাখা (pairwise comparison matrix):
Way সংখ্যা (N) | Exact LRU-র জন্য bit/set | Pseudo-LRU tree-র জন্য bit/set |
|---|---|---|
| 2 | 1 | 1 |
| 4 | 6 | 3 |
| 8 | 28 | 7 |
| 16 | 120 | 15 |
২-way-তে মাত্র ১ বিট লাগে (কে বেশি সাম্প্রতিক — একটা বাইনারি প্রশ্ন), তাই exact LRU সস্তা। কিন্তু ৮-way-তে ২৮ বিট per set লাগে, আর প্রতিটা access-এই সেই বিটগুলো আপডেট করতে হয় — বাস্তব cache-এ হাজার হাজার set থাকে, তাই এই খরচ দ্রুত বেড়ে যায়। ১৬-way-তে ১২০ বিট — সম্পূর্ণ অব্যবহারিক হয়ে ওঠে।
Pseudo-LRU — একটা tree দিয়ে আনুমানিক করা
বাস্তব hardware তাই সাধারণত exact LRU-র বদলে একটা আনুমানিক (approximate) সংস্করণ ব্যবহার করে — pseudo-LRU (PLRU)। ধারণা: N-টা way-কে একটা বাইনারি tree-তে সাজানো, প্রতিটা internal node-এ মাত্র ১-বিট — “এই node-এর নিচে বাম অর্ধেক নাকি ডান অর্ধেক বেশি সাম্প্রতিক ব্যবহৃত হয়েছে।” N-টা leaf-এর একটা বাইনারি tree-তে ঠিক N-1-টা internal node — তাই N-1 বিট per set।
bit0
┌───┴───┐
bit1 bit2
┌───┴──┐ ┌──┴───┐
bit3 bit4 bit5 bit6
┌─┴─┐ ┌─┴─┐┌─┴─┐ ┌─┴─┐
w0 w1 w2 w3 w4 w5 w6 w7
প্রতিটা bit বলে: "বাম subtree সাম্প্রতিক, নাকি ডান subtree"
Replacement-এর সময়: root থেকে শুরু করে প্রতিটা bit "কম সাম্প্রতিক" দিকে যাও,
leaf-এ পৌঁছালে সেই way-ই বিদায় হবে।Pseudo-LRU সবসময় ঠিক সেই line বেছে নেয় না যেটা প্রকৃতপক্ষে সবচেয়ে কম সাম্প্রতিক (কারণ এটা পুরো ক্রম না, শুধু একটা বাইনারি বিভাজন মনে রাখে) — কিন্তু বাস্তব hit rate-এ পার্থক্য প্রায়ই নগণ্য, আর hardware খরচ (N-1 বিট বনাম N(N-1)/2 বিট) বহুগুণ কম। এটা একটা ক্লাসিক ইঞ্জিনিয়ারিং trade-off: perfect-এর কাছাকাছি, কিন্তু সস্তা প্রায়ই perfect, কিন্তু ব্যয়বহুল-এর চেয়ে ভালো বাস্তব পছন্দ।
FIFO — সরল কিন্তু ব্যবহারের ধরন উপেক্ষা করে
FIFO (First-In, First-Out): যেই line সবচেয়ে আগে cache-এ ঢুকেছে, সে-ই আগে বের হবে — ব্যবহার হয়েছে কি না, সাম্প্রতিক কি না, কোনো কিছুই বিবেচনায় নেওয়া হয় না। Hardware সরল — শুধু একটা insertion-order pointer (round-robin counter) দরকার, \log_2(N) বিট per set — pseudo-LRU-র চেয়েও সস্তা।
কিন্তু এই সরলতার দাম: একটা line যেটা সবসময় ব্যবহার হচ্ছে (extremely hot) তবু শুধু পুরনো হওয়ার কারণে বিদায় হতে পারে, এমনকি পাশের একটা প্রায়-অব্যবহৃত line টিকে থাকতে পারে শুধু নতুন এসেছে বলে।
Random — বিস্ময়করভাবে প্রতিযোগী
সবচেয়ে সরল পন্থা: set-এর N-টা way-র মধ্যে থেকে এলোমেলোভাবে একটা বেছে বিদায় করা। কোনো state ট্র্যাক করার দরকার নেই — শুধু একটা random (বা pseudo-random) সংখ্যা generator, \log_2(N) বিট আউটপুট।
বিস্ময়করভাবে, random replacement-এর hit rate বাস্তব workload-এ প্রায়ই LRU-র খুব কাছাকাছি (১-৩% পয়েন্ট পার্থক্যের মধ্যে), বিশেষত উচ্চ-associativity cache-এ। কারণ: উচ্চ-associativity-তে “ভুল” line বিদায় করার সম্ভাব্য ক্ষতি সীমিত (এখনও N-1-টা অন্য line আছে যেগুলো hit দিতে পারে), আর random policy-র কোনো “predictable pattern” নেই যা adversarial access pattern দ্বারা exploit করা যায় (একটা নিরাপত্তা-সংক্রান্ত সুবিধা, security module-এ cache-timing attack প্রসঙ্গে প্রাসঙ্গিক)।
একটা তুলনা টেবিল
| Policy | Hardware খরচ | Hit rate (সাধারণ workload) | মূল দুর্বলতা |
|---|---|---|---|
| Random | ন্যূনতম (শুধু RNG) | ভালো, LRU-র কাছাকাছি | কখনো কখনো “hot” line ভুলবশত বিদায় |
| FIFO | কম (log2 N বিট, counter) | মাঝারি | ব্যবহারের ধরন সম্পূর্ণ উপেক্ষা করে, Belady’s anomaly-প্রবণ |
| Pseudo-LRU | মাঝারি (N-1 বিট, tree logic) | LRU-র খুব কাছাকাছি | সামান্য approximation error |
| Exact LRU | বেশি (N(N-1)/2 বিট, প্রতি access আপডেট) | সেরা বাস্তবসম্মত policy-গুলোর মধ্যে | উচ্চ-N-এ hardware খরচ অসহনীয় |
LRU-র একটা দুর্বলতা — Scan-resistance
LRU নিখুঁত না — একটা বাস্তব সমস্যা: যদি একটা প্রোগ্রাম হঠাৎ একবার একটা বিশাল, এক-বারের জন্য ব্যবহৃত ডেটাসেট scan করে (যেমন একটা বড় ফাইল সম্পূর্ণ পড়া, বা একটা এক-বারের bulk operation), সেই scan-এর প্রতিটা নতুন line “সবচেয়ে সাম্প্রতিক” হিসেবে চিহ্নিত হয় — এবং LRU-র নিয়ম অনুযায়ী আগের, সত্যিকারের “hot” (বারবার-ব্যবহৃত) line-গুলোকে বিদায় করে দেয় জায়গা করার জন্য। Scan শেষ হওয়ার পর, cache পুরোপুরি সেই এক-বার-ব্যবহৃত ডেটায় ভরে থাকে, আর আগের hot ডেটা হারিয়ে গেছে — এটাকে বলে cache pollution। এই সমস্যা সমাধানে কিছু বাস্তব সিস্টেম (হার্ডওয়্যার cache-এর চেয়ে বেশি database buffer pool ও software cache-এ দেখা যায়, যেমন PostgreSQL-এর buffer manager বা ZFS-এর ARC — Adaptive Replacement Cache) দুইটা আলাদা তালিকা রাখে — একটা “একবার ব্যবহৃত” আইটেমের জন্য, একটা “একাধিকবার ব্যবহৃত” আইটেমের জন্য — যাতে একটা এক-বারের scan পুরনো hot ডেটাকে সম্পূর্ণ উৎখাত করতে না পারে। হার্ডওয়্যার cache-এ pseudo-LRU-র সরলতার কারণে এই ধরনের সূক্ষ্ম সুরক্ষা কম দেখা যায়, কিন্তু software-এ (databases module-এ বিস্তারিত) এটা একটা প্রমাণিত, ব্যাপকভাবে ব্যবহৃত কৌশল।
Write Policy — লেখা কখন নিচে পৌঁছায়
Cache শুধু read না, write-ও সামলায়। CPU যখন একটা cache line-এর মধ্যে থাকা ডেটা বদলায়, সেই পরিবর্তন কখন memory (বা নিচের cache স্তর) পর্যন্ত পৌঁছাবে — এই প্রশ্নের দুইটা মৌলিক উত্তর।
Write-through — সাথে সাথে সব জায়গায়
প্রতিটা write সাথে সাথেই cache-এ, আর একই সাথে নিচের memory স্তরেও লেখা হয়।
সুবিধা: সরলতা। Cache আর memory কখনোই আলাদা হয় না — memory সবসময় সত্যিকারের, হালনাগাদ মান ধরে রাখে। এর মানে অন্য কোনো device (DMA, অন্য CPU core) যদি সরাসরি memory পড়ে, সবসময় সঠিক, সাম্প্রতিক মান পাবে — কোনো বাড়তি সমন্বয় (synchronization) ছাড়াই।
দাম: memory traffic। প্রতিটা write-ই নিচের, ধীর স্তর পর্যন্ত যেতে হয় — যদি একই ঠিকানায় বারবার লেখা হয় (temporal locality-র write সংস্করণ), প্রতিটা লেখাই আলাদা memory traffic তৈরি করে, cache থাকা সত্ত্বেও write-এর জন্য কোনো speed-up নেই।
Write-back — শুধু cache-এ, পরে নিচে
Write শুধু cache line-এ হয়; সেই line একটা “dirty” (নোংরা/অসংগত) বলে চিহ্নিত করা হয় (একটা বাড়তি bit — dirty bit)। নিচের memory স্তরে লেখা হয় শুধু তখনই যখন সেই line উৎখাত (evict) হয়।
সুবিধা: কম traffic, দ্রুত write। একই line-এ বারবার লেখা হলে (১০০০ বার ধরুন), সবগুলো লেখা cache-এই থাকে — শুধু যখন সেই line অবশেষে replacement policy-র কারণে বিদায় হয়, তখনই একটামাত্র write নিচের স্তরে যায়।
Write-through: ১০০০ বার লেখা → ১০০০ বার memory-তে ট্রাফিক
Write-back: ১০০০ বার লেখা → cache-এ ১০০০ বার (দ্রুত) + eviction-এ ১ বার memory-তে ট্রাফিক১০০০× কম memory traffic — শুধু access pattern-এ temporal locality থাকার কারণে, ঠিক এই module-এর মূল থিমেরই আরেকটা প্রয়োগ।
দাম: জটিলতা আর একটা বাস্তব consistency সমস্যা। Dirty bit ট্র্যাক করতে হয়। Eviction-এর সময় শুধু নতুন line আনা না, পুরনো dirty line-টা প্রথমে লিখে ফেলতে হয় (একটা বাড়তি ধাপ, “write-back” নামটাই সেখান থেকে)। আর সবচেয়ে গুরুত্বপূর্ণ — যতক্ষণ line dirty অবস্থায় cache-এ আছে, memory-তে থাকা মান পুরনো (stale)। কোনো অন্য device যদি সরাসরি memory পড়ে, সে ভুল, পুরনো মান পাবে।
Write-allocate বনাম No-write-allocate — write miss-এ কী হয়
এখনও একটা প্রশ্ন বাকি: যদি CPU এমন একটা ঠিকানায় লেখে যেটা cache-এ নেই (write miss), তখন কী হবে?
- Write-allocate: প্রথমে সেই line-টা cache-এ load করা হয় (যেন এটা একটা read miss), তারপর write সেই cache line-এ প্রয়োগ হয়। যুক্তি: যেই ঠিকানায় এইমাত্র লেখা হলো, spatial/temporal locality অনুযায়ী সেটা শীঘ্রই আবার লাগতে পারে (read বা write দুটোই) — তাই cache-এ রাখাই লাভজনক।
- No-write-allocate: লেখাটা সরাসরি নিচের memory স্তরে পাঠানো হয়, cache-এ কোনো line load করা হয় না।
সাধারণ pairing (নির্বিচার না — একটা যৌক্তিক মিল):
| জোড়া | যুক্তি |
|---|---|
| Write-back + write-allocate | যেহেতু write-back বারবার একই line-এ লেখা সস্তা করে তোলে, একটা নতুন write-miss line-কে cache-এ রাখাই লাভজনক — পরের write-গুলো cache-এই থাকবে |
| Write-through + no-write-allocate | যেহেতু write-through-এ প্রতিটা write এমনিতেই memory পর্যন্ত যায়, নতুন line cache-এ রাখার বাড়তি সুবিধা কম — শুধু আরেকটা line load করার খরচ যোগ হয় |
এই দুইটা pairing-ই বাস্তবে সবচেয়ে বেশি দেখা যায়, কিন্তু চারটা সমন্বয়ই (write-through+write-allocate, write-back+no-write-allocate) প্রযুক্তিগতভাবে সম্ভব — শুধু কম প্রচলিত, কারণ তাদের যুক্তিসঙ্গত সুবিধা কম স্পষ্ট।
ভেতরে কী ঘটছে
AMAT — Average Memory Access Time
এখন পর্যন্ত আমরা hit-এর গতি (~4 cycle L1-এ) আর miss-এর গতি (নিচের স্তরে যাওয়ার খরচ) আলাদা করে দেখেছি। কিন্তু একটা প্রোগ্রামের প্রকৃত, গড় performance এই দুইটা একসাথে মিশিয়ে নির্ধারণ করে — কারণ কিছু access hit হয়, কিছু miss হয়, আর দুটোর অনুপাতই (hit rate) ঠিক করে গড়টা কোন দিকে ঝুঁকবে।
যেখানে t_hit = hit হলে যে সময় লাগে (cache-এর নিজের access time), m_rate = miss rate (miss হওয়া access-এর ভগ্নাংশ, 0 থেকে 1), আর t_penalty = miss হলে বাড়তি যে সময় লাগে (নিচের স্তর থেকে ডেটা আনতে)।
স্বজ্ঞা: প্রতিটা access-ই অন্তত t_hit সময় নেয় (cache নিজেই check করতে হবে, hit হোক বা miss)। তার উপর, যেই ভগ্নাংশ (m_rate) miss হয়, তাদের জন্য বাড়তি t_penalty যোগ হয়। এটা একটা weighted average — hit path আর miss path-এর, miss rate দিয়ে ওজন করা।
একটা সরল সংখ্যাগত উদাহরণ — সংবেদনশীলতা দেখা
ধরুন t_hit = 4 cycle (L1), আর সরলতার জন্য ধরুন miss হলে সরাসরি DRAM পর্যন্ত যেতে হয় (t_penalty = 200 cycle — L2/L3 আপাতত বাদ দিয়ে, শুধু গল্পটা সরল রাখতে)।
| Miss rate | AMAT গণনা | ফলাফল |
|---|---|---|
1% (0.01) | 4 + 0.01 × 200 = 4 + 2 | 6.0 cycle |
5% (0.05) | 4 + 0.05 × 200 = 4 + 10 | 14.0 cycle |
10% (0.10) | 4 + 0.10 × 200 = 4 + 20 | 24.0 cycle |
20% (0.20) | 4 + 0.20 × 200 = 4 + 40 | 44.0 cycle |
Multi-level AMAT — পুরো hierarchy জুড়ে
বাস্তবে miss সরাসরি DRAM-এ যায় না — L1 miss হলে L2-তে যায়, L2 miss হলে L3-তে, L3 miss হলে তবেই DRAM-এ। প্রতিটা স্তরের নিজের hit time আছে, আর নিজের (সেই স্তর পর্যন্ত পৌঁছানো access-গুলোর মধ্যে) miss rate — একে বলে local miss rate। AMAT তখন recursively গণনা করা হয়, নিচের স্তর থেকে উপরে:
অর্থাৎ একটা স্তরের “miss penalty” আসলে তার নিচের স্তরের সম্পূর্ণ AMAT — কারণ সেই নিচের স্তরও নিজে hit/miss মিশ্রণ নিয়ে কাজ করে।
সংখ্যায়: লেসন ৭-এর latency table ব্যবহার করে (t_hit: L1=4, L2=12, L3=40, DRAM=200 cycle), আর ধরে নিয়ে local miss rate — L1: 5%, L2: 30%, L3: 20%:
ধাপ ১ — সবচেয়ে নিচের স্তর থেকে শুরু (DRAM-এর নিজের কোনো miss rate নেই — এটাই শেষ স্তর ধরছি):
AMAT_L3 = t_hit_L3 + m_rate_L3 × t_DRAM
= 40 + 0.20 × 200
= 40 + 40
= 80 cycle
ধাপ ২ — L2, যার miss penalty = AMAT_L3:
AMAT_L2 = t_hit_L2 + m_rate_L2 × AMAT_L3
= 12 + 0.30 × 80
= 12 + 24
= 36 cycle
ধাপ ৩ — L1, যার miss penalty = AMAT_L2:
AMAT_L1 = t_hit_L1 + m_rate_L1 × AMAT_L2
= 4 + 0.05 × 36
= 4 + 1.8
= 5.8 cycleচূড়ান্ত AMAT ≈ ৫.৮ cycle — L1-এর নিজের hit time-এর (৪ cycle) খুব কাছাকাছি, যদিও ডেটার একটা অংশ আসলে DRAM পর্যন্ত গিয়ে ফিরে এসেছে। এটাই hierarchy-র প্রতিশ্রুতির সংখ্যাগত প্রমাণ (লেসন ৭-এর hood section-এর informal হিসাবের একটা কঠোর সংস্করণ)।
Local বনাম global miss rate
local miss rate বলে “এই স্তর পর্যন্ত যে access পৌঁছেছে, তার কত শতাংশ miss হলো”। global miss rate বলে “মূল, সব access-এর মধ্যে কত শতাংশ শেষ পর্যন্ত এই স্তরেও miss করল”:
L1 global miss rate = L1 local miss rate = 5%
L2 global miss rate = 5% × 30% = 1.5% (মূল access-এর মাত্র 1.5% L2 পর্যন্ত গিয়ে সেখানেও miss করে)
L3 global miss rate = 5% × 30% × 20% = 0.3% (মাত্র 0.3% access DRAM পর্যন্ত যায়)এই পার্থক্যটা গুরুত্বপূর্ণ — L2-এর “৩০% miss rate” শুনতে খারাপ লাগতে পারে, কিন্তু সেটা শুধু সেই অল্প কয়েকটা (মূল access-এর ৫%) access-এর মধ্যে ৩০%, যেগুলো ইতিমধ্যে L1-এ miss করেছে। Global miss rate (১.৫%) প্রকৃত ছবিটা দেখায় — সামগ্রিকভাবে খুব কম access-ই আসলে L2 পর্যন্ত গিয়ে আবার miss করছে।
সংবেদনশীলতা আবার — এবার multi-level-এ
যদি শুধু L1-এর local miss rate 5% থেকে 8%-এ বাড়ে (L2/L3 অপরিবর্তিত, AMAT_L2 = 36 স্থির ধরে):
5.8 থেকে 6.88 cycle — প্রায় ১৮.৬% বৃদ্ধি, শুধু L1 miss rate-এ ৩ percentage point (আপেক্ষিকভাবে ৬০%) পরিবর্তনের জন্য। এটাই আবার সেই একই amplification নীতি — যেহেতু miss penalty (৩৬ cycle, AMAT_L2) hit time-এর (৪ cycle) চেয়ে ৯× বড়, miss rate-এর যেকোনো পরিবর্তন বড় করে বিবর্ধিত (amplified) হয়ে AMAT-এ প্রতিফলিত হয়।
উদাহরণ
সংখ্যায় সম্পূর্ণ ট্রেস — একটা 4-way set, তিনটা policy
ধরুন একটা 4-way set-এ (way 0-3, সবগুলো খালি শুরুতে) নিচের ক্রমে address-এর reference আসছে (letter দিয়ে ভিন্ন address বোঝাচ্ছি, একই set-এ map হয়): A, B, C, D, A, E, A, B।
LRU ট্রেস:
| Access | Set অবস্থা (সবচেয়ে সাম্প্রতিক → সবচেয়ে পুরনো) | Hit/Miss | বিদায় (যদি লাগে) |
|---|---|---|---|
| A | A | Miss (compulsory) | — |
| B | B, A | Miss | — |
| C | C, B, A | Miss | — |
| D | D, C, B, A | Miss (এখন set পূর্ণ) | — |
| A | A, D, C, B | Hit | — |
| E | E, A, D, C | Miss | B বিদায় (সবচেয়ে পুরনো) |
| A | A, E, D, C | Hit | — |
| B | B, A, E, D | Miss | C বিদায় (সবচেয়ে পুরনো) |
মোট: ৬টা miss, ২টা hit (hit rate = 2/8 = 25%)।
FIFO ট্রেস (একই reference sequence, কিন্তু বিদায় insertion-order অনুযায়ী, ব্যবহার-ক্রম না):
| Access | Set অবস্থা (insertion order) | Hit/Miss | বিদায় |
|---|---|---|---|
| A | A | Miss | — |
| B | A, B | Miss | — |
| C | A, B, C | Miss | — |
| D | A, B, C, D | Miss (পূর্ণ) | — |
| A | A, B, C, D | Hit (এখনও ভেতরে আছে) | — |
| E | B, C, D, E | Miss | A বিদায় (সবচেয়ে আগে ঢুকেছিল, যদিও এইমাত্র ব্যবহার হলো!) |
| A | C, D, E, A | Miss (A আবার আনতে হলো) | B বিদায় |
| B | D, E, A, B | Miss | C বিদায় |
মোট: ৭টা miss, ১টা hit (hit rate = 1/8 = 12.5%) — এই নির্দিষ্ট sequence-এ FIFO LRU-র চেয়ে খারাপ করল, কারণ এটা A-কে বিদায় করল ঠিক তার পরেই আবার ব্যবহার হওয়া সত্ত্বেও, শুধু এটা সবচেয়ে আগে ঢুকেছিল বলে — উপরের Belady’s anomaly Callout-এ উল্লেখিত সমস্যারই একটা ছোট প্রদর্শনী।
Write policy ট্রেস — dirty bit বাস্তবে
ধরুন একই cache line-এ (address X) পরপর ৩টা write হচ্ছে, তারপর সেই line উৎখাত হচ্ছে (অন্য কিছু cache-এ আনার জন্য জায়গা করতে)।
Write-through:
write X=1 → cache-এ X=1, memory-তেও সাথে সাথে X=1 লেখা হলো (memory traffic: ১)
write X=2 → cache-এ X=2, memory-তেও সাথে সাথে X=2 লেখা হলো (memory traffic: ২)
write X=3 → cache-এ X=3, memory-তেও সাথে সাথে X=3 লেখা হলো (memory traffic: ৩)
eviction → memory ইতিমধ্যে হালনাগাদ, কিছু করার নেই (মোট memory traffic: ৩)Write-back:
write X=1 → cache-এ X=1, dirty=1, memory অপরিবর্তিত (এখনও পুরনো মান) (memory traffic: ০)
write X=2 → cache-এ X=2, dirty=1 (আগে থেকেই), memory অপরিবর্তিত (memory traffic: ০)
write X=3 → cache-এ X=3, dirty=1 (আগে থেকেই), memory অপরিবর্তিত (memory traffic: ০)
eviction → dirty=1 দেখে memory-তে X=3 লেখা হলো (এই প্রথমবার) (মোট memory traffic: ১)৩টা লেখায় write-through-এ ৩-বার memory traffic, write-back-এ মাত্র ১-বার — ৩× কম, আর যদি ৩-এর বদলে ১০০০-বার লেখা হতো, পার্থক্যটা হতো ১০০০×। লক্ষ্য করুন — মাঝের দুইটা write (X=2 লেখার পর X=3 লেখা) write-back-এ পুরোপুরি “নষ্ট” হয়ে গেল memory-র দৃষ্টিকোণ থেকে — memory কখনো X=2 দেখলই না, সরাসরি 1 থেকে 3-এ গেল। এটাই write-back-এর efficiency-র উৎস: শুধু চূড়ান্ত মানটাই memory পর্যন্ত পাঠানোর দরকার, মাঝের প্রতিটা পরিবর্তন না।
নিজে চালিয়ে দেখুন
Replacement policy simulator — একটা memory trace-এ LRU/FIFO/Random তুলনা করুন
import random
from collections import OrderedDict
def simulate_lru(trace, ways):
cache = OrderedDict()
hits = 0
for addr in trace:
if addr in cache:
hits += 1
cache.move_to_end(addr) # সাম্প্রতিক ব্যবহৃত হিসেবে চিহ্নিত
else:
if len(cache) \>= ways:
cache.popitem(last=False) # সবচেয়ে পুরনো (least recently used) বিদায়
cache[addr] = True
return hits / len(trace)
def simulate_fifo(trace, ways):
cache = OrderedDict()
hits = 0
for addr in trace:
if addr in cache:
hits += 1 # move_to_end করা হয় না — insertion order অপরিবর্তিত
else:
if len(cache) \>= ways:
cache.popitem(last=False) # সবচেয়ে আগে ঢোকা বিদায়
cache[addr] = True
return hits / len(trace)
def simulate_random(trace, ways, seed=42):
rng = random.Random(seed)
cache = []
hits = 0
for addr in trace:
if addr in cache:
hits += 1
else:
if len(cache) \>= ways:
victim = rng.randrange(len(cache))
cache.pop(victim)
cache.append(addr)
return hits / len(trace)
# একটা locality-সহ synthetic trace — কিছু address বারবার, কিছু নতুন
random.seed(1)
trace = []
working_set = list(range(6)) # cache-এর চেয়ে বড় working set (ways=4 নিচে)
for _ in range(2000):
if random.random() \< 0.85:
trace.append(random.choice(working_set[:4])) # temporal locality — hot subset
else:
trace.append(random.choice(working_set)) # মাঝেমধ্যে ঠান্ডা অংশ
for ways in [2, 4, 6]:
lru_hr = simulate_lru(trace, ways)
fifo_hr = simulate_fifo(trace, ways)
rand_hr = simulate_random(trace, ways)
print(f"ways={ways}: LRU={lru_hr:.3f} FIFO={fifo_hr:.3f} Random={rand_hr:.3f}")প্রত্যাশিত ফলাফলের ধরন:
ways=2: LRU=0.612 FIFO=0.545 Random=0.571
ways=4: LRU=0.891 FIFO=0.834 Random=0.856
ways=6: LRU=0.947 FIFO=0.940 Random=0.938লক্ষ্য করুন ways=6-এ (যেখানে পুরো 6-উপাদানের working set-ই cache-এ আঁটে) তিনটা policy-র hit rate প্রায় সমান — যখন conflict-ই নেই, policy কোনো পার্থক্য তৈরি করে না। কিন্তু ways=2-এ (যেখানে associativity সীমিত, বাছাই গুরুত্বপূর্ণ) LRU স্পষ্টভাবে এগিয়ে — এটাই এই লেসনের তুলনা টেবিলের একটা সরাসরি, পরিমাপযোগ্য যাচাই।
একই access trace-এ ভিন্ন replacement policy ভিন্ন hit rate দেয় — এই লেসনের তাত্ত্বিক তুলনা টেবিলটা বাস্তব সংখ্যায় যাচাই করা যায়।
নিজে বানান
AMAT Calculator — hit rate বদলালে performance-এর প্রভাব দেখুন
- প্রতিটা স্তরের hit_time আর local miss_rate ইনপুট নিন (list of tuples, সবচেয়ে উপরের স্তর থেকে)
- সবচেয়ে নিচের স্তর থেকে উপরের দিকে recursively AMAT গণনা করুন
- একটা নির্দিষ্ট স্তরের miss rate সামান্য বদলে (যেমন ±2 percentage point) নতুন AMAT আর শতাংশ পরিবর্তন রিপোর্ট করুন
- একটা গ্রাফ-জাতীয় টেক্সট আউটপুট বানান যা miss rate বনাম AMAT দেখায়, 0% থেকে 30% পর্যন্ত
def compute_amat(levels, final_penalty):
"""levels: [(hit_time, miss_rate), ...] উপর থেকে নিচে। final_penalty: শেষ স্তরের নিচের (যেমন DRAM) সময়।"""
amat = final_penalty
for hit_time, miss_rate in reversed(levels):
amat = hit_time + miss_rate * amat
return amat
levels = [
(4, 0.05), # L1
(12, 0.30), # L2
(40, 0.20), # L3
]
dram = 200
base_amat = compute_amat(levels, dram)
print(f"বেস AMAT: {base_amat:.2f} cycle")
# L1 miss rate বদলে সংবেদনশীলতা দেখুন
for new_l1_rate in [0.03, 0.05, 0.08, 0.12]:
modified = [(4, new_l1_rate), (12, 0.30), (40, 0.20)]
amat = compute_amat(modified, dram)
pct_change = (amat - base_amat) / base_amat * 100
print(f"L1 miss_rate={new_l1_rate:.0%} → AMAT={amat:.2f} cycle ({pct_change:+.1f}%)")প্রত্যাশিত আউটপুট:
বেস AMAT: 5.80 cycle
L1 miss_rate=3% → AMAT=5.08 cycle (-12.4%)
L1 miss_rate=5% → AMAT=5.80 cycle (+0.0%)
L1 miss_rate=8% → AMAT=6.88 cycle (+18.6%)
L1 miss_rate=12% → AMAT=8.32 cycle (+43.4%)এই টেবিলটাই এই লেসনের কেন্দ্রীয় বার্তার একটা নিজ-হাতে-যাচাই করা সংস্করণ — L1 miss rate ৫% থেকে ১২%-এ (২.৪× বৃদ্ধি) গেলে AMAT প্রায় ৪৩% বেড়ে যায়, শুধুমাত্র সবচেয়ে উপরের স্তরের একটা ছোট পরিবর্তনের কারণে — কারণ সেই পরিবর্তন নিচের প্রতিটা স্তরের বিশাল miss penalty দিয়ে বিবর্ধিত হয়।
বাস্তব সিস্টেমে
বাস্তব সিস্টেমে cache policy
১. আধুনিক CPU-র বাস্তব replacement policy
Intel এবং AMD-র বেশিরভাগ আধুনিক L2/L3 cache pseudo-LRU-র বিভিন্ন সংস্করণ ব্যবহার করে (কিছু নতুন ডিজাইনে আরও পরিমার্জিত “adaptive” policy, যা access pattern দেখে LRU-সদৃশ আর scan-resistant আচরণের মধ্যে পরিবর্তিত হয়)। এই লেসনের N-1-বিট tree সরলীকৃত সংস্করণ, বাস্তব chip-এ প্রায়ই আরও সূক্ষ্ম variant ব্যবহৃত হয়, কিন্তু মূল নীতি (exact LRU-র সম্পূর্ণ state ছাড়াই আনুমানিক করা) একই।
২. প্রায় সব আধুনিক CPU cache write-back ব্যবহার করে
L1/L2/L3 — প্রায় সবগুলোই আধুনিক CPU-তে write-back + write-allocate। কারণ memory bandwidth সবসময় একটা মূল্যবান সম্পদ, আর write-back-এর traffic সাশ্রয় (এই লেসনের ১০০০× উদাহরণের মতো) সামগ্রিক performance-এ বড় প্রভাব ফেলে।
৩. Write buffer ও write-combining — write-এর latency লুকানো ও ব্যাচ করা
কিছু ডিজাইনে (বা write-back-এর eviction-এর সময়) একটা ছোট write buffer ব্যবহার করা হয় — CPU-কে memory write সম্পূর্ণ হওয়ার জন্য stall না করিয়ে, লেখাটা একটা সারিতে (queue) রেখে CPU পরের instruction চালিয়ে যায়। এটা write policy-র দাম আংশিকভাবে লুকিয়ে ফেলে, hardware জটিলতার বিনিময়ে। একটা সম্পর্কিত কৌশল — write-combining: যদি write buffer-এ একাধিক ছোট write একই cache-line-প্রস্থের region-এর মধ্যে জমা হয় (যেমন একটা 4-বাইট write তারপর তার পাশের আরেকটা 4-বাইট write), hardware সেগুলোকে একটা একক, বড় memory transaction-এ মিশিয়ে (combine) ফেলে নিচের স্তরে পাঠানোর আগে — অনেকটা এই লেসনের write-back উদাহরণেরই একটা সম্প্রসারণ, যেখানে শুধু “চূড়ান্ত মান” না, “সংলগ্ন ছোট write-গুলো একসাথে” পাঠানো হয়। GPU driver ও high-performance memory-mapped I/O-তে এটা ব্যাপকভাবে ব্যবহৃত, কারণ সেখানে ছোট, ঘনঘন write bandwidth-এর বড় অপচয় ঘটাতে পারে।
৪. OS page replacement — একই সমস্যা, ভিন্ন স্কেলে
operating-systems module-এ (Level 4) দেখবেন OS-এর virtual memory system একদম এই লেসনের একই সমস্যার মুখোমুখি হয় — physical RAM পূর্ণ হলে কোন page evict হবে (swap-এ পাঠানো হবে)। যেহেতু exact LRU সেখানেও ব্যয়বহুল (কোটি কোটি page-এর জন্য), OS প্রায়ই একটা approximation ব্যবহার করে যার নাম clock algorithm (second-chance) — এই লেসনের pseudo-LRU-র philosophical চাচাতো ভাই: সস্তা, কিন্তু LRU-র মূল স্বজ্ঞা ধরে রাখার চেষ্টা করে।
সংক্ষেপে কীভাবে কাজ করে: প্রতিটা page-এর একটা মাত্র reference bit থাকে (access হলে 1 হয়ে যায়)। Page-গুলো একটা বৃত্তাকার (circular) তালিকায় সাজানো, একটা “hand” (কাঁটা) ঘুরতে থাকে। Eviction দরকার হলে hand বর্তমান page-এ দেখে — bit 0 হলে সেটাই evict হয়; bit 1 হলে সেটাকে 0 করে দিয়ে (একটা “দ্বিতীয় সুযোগ” — second-chance) hand পরের page-এ চলে যায়। এভাবে সাম্প্রতিক-ব্যবহৃত page কখনো সাথে সাথে evict হয় না (অন্তত একবার “সুযোগ” পায়), কিন্তু পূর্ণ ব্যবহারের ক্রম ট্র্যাক করার (exact LRU-র মতো) কোনো খরচ ছাড়াই — মাত্র ১ বিট per page, এই লেসনের ৮-way pseudo-LRU-র ৭ বিট per set-এর সাথে তুলনীয় ধারণাগত সরলীকরণ, শুধু ভিন্ন স্কেলে (per-page বনাম per-set) প্রয়োগ করা।
৫. Redis ও অন্যান্য in-memory system-এ software LRU
Redis-এর মতো key-value store maxmemory-policy allkeys-lru সেটিং সমর্থন করে — hardware cache না হলেও একই মূলনীতি: memory ভরে গেলে সবচেয়ে কম-সাম্প্রতিক-ব্যবহৃত key বিদায় করা। এখানে exact LRU ট্র্যাক করা তুলনামূলক সহজ (software-এ, hardware-এর মতো প্রতি-cycle বাধ্যবাধকতা নেই), তাই Redis প্রায়ই একটা approximated-LRU ব্যবহার করে (র্যান্ডম sample-এর মধ্যে সবচেয়ে পুরনো বাছাই) — গতি আর নির্ভুলতার মধ্যে আরেকটা বাস্তব trade-off।
৬. Database write-ahead log — write policy-র একটা দূরবর্তী চাচাতো ভাই
Database-এ write-ahead logging (WAL) এই লেসনের write-through-এর একটা দর্শনগত প্রতিধ্বনি — durability নিশ্চিত করতে প্রতিটা পরিবর্তন প্রথমে একটা লগে (ধীর কিন্তু নির্ভরযোগ্য storage-এ) লেখা হয়, তারপর actual data page-এ (যেটা মূলত একটা write-back-ধরনের buffer pool-এ থাকে, লেসন ৭-এর “বাস্তব সিস্টেমে” অংশে উল্লেখিত)। databases module-এ এই trade-off বিস্তারিত আসবে।
৭. Cache-timing attack — random replacement-এর নিরাপত্তা সুবিধা
security module-এ দেখবেন predictable cache behavior (যেমন deterministic LRU) কখনো কখনো side-channel attack-এ ব্যবহৃত হতে পারে — আক্রমণকারী cache-এর আচরণ পর্যবেক্ষণ করে গোপন তথ্য (যেমন encryption key) সম্পর্কে অনুমান করতে পারে। এই কারণে কিছু নিরাপত্তা-সচেতন design ইচ্ছাকৃতভাবে randomized replacement বা randomized cache indexing ব্যবহার করে predictability কমাতে — এই লেসনের “random surprisingly competitive” পর্যবেক্ষণটা তখন শুধু performance না, নিরাপত্তার প্রশ্নও হয়ে ওঠে।
৮. Compiler ও profiler-এর AMAT-সচেতন optimization
Profiling টুল (perf, VTune) সরাসরি hit/miss counter মাপে প্রতিটা cache স্তরে, যেখান থেকে বাস্তব AMAT গণনা করা যায় — advanced-architecture module-এ (Level 11) এই measurement পদ্ধতি বিস্তারিত শিখবেন, ঠিক এই লেসনের সূত্র ব্যবহার করে বাস্তব প্রোগ্রামের bottleneck খুঁজে বের করা।
যে ভুলগুলো সবাই করে
“LRU-ই তাত্ত্বিকভাবে সবচেয়ে ভালো সম্ভব replacement policy”
LRU একটা চমৎকার practical heuristic (temporal locality-র উপর ভিত্তি করে), কিন্তু তাত্ত্বিকভাবে optimal না। সত্যিকারের optimal policy — Bélády’s OPT algorithm — ভবিষ্যতের access pattern জানার উপর নির্ভর করে (“যেটা সবচেয়ে দেরিতে আবার লাগবে সেটা বিদায় করো”), যেটা বাস্তব hardware-এ অসম্ভব। LRU শুধু এই অসম্ভব আদর্শের একটা ব্যবহারিক, বাস্তবায়নযোগ্য আনুমানিক সংস্করণ — সেরা বাস্তবসম্মত পছন্দ, সেরা তাত্ত্বিক পছন্দ না।
“Write-back সবসময় write-through-এর চেয়ে ভালো — তাই write-through আর ব্যবহার হয় না”
Write-back memory traffic-এ ভালো, কিন্তু এর দাম আছে — জটিলতা (dirty bit ট্র্যাকিং), আর সবচেয়ে গুরুত্বপূর্ণ, multi-core বা DMA পরিস্থিতিতে consistency সমস্যা। Write-through-এর সরলতা এখনও মূল্যবান জায়গায় — যেখানে immediate consistency জরুরি (যেমন কিছু I/O-mapped memory region, বা memory-mapped device register, যেখানে “লেখা মানেই তৎক্ষণাৎ device দেখবে” নিশ্চিত করা জরুরি — সেখানে write-back-এর delay আসলে একটা bug তৈরি করবে)। তাই আধুনিক system-ও নির্দিষ্ট memory region-এর জন্য write-through (বা “uncached”) mode বেছে নেয়, শুধু general-purpose data cache-এ write-back প্রাধান্য পায়।
“AMAT সূত্র শুধু একটা একক cache স্তরের জন্য প্রযোজ্য”
AMAT সূত্র recursively যেকোনো গভীরতার hierarchy-তে প্রয়োগযোগ্য — এই লেসনের multi-level উদাহরণেই দেখানো হয়েছে, যেখানে একটা স্তরের “miss penalty” আসলে তার নিচের স্তরের সম্পূর্ণ AMAT (যেটা নিজেই তার নিচের স্তরের AMAT-এর উপর নির্ভর করে)। সরল একক-স্তর version (hit_time + miss_rate × miss_penalty, যেখানে penalty একটা constant) শুধু একটা সরলীকরণ, শেখার জন্য সুবিধাজনক — বাস্তব সিস্টেম বিশ্লেষণে পুরো recursive সংস্করণ প্রয়োজন।
বুঝেছেন কি না দেখুন
1একটা 4-way set-এ exact LRU ট্র্যাক করতে কত বিট per set লাগে (pairwise matrix পদ্ধতিতে)? Pseudo-LRU tree-তে কত বিট লাগে?
স্মরণ
4-way set-এ exact LRU ট্র্যাক করতে কত বিট per set লাগে (pairwise matrix পদ্ধতিতে)? Pseudo-LRU tree-তে কত বিট লাগে?Exact LRU: N(N-1)/2 = 4×3/2 = 6 বিট। Pseudo-LRU: N-1 = 3 বিট। অর্থাৎ pseudo-LRU exact LRU-র অর্ধেক বিট ব্যবহার করে এই আকারে — associativity যত বাড়ে এই পার্থক্য তত বড় হয় (৮-way-তে ২৮ বনাম ৭, প্রায় ৪× পার্থক্য)।
2FIFO policy কখনো কখনো একটা “hot” (বারবার ব্যবহৃত) line বিদায় করে দেয়, যেখানে LRU সেটা করবে না। কেন?
যুক্তি
FIFO শুধু কখন cache-এ ঢুকেছিল সেটা ট্র্যাক করে, কখন সর্বশেষ ব্যবহার হয়েছিল সেটা না। একটা line অনেক আগে ঢুকে থাকতে পারে কিন্তু এখনও প্রতি কয়েক access-এই ব্যবহার হতে পারে (hot) — FIFO তবুও তাকে বিদায় করবে শুধু “সবচেয়ে পুরনো ঢোকা” হওয়ার কারণে, কারণ FIFO ব্যবহারের প্যাটার্নকে সম্পূর্ণ উপেক্ষা করে। LRU এই সমস্যা এড়ায় কারণ এটা সরাসরি সাম্প্রতিক-ব্যবহার ট্র্যাক করে, insertion-order না। এই লেসনের worked example-এ A ঠিক এই কারণে FIFO-তে ভুলভাবে বিদায় হয়েছিল, এইমাত্র hit হওয়া সত্ত্বেও।
3একটা L1 cache, t_hit = 4 cycle, miss_rate = 4%, আর miss হলে সরাসরি DRAM-এ যায় (t_penalty = 200 cycle)। AMAT কত? এখন যদি একজন ইঞ্জিনিয়ার associativity বাড়িয়ে miss_rate-কে 2%-এ নামান (একই t_hit বজায় রেখে), নতুন AMAT কত, আর শতাংশ উন্নতি কত?
প্রয়োগ
t_hit = 4 cycle, miss_rate = 4%, আর miss হলে সরাসরি DRAM-এ যায় (t_penalty = 200 cycle)। AMAT কত? এখন যদি একজন ইঞ্জিনিয়ার associativity বাড়িয়ে miss_rate-কে 2%-এ নামান (একই t_hit বজায় রেখে), নতুন AMAT কত, আর শতাংশ উন্নতি কত?প্রথম AMAT = 4 + 0.04 × 200 = 4 + 8 = 12 cycle। নতুন AMAT = 4 + 0.02 × 200 = 4 + 4 = 8 cycle। উন্নতি = (12-8)/12 = 33.3% — শুধু miss rate অর্ধেক করার মাধ্যমে AMAT-এ প্রায় এক-তৃতীয়াংশ উন্নতি, বিশাল miss penalty-র কারণে।
4একটা cache line-এ একই session-এ 10,000-বার write হয়, তারপর evict হয়। Write-through-এ কত memory write ঘটবে? Write-back-এ কত? Traffic reduction অনুপাত কত?
প্রয়োগ
10,000-বার write হয়, তারপর evict হয়। Write-through-এ কত memory write ঘটবে? Write-back-এ কত? Traffic reduction অনুপাত কত?Write-through: প্রতিটা লেখাই সাথে সাথে memory-তে যায়, তাই 10,000-বার memory write। Write-back: শুধু cache line-এ 10,000-বার লেখা হয় (dirty bit set থাকে, কিন্তু memory অপরিবর্তিত থাকে), আর eviction-এর সময় মাত্র ১-বার memory-তে চূড়ান্ত মান লেখা হয়। Traffic reduction: 10,000× — এটাই দেখায় কেন high-write, high-locality workload-এ write-back-এর সুবিধা এত বিশাল।
5একজন সহপাঠী বলছেন — “write-back cache-এ dirty bit থাকলে memory কখনো ভুল মান দেখায় না, কারণ eventually লেখা হয়েই যায়।” এই দাবিতে কোন গুরুত্বপূর্ণ সময়-সংক্রান্ত (temporal) ফাঁক আছে, আর সেটা কোন বাস্তব পরিস্থিতিতে সমস্যা তৈরি করে?
যুক্তি
“Eventually” শব্দটাই সমস্যা — dirty line eviction পর্যন্ত memory-তে পুরনো মান থেকে যায়, আর সেই সময়ের মধ্যে যদি অন্য কোনো observer (অন্য CPU core যার নিজস্ব cache আছে, একটা DMA device যা সরাসরি memory পড়ে, বা memory-mapped I/O) সেই ঠিকানা পড়ে, তারা stale (পুরনো) মান পাবে — eviction হওয়ার আগ পর্যন্ত সেটা “ভুল” থেকেই যায়, “eventually ঠিক হয়ে যাবে” সেই মুহূর্তের জন্য কোনো সান্ত্বনা না। এটাই multi-core cache coherence (MESI protocol, Level 11) আর distributed system consistency (Level 9) সমস্যার মূল বীজ — একাধিক জায়গায় একই ডেটার একাধিক কপি থাকলে, “কখন কোন কপি সত্যি” এই প্রশ্নের একটা স্পষ্ট প্রোটোকল দরকার, শুধু “eventually ঠিক হবে” যথেষ্ট না।
6একটা embedded system ডিজাইন করছেন যেখানে একটা sensor সরাসরি একটা নির্দিষ্ট memory ঠিকানায় (memory-mapped register) ক্রমাগত নতুন মান লিখছে, আর CPU সেটা পড়ে সিদ্ধান্ত নেয়। CPU যদি সেই ঠিকানাকে write-back cache-এ রাখে, কী সমস্যা হতে পারে? কী নীতি (এই দুই লেসনের যেকোনো ধারণা ব্যবহার করে) এই ঠিকানার জন্য উপযুক্ত হবে?
ডিজাইন
সমস্যা: এই সমস্যাটা আসলে dirty-bit/consistency সমস্যার একটা আয়না-প্রতিফলন — sensor memory-তে সরাসরি নতুন মান লিখছে, কিন্তু CPU-র cache-এ যদি সেই ঠিকানার একটা পুরনো কপি (stale copy) বসে থাকে, CPU সেই পুরনো cache কপিই বারবার পড়বে, কখনো sensor-এর নতুন মান দেখবে না — কারণ cache “মনে করে” তার কাছে already valid ডেটা আছে। উপযুক্ত সমাধান: এই ধরনের ঠিকানার জন্য cache সম্পূর্ণ বাইপাস করা (uncached memory region হিসেবে চিহ্নিত করা) — প্রতিটা read সরাসরি memory থেকে আসবে, cache-এর কোনো stale কপি থাকার সুযোগই থাকবে না। এটা এই লেসনের একটা গুরুত্বপূর্ণ সাধারণ নীতির উদাহরণ: cache শুধু তখনই সাহায্য করে যখন ডেটা শুধু CPU নিজে পরিবর্তন করে বা পড়ে; বাইরের কোনো পক্ষ (sensor, DMA, অন্য core) যদি একই ঠিকানা স্বাধীনভাবে বদলাতে পারে, cache-এর mechanism (হয়তো hardware cache-coherence protocol ছাড়া) সেই পরিবর্তন সম্পর্কে অন্ধ থাকে।
এরপর কী
তিনটা লেসন মিলিয়ে আমরা এখন একটা সম্পূর্ণ ছবি পেয়েছি: memory hierarchy কেন আছে (locality of reference), cache কীভাবে একটা বিশাল address space ছোট array-তে map করে (tag/index/offset, associativity spectrum), আর পূর্ণ হলে/লেখার সময় কী সিদ্ধান্ত নেওয়া হয় (replacement policy, write policy) — সবকিছু মিলে AMAT-এ প্রকাশিত হয়, যেটা একটা প্রোগ্রামের প্রকৃত গড় memory-access গতি নির্ধারণ করে।
কিন্তু CPU-র memory access শুধু “hit না miss” এই একরৈখিক গল্প না। একটা আধুনিক CPU একই সময়ে একাধিক instruction-এর ভিন্ন ভিন্ন পর্যায় (fetch, decode, execute, memory-access, write-back) সমান্তরালে চালায় — একটা assembly line-এর মতো। যখন একটা instruction cache miss-এ আটকে যায়, বাকি pipeline-এর কী হয়? পরের লেসনগুলোতে আপনি pipelining, hazard, আর branch prediction নিয়ে ঠিক এই প্রশ্নগুলোর উত্তর পাবেন — যেখানে এই তিনটা লেসনের cache miss-এর “দাম” (miss penalty) একটা কেন্দ্রীয় ভূমিকা পালন করবে pipeline stall বিশ্লেষণে।
আরও পড়ুন
- Computer Organization and Design (RISC-V Edition), Chapter 5 — David A. Patterson, John L. Hennessy · Replacement policy, write policy, আর AMAT-এর প্রামাণ্য আলোচনা
- Computer Architecture: A Quantitative Approach, Chapter 2 — John L. Hennessy, David A. Patterson · AMAT-এর multi-level hierarchical বিশ্লেষণ, miss rate classification (3C model)
- A Study of Replacement Algorithms for a Virtual-Storage Computer — László Bélády · মূল OPT/Belady's algorithm পেপার — optimal replacement আর Belady's anomaly-র উৎস, IBM Systems Journal, 1966
- What Every Programmer Should Know About Memory, Section 3.3 — Ulrich Drepper · Write policy আর বাস্তব CPU cache আচরণের ব্যবহারিক বিবরণ