پیش‌واکشی حافظه نهان

پیش‌واکشی حافظه نهان (به انگلیسی: cache prefetching)، تکنیکی است که توسط پردازنده‌های رایانه انجام می‌شود و برای تقویت عملکرد اجرای برنامه‌ها است. در این تکنیک، پردازنده دستورالعمل‌ها یا داده‌ها را از حافظه اصلی (حافظه کندتر) به یک حافظه محلی (حافظه تندتر) قبل از اینکه واقعاً مورد نیاز باشد بازیابی می‌کند (از این رو اصطلاح 'prefetch' نامیده می‌شود).^[۱] اکثر پردازنده‌های کامپیوتری مدرن، دارای حافظه نهان سریع و محلی هستند که داده‌های بازیابی شده را تا زمانی که مورد استفاده قرار نگرفته‌اند در خود نگه می‌دارند. معمولاً عملیات پیش واکشی در حافظه اصلی صورت می‌گیرد. به دلیل طراحی پردازنده‌ها، معمولاً دسترسی به حافظه‌های نهان بسیار سریع‌تر از دسترسی به حافظه اصلی است، بنابراین واکشی اولیه داده‌ها و سپس دسترسی به آن‌ها از طریق حافظه نهان معمولاً چندین مرتبه سریع‌تر از دسترسی مستقیم به آن‌ها از حافظه اصلی است. واکشی اولیه را می‌توان با دستورالعمل‌های کنترل حافظه پنهان غیر مسدود کننده (non-blocking) انجام داد.

مقایسه پیش واکشی حافظه نهان در داده‌ها با دستورالعمل‌ها

پیش واکشی حافظه نهان می‌تواند داده‌ها یا دستورالعمل‌ها را در حافظه پنهان بازیابی کند.

پیش واکشی داده، داده‌ها را قبل از نیاز بازیابی می‌کند. از آنجا که الگوهای دسترسی به داده‌ها نظم کمتری نسبت به الگوهای دستورالعمل نشان می‌دهند، واکشی داده‌ها معمولاً چالش‌برانگیزتر از واکشی دستورالعمل است.
پیش واکشی دستورالعمل، دستورالعمل‌ها را قبل از نیاز به اجرا بازیابی می‌کند. اولین ریزپردازنده‌های اصلی که از نوعی پیش واکشی دستورالعمل استفاده کردند، Intel 8086 (شش بایت) و موتورولا ۶۸۰۰۰ (چهار بایت) بودند. در سال‌های اخیر، تمام پردازنده‌های با کارایی بالا از تکنیک‌های پیش واکشی استفاده می‌کنند.

مقایسه پیش واکشی حافظه نهان سخت‌افزار با نرم‌افزار

پیش واکشی حافظه نهان می‌تواند توسط سخت‌افزار یا نرم‌افزار انجام شود.

پیش واکشی مبتنی بر سخت‌افزار معمولاً با داشتن مکانیزم سخت‌افزاری اختصاصی در پردازنده انجام می‌شود. در این روش، دستورالعمل‌ها یا داده‌هایی را که توسط برنامه اجراکننده در یک جریان خاص (stream) درخواست می‌شود، بررسی می‌شود و چند دستور یا دادهٔ بعدی که ممکن است در این جریان برنامه به آن نیاز داشته باشد شناسایی می‌کند و در حافظه پنهان پردازنده، پیش واکشی می‌کند.^[۲]
پیش واکشی مبتنی بر نرم‌افزار معمولاً با تجزیه و تحلیل کد توسط کامپایلر و درج دستورالعمل‌های اضافی «پیش واکشی» در برنامه هنگام کامپایل شدن انجام می‌شود.^[۳]

روش‌های پیش واکشی سخت‌افزاری

بافرهای جریان (Stream buffers)

بافرهای جریان بر اساس مفهوم "بلوک پیش بینی (OBL)" پیشنهاد شده توسط آلن جی اسمیت توسعه یافتند.^[۱]
بافرهای جریان یکی از رایج‌ترین تکنیک‌های پیش واکشی مبتنی بر سخت‌افزار هستند. این تکنیک در ابتدا توسط نورمن جوپی در سال 1990^[۴] ابداع شد و از آن زمان تاکنون انواع مختلفی از این روش ارائه شده‌است.^[۵]^[۶]^[۷] ایده اصلی این است که آدرس حافظه پنهان (و $k$ آدرس‌های بعدی) در بافر جداگانه‌ای با عمق $k$ بازیابی می‌شوند. این بافر، بافر جریان نامیده می‌شود و از حافظه نهان جدا است. در صورتی که آدرس ذخیره شده در بلوک‌ها، با آدرسی که برنامه درحال اجرا روی پردازنده درخواست کرده مطابقت داشته باشد، پردازنده، آدرس مورد نیاز برنامه را از طریق بافر جریان در اختیار برنامه می‌دهد (که این فضا برای انجام دستورالعمل یا ذخیره داده استفاده می‌شود). شکل زیر این تنظیمات را نشان می‌دهد:

