Hardware Prefetching
হার্ডওয়্যার প্রিফেচিং
CPU-র dedicated unit যা memory access pattern দেখে ভবিষ্যতের ঠিকানা অনুমান করে explicit request-এর আগেই cache-এ নিয়ে আসে। শুধু sequential/stride প্যাটার্নে কাজ করে — pointer chasing সম্পূর্ণ অসহায় করে দেয়।
also: prefetcher, stride prefetcher, sequential prefetcher, prefetch distance
সবচেয়ে সরল রূপ next-line prefetcher — line N access হলে
N+1-ও এনে রাখে। বাস্তবে বেশি ব্যবহৃত stride prefetcher একটা
per-load stride table রাখে (last address, last stride, confidence
counter) — একই stride বারবার দেখলে (থ্রেশহোল্ড, সাধারণত ২-৩ বার)
prefetch শুরু করে।
Prefetch distance গুরুত্বপূর্ণ হিসাব: DRAM latency ~২০০ cycle, loop iteration যদি ৫ cycle লাগে, latency পুরোপুরি hide করতে ~৪০ iteration আগে prefetch শুরু করতে হয়।
কেন pointer chasing ভাঙে এটা: array access-এ পরের ঠিকানা
arithmetically গণনাযোগ্য (base + i×stride), prefetcher নিজেই
হিসাব করে ফেলতে পারে। Linked-list-এ node->next-এর মান memory-তে
লুকানো — জানতে হলে node আগে পড়তেই হবে। এটা engineering সীমা না,
তথ্যতাত্ত্বিক সীমা — কোনো prefetcher এমন ঠিকানা prefetch করতে
পারে না যা এখনো পড়াই হয়নি। ফলাফল: sequential access-এ Memory-Level
Parallelism (MLP) বেশি (বহু request একসাথে in-flight, latency
overlap হয়); pointer chasing-এ MLP = ১ (সম্পূর্ণ serialized) —
mathematics/asymptotic-notation-এর সেই ১০-২০× array-বনাম-linked-list
গ্যাপের মূল কারণ।
Software prefetch hint (__builtin_prefetch) কখনো fault করে
না, শুধু একটা suggestion — খুব আগে দিলে cache pollution, খুব দেরিতে
দিলে latency হাইড হয় না। Measure ছাড়া বিশ্বাসযোগ্য না।
অনেক prefetcher ৪ KB page boundary পার হয়ে prefetch করে না (physical address contiguity নিশ্চিত না বলে) — তাই বড় stride constant হলেও কার্যকারিতা হারাতে পারে।