TheMemoryHierarchy

TodayStoragetechnologiesandtrendsLocalityofreferenceCachinginthememoryhierarchyRandom-AccessMemory(RAM)Random-AccessMemory(RAM)KeyfeaturesRAMistraditionallypackagedasachip.Basicstorageunitisnormallyacell(onebitpercell).MultipleRAMchipsformamemory.StaticRAM(SRAM)Eachcellstoresabitwithasix-transistorcircuit.Retainsvalueindefinitely,aslongasitiskeptpowered.Relativelyinsensitivetoelectricalnoise(EMI),radiation,etc.FasterandmoreexpensivethanDRAM.DynamicRAM(DRAM)Eachcellstoresbitwithacapacitor.Onetransistorisusedforaccess.Valuemustberefreshedevery10-100ms.Moresensitivetodisturbances(EMI,radiation,…)thanSRAM.SlowerandcheaperthanSRAM.SRAMvsDRAMSummaryConventionalDRAMOrganizationdxwDRAM:dwtotalbitsorganizedasdsupercellsofsizewbitscolsrows01230123Internalrowbuffer16x8DRAMchipaddrdatasupercell(2,1)2bits/8bits/Memorycontroller(to/fromCPU)ReadingDRAMSupercell(2,1)Step1(a):Rowaccessstrobe(RAS)selectsrow2.Step1(b):Row2copiedfromDRAMarraytorowbuffer.ColsRowsRAS=20123012Internalrowbuffer16x8DRAMchip3addrdata2/8/MemorycontrollerReadingDRAMSupercell(2,1)Step2(a):Columnaccessstrobe(CAS)selectscolumn1.Step2(b):Supercell(2,1)copiedfrombuffertodatalines,andeventuallybacktotheCPU.ColsRows01230123Internalrowbuffer16x8DRAMchipCAS=1addrdata2/8/Memorycontrollersupercell(2,1)supercell(2,1)ToCPUMemoryModules:supercell(i,j)64MBmemorymoduleconsistingofeight8Mx8DRAMsaddr(row=i,col=j)MemorycontrollerDRAM7DRAM00317815162324326339404748555664-bitdoublewordatmainmemoryaddressAbits0-7bits8-15bits16-23bits24-31bits32-39bits40-47bits48-55bits56-6364-bitdoubleword03178151623243263394047485556EnhancedDRAMsBasicDRAMcellhasnotchangedsinceitsinventionin1966.CommercializedbyIntelin1970.DRAMcoreswithbetterinterfacelogicandfasterI/O:SynchronousDRAM(SDRAM)UsesaconventionalclocksignalinsteadofasynchronouscontrolAllowsreuseoftherowaddresses(e.g.,RAS,CAS,CAS,CAS)Doubledata-ratesynchronousDRAM(DDRSDRAM)DoubleedgeclockingsendstwobitspercycleperpinDifferenttypesdistinguishedbysizeofsmallprefetchbuffer:DDR(2bits),DDR2(4bits),DDR3(8bits)By2010,standardformostserveranddesktopsystemsIntelCorei7supportsonlyDDR3SDRAMDDRDDR2vsDDR3NonvolatileMemoriesDRAMandSRAMarevolatilememoriesLoseinformationifpoweredoff.NonvolatilememoriesretainvalueevenifpoweredoffRead-onlymemory(ROM):programmedduringproductionProgrammableROM(PROM):canbeprogrammedonceEraseablePROM(EPROM):canbebulkerased(UV,X-Ray)ElectricallyeraseablePROM(EEPROM):electronicerasecapabilityFlashmemory:EEPROMswithpartial(sector)erasecapabilityWearsoutafterabout100,000erasings.UsesforNonvolatileMemoriesFirmwareprogramsstoredinaROM(BIOS,controllersfordisks,networkcards,graphicsaccelerators,securitysubsystems,…)Solidstatedisks(replacerotatingdisksinthumbdrives,smartphones,mp3players,tablets,laptops,…)DiskcachesTraditionalBusStructureConnecting

