راهنمای جامع پردازنده های (Intel و AMD) | تشخیص نسل CPU، معنی پسوندها، مقایسه قدرت، انتخاب بهترین پردازنده و کاربرد هر مدل

Cache Coherence چیست؟

چرا Cache Coherence لازم است؟

فرض کنید در RAM
متغیری با مقدار:

X = 10

وجود دارد.

Core 0
و Core 1
هر دو این داده را
داخل Cache خود می خوانند.

Core 0 Cache
→
X = 10

Core 1 Cache
→
X = 10

سپس Core 0
مقدار X را
به 20 تغییر می دهد.

Core 0
→
X = 20

اگر هیچ مکانیزم هماهنگی
وجود نداشته باشد،
Core 1 ممکن است
همچنان:

X = 10

را معتبر بداند.

این همان مشکلی است
که Coherence Protocol
باید مدیریت کند.

چرا Coherence روی Cache Line کار می کند؟

Cache
معمولاً داده را
به صورت Byte منفرد
مدیریت نمی کند.

واحد پایه انتقال
و مدیریت Cache:

Cache Line

است.

در بسیاری از CPUهای مدرن،
اندازه رایج Cache Line:

64 Bytes

است،
هرچند این مقدار
یک قانون جهانی برای تمام معماری ها نیست.

Coherence نیز معمولاً
وضعیت را در سطح
Cache Line دنبال می کند.

MESI چیست؟

حالت Modified چیست؟

اگر Cache Line
در وضعیت:

Modified

باشد،
داده توسط این Cache
تغییر کرده است
و نسخه موجود در Memory
ممکن است قدیمی تر باشد.

Cache
→
New Data

Memory
→
Older Data

این Line
باید در زمان مناسب
به سطح پایین تر حافظه
Write Back شود.

حالت Exclusive چیست؟

در وضعیت:

Exclusive

Cache Line معتبر است
و این Cache
تنها دارنده نسخه Cache شده
آن Line محسوب می شود.

همچنین داده هنوز
نسبت به نسخه Memory
تغییر نکرده است.

حالت Shared چیست؟

در وضعیت:

Shared

Cache Line معتبر است،
اما Cacheهای دیگری نیز
می توانند نسخه ای
از همان Line
داشته باشند.

Core 0 Cache
→
Shared Line

Core 1 Cache
→
Shared Line

حالت Invalid چیست؟

اگر Cache Line
در وضعیت:

Invalid

باشد،
داده موجود در آن Line
دیگر نباید
به عنوان نسخه معتبر
استفاده شود.

اگر Core
دوباره به آن داده نیاز داشته باشد،
باید نسخه معتبر
را از محل مناسب
دریافت کند.

وقتی دو Core یک Line مشترک دارند و یکی می خواهد آن را تغییر دهد چه اتفاقی می افتد؟

فرض کنید Core 0
و Core 1
هر دو نسخه ای
از یک Cache Line دارند.

Core 0
→
Shared

Core 1
→
Shared

حال Core 0
می خواهد داده
داخل Line را تغییر دهد.

Core 0
باید ابتدا حق نوشتن
روی Line را به دست آورد.

نسخه Core 1
باید نامعتبر شود.

Core 0
→
Modified

Core 1
→
Invalid

Cache Invalidation چیست؟

Cache Line Ownership چیست؟

برای اینکه یک Core
بتواند Line را تغییر دهد،
باید وضعیت مناسبی
برای نوشتن
روی آن Line داشته باشد.

به صورت مفهومی
می توان گفت
Core باید:

Ownership

آن Cache Line
را به دست آورد.

اگر Core دیگری
نسخه قابل استفاده
از Line داشته باشد،
Protocol باید
وضعیت آن نسخه
را هماهنگ کند.

Read For Ownership چیست؟

یکی از عملیات مهم
در سیستم های Coherent:

RFO
=
Read For Ownership

است.

وقتی Core
قصد نوشتن
روی یک Cache Line
را دارد،
ممکن است درخواست کند
Line را با حق Ownership
دریافت کند.

این عملیات
می تواند باعث
Invalid شدن نسخه های دیگر شود.

Cache-to-Cache Transfer چیست؟

همیشه لازم نیست
داده ابتدا
به DRAM نوشته شود
و سپس Core دیگر
آن را از DRAM بخواند.

در برخی معماری ها
داده می تواند
از Cache مرتبط
به Core دیگر
تامین شود.

Core 0 Cache
→
Interconnect
→
Core 1 Cache

این فرآیند
می تواند از مراجعه
غیرضروری به DRAM
جلوگیری کند.

Snooping چیست؟

برای مثال
اگر Core 0
درخواست Ownership
یک Line را بدهد،
Core 1 ممکن است
متوجه شود
نسخه ای از همان Line
را در Cache دارد.

Protocol
سپس وضعیت Line
را بر اساس قواعد معماری
تغییر می دهد.

Core 0 Ownership Request
→
Coherence System
→
Core 1 Copy Invalidated

Directory-based Coherence چیست؟

در سیستم های بزرگ،
Broadcast کردن
هر درخواست Coherence
به تمام Agentها
می تواند پرهزینه باشد.

یک روش مقیاس پذیرتر
استفاده از:

Directory-based Coherence

است.

Directory
اطلاعاتی درباره محل
نسخه های Cache شده
یک Line نگه می دارد.

در نتیجه
درخواست Coherence
می تواند هدفمندتر
ارسال شود.

Coherence Traffic چیست؟

پیام ها و انتقال هایی
که برای هماهنگ نگه داشتن
Cacheها ایجاد می شوند:

Coherence Traffic

نامیده می شوند.

این ترافیک
می تواند شامل:

• درخواست Ownership،
• Invalidation،
• Cache Line Transfer،
• Snoop Request،
• Snoop Response،
• و پیام های وضعیت

باشد.

آیا اشتراک داده فقط برای Write مشکل ایجاد می کند؟

چند Core
می توانند داده ای
را فقط بخوانند
و نسخه های Shared
آن را در Cache
نگه دارند.

تا زمانی که
هیچ Core
قصد تغییر Line را نداشته باشد،
چنین اشتراکی
معمولاً هزینه Coherence
بسیار کمتری
نسبت به Write Sharing دارد.

Read Sharing
→
Usually Cheap

Frequent Write Sharing
→
Potentially Expensive

False Sharing چیست؟

یک مثال ساده از False Sharing

فرض کنید دو Counter داریم:

Counter_A

Counter_B

Thread 0
فقط Counter_A
را تغییر می دهد.

Thread 1
فقط Counter_B
را تغییر می دهد.

از نظر منطقی
هیچ داده مشترکی وجود ندارد.

اما اگر هر دو Counter
داخل یک Cache Line باشند:

One Cache Line
=
Counter_A
+
Counter_B

هر Write
می تواند Ownership
کل Cache Line
را تغییر دهد.

Cache Line Ping-Pong چیست؟

در False Sharing شدید،
Ownership یک Cache Line
ممکن است مرتباً
میان Coreها جابه جا شود.

Core 0
→
Ownership
→
Core 1
→
Ownership
→
Core 0
→
Ownership

به این رفتار
به صورت غیررسمی:

Cache Line Ping-Pong

گفته می شود.

Padding چگونه می تواند False Sharing را کاهش دهد؟

یکی از تکنیک ها
این است که داده هایی
که توسط Threadهای مختلف
مرتباً نوشته می شوند،
روی Cache Lineهای جداگانه
قرار گیرند.

برای این کار
ممکن است از:

Padding
/
Alignment

استفاده شود.

Cache Line 0
→
Counter_A

Cache Line 1
→
Counter_B

البته Padding
مصرف حافظه را افزایش می دهد
و نباید بدون Profiling
به صورت افراطی استفاده شود.

True Sharing با False Sharing چه تفاوتی دارد؟

Atomic Operation چه ارتباطی با Cache Coherence دارد؟

عملیات Atomic
باید طوری اجرا شود
که سایر Threadها
وضعیت نیمه تمام
عملیات را مشاهده نکنند.

برای اجرای بسیاری
از Atomic Operationها،
CPU از مکانیزم های:

• Cache Coherence،
• Cache Line Ownership،
• Memory Ordering،
• و دستورهای Atomic

استفاده می کند.

بنابراین Atomic
الزاماً به معنی
قفل کردن کل Memory Bus
نیست.

Cache Coherence و Memory Consistency یک چیز هستند؟

خیر.

این دو مفهوم
به یکدیگر مرتبط هستند،
اما مسئله یکسانی
را حل نمی کنند.

Coherence
بیشتر درباره هماهنگی
نسخه های یک Memory Location
میان Cacheهاست.

Memory Consistency
درباره قواعد مشاهده
ترتیب عملیات حافظه
در سطح گسترده تر است.

Cache Coherence
→
Which Value?

Memory Consistency
→
In What Observable Order?

Cache Coherence چه ارتباطی با NUMA دارد؟

در سیستم چندسوکته،
Cache Line
ممکن است میان Coreهایی
در NUMA Nodeهای مختلف
به اشتراک گذاشته شود.

در این حالت
پیام های Coherence
ممکن است از
Inter-Socket Interconnect
عبور کنند.

Socket 0 Core
↔
Inter-Socket Link
↔
Socket 1 Core

بنابراین False Sharing
یا Shared Writeهای شدید
می توانند در سیستم NUMA
هزینه بیشتری داشته باشند.

Cache Coherence در CPUهای Chiplet-based چگونه اهمیت پیدا می کند؟

در پردازنده Chiplet-based،
Coreها ممکن است
روی Dieهای مختلف
قرار داشته باشند.

Fabric داخلی CPU
باید انتقال داده
و پیام های Coherence
را میان این بخش ها
مدیریت کند.

Compute Die A
↔
Coherent Fabric
↔
Compute Die B

معماری دقیق
در پردازنده های مختلف
متفاوت است.

Shared Last-Level Cache چه کمکی می کند؟

بسیاری از CPUها
سطحی از Cache
را میان چند Core
به اشتراک می گذارند.

این Cache
می تواند در:

• اشتراک داده،
• کاهش مراجعه به DRAM،
• مدیریت انتقال Cache Line،
• و پیاده سازی ساختار Coherence

نقش داشته باشد.

نحوه دقیق این نقش
به معماری CPU
وابسته است.

Inclusive و Non-Inclusive Cache چه ارتباطی با Coherence دارند؟

رابطه میان سطح های Cache
می تواند در معماری های مختلف
متفاوت باشد.

