حافظه نهان

حافظه نهان

اسلاید 1: حافظه ی نهاندانشگاه ایلام

اسلاید 2: انواع حافظهTypeSizeSpeedCost/bitRegister< 1KB< 1ns$$$$On-chip SRAM8KB-6MB< 10ns$$$Off-chip SRAM1Mb – 16Mb< 20ns$$DRAM64MB – 1TB< 100ns$Disk40GB – 1PB< 20ms~0

اسلاید 3: سلسله مراتب حافظهRegistersOn-ChipSRAMOff-ChipSRAMDRAMDiskCAPACITYSPEED and COST

اسلاید 4: چرا سلسله مراتب حافظه کار می کند؟محلی بودن ارجاعات زمانییک مکان از حافظه په صورت پشت سر هم مورد ارجاع قرار می گیرد. مکانیمکانهای متوالی حافظه به صورت پشت سر هم مورد ارجاع قرار می گیرند. موضوع فوق از لحاظ تجربی ثابت شده است. نتیجه ی مهم و با ارزشی است. حتی یک حافظه ی نهان کوچک (8KB) نیز می تواند 90% ارجاعات یک برنامه چند مگابایتی را پوشش دهد. Lots ofdynamic RAMA little staticRAM (cache)CPU

اسلاید 5: 5در قطعه کدهای روبرو شی employee و آرایه ی a از ارجاع به محلهای متوالی حافظه (spatial locality) می برند. متغییر sum از ارجاعات همزمان به یک مکان مشابه از حافظه (temporal locality) بهره می برد. مثال employee.name = “Homer Simpson”;employee.boss = “Mr. Burns”;employee.age = 45;sum = 0;for (i = 0; i < MAX; i++)sum = sum + a[i];

اسلاید 6: چهار سوال مهم؟مکان یابییک بلوک حافظه از حافظه ی اصلی را در کجای حافظه ی نهان ذخیره کنیم؟تشخیصاز کجا بدانیم که مطلب مورد نظر در حافظه ی نهان قرار دارد؟جابجاییدر صورت پر بودن حافظه ی نهان کدام بلوک را جابجا کنیم؟سیاست نوشتنتغییرات حافظه ی نهان را کی به حافظه ی اصلی منتقل کنیم؟

اسلاید 7: مکان یابیMemory TypePlacementCommentsRegistersAnywhere; Int, FP, SPRCompiler/programmer managesCache (SRAM)Fixed in H/WDirect-mapped,set-associative, fully-associativeDRAMAnywhereO/S managesDiskAnywhereO/S managesHUH?

اسلاید 8: طراحی حافظه ی نهان

اسلاید 9: نگاشت مستقیم

اسلاید 10:

اسلاید 11: نگاشت مستقیمفرض کنید که حافظه ی نهان دارای 64 بلوک است و اندازه ی هر بلوک حافظه ی نهان برابر 16 بیت است و عرض حافظه ی اصلی 8 بیت است. آدرس 1200 در کجا قرار می گیرد؟1200d=10010110000B  24به این سوال جواب دهید

اسلاید 12: انجمنی کاملبلوک داده می تواند در هر جایی باشد. یعنی باید تمام برچسب ها را همزمان با هم مقایسه کنیم. خیلی گران است. SRAM CacheHashAddressData OutOffset32-bit AddressOffsetTagHitTag Check?=Tag

اسلاید 13: انجمنی چهار مسیره

اسلاید 14: مکان یابی و تشخیصفرض کنید که در نمایش <BS, S, B>:BS اندازه ی بلوک، S تعداد اعضای هر مجموعه و B نیز تعداد بلوکهای حافظه ی نهان است. لذا، تعداد مجموعه ها برابر است با B/S. <32,64,64>: o=5, i=6, t=21: direct-mapped (S=B)<32,16,64>: o=5, i=4, t=23: 4-way S-A (S = B / 4)<32,1,64>: o=5, i=0, t=27: fully associative (S=1)Total size = BS x B = BS x S x (B/S)Offset32-bit AddressTagIndexطولمنظوربخشo=log2(اندازه ی بلوک)انتخاب کلمه ی مورد نظر در داخل بلوکOffseti=log2(تعداد اعضای یک مجموعه ها)انتخاب یک مجموعه از بلوکهاIndext=32 - o - iIdبلوک مورد نظر در داخل مجموعهTag

اسلاید 15: جابجاییاندازه حافظه ی نهان محدود استاگر حافظه ی نهان پر شد چکار کنیم؟FIFO (first-in-first-out)LRU (least recently used)NMRU (not most recently used)Pseudo-random (yes, really!)در نگاشت مستقیم کاندید جابجایی مشخص است. در نگاشت انجمنی اگر حافظه ی نهان دو مسیره باشد، LRU را به آسانی می توان پیاده کرد. اگر تعداد مجموعه ها از 2 بیشتر باشد، روش انتخاب شبه تصادفی مناسب است!

اسلاید 16: سیاست نوشتنسلسله مراتب حافظهدو یا بیشتر کپی از یک بلوک یکسانحافظه ی اصلی و حافظه ی جانبیهنگام نوشتن چکار کنیم؟در نهایت، تمام کپیها باید یکسان شوند. یعنی، نوشتن باید در تمام سطوح منتشر شود.

