در رایانش، یک الگوریتم کش-ناآگاه (یا الگوریتم فراگیر کش) الگوریتمی است که برای استفاده از حافظه کش پردازنده طراحی شده است، بدون این که اندازه کش (یا طول خطوط کش و غیره) به عنوان یک پارامتر صریح در نظر گرفته شود. یک الگوریتم کش-ناآگاه بهینه، الگوریتمی است که به طور بهینه از کش استفاده میکند (به طور مجانبی، با نادیده گرفتن عوامل ثابت). بنابراین، یک الگوریتم کش-ناآگاه به گونهای طراحی شده است که بدون نیاز به تغییر، در ماشینهای مختلف با اندازههای مختلف کش، یا در یک سلسلهمراتب حافظه با سطوح مختلف کش و اندازههای متفاوت، به خوبی عمل کند. الگوریتمهای کش-ناآگاه در مقایسه با کاشیبندی حلقه صریح قرار میگیرند، که به طور صریح یک مسئله را به بلوکهایی تقسیم میکند که برای یک کش مشخص بهینه شدهاند.
الگوریتمهای کش-ناآگاه بهینه برای ضرب ماتریس، ترانهاده ماتریس، مرتبسازی و چند مسئله دیگر شناخته شدهاند. برخی از الگوریتمهای عمومیتر، مانند FFT کوولی-توکی، تحت انتخابهای معینی از پارامترها به طور بهینه کش-ناآگاه هستند. از آنجایی که این الگوریتمها تنها به طور مجانبی بهینه هستند (با نادیده گرفتن عوامل ثابت)، ممکن است برای دستیابی به عملکرد تقریباً بهینه به تنظیمات خاص ماشین نیاز باشد. هدف الگوریتمهای کش-ناآگاه کاهش میزان چنین تنظیماتی است که لازم است.
معمولاً یک الگوریتم کش-ناآگاه با یک الگوریتم تقسیم و غلبه بازگشتی کار میکند، جایی که مسئله به زیرمسائل کوچکتر و کوچکتر تقسیم میشود. در نهایت، به اندازهای از زیرمسئله میرسیم که در کش جا میگیرد، بدون توجه به اندازه کش. برای مثال، یک ضرب ماتریس کش-ناآگاه بهینه با تقسیم بازگشتی هر ماتریس به چهار زیرماتریس برای ضرب، و ضرب زیرماتریسها به صورت عمقی به دست میآید.[citation needed] در تنظیم برای یک ماشین خاص، ممکن است از یک الگوریتم چندگانه استفاده شود که از کاشیبندی حلقه که برای اندازههای کش خاص در سطح پایین تنظیم شده است، استفاده میکند، اما در غیر این صورت از الگوریتم کش-ناآگاه استفاده میکند.
به طور کلی، یک برنامه میتواند به صورت بهتری به کش توجه کند:[۱]
الگوریتمهای کش-ناآگاه معمولاً با استفاده از یک مدل ایدهآل از کش تحلیل میشوند که گاهی به آن مدل کش-ناآگاه گفته میشود. این مدل برای تحلیل کردن، بسیار سادهتر از مشخصات کش واقعی (که دارای همبستگی پیچیده، سیاستهای جایگزینی و غیره هستند) میباشد؛ اما در بسیاری از موارد ثابت شده که با یک عامل ثابت از عملکرد یک کش واقعی قابل مقایسه است. این مدل با مدل حافظه خارجی متفاوت است زیرا الگوریتمهای کش-ناآگاه اندازه بلاک یا اندازه کش را نمیدانند.
یک مقایسه تجربی بین دو الگوریتم مبتنی بر RAM، یک الگوریتم آگاه از کش، و دو الگوریتم کش-ناآگاه که صفهای اولویتدار را پیادهسازی میکنند نشان داد که:[۲]
یک بررسی دیگر، جدولهای هش (به عنوان مبتنی بر RAM یا بیتوجه به کش)، درختهای B (به عنوان کش-آگاه)، و یک ساختار داده بیتوجه به کش به نام «مجموعه بندر» را مقایسه کرد. برای هر دو معیار زمان اجرا و استفاده از حافظه، جدول هش بهترین بود و پس از آن درخت B قرار داشت و مجموعه بندر در تمامی موارد بدترین بود. استفاده از حافظه در همه آزمایشها از حافظه اصلی فراتر نرفت. جدولهای هش به عنوان «ساده برای پیادهسازی» توصیف شدند، در حالی که مجموعه بندر «نیاز به تلاش بیشتری برای پیادهسازی صحیح داشت».[۳]