در برخی طراحی ها،
Last-Level Cache
اطلاعاتی درباره Lineهای
موجود در Cacheهای خصوصی
نگه می دارد.

در برخی طراحی های دیگر،
ساختارهای Directory
یا Metadata جداگانه
برای Tracking
استفاده می شوند.

بنابراین صرف دانستن
اندازه L3 Cache
برای فهم رفتار Coherence
کافی نیست.

چرا افزایش تعداد Core طراحی Coherence را سخت می کند؟

با افزایش تعداد Core،
تعداد Cacheهای خصوصی
و تعداد مصرف کنندگان
داده مشترک افزایش می یابد.

اگر هر Core
مجبور باشد
تمام تراکنش های تمام Coreهای دیگر
را بررسی کند،
Scaling دشوار می شود.

4 Cores
→
Limited Coherence Domain

64+ Cores
→
Much Larger Coherence Problem

به همین دلیل
CPUهای بزرگ
از Fabric،
Directory،
Hierarchy
و روش های پیچیده تر
برای مدیریت Coherence
استفاده می کنند.

Cache Coherence در Server چرا مهم تر می شود؟

Serverها ممکن است
ده ها یا صدها Thread
فعال داشته باشند.

Workloadهایی مانند:

• Database،
• Virtualization،
• Web Server،
• In-Memory Processing،
• Scientific Computing،
• و Data Analytics

می توانند داده مشترک زیادی
میان Threadها داشته باشند.

در چنین شرایطی
Data Structure Design
و Thread Placement
اهمیت زیادی پیدا می کنند.

Database چگونه می تواند Coherence Traffic ایجاد کند؟

Database Engine
ممکن است ساختارهای مشترکی مانند:

• Lock Table،
• Queue،
• Shared Counter،
• Buffer Metadata،
• Transaction State،
• و Index Metadata

داشته باشد.

اگر تعداد زیادی Thread
مرتباً این ساختارها
را تغییر دهند،
Cache Lineهای مربوط
می توانند بسیار Hot شوند.

Hot Cache Line چیست؟

اصطلاح:

Hot Cache Line

معمولاً برای Lineای
استفاده می شود
که تعداد زیادی Core
مرتباً به آن دسترسی دارند
یا آن را تغییر می دهند.

یک Counter مشترک جهانی
می تواند نمونه ساده ای
از چنین Lineای باشد.

چرا Per-Thread Data می تواند سریع تر باشد؟

یکی از روش های کاهش
Shared Write
این است که هر Thread
نسخه محلی خودش
از برخی داده ها
را داشته باشد.

Thread 0
→
Local Counter 0

Thread 1
→
Local Counter 1

Thread 2
→
Local Counter 2

سپس در زمان مناسب
نتایج با یکدیگر
ترکیب شوند.

این روش
می تواند تعداد Writeهای
روی Cache Line مشترک
را کاهش دهد.

چرا Read-Mostly Data برای سیستم چند هسته ای مناسب تر است؟

اگر تعداد زیادی Core
داده ای را بخوانند
اما به ندرت تغییر دهند،
Cacheها می توانند
نسخه های Shared
را نگه دارند.

مشکل اصلی
زمانی افزایش می یابد
که همان داده
مرتباً نوشته شود.

Many Readers
+
Few Writers
→
Usually Easier to Scale

Many Writers
→
More Coherence Pressure

چرا Multithreading همیشه با افزایش Core سریع تر نمی شود؟

اگر Threadها
مستقل باشند،
افزایش Core
می تواند Parallelism
را بالا ببرد.

اما اگر Threadها
مرتباً داده مشترک
را تغییر دهند،
بخشی از زمان
صرف Synchronization
و Coherence می شود.

More Threads
+
Shared Writable Data
→
More Coordination Cost

به همین دلیل
Speedup برنامه های Parallel
همیشه خطی نیست.

SMT و Hyper-Threading چه ارتباطی با Cache Coherence دارند؟

Threadهای منطقی
روی یک Physical Core
معمولاً بسیاری از منابع
همان Core را
به اشتراک می گذارند.

بنابراین ارتباط آنها
با Cache
با دو Thread
روی دو Core مستقل
یکسان نیست.

Coherence
بیشتر زمانی مطرح می شود
که نسخه های یک Cache Line
در ساختارهای Cache مستقل
قرار گرفته باشند.

جزئیات دقیق
به Microarchitecture
وابسته است.

آیا GPU هم مسئله Coherence دارد؟

GPUها نیز
Hierarchy حافظه و Cache
دارند،
اما مدل Coherence
آنها الزاماً
مانند CPU نیست.

همچنین در سیستم هایی
که CPU و GPU
حافظه یا Address Space
را به شکل نزدیک تری
به اشتراک می گذارند،
مسئله Coherence
پیچیده تر می شود.

معماری دقیق
به پلتفرم
و نوع Accelerator
بستگی دارد.

DMA چه ارتباطی با Cache Coherence دارد؟

همان طور که در فصل PCIe دیدیم،
Device می تواند
از DMA
برای خواندن یا نوشتن Memory
استفاده کند.

اگر CPU
نسخه Cache شده
از همان داده داشته باشد،
سیستم باید مطمئن شود
CPU و Device
داده سازگاری مشاهده می کنند.

نحوه انجام این کار
به معماری سیستم
و نوع I/O Coherency
بستگی دارد.

I/O Coherence چیست؟

در برخی پلتفرم ها،
Deviceها
می توانند در یک Domain
هماهنگ تر با Cacheهای CPU
فعالیت کنند.

این مفهوم:

I/O Coherence

می تواند نیاز
به برخی عملیات نرم افزاری
برای هماهنگ کردن
CPU Cache و Device Memory Access
را کاهش دهد.

اما مدل دقیق Coherency
میان پلتفرم ها
متفاوت است.

آیا برنامه نویس باید MESI را مستقیماً مدیریت کند؟

معمولاً خیر.

MESI و Protocolهای مشابه
در سطح سخت افزار
مدیریت می شوند.

برنامه نویس
بیشتر باید به:

• Data Layout،
• Synchronization،
• Atomic Operations،
• Memory Model،
• False Sharing،
• Thread Placement،
• و Data Locality

توجه کند.

آیا تمام CPUها دقیقاً از MESI ساده استفاده می کنند؟

خیر.

MESI
مدل پایه بسیار خوبی
برای یادگیری مفهوم
Cache Coherence است،
اما معماری های واقعی
می توانند حالت ها
و Optimizationهای بیشتری
داشته باشند.

نمونه هایی از توسعه های شناخته شده:

MESIF

MOESI

هستند.

جزئیات پیاده سازی
میان خانواده های مختلف CPU
متفاوت است.

حالت Owned در MOESI چه مفهومی دارد؟

برخی Protocolها
حالت:

Owned

را اضافه می کنند.

این حالت
به صورت کلی
اجازه می دهد
یک Cache
مسئول نسخه تغییر یافته داده باشد،
در حالی که Cacheهای دیگر
می توانند نسخه Shared
آن را داشته باشند.

جزئیات دقیق
به Protocol
و Microarchitecture
بستگی دارد.

حالت Forward در MESIF چه کاربردی دارد؟

در MESIF
حالت:

Forward

می تواند یکی از Cacheها
را به عنوان پاسخ دهنده ترجیحی
برای Line مشترک
مشخص کند.

این کار
می تواند پاسخ دهی
به برخی درخواست ها
را سازمان یافته تر کند.

چگونه مشکلات Coherence را پیدا کنیم؟

از روی Task Manager
یا درصد CPU
به تنهایی
نمی توان False Sharing
را با اطمینان تشخیص داد.

معمولاً به:

• Hardware Performance Counters،
• CPU Profilers،
• Memory Access Analysis،
• Cache Miss Metrics،
• Coherence Events،
• و Thread Scaling Tests

نیاز است.

نشانه های احتمالی مشکل Coherence چیست؟

برخی نشانه ها
می توانند شامل:

• Scaling ضعیف با افزایش Thread،
• Performance بهتر با Thread کمتر،
• حساسیت شدید به Thread Affinity،
• ترافیک بالای Cache-to-Cache،
• Remote HITهای زیاد در سیستم NUMA،
• Hot Cache Line،
• و افزایش Latency در Shared Data Structures

باشند.

این علائم
به تنهایی اثبات کننده نیستند
و باید با Profiling
بررسی شوند.

چگونه می توان Coherence Overhead را کاهش داد؟

راهکار دقیق
به نرم افزار بستگی دارد،
اما اصول رایج شامل:

• کاهش Shared Writable Data،
• استفاده از Per-Thread Data در صورت مناسب بودن،
• کاهش False Sharing،
• استفاده صحیح از Alignment،
• تقسیم Dataset میان Workerها،
• کاهش Global Counterهای پرتکرار،
• Batch کردن Updateها،
• کاهش Synchronization غیرضروری،
• بهبود Thread Affinity،
• و توجه به NUMA Locality

هستند.

چرا Batch کردن Updateها می تواند مفید باشد؟

فرض کنید هر Thread
بعد از هر عملیات
یک Counter جهانی
را Update کند.

این کار
می تواند Ownership Transfer
زیادی ایجاد کند.

روش دیگر
این است که Thread
ابتدا چند Update
را محلی جمع کند
و سپس نتیجه
را یکجا اضافه کند.

Many Shared Updates
→
One Batched Shared Update

در برخی Workloadها
این روش
Coherence Traffic
را به میزان زیادی کاهش می دهد.

آیا هنگام خرید CPU باید نوع Coherence Protocol را مقایسه کنیم؟

برای خریدار عادی،
معمولاً خیر.

مقایسه مستقیم:

MESI
vs
MOESI
vs
MESIF

معیار مناسبی
برای انتخاب CPU نیست.

Performance واقعی
نتیجه مجموعه بزرگی
از عوامل است:

• Microarchitecture،
• Core Count،
• Cache Hierarchy،
• Interconnect،
• Memory Subsystem،
• Clock،
• Scheduler Behavior،
• و Workload.

Cache Coherence برای Workstation چه زمانی مهم می شود؟

در Workstationهای
دارای تعداد Core زیاد،
Workloadهای Multithreaded
می توانند تحت تاثیر
الگوی اشتراک داده قرار گیرند.

نمونه ها:

• رندر CPU،
• Simulation،
• Compilation،
• Scientific Computing،
• پردازش داده،
• و برخی Engineهای تولید محتوا.

البته میزان حساسیت
هر نرم افزار
متفاوت است.

آیا کاربر عادی باید Cache Coherence را تنظیم کند؟

خیر.

Cache Coherence
توسط سخت افزار
و سیستم عامل
مدیریت می شود.

