計算機組成與系統(tǒng)結(jié)構(gòu)

陳澤宇副教授計算機組成與系統(tǒng)結(jié)構(gòu)陳澤宇副教授第1章計算機系統(tǒng)概論第2章運算方法和運算器第3章存儲系統(tǒng)第4章指令系統(tǒng)第5章中央處理器（CPU）第6章總線系統(tǒng)第7章輸入輸出（I/O）系統(tǒng)第8章并行計算機系統(tǒng)第1章計算機系統(tǒng)概論3.4高速緩沖存儲器（CACHE）3.4.1Cache基本原理3.4.2地址映射3.4.3替換策略3.4.4寫操作策略3.4高速緩沖存儲器（CACHE）3.4.1Cache基計算機系統(tǒng)中，CPU的運行速度與主存的訪問速度極不匹配800MHzPentiumIIICPU一條指令的執(zhí)行時間約為1.25ns，而133MHzSDRAM的存取時間為7.5ns在83%的時間內(nèi)CPU都處于等待狀態(tài)，運行效率極低為提高CPU利用率，現(xiàn)代計算機體系結(jié)構(gòu)中廣泛采用高速緩沖存儲器（Cache）技術(shù)計算機系統(tǒng)中，CPU的運行速度與主存的訪問速度極不匹配3.4.1Cache基本原理程序訪問的局部性程序員通常采用模塊化的程序設(shè)計方法，某一模塊的程序往往集中在存儲器邏輯地址空間中很小的一塊范圍內(nèi)，且程序地址分布是連續(xù)的CPU在一段較短的時間內(nèi)，是對連續(xù)地址的一段很小的主存空間頻繁地進行訪問，而對此范圍以外地址的訪問甚少3.4.1Cache基本原理程序訪問的局部性高速緩沖存儲器（Cache）技術(shù)利用程序訪問的局部性原理，把程序中正在使用的部分（活躍塊）存放在一個小容量的高速Cache中，使CPU的訪存操作大多針對Cache進行解決高速CPU和低速主存之間速度不匹配的問題，使程序的執(zhí)行速度大大提高高速緩沖存儲器（Cache）技術(shù)1.Cache的功能Cache是介于CPU和主存之間的小容量存儲器存取速度比主存快，接近CPU能高速地向CPU提供指令和數(shù)據(jù)，提高程序的執(zhí)行速度Cache是主存的緩沖存儲器由高速的SRAM組成所有控制邏輯全部由硬件實現(xiàn)，對程序員而言是透明的有些CPU內(nèi)置Cache，出現(xiàn)了兩級以上的多級Cache系統(tǒng)1.Cache的功能Cache是介于CPU和主存之間的小容Cache系統(tǒng)與CPU和主存的關(guān)系FLASH演示Cache系統(tǒng)與CPU和主存的關(guān)系2.Cache的基本原理CPU與Cache之間的數(shù)據(jù)交換以字為單位Cache與主存之間的數(shù)據(jù)交換以塊為單位一個塊由若干個定長字組成2.Cache的基本原理CPU與Cache之間的數(shù)據(jù)交換以當CPU讀取主存中的一個字時，該字的主存地址被發(fā)給Cache和主存Cache控制邏輯依據(jù)地址判斷該字當前是否存在于Cache中若在，該字立即被從Cache傳送給CPU；若不在，則用主存讀周期把該字從主存讀出送到CPU同時把含有這個字的整個數(shù)據(jù)塊從主存讀出送到Cache中并采用一定的替換策略將Cache中的某一塊替換掉（替換算法由Cache管理邏輯電路來實現(xiàn)）當CPU讀取主存中的一個字時，該字的主存地址被發(fā)給CacheCache原理圖FLASH演示

