کش: داده‌ی داغ رو نزدیک نگه داشتن (Cache)
بفهم چرا رم صدها تیک ساعت با پردازنده فاصله داره، کش‌های کوچیک و سریع چطور این انتظار رو پنهون می‌کنن، و چرا خوندن داده به‌ترتیب خیلی سریع‌تر از پریدن این‌ور و اون‌وره.
فاصله
۱۰۰ نانوثانیه برای پردازنده خیلی طولانیه
یه پردازنده‌ی ۳ گیگاهرتزی ثانیه‌ای ۳ میلیارد بار تیک می‌زنه، پس هر تیک حدود یک‌سوم نانوثانیه‌ست. یعنی یه خوندن از رم که حدوداً ۱۰۰ نانوثانیه طول می‌کشه، حدود ۳۰۰ تیک هزینه داره. یه جمع ساده حدود یه تیک طول می‌کشه. پس اگه پردازنده هر بار که یه مقدار لازم داشت منتظر رم می‌موند، تقریباً کل وقتش به انتظار می‌گذشت و تقریباً هیچ کاری نمی‌کرد.
۱۰۰ نانوثانیه ÷ یک‌سوم نانوثانیه برای هر تیک ≈ ۳۰۰ تیک: زمانی که پردازنده می‌تونست توش صدها جمع انجام بده.
خودت رو امتحان کن
یه پردازنده با ۳ گیگاهرتز کار می‌کنه، پس هر تیک حدود یک‌سوم نانوثانیه‌ست. توی یه خوندن ۱۰۰ نانوثانیه‌ای از رم، تقریباً چند تا تیک می‌گذره؟
- حدود ۳
- حدود ۳۰
- حدود ۳۰۰
- حدود ۳ میلیارد
جواب رو ببین
حدود ۳۰۰
درسته. توی هر نانوثانیه ۳ تیک، ضرب در ۱۰۰ نانوثانیه، می‌شه حدود ۳۰۰ تیک انتظار فقط برای یه مقدار.
حافظه‌ی نهان (Cache)
یه حافظه‌ی کوچیک و خیلی سریع روی تراشه‌ی پردازنده که از داده‌هایی که تازگی استفاده شدن کپی نگه می‌داره، تا دفعه‌ی بعد که لازم شدن مجبور نباشه از رم بیاردشون. بیشتر تراشه‌ها سه سطح دارن (اندازه‌ها و زمان‌ها تقریبین و از تراشه‌ای به تراشه‌ی دیگه فرق می‌کنن): L1، حدود ۳۲ تا ۶۴ کیلوبایت برای هر هسته، حدود ۱ نانوثانیه؛ L2، از چند صد کیلوبایت تا چند مگابایت، حدود ۳ تا ۵ نانوثانیه؛ L3، از چند تا چند ده مگابایت که بین همه‌ی هسته‌ها مشترکه، حدود ۱۰ تا ۲۰ نانوثانیه.
وقتی پردازنده یه مقدار می‌خواد، اول L1 رو نگاه می‌کنه، بعد L2، بعد L3، و فقط آخر سر تا خود رم می‌ره.
برخورد، از دست رفتن، خط
برخورد سریعه، از دست رفتن راه دورتری می‌ره
اگه داده از قبل توی کش باشه، بهش می‌گن برخورد (Cache hit) و توی حدود یه نانوثانیه تحویل داده می‌شه. اگه نباشه، از دست رفتن (Cache miss)ـه: درخواست می‌ره سراغ سطح بعدی و کندتر، و آخرش رم. وقتی داده برمی‌گرده، یه کپیش برای دفعه‌ی بعد توی کش می‌مونه. تازه کش هیچ‌وقت فقط یه بایت نمی‌آره: یه خط کش (Cache line) کامل می‌آره، معمولاً ۶۴ بایت. یه بایت بخوای، ۶۳ تا همسایه‌ش هم مجانی همراهش میان.
آدرس ۱۰۰۰ رو بخونی، کش کل خط از ۱۰۰۰ تا ۱۰۶۳ رو می‌آره. حالا هر کدوم از این ۶۴ آدرس یه برخورده.
خودت رو امتحان کن
پردازنده یه مقداری می‌خواد که نه توی L1 هست، نه L2، نه L3. چی می‌شه؟
- برنامه با یه خطای کش کرش می‌کنه
- مقدار از رم آورده می‌شه، و یه کپی از کل خطش توی کش می‌مونه
- پردازنده اون مقدار رو رد می‌کنه و بدونش ادامه می‌ده
- مقدار از رم آورده می‌شه، ولی کش اصلاً تغییری نمی‌کنه
جواب رو ببین
مقدار از رم آورده می‌شه، و یه کپی از کل خطش توی کش می‌مونه
درسته. از دست رفتن خطا نیست، فقط یه سفر کندتره. داده از رم میاد، و خط ۶۴ بایتیش توی کش می‌مونه تا خوندن بعدی از همون نزدیکی برخورد باشه.
قدم‌به‌قدم ببین
سلسله‌مراتب: L1، L2، L3، بعد رم کنار پردازنده چهار تا جعبه هست که هر کدوم از قبلی پهن‌تره: L1 با ۶۴ کیلوبایت و حدود ۱ نانوثانیه، L2 با ۱ مگابایت و حدود ۴ نانوثانیه، L3 با ۳۲ مگابایت و حدود ۱۵ نانوثانیه، و رم با ۱۶ گیگابایت و حدود ۱۰۰ نانوثانیه. هر سطح از قبلی بزرگ‌تر و کندتره. این اندازه‌ها و زمان‌ها مثال‌های تقریبی‌ان، نه عدد دقیقِ یه تراشه‌ی خاص.
آدرس ۱۰۰۰: از دست رفت، از دست رفت، از دست رفت، رم پردازنده برای اولین بار آدرس ۱۰۰۰ رو می‌خواد. L1 نداره، L2 هم نداره، L3 هم نداره: هر کدوم یه miss نشون می‌دن و درخواست تا خود رم می‌ره. زمان‌سنج حدود ۱۰۰ نانوثانیه رو نشون می‌ده.
خط ۱۰۰۰ تا ۱۰۶۳ برمی‌گرده؛ ۱۰۰۱ یه برخورده رم فقط یه بایت پس نمی‌فرسته: کل خط ۶۴ بایتی، یعنی آدرس‌های ۱۰۰۰ تا ۱۰۶۳، برمی‌گرده و توی کش‌ها نگه داشته می‌شه. پس وقتی پردازنده دفعه‌ی بعد ۱۰۰۱ رو می‌خواد، از قبل توی L1 هست: یه برخورد، توی حدود یه نانوثانیه.
از دست رفتن ۱۰۰ نانوثانیه در برابر برخورد ۱ نانوثانیه دو تا میله کنار هم: میله‌ی از دست رفتن، حدود ۱۰۰ نانوثانیه، از این سر تا اون سر قاب کشیده شده؛ میله‌ی برخورد، حدود ۱ نانوثانیه، یه باریکه‌ی نازکه. همون نوع خوندنه، تقریباً صد برابر سریع‌تر، فقط چون داده از قبل نزدیک بوده.
خودت رو امتحان کن
درست بعد از خوندن آدرس ۱۰۰۰ که دیدی، پردازنده آدرس ۱۰۴۰ رو می‌خواد. چی می‌شه؟
- یه از دست رفتن دیگه تا خود رم، حدود ۱۰۰ نانوثانیه، چون ۱۰۴۰ قبلاً خواسته نشده بود
- یه برخورد توی L1، حدود ۱ نانوثانیه، چون ۱۰۴۰ با خط ۱۰۰۰ تا ۱۰۶۳ اومده بود
- یه برخورد، ولی فقط توی L3، چون L1 فقط یه بایت نگه می‌داره
- خطا، چون فقط ۱۰۰۰ و ۱۰۰۱ آورده شده بودن
جواب رو ببین
یه برخورد توی L1، حدود ۱ نانوثانیه، چون ۱۰۴۰ با خط ۱۰۰۰ تا ۱۰۶۳ اومده بود
درسته. از دست رفتنِ ۱۰۰۰ کل خط ۶۴ بایتی، یعنی ۱۰۰۰ تا ۱۰۶۳، رو آورد و ۱۰۴۰ توی همین خطه. این همون سواری مجانیه که خط کش بهت می‌ده.
اگه یه برخورد L1 یه ثانیه طول می‌کشید
زمان رو اون‌قدر کش بده که یه برخورد توی L1 یه ثانیه طول بکشه. اون‌وقت یه خوندن از رم حدود یک دقیقه و نیم تا دو دقیقه طول می‌کشید. خوندن از اس‌اس‌دی حدود یه روز، و پیدا کردن جای داده روی هارد دیسک چند ماه. این‌ها مقایسه‌های معروف و تقریبی‌ان نه عدد دقیق، ولی شکل کلی درسته: هر قدم که از پردازنده دورتر می‌شی، خیلی بیشتر باید منتظر بمونی. برای همینه که نزدیک نگه داشتن داده‌ی داغ این‌قدر مهمه.
تعداد خوندن یکسان، سرعت خیلی متفاوت
پیمایش یه آرایه به‌ترتیب
خونه‌ی ۰، ۱، ۲، ۳ و… رو بخون.
یه از دست رفتن یه خط ۶۴ بایتی رو می‌آره و چند تا خوندن بعدی برخوردن. پردازنده بیشتر وقت‌ها هر بار فقط حدود یه نانوثانیه صبر می‌کنه.
این همون محلی بودن مکانی (Spatial locality)ـه: استفاده از داده‌ای که کنار چیزیه که همین الان استفاده کردی.
پریدن این‌ور و اون‌ور حافظه
یه زنجیره‌ی بلند از اشاره‌گرها رو دنبال کن که همه‌جای رم پخش شدن.
تقریباً هر خوندن روی یه خط جدید می‌افته، پس تقریباً هر خوندن یه از دست رفتنه، هر کدوم حدود ۱۰۰ نانوثانیه.
همون تعداد دستور می‌تونه چند برابر کندتر اجرا بشه.
خودت رو امتحان کن
کدوم فهرست از سریع‌ترین به کندترین مرتب شده؟
- کش L1، رجیستر، رم، اس‌اس‌دی
- رجیستر، کش L1، رم، اس‌اس‌دی
- رجیستر، رم، کش L1، اس‌اس‌دی
- اس‌اس‌دی، رم، کش L1، رجیستر
جواب رو ببین
رجیستر، کش L1، رم، اس‌اس‌دی
درسته. رجیسترها داخل خود هسته‌ی پردازنده‌ن، L1 درست کنارشه، رم بیرون از تراشه‌ست، و اس‌اس‌دی از اون هم کندتره.
کل سلسله‌مراتب حافظه (Memory Hierarchy)
- از بالا به پایین: رجیسترها ← L1 ← L2 ← L3 ← رم ← اس‌اس‌دی ← هارد دیسک.
- هر پله پایین‌تر بزرگ‌تر، ارزون‌تر برای هر بایت و کندتره.
- کش‌ها به‌خاطر محلی بودن (Locality) جواب می‌دن: برنامه‌ها همون داده رو زود دوباره استفاده می‌کنن (زمانی) و از داده‌ی کنار چیزی که همین الان استفاده کردن استفاده می‌کنن (مکانی).
- خودت این کش‌ها رو مدیریت نمی‌کنی؛ سخت‌افزار خودکار پر و خالیشون می‌کنه.
خودت رو امتحان کن
هر جایی که داده می‌تونه باشه رو به زمان تقریبی خوندنش وصل کن
جواب رو ببین
- کش L1 → حدود ۱ نانوثانیه
- کش L3 → حدود ۱۰ تا ۲۰ نانوثانیه
- رم → حدود ۱۰۰ نانوثانیه
- اس‌اس‌دی → چند ده میکروثانیه
مرور درس
- هر خوندن از رم حدوداً ۱۰۰ نانوثانیه طول می‌کشه، یعنی حدود ۳۰۰ تیکِ یه پردازنده‌ی ۳ گیگاهرتزی.
- کش یه حافظه‌ی کوچیک و سریع روی تراشه‌ست که از داده‌های تازه استفاده‌شده کپی نگه می‌داره، توی سطح‌های L1، L2 و L3.
- برخورد توی حدود یه نانوثانیه جواب می‌ده؛ از دست رفتن می‌ره سراغ سطح بعدی و آخرش رم، و موقع برگشت یه کپی نگه می‌داره.
- کش خط‌های کامل ۶۴ بایتی می‌آره، پس خوندن داده به‌ترتیب سریعه و پریدن این‌ور و اون‌ور حافظه کند.
- سلسله‌مراتب حافظه این‌طوریه: رجیستر، L1، L2، L3، رم، اس‌اس‌دی، هارد دیسک؛ هر پله بزرگ‌تر، ارزون‌تر و کندتر.