کاربر عادی
نیازی به تنظیم MESI
یا Cache Line Stateها ندارد.

اهمیت شناخت این موضوع
بیشتر برای:

• درک معماری CPU،
• تحلیل Performance،
• برنامه نویسی Multithreaded،
• Server Optimization،
• Database Engineering،
• و طراحی سیستم های مقیاس پذیر

است.

Memory Ordering چیست؟

یک مثال ساده

فرض کنید یک Thread
دو عملیات زیر را انجام دهد:

Data = 100

Ready = 1

برنامه نویس ممکن است
انتظار داشته باشد
وقتی Thread دیگر
مقدار Ready را برابر 1 دید،
حتماً Data نیز
مقدار 100 داشته باشد.

اما بدون قواعد مناسب
Synchronization،
این نتیجه را نمی توان
در تمام Memory Modelها
صرفاً از روی ترتیب متن برنامه
فرض کرد.

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

چرا CPU اصلاً عملیات را Reorder می کند؟

اگر پردازنده مجبور بود
هر دستور را
کاملاً به ترتیب
و فقط پس از پایان دستور قبلی
اجرا کند،
بخش زیادی از توان
سخت افزار مدرن
بلااستفاده می ماند.

CPU تلاش می کند
زمان های انتظار را
با انجام کارهای مستقل
پنهان کند.

Memory Stall
→
Independent Work
→
Better Utilization

این همان فلسفه ای است
که پشت بسیاری از تکنیک های
Out-of-Order Execution
قرار دارد.

Load و Store چیستند؟

به صورت ساده:

Load
=
Read Data From Memory Hierarchy

Store
=
Write Data To Memory Hierarchy

اما در یک CPU مدرن،
Load و Store
فقط عملیات ساده
«خواندن از RAM»
و «نوشتن در RAM»
نیستند.

آنها از ساختارهای داخلی
متعددی عبور می کنند
و معمولاً با Cache
سروکار دارند.

مسیر کلی Load و Store در CPU

به صورت مفهومی
می توان مسیر را چنین دید:

Instruction
→
Address Generation
→
Load / Store Unit
→
Cache Hierarchy
→
Memory System

البته جزئیات
در هر Microarchitecture
متفاوت است.

Load/Store Unit چیست؟

Store Buffer چیست؟

عملیات Store
ممکن است نتواند
همان لحظه
تمام مسیر نوشتن
در Cache و سیستم حافظه
را کامل کند.

CPU می تواند
Store را موقتاً
در ساختاری مانند:

Store Buffer

نگه دارد
و اجرای دستورهای بعدی
را ادامه دهد.

Load Queue چیست؟

CPU باید Loadهای
در حال اجرا
و ارتباط آنها
با Storeهای قبلی
را دنبال کند.

ساختاری مانند:

Load Queue

برای Tracking
عملیات Load
استفاده می شود.

جزئیات دقیق
به معماری پردازنده
وابسته است.

Store Queue چیست؟

Store Queue
اطلاعات مربوط
به Storeهای در حال پردازش
را نگه می دارد.

CPU باید بداند:

• Store به چه آدرسی مربوط است،
• چه داده ای باید نوشته شود،
• آیا Store آماده Commit شدن است،
• و آیا Load بعدی به همان آدرس وابسته است.

Memory Dependency چیست؟

اگر دو عملیات حافظه
به یک Location
دسترسی داشته باشند،
ترتیب آنها
ممکن است برای نتیجه برنامه
مهم باشد.

برای مثال:

Store X = 10

Load X

Load نباید
به اشتباه
مقدار قدیمی X
را به عنوان نتیجه نهایی
دریافت کند.

Memory Disambiguation چیست؟

Speculative Load چیست؟

در برخی شرایط
CPU ممکن است
یک Load را
قبل از مشخص شدن کامل
وضعیت Storeهای قدیمی تر
به صورت Speculative
اجرا کند.

Predict No Dependency
→
Execute Load Early

اگر بعداً مشخص شود
Dependency وجود داشته،
CPU باید نتیجه اشتباه
را اصلاح کند.

Memory Order Violation چیست؟

اگر CPU
یک Load را
بر اساس حدس استقلال
زودتر اجرا کند
و بعداً مشخص شود
Store قبلی
به همان Address مربوط بوده،
Speculation اشتباه بوده است.

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

Wrong Memory Dependency Prediction
→
Violation Detected
→
Replay / Recovery

Store-to-Load Forwarding چیست؟

فرض کنید CPU
مقداری را Store کرده،
اما آن Store هنوز
تمام مسیر خود
را کامل نکرده است.

سپس همان Core
مقدار همان Address
را Load می کند.

CPU ممکن است
داده را مستقیماً
از Store Buffer
یا ساختار مرتبط
به Load تحویل دهد.

Store Buffer
→
Forward Data
→
Younger Load

این تکنیک:

Store-to-Load Forwarding

نامیده می شود.

چه نوع Reorderingهایی مطرح هستند؟

هنگام مطالعه Memory Model
معمولاً ترکیب هایی مانند
موارد زیر بررسی می شوند:

Load → Load

Load → Store

Store → Load

Store → Store

معماری های مختلف
درباره اینکه کدام ترتیب ها
باید حفظ شوند
و کدام ها می توانند
از دید نرم افزار Relax شوند،
قوانین متفاوتی دارند.

Strong و Weak Memory Ordering یعنی چه؟

به صورت آموزشی،
معماری هایی که
محدودیت بیشتری
روی Reordering قابل مشاهده
اعمال می کنند
معمولاً Stronger
در نظر گرفته می شوند.

معماری هایی که
آزادی بیشتری
برای Reordering دارند
به Synchronization صریح تری
از طرف نرم افزار
نیاز دارند.

Stronger Ordering
→
Fewer Observable Reorderings

Weaker Ordering
→
More Allowed Reorderings

x86 و ARM از نظر Memory Ordering چه تفاوتی دارند؟

خانواده x86
معمولاً Memory Model
نسبتاً قوی تری
نسبت به بسیاری از معماری های
Weakly Ordered
ارائه می دهد.

معماری هایی مانند ARM
در بسیاری از موارد
آزادی بیشتری
برای Ordering
فراهم می کنند.

اما این مقایسه
نباید به این برداشت
تبدیل شود که:

x86
=
No Reordering

چنین چیزی صحیح نیست.

هر معماری
Memory Model رسمی
و دستورهای Synchronization
مخصوص خود را دارد.

Memory Barrier چیست؟

Fence چیست؟

Fence
اصطلاح رایجی
برای دستور یا مکانیزمی است
که مرزی
میان گروه هایی
از عملیات حافظه
ایجاد می کند.

Memory Operations Before Fence
→
Fence
→
Memory Operations After Fence

نوع دقیق تضمین
به نوع Fence
و معماری CPU
بستگی دارد.

آیا همه Fenceها یکسان هستند؟

خیر.

برخی معماری ها
انواع مختلفی
از Barrier
برای Load و Store
ارائه می دهند.

به صورت مفهومی
ممکن است با مواردی مانند:

Load Fence

Store Fence

Full Memory Fence

روبه رو شویم.

Acquire چیست؟

Acquire
نوعی Ordering Semantic
است که معمولاً
هنگام دریافت
یک وضعیت Synchronization
استفاده می شود.

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

Acquire
→
Subsequent Operations

Release چیست؟

Release
معمولاً هنگام انتشار
یک وضعیت
برای Thread دیگر
استفاده می شود.

عملیات حافظه قبلی
باید طبق قواعد
Memory Model
پیش از Release
به شکل لازم
Ordered شوند.

Previous Operations
→
Release

Acquire و Release چگونه با هم کار می کنند؟

یک Thread
می تواند داده ای را آماده کند
و سپس با Release
وضعیت آماده بودن
را منتشر کند.

Thread دیگر
با Acquire
آن وضعیت
را دریافت می کند.

Thread A
→
Write Data
→
Release

Thread B
→
Acquire
→
Read Data

این الگو
یکی از مفاهیم پایه
در Synchronization مدرن است.

Atomic Operation چیست؟

چرا افزایش ساده یک Counter الزاماً Atomic نیست؟

دستور سطح بالا:

Counter++

ممکن است از نظر مفهومی
شامل چند مرحله باشد:

Load Counter
→
Add 1
→
Store Counter

اگر دو Thread
این مراحل را
بدون Synchronization مناسب
همزمان انجام دهند،
ممکن است Update
یکی از آنها از بین برود.

Lost Update چیست؟

فرض کنید:

Counter = 10

Thread A
مقدار 10 را می خواند.

Thread B نیز
مقدار 10 را می خواند.

هر دو
یک واحد اضافه می کنند
و مقدار 11
را می نویسند.

نتیجه:

Expected = 12

Actual = 11

یکی از Updateها
عملاً گم شده است.

Read-Modify-Write چیست؟

بسیاری از Atomic Operationها
از نوع:

Read
→
Modify
→
Write

هستند.

تفاوت مهم
این است که سخت افزار
و Memory Model
تضمین می کنند
این عملیات
با Atomicity لازم
انجام شود.

Compare-and-Swap چیست؟

مثال ساده Compare-and-Swap

فرض کنید:

X = 10

عملیات می گوید:

Compare X With 10

If Equal
→
X = 20

اگر در فاصله
Thread دیگری X را تغییر داده باشد،
Compare شکست می خورد
و نرم افزار
می تواند تصمیم دیگری بگیرد
یا عملیات را Retry کند.

CAS Loop چیست؟

برخی الگوریتم های
Lock-Free
از الگویی شبیه:

Read
→
Calculate New Value
→
Compare-and-Swap
→
Retry If Failed

استفاده می کنند.

اگر Thread دیگری
داده را تغییر داده باشد،
CAS شکست می خورد
و عملیات دوباره
تلاش می شود.

Fetch-and-Add چیست؟

یکی دیگر از
Atomic Primitiveهای رایج:

Fetch-and-Add

است.

این عملیات
مقدار فعلی را دریافت می کند
و همزمان
مقدار مشخصی
به آن اضافه می کند.

برای Counterهای Atomic
کاربرد زیادی دارد.

Atomic Operation چه ارتباطی با Cache Coherence دارد؟

برای تغییر Atomic
یک داده Cache شده،
Core معمولاً
باید کنترل مناسب
روی Cache Line مربوط
داشته باشد.

Coherence Protocol
کمک می کند
Coreهای دیگر
نتوانند همزمان
نسخه ناسازگار
از همان Line
را تغییر دهند.