按內(nèi)容尋址的相聯(lián)存儲器（表）用于存放與Cache中數(shù)據(jù)相對應(yīng)的主存地址可以快速檢索、判斷CPU讀取的某個字當前是否存在于Cache中Cache原理圖3.Cache的命中率基于程序訪問的局部性原理，增加Cache使要訪問的數(shù)據(jù)絕大多數(shù)都可在Cache中找到這樣才能在性能上使主存的平均讀出時間盡可能接近Cache的讀出時間Cache的工作效率通常用“命中率”來表示3.Cache的命中率基于程序訪問的局部性原理，命中率：CPU要訪問的信息在Cache中的概率Cache的命中率越高，CPU訪問主存的速度就越接近訪問Cache的速度通常Cache的容量越大，存儲的塊也越多，CPU的命中率就越高但是，當Cache的容量達到一定值時，命中率并不會隨著容量的增大而增加，而成本卻相應(yīng)增加所以，Cache的容量一般是命中率與成本價格的折中命中率：CPU要訪問的信息在Cache中的概率在一個程序執(zhí)行期間，設(shè)Nc表示Cache完成存取的總次數(shù)，Nm表示主存完成存取的總次數(shù)，h定義為命中率，則有若tc表示命中時的Cache訪問時間，tm表示未命中時的主存訪問時間，1-h表示未命中率，則Cache－主存系統(tǒng)的平均訪問時間ta為：設(shè)e表示訪問效率，則有為提高訪問效率e，命中率h越接近1越好在一個程序執(zhí)行期間，【例3-1】CPU執(zhí)行一段程序時，Cache完成存取的次數(shù)為1900次，主存完成存取的次數(shù)為100次，已知Cache存取周期為50ns，主存存取周期為250ns，求Cache－主存系統(tǒng)的效率和平均訪問時間?！窘狻縉c=1900，Nm=100，tc=50ns，tm=250ns∴ 命中率h=Nc/(Nc+Nm)=1900/(1900+100)=0.95

平均訪問時間ta =htc+(1-h)tm

=0.95×50+(1-0.95)×250=60ns

效率e=tc/ta=50/60=83.3%【例3-1】CPU執(zhí)行一段程序時，Cache完成存取的次數(shù)為3.4.2地址映射Cache的容量很小，保存的只是主存內(nèi)容的一個子集，且Cache與主存的數(shù)據(jù)交換是以塊為單位的為了把信息放到Cache中，必須應(yīng)用某種函數(shù)把主存地址定位到Cache中，這稱為地址映射CPU執(zhí)行程序時，會將程序中的主存地址變換成Cache地址，這個變換過程叫做地址變換假設(shè)某臺計算機主存容量為1MB，被分為2048塊，每塊512BCache容量為8KB，被分為16塊，每塊也是512B3.4.2地址映射Cache的容量很小，保存的只是主存內(nèi)容1.直接映射直接映射的Cache組織主存中的一個塊只能映射到Cache的某一特定塊中去主存的第0塊、第16塊、……、第2032塊，只能映射到Cache的第0塊主存的第1塊、第17塊、……、第2033塊，只能映射到Cache的第1塊……1.直接映射直接映射的Cache組織直接映射是最簡單的地址映射方式硬件簡單，成本低，地址變換速度快，不涉及替換算法不夠靈活，Cache的存儲空間得不到充分利用每個主存塊只有一個固定存放位置，容易產(chǎn)生沖突，使Cache效率下降，因此只適合大容量Cache采用如果一個程序需要重復(fù)引用主存中第0塊與第16塊，最好將主存第0塊與第16塊同時復(fù)制到Cache中但由于它們都只能復(fù)制到Cache的第0塊中去，即使Cache中別的存儲空間空著也不能占用因此這兩個塊會不斷交替裝入Cache，導致命中率降低直接映射是最簡單的地址映射方式2.全相聯(lián)映射全相聯(lián)映射的Cache組織主存中任何一塊都可以映射到Cache中的任何一塊位置上2.全相聯(lián)映射全相聯(lián)映射的Cache組織全相聯(lián)映射方式比較靈活，主存的各塊可以映射到Cache的任一塊中，Cache的利用率高塊沖突概率低只要淘汰Cache中的某一塊，即可調(diào)入主存的任一塊由于Cache比較電路的設(shè)計和實現(xiàn)比較困難，這種方式只適合于小容量Cache采用全相聯(lián)映射方式3.組相聯(lián)映射組相聯(lián)映射是直接映射和全相聯(lián)映射的折中方案主存和Cache都分組主存中一個組內(nèi)的塊數(shù)與Cache

