حافظه نهان N-Way Set Associative

تحلیل جامع ساختار، عملکرد و پیاده‌سازی

معماری کامپیوتر•سیستم‌های حافظه•۱۴۰۴/۱۰/۱۱

💡 راهنمای استفاده: اصطلاحات فنی در متن با خط نقطه‌چین مشخص شده‌اند.
• روی اصطلاح هاور کنید تا تعریف مختصر ببینید
• کلیک کنید برای مشاهده تعریف کامل، مثال‌ها و جزئیات

۱. مقدمه

۱.۱. ضرورت وجود حافظه نهان

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

معماری Set Associative ترکیبی از دو رویکرد Direct Mapped و Fully Associative است که تعادل بهینه‌ای بین هزینه، پیچیدگی و عملکرد ایجاد می‌کند. این معماری با ارائه انعطاف‌پذیری در نگاشت آدرس‌ها و حفظ سادگی نسبی در پیاده‌سازی، به یکی از رایج‌ترین انواع Cache در پردازنده‌های مدرن تبدیل شده است.

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

هرم سلسله مراتب حافظه - از سریع‌ترین (Registers) تا کندترین (Storage)

مقایسه بصری سرعت و ظرفیت حافظه

Core 0

Core 1

Core 2

Core 3

Core 4

Core 5

Core 6

Core 7

L3 Cache - 36 MB (Shared)

12-Way Set Associative

Memory Controller

I/O Controllers

نمودار ساده‌شده ساختار Die پردازنده - نمایش Cache و هسته‌های پردازشی

۱.۲. مفاهیم پایه حافظه نهان

مفاهیم کلیدی:

• Cache Hit:

زمانی که داده مورد نیاز در Cache موجود باشد و دسترسی سریع انجام شود.

• Cache Miss:

زمانی که داده در Cache نباشد و باید از حافظه اصلی واکشی شود.

• Temporal Locality:

داده‌هایی که اخیراً استفاده شده‌اند احتمالاً دوباره مورد استفاده قرار می‌گیرند.

• Spatial Locality:

داده‌های مجاور به داده‌های اخیراً استفاده‌شده احتمالاً به زودی نیاز خواهند شد.

• Block/Line:

واحد اساسی انتقال داده بین Cache و حافظه اصلی (معمولاً ۶۴ بایت).

• Replacement Policy:

الگوریتم تعیین اینکه در صورت پر بودن Cache، کدام بلوک باید جایگزین شود.

تأخیر دسترسی به Cache در پردازنده‌های مدرن (به سیکل)

L1 Cache

۴-۵ cycles

اندازه: ۳۲-۹۶ KB

سریع‌ترین - مستقیماً به هسته متصل

L2 Cache

۱۲-۱۴ cycles

اندازه: ۲۵۶ KB - ۲ MB

متوسط - اختصاصی هر هسته

L3 Cache

۴۲-۵۰ cycles

اندازه: ۱۶-۳۶ MB

مشترک - بین همه هسته‌ها

حافظه اصلی (DRAM)

۲۰۰-۳۰۰ cycles

اندازه: ۸-۱۲۸ GB | تأخیر: ~۵۰-۷۰ ns

کندترین - تأثیر Cache Miss بسیار بالا

💡 تحلیل عملکرد:

با فرض Cache Hit Rate ۹۵٪ در L1:

• میانگین زمان دسترسی: (۰.۹۵ × ۴) + (۰.۰۵ × ۲۰۰) = ۱۳.۸ cycles
• با Cache Hit Rate ۷۵٪: (۰.۷۵ × ۴) + (۰.۲۵ × ۲۰۰) = ۵۳ cycles
• بدون Cache: ۲۰۰+ cycles برای هر دسترسی!

سلسله مراتب حافظه در معماری مدرن

CPU Registers

<1 cycle

L1 Cache

4-5 cycles | 32-96 KB

L2 Cache

12-14 cycles | 256KB-2MB

L3 Cache

42-50 cycles | 16-36 MB

Main Memory

200-300 cycles | 8-128 GB

50x

L1 سریعتر از RAM

95%

Cache Hit Rate معمولی

15x

بهبود عملکرد با Cache

۱.۳. انواع معماری‌های Cache

Direct Mapped

مزایا: سریع و ساده

معایب: Conflict Miss بالا

کاربرد: L1 Cache های کوچک

Set Associative

مزایا: تعادل خوب

معایب: پیچیدگی متوسط