Atomic RMW
→
Cache Line Ownership
→
Coherence Coordination

Lock چه ارتباطی با Atomic Operation دارد؟

بسیاری از Lockها
در سطح پایین
با استفاده از
Atomic Primitiveها
ساخته می شوند.

برای مثال
یک Lock ساده
می تواند با
Compare-and-Swap
وضعیت:

Unlocked
→
Locked

را به صورت Atomic
تغییر دهد.

Spinlock چیست؟

Spinlock
نوعی Lock است
که Thread
به جای Sleep کردن،
مرتباً وضعیت Lock
را بررسی می کند.

Check Lock
→
Busy
→
Check Again
→
Busy
→
Check Again

برای انتظارهای بسیار کوتاه
ممکن است مفید باشد،
اما استفاده نامناسب
می تواند CPU Time
و Coherence Traffic
زیادی مصرف کند.

Mutex چیست؟

Mutex
مکانیزمی برای
Mutual Exclusion است.

یعنی در یک لحظه
فقط Thread مجاز
وارد Critical Section
شود.

One Owner
→
Critical Section

پیاده سازی Mutex
معمولاً ترکیبی
از Primitiveهای سخت افزاری
و امکانات سیستم عامل است.

Critical Section چیست؟

Critical Section
بخشی از برنامه است
که به داده یا منبع مشترک
دسترسی دارد
و باید تحت قواعد
Synchronization مناسب
اجرا شود.

اگر چند Thread
بدون هماهنگی صحیح
وارد چنین بخشی شوند،
Race Condition
ممکن است ایجاد شود.

Race Condition چیست؟

Data Race چیست؟

تعریف دقیق Data Race
به Memory Model
زبان برنامه نویسی
وابسته است.

به صورت کلی،
وقتی چند Thread
بدون Synchronization مناسب
به یک Memory Location
دسترسی دارند
و حداقل یکی از دسترسی ها
Write است،
ممکن است با Data Race
روبه رو شویم.

Data Race
و Race Condition
مفاهیم مرتبط
اما کاملاً مترادف نیستند.

فقط CPU می تواند عملیات را Reorder کند؟

خیر.

Compiler نیز
برای Optimization
می تواند ترتیب عملیات
را تغییر دهد،
به شرطی که
قواعد زبان
و رفتار قابل مشاهده برنامه
نقض نشوند.

Source Code
→
Compiler Optimization
→
Machine Instructions
→
CPU Execution

بنابراین در برنامه نویسی Concurrent
هم Compiler
و هم CPU
باید در نظر گرفته شوند.

آیا volatile مشکل Memory Ordering را حل می کند؟

پاسخ به زبان برنامه نویسی
بستگی دارد.

واژه:

volatile

در زبان های مختلف
معنی یکسانی ندارد.

برای مثال،
مفهوم volatile در C و C++
با Java
یکسان نیست.

بنابراین نباید
volatile را
یک راه حل عمومی
برای Multithreading
در تمام زبان ها دانست.

Memory Model چیست؟

Memory Model سخت افزار و زبان برنامه نویسی چه تفاوتی دارند؟

CPU
یک Memory Model
در سطح ISA
ارائه می دهد.

اما زبان هایی مانند:

C++
/
Java
/
Rust

نیز قواعد Concurrent
مخصوص خود را دارند.

Compiler باید
کد سطح بالا
را به دستورهایی تبدیل کند
که هم قواعد زبان
و هم قواعد معماری CPU
را رعایت کنند.

Sequential Consistency چیست؟

Sequential Consistency
یک مدل مفهومی مهم
برای فهم Concurrent Execution است.

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

One Global Interleaving
+
Per-Thread Program Order

مدل های واقعی
ممکن است تضمین های
ضعیف تری ارائه دهند
تا Performance بیشتری
امکان پذیر شود.

Happens-Before چیست؟

در Memory Modelهای
زبان های مدرن،
رابطه ای مانند:

Happens-Before

برای بیان
Ordering منطقی
میان عملیات استفاده می شود.

اگر عملیات A
طبق قواعد زبان
Happens-Before
عملیات B باشد،
نرم افزار می تواند
تضمین های مشخصی
درباره Visibility
و Ordering داشته باشد.

Synchronizes-With چیست؟

در برخی Memory Modelها،
عملیات Synchronization
می توانند رابطه:

Synchronizes-With

ایجاد کنند.

این رابطه
می تواند بخشی
از زنجیره ای باشد
که Happens-Before
را ایجاد می کند.

الگوی Message Passing چگونه کار می کند؟

یکی از مثال های کلاسیک:

Thread A:
Data = 100
→
Release Ready = 1

Thread B:
Acquire Ready
→
Read Data

اگر Synchronization
طبق Memory Model
صحیح انجام شود،
Thread B
بعد از مشاهده Ready
می تواند داده منتشر شده
توسط Thread A
را طبق تضمین های مربوط
مشاهده کند.

تفاوت Cache Coherence و Memory Ordering چیست؟

Lock-Free Programming چیست؟

Lock-Free
به الگوریتم هایی گفته می شود
که برای پیشرفت سیستم
به Mutex سنتی
وابسته نیستند.

آنها معمولاً
از Atomic Primitiveهایی مانند:

Compare-and-Swap

Fetch-and-Add

استفاده می کنند.

اما Lock-Free
الزاماً به معنی
ساده تر یا سریع تر بودن
در همه شرایط نیست.

Wait-Free چه تفاوتی با Lock-Free دارد؟

این دو اصطلاح
تضمین پیشرفت متفاوتی دارند.

در Lock-Free
سیستم به طور کلی
باید پیشرفت کند،
اما یک Thread خاص
ممکن است چند بار
Retry شود.

در Wait-Free
هدف قوی تر است:
هر عملیات باید
در تعداد محدودی مرحله
پیشرفت کند.

ABA Problem چیست؟

در الگوریتم های مبتنی بر CAS،
ممکن است Thread
مقدار A را بخواند.

سپس Thread دیگری
مقدار را:

A
→
B
→
A

تغییر دهد.

Thread اول
فقط مقدار فعلی A
را می بیند
و ممکن است تصور کند
هیچ تغییری رخ نداده است.

این مسئله:

ABA Problem

نامیده می شود.

آیا استفاده زیاد از Atomicها می تواند مشکل ساز شود؟

بله.

Atomic Operation
ابزار ضروری
برای Concurrent Programming است،
اما اگر تعداد زیادی Thread
مرتباً یک Location مشترک
را Atomic Update کنند،
همان Location
می تواند نقطه Contention شود.

More Threads
+
One Shared Atomic
≠
Linear Scaling

Sharding یک Counter چگونه کمک می کند؟

به جای یک Counter جهانی:

Global Counter

می توان در برخی طراحی ها
چند Counter محلی
ایجاد کرد.

Counter 0
→
Worker 0

Counter 1
→
Worker 1

Counter 2
→
Worker 2

سپس نتایج
در زمان مناسب
Aggregate شوند.

این روش
می تواند Contention
روی یک Cache Line
را کاهش دهد.

سیستم عامل چه نقشی دارد؟

Kernel
برای ساخت:

• Locks،
• Scheduler Data Structures،
• Interrupt Handling،
• Device Drivers،
• Reference Counters،
• و ارتباط میان Coreها

به Atomic Operation
و Memory Barrier
وابسته است.

بدون این Primitiveها،
ساخت یک Kernel
چند هسته ای قابل اعتماد
بسیار دشوار خواهد بود.

Memory Ordering در Device Driver چرا مهم است؟

Driver
ممکن است ابتدا
داده ای را در Memory
آماده کند
و سپس Register
یک Device را تغییر دهد.

اگر Ordering مناسب
رعایت نشود،
Device ممکن است
Notification را
قبل از آماده شدن
کامل داده مشاهده کند.

Prepare Descriptor
→
Memory Barrier
→
Notify Device

جزئیات دقیق
به Platform
و Device Model
بستگی دارد.

DMA و Memory Ordering چه ارتباطی دارند؟

Deviceهایی که از DMA
استفاده می کنند
می توانند مستقیماً
با Memory System
تعامل داشته باشند.

CPU و Driver
باید طبق قواعد پلتفرم
مطمئن شوند
داده پیش از شروع DMA
در وضعیت مناسب قرار دارد
و نتیجه DMA
پیش از مصرف توسط CPU
به شکل صحیح
قابل مشاهده است.

Memory Ordering در Database چه اهمیتی دارد؟

Database Engineهای مدرن
ممکن است هزاران عملیات
Concurrent
را مدیریت کنند.

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

• Lock Manager،
• Buffer Pool Metadata،
• Transaction State،
• Queues،
• Reference Counters،
• و Concurrent Index Structures

به Synchronization صحیح
نیاز دارند.

چرا این موضوع در Server مهم تر می شود؟

هرچه تعداد Core
و Thread بیشتر شود،
احتمال تعامل
با داده مشترک
نیز بیشتر می شود.

در Serverهای بزرگ،
طراحی نامناسب
Synchronization
می تواند باعث:

• Lock Contention،
• Atomic Contention،
• Cache Line Ping-Pong،
• Coherence Traffic،
• و Scaling ضعیف

شود.

آیا کاربر عادی باید Memory Barrier را تنظیم کند؟

خیر.

این مکانیزم ها
توسط CPU،
Compiler،
سیستم عامل
و نرم افزار
مدیریت می شوند.

کاربر هنگام خرید
لپ تاپ،
کامپیوتر،
Workstation
یا Server
گزینه ای به نام
Memory Barrier
تنظیم نمی کند.

شناخت این مفاهیم
برای فهم عمیق تر
معماری CPU
و رفتار نرم افزار
اهمیت دارد.

Branch چیست؟

Conditional Branch چیست؟

Conditional Branch
به نتیجه یک شرط
وابسته است.

برای مثال:

if (x > 10)

اگر شرط برقرار باشد،
CPU یک مسیر
و اگر برقرار نباشد،
مسیر دیگری را دنبال می کند.

Condition
→
True Path / False Path

Taken و Not Taken یعنی چه؟

در یک Branch شرطی،
معمولاً دو نتیجه اصلی مطرح است.

Taken
=
Jump To Branch Target

Not Taken
=
Continue Sequential Execution

Predictor باید حدس بزند
Branch در اجرای فعلی
Taken خواهد شد
یا Not Taken.

چرا CPU نمی تواند فقط منتظر نتیجه Branch بماند؟

از نظر فنی می تواند،
اما Performance
به شدت کاهش پیدا می کند.

نتیجه Branch
ممکن است چند Stage
بعد از Fetch
مشخص شود.

