第4章 存儲層次結(jié)構(gòu)設(shè)計 課件

計算機體系結(jié)構(gòu)周學(xué)海xhzhou國科學(xué)技術(shù)大學(xué)基本流水線小結(jié)流水線提高的是指令帶寬（吞吐率），而不是單條指令的執(zhí)行速度相關(guān)限制了流水線性能的發(fā)揮結(jié)構(gòu)相關(guān)：需要更多的硬件資源數(shù)據(jù)相關(guān)：需要定向，編譯器調(diào)度控制相關(guān)：盡早檢測條件，計算目標(biāo)地址，延遲轉(zhuǎn)移，預(yù)測編譯器可降低數(shù)據(jù)相關(guān)和控制相關(guān)的開銷Load延遲槽\Branch延遲槽\Branch預(yù)測增加流水線的級數(shù)會增加相關(guān)產(chǎn)生的可能性異常，浮點運算使得流水線控制更加復(fù)雜長流水線（浮點數(shù)流水線）引起的“相關(guān)”問題長流水線中精確中斷的處理方法浮點數(shù)流水線的性能:RAW相關(guān)引起的性能損失是主要因素浮點數(shù)流水線示例(MIPSR4000)中國科學(xué)技術(shù)大學(xué)chapter3.2第4章存儲層次結(jié)構(gòu)設(shè)計4.1存儲層次結(jié)構(gòu)4.2Cache基本知識4.3基本的Cache優(yōu)化方法4.4高級的Cache優(yōu)化方法4.5存儲器技術(shù)與優(yōu)化4.6虛擬存儲器－基本原理2025/3/6計算機體系結(jié)構(gòu)34.1存儲層次結(jié)構(gòu)存儲系統(tǒng)設(shè)計是計算機體系結(jié)構(gòu)設(shè)計的關(guān)鍵問題之一價格，容量，速度的權(quán)衡用戶對存儲器的“容量，價格和速度”要求是相互矛盾的速度越快，每位價格就高容量越大，每位價格就低容量越大，速度就越慢目前主存一般由DRAM構(gòu)成Microprocessor與Memory之間的性能差異越來越大CPU性能提高大約60%/yearDRAM性能提高大約9％/year2025/3/6計算機體系結(jié)構(gòu)4技術(shù)發(fā)展趨勢

Capacity Speed(latency)Logic: 2xin3years 2xin3yearsDRAM: 4xin3years 2xin10yearsDisk: 4xin3years 2xin10years2025/3/6計算機體系結(jié)構(gòu)5YearDRAMSize CycleTime1980 64Kb 250ns1983 256Kb 220ns1986 1Mb 190ns1989 4Mb 165ns1992 16Mb 145ns1995 64Mb 120ns1000:1!2:1!20098192(8Gbi)TrendsinDRAM2025/3/6計算機體系結(jié)構(gòu)6Processor-DRAMMemoryGap(latency)微處理器與DRAM的性能差異2025/3/6計算機體系結(jié)構(gòu)7Processor-MemoryPerformanceGapGrowingMicroprocessor-DRAM性能差異

利用caches緩解微處理器與存儲器性能上的差異Microprocessor-DRAM性能差異timeofafullcachemissininstructionsexecuted1stAlpha:340ns/5.0ns=

68clksx2or136instructions2ndAlpha:266ns/3.3ns=

80clksx4or320instructions3rdAlpha:180ns/1.7ns=108clksx6or648instructions2025/3/6計算機體系結(jié)構(gòu)8Processor$MEMMemoryreferencestream<op,addr>,<op,addr>,<op,addr>,<op,addr>,...op:i-fetch,read,write通過優(yōu)化存儲系統(tǒng)的組織來使得針對典型應(yīng)用平均訪存時間最短WorkloadorBenchmarkprograms存儲系統(tǒng)的設(shè)計目標(biāo)2025/3/6計算機體系結(jié)構(gòu)9基本解決方法：多級層次結(jié)構(gòu)多級分層結(jié)構(gòu)M1速度最快，容量最小，每位價格最高Mn速度最慢，容量最大，每位價格最低并行存儲系統(tǒng)接近M1的速度，容量和價格接近Mn2025/3/6計算機體系結(jié)構(gòu)10CPUM1M2Mn………..計算機系統(tǒng)的多級存儲層次2025/3/6計算機體系結(jié)構(gòu)11CPURegisterMEMORYI/OdeviceL1CACHEL2CACHEL3CACHE300ps1ns3-10ns10-20ns50-100ns5-10ms1000B64KB256K2-4MB4-16GB4-16TBCPURegisterMEMORYI/OdeviceL1CACHEL2CACHE500ps2ns10-20ns50-100ns25-50μs500B64KB256K256-512MB4-8GBServerPMD存儲層次工作原理：Locality!TemporalLocality(時間局部性):=>保持最近訪問的數(shù)據(jù)項最接近微處理器SpatialLocality(空間局部性):以由地址連續(xù)的若干個字構(gòu)成的塊為單位，從低層復(fù)制到上一層2025/3/6計算機體系結(jié)構(gòu)12LowerLevelMemoryUpperLevelMemoryToProcessorFromProcessorBlkXBlkY應(yīng)用程序局部性原理:給用戶一個采用低成本技術(shù)達到的存儲容量.（容量大，價格低）一個采用高速存儲技術(shù)達到的訪問速度.（速度快）典型的存儲器訪問模式2025/3/6計算機體系結(jié)構(gòu)13存儲層次結(jié)構(gòu)涉及的基本概念BlockBlock:不同層次的Block大小可能不同命中和命中率失效和失效率鏡像和一致性問題高層存儲器是較低層存儲器的一個鏡像高層存儲器內(nèi)容的修改必須反映到低層存儲器中數(shù)據(jù)一致性問題尋址：不管如何組織，我們必須知道如何訪問數(shù)據(jù)要求：不同層次上塊大小可以不同在L0cache可能以Double,Words,Halfwords,或bytes在L1cache僅以cacheline或slot為單位訪問在更低層…..因此總是存在地址映射問題物理地址格式BlockFrameAddress+BlockOffset2025/3/6計算機體系結(jié)構(gòu)14存儲層次的性能參數(shù)(1/2)假設(shè)采用二級存儲：M1和M2M1和M2的容量、價格、訪問時間分別為：S1、C1、TA1S2、C2、TA22025/3/6計算機體系結(jié)構(gòu)15LowerLevelMemoryUpperLevelMemoryToProcessorFromProcessorBlkXBlkY存儲層次的性能參數(shù)(2/2)存儲層次的平均每位價格CC=(C1*S1+C2*S2)/(S1+S2)命中(Hit):訪問的塊在存儲系統(tǒng)的較高層次上若一組程序?qū)Υ鎯ζ鞯脑L問，其中N1次在M1中找到所需數(shù)據(jù)，N2次在M2中找到數(shù)據(jù)則HitRate（命中率）:存儲器訪問在較高層命中的比例H=N1/(N1+N2)HitTime（命中時間）:訪問較高層的時間，TA1失效(Miss):訪問的塊不在存儲系統(tǒng)的較高層次上MissRate（失效）=1-(HitRate)=1–H＝N2/(N1+N2)當(dāng)在M1中沒有命中時：一般必須從M2中將所訪問的數(shù)據(jù)所在塊搬到M1中，然后CPU才能在M1中訪問。設(shè)傳送一個塊的時間為TB,即不命中時的訪問時間為：TA2+TB+TA1=TA1+TMTM通常稱為失效開銷平均訪存時間:平均訪存時間TA=HTA1+(1-H)(TA1+TM)=TA1+(1-H)TM2025/3/6計算機體系結(jié)構(gòu)16常見的存儲層次的組織Registers<->Memory由編譯器完成調(diào)度cache<->memory由硬件完成調(diào)度memory<->disks由硬件和操作系統(tǒng)（虛擬管理）由程序員完成調(diào)度2025/3/6計算機體系結(jié)構(gòu)17CacheMemory?小而快（SRAM）的存儲技術(shù)存儲正在訪問的部分指令和數(shù)據(jù)用于減少平均訪存時間通過保持最近訪問的數(shù)據(jù)在處理器附近來挖掘時間局部性通過以塊為單位在不同層次移動數(shù)據(jù)來挖掘空間局部性主要目標(biāo)：提高訪存速度降低存儲系統(tǒng)成本2025/3/6計算機體系結(jié)構(gòu)18Cache無處不在體系結(jié)構(gòu)中，Cache無處不在寄存器：Cache