کاربرد: رایج‌ترین نوع

Fully Associative

مزایا: Miss Rate پایین

معایب: بسیار پیچیده و گران

کاربرد: TLB ها

مقایسه تعاملی Associativity های مختلف

شبیه‌ساز تعاملی Cache Associativity

با تغییر پارامترها تأثیر Associativity بر عملکرد و پیچیدگی را مشاهده کنید

💾اندازه Cache

32 KB

32,768 bytes

📦اندازه Block

64 B

512 bits

🔢تعداد کل Blocks

512

blocks

📍

Direct Mapped

1 Ways512 Sets

زمان دسترسی

64.8

cycles

Hit Rate69%

پیچیدگی سخت‌افزار1/10

🔶

2-Way Set Associative

2 Ways256 Sets

زمان دسترسی

41.2

cycles

Hit Rate81%

پیچیدگی سخت‌افزار2/10

⬛

4-Way Set Associative

4 Ways128 Sets

زمان دسترسی

21.6

cycles

Hit Rate91%

پیچیدگی سخت‌افزار7/10

🟩

8-Way Set Associative

8 Ways64 Sets

زمان دسترسی

9.9

cycles

Hit Rate97%

پیچیدگی سخت‌افزار10/10

🌐

Fully Associative

512 Ways1 Sets

زمان دسترسی

7.9

cycles

Hit Rate98%

پیچیدگی سخت‌افزار10/10

💡نکات کلیدی

• Direct Mapped: ساده‌ترین و سریع‌ترین اما کمترین Hit Rate
• N-Way: تعادل بین عملکرد و پیچیدگی - انتخاب محبوب CPUها
• Fully Associative: بهترین Hit Rate اما پیچیده‌ترین و گران‌ترین
• Cache بزرگتر = Hit Rate بهتر | Block کوچکتر = انعطاف‌پذیری بیشتر

۲. ساختار معماری

۲.۱. سازماندهی حافظه

در معماری N-Way Set Associative، حافظه نهان به مجموعه‌ای از Set ها تقسیم می‌شود. هر Set شامل N تا Way (راه) است که هر کدام می‌توانند یک بلوک از حافظه اصلی را ذخیره کنند. این ساختار امکان می‌دهد یک آدرس حافظه در N مکان مختلف درون یک Set قرار گیرد.

پارامترهای اصلی:

Number of Sets (S):تعداد Set های موجود در Cache
Associativity (N):تعداد Way ها در هر Set
Block Size (B):اندازه هر بلوک Cache به بایت
Cache Size:S × N × B بایت

۲.۲. ساختار آدرس

هر آدرس حافظه به سه بخش اصلی تقسیم می‌شود:

Tag

برای شناسایی یکتای بلوک در Set استفاده می‌شود. در مرحله مقایسه (Comparison) بررسی می‌شود.

Bits: [31:log₂(S×B)]

Set Index

مشخص می‌کند بلوک در کدام Set باید جستجو شود. تعیین‌کننده مکان Set است.

Bits: [log₂(S×B)-1:log₂(B)]

Block Offset

آدرس بایت مورد نظر در داخل بلوک را مشخص می‌کند. برای دسترسی به داده درون بلوک.

Bits: [log₂(B)-1:0]

۲.۳. نگاشت آدرس به Cache

Memory Block to Cache Set Mapping

Main Memory

Block 0

Block 1

Block 2

Block 3

Block 4

Block 5

Block 6

Block 7

Block 8

Block 9

Block 10

Block 11

Block 12

Block 13

Block 14

Block 15

4-Way Set Associative Cache

Set 0

(way 0)

(way 1)

(way 2)

(way 3)

Set 1

(way 0)

(way 1)

(way 2)

(way 3)

Set 2

(way 0)

(way 1)

(way 2)

(way 3)

Set 3

(way 0)

(way 1)

(way 2)

(way 3)

Set Index = (Block Address) mod (Number of Sets)

تأثیر Cache Hit Rate بر عملکرد

Cache Hit Rate95%

Cache Hits

95%

Cache Misses

14.8

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

92.6%

بهبود عملکرد

فرمول: Average Access Time = Hit Rate × Hit Time + Miss Rate × Miss Penalty

Hit Time = 5 cycles (L1 Cache) | Miss Penalty = 200 cycles (Main Memory)

فرمول نگاشت:

Set Index = (Block Address) mod (Number of Sets)