اگر Front-End
تا آن زمان متوقف بماند،
دستورهای جدیدی
وارد Pipeline نمی شوند.

Unknown Branch
→
Stop Fetching
→
Pipeline Bubbles
→
Lost Performance

Branch Prediction
برای جلوگیری از همین توقف
طراحی شده است.

Branch Predictor چیست؟

یک مثال ساده از پیش بینی Branch

فرض کنید برنامه
یک Loop دارد
که 1000 بار اجرا می شود.

Branch انتهای Loop
در بیشتر دفعات
به ابتدای Loop برمی گردد.

Iteration 1
→
Taken

Iteration 2
→
Taken

…

Iteration 999
→
Taken

Final Iteration
→
Not Taken

این رفتار
نسبتاً قابل پیش بینی است.

Static Branch Prediction چیست؟

ساده ترین روش
استفاده از یک قانون ثابت
برای پیش بینی Branch است.

برای مثال:

Always Predict Taken

یا:

Always Predict Not Taken

این روش ساده است،
اما رفتار واقعی برنامه
را به خوبی
یاد نمی گیرد.

Dynamic Branch Prediction چیست؟

Dynamic Predictor
از رفتار گذشته Branchها
برای پیش بینی آینده
استفاده می کند.

Previous Behavior
→
Predictor State
→
Future Prediction

اگر یک Branch
در اجراهای اخیر
تقریباً همیشه Taken بوده باشد،
Predictor می تواند
از این History
استفاده کند.

One-Bit Predictor چگونه کار می کند؟

یک مدل آموزشی ساده
می تواند فقط نتیجه قبلی Branch
را نگه دارد.

Last Time = Taken
→
Predict Taken

Last Time = Not Taken
→
Predict Not Taken

این روش
از Static Prediction بهتر است،
اما با یک تغییر موقت
سریعاً جهت پیش بینی
را عوض می کند.

Two-Bit Saturating Counter چیست؟

یک روش کلاسیک
استفاده از چند حالت
به جای یک Bit ساده است.

Strongly Taken

Weakly Taken

Weakly Not Taken

Strongly Not Taken

در این حالت
یک نتیجه متفاوت
الزاماً جهت پیش بینی
را فوراً تغییر نمی دهد.

این نوع Hysteresis
می تواند Predictor
را در برابر تغییرات موقتی
مقاوم تر کند.

Branch History چیست؟

Predictorهای پیشرفته
فقط نتیجه قبلی
یک Branch را بررسی نمی کنند.

آنها می توانند
الگوی چند Branch قبلی
را نیز در نظر بگیرند.

T
→
T
→
N
→
T
→
?

چنین Historyهایی
می توانند الگوهای
پیچیده تر برنامه
را آشکار کنند.

Local Branch History چیست؟

Local History
رفتار گذشته
همان Branch مشخص
را دنبال می کند.

برای مثال،
اگر یک Branch
الگویی مانند:

Taken
→
Taken
→
Not Taken

را مرتب تکرار کند،
Predictor می تواند
از History همان Branch
استفاده کند.

Global Branch History چیست؟

نتیجه یک Branch
گاهی به Branchهای قبلی
برنامه وابسته است.

Global History
رفتار چند Branch اخیر
را به صورت یک Context
در نظر می گیرد.

Recent Branch Outcomes
→
Global History
→
Prediction Context

Branch Target Buffer چیست؟

Direction Prediction و Target Prediction چه تفاوتی دارند؟

Predictor باید
در بسیاری از Branchها
دو سؤال را پاسخ دهد.

سؤال اول:

Taken Or Not Taken?

سؤال دوم:

If Taken, Where?

اولی Direction Prediction
و دومی Target Prediction
است.

Return Address Stack چیست؟

Function Callها
معمولاً پس از پایان تابع
باید به محل فراخوانی
بازگردند.

پردازنده می تواند
برای پیش بینی Returnها
از ساختاری مانند:

Return Address Stack

یا RAS استفاده کند.

هنگام Call،
Return Address
در این ساختار
دنبال می شود
و هنگام Return
برای پیش بینی مقصد
مورد استفاده قرار می گیرد.

Indirect Branch چیست؟

در Direct Branch
مقصد معمولاً
از خود Instruction
قابل استخراج است.

اما در Indirect Branch،
مقصد می تواند
از Register
یا داده دیگری
به دست آید.

Indirect Branch
→
Multiple Possible Targets

پیش بینی چنین Branchهایی
می تواند دشوارتر باشد.

Virtual Functionها چه ارتباطی با Branch Prediction دارند؟

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

اگر یک Call Site
در زمان های مختلف
به مقصدهای متفاوت
هدایت شود،
Predictor باید
Target مناسب
را حدس بزند.

به همین دلیل
رفتار Callهای غیرمستقیم
می تواند روی Front-End Performance
اثر بگذارد.

Speculative Execution چیست؟

اگر پیش بینی درست باشد چه اتفاقی می افتد؟

اگر Predictor
مسیر صحیح را حدس زده باشد،
CPU از قبل
روی دستورهای مفید
کار کرده است.

Correct Prediction
→
Useful Speculation
→
Pipeline Continues

این همان حالتی است
که Branch Prediction
ارزش واقعی خود
را نشان می دهد.

Branch Misprediction چیست؟

Pipeline Flush چیست؟

وقتی Branch Misprediction
مشخص می شود،
دستورهای وابسته
به مسیر اشتباه
باید از جریان موثر اجرا
حذف شوند.

Wrong Path
→
Detect Misprediction
→
Squash Wrong Instructions
→
Redirect Fetch

در توضیحات عمومی
این فرآیند
اغلب Pipeline Flush
نامیده می شود،
هرچند جزئیات دقیق
در Microarchitectureهای مختلف
متفاوت است.

Branch Misprediction Penalty چیست؟

از لحظه ای که
CPU مسیر اشتباه را دنبال کرده
تا زمانی که
مسیر صحیح دوباره
Pipeline را پر کند،
بخشی از زمان
و ظرفیت پردازشی
از دست می رود.

این هزینه:

Branch Misprediction Penalty

نامیده می شود.

هزینه Misprediction از کجا می آید؟

هزینه می تواند
شامل چند بخش باشد:

• کاری که روی مسیر اشتباه انجام شده است،
• Redirect کردن Front-End،
• دریافت دستورهای مسیر صحیح،
• Decode مجدد جریان صحیح،
• و پر شدن دوباره بخش های لازم Pipeline.

Wrong-Path Work
+
Recovery
+
Front-End Refill
=
Misprediction Cost

Pipeline عمیق چه ارتباطی با Branch Prediction دارد؟

هرچه فاصله
میان Fetch یک Branch
و مشخص شدن نتیجه آن
بیشتر باشد،
CPU می تواند
دستورهای بیشتری
از مسیر حدسی
وارد Pipeline کند.

در نتیجه،
Misprediction
بالقوه می تواند
هزینه بیشتری داشته باشد.

Deeper Effective Pipeline
→
Potentially Higher Misprediction Cost

Branch Prediction چگونه روی IPC اثر می گذارد؟

IPC
فقط به تعداد Execution Unitها
وابسته نیست.

اگر Front-End
مرتباً مسیر اشتباه
را انتخاب کند،
Back-End
نمی تواند جریان پیوسته ای
از دستورهای مفید
دریافت کند.

Bad Prediction
→
Front-End Disruption
→
Less Useful Work
→
Lower Effective IPC

آیا همه Branchها به یک اندازه قابل پیش بینی هستند؟

خیر.

برخی Branchها
الگوی بسیار منظم دارند.

برای مثال
Loopهایی که
تعداد مشخصی تکرار می شوند.

برخی دیگر
به داده هایی وابسته اند
که رفتار آنها
بسیار نامنظم است.

Predictable Pattern
→
High Prediction Accuracy

Irregular Pattern
→
Harder Prediction

چرا داده های نامنظم می توانند Branch را گران کنند؟

فرض کنید برنامه
برای هر عنصر
یک شرط بررسی کند.

اگر تقریباً تمام عناصر
یک نتیجه مشابه داشته باشند،
Predictor احتمالاً
الگو را سریع یاد می گیرد.

اما اگر نتیجه شرط
تقریباً غیرقابل پیش بینی باشد،
نرخ Misprediction
می تواند افزایش پیدا کند.

Unpredictable Data
→
Unpredictable Branch
→
More Mispredictions

چرا گاهی پردازش داده مرتب شده سریع تر است؟

یکی از دلایل احتمالی
می تواند Predictability
بهتر Branchها باشد.

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

البته Performance واقعی
می تواند به عوامل دیگری مانند:

• Cache Locality،
• Memory Access Pattern،
• Compiler Optimization،
• Vectorization،
• و نوع الگوریتم

نیز وابسته باشد.

Branchless Code چیست؟

Branchless Programming
تلاش می کند
در برخی بخش های حساس
تصمیم گیری مبتنی بر Branch
را با روش های دیگری
جایگزین کند.

برای مثال،
ممکن است Compiler
یا برنامه نویس
از:

• Conditional Move،
• Masking،
• Arithmetic Transformations،
• و Vector Operations

استفاده کند.

Conditional Move چیست؟

برخی ISAها
امکان انتخاب یک مقدار
بر اساس Condition
بدون Branch معمولی
را فراهم می کنند.

Condition
→
Select Value A Or B

این روش
می تواند برای Branchهای
سخت قابل پیش بینی
مفید باشد،
اما همیشه
بهترین انتخاب نیست.

Compiler چه نقشی در Branch Performance دارد؟

Compiler می تواند
ساختار کد را
به شکل های مختلف
به Machine Code
تبدیل کند.

بسته به شرایط
ممکن است:

• Branch تولید کند،
• از Conditional Move استفاده کند،
• Loop را تغییر دهد،
• کد را Vectorize کند،
• یا Layout مسیرهای رایج را بهینه کند.

بنابراین کد سطح بالا
الزاماً تصویر دقیقی
از Branchهای نهایی CPU
ارائه نمی دهد.

Hot Path چیست؟

Hot Path
مسیری از برنامه است
که بسیار بیشتر
از مسیرهای دیگر
اجرا می شود.

Compiler و CPU
می توانند از اطلاعات
مربوط به رفتار رایج برنامه
برای بهینه سازی
این مسیرها استفاده کنند.

Frequently Executed Path
=
Hot Path

Profile-Guided Optimization چه ارتباطی با Branch دارد؟