onvariables一、二級Cache：CacheonmemoryMemory：Cacheonharddisks存儲最近執(zhí)行的程序和數(shù)據(jù)Harddisks可以視為主存的擴展（VM）分支目標(biāo)緩存及分支預(yù)測緩存緩存分支目標(biāo)及預(yù)測信息2025/3/6計算機體系結(jié)構(gòu)194.2Cache基本知識2025/3/6計算機體系結(jié)構(gòu)20Q1：映象規(guī)則當(dāng)要把一個塊從主存調(diào)入Cache時，如何放置問題三種方式全相聯(lián)方式：即所調(diào)入的塊可以放在cache中的任何位置直接映象方式：主存中每一塊只能存放在cache中的唯一位置一般，主存塊地址i與cache中塊地址j的關(guān)系為：

j＝imod（M)，M為cache中的塊數(shù)組相聯(lián)映象：主存中每一塊可以被放置在Cache中唯一的一個組中的任意一個位置，組由若干塊構(gòu)成，若一組由n塊構(gòu)成，我們稱N路組相聯(lián)組間直接映象組內(nèi)全相聯(lián)若cache中有G組，則主存中的第i塊的組號KK=imod(G),2025/3/6計算機體系結(jié)構(gòu)21Q1:Wherecanablockbeplacedintheupperlevel?Block12placedin8blockcache:Fullyassociative,directmapped,2-waysetassociativeS.A.Mapping=BlockNumberModuloNumberSets2025/3/6計算機體系結(jié)構(gòu)2201234567Blockno.Fullyassociative:block12cangoanywhere01234567Blockno.Directmapped:block12cangoonlyintoblock4(12mod8)01234567Blockno.Setassociative:block12cangoanywhereinset0(12mod4)Set0Set1Set2Set301234567890123456789012345678901Block-frameaddress1111111111222222222233Blockno.Q1的討論N-Way組相聯(lián)：如果每組由N個塊構(gòu)成，cache的塊數(shù)為M，則cache的組數(shù)G為M/N不同相聯(lián)度下的路數(shù)和組數(shù) 路數(shù)組數(shù) 全相聯(lián)M1

直接相聯(lián)1M

其他組相聯(lián)1<N<M1<G<M相聯(lián)度越高，cache空間利用率就越高，塊沖突概率就越小，失效率就越低N值越大，失效率就越低，但Cache的實現(xiàn)就越復(fù)雜，代價越大現(xiàn)代大多數(shù)計算機都采用直接映象，兩路或四路組相聯(lián)。2025/3/6計算機體系結(jié)構(gòu)23Q2(1/2):查找方法在CACHE中每一block都帶有tag域（標(biāo)記域），標(biāo)記分為兩類AddressTags：標(biāo)記所訪問的單元在哪一塊中，這樣物理地址就分為三部分：AddressTags##Blockindex##blockOffset

全相聯(lián)映象時，沒有BlockIndex

顯然Addresstag越短，查找所需代價就越小StatusTags：標(biāo)記該塊的狀態(tài)，如Valid,Dirty等2025/3/6計算機體系結(jié)構(gòu)24BlockoffsetBlockAddressTagIndexSetSelectDataSelectQ2（2/2)查找方法原則：所有可能的標(biāo)記并行查找，cache的速度至關(guān)重要，即并行查找并行查找的方法用相聯(lián)存儲器實現(xiàn)，按內(nèi)容檢索用單體多字存儲器和比較器實現(xiàn)顯然相聯(lián)度N越大，實現(xiàn)查找的機制就越復(fù)雜，代價就越高無論直接映象還是組相聯(lián)，查找時，只需比較tag，index無需參加比較2025/3/6計算機體系結(jié)構(gòu)25Tag和數(shù)據(jù)陣列并行訪問的邏輯結(jié)構(gòu)2025/3/6計算機體系結(jié)構(gòu)26Tag和數(shù)據(jù)陣列并行訪問的流水線模式2025/3/6計算機體系結(jié)構(gòu)27Tag和數(shù)據(jù)陣列串行訪問的邏輯結(jié)構(gòu)2025/3/6計算機體系結(jié)構(gòu)28Tag和數(shù)據(jù)陣列串行訪問的流水線模式2025/3/6計算機體系結(jié)構(gòu)29直接映像Cache查找過程2025/3/6計算機體系結(jié)構(gòu)30全相聯(lián)Cache查找過程2025/3/6計算機體系結(jié)構(gòu)31Example:1KBDirectMappedCachewith32BBlocks對于容量為2N

