سلسله‌مراتب حافظه نهان

سلسله‌مراتب کش یا کش‌های چند سطحی به معماری حافظه اطلاق می‌شود که از سلسله‌مراتبی از حافظه‌های ذخیره‌سازی بر اساس سرعت‌های مختلف دسترسی به داده‌های کش استفاده می‌کند. داده‌های پرکاربرد در حافظه‌های پرسرعت ذخیره می‌شوند که امکان دسترسی سریع‌تر توسط هسته‌های واحد پردازش مرکزی (CPU) را فراهم می‌کنند.

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

پیش‌زمینه

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

این منجر به مفهوم حافظه نهان شد که اولین بار توسط موریس ویلکس، دانشمند کامپیوتر بریتانیایی در دانشگاه کمبریج در سال ۱۹۶۵ ارائه شد. او چنین مدل‌های حافظه را «حافظه برده» نامید. تقریباً بین سال‌های ۱۹۷۰ و ۱۹۹۰، مقالاتی از Anant Agarwal, Alan Jay Smith, Mark D. Hill, Thomas R. Puzak و دیگران دربارهٔ طراحی‌های حافظه کش بحث شدند. اولین مدل‌های حافظه نهان در آن زمان پیاده‌سازی شدند، اما حتی زمانی که محققان در حال بررسی و پیشنهاد طرح‌های بهتر بودند، نیاز به حافظه سریع‌تر ادامه داشت. این نیاز از این واقعیت ناشی می‌شود که اگرچه مدل‌های کش اولیه تأخیر دسترسی به داده‌ها را بهبود می‌بخشیدند، با توجه به هزینه و محدودیت‌های فنی، امکان نزدیک شدن ظرفیت حافظه نهان یک سیستم به اندازه ظرفیت حافظه اصلی وجود نداشت. از سال ۱۹۹۰ به بعد، ایده‌هایی مانند افزودن یک سطح کش دیگر (سطح دوم)، به عنوان پشتیبان برای حافظه نهان سطح اول ارائه شد. Jean-Loup Baer, Wen-Hann Wang, Andrew W. Wilson و دیگر محققان تحقیقاتی در مورد این مدل انجام دادند. هنگامی که چندین شبیه‌سازی و پیاده‌سازی مزایای مدل‌های کش دو سطحی را نشان دادند، مفهوم کش چند سطحی به عنوان یک مدل جدید و به‌طور کلی بهتر از حافظه‌های کش مورد توجه قرار گرفت. از سال ۲۰۰۰، مدل‌های کش چند سطحی مورد توجه گسترده قرار گرفته‌اند و در حال حاضر در بسیاری از سیستم‌ها، مانند کش‌های سه سطحی که در محصولات Core i7 اینتل وجود دارند، پیاده‌سازی می‌شوند.

کش چندسطحی

دسترسی به حافظه اصلی برای هر اجرای دستورالعمل ممکن است منجر به پردازش کند شود، با سرعت کلاک که بسته به زمان مورد نیاز برای یافتن و واکشی داده‌ها می‌باشد. به منظور نهان کردن این تأخیر حافظه از پردازنده، از کش داده استفاده می‌شود. هر زمان که داده مورد نیاز پردازنده باشد، از حافظه اصلی گرفته شده و در ساختار حافظه کوچکتر به نام کش که همان حافظه نهان است ذخیره می‌شود. اگر نیاز بیشتری به آن داده وجود داشته باشد، ابتدا قبل از رفتن به حافظه اصلی، حافظه نهان جستجو می‌شود. این ساختار از نظر زمان صرف شده برای جستجو و واکشی داده‌ها با توجه به حافظه اصلی به پردازنده نزدیکتر است. مزایای استفاده از کش را می‌توان با محاسبه میانگین زمان دسترسی (AAT) برای سلسله مراتب حافظه بدون و با کش ثابت کرد.

میانگین زمان دسترسی (AAT)

