نگاشت کش(حافظه پنهان) و انوع نگاشت های کش چیست؟

در این مقاله در مورد انواع نگاشت های حافظه کش (نگاشت مستقیم ، نگاشت کاملا انجمنی ، نگاشت انجمنی جمعی) صحبت خواهیم کرد؛ از این رو اگر با اصطلاحات و واژگان حافظه کش (حافظه پنهان)، سطوح حافظه کش ، حافظه های DRAM ، حافظه های SRAM ، حافظه های eDRAM ، حافظه های eSRAM و مفهایم مرتبط با آن‌ها آشنا نیستید و در مورد آن‌ها اطلاعی ندارید، می‌توانید به لینک‌های زیر مراجعه کنید.

1-1 نگاشت حافظه پنهان [1] (کش)

اگر یک آدرس مشخصی در داخل کش قرار دارد، پردازنده‌ و سیستم‌های کنترلی حافظه‌ی کش می‌بایست به سرعت آن آدرس را تشخیص دهد. در حال حاضر پیکربندی‌های حافظه‌ پنهان (کش) همچنان در حال توسعه است، اما به طور کلی حافظه‌‌های پنهان با سه پیکربندی سنتی کار می‌کنند؛ منظور از پیکربندی سنتی، یعنی سه روش محبوب از نگاشت آدرس‌های حافظه‌ای که برای آدرس‌دهی بلوک‌های ‌حافظه‌ استفاده می‌شوند، این سه روش عبارتند از:

کش با نگاشت مستقیم [2]: برای هر آدرس یک فضای بخصوصی در کش در نظر گرفته شده است.

کش با نگاشت کاملا انجمنی [3]: برای هر آدرس، پردازنده باید کل حافظه‌ی کش را جستجو کند. در این نگاشت داده‌ها به صورت کاملا تصادفی در حافظه‌ی کش قرار می‌گیرند و ذخیره می‌شوند.

کش با نگاشت انجمی جمعی [4]: برای هر آدرس مجموعه‌هایِ کوچکی از بلوک حافظه‌ایِ کش در نظر گرفته شده است. این نگاشت ترکیبی از نگاشت مستقیم و نگاشت کاملا انجمنی است. در این نگاشت، پردازنده، آدرس‌ها را فقط در یکی از مجموعه‌های کوچکی (یا Sets) از بلوک‌های حافظه‌ای جستجو می‌کند.

1-1- نگاشت مستقیم Direct Mapping :

در این روش برای پیاده سازی cache از یک حافظه SRAM سریع استفاده میشود:

اگر حافظه اصلی دارای 2^s کلمه و حافظه cache دارای 2^rکلمه باشند در نتیجه به ترتیب به n و k بیت آدرس نیاز خواهند داشت. آدرس  n بیتی حافظه اصلی بصورت زیر تقسیم می‌شود (شکل1‑1)

شکل‏1‑1 آدرس‌دهی و تعداد بیت‌های لازم در نگاشت مستقیم توسط پردازنده

وقتی که آدرسی توسط CPU تولید میشود با استفاده از قسمت Index آن یک کلمه از حافظه cache خوانده شده و مقدار Tag ذخیره شده در آن با مقدار Tag آدرس مقایسه می‌گردد. اگر دو Tag یکسان بودند داده همانند شکل ‏1‑2، کش مورد استفاده قرار می‌گیرد و به عبارتی Hit انجام می‌شود در غیر اینصورت Miss انجام شده و داده از حافظه خوانده شده و همراه با Tag جدید در cache نوشته می‌شود. در این روش اگر رجوع به آدرسها با index ِ یکسان، زیاد اتفاق بیافتد، درصد موفقیت پایین میاید.

شکل1‑2 جستجوی داده در نگاشت مستقیم توسط پردازنده و کش آن

1-2- نگاشت کاملا انجمنی Associate Mapping :

در این روش که سریعترین راه پیاده سازی یک کش است، از یک حافظه associative استفاده می‌شود. در این حافظه هم آدرس و هم محتوی یک کلمه ذخیره می‌شوند. در نتیجه کش می‌تواند محتوای هر محل از حافظه را ذخیره نماید. (شکل ‏1‑3)

هنگام جستجو برای یک داده آدرس آن به حافظه associative عرضه می‌شود. در صورتیکه ورودی متناظری در حافظه باشد، داده مربوطه در خروجی ظاهر می‌گردد. در غیر اینصورت هر دو آدرس و داده در حافظه associative ذخیره خواهند شد. معمولا از الگوریتم FIFO (فی‌فو)[5] برای جایگزینی در کش استفاده می‌شود.

شکل‏1‑3 آدرس‌دهی و نگاشت کاملا انجمنی توسط پردازنده

1-3- نگاشت Set-associative mapping :

در این روش هر محلی از حافظه‌ی کش می‌تواند چندین کلمه با آدرس Index یکسان را ذخیره نماید. تعداد data-tag های ذخیره شده در حافظه یک set خوانده می‌شود. برای مقایسه tag آدرس تولید شده با مقادیر ذخیره شده از حافظه associative استفاده می‌شود. (شکل ‏1‑4) با بزرگ شدن set ها درصد موفقیت کش افزایش می‌یابد.

شکل‏1‑4 آدرس‌دهی و تعداد بیت‌های لازم در نگاشت انجمنی جمعی توسط پردازنده

برای دسترسی به داده‌های داخل کش و همچنین برای خواندن [9] ، نوشتن [10] و بالانویسی [11] داده‌ها بر روی حافظه‌‌های کش، الگوریتم‌ها و کنترل کننده‌های متعددی استفاده شده است. برای اطلاعات بیشتر می‌توانید به مراجع کتاب‌های درسی ریزپردازنده و معماری کامپیوتر مراجعه کنید.

زیرنوشت

[1] Cache memory mapping

[2] Direct Mapping

[3] Fully associative mapping

[4] Set associative mapping

[5] First in first out

[6] Hit cache

[7] Miss cache

[8] Hit Rate

[9] Read

[10] Write

[11] Overwrite