حافظه cache

تو پروژه اخیرم قراره از میکروکنترلری استفاده کنم که cache داره و میشه به کمکش کدهای برنامه رو که قراره تو حافظه‌ی خارجی قرار بگیره، با سرعت خوبی اجرا کرد. این بود که لازم شد یه سر به بحث cache بزنم و یه آشنایی ساده در حدی که کارم راه بیفته باهاش پیدا کنم. در خصوص حافظه Cache شرکت ST اپلیکیشن نوت AN4839 رو برای میکروکنترلرهای STM32F7 و STMH7 منتشر کرده. پیش فرض هم اینه که خواننده آشنایی اولیه با یکسری از مفاهیم Cache را دارد. حالا در ادامه قصد دارم توضیح مختصری در خصوص Cache بدم تا ؤافرادی که این آشنایی رو ندارن به مشکل نخورند.

بگذارید از یکم قبل‌تر شروع کنیم. میدونیم که به بطور کلی دو حافظه‌ی فرّار-مثل RAM- و غیرفرّار-مثل FLASH- در میکروکنترلر داریم. اغلب هم اینطوریه که حافظه فلش در حجم بالاتر و قیمت پایین‌تر از RAM عرضه میشه.

با وجود حافظه Flash چه نیازی به RAM داریم؟!

یکی از دلایل سرعت هست. سرعت خواندن و به ویژه نوشتن در حافظه Flash به مراتب از حافظه RAM کندتر است. به همین دلیل ما یک حافظه با مقدار کمتر اما سریع‌تر در کنار پردازنده قرار میدهیم تا بهمون کمک کنه بهینه‌تر برنامه رو اجرا کنیم. مشابه با همین رویه رو میتونیم جاهای دیگه هم ببینیم. یعنی در سیستم‌های کامپیوتری ما باز هم شاهد این هستیم که یک حافظه‌ی کمتر و البته پرسرعت‌تر در میان دو واحد قرار داده‌اند تا کارایی برنامه بالاتر برود. مثلاً در مشخصات یکسری از میکروهای ST میبینیم که دارای حافظه CCM یا Core Coupled Memory است. حافظه‌ای که با حجمی کمتر اما سرعتی بالاتر از SRAM اصلی در کنار پردازنده قرار داده شده تا یکسری از متغیرها یا کدهای برنامه که گلوگاه سرعت اجرای کد هستند را در آن قرار بدهیم.

حالا ST در میکروهای با توان پردازشی بالاتر خود مثل کورتکس M7 آمده علاوه بر CCM یک حافظه‌ی کوچک اما پرسرعت‌ قرار داده تا راندمان بیشتر شود. و خب همونطور که میدونید اسم این حافظه کوچک Cache است. ما در این میکروها با کش Level 1 یا به طور مختصر L1 روبرو هستیم. در سیستم‌های کامپیوتری، Cache گاهی به چند سطح L2، L1 و L3 تقسیم میشه که باز همان رویه‌ی حجم کمتر اما پرسرعت‌تر، تکرار شده.

خیلی ساده و خلاصه، نحوه‌ی استفاده CPU از Cache به این صورت است که نگاه می‌کند آیا محلی از حافظه که قرار است خوانده(نوشته) شود در Cache وجود دارد یا خیر. اگر وجود داشت Cache Hit رخ داده و اطلاعات ازحافظه Cache با سرعت بالا خوانده(نوشته) می‌شود. در غیر این صورت Cache Miss رخ داده و باید سراغ حافظه‌ی کم سرعت اصلی برویم. به این صورت که اگر داخل Cache جای خالی وجود داشت که هیچ، وگرنه باید با پاک کردن داده‌های قبلی ابتدا جای خالی ایجاد کنیم و سپس با خواندن از حافظه‌ی اصلی داده‌ی مدنظرمان را وارد ‌‌Cache کنیم تا CPU بتواند به آن دسترسی پیدا کند. به این ترتیب هر چه  Cache Hit بیشتر باشد، یعنی سرعت و راندمان ما بالاتر است.

چطور می‌توان ‌Cache Hit را افزایش داد؟

