معماری کامپیوتر _ حافظه
مباحث زیادی در این قسمت وجود داره که من می خوام در مورد مباحث مربوط به نگاشت حافظه بگم و همچنین مباحثی خاص در مورد کش و همچنین قسمت هایی که ازش سوال میاد رو بیان کنم ولی پیشنهاد میکنم اگر استادتون چیزی فراتر از این مباحث گفته پس به کتاب یا جزوه استادتون هم حتما مراجعه کنین.
خب میدونین که کش برای سرعت بخشیدن واسه استفاده از دیتا هایی که در حافظه داریم خیلی مناسبه یعنی زمان دسترسی به حافظه خیلی زیاد اگر بخواین چیزی از حافظه بردارین کلی زمان باید مصرف کنین چون حافظه خیلی بزرگه و زمان جست و جو برای پیدا کردن دیتا خیلی طول میکشه.
پس اومدن کش رو درست کردن که یه چیزی مثل حافظه اما خیلی کوچیک تر که زمان پیدا کردن دیتا در اون خیلی کمتره.
حالا ما دیتا هایی که خیلی بهشون نیاز پیدا می کنیم و به خاطرش مجبوریم همش بریم حافظه رو بگردیم پیداش کنیم و بیارمش رو میذاریم در کش که هر وقت بهشون نیاز داشتیم سریع تر پیداشون کنیم.
حالا فرض کنین شما دنبال یک دیتا خاص می گردین حالا برای پیدا کردنش باید چیکار کرد؟
آیا در کش هست یا نیست ؟
جواب اینه که هر وقت به یک دیتا نیاز داشتین اول کش رو میگردین که آیا در کش هست یا نه , اگر بود که بر میدارین و میرین اما اگر نبود باید برین در حافظه اصلی و بیارینش.
حالا میخوایم بگیم که چطوری کش رو پر کنیم و دیتا بهش بدیم :
قانون کار اینه که همیشه تعداد ستون های حافظه اصلی و کش با هم برابرند.
حافظه و کش از تعدادی سطر تشکیل شدن که هر سطر تعدادی ستون داره دقیقا مثل یک ماتریس دو بعدی.
وقتی شما میرین در حافظه و یک مقدار رو بر میدارین قانونه نگاشت بهتون میگه که باید اون رو در کش هم قرار بدین تا شاید در آینده نزدیک دوباره مورد استفاده قرار بگیره.
شما مثلا به سطر ۱۰۰ ستون ۵ از حافظه نیاز دارین خب طبیعتا میرین در حافطه , سطر ۱۰۰ , ستون پنجمش رو میگیرین و کارتون رو انجام می دین اما قانونه نگاشت میگه که وقتی دیتا مورد نظرتون رو گرفتین باید کل سطرش رو در کش قرار بدین یعنی در این مثال باید کل سطر ۱۰۰ رو در یکی از سطر های کش قرار بدین.(با توجه به این نکته که اندازه سطر در حافظه با اندازه سطر در کش برابر یعنی همون برابری ستون های کش و حافظه اصلی )
حالا به نظرتون این کار واسه چیه ؟ چرا کل سطر رو میارن ؟
جواب اینجاست که باید توجه کنین برنامه داره با یه ترتیبی اجرا میشه , وقتی شما الآن به سطر ۱۰۰ ستون ۵ نیاز دارین احتمالش خیلی زیاده در دستور بعدی به ستون های دیگش نیاز داشته باشین یعنی مثلا سطر ۱۰۰ ستون ۱ , پس میان کل سطر رو ذخیره میکنن تا این مشکل هم حل بشه.
پس تا حالا متوجه شدیم نگاشت چیه , به قرار دادن یک سطر حافظه در یک سطر کش میگن نگاشت.
حالا سوال اینجا پیش میاد که وقتی یک سطر از حافظه رو گرفتیم در کدوم سطر از کش قرارش بدیم ؟
در جواب این سوال روش های نگاشت مطرح میشن که عبارت اند از direct mapping , fully associative , set associative که در ادامه به توضیح نحوه عملکرد این روش ها می پردازیم.
برای شروع نیاز به یک مثال داریم تا ایم روش هارو روشون پیاده سازی کنیم و توضیحاتمون رو بر روی این مثال انجام بدیم.
فرض کنید که ما یک حافظه ۳۲* ۴ داشته باشیم یعنی حافظه ای که ۳۲ سطر و هر سطر دارای ۴ ستون است.
میشه با یک ضرب ساده فهمید که تعداد خانه های این حافظه برابر ۳۲ * ۴ = ۱۲۸ است یعنی در کل ۱۲۸ خانه دارد که به صورت یک ماتریس ۳۲ سطری و ۴ ستونی در آمده است.
برای اینکه بتونیم به تک تک اینخانه ها دسترسی داشته باشیم باید بتونیم به تک تک این خونه ها آدرس بدیم یعنی به کل این ۱۲۸ خانه , پس برای آدرس دهی به آن نیاز به ۷ بیت (۲۷=۱۲۸) نیاز داریم پس آدرس ما در اینجا ۷ بیت است.
حالا شروع میکنیم به توضیح اولین روش نگاشت یعنی direct mapping یا همون نگاشت مستقیم.
همون طور که از اسمش معموله ما اینجا قراره یک سطر از حافظه رو به طور مستقیم و پیش بینی شده در یک سطر از کش قرار بدیم به این صورت که در موقع نگاشت ما دیتا را در محل خاصی میگذاریم که وقتی دنبالش میگردیم فقط همون محل خاص رو بگردیم.
به مثال زیر توجه کنید :
فرض کنید که کش ما هم ۴ سطر دارد به همراه همون حافظه ۳۲ سطری .
حالا میخوایم بدونیم وقتی سطر x از حافظه میاد باید در کدوم سطر از کش قرار بگیره.
در روش مستقیم میگن شماره سطر حافظه رو تقسیم بر تعداد سطر های کش کن و اون سطر حافظه رو در باقیمانده این تقسیم قرار بده برای مثال فرض کنید سطر ۱۰ حافظه رو میخواین در کش قرار بدین حالا باید ابتدا ۱۰ رو بر ۴ ( تعداد سطر های کش) تقسیم کنیم بعد ببینیم باقیماندش چند میشه که باقیمانده این تقسیم میشه ۲ پس ما باید در اینجا سطر ۱۰ حافظه رو در سطر ۲ کش قرار بدیم.
این کارو چطوری باید انجام داد یا بهتره بگم روش حل مسایل چطوریه ؟
تو همین مثال توجه کنین که ما ۷ بیت آدرس حافظه داریم که چون ۳۲ سطر داریم و ۴ ستون پس ۵ بیت پرارزش آن برای شماره سطر و ۲ بیت کم ارزش آن برای شماره ستون است یعنی ۵ بیت اول میگه کدام یک از ۳۲ سطر منظورمونه و ۲ بیت بعد میگه در اون سطر کدام یک از ۴ ستونش منظور ماست.
پس اگر این xxxxxxx را ۷ بیت آدرس خود فرض کنیم ۲ x سمت راست مربوط به شماره ستون است که با صحبت هایی که شد ما با سماره سطر کار داریم نه با شماره ستون چون ما قراره کل یک سطر رو در کش ذخیره کنیم پس مد نظر با ۵ بیت اول آدرس می باشد.
حالا ما باید با این ۵ بیت باقیمانده شماره سطر کش رو به دست بیاریم.
یه نکته اینجاست که وقتی یک عدد باینری رو در تقسیم بر ۲ کنین در عمل یعنی بیت سمت راست یا همون کم ارزشش رو حذف کردین و اگر باقیمانده به ۲ بیگیرین در عمل انگار بیت سمت راستش رو به عنوان جواب در نظر گرفتین , تقسیم بر ۴ میشه ۲ بیت سمت راست , تقسیم بر ۸ میشه ۳ بیت سمت راست و … .
حالا اینجا چون ما ۴ سطر کش داریم پس باید این عدد ۵ بیتی رو باقیمانده بگیریم به ۴ و طبق نکته بالا در عمل داریم ما ۲ بیت سمت راستشو میگیریم.
پس از این ۵ بیت باقیمانده ۲ بیت راستش هم شد به عنوان شماره سطر کش.
حالا ۳ بیت هنوز مونده که این ۳ بیت رو به عنوان tag در نظر میگریم.
Tag چیه ؟
خب طبق گفته ما اگر سطر ۱۰ حافظه بیاد در کش باید بره در خونه ۲ قرار بگیره چون باقیماندش به ۴ میشه ۲ .
حالا اگر سطر ۶ بیاد چی میشه ؟
بله ۶ هم باقیماندش به ۴ میشه ۲ پس اون هم باید در سطر ۲ قرار بگیره و ۱۰ رو از اونجا حذف کنه تا خودش بتونه اون جا قرار بگیره.
حالا سوال اینجا پیش میاد وقتی شما دنبال سطر ۱۰ میگردین از کجا می فهمین در کش هست یا نه ؟
باید باقیمانده بگیرین به ۴ که میشه ۲ پس اگر سطر ۱۰ حافظه بخواد در کش باشه باید در سطر دوم کش باشه و نه در جای دیگه.
پس میرین سراغ سطر دوم کش که ببینین سطر ۱۰ حافظه اونجا هست یه نه , وقتی میرین به سطر دوم کش می بینین که داخلش یه مقداری قرار داره اما از کجا میدونین چیزی که داخلش هست محتوای سطر ۱۰ حافظه است یا محتوای سطر ۶ حافظه ؟
جواب شما tag است.
درسته باقیمانده این دو عدد به ۴ با هم برابر شده است اما آن ۳ بیتی که از ۵ بیت آدرس سطر آن ها باقیمانده با هم فرق دارد پس ما میتوانیم از طریق آن ۳ بیت بفهمیم که مقدار داخل این سطر برابر با کدوم سطر از حافظه است که این ۳ بیت رو ( در این مثال شده ۳ بیت ) به عنوان tag در یک بسته بندی جدا کنار هر سطر از کش قرار میدیم.
پس برای مثال بالا که در کل ۷ بیت بود این اتفاق افتاد :
۲ بیت برای ستون | ۲ بیت برای شماره سطر | ۳ بیت برای tag |
یه بار دیگه ببینیم این روش چیه و چطوری کار میکنه :
اول اینکه این روش میگه باید هر سطری از حافظه رو در یک سطر خاص از کش قرار بدیم موقع نگاشت و با این کار باعث میشه که وقتی دنبال یه سطری میگردیم که اول باید کش رو بگردیم دیگه لازم نیست واسه پیدا کردنش کل کش رو بگردیم بلکه فقط باید چک کنیم در یک خونه ی خاص هست یا نه که اگر اونجا بود پس حتما در کل کش هم نیست که بعدش دیگه میریم از حافظه میاریمش.
بعد در مورد این صحب کردیم که اون خونه خاصی که باید درونش قرار بدیم کجاست که الگوریتم این بود که باید شماره سطر حافظه رو به تعداد سطر های کش باقیمانده بگیریم و در آن جا قرار بدیم.
در مورد tag و اهمیت اون هم توضیح داده شد.
در ادامه روش های بعدی رو توضیح میدم و سپس یک مثال کلی براشون حل میکنم.
روش نگاشت بعدی ای که میخوام بگم روش fully associative است.
خب اول میخوام یک نقطه ضعف از روش مستقیم بهتون بگم بعد به این روش جدید برسیم.
در روش مستقیم ما هر سطر حافظه رو در یک سطر خاص قرار میدادیم خب این خوبیش این بود که وقتی دنبال یک سطر خاص میگشتی میدونستی دقیقا باید کجارو بگردی یعنی لازم نبود کل کش رو بگردی و فقط یک خونه رو میگشتی و پیداش میکردی و یا اگر نبود یعنی دیگه کلا در کش نیست.
اما بدی ای که داره اینه که فرض کنین در همین مثال قبل اول سطر ۲ رو نیاز داشته باشین که این سطر میاد میره سطر دوم کش بعد سطر ۶ رو نیاز داشته باشین که اونم باید بره سطر دوم کش پس قبلی باید پاک بشه بعد سطر ۱۰ بیاد ۶ رو پاک کنه بعد ۱۴ بیاد ۱۰ رو پاک کنه و خودش بشینه و … اگه دقت کنین تکام این اعداد باید در خونه ۲ کش قرار بگیرن و مجبورن نفر قبلی رو پاک کنن در حالی که ما ۳ تا خونه خالی دیگه داریم اما اینا گیر دادن به همین یه خونه چون روشمون همینه و باید در همین خونه قرار بگیرن پس این روش زمانی که سطر هایی با باقیمانده یکسان پشت سر هم فراخوانی میشن خوب کار نمیکنه و یا به اصطلاح از حافظه ای که در اختیار داره بهینه استفاده نمیکنه.
این روش جدید یعنی fully associative یا همون تمام انجمنی میاد این نقض رو برطرف میکنه.
این روش میگه اگر سطری از حافظه رو خواستی در کش بذاری دیگه مهم نیست کجا بذاری باید در اولین خونه خالی ای که پیدا کردی قرارش بدی.
اینجا داریم از حافظه به خوبی استفاده می کنیم اما بدی ای که داره اینه که واسه اینکه بفهمی سطر x از حافظه در کش هست یا نه مجبوری کل کش رو بگردی تا بفهمی هست یا نه بر عکس روش قبل که فقط یک خونه رو چک میکرد.
حالا ببینیم اینجا ۷ بیت آدرس ما چگونه تفکیک میشه(طبق مثال قبل در نگاشت مستقیم ).
خب طبق گفته قبلی ۲ بیت که میره واسه ستون که در هر ۳ روش این اتفاق میفته چون ما فقط با شماره سطر کار داریم.
۵ بیت باقیمانده اینجا کلا میشه tag چون دیگه اینجا قرار نیست بدونیم هر سطر دقیقا در کدوم سطر کش قرار داره , به شکل زیر توجه کنید که در کل ۷ بیت است :
۲ بیت ستون | ۵ بیت tag |
خب دیدم این روش نقطه ضعف روش قبل رو پوشش داد اما خودش هم نقطه ضعف داره.
روش بعدی set associative است که تلفیقی از هر دو روش است یعنی از هر دو روش استفاده کرده و سعی کرده از نقاط قوت هر دو روش استفاده کنه.
در اینجا به جای اینکه بدونیم هر سطر حافظه دقیقا در کدوم سطر از کش قرار میگیره به جاش میتونیم بفهمیم در کدوم سطر ها ممکنه باشه یعنی مثلا به جای دقیقا یک سطر یه منطقه یا به اصطلاح یک set از سطر هارو بهش نشون میدیم تا در یکیشون قرار بگیره.
در صورت سوال هم میگه که هر set باید چند سطر رو داشته باشه مثلا میگه ۲-way set associative که یعنی ما باید هر ۲ سطر از کش رو تبدیل کنیم به یک set که هر سط یک شماره داره.
برای مثال فرض کنید که حافظه ما همون ۱۲۸ خونه ینی ۷ بیت آدرس است اما کش ما ۸ سطر دارد و روش نگاشت ۲-way set associative میباشد یعنی ما باید هر دو سطر از کش رو در یک set قرار بدیم پس ما اینجا ۴ set خواهیم داشت با نام های s0 , s1 , s2 , s3 که مثلا در s0 ما سطر های شماره ۰ و ۱ رو داریم و در s1 سطر های ۲ و ۳ و به همین ترتیب … .
در اینجا وقتی یک سطر از حافظه میاد ما از روش مستقیم استفاده میکنیم اما میگیم که در کدوم set قرار بگیر پس شماره سطر حافظه رو باقیمانده میگیریم به تداد set هایی که داریم بعد متوجه میشیم که باید در کدوم set قرار بگیره , بعد از اون در set ای که مشخص شد در اولین خونه خالی در اون set قرار میگیره (مثل روش تمام انجمنی ) .
پس ما اینجا برای این ۷ بیت باید ابتدا طبق معمول بیت های مربوط به ستون رو جدا کنیم که اینجا ۲ بیت است سپس بیت های مربوط به شماره set رو جدا کنیم که چون ۴ تا set داریم میشه ۲ بیت و بعد هرچی موند میشه tag که اینجا ۳ بیت است.
دقت کنید که ما تعداد set هارو در نظر گرفتیم اما در روش مستقیم تعداد سطرها مد نظرمون بود یعنی اگه همین مثال یعنی ۸ سطر کش را برای روش مستقیم در نظر بگیریم به جز ۲ بیت برای ستون ما باید ۳ بیت برای شماره سطر در نظر بگیریم چون ۸ سطر داریم و ۲ بیت باقیمانده میشد tag در روش تمام انجمنی هم که همیشه ستون رو جدا کنین بقیش میشه tag .
شکل set associative به صورت زیر است :
ستون | set | tag |
خب حالا که با روش ها آشنا شدیم وقتشه که یه مثال بهتر داشته باشیم و هر سه روش رو درونش پیاده سازی کنیم و به جواب های مختلف برسیم.
قبل از اعلام مثال چند نکته بگم که برای اینجور سوال ها همیشه باید به یه صورتی اندازه ی حافظه رو در سوال به ما بدهند تا ما بفهمیم چند بیت آدرس داریم , ممکنه بگن مثلا ۲ گیگ ram داریم که کار ما آسون شده یعنی حجم ram رو بهمون داده و اینجا میشه فهمید چون گیگ یعنی ۲ به توان ۳۰ و چون ۲ گیگ ram داریم یعنی ۲ به توان ۳۱ بایت ram داریم که در این حالت ۳۱ بیت آدرس داریم , یا بگن ram ما دارای ۳۲ بلاک ۴ بایتی است که باید ضرب کنیم که میشه ۱۲۸ بایت که میفهمیم ۷ بیت آدرس داریم.
دقت داشته باشید که تعداد ستون های سطر و ram با هم برابرند.
از طرفی ما باید بتونیم تعداد سطر های کش رو به دست بیاریم یعنی اگر حجم کش رو بهمون دادن ما باید بفهمیم چندتا سطر داره که اگر حجم رو تقسیم بر تعداد ستون ها کنیم تعداد سطر ها به دست میاد چون حجم از ضرب سطر در ستون به دست اومده پس اگر حجم رو تقسیم بر هر کدومشون کنی اون یکی به دست میاد.
مثال :
پردازنده ای دارای ۴ گیگا بایت حافظه ram و دارای کش به اندازه ۵۱۲ کیلو بایت است . اگر سایز هر بلاک ۱۶ بایت باشد , حجم مورد نیاز جهت ذخیره سازی tag را در روش های direct mapping , fully associative , 2-way set associative مشخص کنید ؟
پاسخ :
خب اینجا حجم ram رو داریم و نیاز به شرب کردن سطر در ستون نیست.
۴ گیگ یعنی ۲ به توان ۳۲ بایت چرا چون ۴ که میشه ۲ به توان ۲ که ضرب میشه در گیگ که میشه ۲ به توان ۳۰ .
پس ما ۳۲ بیت آدرس داریم.
لازم به ذکر است که گیگ یعنی ۲ به توان ۳۰ و مگ یعنی ۲ توان ۲۰ و کیلو یعنی ۲ به توان ۱۰ .
از طرفی ما اینجا حجم کش رو داریم پس باید تعداد سطر های کش رو به دست بیاریم.
۵۱۲ کیلو یعنی : ۲۹ * ۲۱۰ = ۲۱۹ بایت که ۵۱۲ یعنی ۲ به توان ۹ و کیلو هم ۲ به توان ۱۰ .
پس ما در کل ۲ به تون ۱۹ بایت کش داریم اما در این کش چند سطر وچود داره ؟
در سوال گفته سایز هر بلاک ۱۶ بایت است یعنی سر سطر سایزش یا همون تعداد ستون هاش ۱۶ بایت است که یعنی در کش و در حافظه ما ۱۶ ستون داریم یعنی ۲ به توان ۴ تا .
تعداد سطر های کش میشه : ۲۱۹ / ۲۴ = ۲۱۵ یعنی ما ۲ به تان ۱۵ تا سطر کش داریم.
اشتباه نکنید ما ۱۵ تا سطر نداریم , بله ۲ به توان ۱۵ سطر داریم یعنی ۱۶۳۸۴ سطر در کش داریم.
خب حالا روش direct mapping رو چک کنیم که چند بیت برای tag نیاز داره :
ما ۱۶ تا ستون داریم یعنی ۲۴ ستون داریم پس ۴ بیت برای ستون در هر سه روش نیاز داریم.
در روش direct mapping باید باقیمانده بگیریم به تعداد سطر های کش که ۲۱۵ تا میباشد پس اینجا ۱۵ بیت برای شماره سطر کش نیاز داریم.
خب ۱۹ بیت که رفت , حالا از ۳۲ بیت فقط ۱۳ بیت باقی مونده که میشه tag .
به شکل زیر توجه کنید :
۴ بیت ستون | ۱۵ بیت ستون | ۱۳ بیت tag |
خب نکته اینجاست که ما برای هر یک سطر از کش ۱۳ بیت tag داریم .
سوال اینه که حجم مورد نیاز برای tag در کل کش چقدره ؟
خب ما ۲۱۵ تا سطر داریم که هر سطر ۱۳ بیت tag داره پس ۲۱۵ * ۱۳ میشه حجم مورد نیاز برای ذخیره سازیه tag که به ازای هر سطر ۱۳بیت در نظر گرفته شده است .
خب حالا در روش fully associative چک کنیم ببینیم چند بیت برای tag نیاز داریم و حجم مورد نیاز برای tag چقدر میشه.
در این روش تعداد بیت های ستون رو جدا میکردیم که ۴ بیت است و بقیش میشد tag .
4 بیت ستون | ۲۸ بیت tag |
حجم مورد نیاز برای ذخیره سازی tag = 215 * 28
روش ۲-way set associative :
طبق صورت سوال ما باید از روش ۲-way استفاده کنیم یعنی هر دوتا سطر رو یک set در نظر بگیریم پس برای اینکه بفهمیم چند set داریم باید اعداد سطر های کش رو تقسیم بر ۲ کنیم ( چون ۲-way است , اگر ۴-way بود تقسیم بر ۴ میشد و به همین ترتیب … )
۲۱۵ / ۲۱ = ۲۱۴ پس یعنی ما ۲ به توان ۱۴ تا set داریم پس یعنی ۱۴ بیت نیاز داریم برای آدرس دادن به این set ها .
۴ بیت ستون | ۱۴ بیت set | 14 بیت tag |
خب ۱۴ بیت tag داریم , حالا حجم مورد نیاز برای ذخیره سازی tag چقدره ؟
توجه کنین که هر tag برای یک سطر است نه برای هر set پس باید تعداد بیت ها ی tag رو ضرب در تعداد سطر ها کنیم که ۲۱۵ است نه تعداد set ها که ۲ به توان ۱۴ به دست آمده پس جواب برابر : ۲۱۵ * ۱۴ می باشد.
این یه مثال بود که در این قسمت دید , حالا میخوام یک مثال از نوعی دیگر براتون بزنم که نحوه عملیاتی این روش ها درونش بررسی میشه .
یه نکته اینکه در روش direct mapping معلومه هر سطر کجا باید بره و اگر پر بود قبلی رو پاک میکنه اما اگر روش fully associative باشه وقتی کش پر باشه کجا باید بشینه یا بهتره بگیم که کدوم سطر باید حذف بشه که دو روش اینجا معرفی میکنیم به اسم های FIFO و LRU که در مثال می بینید.
نکته بعدی که منظور از hit یعنی زمانی که دنبال یک سطر میگردین و در کش پیداش میکنین به اصطلاح hit شده و اگر در کش نباشه و مجبور بشین برین از ram بیارینش به اصطلاح miss شده که نرخ hit یعنی تعداد hit ها تقسیم بر تعداد کل و نرخ miss یعنی تعداد miss ها تقسیم بر تعداد کل .
مثال :
فرض کنید ظرفیت کش ما ۴ بلاک ۴ بایتی است.
اگر در حین اجرای برنامه رد آدرس زیر تولید شود نرخ hit , miss را در شرایط زیر به دست آورید :
الف ) شیوه نگاشت direct mapping
ب ) شیوه نگاشت fully associatve و روش جایگزینی FIFO
ج ) شیوه نگاشت fully associative و روش جایگزینی LRU
د ) شیوه نگاشت ۲-way set associative و روش جایگزینی LRU
رد آدرس به صورت زیر است :
۳,۶۵,۱,۳۳,۴,۹,۵,۲,۳۹,۶,۸,۱۳,۷,۳۶
خب اینجا منظور از رد آدرس اینه که هر عددی که می بینین منظورش شماره خونه دیتایی هست که میخواد نه شماره سطر اون دیتا در حالی که ما فقط با شماره سطر کار داریم.
برای اینکه این عدد ها رو به شماره سطر تبدیل کینم باید هر یک رو بر تعداد ستون ها تقسیم کنیم تا شماره سطرشون به دست بیاد.
کش در اینجا ۴ بلاک ۴ بایتی است از روی ۴ بلاک می فهمیم که ۴ سطر داره و از روی ۴ بایتی بودنش می فهمیم ۴ ستون داره و از اونجایی که تعداد ستون های کش و ram با هم برابرند پس ram هم دارای ۴ ستون است پس این اعداد باید تقسیم بر ۴ بشوند که تعداد ستون ها است .
پس از تقسیم کردن اعداد به صورت زیر در می آیند که نشان دهنده شماره سطر است :
۰,۱۶,۰,۸,۱,۲,۱,۰,۹,۱,۲,۳,۱,۹
شماره سطر ها از حاصل تقسیم بر تعداد ستون ها به دست آمد . توجه کنید حاصل تقسیم , نه باقیمانده تقسیم.
حالا ما شماره سطر هارو داریم.
خب حالا به قسمت الف از سوال پاسخ میدیم که اگر شماره سطر های بالا به ترتیب وارد بشن با روش direct mapping چند hit و چند miss خواهیم داشت :
در نظر داشته باشید که در ابتدا کش خالی است.
ابتدا سطر ۰ میاد و miss میشه چون هیچی نیست و بعد سطر ۰ حافظه رو میاریم و میذاریم در سطر ۰ از کش .
Block 0 |
سپس سطر ۱۶ میاد که چون نیست میره از ram میاره و میخواد بذاره در کش که باید تقسیم بر ۴ یعنی تعداد سطر های کش بشه و باقیماندش حساب بشه که ۰ هستش پس باید بره در خط کش قرار بگیره اما چون سطر ۰ پر هستش مجبوره قبلی رو پاک کنه و خودش در اونجا بشینه.
Block 16 |
حالا ۰ میاد که باز می بینیم ۰ دیگه در کش نیست چون توسط ۱۶ حذف شده پس بازهم miss میشه :
Block 0 |
حالا ۸ میاد که باز miss میشه چون در کش نیست و میره از ram میاره و چون باقیماندش به ۴ میشه ۰ اون رو باید در سطر ۰ کش قرار بدیم و block 0 رو باید حذف کنیم :
Block 8 |
1 میاد و نیست و miss میشه و در سطر ۱ قرار میگیره ( هر عددی کوکتر از x باقیماندش به x میشه خودش و اینجا باقیمانده ی اعداد زیر ۴ به ۴ میشن خودشون )
Block 8 |
Block 1 |
حالا ۲ میاد که باز نیست و miss میشه و در سطر ۲ قرار میگیره :
Block 8 |
Block 1 |
Block 2 |
حالا ۱ میاد و چون در سطر یک کش این بلاک وجود داره پس hit میشه و کش تغییری نمیکنه و مثل شکل بالا باقی می مونه .
حالا ۰ میاد نیست miss میشه میره سطر ۰ :
Block 0 |
Block 1 |
Block 2 |
حالا ۹ میاد نیست miss میشه و باید بره در سطر یک از کش :
Block 0 |
Block 9 |
Block 2 |
حالا ۱ میاد و چون نیست miss میشه و میره سطر یک از کش :
Block 0 |
Block 1 |
Block 2 |
حالا ۲ میاد و هست و hit میشه.
حالا ۳ میاد و نیست و miss میشه و میره در سطر سوم از کش :
Block 0 |
Block 1 |
Block 2 |
Block 3 |
حالا ۱ میاد و چون هست hit میشه.
حالا ۹ میاد و نیست و miss میشه و میره سطر یک از کش :
Block 0 |
Block 9 |
Block 2 |
Block 3 |
ما در اینجا از ۱۴ مرتبه ارجاعی که داشتیم ۳ بار hit و ۱۱ بار miss داشتیم پس :
Hit rate = 3 /14 , miss rate = 11 / 14
خب حالا بریم ببینیم در قسمت ب باید چکار کنیم :
شماره سطر هارو که داریم و ۱۴ مرتبه ارجاع داریم.
در شکل زیر سطر اول شماره سطر های درخواستی هستند و سطر دوم نشان دهنده HIT و MISS میباشد و ۴ سطر بعدی حالت کش را شبیه سازی میکند.
در نظر داشته باشید که روش FIFO میگه که هنگام حذف کسی رو حذف کن که زودتر از همه اومده باشه.
به طرز اضافه کردنه من در جدول دقت کنین این یه روش برای جلوگیری از خطای محاسباتی شماست که هرکسی وارد بشه از بالا وارد میکنم تا در نهایت هرکی پایین تر باشه یعنی از بقیه زودتر اومده و حذف میشه.
۹ | ۱ | ۳ | ۲ | ۱ | ۹ | ۰ | ۱ | ۲ | ۱ | ۸ | ۰ | ۱۶ | ۰ |
h | m | m | h | h | m | m | h | m | m | m | hit | m | miss |
1 | 1 | 3 | 9 | 9 | 9 | 0 | 2 | 2 | 1 | 8 | 16 | 16 | 0 |
3 | 3 | 9 | 0 | 0 | 0 | 2 | 1 | 1 | 8 | 16 | 0 | 0 | |
9 | 9 | 0 | 2 | 2 | 2 | 1 | 8 | 8 | 16 | 0 | |||
0 | 0 | 2 | 1 | 1 | 1 | 8 | 16 | 16 | 0 |
در اینجا ۵ تا hit داشتیم و ۹ تا miss که میشه :
Hit rate = 5 / 14 , miss rate = 9 / 14
این جا از روش جایگزینی FIFO استفاده کردیم که هرکی زودتر اومده بود میرفت بیرون.
حالا در قسمت ج این سوال میخوایم از LRU به جای FIFO استفاده کنیم.
این روش میگه کسی رو حذف کن که دیرتر از همه ازش استفاده شده یعنی به گذشته نگاه کن هرکی این اواخر ازش استفاده شده رو نگه دار و از انتها به ابتدا ( منظور از انتها یعنی جایی که الان هستیم ) بین کسایی که در کش هستند آخرین نفری که دیدی رو حذف کن.
برای راحتی کار و دوری از اشتباه محساباتی به روش زیر دقت کنین.
در اینجا هروقت کسی hit بشه میاد بالای صف قرار میگیره اما در FIFO مکانش تغییر نمیکرد .
اینجا هم هرکی آخر باشه حذف میشه با فرق اینکه هرکی رو ببینیم و hit بشه هرجا باشه میاد بالای صف قرار میگیره.
9 | 1 | 3 | 2 | 1 | 9 | 0 | 1 | 2 | 1 | 8 | 0 | 16 | 0 |
h | h | m | h | h | m | h | h | m | m | m | hit | m | miss |
9 | 1 | 3 | 2 | 1 | 9 | 0 | 1 | 2 | 1 | 8 | 0 | 16 | 0 |
1 | 3 | 2 | 1 | 9 | 0 | 1 | 2 | 1 | 8 | 0 | 16 | 0 | |
3 | 2 | 1 | 9 | 0 | 1 | 2 | 8 | 8 | 0 | 16 | |||
2 | 9 | 9 | 0 | 2 | 2 | 8 | 0 | 0 | 16 |
در اینجا ۷ تا hit داشتیم و ۷ تا miss که میشه :
Hit rate = 7 / 14 , miss rate = 7 / 14
خب این از روش fully associative حالا میریم سراغ ۲-way set associative که قسمت د از سوال است.
اینجا ۴ بلاک داریم یعنی کش ما ۴ سطر دارد که اگر ۲-way انجام بدیم یعنی هر ۲ بلاک رو یک set در نظر بگیریم پس ما ۲ تا set داریم که هر set نیز ۲ تا سطر دارد.
میتونین همانند روش direct mapping کش رو بکشین و set هارو جدا کنین و هر عدد رو در set مربوطه برده و سپس به صورت fully associative درون set قرار بدین یعنی در اولین خونه خالی در آن set که اگر پر بود باید از روش LRU استفاده کنید.
اما روش پیشنهادی بنده برای جلوگیری از خطا اینه که ابتدا set هارو جدا کنین بعد برای هر set جداگانه اعدادی که به آن set مربوط میشوند را به ترتیب جدا کنید و در نهایت بر روی هر set عمل LRU را انجام دهید.
در این مثال ما دو تا set داریم به اسم های s0 و s1 که تمام اعدادی که باقیمانده آن ها به ۲ برابر ۰ می شود باید در s0 قرار بگیرند و اعدادی که باقیمانده یک دارند باید در s1 قرار بگیرند.
همانطور که از قبل داشتیم اعداد به صورت زیر هستند.
9 | 1 | 3 | 2 | 1 | 9 | 0 | 1 | 2 | 1 | 8 | 0 | 16 | 0 |
حالا از چپ به راست به ترتیب اعدادی که باقیمانده به ۲ آن ها برابر ۰ هستند را به ترتیب بنویسید :
۲ | ۰ | ۲ | ۸ | ۰ | ۱۶ | ۰ |
توجه کنید که در s0 فقط این اعداد می آیند و اعداد دیگر هیچ نقشی در s0 ندارند پس می توانیم این قسمت را جدا حساب کنیم پس حالا روی این اعداد عمل fully associative را انجام دهید البته با توجه به اینکه ما در s0 هستیم پس در نظر داشته باشید که اینجا ۲ سطر داریم نه ۴ سطر پس داریم(با الگوریتم جایگزینیه LRU ) :
2 | 0 | 2 | 8 | 0 | 16 | 0 |
hit | miss | miss | miss | hit | miss | miss |
2 | 0 | 2 | 8 | 0 | 16 | 0 |
0 | 2 | 8 | 0 | 16 | 0 |
حالا اعدادی که باقیمانده ۱ دارند را از چپ به راست جدا کنید و با LRU پیاده سازی کنید :
۹ | ۱ | ۳ | ۱ | ۹ | ۱ | ۱ |
miss | hit | miss | hit | miss | hit | miss |
9 | 1 | 3 | 1 | 9 | 1 | 1 |
1 | 3 | 1 | 9 | 1 |
همانطور که می بینید ۲ تا hit در s0 داریم و ۳ تا hit در s1 پس درکل ۵ hit داریم :
Hit rate = 5 /14 , miss rate = 9 / 14
خب اینم از حل این سوال امیدوارم که کاملا متوجه شده باشید.
یه نکته بگم که اینجا ۴ بلاک ۴ بایته بود که تقسیم بر ۴ بایت شد و در direct ما باقیمانده به تعداد سطر ها یعنی ۴ میگرفتیم حالا اگر ۸ بلاک ۴ بایته داشتیم چی ؟
بله تقسیم به ۴ و در direct mapping باقیمانده به ۸ .
با همین فرض در قسمت د سوال بالا ما ۴ تا set خواهیم داشت.
خب مباحث اصلی ای که میخواستم بگم همین بود ولی برای مثال برای یک موضوضع دیگه نکاتی بیان میکنم.
وقتی یک کش دارین و میخواین دنباله چیزی بگردین باید اول برین در کش بگردین و بعد اگر نبود برین سراغ ram حالا اگر بخوایم یک میانگینی بگیریم از زمان دسترسیمون باید ببینیم چه زمان هایی miss میشیم و مجبوریم بریم سراغ ram .
Tavg = tcach + (miss)miss penalti
یعنی ببینیم چند درصد از دیتا ها در کش نیستند ( miss ) آن را در جریمه دسترسی به ram ضرب کنیم.
برای درک بیشتر به مثال های زیر توجه کنید :
فرض کنید CPIbase =1 و نرخ کلاک ۵۰۰ MGH , زمان دسترسی به حافظه اصلی ۲۰۰ ns , نرخ نقصان دستورات در کش L1 برابر ۵% . ماشین چند برابر سریع می شود اگر از یک کش L2 که زمان دسترسی ۲۰ ns دارد استفاده کنیم . در ضمن در این صورت نرخ نقصان به حافظه اصلی به ۲% کاهش میابد .
پاسخ :
هرجا اگر پنالتی رو بهتون دادند که کارتون راحت تره و گرنه باید برای حساب کردن پنالتی هر قسمت , زمان دسترسی اون قسمت رو تقسیم بر clock cycle time کنید.
ما در اینجا clock rate روداریم که ۵۰۰ MGH است که برای به دست آوردن clock cycle time باید آن را معکوس کنیم یعنی :
Clock cycle time = 1 / clock rate = 1 / 500 MGH = 1 / 500 * 106 =
= 1 / 0.5 * 109 = (۰.۵ = ½) = ۲/۱۰۹ = ۲ * ۱۰-۹ = ۲ ns
در فرمول ۰.۵ رو برابر ½ گرفتیم و سپس ۲ از مخرجه کسر پایینی رفت به صورت کسر بالایی.
Miss penalty = 200 (ns) / 2 (ns/clock cycles) = ۱۰۰ clock cycles
CPI بدون کش L2 = CPIbase + miss stall cycles per instruction
CPI = 1 + 0.05 * 100 = 6
که در اینجا CPIbase که میشه گفت همان زمان دسترسی به کش L1 است را بعلاوه با درصد miss در پنالتی دسترسی به حافظه کردیم.
حالا اگر کش L2 اضافه شود اگر زمانی در کش L1 , miss اتفاق افتاد به سراغ L2 میریم و اگر اونجا هم نبود میریم سراغ ram .
یعنی وقتی میخواین درصد miss رو برای رسیدن به ram حساب کنیم باید درصد miss در L1 رو در درصد miss در L2 ضرب کنیم چون باید در هر دوتا کش نباشه تا به ram برسیم اما در این سوال خودش گفته با وجود L2 نرخ نقصان به حافظه اصلی برابر ۲% است یعنی ضرب شده ی نرخ نقصان L1 در نرخ نقصان L2 شده ۲% پس دیگه نیاز نیست ضرب کنی چون نرخ نقصان حافظه رو مستقیم بهمون داده .
پنالتی کش L2 هم برابر میشه با : ۲۰ / ۲ = ۱۰
CPI با کش L2 برابر میشه با :
CPI = 1 + 0.05*10 + 0.02*100 = 3.5
در اینجا CPIbase را بعلاوه درصد نقصان کش اول در جریمه برای دسترسی به کش L2 کردیم بعلاوه نرخ نقصان به ram در جریمه دسترسی به ram .
هرجا هستیم باید درصد خطای خودمون رو در پنالتی دسترسی به کش بعدی ضرب کنیم .
بنابراین سرعت ۶ / ۳.۵ = ۱.۷ برابر شده است.
مثال بعدی :
فرض کنید نرخ نقصان دستورات ۲ درصد و نرخ نقصان دیتا ۴ درصد و CPI بدون miss برابر ۲ و جریمه miss برابر ۴۰ سایکل باشد . اگر ۳۶ درصد کل دستورات حافظه ای باشند ( load , store باشند ) سرعت ماشین چند برابر می شود اگر اصلا miss وجود نداشته باشد ؟
پاسخ :
خب اینجا دیگه پنالتی رو مستقیم بهمون داده و زمان رو نداده که ما بخوایم تقسیمی انجام بدیم.
اگر I را تعداد کل دستورات فرض کنیم داریم :
Instruction miss cycles = I * 0.02 * 40 = 0.8 I
Data miss cycles = I * 0.36 * 0.04 * 40 = 0.56 I
که اولی میگه ۲ درصد از دستورات miss میشن که هرکدوم ۴۰ سایکل جریمه داره.
دومی میگه ۳۶ درصد از دستورات حافظه ای هستند که از بین این ها ۴ درصدشون miss میشن که ۴۰ سایکل جریمه میشن هرکدومش.
نکته : چرا دستورات معمولی و حافظه ای یعنی load , store رو جدا کردند ؟
چون load , store علاوه کاری که تمام دستورات انجام میدن یه مرحله دیگه هم دارن که در هر صورت باید به حافظه دیتا رجوع کنند که مثلا در store در هر صورت شما باید برید در حافظه دیتا و چیزی بنویسید و در load هم باید برید از حافظه دیتا چیزی بخونید پس این دو دستور علاوه بر اینکه با همه مقایسه میشن یه CPI جدا برای خودشون دارن که باید محاسبه بشه و با قبلی جمع بشه.( در اینجا حافظه دستور و دیتا جداست یعنی یک حافظه برای دستورات داریم و یک حافظه دیگر برای دیتا (mips) (
0.8 I + 0.56 I = 1.36 I = total number of memory stall cycles
بنابر این CPI با توجه به stall ها برابر ۲ + ۱.۳۶ = ۳.۳۶
Speed up = CPIstall / CPIperfect = 3.36 / 2 = 1.68
خب اینم از حل این مثال ولی پیشنهاد میکنم مثال های بیشتری در این مورد حل کنید.
یک نکته دیگه هم بگم و تمام J
فرض کنید یک ماتریس ۳۲ * ۳۲ دارید و یک کش ۱۶ بلاک ۸ بایتی و روش کار direct mapping است .
حالا سوال اینجاست اگر این ماتریس رو سطری بخونیم بهتره یا ستونی ؟
خب اگر سطری بخونین اینطوری میشه که وقتی خونه اول از سطر اول رو میخونین(یعنی خونه شماره ۰ ) ۸ تا خونه ی اول از سطر اول رو میاره میذاره در کش چون کش ما هر سطرش ۸ بایت جا داره پس ۸ تا میتونه بیاره پس الان خونه ۰ تا ۷ در سطر اول قرار داره.
شکل زیر سطر اول کش را نشان می دهد
۷ | ۶ | ۵ | ۴ | ۳ | ۲ | ۱ | ۰ |
خونه بعدی که میخواین بخونین از ماتریس خونه شماره ۱ است و می بینین که در کش هست و hit میشه.
به همین ترتیب تا ۷ همه hit میشن و وقتی ۸ میاد miss میشه اما در ادامش چون وقتی ۸ میاد از ۸ تا ۱۵ وارد کش میشن پس از ۹ تا ۱۵ hit میشن.
اگر دقت کنین تا آخر اگر ادامه بدیم از هر ۸ تا ۷ تاش hit میشه پس :
Hit rate = 7 / 8
حالا فرض کنین ستونی میخوایم بخونیم :
۰ رو میخونیم و از ۰ تا ۷ میان تو سطر شماره ۰ از کش.
بعد خونه ۳۲ رو میخونیم ( خونه اول از سطر بعدی ) که چون نیست miss میشه و خودش و ۷ تای بعدی رو میاره تو کش.
منظور از خونه ی ۳۲ یعنی سطر ۴ از ram چرا ؟
چون ما تعداد ستون هامون ۸ تاست پس ۳۲ / ۸ = ۴ پس یعنی سطر چهار که اگر باقیمانده به ۱۶ یعنی تعداد سطر های کش بگیریم باید بره در سطر ۴ از کش قرار بگیره این سطر یعنی خونه های ۳۲ تا ۳۹ در سطر ۴ کش هستند.
خونه بعدی که قراره خونده بشه ۶۴ است که یعنی سطر ۱۶ که باید بره در سطر ۰ از کش بشینه.
چی شد؟یعنی رفت اون سطر صفری که اول گذاشتیم رو پاک کرد؟
آره دیگه پاک کرد …
به همین ترتیب اگه ادامه بدیم همه خونه های ستون اول miss میشن و وقتی میریم ستون دوم رو بخونیم دیگه اونا در کش نیستن و قبلا پاک شدن !!!
پس یعنی کل خونه های ماتریس miss میشه و ما هیچ hit ای نداریم چون یک سطر ذخیره میشه در کش و تا ما بخوایم یک ستون رو بخونیم و بریم سراغ خونه بعدی از اون سطر دیگه اون سطر پاک شده و نیست و باید بریم دوباره بیاریمش.
در این مثال اگر روش direct mapping هم نبود (در این مثال خاص) باز هم همین اتفاق میفتاد چون ما ۱۶ سطر در کش داریم و در ماتریس ۳۲ سطر داریم.
بعد از اینکه در ستون اول ۱۶ تای اول رو خوندیم و در کش گذاشتیم بعدش ۱۶ تای دوم میان اونارو پاک میکنن و خودشون جاشون می شینن و باز هم همه ی خونه ها miss میشن.
این بود مطالبی که میخواستم از قسمت حافظه براتون توضیح بگم.
امیدوارم براتون مفید بوده باشه.
بازم تکرار میکنم که این فصل مطالب زیادی داره که من مهم ترین اون هارو گفتم که پیشنهاد میکنم بهتون یه سری به کتاب هم بزنین .
به دلیل زیاد بودن مطالب در این مقالات و بالا بودن تعداد صفحات شاید اشتباهات انشایی یا املایی از بنده سر زده باشه که از همین جا عذرخواهی میکنم.
اگر سوالی بود با بنده در سایت zerotohero.ir در میون بذارید.
پایان
مطالب زیر را حتما مطالعه کنید
حسگرها و فناوریهای پوشیدنی و کاربردهای آنها در پزشکی
آشنایی با نمودار رابطهای (ER)
درخت دودویی
ساختمان داده درخت
مدار منطقی – گیت های منطقی
مدار منطقی-جبر بول
4 Comments
Join the discussion and tell us your opinion.
دیدگاهتان را بنویسید لغو پاسخ
برای نوشتن دیدگاه باید وارد بشوید.
سلام
فقط خواستم تشکر ویژه ای ازت بکنم که اینقدر قشنگ توضیح دادی. چندتا جزوه رو دیدم انقدر گنگ بود که حالم بهم خورد. شما اولین نفری هستید که از توضیحاتش تو بخش حافظه لذت بردم.
موفق و پیروز باشید.
سلام میشه در مورد محاسبه تگ و ایندکس زمانی که هم حافظه مجازی یا virtual داریم و هم حافظه فیزیکی داریم توضیح بدید چطوری به دست میاد؟
تو این سوال : “پردازنده ای دارای ۴ گیگا بایت حافظه ram و دارای کش به اندازه ۵۱۲ کیلو بایت است . اگر سایز هر بلاک ۱۶ بایت باشد , حجم مورد نیاز جهت ذخیره سازی tag را در روش های direct mapping , fully associative , 2-way set associative مشخص کنید ؟”
گفته سایز هر بلاک ۱۶ بایت است . پس اول باید بایت و به بیت تبدیل کنیم یعنی ضرب در ۲ به توان ۳ کنیم که میشه ۲ به توان ۷ … پس ۷ بیت اول مال ستونه
درسته ؟
سلام دوست عزیز
اگر دقت کنید تمام اطلاعات بر اساس بایت داده شده , حجم ram و کش , اینجا نیازی به تبدیل بایت به بیت نیست , شما باید ۴ بیت از ۳۲ بیت آدرسی که دارید رو به ستون اختصاص بدین و بقیه مراحل هم در مقاله گفته شده
موفق باشین