در Profile-Guided Optimization
یا PGO،
اطلاعات اجرای واقعی برنامه
می تواند به Compiler
کمک کند بفهمد
کدام مسیرها
بیشتر استفاده می شوند.

Runtime Profile
→
Compiler
→
Better Code Layout

این اطلاعات
می تواند در بهینه سازی
Branchها،
Layout کد
و Hot Pathها
مفید باشد.

چرا Branch Predictor بخشی از Front-End محسوب می شود؟

Front-End باید بداند
Instruction بعدی
را از کجا دریافت کند.

اگر Branch وجود داشته باشد،
آدرس Fetch بعدی
به نتیجه Prediction
وابسته می شود.

Branch Predictor
→
Next Fetch Address
→
Instruction Fetch

بنابراین Predictor
مستقیماً روی جریان
Instruction Delivery
اثر می گذارد.

Branch Prediction چه ارتباطی با Instruction Cache دارد؟

Predictor
مسیر آینده Fetch
را تعیین می کند.

سپس Front-End
باید Instructionهای آن مسیر
را از ساختارهایی مانند
Instruction Cache
دریافت کند.

بنابراین حتی Prediction صحیح
اگر به مسیری منتهی شود
که Instructionهای آن
در Cache حاضر نیستند،
ممکن است با
Front-End Stall
روبه رو شود.

Branch Predictor چه ارتباطی با Micro-op Cache دارد؟

در معماری هایی
که Micro-op Cache دارند،
Predictor می تواند
مسیر Fetch آینده
را مشخص کند
و Front-End
در صورت Hit
Micro-opهای Decode شده
را سریع تر دریافت کند.

Correct Prediction
+
Micro-op Cache Hit
→
Efficient Front-End Delivery

چرا CPUهای Wide به Predictor قوی نیاز دارند؟

اگر CPU بتواند
تعداد زیادی Instruction
را در هر Cycle
Fetch،
Decode
و Dispatch کند،
مسیر اشتباه
می تواند منابع بیشتری
را در مدت کوتاه
مصرف کند.

بنابراین با افزایش
عرض پردازنده،
کیفیت Prediction
اهمیت بیشتری پیدا می کند.

Wider Machine
→
More Instructions In Flight
→
Higher Value Of Accurate Prediction

Predictorهای مدرن چقدر پیچیده هستند؟

بسیار پیچیده تر
از مدل ساده
One-Bit Predictor هستند.

پردازنده های مدرن
می توانند چندین منبع اطلاعاتی
و چند Predictor
را ترکیب کنند.

هدف این است
که الگوهای مختلف Branch
با روش مناسب تری
پیش بینی شوند.

جزئیات دقیق
Predictor پردازنده های تجاری
همیشه به صورت کامل
منتشر نمی شود.

Hybrid Predictor چیست؟

یک Predictor
ممکن است برای
یک نوع Pattern
عالی باشد
و برای Pattern دیگر
ضعیف تر عمل کند.

Hybrid Predictor
چند Predictor
یا چند نوع History
را ترکیب می کند.

Predictor A
+
Predictor B
+
Selection Logic
→
Final Prediction

TAGE Predictor چیست؟

TAGE
خانواده ای شناخته شده
از روش های Branch Prediction است
که از Historyهایی
با طول های متفاوت
استفاده می کند.

Short History
+
Medium History
+
Long History
→
Better Pattern Coverage

ایده مهم این است
که همه Branchها
برای پیش بینی مناسب
به یک طول History
نیاز ندارند.

Loop Predictor چیست؟

بعضی Branchها
رفتار حلقه ای
بسیار مشخصی دارند.

برای مثال:

Taken × 99
→
Not Taken × 1

Predictor تخصصی Loop
می تواند تعداد Iterationها
یا الگوی خروج از حلقه
را دنبال کند.

Neural Branch Prediction چیست؟

برخی تحقیقات
و طراحی های Predictor
از ایده های محاسباتی
الهام گرفته از
مدل های یادگیری
برای تشخیص Correlationهای
طولانی تر استفاده می کنند.

نمونه کلاسیک پژوهشی:

Perceptron Branch Predictor

هدف چنین روش هایی
تشخیص Patternهایی است
که Predictorهای ساده تر
ممکن است نتوانند
به خوبی مدل کنند.

چرا نمی توان Predictor را بی نهایت بزرگ کرد؟

Predictor بزرگ تر
می تواند History
و State بیشتری نگه دارد،
اما هزینه دارد.

• فضای Die،
• مصرف انرژی،
• Latency دسترسی،
• پیچیدگی طراحی،
• و محدودیت Timing.

Predictor باید
بسیار سریع باشد،
زیرا Front-End
تقریباً در هر لحظه
به نتیجه آن نیاز دارد.

Branch Prediction چه تاثیری بر مصرف انرژی دارد؟

Predictor خود
انرژی مصرف می کند،
اما Misprediction نیز
باعث انجام کار بی فایده
روی مسیر اشتباه می شود.

Wrong-Path Fetch
+
Wrong-Path Decode
+
Wrong-Path Execution
→
Wasted Energy

بنابراین Prediction بهتر
علاوه بر Performance
می تواند روی
Energy Efficiency
نیز اثر بگذارد.

Speculative Execution چه ارتباطی با امنیت دارد؟

اجرای حدسی
برای Performance
بسیار ارزشمند است،
اما پژوهش های امنیتی
نشان داده اند
که اثرات Microarchitectural
برخی عملیات حدسی
می توانند در شرایط خاص
به Side Channel
تبدیل شوند.

یکی از مشهورترین خانواده های
این نوع حملات:

Spectre

است.

Architectural State و Microarchitectural State چه تفاوتی دارند؟

اگر Speculation
اشتباه باشد،
CPU می تواند
نتیجه معماری دستورهای اشتباه
را کنار بگذارد.

اما اجرای آنها
ممکن است روی بخش هایی
از Microarchitecture
اثر گذاشته باشد.

برای مثال،
رفتار Cache
می تواند بخشی
از چنین اثراتی باشد.

Architectural Result
→
Squashed

Microarchitectural Side Effects
→
Potentially Observable

Spectre به زبان ساده چیست؟

Spectre
نام خانواده ای
از آسیب پذیری ها و تکنیک های حمله است
که از رفتار
Speculative Execution
و Side Channelهای
Microarchitectural
سوء استفاده می کنند.

نکته مهم این است
که Speculative Execution
ذاتاً یک «باگ ساده»
نیست.

این مکانیزم
یکی از پایه های Performance
پردازنده مدرن است،
اما مرز میان
Performance Optimization
و Security Isolation
باید با دقت مدیریت شود.

مقابله با آسیب پذیری های Speculation می تواند روی Performance اثر بگذارد؟

بله،
بسته به نوع آسیب پذیری،
CPU،
سیستم عامل،
Workload
و Mitigation مورد استفاده.

برخی Mitigationها
می توانند بخشی
از آزادی Speculation
یا Prediction
را محدود کنند.

اما میزان اثر
در همه سیستم ها
و همه نرم افزارها
یکسان نیست.

Branch Prediction در Serverها چرا مهم است؟

Server Workloadها
می توانند شامل:

• Database Engine،
• Web Server،
• Runtimeهای زبان،
• Virtual Machine،
• Compression،
• Networking،
• و پردازش درخواست های پیچیده

باشند.

بسیاری از این Workloadها
دارای Control Flow
پیچیده هستند.

بنابراین Predictor قوی
می تواند نقش مهمی
در Throughput واقعی
داشته باشد.

Branch Prediction در Database چه اهمیتی دارد؟

Database Engine
ممکن است مرتباً:

• شرط ها را بررسی کند،
• رکوردها را فیلتر کند،
• ساختارهای درختی را پیمایش کند،
• نوع داده را بررسی کند،
• و مسیرهای متفاوت Query Execution را اجرا کند.

اگر Control Flow
وابسته به داده
بسیار نامنظم باشد،
Branch Misprediction
می تواند بخشی
از هزینه پردازش شود.

Branch Prediction در بازی ها چه نقشی دارد؟

موتور بازی
فقط عملیات گرافیکی
انجام نمی دهد.

CPU ممکن است:

• منطق بازی،
• هوش مصنوعی،
• Physics،
• Animation،
• Scene Management،
• Draw Call Preparation،
• و سیستم های Gameplay

را پردازش کند.

بسیاری از این سیستم ها
دارای Branchهای متعدد هستند.

بنابراین کیفیت Microarchitecture
و Predictor
می تواند روی Performance
CPU در بازی ها اثر بگذارد.

مرورگر وب هم از Branch Prediction تاثیر می گیرد؟

بله.

مرورگر مدرن
مجموعه بزرگی از:

• JavaScript Engine،
• Rendering Engine،
• Layout،
• Networking،
• Parsing،
• Garbage Collection،
• و Security Logic

است.

چنین Workloadهایی
Control Flow
بسیار متنوعی دارند
و از پیشرفت های
Branch Prediction
بهره می برند.

در Workstation چه کاربردی دارد؟

نرم افزارهای مهندسی،
شبیه سازی،
کامپایل،
پردازش داده،
CAD،
مدل سازی سه بعدی
و تولید محتوا
همگی بخش هایی دارند
که Performance آنها
به اجرای کد عمومی CPU
وابسته است.

بنابراین Branch Prediction
محدود به لپ تاپ
یا یک نوع نرم افزار خاص نیست.

این مکانیزم
در پردازنده های:

• Desktop،
• Laptop،
• Workstation،
• Server،
• Mobile Device،
• و بسیاری از سیستم های پردازشی دیگر

اهمیت دارد.

چرا فرکانس به تنهایی قدرت CPU را مشخص نمی کند؟

دو پردازنده
می توانند فرکانس مشابهی داشته باشند،
اما یکی:

• Predictor دقیق تری داشته باشد،
• Front-End قوی تری داشته باشد،
• Cache بهتری داشته باشد،
• Execution Engine عریض تری داشته باشد،
• و Mispredictionها را سریع تر Recover کند.

بنابراین:

Same GHz
≠
Same Performance

آیا Branch Predictor می تواند بین نسل های CPU بهتر شود؟

بله.

یکی از مسیرهای
افزایش Performance نسل به نسل
بهبود Front-End
و Branch Prediction است.

حتی اگر فرکانس
تغییر بزرگی نکند،
کاهش Misprediction
می تواند باعث شود
CPU در هر واحد زمان
کار مفید بیشتری انجام دهد.

آیا Benchmark ساده می تواند کیفیت Branch Predictor را نشان دهد؟

همیشه نه.

Workloadهای مختلف
Branch Behavior
متفاوتی دارند.