CPUandMemoryAbusisacollectionofparallelwiresthatcarryaddress,data,andcontrolsignals.Busesaretypicallysharedbymultipledevices.MainmemoryI/ObridgeBusinterfaceALURegisterfileCPUchipSystembusMemorybusMemoryReadTransaction(1)CPUplacesaddressAonthememorybus.

ALURegisterfileBusinterfaceA0AxMainmemoryI/Obridge%eaxLoadoperation:

movlA,%eaxMemoryReadTransaction(2)MainmemoryreadsAfromthememorybus,retrieveswordx,andplacesitonthebus.ALURegisterfileBusinterfacex0AxMainmemory%eaxI/ObridgeLoadoperation:

movlA,%eaxMemoryReadTransaction(3)CPUreadwordxfromthebusandcopiesitintoregister%eax.xALURegisterfileBusinterfacexMainmemory0A%eaxI/ObridgeLoadoperation:

movlA,%eaxMemoryWriteTransaction(1)CPUplacesaddressAonbus.Mainmemoryreadsitandwaitsforthecorrespondingdatawordtoarrive.yALURegisterfileBusinterfaceAMainmemory0A%eaxI/ObridgeStoreoperation:

movl%eax,AMemoryWriteTransaction(2)CPUplacesdatawordyonthebus.yALURegisterfileBusinterfaceyMainmemory0A%eaxI/ObridgeStoreoperation:

movl%eax,AMemoryWriteTransaction(3)MainmemoryreadsdatawordyfromthebusandstoresitataddressA.yALUregisterfilebusinterfaceymainmemory0A%eaxI/ObridgeStoreoperation:

movl%eax,AWhat’sInsideADiskDrive?SpindleArmActuatorPlattersElectronics(includingaprocessorandmemory!)SCSIconnectorImagecourtesyofSeagateTechnologyDiskGeometry(Muliple-PlatterView)Alignedtracksformacylinder.Surface0Surface1Surface2Surface3Surface4Surface5CylinderkSpindlePlatter0Platter1Platter2DiskGeometryDisksconsistofplatters,eachwithtwosurfaces.Eachsurfaceconsistsofconcentricringscalledtracks.Eachtrackconsistsofsectorsseparatedbygaps.SpindleSurfaceTracksTrackkSectorsGapsDiskOperation(Single-PlatterView)ThedisksurfacespinsatafixedrotationalrateBymovingradially,thearmcanpositiontheread/writeheadoveranytrack.Theread/writeheadisattachedtotheendofthearmandfliesoverthedisksurfaceonathincushionofair.spindlespindlespindlespindlespindleDiskOperation(Multi-PlatterView)ArmRead/writeheadsmoveinunisonfromcylindertocylinderSpindleTracksdividedintosectorsDiskStructure-topviewofsingleplatterSurfaceorganizedintotracksDiskAccessHeadinpositionaboveatrackDiskAccessRotationiscounter-clockwiseDiskAccess–ReadAbouttoreadbluesectorDiskAccess–ReadAfterBLUE

readAfterreadingbluesectorDiskAccess–ReadAfterBLUE

readRedrequestschedulednextDiskAccess–SeekAfterBLUE

readSeekforREDSeektored’strackDiskAccess–RotationalLatencyAfterBLUE

readSeekforREDRotationallatencyWaitforredsectortorotatearoundDiskAccess–ReadAfterBLUE

readSeekforREDRotationallatencyAfterREDreadCompletereadofredDiskAccess–ServiceTimeComponentsAfterBLUE