بلوک‌هایی با فاصله Number of Sets در حافظه اصلی، به یک Set نگاشت می‌شوند.

۳. عملیات دسترسی

۳.۱. فرآیند خواندن (Read)

استخراج Set Index

بخش Set Index از آدرس استخراج شده و Set مورد نظر شناسایی می‌شود.

مقایسه موازی Tag ها

Tag آدرس با Tag همه Way های معتبر (Valid=1) در Set به‌صورت موازی مقایسه می‌شود. این عملیات توسط N Comparator انجام می‌شود.

تصمیم‌گیری Hit/Miss

Cache Hit: یکی از Tag ها مطابقت داشت → داده از Way مربوطه خوانده می‌شود

Cache Miss: هیچ Tag ای مطابقت نداشت → بلوک از حافظه اصلی واکشی می‌شود

جایگزینی در صورت Miss

در صورت Cache Miss و پر بودن همه Way ها، یکی از Way ها بر اساس سیاست جایگزینی (مثلاً LRU) انتخاب و جایگزین می‌شود.

۴. سیاست‌های جایگزینی

زمانی که Cache Miss رخ می‌دهد و همه Way های یک Set پر هستند، باید یکی از بلوک‌ها جایگزین شود. سیاست جایگزینی تعیین می‌کند کدام بلوک باید حذف شود.

۴.۱. الگوریتم LRU (Least Recently Used)

LRU (Least Recently Used) Replacement Policy

Current Cache Set State

Last Access: T-4

Newer

Last Access: T-2

Older

Last Access: T-7

Newest

Last Access: T-1

Oldest (LRU)

Replace ↓

After Replacement (New Block X)

Newer

Older

Newest

New Block

مشخصات LRU:

بلوکی که مدت زمان بیشتری از آخرین دسترسی آن گذشته، جایگزین می‌شود
نیاز به نگهداری اطلاعات زمان دسترسی برای هر Way
پیچیدگی سخت‌افزاری: O(N log N) بیت برای هر Set
عملکرد مناسب برای الگوهای دسترسی زمانی

۴.۲. سایر الگوریتم‌ها

FIFO (First-In-First-Out)

قدیمی‌ترین بلوک وارد شده به Cache جایگزین می‌شود.

✓ پیاده‌سازی ساده‌تر

✓ هزینه سخت‌افزاری کمتر

✗ عملکرد ضعیف‌تر از LRU

Random Replacement

یک Way به‌صورت تصادفی برای جایگزینی انتخاب می‌شود.

✓ ساده‌ترین پیاده‌سازی

✓ هزینه سخت‌افزاری بسیار کم

~ عملکرد غیرقابل پیش‌بینی

LFU (Least Frequently Used)

بلوکی که کمترین تعداد دسترسی را داشته جایگزین می‌شود.

✓ مناسب الگوهای تکراری

✗ نیاز به Counter برای هر Way

✗ مشکل با تغییر الگوی دسترسی

Pseudo-LRU

تقریبی از LRU با پیچیدگی کمتر.

✓ عملکرد نزدیک به LRU

✓ هزینه کمتر (N-1 بیت)

→ رایج در پردازنده‌های مدرن

مقایسه بصری سازماندهی Cache

Direct Mapped (1-Way)

Set 0

Set 1

Set 2

Set 3

یک مکان ثابت برای هر آدرس

2-Way Set Associative

Way 0

Way 1

Way 0

Way 1

Way 0

Way 1

Way 0

Way 1

دو مکانممکن در هر Set

Fully Associative

هر بلوک در هر مکانی قابل ذخیره

💡 نکته: افزایش Associativity منجر به کاهش Conflict Miss می‌شود اما پیچیدگی سخت‌افزار و مصرف انرژی را افزایش می‌دهد. اکثر پردازنده‌های مدرن از 4-Way تا 16-Way Set Associative استفاده می‌کنند.

۵. تحلیل عملکرد

۵.۱. معیارهای ارزیابی

Hit Rate

Hit Rate = (Number of Hits) / (Total Accesses) × 100%

درصد دسترسی‌هایی که داده در Cache یافت می‌شود

Miss Rate

Miss Rate = 1 - Hit Rate = (Number of Misses) / (Total Accesses) × 100%

Average Memory Access Time (AMAT)

AMAT = Hit Time + (Miss Rate × Miss Penalty)

میانگین زمان دسترسی به حافظه با در نظر گرفتن Cache