字節(jié)的cache:最高(32-N)位部分

為CacheTag最低M位為字節(jié)選擇位(BlockSize=2M)2025/3/6計算機體系結(jié)構(gòu)32CacheIndex0123:

CacheDataByte00431:CacheTagExample:0x50Ex:0x010x50Storedaspartofthecache“state”ValidBit:31Byte1Byte31:Byte32Byte33Byte63:Byte992Byte1023:

CacheTagByteSelectEx:0x009BlockaddressExample:SetAssociativeCacheN-waysetassociative:每一個cache索引對應(yīng)N個cacheentries這N個cache項并行操作Example:Two-waysetassociativecacheCacheindex選擇cache中的一組這一組中的兩塊對應(yīng)的Tags與輸入的地址同時比較根據(jù)比較結(jié)果選擇數(shù)據(jù)2025/3/6計算機體系結(jié)構(gòu)33CacheDataCacheBlock1CacheTagValid:::CacheDataCacheBlock0CacheTagValid:::CacheIndexMux01Sel1Sel0CacheBlockCompareAdrTagCompareORHitQ3：替換算法主存中塊數(shù)一般比cache中的塊多，可能出現(xiàn)該塊所對應(yīng)的一組或一個Cache塊已全部被占用的情況，這時需強制騰出其中的某一塊，以接納新調(diào)入的塊，替換哪一塊，這是替換算法要解決的問題：直接映象，因為只有一塊，別無選擇組相聯(lián)和全相聯(lián)有多種選擇替換方法隨機法（Random)，隨機選擇一塊替換優(yōu)點：簡單，易于實現(xiàn)缺點：沒有考慮Cache塊的使用歷史，反映程序的局部性較差，失效率較高FIFO－選擇最早調(diào)入的塊優(yōu)點：簡單雖然利用了同一組中各塊進入Cache的順序，但還是反映程序局部性不夠，因為最先進入的塊，很可能是經(jīng)常使用的塊最近最少使用法（LRU)(LeastRecentlyUsed)優(yōu)點：較好的利用了程序的局部性，失效率較低缺點：比較復(fù)雜，硬件實現(xiàn)較困難2025/3/6計算機體系結(jié)構(gòu)34LRU和Random的比較（失效率）觀察結(jié)果（失效率）相聯(lián)度高，失效率較低。Cache容量較大，失效率較低。LRU在Cache容量較小時，失效率較低隨著Cache容量的加大，Random的失效率在降低2025/3/6計算機體系結(jié)構(gòu)35DataCachemissesper1000instructionscomparingLRU,Random,FIFOreplacementforseveralsizesandassociativities.Thesedatawerecollectedforablocksizeof64bytesfortheAlphaarchitectureusing10SPEC2000benchmarks.FivearefromSPECint2000(gap,gcc,gzip,mcfandperl)andfivearefromSPECfp2000(applu,art,equake,lucasandswim)Q4:寫策略程序?qū)Υ鎯ζ髯x操作占26％，寫操作占9％寫所占的存儲器訪問比例9/(100+26+9)大約為7％占訪問數(shù)據(jù)Cache的比例：9/(26+9)大約為25%大概率事件優(yōu)先原則－優(yōu)化Cache的讀操作Amdahl定律：不可忽視“寫”的速度“寫”的問題讀出標(biāo)識，確認(rèn)命中后，對Cache寫（串行操作）Cache與主存內(nèi)容的一致性問題寫策略就是要解決:何時更新主存問題2025/3/6計算機體系結(jié)構(gòu)36兩種寫策略寫直達法（Writethrough)優(yōu)點：易于實現(xiàn)，容易保持不同層次間的一致性缺點：速度較慢寫回法優(yōu)點：速度快，減少訪存次數(shù)缺點：一致性問題當(dāng)發(fā)生寫失效時的兩種策略按寫分配法(Writeallocate)：寫失效時，先把所寫單元所在塊調(diào)入Cache，然后再進行寫入，也稱寫時?。‵etchonWrite)方法不按寫分配法（no-writeallocate):寫失效時，直接寫入下一級存儲器，而不將相應(yīng)塊調(diào)入Cache，也稱繞寫法（Writearound)原則上以上兩種方法都可以應(yīng)用于寫直達法和寫回法，一般情況下WriteBack用WriteallocateWritethrough用no-writeallocate2025/3/6計算機體系結(jié)構(gòu)37Write-back,WriteAllocate2025/3/6計算機體系結(jié)構(gòu)38Write-Through,NoWriteAllocate2025/3/6計算機體系結(jié)構(gòu)3904/02-Review存儲系統(tǒng)的性能指標(biāo)：速度、容量和價格平均訪存時間=命中時間+失效率×失效開銷Cache4Q映射規(guī)則查找方法替換策略寫策略2025/3/6計算機體系結(jié)構(gòu)40AlphaAX21064Cache結(jié)構(gòu)（數(shù)據(jù)Cache)基本技術(shù)特性容量8KB，Block32Bytes,共256個Blocks，每個字為8個字節(jié)直接映象寫直達法，寫失效時，no-writeallocate方法寫緩沖：4個blocks21064物理地址34位21位tag##8位index##5位塊內(nèi)偏移Cache命中的步驟讀命中寫命中Cache失效Cache向CPU發(fā)暫停信號塊傳送，21064Cache與下一級存儲器之間數(shù)據(jù)通路16字節(jié)，傳送全部32字節(jié)需要10個cycles2025/3/6計算機體系結(jié)構(gòu)41AlphaAX21064Cache結(jié)構(gòu)（數(shù)據(jù)Cache)基本技術(shù)特性Block32bytesperBlock,共256個Block直接映象寫直達法，寫失效時，no-writeallocate方法21064物理地址34位21位tag##8位index##5位塊內(nèi)偏移Cache命中的步驟讀命中寫命中Cache失效Cache向CPU發(fā)暫停信號塊傳送，21064Cache與下一級存儲器之間數(shù)據(jù)通路16字節(jié)，傳送全部32字節(jié)需要10個cycles2025/3/6計算機體系結(jié)構(gòu)42Alpha21264DataCache基本技術(shù)特征Cachesize:64KbytesBlocksize:64-bytesTwo-way組相聯(lián)Writeback,寫失效時，writeallocate2126448-bits虛擬地址，虛實映射為44-bits的物理地址，也支持43-bits虛擬地址，虛實映射為41-bits的物理地址29位tags##9位index##6位Blockoffset2025/3/6計算機體系結(jié)構(gòu)43Alpha21264DataCache2025/3/6計算機體系結(jié)構(gòu)44Cache性能分析CPUtime=(CPUexecutionclockcycles+