中的分組數(shù)相同組間直接映射，組內(nèi)全相聯(lián)映射將Cache分成u組，每組v塊主存塊存放到哪個組是固定的至于存到該組哪一塊則是靈活的主存分為256組，每組8塊；Cache分為8組，每組2塊3.組相聯(lián)映射組相聯(lián)映射是直接映射和全相聯(lián)映射的折中方案組相聯(lián)映射方式主存中的各塊與Cache的組號之間有固定的映射關(guān)系但可自由映射到對應(yīng)Cache組中的任何一塊主存中的第0塊、第8塊……均映射于Cache的第0組，但可映射到Cache第0組中的第0塊或第1塊；主存的第1塊、第9塊……均映射于Cache的第1組，但可映射到Cache第1組中的第2塊或第3塊組相聯(lián)映射方式常采用的組相聯(lián)結(jié)構(gòu)Cache每組內(nèi)有2、4、8、16塊，稱為2路、4路、8路、16路組相聯(lián)Cache組相聯(lián)結(jié)構(gòu)Cache是前兩種方法的折中方案適度兼顧二者的優(yōu)點盡量避免二者的缺點得到普遍采用常采用的組相聯(lián)結(jié)構(gòu)Cache3.4.3替換策略Cache工作原理要求它盡量保存最新數(shù)據(jù)當從主存向Cache傳送一個新塊，而Cache中可用位置已被占滿時，就會產(chǎn)生Cache替換的問題替換問題與Cache的組織方式緊密相關(guān)：對直接映射Cache來說，只要把此可用位置上的主存塊換出Cache即可對全相聯(lián)和組相聯(lián)Cache來說，從若干可用位置中選取一個，把主存塊換出Cache3.4.3替換策略Cache工作原理要求它盡量保存最新數(shù)據(jù)1.最不經(jīng)常使用（LFU）算法LFU（LeastFrequentlyUsed，最不經(jīng)常使用）算法將一段時間內(nèi)被訪問次數(shù)最少的那個塊替換出去每塊設(shè)置一個計數(shù)器，從0開始計數(shù)，每訪問一次，被訪塊的計數(shù)器就增1當需要替換時，將計數(shù)值最小的塊換出，同時將所有塊的計數(shù)器都清零將計數(shù)周期限定在對這些特定塊兩次替換的間隔時間內(nèi)不能嚴格反映近期訪問情況新調(diào)入的塊很容易被替換出去1.最不經(jīng)常使用（LFU）算法LFU（LeastFreq2.近期最少使用（LRU）算法LRU（LeastRecentlyUsed，近期最少使用）算法把CPU近期最少使用的塊替換出去需要隨時記錄Cache中各塊的使用情況，以便確定哪個塊是近期最少使用的塊每塊設(shè)置一個計數(shù)器，Cache每命中一次，命中塊計數(shù)器清零，其他各塊計數(shù)器增1當需要替換時，將計數(shù)值最大的塊換出2.近期最少使用（LRU）算法LRU（LeastReceLRU算法相對合理，但實現(xiàn)起來比較復(fù)雜，系統(tǒng)開銷較大保護了剛調(diào)入Cache的新數(shù)據(jù)塊，具有較高的命中率不能肯定調(diào)出去的塊近期不會再被使用，所以不能算作最合理、最優(yōu)秀的算法研究表明，采用這種算法可使Cache命中率達到90%左右LRU算法相對合理，但實現(xiàn)起來比較復(fù)雜，系統(tǒng)開銷較大3.隨機替換最簡單的替換算法是隨機替換完全不管Cache的情況，簡單地根據(jù)一個隨機數(shù)選擇一塊替換出去在硬件上容易實現(xiàn)，且速度也比前兩種算法快缺點是降低了命中率和Cache工作效率3.隨機替換最簡單的替換算法是隨機替換3.4.4寫操作策略由于Cache的內(nèi)容只是主存內(nèi)容的一個子集，應(yīng)當與主存內(nèi)容保持一致，而CPU對Cache的寫入更改了Cache的內(nèi)容為此，可選用寫操作策略使Cache內(nèi)容與主存內(nèi)容保持一致3.4.4寫操作策略由于Cache的內(nèi)容只是主存內(nèi)容的一個1、寫回法（Write-Back）當CPU寫Cache命中時，只修改Cache的內(nèi)容，而不立即寫入主存只有當此塊被換出時才寫回主存寫Cache和寫主存異步進行，顯著減少訪問主存的次數(shù)但存在數(shù)據(jù)不一致的隱患實現(xiàn)這種方法時，每個Cache塊必須配置一個修改位，以反映此塊是否被CPU修改過1、寫回法（Write-Back）當CPU寫Cache命中時2、全寫法（Write-Through）當寫Cache命中時，Cache與主存同時發(fā)生寫修改寫Cache和寫主存同步進行較好地維護了Cache與主存的內(nèi)容一致性實現(xiàn)這種方法時，Cache中的每個塊無需設(shè)置修改位以及相應(yīng)的判斷邏輯由于Cache對CPU向主存的寫操作沒有高速緩沖功能，從而降低了Cache的功效2、全寫法（Write-Through）當寫Cache命中時3、寫一次法（Write-Once）寫一次法是基于寫回法并結(jié)合全寫法的寫操作策略寫命中與寫未命中的處理方法與寫回法基本相同只是第一次寫命中時要同時寫入主存，以便于維護系統(tǒng)全部Cache的一致性3、寫一次法（Write-Once）寫一次法是基于寫回法并結(jié)本講到此結(jié)束，謝謝！本講到此結(jié)束，謝謝！計算機組成與系統(tǒng)結(jié)構(gòu)

