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

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

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

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

• پیش واکشی داده، داده‌ها را قبل از نیاز بازیابی می‌کند. از آنجا که الگوهای دسترسی به داده‌ها نظم کمتری نسبت به الگوهای دستورالعمل نشان می‌دهند، واکشی داده‌ها معمولاً چالش‌برانگیزتر از واکشی دستورالعمل است.

• پیش واکشی دستورالعمل، دستورالعمل ها را قبل از نیاز به اجرا بازیابی می کند. اولین ریزپردازنده های اصلی که از نوعی پیش واکشی دستورالعمل استفاده کردند، Intel 8086 (شش بایت) و موتورولا 68000 (چهار بایت) بودند. در سال های اخیر، تمام پردازنده های با کارایی بالا از تکنیک های پیش واکشی استفاده می کنند.

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

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

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

• پیش واکشی مبتنی بر نرم افزار معمولاً با تجزیه و تحلیل کد توسط کامپایلر و درج دستورالعمل های اضافی «پیش واکشی» در برنامه هنگام کامپایل شدن انجام می شود.

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

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

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

یک بافر جریان مشابه با بافری که در ابتدا توسط نورمن جوپی در سال 1990 پیشنهاد شد.

• هر زمان که مکانیزم پیش واکشی بخواهد بلوکی مثل A را از سیستم پیش واکشی کند، یک بافر جریان برای پیش واکشی چند بلوک متوالی ایجاد می کند. مثلا اگر بافر جریان بتواند 4 بلوک را نگه دارد، 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. به عنوان مثال، اگر یک تکرار از حلقه 7 سیکل طول بکشد تا اجرا شود، cache miss penalty چهل و نه چرخه باشد. داریم

$k=49/7=7$

. که به این معنی است که باید 7 عنصر را پیش واکشی کنیم. در زمان اولین تکرار، i=0 خواهد بود، بنابراین عنصر هفتم را پیش واکشی می کنیم. با همین منوال، 7 عنصر اول (i=0->6) همچنان پیش واکشی می شوند (به عبارتی دیگر هر عنصر از آرایه1 در یک خط کش برای خودش قرار دارد).

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

• در حالی که پیش واکشی نرم افزار به مداخله برنامه نویس یا کامپایلر نیاز دارد، پیش واکشی سخت افزاری نیز به مکانیزم های سخت افزاری خاصی نیاز دارد.
• پیش واکشی نرم‌افزار فقط با حلقه‌هایی که دسترسی منظم به آرایه وجود دارد به خوبی کار می‌کند، زیرا در غیر اینصورت برنامه‌نویس باید دستورالعمل‌های پیش واکشی را به صورت دستی بنویسد. در حالی که پیش واکشی‌ سخت‌افزار بر اساس رفتار برنامه در زمان اجرا کار می‌کنند.
• همچنین پیش واکشی سخت‌افزار در مقایسه با پیش واکشی نرم‌افزار، کمتر از 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 را در نظر بگیرید که در آن هر تکرار 3 چرخه برای اجرا و عملیات پیش واکشی 12 چرخه طول می کشد. این بدان معناست که برای اینکه داده های پیش واکشی شده مفید باشند، باید پیش واکشی را $12/3=4$ تکرار قبل از استفاده اصلی انجام دهیم.

همچنین ببینید

• پیش واکشی ورودی صف
• پیش واکشی پیوند
• پیش واکش کننده
• دستورالعمل کنترل کش