حافظه نهان، که ظرفیت کوچکی دارد، ممکن است منجر به از دست دادن مکرر شود - زمانی که جستجو در حافظه نهان اطلاعات مورد نظر را برنمی‌گرداند - که منجر به فراخوانی حافظه اصلی برای واکشی داده می‌شود. از این رو، AAT تحت تأثیر نرخ باخت (miss rate) هر ساختاری است که از آن داده‌ها را جستجو می‌کند.

AAT = hit time + ((miss rate) * (miss penalty))

AAT برای حافظه اصلی توسط Hit time _{main memory} داده می‌شود. AAT برای حافظه‌های کش توسط فرمول زیر داده می‌شود:

Hit time _cache + (Miss rate _cache × Miss Penalty _{time taken to go to main memory after missing cache})

زمان برد (Hit time) برای حافظه نهان کمتر از زمان برد برای حافظه اصلی است، بنابراین AAT برای بازیابی داده‌ها در هنگام دسترسی از طریق کش به جای حافظه اصلی، به‌طور قابل توجهی کمتر است.

مبادلات

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

تکامل

در صورت رخ دادن یک باخت (miss) توسط کش، هدف استفاده از چنین ساختاری بی فایده می‌شود و رایانه باید برای واکشی داده‌های مورد نیاز به حافظه اصلی برود. با این حال، با یک کش چند سطحی، اگر کامپیوتر نزدیکترین حافظه نهان به پردازنده (حافظه نهان سطح یک یا L1) را از دست بدهد، سپس در نزدیکترین سطح (های) کش بعدی جستجو می‌کند و تنها در صورتی به حافظه اصلی می‌رود که این سطوح شکست بخورند. روند کلی این است که حافظه نهان L1 کوچک و در فاصله ۱ تا ۲ سیکل ساعت CPU از پردازنده نگه داشته شود. در حالی که در سطوح پایین‌تر ظرفیت بیشتری نسبت به L1 داریم از این رو این سطوح دورتر ولی با نرخ باخت کمتری نسبت به L1 هستند. این منجر به AAT بهتری می‌شود. تعداد سطوح حافظه نهان توسط معماران سخت‌افزار با توجه به نیازهای آنها پس از بررسی معاوضه بین هزینه، AAT و اندازه تعیین و طراحی می‌شوند.

دستاوردهای عملکردی

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

مثال: main memory = 50 ns, L1 = 1 ns with 10% miss rate, L2 = 5 ns with 1% miss rate, L3 = 10 ns with 0.2% miss rate

• بدون کش، AAT = 50 ns
• کش سطح یک (L1): AAT = 1 ns + (۰٫۱ × 50 ns) = 6 ns
• کش دو سطحی (L1-2): AAT = 1 ns + (۰٫۱ × [5 ns + (۰٫۰۱ × 50 ns)]) = 1.55 ns
• کش سه سطحی (L1-3): AAT = 1 ns + (۰٫۱ × [5 ns + (۰٫۰۱ × [10 ns + (۰٫۰۰۲ × 50 ns)])]) = 1.5101 ns

معایب

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

مشخصات

مجزا و یکپارچه

در یک کش مجزا (Banked Cache)، کش به یک حافظه نهان اختصاص داده شده برای ذخیره‌سازی دستورالعمل‌ها و یک کش اختصاص داده شده به داده‌ها تقسیم می‌شود. در مقابل، یک کش یکپارچه (Unified Cache) حاوی دستورالعمل‌ها و داده‌ها در همان کش است. در طول یک فرایند، حافظه نهان L1 (یا سطوح بالاتر نسبت به اتصال به پردازنده) توسط پردازنده برای بازیابی دستورالعمل‌ها و داده‌ها قابل دسترسی است. نیاز به اجرای همزمان هر دو اقدام به چندین پورت و زمان دسترسی بیشتر در یک کش یکپارچه نیاز دارد. داشتن چندین پورت به سخت‌افزار و سیم کشی اضافی نیاز دارد که منجر به ساختار قابل توجهی بین حافظه نهان و واحدهای پردازش می‌شود. برای جلوگیری از این امر، کش L1 اغلب به عنوان یک کش مجزا سازماندهی می‌شود که منجر به پورت‌های کمتر، سخت‌افزار کمتر و به‌طور کلی زمان دسترسی کمتر می‌شود.

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