陳澤宇副教授計算機組成與系統(tǒng)結(jié)構(gòu)陳澤宇副教授第1章計算機系統(tǒng)概論第2章運算方法和運算器第3章存儲系統(tǒng)第4章指令系統(tǒng)第5章中央處理器（CPU）第6章總線系統(tǒng)第7章輸入輸出（I/O）系統(tǒng)第8章并行計算機系統(tǒng)第1章計算機系統(tǒng)概論3.4高速緩沖存儲器（CACHE）3.4.1Cache基本原理3.4.2地址映射3.4.3替換策略3.4.4寫操作策略3.4高速緩沖存儲器（CACHE）3.4.1Cache基計算機系統(tǒng)中，CPU的運行速度與主存的訪問速度極不匹配800MHzPentiumIIICPU一條指令的執(zhí)行時間約為1.25ns，而133MHzSDRAM的存取時間為7.5ns在83%的時間內(nèi)CPU都處于等待狀態(tài)，運行效率極低為提高CPU利用率，現(xiàn)代計算機體系結(jié)構(gòu)中廣泛采用高速緩沖存儲器（Cache）技術(shù)計算機系統(tǒng)中，CPU的運行速度與主存的訪問速度極不匹配3.4.1Cache基本原理程序訪問的局部性程序員通常采用模塊化的程序設(shè)計方法，某一模塊的程序往往集中在存儲器邏輯地址空間中很小的一塊范圍內(nèi)，且程序地址分布是連續(xù)的CPU在一段較短的時間內(nèi)，是對連續(xù)地址的一段很小的主存空間頻繁地進行訪問，而對此范圍以外地址的訪問甚少3.4.1Cache基本原理程序訪問的局部性高速緩沖存儲器（Cache）技術(shù)利用程序訪問的局部性原理，把程序中正在使用的部分（活躍塊）存放在一個小容量的高速Cache中，使CPU的訪存操作大多針對Cache進行解決高速CPU和低速主存之間速度不匹配的問題，使程序的執(zhí)行速度大大提高高速緩沖存儲器（Cache）技術(shù)1.Cache的功能Cache是介于CPU和主存之間的小容量存儲器存取速度比主存快，接近CPU能高速地向CPU提供指令和數(shù)據(jù)，提高程序的執(zhí)行速度Cache是主存的緩沖存儲器由高速的SRAM組成所有控制邏輯全部由硬件實現(xiàn)，對程序員而言是透明的有些CPU內(nèi)置Cache，出現(xiàn)了兩級以上的多級Cache系統(tǒng)1.Cache的功能Cache是介于CPU和主存之間的小容Cache系統(tǒng)與CPU和主存的關(guān)系FLASH演示Cache系統(tǒng)與CPU和主存的關(guān)系2.Cache的基本原理CPU與Cache之間的數(shù)據(jù)交換以字為單位Cache與主存之間的數(shù)據(jù)交換以塊為單位一個塊由若干個定長字組成2.Cache的基本原理CPU與Cache之間的數(shù)據(jù)交換以當CPU讀取主存中的一個字時，該字的主存地址被發(fā)給Cache和主存Cache控制邏輯依據(jù)地址判斷該字當前是否存在于Cache中若在，該字立即被從Cache傳送給CPU；若不在，則用主存讀周期把該字從主存讀出送到CPU同時把含有這個字的整個數(shù)據(jù)塊從主存讀出送到Cache中并采用一定的替換策略將Cache中的某一塊替換掉（替換算法由Cache管理邏輯電路來實現(xiàn)）當CPU讀取主存中的一個字時，該字的主存地址被發(fā)給CacheCache原理圖FLASH演示

