Cache-Oblivious
ক্যাশ-অব্লিভিয়াস
Cache size বা line length জেনে না রেখেই cache performance optimize করা algorithm design — recursive decomposition-এ memory-র প্রতিটা স্তরে ভালো চলে।
also: cache-oblivious algorithm, cache oblivious
দুই design philosophy:
| Approach | ভরসা | দুর্বলতা |
|---|---|---|
| Cache-aware | B (line), M (cache size) tuning | machine বদলালে retune |
| Cache-oblivious | কোনো hardware parameter নেই | ডিজাইন জটিল |
মূল কৌশল: subproblem recursively এত ছোট করা যেন কোনো না কোনো cache স্তরে পুরোটা আঁটতেই থাকে। Van Emde Boas layout-এ সাজানো tree, cache-oblivious matrix multiply, funnel sort — ক্লাসিক উদাহরণ।
Ideal-cache model-এ অজানা B, M-এর জন্য optimal I/O prove করলে বাস্তবের প্রতিটা স্তরে (L1, L2, LLC, RAM, SSD) optimal। Theory-র প্রতিশ্রুতি: একবার লেখো, সব হার্ডওয়্যারে দ্রুত।