Memorystallclockcycles)xclockcycletime

Memorystallclockcycles=

(ReadsxReadmissratexReadmisspenalty+

WritesxWritemissratexWritemisspenalty)

Memorystallclockcycles=

MemoryaccessesxMissratexMisspenaltyDifferentmeasure:AMAT

AverageMemoryAccesstime(AMAT)=

HitTime+(MissRatexMissPenalty)Note:memoryhittimeisincludedinexecutioncycles.2025/3/6計算機體系結(jié)構(gòu)45性能分析舉例SupposeaprocessorexecutesatClockRate=200MHz(5nspercycle),Ideal(nomisses)CPI=1.150%arith/logic,30%ld/st,20%controlMissBehavior:10%ofmemoryoperationsget50cyclemisspenalty1%ofinstructionsgetsamemisspenaltyCPI =idealCPI+averagestallsperinstruction =1.1(cycles/ins)+

[0.30(DataMops/ins)

x0.10(miss/DataMop)x50(cycle/miss)]+

[1(InstMop/ins)

x0.01(miss/InstMop)x50(cycle/miss)]

=(1.1+1.5+.5)cycle/ins=3.165%(2/3.1)ofthetimetheprocisstalledwaitingformemory!AMAT=(1/1.3)x[1+0.01x50]+(0.3/1.3)x[1+0.1x50]=2.542025/3/6計算機體系結(jié)構(gòu)46Example:HarvardArchitectureUnifiedvsSeparateI&D(Harvard)Statistics(giveninH&P):16KBI&D:Instmissrate=0.64%,Datamissrate=6.47%32KBunified:Aggregatemissrate=1.99%Whichisbetter(ignoreL2cache)?Assume33%dataops

75%accessesfrominstructions(1.0/1.33)hittime=1,misstime=50Notethatdatahithas1stallforunifiedcache(onlyoneport)AMATHarvard=75%x(1+0.64%x50)+25%x(1+6.47%x50)=2.05AMATUnified=75%x(1+1.99%x50)+25%x(1+1+1.99%x50)=2.242025/3/6計算機體系結(jié)構(gòu)47ProcI-Cache-1ProcUnifiedCache-1UnifiedCache-2D-Cache-1ProcUnifiedCache-22025/3/6計算機體系結(jié)構(gòu)48以順序執(zhí)行的計算機UltraSPARCIII為例.假設(shè)Cache失效開銷為100clockcycles，所有指令忽略存儲器停頓需要1個cycle,Cache失效可以用兩種方式給出（1）假設(shè)平均失效率為2%，平均每條指令訪存1.5次（2）假設(shè)每1000條指令cache失效次數(shù)為30次分別基于上述兩種條件計算處理器的性能結(jié)論：CPUtime=IC*(1+2%*1.5*100)*T=IC*4*T(1)CPI越低，固定周期數(shù)的Cache失效開銷的相對影響就越大(2)在計算CPI時，失效開銷的單位是時鐘周期數(shù)。因此，即使兩臺計算機的存儲層次完全相同，時鐘頻率較高的CPU的失效開銷會較大，其CPI中存儲器停頓部分也就較大。因此Cache對于低CPI，高時鐘頻率的CPU來說更加重要2025/3/6計算機體系結(jié)構(gòu)49考慮不同組織結(jié)構(gòu)的Cache對性能的影響:B-19例題：直接映像Cache和兩路組相聯(lián)Cache，試問他們對CPU性能的影響？先求平均訪存時間，然后再計算CPU性能。分析時請用以下假設(shè)：（1）理想Cache(命中率為100%）情況下CPI為1.0，時鐘周期為0.35ns，平均每條指令訪存1.4次（2）兩種Cache容量均為128KB，塊大小都是64B（3）采用組相聯(lián)時，由于多路選擇器的存在，時鐘周期增加到原來的1.35倍（4）兩種結(jié)構(gòu)的失效開銷都是65ns(在實際應(yīng)用中，應(yīng)取整為整數(shù)個時鐘周期）（5）命中時間為1個cycle，128KB直接映像Cache的失效率為2.1%,相同容量的兩路組相聯(lián)Cache的失效率為1.9%2025/3/6計算機體系結(jié)構(gòu)50失效開銷與Out-of-Order執(zhí)行的處理器需要確定兩個參數(shù)：LengthofmemorylatencyLengthoflatencyoverlap例如：在前面的例子中，若假設(shè)允許處理器亂序執(zhí)行，則對于直接映射方式，假設(shè)30%的失效開銷可以覆蓋（overlap)，那么原來的70ns失效開銷就變?yōu)?9ns.2025/3/6計算機體系結(jié)構(gòu)51-reviewCache基本原理4QCache性能分析CPUtime=(CPUexecutionclockcycles+

Memorystallclockcycles)xclockcycletimeMemorystallclockcycles=

(ReadsxReadmissratexReadmisspenalty+

WritesxWritemissratexWritemisspenalty)Memorystallclockcycles=

MemoryaccessesxMissratexMisspenaltyDifferentmeasure:AMAT

AverageMemoryAccesstime(AMAT)=