按內(nèi)容尋址的相聯(lián)存儲器（表）用于存放與Cache中數(shù)據(jù)相對應(yīng)的主存地址可以快速檢索、判斷CPU讀取的某個字當前是否存在于Cache中Cache原理圖3.Cache的命中率基于程序訪問的局部性原理，增加Cache使要訪問的數(shù)據(jù)絕大多數(shù)都可在Cache中找到這樣才能在性能上使主存的平均讀出時間盡可能接近Cache的讀出時間Cache的工作效率通常用“命中率”來表示3.Cache的命中率基于程序訪問的局部性原理，命中率：CPU要訪問的信息在Cache中的概率Cache的命中率越高，CPU訪問主存的速度就越接近訪問Cache的速度通常Cache的容量越大，存儲的塊也越多，CPU的命中率就越高但是，當Cache的容量達到一定值時，命中率并不會隨著容量的增大而增加，而成本卻相應(yīng)增加所以，Cache的容量一般是命中率與成本價格的折中命中率：CPU要訪問的信息在Cache中的概率在一個程序執(zhí)行期間，設(shè)Nc表示Cache完成存取的總次數(shù)，Nm表示主存完成存取的總次數(shù)，h定義為命中率，則有若tc表示命中時的Cache訪問時間，tm表示未命中時的主存訪問時間，1-h表示未命中率，則Cache－主存系統(tǒng)的平均訪問時間ta為：設(shè)e表示訪問效率，則有為提高訪問效率e，命中率h越接近1越好在一個程序執(zhí)行期間，【例3-1】CPU執(zhí)行一段程序時，Cache完成存取的次數(shù)為1900次，主存完成存取的次數(shù)為100次，已知Cache存取周期為50ns，主存存取周期為250ns，求Cache－主存系統(tǒng)的效率和平均訪問時間?！窘狻縉c=1900，Nm=100，tc=50ns，tm=250ns∴ 命中率h=Nc/(Nc+Nm)=1900/(1900+100)=0.95

平均訪問時間ta =htc+(1-h)tm

=0.95×50+(1-0.95)×250=60ns

