به نام خدا
سلام
سریع میرم سراغ اصل مطلب
اول بگم که منبع ما کتاب سازمان و معماری کامپیوتر ویلیام استالینگز هست ویراست 10 میتونید از اینجا دانلود کنید
توضیح ابتدایی کش اینه که بین حافظه و پردازنده قرار میگیره و کارش اینه که بخشی از رم رو بیاره و توی خودش ذخیره کنه تا پردازنده به سرعت به دستور العمل ها و داده ها دسترسی داشته باشه. سرعت کش خیلی بالاتر از رم هستش.
تصویر زیر داره چیزی رو که توضیح دادم رو نشون میده
سازمان حافظه نهان به این صورت تعریف میشه که شامل چندتا بلاک هست که هر بلاک شامل چند کلمه یا بایت از حافظه اصلی هست. مثلا اگه اندازه یک بلاک 8 بایت باشه یعنی هر بلاک میتونه هشت بایت رو نگه داری کنه.
کنار هر بلاک یک تگ وجود داره که یه سری مشخصات رو نگه داری میکنه که در ادامه به صورت کامل توضیح داده میشه.
وقتی پردازنده میره یه مکان حافظه رو بخونه حافظه کش فقط همون کلمه رو نمیاره بلکه میره و یه بلاک رو میاره و درون کش ذخیره میکنه (که اندازه بلاک رو حافظه کش تعریف میکنه) این برای اینه که تجربه نشون داده که وقتی یه برنامه درحال اجراست معمولا با بخش کمی از حافظه سر و کار داره که خیلی به هم نزدیک هستن به این موضوع میگن Locality Of Reference یعنی محلی بودن ارجاع که بیان میکنه مثلا برنامه ها معمولا یه لوپ دارن که هی تکرار میشه و فقط یه بخش خیلی کوچیکی از حافظه نیاز هست یا برای آرایه ها هم همینطور.
این ویژگی باعث میشه بتونیم از حافظه کش استفاده کنیم در غیر اینصورت نمیتونستیم فقط بخشی از حافظه رو بیاریم توی کش و باید کل برنامه رو توی کش میاوردیم که امکان پذیر نبود. (چون کش خیلی کوچیکه در حد 16 کیلوبایت و 32 کیلوبایت هست)
توی تصویر بالا همونطور که توضیح داده شد هر سطر حافظه نهان شامل یک بلاک هست و یک تگ، به هر سطر حافظه نهان میگن خط نمیگن سطر پس هر خط حافظه نهان یک تگ و یک بلاک داره که طبق تصویر هر بلاک K کلمه رو ذخیره میکنه. همین بلاک رو میشه برد توی حافظه و اونجا نشون داد پس میشه حافظه رو به بلاک های K کلمه ای تقسیم بندی کرد
وقتی پردازنده میره به یه آدرسی تا مقدارش رو بیاره این آدرس وارد حافظه کش میشه و به سرعت چک میشه که آیا این مقدار قبلا در حافظه کش ذخیره شده یا خیر و اگه آره سریع مقدارش به پردازنده میفرسته اگه موجود نباشه میره و از حافظه اصلی میاره توی کش و برای پردازنده میفرسته.
وقتی که پردازنده آدرس رو روی آدرس باس میزاره و کنترل باس رو برای خواندن فعال میکنه حافظه کش آدرس رو بر میداره و اگه موجود باشه بافر های آدرس و داده رو غیر فعال میکنه و پاسخ رو به پردازنده میده اینکار رو برای کاهش ترافیک سیستم باس انجام میده. شکل زیر این موضوع رو نشون میده.
Mapping Function : حالا بحث اصلی اینه که چطور میخوایم یه مقدار رو بیاریم توی حافظه نهان و چطور میخوایم اون آدرسی رو که پردازنده روی آدرس باس گذاشته رو تشخیص بدیم که آیا توی حافظه نهان هست یا نه؟
Direct Mapping یا نگاشت مستقیم:
در حالت دایرکت مپینگ از فرمول زیر استفاده میشه
i = j modulo m
که در اون
شماره خط حافظه نهان i = cache line number
شماره بلاک حافظه اصلی j = main memory block number
تعداد کل خطوط حافظه نهان m = number of lines in the cache
عبارت modulo یعنی باقی مانده یعنی همون % توی برنامه نویسی
یعنی اگه میخوای بدونی که بلاک j ام حافظه اصلی کجای حافظه نهان قرار داره عدد J رو بر تعداد خطوط حافظه نهان تقسیم کن و نتیجه اش میشه i که نشان دهنده خطی هست که بلاک J حافظه درش ذخیره شده.
بزارید به صورت ساده یه مثال بزنیم. فرض کنید اندازه حافظه دقیقا هم اندازه حافظه کش باشه در این صورت حداکثر j که همان شماره بلاک حافظه اصلی هست برابر خواهد شد با m که همان تعداد خطوط حافظه نهان است. (میتونید برای سادگی شما هم هر بلاک حافظه اصلی رو توی یک خط مثل حافظه نهان فرض کنید) حالا هر بلاک حافظه اصلی دقیقا متناظر میشه با یک خط از حافظه نهان شکل زیر
به این میگن نگاشت مستقیم یا دایرکت مپینگ. ولی حالا مگه اندازه حافظه اصلی اندازه حافظه نهان هست؟! هرگـــــز
بنابراین ما حافظه اصلی رو با اندازه ی حافظه کش تقسیم میکنیم! مثلا اگه در تصویر بالا اندازه حافظه اصلی دو برابر حافظه نهان باشه به این شکل میشه (عکس زیر رو خودم درست کردم و توی کتاب نیست)
هدف ام از ساخت عکس بالا اینه که بگم اگه حافظه اصلی دو برابر حافظه نهان باشه برای هر خط حافظه نهان دو تا کاندید وجود داره. این اتفاق با باقی مانده امکان پذیر هست! باقی مانده اگه عدد بلاک مربوط به حافظه (j) بزرگتر از کل تعداد خطوط حافظه کش (m) باشه میاد و یه عددی به ما میده که توی بازه ۰ تا m-1 هست.
یه مسئله ای رخ میده!
اگه هر خطی ممکنه چند تا کاندید داشته باشه پس ما از کجا بفهمیم که کدام کاندید الان توی کش هست؟!
اینجاست که تگ به کمک ما میاد!!
تصویر بالا داره فرمت آدرس حافظه اصلی رو نشون میده
اگه فرض کنیم که حافظه ما با 24 بیت آدرس دهی میشه (یعنی 16 مگ هست) میتونیم فرض کنیم که آدرس به سه بخش تقسیم میشه!
بخش Word توی تصویر بالا داره نشون میده که توی بلاک ما کدوم کلمه منظورت هست! الان اینجا 2 بیت هست یعنی هر بلاک ما 4 تا کلمه داره که بوسیله W بین این 4 کلمه یکی انتخاب میشه!
Line داره نشون میده که کدوم خط حافظه کش منظور ما هست!
و Tag هم داره نشون میده که کدوم یک از کاندید های مربوط به این خط توی این خط قرار گرفته!
میتونید بگید کدوم بلاک های حافظه برای خط 0 کاندید هستن؟
خیلی ساده :
00 00000000000000 00000000
00 00000000000000 00000001
00 00000000000000 00000010
00 00000000000000 00000011
00 00000000000000 00000100
00 00000000000000 00000101
................................
................................
00 00000000000000 11111111
همشون کاندید های مربوط به خط صفر حافظه کش هستن. نتیجه میگیریم به تعداد بیت های تگ، ما کاندید برای هر خط کش داریم. پس توی این مثال ما 8^2 یعنی 256 تا کاندید برای هر خط داریم.
حالا از کجا متوجه بشیم که تگ چند بیت هست؟!
برای بدست آوردن تعداد بیت تگ باید ابتدا تعداد بیت W و سپس تعداد بیت Line رو بدست آورد و از تعداد کل بیت های آدرس کم کرد.
در اینجا چون بلاک های ما هرکدام 4 کلمه هست پس بیت W برابر 2 میباشد و چون حافظه کش ما 64 کیلوبایت (16 بیت) هست و هر خط حافظه کش 4 کلمه هست بنابراین 64K/4 خط داریم یعنی 16k خط داریم که میشه 14 بیت
پس 2 بیت برای w و 14 بیت برای خطوط میشه 16 بیت و اگه از 24 بیت کم کنیم میشه 8 بیت که برابر تعداد بیت های تگ هست!
روش دیگه ای که میشه برای نگاشت حافظه نهان استفاده کرد روش انجمنی یا Associative هست که در ادامه توضیح میدم
روش نگاشت انجمنی یا Associative:
این روش خیلی ساده است ولی مدار پیچیده ای برای دیکد نیاز داره در نتیجه سرعتش پایین تر از روش نگاشت مستقیم هست! ولی باید بررسی بشه چون روش سوم ترکیبی از این دو روش هست.
اگه به تصویر فرمت آدرس که در بالا گذاشته بودم نگاه کنید شامل سه بخش Tag و Line و W هست. توی روش مستقیم هر خط فقط میتونه یه تعداد کاندید توی حافظه داشته باشه و در هر لحظه فقط یه کاندید میتونه توی کش باشه ولی در روش انجمنی اصلا چنین چیزی نداریم و هر بلاک از حافظه میتونه توی هر خط حافظه نهان قرار بگیره پس باید تگ طوری باشه که بتونه همه بلاک ها رو از هم تفکیک بده.
در این روش تگ به شدت بزرگ میشه و اگه مثال قبل رو در نظر بگیرید اندازه تگ میشه 22 بیت.
عکس زیر رو نگاه کنید:
داره نشون میده هر بلاک حافظه میتونه توی هر خونه ای از حافظه کش قرار بگیره.
اگه مثال قبل رو در نظر بگیرید که آرس ما 24 بیتی بود با روش انجمنی آدرس رو میشه به صورت زیر تفسیر کرد.
همانطور که میبینید تگ خیلی بزرگ شده و مدار مربوط به تگ هم پیچیده میشه و سرعت کار پایین میاد.
خلاصه اینکه این روش خیلی ساده است و هر بلاک حافظه هر کجا میتونه قرار بگیره و فقط باید حواسمون به Tag باشه که مسئول نشون دادن کل آدرس هست!
یک روش بین این روش و روش قبل هست که در ادامه میگم
روش انجمنی گروهی یا Set-Association:
همانظور که گفتم این روش ترکیب دو روش قبلی هست
به طور ساده: گفتیم که در روش نگاشت مستقیم هر خط حافظه شامل چند تا کاندید هست که در هر زمان فقط یک کاندید میتونه حضور داشته باشه! در این روش به جای اینکه فقط یک کاندید بتونه توی کش باشه 2 یا تعداد بیشتری میتونه توی کش باشه. برای اینکار نیاز به گروه بندی داریم.
یعنی باید هر چند تا خط رو به یک گروه نسبت بدیم! مثلا گروه 0 میتونه 512 تا نماینده داشته باشه که از این 512 تا نماینده میتونه 2 تاش توی کش باشه!
باید حافظه کش به V گروه تقسیم بندی بشه که هر گروه شامل K خط خواهد بود! در نتیجه تعداد کل خطوط باید K*V باشه یعنی
m = k*v
و رابطه دیگه هم اینه
i = j modulo v
که در اون:
شماره گروه درون کش i = cache set number
شماره بلاک حافظه اصلی j = main memory block number
تعداد کل خطوط کش m = number of lines in the cache
تعداد مجموعه ها v = number of sets
تعداد خطوط در هر مجموعه k = number of lines in each set
مثلا اگه به مثال قبل برگردیم که حافظه کش ما 64 کیلوبایت بود. و هر بلاک شامل 4 بایت بود که 16k خط داشتیم! میتونیم k رو 2 بگیریم یعنی برای اعضای هر مجموعه دو عضو میتونه توی کش حضور داشته باشه. اگه K=2 باشه آنگاه V=8k میشه یعنی 8 هزار مجموعه خواهیم داشت که از هر مجموعه دو عضو میتونه توی کش حضور داشته باشه. در این مثال فرمت آدرس به شکل زیر میشه
در این مثال k = 2 گرفته شده
اگه تصویر بالا رو با حالت نگاشت مستقیم مقایسه کنیم میبینیم که به جای Line عبارت Set قرار گرفته
اونجا 14 بیت بود اینجا 13 بیت. به عبارتی میشه گفت تعداد خطوط حافظه نهان نصف شده! چرا؟!
چون دیگه هر دو خط دارن یک مجموعه رو نگه میدارن. همچنین همونطور که توی نگاشت مستقیم گفتیم که حافظه اصلی رو به تعداد خطوط حافظه نهان تقسیم میکنیم اینجا حافظه اصلی رو به تعداد V تقسیم میکنیم (چون حافظه نهان الان دیگه نصف به نظر میرسه).
نکته اینه که اگه K یک باشه همون حالت نگاشت مستقیم رخ میده و اگه V یک باشه حالت نگاشت انجمنی رخ میده.
همین مطلب ناقص 5 ساعت ناخالص وقتم رو گرفت
امیدوارم که مفید بوده باشه
فعلا
یا علی مدد..!
فو العاده بود،خداقوت پیروز باشید