هر زمان که مکانیزم پیش واکشی بخواهد بلوکی مثل A را از سیستم پیش واکشی کند، یک بافر جریان برای پیش واکشی چند بلوک متوالی ایجاد می‌کند؛ مثلاً اگر بافر جریان بتواند ۴ بلوک را نگه دارد، A+1، A+2، A+3، A+4 را پیش واکشی می‌کنیم و آن‌ها را در بافر جریان اختصاص داده شده نگه می‌داریم. اگر پردازنده در مرحله بعدی A+1 را مصرف کند، باید از بافر جریان به مکان بالاتر از A+1 در حافظه نهان پردازنده منتقل شود و اولین ورودی بافر جریان A+2 خواهد بود. این الگوی پیش واکشی، پیش واکشی متوالی نامیده می‌شود و عمدتاً در مواقعی استفاده می‌شود که قرار است عملیات پیش واکشی روی بلوک‌های مجاور انجام شود. به عنوان مثال، هنگام پیش واکشی دستورالعمل‌ها از این مکانیزم استفاده می‌شود.
این مکانیسم را می‌توان با افزودن چندین بافر جریان توسعه داد که هر کدام، یک جریان پیش واکشی جداگانه را حفظ می‌کنند. برای پیش واکشی هر داده جدید، یک بافر جریان جدید تخصیص داده می‌شود و هر کدام، به روشی مشابه که در بالا توضیح داده شد عمل می‌کنند.
اندازه ایده‌آل بافر از طریق آزمایش کردن معیارهای مختلفو به بقیه ریزمعماری درگیر بستگی دارد.^[۸]

روش دیگری برای پیش واکشی دستورالعمل‌ها، پیش واکشی تعدادی آدرس به صورت دنباله هستند. این روش عمدتاً زمانی استفاده می‌شود که بلوک‌های متوالی که قرار است از قبل واکشی شوند، دارای s آدرس جدا از هم هستند،این روش Strided Prefetching نام دارد.^[۹]

روش‌های پیش واکشی نرم‌افزاری

پیش واکشی هدایت شده توسط کامپایلر

پیش واکشی هدایت شده توسط کامپایلر، در حلقه‌هایی با تعداد زیاد تکرار استفاده می‌شود. در این تکنیک، کامپایلر cache misses را پیش‌بینی می‌کند و یک دستورالعمل پیش واکشی بر اساس جریمه خطا و زمان اجرای دستورالعمل‌ها ایجاد می‌کند.

این پیش واکشی‌ها عملیات حافظه غیر مسدود هستند، یعنی این دسترسی‌های حافظه با دسترسی‌های واقعی حافظه تداخلی ندارند، وضعیت پردازنده را تغییر نمی‌دهند و همچنین باعث وقوع خطا در پردازنده نمی‌شوند.

یکی از مزیت‌های اصلی پیش واکشی نرم‌افزار، کاهش تعداد cache misses است.

مثال زیر نشان می‌دهد که چگونه یک دستورالعمل پیش واکشی به یک کد برای بهبود عملکرد حافظه پنهان اضافه می‌شود.

یک حلقه for را در نظر بگیرید:

for (int i=0; i<1024; i++) {
  array1[i] = 2 * array1[i];
}

در هر تکرار، i امین عنصر از آرایه "array1" قابل دسترسی است؛ بنابراین، می‌توانیم عناصری را که در تکرارهای بعدی به آن نیاز داریم را با قرار دادن یک دستورالعمل "prefetch" مانند شکل زیر پیش واکشی کنیم:

for (int i=0; i<1024; i++) {
  prefetch (array1 [i + k]);
  array1[i] = 2 * array1[i];
}

اینجا، گام پیش واکشی، $k$ به دو عامل بستگی دارد، cache miss penalty و زمان لازم برای اجرای یک تکرار حلقه for. به عنوان مثال، اگر یک تکرار از حلقه ۷ سیکل طول بکشد تا اجرا شود، cache miss penalty چهل و نه چرخه باشد. داریم $k=49/7=7$ . که به این معنی است که باید ۷ عنصر را پیش واکشی کنیم. در زمان اولین تکرار، i=۰ خواهد بود، بنابراین عنصر هفتم را پیش واکشی می‌کنیم. با همین منوال، ۷ عنصر اول (i=۰->۶) همچنان پیش واکشی می‌شوند (به عبارتی دیگر هر عنصر از آرایه۱ در یک خط‌کش برای خودش قرار دارد).

