【正文】 第三章 存儲(chǔ)系統(tǒng) 2 主要內(nèi)容 存儲(chǔ)系統(tǒng)原理 虛擬存儲(chǔ)器 高速緩沖存儲(chǔ)器（ Cache） 三級(jí)存儲(chǔ)系統(tǒng) 3 體系結(jié)構(gòu)的改進(jìn) ? 馮 ?諾依曼機(jī)的改進(jìn)： ? 目的： 存放計(jì)算機(jī)系統(tǒng)中所需要處理的程序與數(shù)據(jù) 。 ? 主存儲(chǔ)器： 用以存放正在運(yùn)行的程序與數(shù)據(jù) 。 ? 輔助存儲(chǔ)器： 存放等待運(yùn)行的程序與數(shù)據(jù)。 ? 通用寄存器組： 是存放那些最經(jīng)常用到的數(shù)據(jù)。 ? 存儲(chǔ)系統(tǒng)： 兩個(gè)或兩個(gè)以上的速度、容量、價(jià)格不同的存儲(chǔ)器采用硬件，軟件或軟、硬件結(jié)合的辦法聯(lián)接成一個(gè)系統(tǒng)。 運(yùn)算器為中心 存儲(chǔ)器為中心 4 存儲(chǔ)系統(tǒng)原理 第一層 第二層 第三層 第四層 第五層 存儲(chǔ)系統(tǒng)中的存儲(chǔ)部件與關(guān)系 速 度 提 高 容 量 增 加 通用寄存器 M1 高速緩沖存儲(chǔ)器 M2 主存儲(chǔ)器 M3 脫機(jī)大容量存儲(chǔ)器 M5 輔助存儲(chǔ)器 M4 5 計(jì)算機(jī)存儲(chǔ)系統(tǒng) 三個(gè)基本參數(shù) ? 存儲(chǔ)容量 S： 以字節(jié)數(shù)表示，單位為 B、 KB、 MB、 GB、 TB等。 ? 存儲(chǔ)器速度 T： 存儲(chǔ)器訪問周期。 ? 存儲(chǔ)器價(jià)格 C： 表示單位容量的平均價(jià)格。 6 存儲(chǔ)系統(tǒng)的目標(biāo) ? 目標(biāo)：大容量；高速度；低價(jià)格 ? 存儲(chǔ)系統(tǒng)中存儲(chǔ)器件現(xiàn)狀： ? 與 CPU速度相比，存儲(chǔ)器速度較低，目前已成為計(jì)算機(jī)系統(tǒng)速度性能瓶頸。 ? 當(dāng)前電子技術(shù)發(fā)展，存儲(chǔ)器器件有： （ 1）容量越大，速度越低，反之亦然； （ 2）速度越高，價(jià)格越高； 7 存儲(chǔ)系統(tǒng)的層次結(jié)構(gòu) ? 距離 CPU越近的存儲(chǔ)器容量越小，速度越高。 ? 最常使用的數(shù)據(jù)在 M1中，其次在 M2中，依 次類推，最少使用數(shù)據(jù)在 Mn中?？拷?CPU存儲(chǔ)器中的數(shù)據(jù)一般是其下一層存儲(chǔ)器中數(shù)據(jù)的子集。 CPU M1 M2 Mn 8 存儲(chǔ)系統(tǒng)的基本特征 ? 包含性： 在小容量的存儲(chǔ)器中，一定能在較大容量存儲(chǔ)器中找到所存信息的副本。 ? 一致性： 當(dāng)副本被修改，要求各存儲(chǔ)器保持同一信息的一致性。 9 存儲(chǔ)系統(tǒng)設(shè)計(jì) ? 存儲(chǔ)系統(tǒng)的設(shè)計(jì)目標(biāo)： M1的速度， Mn的容量和價(jià)格。 ? 層次存儲(chǔ)系統(tǒng)的設(shè)計(jì)依據(jù)： 程序局部性原理。 ? 層次存儲(chǔ)系統(tǒng)的工作過程： CPU訪存時(shí)，首先訪問 M1 ，若不能發(fā)現(xiàn)所需數(shù)據(jù)，進(jìn)而訪問 M2，并把所需數(shù)據(jù)調(diào)入 M1。若仍不能發(fā)現(xiàn)數(shù)據(jù)，接著訪問 Mi，依次類推，直至 Mn。 10 層次結(jié)構(gòu)存儲(chǔ)器的應(yīng)用（ 1） ? CACHE—主存儲(chǔ)器結(jié)構(gòu) 為了提高主存速度，使主存和 CPU速度匹配。一般用硬件實(shí)現(xiàn)。 CPU Cache 主存 輔助硬件 11 層次結(jié)構(gòu)存儲(chǔ)器的應(yīng)用（ 2） ? 主存儲(chǔ)器 —輔助存儲(chǔ)器結(jié)構(gòu) 為了彌補(bǔ)主存的容量不足 ,采用虛擬存儲(chǔ)技術(shù)。用軟件或軟件和硬件結(jié)合的方法實(shí)現(xiàn)。 CPU 主存 輔存 輔助軟硬件 12 層次存儲(chǔ)器性能參數(shù)（二層結(jié)構(gòu)） ? 設(shè)存儲(chǔ)系統(tǒng)的二個(gè)層次為： M1和 M2， M1和 M2的容量為： S S2 訪存時(shí)間為： T T2 每位價(jià)格為： C C2 ? 平均價(jià)格為： ? 當(dāng) S1S2時(shí)， C=C2。 212211ssscscc???13 層次存儲(chǔ)器性能參數(shù)（二層結(jié)構(gòu)） ? 命中率 H： (CPU訪問存儲(chǔ)系統(tǒng)時(shí)，在 M1中找到所需數(shù)據(jù)的概率。 設(shè)訪問 M1和 M2的次數(shù)為 N1和 N2,則： ? 不命中率 或 失效率 F為在 M1中不能發(fā)現(xiàn)所需數(shù)據(jù)的概率： F = 1H 211NNNH??14 層次存儲(chǔ)器性能 ? 一級(jí) Cache的不足： ? 其命中率不可能達(dá)到要求的 。 ? 多級(jí) Cache：通常采用兩級(jí)或三級(jí) Cache。 ? 如通用寄存器等，提高數(shù)據(jù)的重復(fù)利用率。 ? 實(shí)際應(yīng)用中還是很難滿足需求。 15 預(yù)取技術(shù) ? 不命中時(shí)，在數(shù)據(jù)從主存中取出送往 CPU時(shí)，把主存中臨近幾個(gè)單元的數(shù)據(jù)（稱為一個(gè)數(shù)據(jù)塊）取出送入 CPU。利用了程序的局部性原理。 ? 設(shè) n： Cache的塊大小與數(shù)據(jù)塊重復(fù)使用次數(shù)的乘積， H：原來的命中率， H?：采用預(yù)取技術(shù)后的命中率。 ? 如 Cache塊大小為 4個(gè)字，預(yù)取到 Cache中的數(shù)據(jù)的重復(fù)利用率為 5次， Cache原來的命中率為 ，那么采用預(yù)取之后的命中率 H?為 。 nnHH139。???16 頻帶平衡 ? 頻帶寬度： 單位時(shí)間內(nèi)所能訪問的數(shù)據(jù)量。 ? 問題：存儲(chǔ)器與 CPU的訪問速度不匹配。存儲(chǔ)器訪問的速度能否跟上系統(tǒng)的要求，是影響整個(gè)計(jì)算機(jī)系統(tǒng)性能的極為重要的關(guān)鍵問題，也是系統(tǒng)結(jié)構(gòu)設(shè)計(jì)者的主要問題。 ? 有三種途徑來解決這個(gè)問題： ? 多個(gè) 存儲(chǔ)器并行工作 ： 并行 訪問和 交叉 訪問 ? 設(shè)置各種 緩沖存儲(chǔ)器 ：如先行緩沖棧，包括預(yù)取指令緩沖棧、操作數(shù)先行緩沖棧等 ? 采用 存儲(chǔ)系統(tǒng) ：如 Cache存儲(chǔ)系統(tǒng) 17 并行訪問存儲(chǔ)器 ? 基本思路：通過設(shè)置多個(gè)存儲(chǔ)模塊，使在一個(gè)存取周期內(nèi)可以訪問多個(gè)數(shù)據(jù)，以此提高存儲(chǔ)器的速度。 ? 三種方法實(shí)現(xiàn)并行存儲(chǔ)器： ? 并行訪問存貯器 ? 交叉訪問存儲(chǔ)器 ? 無訪問沖突存儲(chǔ)器 18 并行訪問存儲(chǔ)器 數(shù)據(jù)寄存器 數(shù)據(jù)總線 地址總線 地址寄存器 體號(hào) W W1 W2 W3 W4 m1 m2 m3 m4 b a 體內(nèi)地址 地址寄存器中 高位部分 作為 模塊地址 ，同時(shí)訪問多個(gè)存儲(chǔ)模塊。若干位 低位地址 進(jìn)行 多路選擇 。 19 并行訪問存儲(chǔ)器 ——評(píng)價(jià) ? 優(yōu)點(diǎn)： 簡(jiǎn)單、容易。 ? 缺點(diǎn)： 訪問的沖突大。 ? 主要沖突： ? 取指令沖突（條件轉(zhuǎn)移，轉(zhuǎn)移成功，隨后取出指令無用） ? 讀操作數(shù)沖突（需要的多個(gè)操作數(shù)不一定都存放在同一個(gè)存儲(chǔ)字中，否則可能需要多次讀出） ? 寫數(shù)據(jù)沖突（必須湊齊 n個(gè)數(shù)才一起寫入存儲(chǔ)器，否則影響頻帶寬度） ? 讀寫沖突（要讀出的一個(gè)字和要寫入的一個(gè)字處在同一個(gè)存儲(chǔ)字內(nèi)時(shí)，無法在一個(gè)存儲(chǔ)周期內(nèi)完成）。 20 多體并行交叉訪問存儲(chǔ)器 模 M主存儲(chǔ)器： 分為 M個(gè)存儲(chǔ)體的主存儲(chǔ)器。 同時(shí)訪問： 采取同時(shí)啟動(dòng)，完全并行工作的方式； 交叉訪問： 分時(shí)啟動(dòng)，互相錯(cuò)開一個(gè)存儲(chǔ)體存儲(chǔ)周期的1/M，交叉進(jìn)行工作。 四個(gè)存儲(chǔ)體交叉訪問的時(shí)間關(guān)系 m=4 分時(shí)啟動(dòng)時(shí)間圖 主存周期 主存周期 啟動(dòng) 0體 啟動(dòng) 1體 啟動(dòng) 2體 啟動(dòng) 3體 21 高位交叉訪問存儲(chǔ)器 低位部分：體內(nèi)地址 b=log2n 高位部分：存儲(chǔ)體體號(hào) a=log2m m: 體數(shù) n：每個(gè)體的容量 主要目的：擴(kuò)大容量 W MDR0 0 1 2 3 … n1 MDR1 n n+1 n+2 n+3 … 2n1 MAR0 MAR3 MDRm1 n(m1) n(m1)+1 n(m1)+2 n(m1)+3 … n(m1) MARm1 譯碼 a b 22 低位交叉訪問存儲(chǔ)器 低位交叉存儲(chǔ)器結(jié)構(gòu) 低位部分：存儲(chǔ)體體號(hào) b=log2m 高位部分：體內(nèi)地址 a=log2n W MDR0 0 m 2m 3m … (n1)m MDR1 1 m+1 2m+1 3m+1 … (n1)m+1 MAR0 MAR3 MDRm1 m1 2m1 3m1 4m1 … nm1 MARm1 譯碼 a b 分時(shí) 訪問 23 例： n=8 m=4多體并行低位交叉編址 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 b a 4個(gè)體并行 24 低位交叉訪問存儲(chǔ)器 ——分析 ? 采用低位交叉訪問方式工作的 RAM 實(shí)際上是一 種流水工作方式。 ? 采用低位交叉訪問存貯器能夠大幅度地提高 主存的速度。 ? 并行存取效率： 背景：由于存在訪問沖突或無效的情況（主要是由于 jmp指令引起），因此主存的存取速度 Tm 不是隨存儲(chǔ)器的個(gè)數(shù)增加而線性提高的。例如，在CDC6600中，采用了 32個(gè) RAM體，但只比單個(gè)存儲(chǔ)體訪問速度提高了 10 倍左右。 25 轉(zhuǎn)移概率與并行存儲(chǔ)器 ? 設(shè) k為每個(gè)存儲(chǔ)周期能讀取的有效字?jǐn)?shù)， n個(gè)存儲(chǔ)體無沖突訪問時(shí)， k=n，完全沖突， n=1。 N為每個(gè)存儲(chǔ)周期能讀取的平均有效字?jǐn)?shù)。 ? 設(shè)并行存儲(chǔ)器有 n個(gè)存儲(chǔ)體組成，又 P(1)為表示第一條指令為轉(zhuǎn)移指令的概率， P(2)為 … P(n)為 … 的的概率。試求 N？ ? N又稱為加速倍數(shù)。 ????nkkPkN1)(設(shè)：26 轉(zhuǎn)移概率與并行存儲(chǔ)器 ? 定義： 程序轉(zhuǎn)移概率 g—表示讀出的指令為轉(zhuǎn)移指令且轉(zhuǎn)移成功的概率。 ? 設(shè) p(1)=g；表示讀出的第一條指令為轉(zhuǎn)移指令的概率。 ? p(2)、 P(3)、 …… )1,2,1( )1()( 2)1())2()1(1()3()1())1(1()2(1???????????????????nkggkPgggPPPgggPPk???27 轉(zhuǎn)移概率與并行存儲(chǔ)器 ???????????????nknnnggkpkNgggnP111)1(1)( )1()1()( 即? 當(dāng) k=n時(shí)，表示從前 n1個(gè)存儲(chǔ)體中讀出的都不是轉(zhuǎn)移指令，或轉(zhuǎn)移不成功，則當(dāng) k=n時(shí)，不管是否為轉(zhuǎn)移指令，都將為 n。 ? 當(dāng) g=0時(shí)，表示讀出的幾條指令都不是轉(zhuǎn)移指令，此時(shí) N=n。 ? 當(dāng) g=1時(shí)，表示第一條指令即為轉(zhuǎn)移指令，此時(shí)N=1，為單體。 28 轉(zhuǎn)移概率與并行存儲(chǔ)器 2468101214160 ggNn)1(1 ???轉(zhuǎn)移概率 gn 轉(zhuǎn)移概率 g和并行存貯存貯體 n 間的關(guān)系 一般地取 n=8時(shí)，效果良好。因?yàn)槌绦虻?g一般為 ～ 。 29 無訪問沖突存儲(chǔ)器 ? 低位交叉訪問效率低的原因：存在訪問沖突。 ? 程序中有轉(zhuǎn)移指令； ? 數(shù)據(jù)的隨機(jī)性。 ? 關(guān)于多維數(shù)組的無沖突訪問存儲(chǔ)器：例子見下頁。 ? 解決方法 ①避免數(shù)據(jù)訪問的沖突； ②將存儲(chǔ)體的個(gè)數(shù)設(shè)為質(zhì)數(shù)，以實(shí)現(xiàn)數(shù)據(jù)訪問時(shí)位移量和互質(zhì)。 30 多維數(shù)組的無訪問沖突存儲(chǔ)器 按列訪問有沖突的存儲(chǔ)方案 0號(hào)體