اسلاید 17: سیاست نوشتن: write-throughخیلی راحت استعمل نوشتن در سلسه مراتب حافظه منتشر می شود. Write in L1, L2, memory, disk (?!?)ایراداتپهنای باند مورد نیاز زیاد است. حافظه های سطوح پایینتر کندتر هستند. در عمل، L1 و L2 از این سیاست استفاده می کنند.

اسلاید 18: سیاست نوشتن: write-backپر کاربرد استباید از وضعیت هر خط از حافظه ی نهان نگهداری کنیم.Invalid: یعنی بلوک مورد نظر در حافظه ی نهان نیست. Clean : یعنی بلوک مورد نظر موجود است اما تغییر نکرده است. Dirty : یعنی بلوک مورد نظر موجود است اما تغییر کرده است. وضعیت در کنار برچسب ذخیره می شود. هنگام نوشتن بیت dirty را تنظیم کنید.هنگام خروج از حافظه، اگر بیت dirty تنظیم شده بود داده را در سطوح پایینتر ذخیره کنید.

اسلاید 19: سیاست نوشتنپیچیدگیهای write back: نسخه ی داده در سطوح پایینتر کهنه هستند.همیشه هنگام دسترسی به سطوح پایینتر، ابتدا باید سطوح بالاتر را چک کرد. در سیستمهای تک پردازنده ای خیلی اذیت نمی کند. در سیستمهای چند پردازنده ای باید همبستگی داده ها چک شود. دستگاههای I/O که مستقیما به حافظه دسترسی دارند نیز این مشکل را دارند.

اسلاید 20: مثال حافظه ی نهان Tag0Tag1LRU000032B Cache: <BS=4,S=4,B=8>o=2, i=2, t=2; انجمنی دو مسیرهدر ابتدا خالی است. فقط برچسبها را نشان داده ایم. دنباله ی اجرا:ReferenceBinarySet/WayHit/MissTag Array

اسلاید 21: Tag0Tag1LRU001010ReferenceBinarySet/WayHit/MissLoad 0x2A1010102/0MissTag Array32B Cache: <BS=4,S=4,B=8>o=2, i=2, t=2; انجمنی دو مسیرهدر ابتدا خالی است. فقط برچسبها را نشان داده ایم. دنباله ی اجرا:مثال حافظه ی نهان

اسلاید 22: Tag0Tag1LRU001010ReferenceBinarySet/WayHit/MissLoad 0x2A1010102/0MissLoad 0x2B1010112/0HitTag Array32B Cache: <BS=4,S=4,B=8>o=2, i=2, t=2; انجمنی دو مسیرهدر ابتدا خالی است. فقط برچسبها را نشان داده ایم. دنباله ی اجرا:مثال حافظه ی نهان

اسلاید 23: Tag0Tag1LRU00101111ReferenceBinarySet/WayHit/MissLoad 0x2A1010102/0MissLoad 0x2B1010112/0HitLoad 0x3C1111003/0MissTag Array32B Cache: <BS=4,S=4,B=8>o=2, i=2, t=2; انجمنی دو مسیرهدر ابتدا خالی است. فقط برچسبها را نشان داده ایم. دنباله ی اجرا:مثال حافظه ی نهان

اسلاید 24: Tag0Tag1LRU1010101111ReferenceBinarySet/WayHit/MissLoad 0x2A1010102/0MissLoad 0x2B1010112/0HitLoad 0x3C1111003/0MissLoad 0x201000000/0MissTag Array32B Cache: <BS=4,S=4,B=8>o=2, i=2, t=2; انجمنی دو مسیرهدر ابتدا خالی است. فقط برچسبها را نشان داده ایم. دنباله ی اجرا:مثال حافظه ی نهان

اسلاید 25: Tag0Tag1LRU101100101111ReferenceBinarySet/WayHit/MissLoad 0x2A1010102/0MissLoad 0x2B1010112/0HitLoad 0x3C1111003/0MissLoad 0x201000000/0MissLoad 0x331100110/1MissTag Array32B Cache: <BS=4,S=4,B=8>o=2, i=2, t=2; انجمنی دو مسیرهدر ابتدا خالی است. فقط برچسبها را نشان داده ایم. دنباله ی اجرا:مثال حافظه ی نهان

اسلاید 26: Tag0Tag1LRU011110101111ReferenceBinarySet/WayHit/MissLoad 0x2A1010102/0MissLoad 0x2B1010112/0HitLoad 0x3C1111003/0MissLoad 0x201000000/0MissLoad 0x331100110/1MissLoad 0x110100010/0 (lru)Miss/EvictTag Array32B Cache: <BS=4,S=4,B=8>o=2, i=2, t=2; انجمنی دو مسیرهدر ابتدا خالی است. فقط برچسبها را نشان داده ایم. دنباله ی اجرا:مثال حافظه ی نهان

اسلاید 27: Tag0Tag1LRU01111010 d1111ReferenceBinarySet/WayHit/MissLoad 0x2A1010102/0MissLoad 0x2B1010112/0HitLoad 0x3C1111003/0MissLoad 0x201000000/0MissLoad 0x331100110/1MissLoad 0x110100010/0 (lru)Miss/EvictStore 0x291010012/0Hit/DirtyTag Array32B Cache: <BS=4,S=4,B=8>o=2, i=2, t=2; انجمنی دو مسیرهدر ابتدا خالی است. فقط برچسبها را نشان داده ایم. دنباله ی اجرا:مثال حافظه ی نهان

اسلاید 28: زمان امتحان پنج شنبه 23آذر 1396 ساعت 8تقسیم 11 بر 4