مقایسه پیش واکشی سخت‌افزاری و نرم‌افزاری

در حالی که پیش واکشی نرم‌افزار به مداخله برنامه‌نویس یا کامپایلر نیاز دارد، پیش واکشی سخت‌افزاری نیز به مکانیزم‌های سخت‌افزاری خاصی نیاز دارد.
پیش واکشی نرم‌افزار فقط با حلقه‌هایی که دسترسی منظم به آرایه وجود دارد به خوبی کار می‌کند، زیرا در غیر اینصورت برنامه‌نویس باید دستورالعمل‌های پیش واکشی را به صورت دستی بنویسد. در حالی که پیش واکشی سخت‌افزار بر اساس رفتار برنامه در زمان اجرا کار می‌کنند.
همچنین پیش واکشی سخت‌افزار در مقایسه با پیش واکشی نرم‌افزار، کمتر از CPU استفاده می‌کند.^[۱۰]

معیارهای پیش واکشی حافظه پنهان

سه معیار اصلی برای پیش واکشی حافظه پنهان وجود دارد

پوشش

پوشش، نسبت تعداد cache misses پیشگیری شده به خاطر پیش واکشی به تعداد کل cache misses است:

$Coverage={\frac {\text{Cache Misses eliminated by Prefetching}}{\text{Total Cache Misses}}}$ ،

جایی که، ${\text{Total Cache Misses}}=({\text{Cache misses eliminated by prefetching}})+({\text{Cache misses not eliminated by prefetching}})$

دقت

دقت، نسبت پیش واکشی مفید (آدرس‌های پیش واکشی شده توسط برنامه) به کل پیش واکشی‌ها.

${\text{Prefetch Accuracy}}={\frac {\text{Cache Misses eliminated by prefetching}}{({\text{Useless Cache Prefetches}})+({\text{Cache Misses eliminated by prefetching}})}}$

در حالی که به نظر می‌رسد داشتن دقت کامل به معنای عدم وجود خطا است، اگر بلوک‌های پیش واکشی شده مستقیماً در حافظه پنهان قرار گیرند، خود پیش واکشی‌ها ممکن است منجر به خطاهای جدیدی شوند. اگرچه این مورد ممکن است کسر کوچکی از تعداد کل پیش واکشی‌ها باشد ولی احتمالش صفر نیست.

به موقع بودن

گوییم یک پیش واکشی به موقع است اگر حدفاصل زمان بین پیش واکشی و واکشی کم باشد. یک مثال برای توضیح بیشتر به موقع بودن به شرح زیر است:

یک حلقه for را در نظر بگیرید که در آن هر تکرار ۳ چرخه برای اجرا و عملیات پیش واکشی ۱۲ چرخه طول می‌کشد. این بدان معناست که برای اینکه داده‌های پیش واکشی شده مفید باشند، باید پیش واکشی را $12/3=4$ تکرار قبل از استفاده اصلی انجام دهیم.

جستارهای وابسته

منابع