سیاست‌های شمول

اینکه آیا یک بلوک موجود در لایه کش بالایی می‌تواند در سطح حافظه نهان پایین نیز وجود داشته باشد، توسط خط مشی گنجاندن سیستم حافظه کنترل می‌شود، که ممکن است مشمول (Inclusive)، انحصاری (Exclusive) یا غیر مشمول غیر انحصاری (NINE: Non-Inclusive Non-Exclusive) باشد.

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

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

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

سیاست‌های نوشتن

دو خط مشی وجود دارد که روشی را که در آن یک بلوک کش اصلاح شده در حافظه اصلی بروز می‌شود، تعریف می‌کند: نوشتن همزمان (Write Through) و نوشتن هنگام جایگزینی (Write Back).

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

با این حال، در مورد سیاست نوشتن هنگام جایگزینی، بلوک حافظه نهان تغییر یافته تنها زمانی در سلسله مراتب سطح پایین به روز می‌شود که بلوک حافظه نهان خارج شود. یک «بیت کثیف» (Dirty Bit) به هر بلوک حافظه نهان متصل می‌شود و هر زمان که بلوک کش اصلاح شود تنظیم می‌شود. در طول اخراج، بلوک‌های دارای بیت کثیف تنظیم شده در سلسله مراتب سطح پایین نوشته می‌شوند. تحت این سیاست، خطر از دست رفتن داده وجود دارد، زیرا آخرین نسخه تغییر یافته از یک داده فقط در حافظه نهان ذخیره می‌شود و بنابراین باید برخی از تکنیک‌های اصلاحی را رعایت کرد.

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

ترکیبات رایج این خط‌مشی‌ها عبارتند از "write block", "write allocate", and "write through write no-allocate".

اشتراکی در مقابل اختصاصی

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

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

در پردازنده‌های چند هسته‌ای، انتخاب طراحی برای ایجاد حافظه نهان اشتراکی یا اختصاصی بر عملکرد پردازنده تأثیر می‌گذارد. در عمل، کش سطح بالایی L1 (یا گاهی اوقات L2) به صورت اختصاصی و کش‌های سطح پایین به صورت اشتراکی پیاده‌سازی می‌شوند. این طراحی نرخ دسترسی بالایی را برای کش‌های سطح بالا و نرخ‌های باخت پایین را برای کش‌های سطح پایین فراهم می‌کند.

مدل‌های پیاده‌سازی شده اخیر

IBM POWER7 (2010)

• L1 cache (instruction and data) – each 64-banked, each bank has 2rd+1wr ports 32 kB, 8-way associative, 128B block, write through
• L2 cache – 256 kB, 8-way, 128B block, write back, inclusive of L1, 2 ns access latency
• L3 cache – 8 regions of 4 MB (total 32 MB), local region 6 ns, remote 30 ns, each region 8-way associative, DRAM data array, SRAM tag array

Intel Broadwell microarchitecture (2014)

• L1 cache (instruction and data) – 64 kB per core
• L2 cache – 256 kB per core
• L3 cache – 2 MB to 6 MB shared
• L4 cache – 128 MB of eDRAM (Iris Pro models only)

Intel Kaby Lake microarchitecture (2016)

• L1 cache (instruction and data) – 64 kB per core
• L2 cache – 256 kB per core
• L3 cache – 2 MB to 8 MB shared

AMD Zen microarchitecture (2017)

• L1 cache – 32 kB data & 64 kB instruction per core, 4-way
• L2 cache – 512 kB per core, 4-way inclusive
• L3 cache – 4 MB local & remote per 4-core CCX, 2 CCXs per chiplet, 16-way non-inclusive. Up to 16 MB on desktop CPUs and 64 MB on server CPUs

AMD Zen 2 microarchitecture (2019)

• L1 cache – 32 kB data & 32 kB instruction per core, 8-way
• L2 cache – 512 kB per core, 8-way inclusive
• L3 cache – 16 MB local per 4-core CCX, 2 CCXs per chiplet, 16-way non-inclusive. Up to 64 MB on desktop CPUs and 256 MB on
• server CPUs