۵.۲. تاثیر Associativity

Associativity	Miss Rate (نسبی)	پیچیدگی سخت‌افزار	زمان دسترسی
Direct Mapped (1-way)	بالا	کم	سریع
2-way	متوسط-بالا	متوسط-کم	متوسط-سریع
4-way	متوسط (بهینه)	متوسط (بهینه)	متوسط (بهینه)
8-way	متوسط-پایین	متوسط-بالا	متوسط-کند
Fully Associative	پایین	بالا	کند

نکته کلیدی:

در اکثر پردازنده‌های مدرن، 4-way یا 8-way set associative به عنوان تعادل بهینه بین عملکرد، پیچیدگی و توان مصرفی انتخاب می‌شود. افزایش Associativity بیش از این مقادیر معمولاً بهبود قابل توجهی در Hit Rate ایجاد نمی‌کند.

۶. شبیه‌ساز تعاملی

از شبیه‌ساز زیر برای درک بهتر نحوه عملکرد Cache استفاده کنید. آدرس‌های مختلف را وارد کرده و تغییرات در Cache و آمار Hit/Miss را مشاهده نمایید.

شبیه‌ساز تعاملی Cache

تعداد Set ها

تعداد Way ها

اندازه Block

16 بایت

Hit

Miss

کل دسترسی

Hit Rate

0.00%

Set	Way 0			Way 1			Way 2			Way 3
	V	Tag	Data	V	Tag	Data	V	Tag	Data	V	Tag	Data
0	0	-	-	0	-	-	0	-	-	0	-	-
1	0	-	-	0	-	-	0	-	-	0	-	-
2	0	-	-	0	-	-	0	-	-	0	-	-
3	0	-	-	0	-	-	0	-	-	0	-	-

راهنمای استفاده:

آدرس‌ها را به فرمت هگزادسیمال وارد کنید (مثال: 0x1A4، 0x2F8)
رنگ سبز نشان‌دهنده Cache Hit و رنگ قرمز Cache Miss است
ستون V (Valid bit) نشان می‌دهد آیا Way معتبر است یا خیر
الگوریتم جایگزینی LRU پیاده‌سازی شده است
برای تست بهتر، آدرس‌های با فاصله منظم را امتحان کنید

۷. نتیجه‌گیری

معماری N-Way Set Associative Cache یکی از مهم‌ترین نوآوری‌ها در طراحی سیستم‌های حافظه مدرن است. این معماری با ایجاد تعادل بین انعطاف‌پذیری Fully Associative و سادگی Direct Mapped، امکان دستیابی به عملکرد بالا با پیچیدگی سخت‌افزاری قابل قبول را فراهم می‌کند.

انتخاب مقدار مناسب N (Associativity) بستگی به موارد زیر دارد:

الگوی دسترسی به حافظه در برنامه‌های هدف
محدودیت‌های توان مصرفی و مساحت تراشه
فرکانس کاری مورد نیاز
سطح Cache (L1، L2، L3)

در پردازنده‌های امروزی، معمولاً L1 Cache از 4-way یا 8-way، و L2/L3 از 8-way یا 16-way associativity استفاده می‌کنند.

واژه‌نامه اصطلاحات فنی

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

اصطلاحات اساسی Cache

Cache (حافظه نهان)

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

Hit / Miss

Cache Hit: داده مورد نیاز در Cache موجود است → دسترسی سریع
Cache Miss: داده در Cache نیست → باید از RAM یا حافظه پایین‌تر بخواند → کند
Hit Rate: درصد دفعاتی که داده در Cache پیدا می‌شود (بالاتر = بهتر)
مثال: Hit Rate 95% یعنی از هر 100 دسترسی، 95 بار در Cache موجود است.

Registers (ثبات / رجیسترها)

تعریف: سریع‌ترین و کوچک‌ترین حافظه داخل CPU که مستقیماً توسط دستورات استفاده می‌شود.
سرعت: دسترسی در کمتر از 1 سیکل
اندازه: معمولاً چند ده تا صد رجیستر با اندازه 32 یا 64 بیت
نمونه: EAX, EBX در x86، R0-R31 در RISC-V

DRAM (Dynamic Random Access Memory)

تعریف: حافظه اصلی سیستم (RAM) که برنامه‌ها و داده‌های فعال را نگه می‌دارد.
ویژگی: بزرگ (گیگابایت‌ها) ولی نسبتاً کند (200-300 سیکل)
انواع: DDR3, DDR4, DDR5
تفاوت با Cache: Cache سریع ولی کوچک، DRAM بزرگ ولی کند