HitTime+(MissRatexMissPenalty)2025/3/6計算機體系結(jié)構(gòu)52Summaryofperformanceequationsinthischapter2025/3/6計算機體系結(jié)構(gòu)534.3基本Cache優(yōu)化方法降低失效率1、增加Cache塊的大小2、增大Cache容量3、提高相聯(lián)度減少失效開銷4、多級Cache5、使讀失效優(yōu)先于寫失效縮短命中時間6、避免在索引緩存期間進行地址轉(zhuǎn)換2025/3/6計算機體系結(jié)構(gòu)54改進Cache性能的方法平均訪存時間＝命中時間＋失效率×失效開銷從上式可知，基本途徑降低失效率減少失效開銷縮短命中時間2025/3/6計算機體系結(jié)構(gòu)55降低失效率Cache失效的原因可分為三類3C強制性失效(Compulsory)第一次訪問某一塊，只能從下一級Load，也稱為冷啟動或首次訪問失效容量失效（Capacity)如果程序執(zhí)行時，所需塊由于容量不足，不能全部調(diào)入Cache，則當(dāng)某些塊被替換后，若又重新被訪問，就會發(fā)生失效?？赡軙l(fā)生“抖動”現(xiàn)象沖突失效（Conflict(collision))組相聯(lián)和直接相聯(lián)的副作用若太多的塊映像到同一組（塊）中，則會出現(xiàn)該組中某個塊被別的塊替換（即使別的組或塊有空閑位置)，然后又被重新訪問的情況，這就屬于沖突失效2025/3/6計算機體系結(jié)構(gòu)56各種類型的失效率2025/3/6計算機體系結(jié)構(gòu)57從統(tǒng)計規(guī)律中得到的一些結(jié)果相聯(lián)度越高，沖突失效就越小強制性失效和容量失效不受相聯(lián)度的影響強制性失效不受Cache容量的影響容量失效隨著容量的增加而減少符合2:1Cache經(jīng)驗規(guī)則即大小為N的直接映象Cache的失效率約等于大小為N/2的兩路組相聯(lián)的Cache失效率。2025/3/6計算機體系結(jié)構(gòu)58減少3C的方法從統(tǒng)計規(guī)律可知增大Cache容量對沖突和容量失效的減少有利增大塊減緩強制性失效可能會增加沖突失效（因為在容量不變的情況下，塊的數(shù)目減少了）通過預(yù)取可幫助減少強制性失效必須小心不要把你需要的東西換出去需要預(yù)測比較準(zhǔn)確（對數(shù)據(jù)較困難，對指令相對容易）2025/3/6計算機體系結(jié)構(gòu)59增加塊的大小2025/3/6計算機體系結(jié)構(gòu)60塊大小、容量對失效率的影響Given:missratesfordifferentcachesizes&blocksizesMemorylatency=80cycles+1cycleper8bytesLatencyof16-byteblock=80+2=82clockcyclesLatencyof32-byteblock=80+4=84clockcyclesLatencyof256-byteblock=80+32=112clockcyclesWhichblockhassmallestAMATforeachcachesize?2025/3/6計算機體系結(jié)構(gòu)61塊大小、容量對AMAT的影響Solution:assumehittime=1clockcycleRegardlessofblocksizeandcachesizeCacheSize=4KB,BlockSize=16bytesAMAT=1+8.57%×82=8.027clockcyclesCacheSize=256KB,BlockSize=256bytesAMAT=1+0.49%×112=1.549clockcycles2025/3/6計算機體系結(jié)構(gòu)62塊大小、容量對AMAT的影響降低失效率最簡單的方法是增加塊大?。唤y(tǒng)計結(jié)果如圖所示假定存儲系統(tǒng)在延遲40個時鐘周期后，每2個時鐘周期能送出16個字節(jié)，即：經(jīng)過42個時鐘周期，它可提供16個字節(jié)；經(jīng)過44個四周周期，可提供32個字節(jié)；依此類推。試根據(jù)圖5-6列出的各種容量的Cache，在塊大小分別為多少時，平均訪存時間最小？2025/3/6計算機體系結(jié)構(gòu)63塊大小、容量的權(quán)衡從統(tǒng)計數(shù)據(jù)可得到如下結(jié)論對于給定Cache容量，塊大小增加時，失效率開始是下降，但后來反而上升Cache容量越大，使失效率達到最低的塊大小就越大分析塊大小增加，可使強制性失效減少（空間局部性原理）塊大小增加，可使沖突失效增加（Cache中塊數(shù)量減少）失效開銷增大（上下層間移動，數(shù)據(jù)傳輸時間變大）設(shè)計塊大小的原則，不能僅看失效率原因：平均訪存時間＝命中時間＋失效率×失效開銷2025/3/6計算機體系結(jié)構(gòu)64提高相聯(lián)度8路組相聯(lián)在降低失效率方面的作用已經(jīng)和全相聯(lián)一樣有效2:1Cache經(jīng)驗規(guī)則容量為N的直接映象Cache失效率與容量為N/2的兩路組相聯(lián)Cache的失效率差不多相同提高相聯(lián)度，會增加命中時間2025/3/6計算機體系結(jié)構(gòu)65VictimCache(1/2)在Cache和Memory之間增加一個小的全相聯(lián)Cache2025/3/6計算機體系結(jié)構(gòu)66VictimCache(2/2)基本思想通常Cache為直接映象時沖突失效率較大Victimcache采用全相聯(lián)－失效率較低Victimcache存放由于失效而被丟棄的那些塊失效時，首先檢查Victimcache是否有該塊，如果有就將該塊與Cache中相應(yīng)塊比較。Jouppi(DECSRC)發(fā)現(xiàn)，含1到5項的Victimcache對減少失效很有效，尤其是對于那些小型的直接映象數(shù)據(jù)Cache。測試結(jié)果，項為4的VictimCache能使4KB直接映象數(shù)據(jù)Cache沖突失效減少20%-90%2025/3/6計算機體系結(jié)構(gòu)67減少失效開銷減少CPU與存儲器間性能差異的重要手段平均訪存時間＝命中時間＋失效率×失效開銷基本手段：4、多級Cache技術(shù)(MultilevelCaches)5、讓讀優(yōu)先于寫(GivingPrioritytoReadMissesoverWrites)2025/3/6計算機體系結(jié)構(gòu)68采用多級Cache一級cache保持較小容量降低命中時間降低每次訪問的能耗增加二級cache減少與存儲器的gap減少存儲器總線的負(fù)載多級cache的優(yōu)點減少失效開銷縮短平均訪存時間（AMAT）較大容量的L2

cache可以捕捉許多L1