readSeekforREDRotationallatencyAfterREDreadDatatransferSeekRotationallatencyDatatransferI/OBusMainmemoryI/ObridgeBusinterfaceALURegisterfileCPUchipSystembusMemorybusDiskcontrollerGraphicsadapterUSBcontrollerMouseKeyboardMonitorDiskI/ObusExpansionslotsforotherdevicessuchasnetworkadapters.ReadingaDiskSector(1)MainmemoryALURegisterfileCPUchipDiskcontrollerGraphicsadapterUSBcontrollermousekeyboardMonitorDiskI/ObusBusinterfaceCPUinitiatesadiskreadbywritingacommand,logicalblocknumber,anddestinationmemoryaddresstoaport(address)associatedwithdiskcontroller.ReadingaDiskSector(2)MainmemoryALURegisterfileCPUchipDiskcontrollerGraphicsadapterUSBcontrollerMouseKeyboardMonitorDiskI/ObusBusinterfaceDiskcontrollerreadsthesectorandperformsadirectmemoryaccess(DMA)transferintomainmemory.ReadingaDiskSector(3)MainmemoryALURegisterfileCPUchipDiskcontrollerGraphicsadapterUSBcontrollerMouseKeyboardMonitorDiskI/ObusBusinterfaceWhentheDMAtransfercompletes,thediskcontrollernotifiestheCPUwithaninterrupt(i.e.,assertsaspecial“interrupt”pinontheCPU)SolidStateDisks(SSDs)Pages:512B~4KB,Blocks:32~128pages/16~512KBDataread/writteninunitsofpages.PagecanbewrittenonlyafteritsblockhasbeenerasedAblockwearsoutafter100,000repeatedwrites.FlashtranslationlayerI/ObusPage0Page1PageP-1…Block0…Page0Page1PageP-1…BlockB-1FlashmemorySolidStateDisk(SSD)RequeststoreadandwritelogicaldiskblocksSSDTradeoffs vsRotatingDisksAdvantagesNomovingpartsfaster,lesspower,moreruggedDisadvantagesHavethepotentialtowearoutMitigatedby“wearlevelinglogic”inflashtranslationlayerE.g.IntelX25guarantees1petabyte(1015bytes)ofrandomwritesbeforetheywearoutIn2010,about100timesmoreexpensiveperbyteIn2013,about20times;In2016,about7timesApplicationsMP3players,smartphones,laptopsDesktopsandserversMetric 1980 1985 1990 1995 2000 2005 2010 2010:1980$/MB 8,000 880 100 30 1 0.1 0.06 130,000access(ns) 375 200 100 70 60 50 40 9typicalsize(MB) 0.064 0.256 4 16 64 2,000 8,000 125,000

StorageTrendsDRAMSRAMMetric 1980 1985 1990 1995 2000 2005 2010 2010:1980$/MB 500 100 8 0.30 0.01 0.005 0.0003 1,600,000access(ms) 87 75 28 10 8 4 3 29typicalsize(MB) 1 10 160 1,000 20,000 160,000 1,500,000 1,500,000DiskMetric 1980 1985 1990 1995 2000 2005 2010 2010:1980$/MB 19,200 2,900 320 256 100 75 60 320access(ns) 300 150 35 15 3 2 1.5 200CPUClockRates

1980 1990 1995 2000 2003 2005 2010 2010:1980CPU 8080 386 Pentium P-III P-4 Core2 Corei7 Clockrate(MHz)1 20 150 600 3300 2000 2500 2500Cycletime(ns) 1000 50 6 1.6 0.3 0.50 0.4 2500Cores 1 1 1 1 1 2 4 4Effectivecycle 1000 50 6 1.6 0.3 0.25 0.1 10,000time(ns)Inflectionpointincomputerhistorywhendesignershitthe“PowerWall”TheCPU-MemoryGapThegapwidensbetweenDRAM,disk,andCPUspeeds.DiskDRAMCPUSSDSRAMLocality ThekeytobridgingthisCPU-MemorygapisafundamentalpropertyofcomputerprogramsknownaslocalityTodayStoragetechnologiesandtrendsLocalityofreferenceCachinginthememoryhierarchyLocalityPrincipleofLocality:

ProgramstendtousedataandinstructionswithaddressesnearorequaltothosetheyhaveusedrecentlyTemporallocality:Recentlyreferenceditemsarelikely

tobereferencedagaininthenearfutureSpatiallocality:Itemswithnearbyaddressestend

tobereferencedclosetogetherintimeLocalityExampleDatareferencesReferencearrayelementsinsuccession(stride-1referencepattern).Referencevariablesumeachiteration.InstructionreferencesReferenceinstructionsinsequence.Cyclethroughlooprepeatedly.sum=0;for(i=0;i<n;i++) sum+=a[i];returnsum;SpatiallocalityTemporallocalitySpatiallocalityTemporallocalityQualitativeEstimatesofLocalityClaim:Beingabletolookatcodeandgetaqualitativesenseofitslocalityisakeyskillforaprofessionalprogrammer.Question:Doesthisfunctionhavegoodlocalitywithrespecttoarraya?intsum_array_rows(inta[M][N]){inti,j,sum=0;for(i=0;i<M;i++)for(j=0;j<N;j++)sum+=a[i][j];returnsum;}Yes:

stride-1referencepatternM=2,N=3LocalityExampleQuestion:Doesthisfunctionhavegoodlocalitywithrespecttoarraya?intsum_array_cols(inta[M][N]){inti,j,sum=0;for(j=0;j<N;j++)for(i=0;i<M;i++)sum+=a[i][j];returnsum;}No:

stride-3referencepatternM=2,N=3LocalityExampleQuestion:Canyoupermutetheloopssothatthefunctionscansthe3-darraya

withastride-1referencepattern(andthushasgoodspatiallocality)?intsum_array_3d(inta[M][N][N]){inti,j,k,sum=0;for(i=0;i<M;i++)for(j=0;j<N;j++)for(k=0;k<N;k++)sum+=a[k][i][j];returnsum;}MemoryHierarchiesSomefundamentalandenduringpropertiesofhardwareandsoftware:Faststoragetechnologiescostmoreperbyte,havelesscapacity,andrequiremorepower(heat!).ThegapbetweenCPUandmainmemoryspeediswidening.Well-writtenprogramstendtoexhibitgoodlocality.Theysuggestanapproachfororganizingmemoryandstoragesystemsknownasamemoryhierarchy.TodayStoragetechnologiesandtrendsLocalityofreferenceCachinginthememoryhierarchyAnExampleMemoryHierarchyLatency:011030100100000001000000000CacheCache:

Asmaller,fasterstoragedevicethatactsasastagingareaforasubsetofthedatainalarger,slowerdevice.Fundamentalideaofamemoryhierarchy:Foreachk,thefaster,smallerdeviceatlevelkservesasacacheforthelarger,slowerdeviceatlevelk+1.Whydomemoryhierarchieswork?Becauseoflocality,programstendtoaccessthedataatlevelkmoreoftenthantheyaccessthedataatlevelk+1.Thus,thestorageatlevelk+1canbeslower,andthuslargerandcheaperperbit.GeneralCacheConcepts012345678910111213141589143CacheMemoryLarger,slower,cheapermemoryviewedaspartitionedinto“blocks”Dataiscopiedinblock-sizedtransferunitsSmaller,faster,moreexpensivememorycachesasubsetoftheblocks444101010GeneralCacheConcepts:Hit012345678910111213141549143CacheMemoryDatainblockbisneededRequest:1414Blockbisincache:Hit!GeneralCacheConcepts:Miss01234567891011121314159143CacheMemoryDatainblockbisneededRequest:12Blockbisnotincache:Miss!BlockbisfetchedfrommemoryRequest:1212124GeneralCacheConcepts:Miss01234567891011121314159143CacheMemoryDatainblockbisneededRequest:12Blockbisnotincache:Miss!BlockbisfetchedfrommemoryRequest:121212BlockbisstoredincacheReplacingorevicting:

Processofoverwriting

anexistingblockReplacementpolicy:

Determines