Storage (حافظه جانبی)

تعریف: حافظه دائمی برای ذخیره فایل‌ها (HDD, SSD).
ویژگی: خیلی کند (هزاران سیکل) ولی بسیار بزرگ (ترابایت‌ها) و دائمی
کاربرد: ذخیره سیستم‌عامل، برنامه‌ها، فایل‌های کاربر
نکته: برای استفاده باید ابتدا به RAM لود شود.

انواع Associativity

Direct-Mapped Cache

تعریف: هر بلوک حافظه فقط یک مکان مشخص در Cache دارد (1-way associative).
مزایا: بسیار ساده و سریع، هزینه کم
معایب: Conflict Miss زیاد - دو آدرس مختلف ممکن است همدیگر را از Cache بیرون بزنند
کاربرد: Cache های بسیار کوچک یا سیستم‌های ساده

Set-Associative Cache (N-Way)

تعریف: هر بلوک حافظه می‌تواند در N مکان مختلف درون یک Set قرار گیرد.
مثال: 4-way یعنی هر بلوک 4 جای ممکن دارد
مزایا: تعادل خوب بین سرعت و Miss Rate، انعطاف‌پذیری متوسط
کاربرد: رایج‌ترین نوع - L1, L2, L3 اکثر پردازنده‌ها

Fully-Associative Cache

تعریف: هر بلوک حافظه می‌تواند در هر مکان Cache قرار گیرد (بدون محدودیت Set).
مزایا: کمترین Conflict Miss، بهترین Hit Rate
معایب: خیلی پیچیده، گران، کند - باید همه Entry ها را مقایسه کند
کاربرد: فقط برای Cache های خیلی کوچک مثل TLB (Translation Lookaside Buffer)

Way (راه)

تعریف: هر کدام از مکان‌های موازی درون یک Set که می‌توانند داده ذخیره کنند.
مثال: در 4-way Cache، هر Set دارای 4 Way است
اندازه: N در N-way associative نشان‌دهنده تعداد Way است
نتیجه: Way بیشتر = انعطاف بیشتر = Conflict Miss کمتر

Set (مجموعه)

تعریف: گروهی از Way ها که یک بلوک حافظه می‌تواند در آن‌ها قرار گیرد.
شناسایی: Set Index از آدرس حافظه تعیین می‌کند بلوک به کدام Set می‌رود
مثال: Cache با 256 Set و 4-way → 256 گروه × 4 مکان = 1024 Cache Line کل
فرمول: Set Index = (Block Address) mod (Number of Sets)

ساختار آدرس‌دهی Cache

Tag (برچسب)

تعریف: بخشی از آدرس که برای شناسایی یکتای بلوک داده در یک Set استفاده می‌شود.
کاربرد: بررسی این‌که آیا داده موجود در Cache همان داده مورد نظر است یا خیر
مقایسه: در مرحله Cache Lookup، Tag ذخیره شده با Tag آدرس درخواستی مقایسه می‌شود
نتیجه: اگر Tag ها یکسان باشند → Hit، وگرنه → Miss

Set Index (شاخص مجموعه)

تعریف: بخشی از آدرس که مشخص می‌کند بلوک باید به کدام Set برود.
محاسبه: Set Index = آدرس بلوک mod تعداد Set ها
مثال: اگر 256 Set داشته باشیم، از 8 بیت میانی آدرس استفاده می‌شود (2^8=256)
نکته: همه بلوک‌هایی که Set Index یکسان دارند، رقیب هم هستند

Block Offset (جابجایی بلوک)

تعریف: بخشی از آدرس که مشخص می‌کند بایت مورد نظر در کدام قسمت از Cache Block قرار دارد.
مثال: اگر هر بلوک 64 بایت باشد، 6 بیت پایینی آدرس برای Offset است (2^6=64)
کاربرد: بعد از پیدا کردن بلوک در Cache، با Offset بایت دقیق را پیدا می‌کنیم
Byte Offset: برای انتخاب بایت خاص درون یک Word

Cache Line / Block

تعریف: واحد کوچکترین داده‌ای که در Cache ذخیره و جابجا می‌شود.
اندازه معمول: 64 بایت در پردازنده‌های مدرن
دلیل: به جای انتقال یک بایت، یک بلوک کامل منتقل می‌شود (Spatial Locality)
مثال: وقتی آدرس 1000 را می‌خوانیم، بلوک 1000-1063 وارد Cache می‌شود