效率e=tc/ta=50/60=83.3%【例3-1】CPU執(zhí)行一段程序時，Cache完成存取的次數(shù)為3.4.2地址映射Cache的容量很小，保存的只是主存內(nèi)容的一個子集，且Cache與主存的數(shù)據(jù)交換是以塊為單位的為了把信息放到Cache中，必須應(yīng)用某種函數(shù)把主存地址定位到Cache中，這稱為地址映射CPU執(zhí)行程序時，會將程序中的主存地址變換成Cache地址，這個變換過程叫做地址變換假設(shè)某臺計算機主存容量為1MB，被分為2048塊，每塊512BCache容量為8KB，被分為16塊，每塊也是512B3.4.2地址映射Cache的容量很小，保存的只是主存內(nèi)容1.直接映射直接映射的Cache組織主存中的一個塊只能映射到Cache的某一特定塊中去主存的第0塊、第16塊、……、第2032塊，只能映射到Cache的第0塊主存的第1塊、第17塊、……、第2033塊，只能映射到Cache的第1塊……1.直接映射直接映射的Cache組織直接映射是最簡單的地址映射方式硬件簡單，成本低，地址變換速度快，不涉及替換算法不夠靈活，Cache的存儲空間得不到充分利用每個主存塊只有一個固定存放位置，容易產(chǎn)生沖突，使Cache效率下降，因此只適合大容量Cache采用如果一個程序需要重復(fù)引用主存中第0塊與第16塊，最好將主存第0塊與第16塊同時復(fù)制到Cache中但由于它們都只能復(fù)制到Cache的第0塊中去，即使Cache中別的存儲空間空著也不能占用因此這兩個塊會不斷交替裝入Cache，導致命中率降低直接映射是最簡單的地址映射方式2.全相聯(lián)映射全相聯(lián)映射的Cache組織主存中任何一塊都可以映射到Cache中的任何一塊位置上2.全相聯(lián)映射全相聯(lián)映射的Cache組織全相聯(lián)映射方式比較靈活，主存的各塊可以映射到Cache的任一塊中，Cache的利用率高塊沖突概率低只要淘汰Cache中的某一塊，即可調(diào)入主存的任一塊由于Cache比較電路的設(shè)計和實現(xiàn)比較困難，這種方式只適合于小容量Cache采用全相聯(lián)映射方式3.組相聯(lián)映射組相聯(lián)映射是直接映射和全相聯(lián)映射的折中方案主存和Cache都分組主存中一個組內(nèi)的塊數(shù)與Cache

中的分組數(shù)相同組間直接映射，組內(nèi)全相聯(lián)映射將Cache分成u組，每組v塊主存塊存放到哪個組是固定的至于存到該組哪一塊則是靈活的主存分為256組，每組8塊；Cache分為8組，每組2塊3.組相聯(lián)映射組相聯(lián)映射是直接映射和全相聯(lián)映射的折中方案組相聯(lián)映射方式主存中的各塊與Cache的組號之間有固定的映射關(guān)系但可自由映射到對應(yīng)Cache組中的任何一塊主存中的第0塊、第8塊……均映射于Cache的第0組，但可映射到Cache第0組中的第0塊或第1塊；主存的第1塊、第9塊……均映射于Cache的第1組，但可映射到Cache第1組中的第2塊或第3塊組相聯(lián)映射方式常采用的組相聯(lián)結(jié)構(gòu)Cache每組內(nèi)有2、4、8、16塊，稱為2路、4路、8路、16路組相聯(lián)Cache組相聯(lián)結(jié)構(gòu)Cache是前兩種方法的折中方案適度兼顧二者的優(yōu)點盡量避免二者的缺點得到普遍采用常采用的組相聯(lián)結(jié)構(gòu)Cache3.4.3替換策略Cache工作原理要求它盡量保存最新數(shù)據(jù)當從主存向Cache傳送一個新塊，而Cache中可用位置已被占滿時，就會產(chǎn)生Cache替換的問題替換問題與Cache的組織方式緊密相關(guān)：對直接映射Cache來說，只要把此可用位置上的主存塊換出Cache即可對全相聯(lián)和組相聯(lián)Cache來說，從若干可用位置中選取一個，把主存塊換出Cache3.4.3替換策略Cache工作原理要求它盡量保存最新數(shù)據(jù)1.最不經(jīng)常使用（LFU）算法LFU（LeastFrequentlyUsed，最不經(jīng)常使用）算法將一段時間內(nèi)被訪問次數(shù)最少的那個塊替換出去每塊設(shè)置一個計數(shù)器，從0開始計數(shù)，每訪問一次，被訪塊的計數(shù)器就增1當需要替換時，將計數(shù)值最小的塊換出，同時將所有塊的計數(shù)器都清零將計數(shù)周期限定在對這些特定塊兩次替換的間隔時間內(nèi)不能嚴格反映近期訪問情況新調(diào)入的塊很容易被替換出去1.最不經(jīng)常使用（LFU）算法LFU（LeastFreq2.近期最少使用（LRU）算法LRU（LeastRecentlyUsed，近期最少使用）算法把CPU近期最少使用的塊替換出去需要隨時記錄Ca