cache的失效降低全局失效率2025/3/6計算機體系結(jié)構(gòu)69多級包容性(multilevelinclusive)L1cache的塊總是存在于L2cache中浪費了L2cache空間，L2還應(yīng)當(dāng)有存放其他塊的空間L1中miss,但在L2中命中，則從L2拷貝相應(yīng)的塊到L1在L1和L2中均miss,則從更低級拷貝相應(yīng)的塊到L1和L2對L1寫操作導(dǎo)致將數(shù)據(jù)同時寫到L1和L2Write-through策略用于L1到L2Write-back策略可用于L2到更低級存儲器，以降低存儲總線的數(shù)據(jù)傳輸壓力L2的替換動作（或無效)對L1可見即L2的一塊被替換出去，那么其在L1中對應(yīng)的塊也要被替換出去。2025/3/6計算機體系結(jié)構(gòu)70訪問的塊序列10246替換策略：LRU塊大小相同2025/3/6計算機體系結(jié)構(gòu)71012345670110244161602421Invalid0(0)0(1)2025/3/6計算機體系結(jié)構(gòu)7201012345670(0)0(1)1(2)1(3)2(4)2(5)3(6)3(7)41L1和L2的塊大小不同，L1的blockSize是L2的blockSize的1/2替換策略：LRU考察按L1的塊劃分的訪問序列：0148812(4)2(5)Invalid4(8)4(9)Invalid多級不包容（MultilevelExclusive）L1cache中的塊不會在L2

cache中，以避免浪費空間在L1中miss,但在L2中命中，將導(dǎo)致Cache間塊的互換在L1和L2中均miss,將僅僅從更低層拷貝相應(yīng)的塊到L1L1的被替換的塊移至L2L2存儲L1拋棄的塊，以防后續(xù)L1還需要使用L1到L2的寫策略為Write-BackL2到更低級cache的寫策略為Write-BackL1和L2的塊大小可以相同也可以不同Pentium4had64-byteblocksinL1but128-byteblocksinL2Corei7uses64-byteblocksatallcachelevels(simpler)2025/3/6計算機體系結(jié)構(gòu)73012025/3/6計算機體系結(jié)構(gòu)7400123456L1：1-wayL2：2-way訪問的塊序列01234563替換策略：LRU塊大小相同2123434565WriteBack00101201234--2363452--L2#3L1#5互換