سوالی است که هنوز طراحان سعی می‌کنند پاسخ بهتری برایش پیدا کنند. اما در حد این مقاله ما می‌توانیم یک پاسخ ساده بدهیم. ما باید دنبال یک حدس خوب باشیم. حدسی که بر اساس اون کنترلر Cache سعی می‌کند داده‌هایی که احتمالش بیشتر است مورد استفاده قرار گیرند را در حافظه‌ی Cache نگه دارد. برای این حدس سراغ آمار می‌رویم. اگر نگاهی به آمار محل‌هایی از حافظه که Cache شده‌اند بندازیم به ۲ نتیجه می‌رسیم. اول اینکه اگر پردازنده سراغ آدرس مثلا ‌0x100 از حافظه رفت احتمالش بیشتر است که در ادامه سراغ خانه‌های کناری مثلا آدرس 0x101 برود تا جای دیگری از حافظه. به این اتفاق ‌Spatial Locality می‌گویند. دومین نتیجه که به آن Temporal Locality می‌گویند اشاره بر تعداد دفعات مراجعه پردازنده به یک خانه از حافظه دارد. یعنی اگر ده بار سراغ آدرس 0x200 رفت احتمالش بیشتر است که در آینده باز سراغ این آدرس برود به نسبت مثلا آدرس 0x300  که دوبار بیشتر باهاش کار نداشته.

کنترلر ‌ Cache با هر بار خواندن از حافظه‌ی اصلی چندین بایت که به آن یک Line می‌گویند را هم‌زمان می‌خواند و در خود نگه می‌دارد. مثلا در میکروکنترلر ‌‌STM32H7 یک Line مقدارش ۳۲ بایت است. برای خواندن محلی از حافظه‌ی اصلی لازم است که عملیاتی صورت بگیرد تا محتوای آن محل را در اختیار ما قرار دهد. این زمان آماده سازی چه برای خواندن(نوشتن) یک بایت و چه تعداد بایت‌های بیشتر ثابت است. به همین دلیل در مجموع زمان صرف شده برای خواندن(نوشتن) ۳۲ بایت یکجا، از محلی از حافظه، به نسبت یک بایت، بسیار کمتر است. علاوه بر این موضوع بحث Spatial Locality هم کمک می‌کند تا این دسته‌ای خواندن بایت‌ها راندمان را افزایش دهد.

نگاشت حافظه‌ی بزرگ-اصلی- به حافظه‌ی کوچک-Cache-:

با توضیحاتی که تا الان دادم احتمالا اینطور به نظرتان می‌رسد که در ابتدا Lineهای مورد نیاز به ترتیب تا زمانی که Cache کامل پر نشده در این حافظه قرار می‌گیرند و پس از اتمام فضای خالی Cache سراغ خالی کردن یک Line و جا دادن Line جدید میرود. در این روش یک Line خوانده شده از حافظه‌ی اصلی در هر جایی از Cache می‌تواند واقع شود. اشکال کار اینجاست که پیدا کردن یک آدرس در Cache بسیار زمان‌بر و پیچیده خواهد شد. چراکه کنترلر Cache باید کل Line های Cache را بررسی کند تا ببیند آیا آدرس درخواست شده توسط پردازنده در Cache وجود دارد یا خیر. البته مزیت این روش هم این است که Cache Hit به نسبت روش‌های دیگه بالاتر خواهد بود. به این مدل از نگاشت حافظه Fully Associative گفته می‌شود.

روش دیگری که میتوان انتخاب کرد به این صورت است که ما حافظه‌ی اصلی را به تعداد ‌Lineهای موجود در Cache تقسیم کنیم و هر بلوک را به یک Line مرتبط کنیم. اگر نیاز به خواندن(نوشتن) داده از بلوکی از حافظه شدیم باید سراغ Line مربوطه‌اش برویم. به این مدل از نگاشت Direct Mapped  می‌گویند. خوبی این روش در زمان جستجوی کوتاه و سادگی پیاده سازی کنترلر Cache است. اما عیبش هم این است که Cache Miss آمارش بالا می‌رود.

مدلی که اغلب برای Cacheها به کار برده می‌شود، چیزی مابین این دو است. مثلا در AN4839 می‌خوانیم که data cache به صورت 4way set associative  است. در این حالت حافظه‌ Cache به دسته‌هایی از Line تقسیم می‌شود که هر دسته شامل ۴ لاین است. حافظه‌ی اصلی هم در اینجا به بلوک‌هایی تقسیم بندی می‌شود اما نه به تعداد Lineهای Cache. بلکه تعداد این بلوک‌ها به تعداد دسته‌های Cache است. با این کار هر بلوک به یک دسته ۴ لاینه در Cache نگاشت می‌شود. هنگامی که یک لاین از حافظه‌ی اصلی خوانده(نوشته) می‌شود باید سراغ دسته مربوطه‌اش در Cache برویم-همانند نگاشت Direct Mapped-. اما در آن دسته می‌تواند به دلخواه در یکی از ۴ لاین ممکن بنشیند-همانند نگاشت Associative-. با این کار هم زمان جستجو در Cache را زیاد بالا نبردیم -فقط قرار است در یکی از ۴ لاین هر دسته جستجو و مقایسه انجام بگیرد- و هم اینکه Cache Miss را به نسبت حالت Direct Mapped تا حد خوبی کاهش دادیم.