↑ ^۱٫۰ ^۱٫۱ Smith, Alan Jay (1982-09-01). "Cache Memories". ACM Comput. Surv. 14 (3): 473–530. doi:10.1145/356887.356892. ISSN 0360-0300.
↑ Baer, Jean-Loup; Chen, Tien-Fu (1991-01-01). An Effective On-chip Preloading Scheme to Reduce Data Access Penalty. 1991 ACM/IEEE Conference on Supercomputing. Albuquerque, NM, USA: ACM. pp. 176–186. CiteSeerX 10.1.1.642.703. doi:10.1145/125826.125932. ISBN 978-0-89791-459-8.
↑ Kennedy, Porterfield, Allan (1989-01-01). Software methods for improvement of cache performance on supercomputer applications (Thesis). Rice University. hdl:1911/19069.
↑ Jouppi, Norman P. (1990). Improving direct-mapped cache performance by the addition of a small fully-associative cache and prefetch buffers. New York, New York, USA: ACM Press. CiteSeerX 10.1.1.37.6114. doi:10.1145/325164.325162. ISBN 0-89791-366-3.
↑ Chen, Tien-Fu; Baer, Jean-Loup (1995-05-01). "Effective hardware-based data prefetching for high-performance processors". IEEE Transactions on Computers. 44 (5): 609–623. doi:10.1109/12.381947. ISSN 0018-9340.
↑ Palacharla, S.; Kessler, R. E. (1994-01-01). Evaluating Stream Buffers As a Secondary Cache Replacement. 21st Annual International Symposium on Computer Architecture. Chicago, IL, USA: IEEE Computer Society Press. pp. 24–33. CiteSeerX 10.1.1.92.3031. doi:10.1109/ISCA.1994.288164. ISBN 978-0-8186-5510-4.
↑ Grannaes, Marius; Jahre, Magnus; Natvig, Lasse (2011). "Storage Efficient Hardware Prefetching using Delta-Correlating Prediction Tables". Journal of Instruction-Level Parallelism (13): 1–16. CiteSeerX 10.1.1.229.3483.
↑ Jouppi, Norman P. (1990). Improving direct-mapped cache performance by the addition of a small fully-associative cache and prefetch buffers. New York, New York, USA: ACM Press. CiteSeerX 10.1.1.37.6114. doi:10.1145/325164.325162. ISBN 0-89791-366-3.
↑ Solihin, Yan (2016). Fundamentals of parallel multicore architecture. Boca Raton, FL: CRC Press, Taylor & Francis Group. p. 163. ISBN 978-1-4822-1118-4.
↑ Callahan, David; Kennedy, Ken; Porterfield, Allan (1991-01-01). Software Prefetching. Fourth International Conference on Architectural Support for Programming Languages and Operating Systems. Santa Clara, CA, USA: ACM. pp. 40–52. doi:10.1145/106972.106979. ISBN 978-0-89791-380-5.

[:3-1] ۱٫۰ ^۱٫۱ Smith, Alan Jay (1982-09-01). "Cache Memories". ACM Comput. Surv. 14 (3): 473–530. doi:10.1145/356887.356892. ISSN 0360-0300.

[2] Baer, Jean-Loup; Chen, Tien-Fu (1991-01-01). An Effective On-chip Preloading Scheme to Reduce Data Access Penalty. 1991 ACM/IEEE Conference on Supercomputing. Albuquerque, NM, USA: ACM. pp. 176–186. CiteSeerX 10.1.1.642.703. doi:10.1145/125826.125932. ISBN 978-0-89791-459-8.

[3] Kennedy, Porterfield, Allan (1989-01-01). Software methods for improvement of cache performance on supercomputer applications (Thesis). Rice University. hdl:1911/19069.

[:13-4] Jouppi, Norman P. (1990). Improving direct-mapped cache performance by the addition of a small fully-associative cache and prefetch buffers. New York, New York, USA: ACM Press. CiteSeerX 10.1.1.37.6114. doi:10.1145/325164.325162. ISBN 0-89791-366-3.

[5] Chen, Tien-Fu; Baer, Jean-Loup (1995-05-01). "Effective hardware-based data prefetching for high-performance processors". IEEE Transactions on Computers. 44 (5): 609–623. doi:10.1109/12.381947. ISSN 0018-9340.

[6] Palacharla, S.; Kessler, R. E. (1994-01-01). Evaluating Stream Buffers As a Secondary Cache Replacement. 21st Annual International Symposium on Computer Architecture. Chicago, IL, USA: IEEE Computer Society Press. pp. 24–33. CiteSeerX 10.1.1.92.3031. doi:10.1109/ISCA.1994.288164. ISBN 978-0-8186-5510-4.

[7] Grannaes, Marius; Jahre, Magnus; Natvig, Lasse (2011). "Storage Efficient Hardware Prefetching using Delta-Correlating Prediction Tables". Journal of Instruction-Level Parallelism (13): 1–16. CiteSeerX 10.1.1.229.3483.

[:12-8] Jouppi, Norman P. (1990). Improving direct-mapped cache performance by the addition of a small fully-associative cache and prefetch buffers. New York, New York, USA: ACM Press. CiteSeerX 10.1.1.37.6114. doi:10.1145/325164.325162. ISBN 0-89791-366-3.

[:23-9] Solihin, Yan (2016). Fundamentals of parallel multicore architecture. Boca Raton, FL: CRC Press, Taylor & Francis Group. p. 163. ISBN 978-1-4822-1118-4.

[10] Callahan, David; Kennedy, Ken; Porterfield, Allan (1991-01-01). Software Prefetching. Fourth International Conference on Architectural Support for Programming Languages and Operating Systems. Santa Clara, CA, USA: ACM. pp. 40–52. doi:10.1145/106972.106979. ISBN 978-0-89791-380-5.

[۱]

[۲]

[۳]

[۴]

[۵]

[۶]

[۷]

[۸]

[۹]

[۱۰]