Valid Bit

تعریف: بیتی که نشان می‌دهد آیا داده موجود در یک Cache Line معتبر است یا خیر.
حالت‌ها: 1 = داده معتبر، 0 = داده نامعتبر یا خالی
کاربرد: در ابتدای سیستم همه Valid Bit ها 0 هستند (Cache خالی)
نتیجه: حتی اگر Tag مطابقت داشته باشد، اگر Valid Bit = 0 باشد، Miss است

Dirty Bit

تعریف: بیتی که نشان می‌دهد آیا داده Cache تغییر کرده و با حافظه اصلی متفاوت است.
حالت‌ها: 1 = داده Modified (کثیف)، باید به حافظه نوشته شود، 0 = داده Clean (تمیز)
کاربرد: در Write-Back Cache - فقط وقتی Dirty Bit = 1 باشد، قبل از جایگزینی به حافظه می‌نویسیم
فایده: کاهش نوشتن غیرضروری به حافظه اصلی

الگوریتم‌های جایگزینی

LRU (Least Recently Used)

تعریف: جایگزین کردن بلوکی که مدت زمان طولانی‌تری از آخرین استفاده آن گذشته است.
منطق: بلوکی که زمان زیادی استفاده نشده، احتمالاً در آینده نزدیک هم استفاده نمی‌شود
پیاده‌سازی: نگهداری شمارنده یا timestamp برای هر Cache Line
کاربرد: رایج‌ترین الگوریتم در L1, L2 Cache های مدرن
مثال: اگر 4 بلوک A, B, C, D داشته باشیم و B آخرین بار 100 سیکل پیش استفاده شده، B حذف می‌شود

FIFO (First In, First Out)

تعریف: جایگزین کردن قدیمی‌ترین بلوک (اولین بلوکی که وارد Cache شده).
منطق: مثل صف - اولی که آمده، اولی که می‌رود
مزیت: بسیار ساده و ارزان - فقط یک شمارنده ساده لازم است
مشکل: ممکن است بلوک پرکاربرد را حذف کند

Random Replacement

تعریف: انتخاب تصادفی یکی از بلوک‌ها برای جایگزینی.
مزیت: بسیار ساده، بدون نیاز به نگهداری اطلاعات اضافی
عملکرد: جالب این‌که گاهی نزدیک به LRU عمل می‌کند
کاربرد: سیستم‌هایی که سادگی بیشتر از کارایی اهمیت دارد

LFU (Least Frequently Used)

تعریف: جایگزین کردن بلوکی که کمترین تعداد دفعات استفاده را داشته است.
پیاده‌سازی: نگهداری شمارنده استفاده برای هر بلوک
مشکل: بلوکی که در گذشته زیاد استفاده شده ولی دیگر لازم نیست، ماندگار می‌ماند
کاربرد: کمتر رایج، معمولاً در کاربردهای خاص

سیاست‌های نوشتن (Write Policies)

Write-Through

تعریف: هر نوشتن به Cache همزمان به حافظه اصلی هم نوشته می‌شود.
مزیت: Cache و حافظه همیشه همگام هستند - داده‌ها ایمن‌تر
معایب: کند - هر نوشتن نیاز به دسترسی به حافظه اصلی دارد
بهینه‌سازی: استفاده از Write Buffer برای کاهش تأخیر

Write-Back

تعریف: نوشتن فقط در Cache انجام می‌شود، بعداً (هنگام جایگزینی) به حافظه نوشته می‌شود.
مزیت: سریع - نوشتن‌های متوالی به همان مکان فقط یک بار به حافظه می‌روند
معایب: پیچیده‌تر - نیاز به Dirty Bit، خطر از دست رفتن داده در صورت خرابی
کاربرد: رایج در L1, L2 Cache پردازنده‌های مدرن

Write-Allocate

تعریف: در Write Miss، بلوک از حافظه به Cache آورده می‌شود و سپس نوشتن انجام می‌شود.
منطق: احتمالاً به زودی دوباره به این بلوک نیاز خواهیم داشت
ترکیب: معمولاً با Write-Back استفاده می‌شود

No-Write-Allocate (Write-Around)

