الگوریتم کش-ناآگاه
در رایانش، یک الگوریتم کش-ناآگاه (یا الگوریتم فراگیر کش) الگوریتمی است که برای استفاده از حافظه کش پردازنده طراحی شده است، بدون این که اندازه کش (یا طول خطوط کش و غیره) به عنوان یک پارامتر صریح در نظر گرفته شود. یک الگوریتم کش-ناآگاه بهینه، الگوریتمی است که به طور بهینه از کش استفاده می‌کند (به طور مجانبی، با نادیده گرفتن عوامل ثابت). بنابراین، یک الگوریتم کش-ناآگاه به گونه‌ای طراحی شده است که بدون نیاز به تغییر، در ماشین‌های مختلف با اندازه‌های مختلف کش، یا در یک سلسله‌مراتب حافظه با سطوح مختلف کش و اندازه‌های متفاوت، به خوبی عمل کند. الگوریتم‌های کش-ناآگاه در مقایسه با کاشی‌بندی حلقه صریح قرار می‌گیرند، که به طور صریح یک مسئله را به بلوک‌هایی تقسیم می‌کند که برای یک کش مشخص بهینه شده‌اند.
الگوریتم‌های کش-ناآگاه بهینه برای ضرب ماتریس، ترانهاده ماتریس، مرتب‌سازی و چند مسئله دیگر شناخته شده‌اند. برخی از الگوریتم‌های عمومی‌تر، مانند FFT کوولی-توکی، تحت انتخاب‌های معینی از پارامترها به طور بهینه کش-ناآگاه هستند. از آنجایی که این الگوریتم‌ها تنها به طور مجانبی بهینه هستند (با نادیده گرفتن عوامل ثابت)، ممکن است برای دستیابی به عملکرد تقریباً بهینه به تنظیمات خاص ماشین نیاز باشد. هدف الگوریتم‌های کش-ناآگاه کاهش میزان چنین تنظیماتی است که لازم است.
معمولاً یک الگوریتم کش-ناآگاه با یک الگوریتم تقسیم و غلبه بازگشتی کار می‌کند، جایی که مسئله به زیرمسائل کوچک‌تر و کوچک‌تر تقسیم می‌شود. در نهایت، به اندازه‌ای از زیرمسئله می‌رسیم که در کش جا می‌گیرد، بدون توجه به اندازه کش. برای مثال، یک ضرب ماتریس کش-ناآگاه بهینه با تقسیم بازگشتی هر ماتریس به چهار زیرماتریس برای ضرب، و ضرب زیرماتریس‌ها به صورت عمقی به دست می‌آید.[citation needed] در تنظیم برای یک ماشین خاص، ممکن است از یک الگوریتم چندگانه استفاده شود که از کاشی‌بندی حلقه که برای اندازه‌های کش خاص در سطح پایین تنظیم شده است، استفاده می‌کند، اما در غیر این صورت از الگوریتم کش-ناآگاه استفاده می‌کند.
مدل کش ایده‌آل
[ویرایش]به طور کلی، یک برنامه می‌تواند به صورت بهتری به کش توجه کند:[۱]
- محلی بودن زمانی، که در آن الگوریتم چندین بار همان بخش‌های حافظه را فراخوانی می‌کند؛
- محلی بودن مکانی، که در آن دسترسی‌های بعدی به حافظه، به آدرس‌های حافظه مجاور یا نزدیک می‌باشند.
الگوریتم‌های کش-ناآگاه معمولاً با استفاده از یک مدل ایده‌آل از کش تحلیل می‌شوند که گاهی به آن مدل کش-ناآگاه گفته می‌شود. این مدل برای تحلیل کردن، بسیار ساده‌تر از مشخصات کش واقعی (که دارای همبستگی پیچیده، سیاست‌های جایگزینی و غیره هستند) می‌باشد؛ اما در بسیاری از موارد ثابت شده که با یک عامل ثابت از عملکرد یک کش واقعی قابل مقایسه است. این مدل با مدل حافظه خارجی متفاوت است زیرا الگوریتم‌های کش-ناآگاه اندازه بلاک یا اندازه کش را نمی‌دانند.
کاربرد
[ویرایش]یک مقایسه تجربی بین دو الگوریتم مبتنی بر RAM، یک الگوریتم آگاه از کش، و دو الگوریتم کش-ناآگاه که صف‌های اولویت‌دار را پیاده‌سازی می‌کنند نشان داد که:[۲]
- الگوریتم‌های کش-ناآگاه نسبت به الگوریتم‌های مبتنی بر RAM و کش-آگاه زمانی که داده‌ها در حافظه اصلی قرار می‌گیرند، عملکرد ضعیف‌تری داشتند.
- الگوریتم کش-آگاه به نظر نمی‌رسید که پیاده‌سازی آن به طور قابل توجهی پیچیده‌تر از الگوریتم‌های کش-ناآگاه باشد و در تمامی موارد آزمایش شده در مطالعه، بهترین عملکرد را ارائه داد.
- الگوریتم‌های کش-ناآگاه زمانی که اندازه داده‌ها از اندازه حافظه اصلی بیشتر بود، عملکرد بهتری نسبت به الگوریتم‌های مبتنی بر RAM داشتند.
یک بررسی دیگر، جدول‌های هش (به عنوان مبتنی بر RAM یا بی‌توجه به کش)، درخت‌های B (به عنوان کش-آگاه)، و یک ساختار داده بی‌توجه به کش به نام «مجموعه بندر» را مقایسه کرد. برای هر دو معیار زمان اجرا و استفاده از حافظه، جدول هش بهترین بود و پس از آن درخت B قرار داشت و مجموعه بندر در تمامی موارد بدترین بود. استفاده از حافظه در همه آزمایش‌ها از حافظه اصلی فراتر نرفت. جدول‌های هش به عنوان «ساده برای پیاده‌سازی» توصیف شدند، در حالی که مجموعه بندر «نیاز به تلاش بیشتری برای پیاده‌سازی صحیح داشت».[۳]
منابع
[ویرایش]- ↑ Askitis, Nikolas; Zobel, Justin (2005). "Cache-Conscious Collision Resolution in String Hash Tables". International Symposium on String Processing and Information Retrieval. Springer: 93. doi:10.1007/11575832_1. ISBN 978-3-540-29740-6.
- ↑ Olsen, Jesper Holm; Skov, Søren Christian (2 December 2002). Cache-Oblivious Algorithms in Practice (PDF) (Master's). University of Copenhagen. Retrieved 3 January 2022.
- ↑ Verver, Maks (23 June 2008). "Evaluation of a Cache-Oblivious Data Structure" (PDF). Retrieved 3 January 2022.