------------2025/3/6計算機體系結(jié)構(gòu)7501012345678910110(0)0(1)1(2)1(3)2(4)2(5)3(6)3(7)4(8)4(9)5(10)23L1和L2的塊大小不同，L1的blockSize是L2的blockSize的1/2替換策略：LRU考察按L1的塊劃分的訪問序列：012345678910114(L2#4與L1中的#10互換）878910921434565671011WriteBack0(0)0(1)411------------0(0)------------0(0)0(1)--------0(0)0(1)1(2)--------0(0)0(1)1(2)1(3)------0(0)0(1)1(2)1(3)2(4)------0(0)0(1)1(2)1(3)2(4)2(5)----0(0)0(1)1(2)1(3)2(4)2(5)3(6)--0(0)0(1)1(2)1(3)2(4)2(5)3(6)3(7)4(8)1(2)1(3)2(4)2(5)3(6)3(7)4(8)4(9)1(2)1(3)2(4)2(5)3(6)3(7)4(8)4(9)5(10)----2(5)3(6)3(7)04/04-review基本Cache優(yōu)化方法降低失效率：引起失效的3C1、增加Cache塊的大小2、增大Cache容量3、提高相聯(lián)度減少失效開銷4、多級Cache5、使讀失效優(yōu)先于寫失效縮短命中時間6、避免在索引緩存期間進行地址轉(zhuǎn)換2025/3/6計算機體系結(jié)構(gòu)7604/04-課堂練習(xí):直接映像Cache和兩路組相聯(lián)Cache，試問他們對CPU性能的影響？先求平均訪存時間，然后再計算CPU性能。分析時請用以下假設(shè)：（1）理想Cache(命中率為100%）情況下CPI為1.0，時鐘周期為0.35ns，平均每條指令訪存1.4次（2）兩種Cache容量均為128KB，塊大小都是64B（3）采用組相聯(lián)時，由于多路選擇器的存在，時鐘周期增加到原來的1.35倍（4）兩種結(jié)構(gòu)的失效開銷都是65ns(在實際應(yīng)用中，應(yīng)取整為整數(shù)個時鐘周期）（5）命中時間為1個cycle，128KB直接映像Cache的失效率為2.1%,相同容量的兩路組相聯(lián)Cache的失效率為1.9%2025/3/6計算機體系結(jié)構(gòu)77多級cache的性能分析局部失效率：該級Cache的失效次數(shù)/到達該級Cache的訪存次數(shù)Miss

rateL1

forL1cacheMissrateL2forL2cache全局失效率：該級Cache的失效次數(shù)/CPU發(fā)出的訪存總次數(shù)MissrateL1forL1cacheMissrateL1×MissrateL2forL2cache全局失效率是度量L2cache性能的更好方法性能參數(shù)AMAT=HitTimeL1+MissrateL1×MisspenaltyL1MisspenaltyL1=HitTimeL2+MissrateL2×MisspenaltyL2AMAT=HitTimeL1+MissrateL1×(HitTimeL2+MissrateL2×MisspenaltyL2)2025/3/6計算機體系結(jié)構(gòu)78L1

cache失效率對于I-Cache和D-Cache分開的L1

Cache

MissRateL1=%inst×MissRateI-Cache+%data×MissRateD-Cache

%inst=PercentofInstructionAccesses=1/(1+%LS)

%data=PercentofDataAccesses=%LS/(1+%LS)

%LS=FrequencyofLoadandStoreinstructions每條指令的L1失效次數(shù):

MissesperInstructionL1=MissRateL1×(1+%LS)

MissesperInstructionL1=MissRateI-Cache+%LS×MissRateD-Cache2025/3/6計算機體系結(jié)構(gòu)79具有二級Cache的AMAT舉例Problem:計算AMATI-Cache失效率=

1%，D-Cache失效率=

10%L2

Cache失效率=

40%L1命中時間=

1

cycle(I-Cache和D-Cache相同）L2命中時間=

8

cycles，L2失效開銷=

100cyclesLoad+Store指令頻度=

25%Solution：平均每條指令訪存次數(shù)=

1+25%

=

1.25平均每條指令的失效次數(shù)=

1%+25%×10%

=

0.035L1的失效率=

0.035/1.25=0.028L1的失效開銷=

8

+

0.4×100

=

48

cyclesAMAT

=

1+0.028×48

=

2.3442025/3/6計算機體系結(jié)構(gòu)80Memory

Stall

CyclesPerInstructionMemoryStallCyclesperInstruction=MemoryAccessperInstruction×MissRateL1×MissPenaltyL1=(1+%LS)×MissRateL1×MissPenaltyL1=(1+%LS)×MissRateL1×(HitTimeL2+MissRateL2×MissPenaltyL2)MemoryStallCyclesperInstruction=MissesperInstructionL1×HitTimeL2+MissesperInstructionL2×MissPenaltyL2MissesperInstructionL1=(1+%LS)×MissRateL1MissesperInstructionL2=(1+%LS)×MissRateL1×MissRateL22025/3/6計算機體系結(jié)構(gòu)81兩級Cache的性能Problem:程序運行產(chǎn)生1000個存儲器訪問I-Cachemisses=5,D-Cachemisses=35,L2Cachemisses=8L1Hit=1cycle,L2Hit=8cycles,L2Misspenalty=80cyclesLoad+Storefrequency=25%,CPIexecution=1.1(perfectcache)計算memorystallcyclesperinstruction和有效的CPI如果沒有L2

cache,有效的CPI是多少？Solution：L1MissRate=(5+35)/1000=0.04(or4%peraccess)L1missesperInstruction=0.04×(1+0.25)=0.05L2missesperInstruction=(8/1000)×1.25=0.01MemorystallcyclesperInstruction=0.05×8+0.01×80=1.2CPIL1+L2=

1.1+1.2=2.3,CPI/CPIexecution=2.3/1.1=2.1xslowerCPIL1only=1.1+0.05×80=5.1(worse)2025/3/6計算機體系結(jié)構(gòu)82不同大小的L2cache對應(yīng)的執(zhí)行時間2025/3/6計算機體系結(jié)構(gòu)83Missratesversuscachesizeformultilevelcaches2025/3/6計算機體系結(jié)構(gòu)84兩級Cache的一些研究結(jié)論在L2比L1大得多得情況下，兩級Cache全局失效率和容量與第二級Cache相同的單級Cache的失效率接近局部失效率不是衡量第二級Cache的好指標(biāo)它是第一級Cache失效率的函數(shù)不能全面反映兩級Cache體系的性能第二級Cache設(shè)計需考慮的問題容量：一般很大，可能沒有容量失效，只有強制性失效和沖突失效相聯(lián)度對第二級Cache的作用Cache可以較大，以減少失效次數(shù)多級包容性問題：第一級Cache中的數(shù)據(jù)是否總是同時存在于第二級Cache中。如果L1和L2的塊大小不同，增加了多級包容性實現(xiàn)的復(fù)雜性2025/3/6計算機體系結(jié)構(gòu)85多級Cache舉例Giventhedatabelow,whatistheimpactofsecond-levelcacheassociativityonitsmisspenalty?HittimeL2fordirectmapped=10clockcyclesTwo-waysetassociativityincreaseshittimeby0.1clockcyclesto10.1clockcyclesLocalmissrateL2fordirectmapped=25%LocalmissrateL2fortwo-waysetassociative=20%MisspenaltyL2=100clockcycles結(jié)論：提高相聯(lián)度，可減少第一級Cache的失效開銷第二級Cache特點：容量大，高相聯(lián)度，塊較大，重點減少失效次數(shù)。2025/3/6計算機體系結(jié)構(gòu)86讓讀優(yōu)先于寫圖示2025/3/6計算機體系結(jié)構(gòu)87讓讀失效優(yōu)先于寫由于讀操作為大概率事件，需要讀失效優(yōu)先，以提高性能Write-ThroughCache->WriteBuffer(寫緩沖)，特別對寫直達法更有效WriteBuffer:CPU不必等待寫操作完成，即將要寫的數(shù)據(jù)和地址送到WriteBuffer后，CPU繼續(xù)作其他操作。寫緩沖導(dǎo)致對存儲器訪問的復(fù)雜化在讀失效時寫緩沖中可能保存有所讀單元的最新值，還沒有寫回例如，直接映射、寫直達、512和1024映射到同一塊。則SWR3,512(R0)LWR1,1024(R0)失效

LWR2,512(R0)失效解決問題的方法推遲對讀失效的處理，直到寫緩沖器清空，導(dǎo)致新的問題——讀失效開銷增大。在讀失效時，檢查寫緩沖的內(nèi)容，如果沒有沖突，而且存儲器可訪問，就可以繼續(xù)處理讀失效寫回法時，也可以利用寫緩沖器來提高性能把臟塊放入緩沖區(qū)，然后讀存儲器，最后寫存儲器Write-BackCache->VictimBuffer被替換的臟塊放到了victimbuffer在臟塊被寫回前，需要處理讀失效問題:victimbuffer可能含有該讀失效要讀取的塊Solution:查找victimbuffer，如果命中直接將該塊調(diào)入Cache2025/3/6計算機體系結(jié)構(gòu)88縮短命中時間Copyright?2011,ElsevierInc.AllrightsReserved.FigureB.16Missrateversusvirtuallyaddressedcachesizeofaprogrammeasuredthreeways:withoutprocessswitches(uniprocess),withprocessswitchesusingaprocess-identifiertag(PID),andwithprocessswitchesbutwithoutPIDs(purge).PIDsincreasetheuniprocessabsolutemissrateby0.3%to0.6%andsave0.6%to4.3%overpurging.Agarwal[1987]collectedthesestatisticsfortheUltrixoperatingsystemrunningonaVAX,assumingdirect-mappedcacheswithablocksizeof16bytes.Notethatthemissrategoesupfrom128Kto256K.Suchnonintuitivebehaviorcanoccurincachesbecausechangingsizechangesthemappingofmemoryblocksontocacheblocks,whichcanchangetheconflictmissrate.虛擬地址CacheVS.物理地址CacheCopyright?2011,ElsevierInc.AllrightsReserved.FigureB.17TheoverallpictureofahypotheticalmemoryhierarchygoingfromvirtualaddresstoL2cacheaccess.Thepagesizeis16KB.TheTLBistwo-waysetassociativewith256entries.TheL1cacheisadirect-mapped16KB,andtheL2cacheisafour-waysetassociativewithatotalof4MB.Bothuse64-byteblocks.Thevirtualaddressis64bitsandthephysicaladdressis40bits.虛擬地址轉(zhuǎn)換與Cache定位并行84.4高級Cache優(yōu)化方法縮短命中時間1、小而簡單的第一級Cache2、路預(yù)測方法增加Cache帶寬3、Cache訪問流水化4、無阻塞Cache減小失效開銷5、多體Cache6、關(guān)鍵字優(yōu)先和提前重啟7、合并寫降低失效率8、編譯優(yōu)化通過并行降低失效代價或失效率9、硬件預(yù)取10、編譯器控制的預(yù)取2025/3/6計算機體系結(jié)構(gòu)911、SmallandsimplefirstlevelcachesSmallandsimplefirstlevelcaches容量小，一般命中時間短，有可能做在片內(nèi)另一方案，保持Tag在片內(nèi)，塊數(shù)據(jù)在片外，如DECAlpha第一級Cache應(yīng)選擇容量小且結(jié)構(gòu)簡單的設(shè)計方案Criticaltimingpath:1)定位組(tag),確定tag的位置

2)比較tags,3)選擇正確的塊Direct-mappedcachescanoverlaptagcompareandtransmissionofdata數(shù)據(jù)傳輸和tag比較并行Lowerassociativityreducespowerbecausefewercachelinesareaccessed簡單的Cache結(jié)構(gòu)、可有效減少tag比較的次數(shù)，進而降低功耗2025/3/6計算機體系結(jié)構(gòu)92L1SizeandAssociativity2025/3/6計算機體系結(jié)構(gòu)93Accesstimevs.sizeandassociativityL1SizeandAssociativity2025/3/6計算機體系結(jié)構(gòu)94Energyperreadvs.sizeandassociativity2、WayPrediction為改進命中時間，預(yù)測被選中的路(way)預(yù)測錯誤會導(dǎo)致更長的命中時間預(yù)測的準(zhǔn)確性90%+fortwo-way80%+forfour-wayI-cache比D-cache具有更好的準(zhǔn)確性90年代中期第一次用于MIPSR10000用于ARMCortex-A8WayPrediction方法也可降低功耗：直接預(yù)測要訪問的塊也稱“路選擇”“Wayselection”可有效降低功耗，但一旦預(yù)測錯誤會有更長的命中時間2025/3/6計算機體系結(jié)構(gòu)95