یک Benchmark
با Control Flow ساده
ممکن است Predictor را
چندان تحت فشار قرار ندهد.

در حالی که Workload دیگری
با Branchهای پیچیده
تفاوت معماری ها
را بهتر آشکار کند.

Prefetching چیست؟

Demand Access و Prefetch چه تفاوتی دارند؟

در Demand Access،
CPU زمانی داده را درخواست می کند
که اجرای برنامه
واقعاً به آن نیاز پیدا کرده است.

Need Data
→
Request Data
→
Wait If Necessary

اما در Prefetch:

Predict Need
→
Request Early
→
Data Hopefully Ready Before Use

تفاوت اصلی
در زمان شروع درخواست است.

یک مثال ساده

فرض کنید برنامه
عناصر یک Array بزرگ
را پشت سر هم می خواند.

A[0]
→
A[1]
→
A[2]
→
A[3]
→
A[4]

CPU پس از مشاهده
چند دسترسی متوالی
ممکن است حدس بزند:

اگر برنامه اکنون
این قسمت حافظه را می خواند،
احتمالاً چند Cache Line بعدی
نیز به زودی لازم خواهند شد.

بنابراین می تواند
درخواست آنها را
پیش از Demand Access واقعی
آغاز کند.

Hardware Prefetcher چیست؟

چرا Prefetching را به سخت افزار می سپاریم؟

سخت افزار
می تواند رفتار واقعی
Memory Access
را هنگام اجرای برنامه
مشاهده کند.

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

Observe Access Pattern
→
Detect Pattern
→
Predict Future Address
→
Prefetch

Spatial Locality چرا برای Prefetching مهم است؟

Spatial Locality
می گوید اگر برنامه
به یک Address
دسترسی پیدا کند،
احتمال دارد
در آینده نزدیک
به Addressهای اطراف آن
نیز دسترسی پیدا کند.

این رفتار
پایه بسیاری از
Prefetching Patternهای ساده است.

Address X
→
X + Δ
→
X + 2Δ
→
X + 3Δ

Sequential Access چیست؟

یکی از ساده ترین
الگوهای قابل پیش بینی
دسترسی ترتیبی است.

برای مثال:

Cache Line 100
→
Cache Line 101
→
Cache Line 102
→
Cache Line 103

وقتی چنین الگویی
مشاهده شود،
Prefetcher می تواند
Lineهای بعدی
را زودتر درخواست کند.

Stream Prefetcher چیست؟

Stream Prefetcher
تلاش می کند
جریان های نسبتاً منظم
دسترسی به حافظه
را تشخیص دهد.

Line N
→
Line N+1
→
Line N+2
→
Predict N+3

چنین Prefetcherهایی
می توانند در پردازش
آرایه ها،
Bufferها
و جریان های ترتیبی داده
موثر باشند.

Stride Prefetcher چیست؟

همه دسترسی ها
پشت سر هم نیستند.

ممکن است برنامه
با فاصله ثابت
در حافظه حرکت کند.

Address 1000
→
Address 1064
→
Address 1128
→
Address 1192

اختلاف ثابت:

+64 Bytes

یک Stride Prefetcher
می تواند این فاصله ثابت
را تشخیص دهد
و Address بعدی
را پیش بینی کند.

Prefetching چه ارتباطی با Cache Line دارد؟

Cache
معمولاً داده را
به صورت Byte منفرد
میان سطوح مختلف
جابه جا نمی کند.

انتقال معمولاً
در واحدهایی مانند
Cache Line انجام می شود.

بنابراین Prefetcher نیز
در بسیاری از موارد
با Lineهای حافظه
سروکار دارد.

Predicted Address
→
Corresponding Cache Line
→
Prefetch Request

داده Prefetch شده به کجا می رود؟

پاسخ
به Microarchitecture
و نوع Prefetcher
بستگی دارد.

داده ممکن است
به یکی از سطوح Cache
یا ساختارهای مرتبط
وارد شود.

برای مثال،
یک Prefetcher
ممکن است عمدتاً
برای L1
و Prefetcher دیگری
برای L2
طراحی شده باشد.

بنابراین:

Hardware Prefetcher
≠
One Universal Prefetch Mechanism

آیا یک CPU فقط یک Prefetcher دارد؟

الزاماً خیر.

یک Microarchitecture
می تواند چند مکانیزم
Prefetching مختلف
برای سطوح متفاوت Cache
یا Patternهای مختلف
داشته باشد.

هر Prefetcher
می تواند روی
نوع خاصی از رفتار
تمرکز داشته باشد.

Prefetch Distance چیست؟

اگر Prefetch Distance خیلی کم باشد چه می شود؟

Prefetch ممکن است
بیش از حد دیر
صادر شود.

در این حالت
زمانی که CPU
واقعاً داده را نیاز دارد،
انتقال هنوز
کامل نشده است.

Prefetch Too Late
→
Demand Arrives
→
Data Still Missing
→
Stall

اگر Prefetch Distance خیلی زیاد باشد چه می شود؟

داده ممکن است
خیلی زود وارد Cache شود.

سپس پیش از استفاده واقعی
به دلیل فشار Cache
Evict شود.

یا ممکن است
اصلاً مورد استفاده
قرار نگیرد.

Too Early
→
Occupy Cache
→
Possible Eviction
→
Possible Waste

Prefetch Degree چیست؟

Prefetch Degree
به تعداد درخواست هایی
اشاره دارد
که Prefetcher
برای آینده
در یک مرحله
یا جریان مشخص
ایجاد می کند.

Prefetcher تهاجمی تر
ممکن است چند Line آینده
را همزمان درخواست کند.

Current Line
→
Prefetch +1
→
Prefetch +2
→
Prefetch +3

Prefetch Aggressiveness چیست؟

یک Prefetcher
می تواند محافظه کار
یا تهاجمی باشد.

Prefetching تهاجمی
ممکن است Latency بیشتری
را پنهان کند،
اما ریسک:

• مصرف Bandwidth بیشتر،
• Cache Pollution بیشتر،
• درخواست های بی استفاده بیشتر،
• و رقابت بیشتر در Memory Subsystem

را نیز افزایش می دهد.

Prefetch Accuracy چیست؟

Accuracy
نشان می دهد
چه سهمی از داده هایی
که Prefetch شده اند
واقعاً بعداً
توسط برنامه استفاده شده اند.

Useful Prefetches
/
Total Prefetches
=
Prefetch Accuracy

Prefetcher با Accuracy پایین
می تواند منابع سیستم
را برای داده های بی استفاده
مصرف کند.

Prefetch Coverage چیست؟

Coverage
به این سؤال پاسخ می دهد:

Prefetcher چه مقدار
از Missهایی را
که بدون Prefetch رخ می دادند
توانسته پیشاپیش پوشش دهد؟

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

Prefetch Timeliness چیست؟

فقط درست بودن Prediction
کافی نیست.

داده باید
در زمان مناسب
برسد.

Correct Address
+
Correct Time
=
Useful Prefetch

اگر داده
بعد از Demand Access برسد،
Prediction درست بوده
اما Prefetch
دیر انجام شده است.

Late Prefetch چیست؟

اگر Address آینده
درست پیش بینی شود
اما درخواست
به اندازه کافی زود
صادر نشده باشد،
Demand Access
قبل از رسیدن داده
اتفاق می افتد.

این وضعیت:

Late Prefetch

نامیده می شود.

Useless Prefetch چیست؟

اگر Prefetcher
داده ای را وارد Cache کند
اما برنامه
پیش از Eviction آن
هرگز از داده استفاده نکند،
Prefetch عملاً
مفید نبوده است.

Prefetch
→
Never Used
→
Evicted
=
Useless Prefetch

Cache Pollution چیست؟

Cache ظرفیت محدودی دارد.

اگر Prefetcher
داده های کم ارزش
یا اشتباه زیادی
وارد Cache کند،
ممکن است داده های مفید
برای جا باز کردن
Evict شوند.

Bad Prefetch
→
Occupy Cache
→
Evict Useful Data
→
Cache Pollution

Prefetching چه تاثیری روی Memory Bandwidth دارد؟

Prefetch Request
نیز یک درخواست واقعی
در Memory Hierarchy است.

اگر Prefetcher
داده زیادی درخواست کند،
ترافیک حافظه
افزایش پیدا می کند.

Aggressive Prefetching
→
More Memory Requests
→
More Bandwidth Consumption

در Workloadهای
Bandwidth-Bound،
این موضوع
اهمیت ویژه ای دارد.

چرا Prefetching نمی تواند محدودیت Bandwidth را حذف کند؟

Prefetching
عمدتاً تلاش می کند
Latency را پنهان کند.

اما اگر برنامه
واقعاً حجم داده ای
بیشتر از ظرفیت انتقال
Memory Subsystem
نیاز داشته باشد،
Prefetcher نمی تواند
Bandwidth فیزیکی بیشتری
ایجاد کند.

Prefetching
≠
More Physical Memory Bandwidth

تفاوت Latency و Bandwidth در این بحث چیست؟

Prefetching چه ارتباطی با Memory-Level Parallelism دارد؟

به جای اینکه CPU
یک Memory Request
را ارسال کند
و کاملاً منتظر نتیجه بماند،
سیستم های مدرن
می توانند چند درخواست
را همزمان
در حال پردازش داشته باشند.

Prefetching
می تواند تعداد درخواست های
آینده را زودتر
وارد Memory Subsystem کند.

Multiple Outstanding Requests
→
Better Latency Overlap

MSHR چه ارتباطی با Prefetching دارد؟

در فصل Cache
با ساختارهایی مانند
MSHR آشنا شدیم
که Missهای در حال انتظار
را دنبال می کنند.

Prefetch Requestها نیز
می توانند منابع مربوط
به Miss Handling
را مصرف کنند.

اگر Prefetching
بیش از حد تهاجمی باشد،
ممکن است بخشی از منابع
لازم برای Demand Missهای واقعی
را اشغال کند.

آیا Demand Request و Prefetch Request همیشه اولویت یکسان دارند؟

الزاماً خیر.

Microarchitecture
می تواند درخواست های واقعی برنامه
و درخواست های Speculative Prefetch
را با سیاست های متفاوت
مدیریت کند.

هدف این است
که Prefetching
به Demand Accessهای مهم
آسیب زیادی وارد نکند.

چرا Pointer Chasing برای Prefetcher سخت است؟

فرض کنید هر Node
آدرس Node بعدی
را در خود نگه دارد.

Node A
→
Pointer To B
→
Node B
→
Pointer To C
→
Node C