تعریف: در Write Miss، بلوک به Cache نمی‌آید و مستقیماً به حافظه اصلی نوشته می‌شود.
مزیت: Cache Pollution کمتر برای داده‌هایی که فقط یک بار نوشته می‌شوند
ترکیب: معمولاً با Write-Through استفاده می‌شود

انواع Cache Miss

Compulsory Miss (Cold Miss)

تعریف: اولین بار که به یک بلوک دسترسی می‌شود، حتماً Miss است (چون هنوز در Cache نیست).
دلیل: Cache در ابتدا خالی است
راه‌حل: اجتناب‌ناپذیر - فقط با Prefetching قابل کاهش
مثال: اولین بار که برنامه اجرا می‌شود، همه دسترسی‌ها Miss هستند

Capacity Miss

تعریف: بلوک قبلاً در Cache بوده ولی به دلیل پر بودن Cache از آن خارج شده است.
دلیل: Working Set برنامه بزرگ‌تر از اندازه Cache است
راه‌حل: افزایش اندازه Cache یا بهینه‌سازی برنامه برای استفاده بهتر از Cache
مثال: کار با آرایه 10 مگابایتی در Cache 256 کیلوبایتی

Conflict Miss

تعریف: چند بلوک مختلف به یک Set نگاشت می‌شوند و همدیگر را بیرون می‌زنند (با وجود فضای خالی در Cache).
دلیل: محدودیت Associativity - بلوک‌ها نمی‌توانند در Set دلخواه قرار گیرند
راه‌حل: افزایش Associativity (مثلاً از 4-way به 8-way) یا تغییر الگوی دسترسی
مثال: در Direct-Mapped، دو آدرس با Set Index یکسان همیشه رقیب هستند

Coherence Miss

تعریف: در سیستم‌های چندهسته‌ای، بلوک به دلیل تغییر توسط هسته دیگر Invalid شده است.
دلیل: پروتکل Coherency (مثل MESI) برای حفظ سازگاری بین Cache ها
کاربرد: فقط در سیستم‌های multicore با Shared Memory

مفاهیم اصلی Locality

Temporal Locality (محلی‌سازی زمانی)

تعریف: اگر به یک داده دسترسی پیدا کردیم، احتمالاً در آینده نزدیک دوباره به آن نیاز داریم.
مثال: متغیرهای حلقه (loop counter)، توابع پرکاربرد
استفاده در Cache: داده‌های اخیراً استفاده شده در Cache نگه داشته می‌شوند
نمونه کد: for (i=0; i<1000; i++) - متغیر i هزاران بار استفاده می‌شود

Spatial Locality (محلی‌سازی مکانی)

تعریف: اگر به یک آدرس دسترسی پیدا کردیم، احتمالاً به آدرس‌های نزدیک آن هم نیاز داریم.
مثال: آرایه‌ها، دستورات متوالی برنامه
استفاده در Cache: به جای یک بایت، یک Cache Line کامل (64 بایت) منتقل می‌شود
نمونه کد: arr[0], arr[1], arr[2], ... - دسترسی متوالی به عناصر آرایه

واحدهای زمانی

Cycle (سیکل ساعت)

تعریف: کوچک‌ترین واحد زمانی در پردازنده - یک تیک ساعت CPU.
مدت زمان: وابسته به فرکانس پردازنده - مثلاً در 3 GHz، هر سیکل ≈ 0.33 نانوثانیه
کاربرد: اندازه‌گیری سرعت دسترسی به Cache و حافظه
مثال: L1 Cache: 4 سیکل یعنی 4 تیک ساعت CPU طول می‌کشد

Latency (تأخیر / زمان انتظار)

تعریف: زمانی که از درخواست داده تا دریافت آن می‌گذرد.
واحد: معمولاً بر حسب سیکل یا نانوثانیه
مقایسه: L1: 4-5 سیکل، L2: 12-15 سیکل، L3: 40-50 سیکل، DRAM: 200-300 سیکل
اهمیت: کاهش Latency یکی از اهداف اصلی طراحی Cache است

منابع و مراجع

1. Hennessy, J. L., & Patterson, D. A. (2017). Computer Architecture: A Quantitative Approach (6th ed.). Morgan Kaufmann.

2. Patterson, D. A., & Hennessy, J. L. (2020). Computer Organization and Design RISC-V Edition (2nd ed.). Morgan Kaufmann.

3. Intel Corporation. (2023). Intel® 64 and IA-32 Architectures Optimization Reference Manual.

4. AMD. (2022). Software Optimization Guide for AMD Family 19h Processors.