高級Cache優(yōu)化方法縮短命中時間1、小而簡單的第一級Cache2、路預(yù)測方法增加Cache帶寬3、Cache訪問流水化4、無阻塞Cache減小失效開銷5、多體Cache6、關(guān)鍵字優(yōu)先和提前重啟7、合并寫降低失效率8、編譯優(yōu)化通過并行降低失效代價或失效率9、硬件預(yù)取10、編譯器控制的預(yù)取2025/3/6計算機體系結(jié)構(gòu)963、PipeliningCache實現(xiàn)Cache訪問的流水化提高Cache的帶寬，有利于采用高相聯(lián)度的緩存L1

cache的訪問由多個時鐘周期構(gòu)成Pentium:1cyclePentiumPro–PentiumIII:2cyclesPentium4–Corei7:4cyclesIBM

Power7：3

cycles缺點：增加流水線的段數(shù)增加了分支預(yù)測錯誤造成的額外開銷增加了Load指令與要使用其結(jié)果的指令間的latency增加了I-Cache和D-Cache的延時2025/3/6計算機體系結(jié)構(gòu)972025/3/6計算機體系結(jié)構(gòu)982025/3/6計算機體系結(jié)構(gòu)9904/09-review基本Cache優(yōu)化方法降低失效率：引起失效的3C1、增加Cache塊的大小2、增大Cache容量3、提高相聯(lián)度減少失效開銷4、多級Cache5、使讀失效優(yōu)先于寫失效縮短命中時間6、避免在索引緩存期間進行地址轉(zhuǎn)換2025/3/6計算機體系結(jié)構(gòu)10004/09-review高級Cache優(yōu)化方法縮短命中時間1、小而簡單的第一級Cache2、路預(yù)測方法增加Cache帶寬3、Cache訪問流水化4、無阻塞Cache減小失效開銷5、多體Cache6、關(guān)鍵字優(yōu)先和提前重啟7、合并寫降低失效率8、編譯優(yōu)化通過并行降低失效代價或失效率9、硬件預(yù)取10、編譯器控制的預(yù)取2025/3/6計算機體系結(jié)構(gòu)1014、NonblockingCaches2025/3/6計算機體系結(jié)構(gòu)102允許在Cache失效下繼續(xù)命中在Cache失效時，CPU無需stall主要用于亂序執(zhí)行和多線程處理器HitunderaMiss減少有效的失效開銷增加Cache的帶寬HitunderMultipleMisses針對多個未解決的Cache失效可能會更多地減少有效的失效開銷增加了Cache控制器的復(fù)雜性存儲系統(tǒng)可以支持多個失效時的存儲服務(wù)NonblockingCacheTimeline2025/3/6計算機體系結(jié)構(gòu)103EffectivenessofNon-BlockingCache2025/3/6計算機體系結(jié)構(gòu)104MissStatusHoldingRegister(MSHR)MSHR包含正在等待處理的失效相同的塊可以包含多個未解決的Load/Store失效可以有多個未解決的塊地址失效可以分為Primary:第一次發(fā)起存取請求時的失效塊Secondary:在后續(xù)過程中的失效StructuralStallmiss：MSHR硬件資源耗盡2025/3/6計算機體系結(jié)構(gòu)105NonBlockingCacheOperation當(dāng)Cache失效時，檢查MSHR是否有匹配的塊地址如果有，為該地址分配新的load/store表項如果沒有，分配新的MSHR和load/store表項如果所有MSHR資源都分配完，則Stall（結(jié)構(gòu)相關(guān)）當(dāng)從底層傳輸Cache塊時處理該塊中的Load和Store指令引起的失效Load：根據(jù)blockoffset從該塊中裝載數(shù)據(jù)到寄存器Store：根據(jù)blockoffset將數(shù)據(jù)寫入該塊指定位置完成該塊所有的失效的Load/Store后，釋放MSHR中的對應(yīng)表項

2025/3/6計算機體系結(jié)構(gòu)106Multi-PortedCacheDual-PortedDataCache兩個地址端口（每個Cycle支持兩條load/store指令）在現(xiàn)代處理器中保持較高的指令吞吐率TrueMulti-portedCacheDesign所有的控制和數(shù)據(jù)通路在Cache中是多份的顯著地增加了Cache的面積和訪問時間Multi-BankedCache將cache組織成多個banks每個bank是一個端口可以并行訪問不同的Bank2025/3/6計算機體系結(jié)構(gòu)1075、MultibankedCaches將Cache組織為多個獨立的banks，以支持并行訪問ARMCortex-A8supports1-4banksforL