تا زمانی که Node A
خوانده نشود،
Address مربوط به B
ممکن است مشخص نباشد.

در نتیجه
الگوی ساده Stride
وجود ندارد
و Prefetch کردن
دشوارتر می شود.

چرا Linked List ممکن است از Array کندتر باشد؟

یکی از دلایل احتمالی
تفاوت در Memory Access Pattern است.

Array
معمولاً داده را
در حافظه
منظم تر نگه می دارد.

Array
→
Regular Access
→
Easier Prefetching

اما Nodeهای Linked List
می توانند در نقاط مختلف حافظه
پراکنده باشند.

Linked List
→
Pointer Chasing
→
Irregular Access
→
Harder Prefetching

البته این تنها دلیل
تفاوت Performance
میان این ساختارها نیست.

Random Access چه مشکلی برای Prefetcher ایجاد می کند؟

اگر Addressهای آینده
ارتباط قابل تشخیص
با Addressهای قبلی
نداشته باشند،
Prediction دشوار می شود.

A
→
X
→
Q
→
M
→
Z

Prefetcher ساده
نمی تواند از چنین الگویی
Stride قابل اعتمادی
استخراج کند.

Software Prefetching چیست؟

در برخی ISAها
دستورها یا Hintهایی
برای Prefetch
وجود دارند.

Compiler
یا برنامه نویس
می تواند به CPU
اعلام کند
که احتمالاً داده مشخصی
در آینده لازم خواهد شد.

Software
→
Prefetch Hint
→
Memory Hierarchy

Hardware Prefetching و Software Prefetching چه تفاوتی دارند؟

چرا Software Prefetching همیشه بهتر نیست؟

زمان بندی Prefetch
باید دقیق باشد.

اگر Hint
خیلی دیر صادر شود،
داده به موقع نمی رسد.

اگر خیلی زود صادر شود،
ممکن است داده
پیش از استفاده Evict شود.

علاوه بر این،
Hardware Prefetcher
ممکن است همان Pattern
را از قبل
به خوبی تشخیص دهد.

Compiler می تواند Prefetching انجام دهد؟

در برخی شرایط
Compiler می تواند
Pattern دسترسی
را تحلیل کند
و Prefetch Instruction
یا Optimization مناسب
ایجاد کند.

اما موفقیت این روش
به قابل پیش بینی بودن
Access Pattern
و معماری هدف
بستگی دارد.

Vectorization چه ارتباطی با Prefetching دارد؟

Workloadهای Vectorized
اغلب حجم زیادی داده
را با Pattern نسبتاً منظم
پردازش می کنند.

در چنین شرایطی
Hardware Prefetcher
ممکن است بتواند
جریان حافظه را
به خوبی تشخیص دهد.

Regular Vector Workload
→
Predictable Memory Stream
→
Effective Prefetching

البته اگر حجم داده
به محدودیت Bandwidth برسد،
Prefetching نمی تواند
آن محدودیت را حذف کند.

ترتیب پیمایش Matrix چرا مهم است؟

در بسیاری از زبان ها
داده Matrix
با Layout مشخصی
در حافظه قرار می گیرد.

پیمایش مطابق Layout
می تواند Access Pattern
منظم تری ایجاد کند.

Contiguous Access
→
Better Locality
→
Easier Prefetching

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

Prefetching چه ارتباطی با TLB دارد؟

دسترسی به داده
فقط به Cache
وابسته نیست.

Address Translation
نیز باید انجام شود.

در Workloadهای بزرگ،
رفتار TLB
و Page Translation
می تواند روی توانایی CPU
برای حفظ جریان سریع
Memory Access
اثر بگذارد.

برخی معماری ها
مکانیزم هایی برای کمک
به پیش بینی یا آماده سازی
بخش هایی از مسیر Translation
نیز دارند،
اما جزئیات
Microarchitecture-specific است.

Prefetching در CPU چند هسته ای چه چالشی دارد؟

در سیستم چند هسته ای،
چند Core
می توانند همزمان
Prefetch Request
ایجاد کنند.

این درخواست ها
ممکن است برای:

• Shared Cache Capacity،
• Memory Bandwidth،
• Memory Controller Resources،
• و Interconnect Bandwidth

رقابت کنند.

More Cores
→
More Memory Streams
→
More Prefetch Traffic

Prefetching در Serverها چرا مهم است؟

Serverها
می توانند تعداد زیادی Core
و Memory Channel
داشته باشند.

Workloadهایی مانند:

• Database،
• Analytics،
• Compression،
• Scientific Computing،
• Virtualization،
• و Data Processing

ممکن است حجم زیادی
Memory Traffic
ایجاد کنند.

Prefetching مناسب
می تواند Latency
برخی جریان های داده
را پنهان کند،
اما Prefetching بیش از حد
نیز ممکن است
Shared Bandwidth
را تحت فشار قرار دهد.

Databaseها چقدر از Prefetching سود می برند؟

پاسخ به نوع
Data Structure
و Query بستگی دارد.

Scan کردن
یک بخش بزرگ
و نسبتاً پیوسته از داده
می تواند برای Prefetcher
مناسب باشد.

Sequential Scan
→
Predictable Stream

اما دسترسی های
پراکنده و وابسته
به Pointer
می توانند
سخت تر پیش بینی شوند.

Prefetching در بازی ها چه نقشی دارد؟

موتور بازی
با انواع مختلفی
از داده ها سروکار دارد:

• Object Data،
• Physics State،
• Animation Data،
• AI Structures،
• Scene Data،
• و Rendering Preparation.

بخش هایی که
Memory Layout منظم تری دارند
می توانند استفاده بهتری
از Cache
و Hardware Prefetching
داشته باشند.

Data-Oriented Design چه ارتباطی با Prefetching دارد؟

یکی از ایده های
Data-Oriented Design
این است که
Data Layout
متناسب با نحوه پردازش
طراحی شود.

اگر داده هایی
که پشت سر هم پردازش می شوند
در حافظه نیز
نزدیک یکدیگر باشند،
CPU می تواند
از Cache Line
و Prefetcher
بهتر استفاده کند.

Better Data Layout
→
Better Locality
→
Better Prefetchability
→
Fewer Memory Stalls

Array of Structures و Structure of Arrays چه ارتباطی با Memory Access دارند؟

فرض کنید
برای هزاران Object
فقط یک ویژگی خاص
پردازش می شود.

اگر آن ویژگی ها
به شکل پیوسته
در حافظه قرار گرفته باشند،
دسترسی می تواند
منظم تر باشد.

Structure of Arrays
→
Potentially Contiguous Field Access

در مقابل،
Array of Structures
می تواند داده های دیگری
را نیز داخل همان Cache Lineها
وارد کند.

اینکه کدام Layout بهتر است
کاملاً به Workload بستگی دارد.

آیا Hardware Prefetcher را می توان غیرفعال کرد؟

در برخی Platformها
ممکن است Firmware،
BIOS
یا ابزارهای تخصصی
امکان کنترل
بعضی Prefetcherها
را فراهم کنند.

اما این موضوع
وابسته به CPU
و مادربرد است.

برای استفاده عمومی
معمولاً دلیلی برای
غیرفعال کردن Prefetcher
وجود ندارد.

چنین تنظیماتی
بیشتر برای:

• Benchmarking،
• Performance Analysis،
• Research،
• و Workloadهای تخصصی

بررسی می شوند.

آیا هنگام خرید CPU باید نوع Prefetcher را بررسی کنیم؟

برای کاربر معمولی،
معمولاً خیر.

سازندگان CPU
جزئیات کامل
تمام Prefetcherهای داخلی
را نیز همیشه
به عنوان مشخصات محصول
منتشر نمی کنند.

اثر این مکانیزم ها
بهتر است
در Performance واقعی
پردازنده
و Benchmarkهای معتبر
مشاهده شود.

آیا بهبود Prefetcher می تواند نسل جدید CPU را سریع تر کند؟

بله.

اگر نسل جدید
بتواند Access Patternهای بیشتری
را تشخیص دهد،
Prefetch را دقیق تر
زمان بندی کند
و منابع حافظه
را بهتر مدیریت کند،
Memory Stall
می تواند کاهش پیدا کند.

Better Prefetching
→
Fewer Effective Cache Miss Stalls
→
Higher Useful Throughput

Prefetching چه ارتباطی با مقایسه CPUهای هم فرکانس دارد؟

فرض کنید دو CPU
هر دو با فرکانس مشابه
کار می کنند.

یکی ممکن است
Memory Access آینده
را بهتر پیش بینی کند
و زمان کمتری
منتظر داده بماند.

در نتیجه:

Same Clock Frequency
≠
Same Effective Memory Performance

این یکی دیگر
از دلایلی است
که GHz به تنهایی
معیار قدرت CPU نیست.

Hardware Prefetching و Branch Prediction چه شباهتی دارند؟

هر دو تلاش می کنند
آینده را پیش بینی کنند،
اما موضوع Prediction
متفاوت است.

به صورت مفهومی:

Branch Predictor
→
What Instructions Will We Need?

Data Prefetcher
→
What Data Will We Need?

آیا Prefetching نوعی Speculation است؟

از نظر مفهومی
بله؛
زیرا CPU
پیش از درخواست قطعی برنامه
حدس می زند
که داده ای در آینده
مورد نیاز خواهد بود.

اما Prefetching
با Speculative Execution
Branchها
یک مکانیزم یکسان نیست.

هر دو از Prediction
برای کاهش زمان انتظار
استفاده می کنند،
ولی روی بخش های متفاوتی
از اجرای برنامه
تمرکز دارند.

Prefetching چه تاثیری روی مصرف انرژی دارد؟

Prefetch مفید
می تواند باعث شود
Core زمان کمتری
در انتظار داده بماند.

اما Prefetchهای بی استفاده
باعث انتقال داده
بدون منفعت واقعی می شوند.

Useless Prefetch
→
Memory Traffic
+
Cache Activity
+
Energy Consumption

بنابراین Energy Efficiency
نیز یکی از ملاحظات
طراحی Prefetcher است.

Prefetching در سیستم های NUMA چه پیچیدگی بیشتری دارد؟

در سیستم NUMA،
Latency و Bandwidth
دسترسی به حافظه
می تواند به محل فیزیکی داده
و Node پردازنده
وابسته باشد.

Prefetching
می تواند بخشی از Latency
را پنهان کند،
اما نمی تواند
هزینه معماری
یک Data Placement نامناسب
را به طور کامل حذف کند.

Bad NUMA Placement
+
Remote Memory Access
≠
Fixed By Prefetching Alone