《計算機系統(tǒng)結(jié)構(gòu)》PPT課件.ppt

計算機系統(tǒng)結(jié)構(gòu) 由趙斯琴制作 參考教材 徐煒民 嚴允中編著 計算機系統(tǒng)結(jié)構(gòu) 第3版 電子工業(yè)出版社 教材講述了計算機系統(tǒng)結(jié)構(gòu)的基本概念 設(shè)計原理和分析方法 第一章計算機系統(tǒng)結(jié)構(gòu)設(shè)計基礎(chǔ) 1 1計算機系統(tǒng)結(jié)構(gòu)的含義和分類計算機系統(tǒng)性能有了提高 但價格下降 原因 器件技術(shù)不斷發(fā)展 系統(tǒng)結(jié)構(gòu)的改進 其中計算機系統(tǒng)結(jié)構(gòu)的改進對性能的提高有著不容忽視的作用 1 1 1計算機系統(tǒng)結(jié)構(gòu)的含義G M Amdahl指出 計算機系統(tǒng)結(jié)構(gòu)是指程序設(shè)計員所看到的計算機的基本屬性 即概念性結(jié)構(gòu)和功能特性 是計算機系統(tǒng)結(jié)構(gòu)的外特性 從計算機系統(tǒng)的層次結(jié)構(gòu)上考慮 不同級的程序設(shè)計者所看到計算機屬性是不一樣的 用虛擬計算機觀點定義計算機系統(tǒng)的功能層次 系統(tǒng)總體分析 計算機系統(tǒng)結(jié)構(gòu)的外特性包含的內(nèi)容 指令系統(tǒng)數(shù)據(jù)表示尋址方式寄存器構(gòu)成定義中斷系統(tǒng)存儲體系和管理I O系統(tǒng)機器工作狀態(tài)的定義和切換信息保護 計算機系統(tǒng)結(jié)構(gòu)的內(nèi)部特性 計算機組成 內(nèi)部特性是由硬件和固件實現(xiàn)的 也稱為計算機組成 是計算機系統(tǒng)結(jié)構(gòu)的邏輯實現(xiàn) 包括機器內(nèi)的數(shù)據(jù)通道和控制信號的組成及邏輯設(shè)計 著重于機器級內(nèi)各事件的時序方式與控制機構(gòu) 各部件功能及相互聯(lián)系 計算機實現(xiàn)是指計算機組成的物理實現(xiàn) 包括處理器 主存部件的物理結(jié)構(gòu) 器件的集成度和速度的確定 芯片 模塊 插件 底板的劃分與連接 微組裝及整機裝配技術(shù) 專用芯片的設(shè)計以及信號傳輸 電源 冷卻方法等 例如 指令系統(tǒng)功能的確定屬于系統(tǒng)結(jié)構(gòu)的外特性 而指令的實現(xiàn) 如取指 取操作數(shù) 運算 送結(jié)果等具體操作及其時序?qū)儆诮M成 而實現(xiàn)這些指令功能的具體電路 器件設(shè)計及裝配技術(shù)等屬于實現(xiàn) 1 1 2計算機系統(tǒng)結(jié)構(gòu)的分類 由于計算機系統(tǒng)的基本工作過程是執(zhí)行一條指令的序列 對一組數(shù)據(jù)進行處理 因此Michael J Flynn提出按指令流和數(shù)據(jù)流的多倍性對計算機系統(tǒng)結(jié)構(gòu)分類 指令流 機器執(zhí)行的指令序列 數(shù)據(jù)流 由指令流調(diào)用的數(shù)據(jù)序列 多倍性 在系統(tǒng)中最受限制的部件上 同時處于同一執(zhí)行階段的指令或數(shù)據(jù)的最大個數(shù) 按Flynn分類方法分為 單指令流單數(shù)據(jù)流 SISD 單指令流多數(shù)據(jù)流 SIMD 多指令流單數(shù)據(jù)流 MISD 多指令流多數(shù)據(jù)流 MIMD SISD結(jié)構(gòu) 只要指令部件一次只對一條指令進行譯碼并且只對一個執(zhí)行部件分配數(shù)據(jù) 可以有多個存儲體和多個執(zhí)行部件 可以是流水線的 可以有一個以上功能部件 所有功能部件均由一個控制部件管理 SIMD結(jié)構(gòu) 以并行處理機 陣列處理機 為代表 同一個控制部件管理下 由多個處理單位PU 所有PU均接受從控制部件來的同一條指令 操作對象是來自不同數(shù)據(jù)流的數(shù)據(jù)組 MISD結(jié)構(gòu) 宏流水線中 每個處理器的結(jié)果是下一個處理器的輸入操作數(shù) MIMD結(jié)構(gòu) 大多數(shù)多處理機系統(tǒng)和多計算機系統(tǒng)可以歸為這一類 多處理機之間有相互作用 因為所有數(shù)據(jù)來自所有處理機共享的同一個空間 用最大并行度分類 美籍華人馮澤云 Tse yunFeng 提出用最大并行度對計算機系統(tǒng)進行分類最大并行度Pm是指計算機系統(tǒng)在單位時間內(nèi)能夠處理的最大二進制位數(shù) 最大并行度Pm n m n表示同時處理時一個字中的二進制位數(shù) m表示能同時處理的字數(shù) 按計算機對數(shù)據(jù)處理方式 則Pm值有下列4種類型 字串位串 WSBS n 1 m 1字串位并 WSBP n 1 m 1字并位串 WPBS n 1 m 1 即位片處理 字并位并 WPBP n 1 m 1 即全并行處理 按 并行級 和 流水線 分類 WolfgangHandler根據(jù)計算機系統(tǒng)硬件結(jié)構(gòu)的并行程度和流水線處理程度進行分類 著重于處理器控制部件 PCU 算術(shù)邏輯部件 ALU 和位級電路 BLC 的并行 流水線處理 PCU可視作一個處理機或一個CPU ALU相當于SIMD的處理單元 PE BLC對應(yīng)于在ALU中進行一位運算所需的組合邏輯電路 一個計算機系統(tǒng)C可由6個獨立項目組成的三元組描述為如下 T C K K D D W W K為PCU數(shù) K 為可組成流水線的PCU數(shù) D為ALU 或PE 數(shù) D 為可組成流水線的ALU數(shù) W為ALU 或PE 的字長 W 為一個ALU 或PE 中的流水線段數(shù) 1 2計算機系統(tǒng)的設(shè)計方法 1 2 1軟 硬件取舍的基本原則系統(tǒng)結(jié)構(gòu)設(shè)計的主要任務(wù)是進行軟 硬件功能分配和給用戶提供機器級軟硬界面 相同功能可以設(shè)計成軟件或硬件把功能設(shè)計成硬件時 可以提高運算速度 減少存儲容量 但提高硬件成本降低硬件利用率和系統(tǒng)的靈活性和適應(yīng)性 把功能設(shè)計成軟件時 可以降低硬件成本 提高系統(tǒng)的靈活性和適應(yīng)性 但運算速度會下降 存儲容量要增大 軟件研發(fā)費用增加 因此 軟 硬功能分配比例應(yīng)該考慮現(xiàn)有的硬件和芯片條件下 爭取系統(tǒng)有高的性能和價格比 1 2 2計算機系統(tǒng)設(shè)計的定量原則 1 加快經(jīng)常性事件的速度最重要的也是最廣泛采用的設(shè)計原則 加快處理頻繁出現(xiàn)事件對系統(tǒng)的影響比加速處理很少出現(xiàn)事件的影響大 2 Amdahl定律 系統(tǒng)中對某一部件采用某種更快執(zhí)行方式所能獲得的系統(tǒng)性能改進程度 取決于這種方式被使用頻率 或所占總執(zhí)行時間的比例 Amdahl定義了加速比Te To為采用某種增強功能措施后完成某一任務(wù)所需時間和不采用任何增強功能措施完成同一任務(wù)所需時間 fe為可采用增強功能措施的部分所占百分比Re采用增強功能措施比不采用增強功能可加快執(zhí)行的倍數(shù) 例 若考慮將系統(tǒng)中某一功能的處理速度加快10倍 但該功能的處理使用時間僅為整個系統(tǒng)運行時間的40 則采用此增強功能方法后 能使整個系統(tǒng)性能提高多少 fe 40 re 10Sp 1 1 0 4 0 4 10 1 56 設(shè)求浮點數(shù)平方根FPSQR的操作占整個測試程序執(zhí)行時間的20 一種實現(xiàn)方法是采用FPSQR硬件 使其速度加快10倍 另一種實現(xiàn)方法是使用所有浮點數(shù)指令FP速度加快2倍 同時設(shè)FP指令占整個程序執(zhí)行時間的50 請比較兩種實現(xiàn)方法的優(yōu)劣 3 CPU性能公式 CPU性能取決于3個要素 時鐘頻率f 每條指令時鐘周期數(shù)和指令條數(shù)IC 時鐘周期T 1 f CPU時間 CPU時鐘周期總數(shù) 時鐘周期T若Ii是i指令在程序中的條數(shù) CPIi為i指令的平均時鐘周期 n為程序中指令的種類數(shù) 可以把CPU時間表示為 每條指令平均時鐘周期數(shù)CPI CPU時鐘周期總數(shù) 指令條數(shù)IC經(jīng)代換 可得CPU時間 CPI IC T例 假設(shè)有兩臺機器A和B 對條件轉(zhuǎn)移采用不同的方法 CPUA采用比較指令和條件轉(zhuǎn)移指令處理方法 CPUB采用比較指令和條件轉(zhuǎn)移指令合一方法 在CPUA上 若條件轉(zhuǎn)移指令占總執(zhí)行指令數(shù)的20 比較指令也占20 CPUB的時鐘周期比CPUA慢25 若規(guī)定兩臺機器執(zhí)行條件轉(zhuǎn)移指令需2T 其它指令需要1T 現(xiàn)比較CPUA和CPUB哪個工作速度更快 解 CPU時間 CPI IC TCPIA 20 2 80 1 1 2CPUA時間 CPIA ICA TA 1 2 ICA TA在B內(nèi) ICB ICA 20 ICA 80 ICA轉(zhuǎn)移指令的比重是 20 ICA 80 ICA 25 其它指令比重是1 25 75 CPIB 25 2 75 1 1 25TB 1 25 TACPUB時間 CPIB ICB TB 1 25 0 8 ICA 1 25 TA 1 25 ICA TACPUA時間 CPUB時間若CPUB的條件轉(zhuǎn)移指令比CPUA慢25 比較CPUA和CPUB哪個工作速度更快 除了CPU時間之外 MIPS 每秒百萬次指令 和MFLOPS 每秒百萬次浮點運算 也是比較常用的計算機性能評估標準 ICF表示浮點運算次數(shù) 4 程序訪問的局部性原理 程序訪問的局部性是指程序執(zhí)行中 呈現(xiàn)出頻繁重新使用那些最近已被使用過的數(shù)據(jù)和指令的規(guī)律 統(tǒng)計表明一個程序執(zhí)行時間中的90 是花費在10 的程序代碼上 主要反映在時間和空間局部性兩個方面 它是按層次構(gòu)成存儲體系的主要依據(jù) 1 2 3計算機系統(tǒng)設(shè)計的任務(wù) 1 確定用戶對計算機系統(tǒng)功能 價格和性能的要求功能要求有 應(yīng)用領(lǐng)域 專用還是通用軟件兼容層次 如 在程序設(shè)計語言層次 只需要有新的編譯器 在目標代碼層次 則系統(tǒng)完全確定 像系列機操作系統(tǒng)要求標準 數(shù)據(jù)表示 接口 總線 網(wǎng)絡(luò)等等標準2 軟件和硬件的平衡3 符合未來發(fā)展方向 1 2 4計算機系統(tǒng)的設(shè)計步驟 計算機系統(tǒng)從概念上和功能上可看做是一個多級構(gòu)成的層次結(jié)構(gòu) 從哪個層開始設(shè)計 對設(shè)計步驟是有影響的 通常有3種不同的設(shè)計思路 由上往下 由下往上 由中間開始 系統(tǒng)結(jié)構(gòu)設(shè)計步驟如下 1 需求分析2 需求說明3 概念設(shè)計4 具體設(shè)計5 設(shè)計優(yōu)化和評價 1 3計算機系統(tǒng)結(jié)構(gòu)的發(fā)展 VonNeumann結(jié)構(gòu)改進的VonNeumann結(jié)構(gòu)器件發(fā)展對系統(tǒng)結(jié)構(gòu)的影響應(yīng)用對系統(tǒng)結(jié)構(gòu)的影響軟件 算法對系統(tǒng)結(jié)構(gòu)的影響 計算機系統(tǒng)結(jié)構(gòu)的演變 第2章數(shù)據(jù)表示和指令系統(tǒng) 2 1數(shù)據(jù)表示數(shù)據(jù)類型是指一組值的集合及其上實施的操作的集合 數(shù)據(jù)表示指的是能由硬件直接辨認的數(shù)據(jù)類型 數(shù)據(jù)結(jié)構(gòu)是指結(jié)構(gòu)數(shù)據(jù)類型的組織方式 它反映了在應(yīng)用中所用到的各種數(shù)據(jù)元素或信息單元之間的結(jié)構(gòu)關(guān)系 數(shù)據(jù)結(jié)構(gòu)要經(jīng)過軟件映像 變換成按地址訪問一維存儲器內(nèi)的各種數(shù)據(jù)表示 計算機的數(shù)據(jù)表示如何確定是一個復(fù)雜的問題 基本的數(shù)據(jù)類型有邏輯 布爾 數(shù) 定點數(shù) 整數(shù) 浮點數(shù) 實數(shù) 十進制數(shù) 字符串 數(shù)組等 對這些基本數(shù)據(jù)類型有碼制的選擇 如原碼 反碼 補碼 移碼等 以及基值 位長等 關(guān)系到硬件實現(xiàn)的難易程度和數(shù)據(jù)表示范圍以及數(shù)據(jù)表示的精度等問題 除了基本的數(shù)據(jù)表示之外 數(shù)據(jù)表示的確是關(guān)系到軟 硬件的分配問題 例1 假設(shè)正階 正尾數(shù)浮點數(shù)的表示為如下圖階碼相同 均為二進制 尾數(shù)基值rm 2和rm 16兩種不同值時 浮點數(shù)的表示范圍不同 采用規(guī)格化表示 最小階碼為0 最大階碼為22 1 3 rm 2時 最小尾數(shù)為2 1 最大尾數(shù)為1 2 4 正浮點數(shù)的表示范圍是20 2 1到23 1 2 4 rm 16時 4位2進制數(shù)組成一個16進制數(shù) 最小尾數(shù)為16 1 最大尾數(shù)為1 16 1 正浮點數(shù)的表示范圍是160 16 1到163 1 16 1 浮點數(shù)的下溢處理 尾數(shù)下溢主要產(chǎn)生于加法中的對階 規(guī)格化右移以及在乘法中的取單倍長度的乘積 常用的處理方法有 截斷舍入法恒置 1 法ROM或PLA舍入法 又稱查表舍入法 例2 衡量某種數(shù)據(jù)表示的是否合適 首先要看這種數(shù)據(jù)表示對完成任務(wù)時間和所需存儲容量的影響 假設(shè)有兩個200 200元素 定點數(shù) 的陣列A和B進行相加運算 若用PL 1語言僅需一條語句 經(jīng)優(yōu)化編譯形成6條機器指令 其中4條需要循環(huán)40000次 若機器有陣列型數(shù)據(jù)表示 則只需要1條機器指令就能完成2個矩陣的相加 衡量某種數(shù)據(jù)表示的是否合適 還要看其通用性和利用率 2 2指令及其優(yōu)化 指令系統(tǒng)是計算機所有指令的集合 程序員用各種語言編寫的程序都要翻譯成 編譯或解釋 以指令形式表示的機器語言后才能運行 它是反映了計算機的基本功能 是硬件設(shè)計人員和程序設(shè)計人員都能見到的機器的主要屬性 指令由地址碼和操作碼組成 隨著指令類型的不同 對地址碼的長度要求變化很大 同一個計算機中 可以有1Byte 2Byte 3Byte 4Byte等多種長度的指令 指令優(yōu)化 指令格式的優(yōu)化指的是如何用最短的位數(shù)來表示指令的操作信息和地址信息 使程序中指令的平均字長最短 因此指令格式的優(yōu)化包括操作碼的優(yōu)化和地址碼的優(yōu)化兩部分 2 2 1操作碼的優(yōu)化 操作碼的表示方法通常有三種 等長操作碼 Huffman編碼法和擴展編碼法 下面分別介紹 等長操作碼對于采用等長操作碼的指令系統(tǒng) 若指令系統(tǒng)中共有N種不同功能的指令 則指令系統(tǒng)中的所有指令的操作碼長度固定為 log2N 位 等長操作碼的操作碼長度規(guī)整 有利于簡化硬件設(shè)計 減少指令譯碼時間 如IBM370指令系統(tǒng) 指令操作碼的長度固定為8位 從壓縮代碼的觀點出發(fā) 希望常用指令的操作碼短些 用哈夫曼 Huffman 碼制壓縮的基本概念 出現(xiàn)概率最大的指令用最少的位來表示 而概率較小的指令用較多的位來表示 達到使平均位數(shù)縮短的目的 要采用Huffman編碼法表示操作碼 必須先知道各種指令在程序中出現(xiàn)的概率 這通?？梢酝ㄟ^對已有典型程序進行統(tǒng)計得到 例 現(xiàn)設(shè)有一臺模型機 共有10種不同功能的指令 各指令的使用頻度如表2 1所示 若用等長的操作碼表示需用4位 用哈夫曼壓縮概念進行編碼的步驟 1 將要編碼的指令按出現(xiàn)概率的次序排列 頻率相同的指令可任意排列 2 把出現(xiàn)概率小的兩個指令合并 并將其頻率相加 按相加后的頻率次序重新排序 3 繼續(xù) 2 的過程 直至只剩下兩個頻率 4 對最后兩個頻率分別指定代碼0和1 或1和0 5 若某一頻率由兩個頻率相加而成 則分別指定這兩個頻率的下一個代碼為0和1 或1和0 6 繼續(xù) 5 的過程 直到所有指令均已指定不同代碼為止 舉例說明哈夫曼編碼 哈夫曼樹 將所有的指令按頻率由小到大排序 每次選擇其中最小的兩個頻率合并成 求和 一個新的結(jié)點 然后把它作為葉結(jié)點 一個新的結(jié)點和其它的葉結(jié)點再按頻率大小排序 如此重復(fù) 直至全部頻率都處理完畢最后形成一個頻率為1的根結(jié)點 此后 由根結(jié)點開始向下延伸 對兩個分支分別用一位 1 或 0 或相反 來表示 直至遍歷所有的葉結(jié)點為止 把上述例子用哈夫曼數(shù)編碼 如下圖 構(gòu)造的Huffman樹以及各指令的Huffman編碼均不是唯一的 但采用Huffman編碼的操作碼的平均長度是唯一的 pi li 0 17 2 0 15 0 15 0 13 0 12 3 0 09 0 08 0 07 4 0 03 0 01 5 3 15位 擴展哈夫曼碼 為了使指令操作碼規(guī)整 用擴展哈夫曼碼 Huffman編碼法是最優(yōu)化的編碼方法 但這種編碼方法形成的操作碼很不規(guī)整 10種指令就有4種不同的操作碼長度 既不便于譯碼 也不實用 所以 在此基礎(chǔ)上再結(jié)合采用等長操作碼的編碼方法 可以得到擴展操作碼編碼 擴展操作碼編碼是介于等長操作碼編碼和Huffman編碼之間的一種編碼方式 使操作碼的長度只限于有限的幾種碼長 如這里只有兩種碼長 為便于實現(xiàn)和分級譯碼 一般采用等長擴展 把上述例子用擴展哈夫曼數(shù)編碼 若采用2 4等長擴展操作碼編碼 其操作碼的平均碼長為 pi li 0 17 0 15 2 0 15 0 13 0 12 0 09 0 08 0 07 0 03 0 01 4 3 36位 比較一下3種編碼方式 即直接用二進制編碼 哈夫曼編碼方式 擴展哈夫曼編碼方式的操作碼的平均長度 不同的擴展標志 對于等長擴展碼 根據(jù)采用不同的擴展標志還可以有多種不同的擴展方法 例如 對于4 8 12位擴展碼 有采用每次保留一個碼點標志的15 15 15編碼法 也有采用每次保留一個標志位的8 64 512編碼法 2 2 2地址碼的優(yōu)化 只是有了操作碼的優(yōu)化表示 而沒有在地址碼表示和尋址方式方面采取相應(yīng)的措施 程序所需總位數(shù)還是難以減少的 如果主存是按位編址 操作碼的優(yōu)化表示會直接帶來程序所需總位數(shù)的減少 然而 有些指令卻需2個主存周期才能讀出 這會使機器速度明顯下降 為了不降低訪存取指令的速度 就要維持指令字按整數(shù)邊界存貯 那么如何發(fā)揮操作碼優(yōu)化表示的作用呢 顯然只有地址也是可變長的 才能用得上空白部分 如圖所示 若要充分利用空白浪費空間 就必須對地址碼部分進行優(yōu)化 地址碼的優(yōu)化有四種方法 不允許指令字跨邊界存儲 配合操作碼長度調(diào)整地址碼長度 改變指令中地址碼長度和地址數(shù) 設(shè)計單地址 雙地址 三地址指令 設(shè)法利用指令中空白處 存放立即數(shù)或常數(shù) 例 一臺模型機共有7條指令 各指令的使用頻度分別為35 25 20 10 5 3 2 該模型機有8位和16位兩種指令字長 采用2 4擴展操作碼 8位字長指令為寄存器 寄存器 R R 二地址類型 16位字長指令為寄存器 存儲器 R M 二地址變址尋址 128 變址范圍 127 類型 1 設(shè)計該機的兩種指令格式 標出各字段位數(shù)并給出操作碼編碼 2 該機允許使用多少個可編址的通用寄存器 多少個變址寄存器 3 計算操作碼的平均碼長 解 1 7條指令的2 4擴展操作碼編碼如表所示 為了加快使用頻率高的指令的執(zhí)行速度 設(shè)計時 讓操作碼長度只有2位的3條指令的操作在通用寄存器之間進行 而其它的指令則在寄存器和存儲器之間進行 由于R R型指令長度為8位 操作碼占2位 因此源 目的寄存器編碼部分各占3位 其格式如下 R R型 2位3位3位 由變址尋址的位移量范圍 128 127 可知 R M型指令格式中偏移地址占8位 由于操作碼占4位 源寄存器編碼占3位 R M型指令長度為16位 因此變址寄存器的編碼只占1位 R M型指令格式如下 R M型 4位3位1位8位 2 根據(jù) 1 中設(shè)計的指令格式 通用寄存器編碼占3位 變址寄存器編碼占1位可知 該機允許使用8個可編址的通用寄存器和2個變址寄存器 3 根據(jù)表2 4可計算操作碼的平均碼長為 pi li 0 35 0 25 0 2 2 0 1 0 05 0 03 0 02 4 2 4位 2 2 1尋址方式分析 尋址是指如何確定數(shù)據(jù)地址和轉(zhuǎn)移指令的下一條要執(zhí)行的指令的地址 每一條指令的尋址方式由指令本身確定 或按某些預(yù)先約定規(guī)則進行 有按地址訪問 按內(nèi)容訪問 按堆棧訪問等訪問方式 還可以是按立即數(shù)方式 不同計算機的尋址方式也各不相同 常用的尋址方式有立即數(shù)尋址 寄存器尋址 直接尋址 間接尋址 基址尋址 變址尋址 相對尋址等 尋址方式有多種 相應(yīng)地 一條指令的實現(xiàn)也有多種 指令系統(tǒng)的分析 指令系統(tǒng)的設(shè)計主要是確定它的指令格式 類型 操作以及操作數(shù)的訪問方式 硬件價格的下降 指令系統(tǒng)逐步擴充 指令功能也逐步增強 指令系統(tǒng)的改進是圍繞著縮小與高級語言的語義差異以及有利于操作系統(tǒng)優(yōu)化而進行的 通過操作碼擴展 各種各樣的尋址方式 可變的指令長度來設(shè)計復(fù)雜指令 指令系統(tǒng)從早期的簡單形式 逐步發(fā)展為多種尋址方式 多種數(shù)據(jù)格式的復(fù)雜指令集 這是為了提高計算機功能以滿足用戶日益增長的需求 IBM370計算機上用不同語言編寫的程序所出現(xiàn)的指令的頻度做了統(tǒng)計 經(jīng)分析得出 程序的80 是存取 轉(zhuǎn)移 算術(shù)邏輯運算等簡單指令 而復(fù)雜指令的使用僅占20 但為復(fù)雜指令而設(shè)計的微程序卻占微程序ROM的80 復(fù)雜指令增加而使CPU結(jié)構(gòu)趨于復(fù)雜 對編譯程序的優(yōu)化好處不大 第3章存儲系統(tǒng)結(jié)構(gòu) 并行主存系統(tǒng)主存系統(tǒng)的類型1 主存系統(tǒng)的類型根據(jù)主存中存儲體的個數(shù) 以及CPU訪問主存一次所能讀出的信息的位數(shù) 可以將主存系統(tǒng)分為以下四種類型 1 單體單字存儲器 即存儲器只有一個存儲體 而且存儲體的寬度為一個字 如圖3 1所示是一個字長為W位的單體主存 一次可以訪問一個存儲器字 所以主存最大頻寬Bm W TM 假設(shè) 此存儲器字長W與CPU所要訪問的字 數(shù)據(jù)字或指令字 簡稱CPU字 的字長W相同 則CPU從主存獲得信息的速率就為W TM 我們稱這種主存是單體單字存儲器 圖3 1單體單字存儲器 2 單體多字存儲器 即存儲器只有一個存儲體 但存儲體的總線寬度較大 可以是多個字 如圖3 2所示 若要想提高主存頻寬Bm 使之與CPU速度匹配 顯然可以想到 在同樣的器件條件 即同樣的TM 下 只有設(shè)法提高存儲器的字長W才行 例如 改用圖3 2的方式組成 這樣 主存在一個存儲周期內(nèi)就可以讀出4個CPU字 相當于CPU從主存中獲得信息的最大速率提高到原來的4倍 即Bm 4W TM 我們稱這種主存為單體多字存儲器 圖3 2單體多字 m 4 存儲器 3 多體單字交叉存取的存儲器 如 多體交叉存儲器 因為每個存儲體都是一個CPU字的寬度 4 多體多字交叉存儲器 它將多分體并行存取與單體多字相結(jié)合 我們將能并行讀出多個CPU字的單體多字 多體單字交叉 多體多字交叉存取的主存系統(tǒng)稱為并行主存系統(tǒng) 2 單體多字方式與多體單字交叉方式的區(qū)別 1 單體多字方式要求可并行讀出的m個字必須是地址順序排列且處于同一主存單元 2 而主存采用多體單字方式組成 即采用m個存儲體交叉編址 多個存儲體并行進行存取操作 每個存儲體的寬度一般是一個字的寬度 其所花費的器件和總價格并不比采用單體多字方式的多多少 但其實際帶寬卻可以比較高 這是因為多體單字方式只要m個地址不發(fā)生分體沖突 即沒有發(fā)生兩個以上地址同屬一個分體 即使地址之間不是順序的 仍可并行讀出 使實際帶寬提高成單體單字的m倍 基本的多體交叉方法有兩種 即高位交叉訪問存儲器和低位交叉訪問存儲器 2 高位交叉訪問存儲器圖3 3是高位交叉的四體交叉存儲器結(jié)構(gòu)示意圖 如果主存空間為N 2n字 那么訪問該存儲器的地址為n位 若存儲器由M 2m個存儲體構(gòu)成 用高m位地址來選擇不同的存儲體 低n m位為體內(nèi)的地址 當高m位不相同時 便可以訪問不同的存儲體 即當多個處理機發(fā)出的訪存地址高位不相同時 可對共享存儲器內(nèi)的不同存儲體進行同時存取 當多個處理機發(fā)出的訪存地址高位相同時 即訪存同一存儲體時 就不能并行操作了 我們稱之為存儲器的分體沖突 高位交叉訪問存儲器一般適合于共享存儲器的多機系統(tǒng) 圖3 3高位交叉的四體交叉存儲器結(jié)構(gòu)示意圖 3 低位交叉訪問存儲器圖3 4是低位交叉的四體交叉存儲器結(jié)構(gòu)示意圖 如果主存空間為N 2n字 那么訪問該存儲器的地址為n位 若存儲器由M 2m個存儲體構(gòu)成 用低m位地址來選擇不同的存儲體 高n m位為體內(nèi)地址 當?shù)蚼位不相同時 便可以訪問不同的存儲體 即當處理機發(fā)出的訪存地址訪問不同的存儲體時 地址不一定連續(xù) 可對存儲器內(nèi)的不同存儲體進行并行存取 這里的并行性指的是并發(fā)性 當處理機訪存同一存儲體時 就不能并行操作了 低位交叉訪問存儲器一般適合于單處理機內(nèi)的高速數(shù)據(jù)存取及帶Cache的主存 在最好的情況下 即一個模m的多體交叉訪問存儲器在不發(fā)生分配沖突時的帶寬是單體帶寬的m倍 圖3 4低位交叉的四體交叉存儲器結(jié)構(gòu)示意圖 如果模塊的字是與數(shù)據(jù)總線等寬 W位 若模塊存取一個字的存儲周期是 由m個子周期 要大于或等于總線傳送周期 組成 即 m 并使用m個模塊來交叉存取 則成塊存取可按 間隔流水進行 即每經(jīng) 時間延遲后即啟動下一模塊 這樣 連續(xù)讀m個字所需時間為 m 1 而順序組織方式卻要m 時間 顯然加快了成塊存取速度 模四多體交叉存取存儲器的流水存取示意圖如圖3 5所示 圖3 5模四多體交叉存取存儲器的流水存取示意圖 前面講過 并行主存系統(tǒng)可達到的最大頻寬Bm W m TM 由這個式子可以看出 提高模m的值 是能提高主存系統(tǒng)的頻寬的 但主存頻寬并不是隨m值增大而線性提高 也就是說其實際效率并不像所希望的那么高 例如 CDC 6600 7600采用模32交叉實際頻寬只是理想頻寬的三分之一都不到 這是因為 1 工程實現(xiàn)上由于模m越高 存儲器數(shù)據(jù)總線越長 總線上并聯(lián)的負載越重 有時還不得不增加門的級數(shù) 這些都會使傳輸延遲增加 2 是系統(tǒng)效率問題 對模m交叉 如果都是順序的取指令 效率是可以提高到m倍的 但實際上程序中指令不總是順序執(zhí)行的 一旦出現(xiàn)轉(zhuǎn)移 效率就會下降 轉(zhuǎn)移的頻度越高 這種并行主存系統(tǒng)的效率下降就越大 而數(shù)據(jù)的順序性比指令差 實際的頻寬可能還要低一些 第4章流水線結(jié)構(gòu) 第5章并行處理機 第6章多處理器系統(tǒng) 多處理機屬于MIMD系統(tǒng) 它與SIMD并行處理機有很大的差別 所有的差別歸根結(jié)底來源于兩者開發(fā)的并行性等級不同 多處理機實現(xiàn)的是作業(yè) 任務(wù)之間的并行 粒度組合主要為粗粒度和中粒度 因此 在結(jié)構(gòu)上 多處理機中的每個結(jié)點都應(yīng)該是一臺能獨立執(zhí)行指令的處理機 而不只是一個簡單的處理單元 各處理機之間通過總線或互連網(wǎng)絡(luò)實現(xiàn)通信 在算法上 不再限于數(shù)組和向量中的數(shù)據(jù)并行性 還要挖掘和實現(xiàn)更多通用算法中隱含的并行性 在系統(tǒng)管理上 要更多地依靠軟件手段有效解決資源管理 特別是粒度的組合與調(diào)度 多處理機調(diào)度 進程的同步和通信等 6 1多處理機的概念 6 1 1多處理機系統(tǒng)的定義P H Enslow對多處理機給出了下列定義 1 包含兩個或兩個以上功能大致相同的處理器 2 所有處理器共享一個公共內(nèi)存 3 所有處理器共享I O通道 控制器和外圍設(shè)備 4 整個系統(tǒng)由統(tǒng)一的操作系統(tǒng)控制 在處理器和程序之間實現(xiàn)作業(yè) 任務(wù) 程序段 數(shù)組和數(shù)組元素等各級的全面并行 6 1 2多重處理對處理機特性的要求 1 進程恢復(fù)能力2 有效的現(xiàn)場切換3 大的物理地址空間和虛擬地址空間4 高效率的同步原語5 處理機之間有高效率的通信機構(gòu)6 指令系統(tǒng) 6 1 3多處理機的特點 1 很高的性能價格比 2 很高的可靠性 3 很高的處理速度 4 很好的模塊化 5 具有更大的結(jié)構(gòu)靈活性和更強的通用性 由于在MIMD多處理機中各結(jié)點是一臺獨立的處理機 可以與其它處理機共享主存儲器或采用分布式存儲器 因而在不同的處理機上可并行執(zhí)行不同的作業(yè) 任務(wù)或程序段 所以MIMD多處理機適宜于求解通用算法 另外 它能靈活地開發(fā)數(shù)據(jù)并行性和功能并行性 而SIMD并行處理機只能開發(fā)數(shù)組和向量中存在的數(shù)據(jù)并行性 因此其通用性較差 6 主要開發(fā)高層次作業(yè)及任務(wù)級并行性 對于高層次的并行性開發(fā) 通常是通過算法和程序設(shè)計語言來描述程序中的顯式并行性 或通過編譯器 操作系統(tǒng)和硬件來開發(fā)程序中存在的隱式并行性 而SIMD并行處理機則主要是開發(fā)低層次 即操作一級的并行性 7 并行任務(wù)派生需要用顯式的專用指令來表示 在MIMD多處理機中 一個程序當中就存在多個并發(fā)的程序段 需要專用的指令來表示它們的并發(fā)關(guān)系以控制它們的并發(fā)執(zhí)行 以便一個任務(wù)開始被執(zhí)行時就能派生出可與它并行執(zhí)行的另一些任務(wù) 這個過程稱為并行任務(wù)派生 派生出的新任務(wù)被分配到其它處理機上去并行執(zhí)行 若處理機的數(shù)量不夠 那些暫時不能分配到空閑處理機的任務(wù)就進入排隊器 等待即將釋放的處理機 在SIMD并行處理機中 并行操作由單獨指令表示和控制 故不需要設(shè)置專用的指令 8 并發(fā)執(zhí)行的進程間的同步需要采取特殊措施 以保持程序所要求的正確順序 由于MIMD多處理機實現(xiàn)的是作業(yè) 任務(wù)和程序級的并行性 一般來說 各處理機在同一時刻執(zhí)行的是不同的指令 并行任務(wù)派生后 由于空閑處理機的限制使得所有的新任務(wù)不一定能同時投入運行 又加上各并發(fā)進程之間可能存在數(shù)據(jù)相關(guān) 控制相關(guān)等 為保持程序所要求的正確順序 必須采取特殊的措施來實現(xiàn)并發(fā)進程間的同步 如采用數(shù)據(jù)同步 信號量 鎖 生產(chǎn)者 消費者 控制同步 路障 臨界區(qū) 等 而在SIMD并行處理機中 由于所有的處理單元在同一控制器控制下 同時執(zhí)行同一條指令的功能 工作是自然同步的 9 合理地進行資源分配和任務(wù)調(diào)度 在MIMD多處理機中 由于任務(wù)的大小不相同 各處理機的速度也可能不相同 如異構(gòu)型多處理機系統(tǒng) 互連網(wǎng)絡(luò)的拓撲結(jié)構(gòu)和通信延遲在不同的多處理機中也有很大的差別 在執(zhí)行并發(fā)任務(wù)時 并不是使用的處理機個數(shù)越多 系統(tǒng)獲得的性能就越高 因此需要采用軟件手段 合理地進行資源分配和任務(wù)調(diào)度 否則系統(tǒng)性能將受較大影響 而在SIMD并行處理機中 程序員只需用屏蔽的手段來設(shè)置部分處理單元為不活躍狀態(tài) 來控制實際參加并行操作的處理單元數(shù)目 6 2多處理機結(jié)構(gòu) 6 2 1多處理機的基本結(jié)構(gòu)多處理機在系統(tǒng)結(jié)構(gòu)上可分為兩類 緊耦合多處理機和松耦合多處理機 1 緊耦合 tightlycoupled 多處理機緊耦合多處理機是通過共享主存來實現(xiàn)處理機間的通信的 各處理機與主存之間通過一個互連網(wǎng)絡(luò)連接 在這種系統(tǒng)中 處理機間的數(shù)據(jù)通信速率將受限于主存的帶寬 而處理機的數(shù)目受限于處理機 主存互連網(wǎng)絡(luò)帶寬以及多臺處理機同時訪問主存所引起的沖突概率 為了減少處理機訪問主存的沖突 常采用如下方法 1 多處理機的主存采用多模塊交叉存取 模塊數(shù)越多 發(fā)生沖突的概率將越低 但必須解決好數(shù)據(jù)在各存儲器模塊中的定位和分配 2 讓每臺處理機擁有一個小容量的局存 用來存放頻繁使用的核心代碼等 以減少對主存的訪問 3 讓每臺處理機都有一個Cache 以減少對主存的訪問 但必須注意Cache與主存之間以及各個Cache之間的數(shù)據(jù)一致性 緊耦合多處理機的典型結(jié)構(gòu)如圖7 1所示 系統(tǒng)由m個共享存儲器模塊 p臺處理機和d個I O通道組成 每臺處理機可以擁有一個Cache存儲器或一個小容量的本地存儲器 用三個互連網(wǎng)絡(luò)PPIN 處理機 處理機 PMIN 處理機 主存 和PIOIN 處理機 I O通道 將所有的處理機 共享存儲器模塊 以及I O通道連接起來 緊耦合多處理機按所用處理機類型是否相同可分為同構(gòu)型和異構(gòu)型多處理機 圖6 1緊耦合多處理機系統(tǒng)的典型結(jié)構(gòu) 在緊耦合多處理機中 如果每臺處理機在訪問任意一個存儲器模塊或I O設(shè)備時 都具有同等的能力 包括字寬和讀寫時間等都相同 那么這個系統(tǒng)就具有對稱性 反之 表示多處理機是非對稱的 一個多處理機要成為對稱式多處理機必須滿足兩個條件 首先存儲器必須是集中共享的 其次系統(tǒng)所用的互連網(wǎng)絡(luò)也必須是對稱的 緊耦合多處理機按其對稱性可分為對稱式多處理機和非對稱式多處理機 對稱式多處理機能實現(xiàn)各處理機與各I O通道之間完全連接 有很大的靈活性 但價格昂貴 所以多數(shù)多處理機仍采用非對稱式的互連 即連到一臺處理機的設(shè)備不能被另一臺處理機直接訪問 帶非對稱I O子系統(tǒng)的多處理機如圖6 2所示 圖6 2帶非對稱I O子系統(tǒng)的多處理機 圖6 3帶冗余連接的非對稱I O子系統(tǒng) 在非對稱式多處理機中 一旦某臺處理機出現(xiàn)故障 它所接的外設(shè)將無法被其它處理機所訪問 例如 在圖6 2中 若處理機P1出現(xiàn)故障 則它所接的IOP1將不能被其它處理機中的任何一個所訪問 因此在很多非對稱式多處理機中都采用了適當?shù)娜哂噙B接 在一定程度上提高了設(shè)備的利用率 帶冗余連接的非對稱I O子系統(tǒng)的多處理機如圖6 3所示 在此圖中 若處理機P1發(fā)生故障 處理機Pp仍可以訪問IOP1 但這是以增加一個多通路仲裁邏輯為代價的 在緊耦合多處理機中 常見的組合是同構(gòu)對稱式多處理機及異構(gòu)非對稱式多處理機 1 同構(gòu)對稱式多處理機Sequent公司生產(chǎn)的Balance多處理機就是同構(gòu)對稱式的 它的結(jié)構(gòu)如圖6 4所示 處理機數(shù)為2 32個 共享存儲器模塊數(shù)為1 6個 其中 每臺處理機由80386微處理器和浮點運算器Weitek1167FPU組成 并帶有64KB的Cache 存儲器由8MB 可擴充到48MB 的存儲器模塊和一個存儲控制器組成 各處理機和存儲器模塊均與系統(tǒng)總線相連 系統(tǒng)總線還通過總線適配器與Ethernet局域網(wǎng) SCSI相連 或通過磁盤控制器與磁盤相連 此外 系統(tǒng)總線還可借助總線適配器和Multibus與遠程網(wǎng)相連 圖6 4Sequent的Balance同構(gòu)對稱式多處理機 2 異構(gòu)非對稱式多處理機異構(gòu)非對稱式多處理機的一般結(jié)構(gòu)如圖6 5所示 其中主CPU所用的處理機可不同于從機中的處理機 從機中CIOP處理機與字符外設(shè)相連 BIOP與數(shù)組外設(shè)相連 NIOP及GIOP分別為網(wǎng)絡(luò)及圖形處理機 ACOP為向量加速處理機 圖6 5異構(gòu)非對稱式多處理機的一般結(jié)構(gòu) 2 松耦合 looselycoupled 多處理機松耦合多處理機是通過消息傳遞方式來實現(xiàn)處理機間的相互通信的 而每臺處理機是由一個獨立性較強的計算機模塊組成 該模塊由處理器 較大容量的本地存儲器 在運算時所需的絕大部分的指令和數(shù)據(jù)均取自本地存儲器 I O設(shè)備以及與消息傳遞系統(tǒng) MessageTransferSystem MTS 相連的接口組成 當不同模塊上運行的進程間需要通信時 可通過網(wǎng)絡(luò)接口電路及消息傳遞系統(tǒng)進行信息交換 由于這種相互間的耦合程度是很松散的 因此稱之為松耦合多處理機 松耦合多處理機可分為非層次式和層次式兩種結(jié)構(gòu) 1 非層次式松耦合多處理機圖6 6是一個典型的通過消息傳遞系統(tǒng)進行互連的松耦合非層次式多處理機 該系統(tǒng)有N個計算機模塊 或稱結(jié)點 每個計算機模塊由微處理器 Cache 本地存儲器LM和一組I O設(shè)備組成 各計算機模塊的進程之間通過網(wǎng)絡(luò)接口電路NIC NetworkInterfaceCircuitry 和消息傳遞系統(tǒng)進行通信 其中的NIC通常是由通道和仲裁開關(guān)CAS ChannelandArbiterSwitch 組成 用于對兩個或多個計算機模塊同時請求訪問MTS的某個物理段時進行仲裁 按照一定的算法 選擇其中一個請求并延遲其它的請求 直至被選擇的請求服務(wù)完成 圖6 6松耦合非層次式多處理機系統(tǒng)的典型結(jié)構(gòu) 2 層次式松耦合多處理機在層次式松耦合多處理機中采用了多級總線實現(xiàn)層次連接 圖6 7中示出了卡內(nèi)基 梅隆大學(xué)研制的由50個LSI 11小型機組成的Cm 層次式松耦合多處理機 最基本的計算機模塊Cm中有自己的LSI 11總線 通過開關(guān)S經(jīng)MAP總線與其它Cm相連 每個MAP總線可連接多達14個計算機模塊Cm 構(gòu)成一個計算機模塊群 cluster 模塊群內(nèi)的各處理機用較低的通信開銷實現(xiàn)數(shù)據(jù)共享 圖6 7Cm 層次式松耦合多處理機 與MAP總線相連的Kmap是系統(tǒng)內(nèi)各計算機模塊群間的連接器 而各模塊群間的連接是通過群間雙總線實現(xiàn)的 采用雙總線的主要目的是為了提高系統(tǒng)的可靠性 因此 Cm 是一個三層總線多處理機 三級的訪存時間分別為 計算機模塊內(nèi)3 5 s 計算機模塊群內(nèi)9 3 s 而群間則為26 s 在松耦合多處理機中 由于各計算機模塊實際上是一臺完整的計算機 各計算機除了帶有本地存儲器外 一般都設(shè)有Cache存儲器 因此與緊耦合多處理機一樣 要解決多處理機Cache之間 Cache與主存之間的一致性問題 6 2 2多處理機系統(tǒng)的存儲器結(jié)構(gòu) 1 主存的組成 2 多處理機系統(tǒng)的Cache結(jié)構(gòu)Cache一致性問題的原因如果多臺處理機在運行同一程序時不存在共享數(shù)據(jù) 或共享數(shù)據(jù)不允許調(diào)入各自的Cache時 將不會出現(xiàn)Cache的一致性問題 若允許共享數(shù)據(jù)調(diào)入各處理機的Cache中 并且允許處理機對共享數(shù)據(jù)進行寫入操作時 就會產(chǎn)生各Cache中的共享數(shù)據(jù)之間 Cache與共享存儲器之間的數(shù)據(jù)的不一致 具體來說 有以下三個方面的原因 1 共享可寫數(shù)據(jù) 2 多處理機的進程遷移 3 繞過Cache的I O操作 以下以沒有任何Cache一致性控制的共享存儲器雙處理機為例說明上述原因 處理機P1和P2擁有各自的Cache存儲器Cache1和Cache2 我們將對寫直達 WT 法和寫回 WB 法分別予以分析 若使用寫直達法 Cache數(shù)據(jù)的更新總是會引起主存內(nèi)容的立即更新 若使用寫回法 只有當Cache中的某一個數(shù)據(jù)塊被替換時 該數(shù)據(jù)塊才會在替換前被寫回主存 所以在對Cache的寫操作命中后的一段時間內(nèi) Cache和主存內(nèi)容是不一致的 A 由共享可寫數(shù)據(jù)引起的Cache不一致假設(shè)在寫操作之前Cache的初始狀態(tài)如圖6 8 a 所示 處理機P1和P2各自Cache中的數(shù)據(jù) 標為x 與共享主存器中的相應(yīng)數(shù)據(jù)是一致的 圖中數(shù)據(jù)x加方框表示數(shù)據(jù)x所在的數(shù)據(jù)塊 圖6 8由共享可寫數(shù)據(jù)引起的Cache不一致 若使用寫直達法 如圖6 8 b 所示 當處理機P1修改Cache1中的數(shù)據(jù)成x 時 在共享存儲器中的相應(yīng)數(shù)據(jù)也立即更新為x 這導(dǎo)致與處理機P2中Cache2所緩存的數(shù)據(jù)不一致 若使用寫回法 如圖6 8 c 所示 當處理機P1修改Cache1中的數(shù)據(jù)成x 時 Cache1的變化不會引起Cache2和共享存儲器的變化 這導(dǎo)致與共享存儲器和處理機P2中Cache2所緩存的數(shù)據(jù)不一致 由此可見 在多處理機中要解決由共享可寫數(shù)據(jù)引起的不一致 必須在每次寫操作后立即使其它處理機的Cache中包含有相同Cache塊的不同拷貝失效或者進行更新 B 由進程遷移引起的Cache不一致假設(shè)在遷移前Cache的初始狀態(tài)如圖6 9 a 所示 處理機P1的Cache1中有共享存儲器中數(shù)據(jù)x的拷貝 若使用寫直達法 如圖6 9 b 所示 當某進程從P1遷移到P2后 處理機P2在執(zhí)行此進程時由于要使用數(shù)據(jù)x 會將x所在的Cache塊由共享存儲器調(diào)入Cache2 假設(shè)進程運行時將Cache2的數(shù)據(jù)x改寫為x 在共享存儲器中的相應(yīng)數(shù)據(jù)也立即更新為x 這導(dǎo)致與處理機P1中Cache1所緩存的數(shù)據(jù)不一致 圖6 9由進程遷移引起的Cache不一致 若使用寫回法 如圖6 9 c 所示 當處理機P1修改Cache1中的數(shù)據(jù)成x 時 Cache1的變化不會引起共享存儲器的變化 當某進程從P1遷移到P2后 處理機P2在執(zhí)行此進程時由于要使用數(shù)據(jù)x 會將x所在的Cache塊由共享存儲器調(diào)入Cache2 此時調(diào)入的數(shù)據(jù)x并非是已經(jīng)修改過的x 這將導(dǎo)致共享存儲器及Cache2與處理機P1中Cache1所緩存的數(shù)據(jù)不一致 C 由繞過Cache的I O操作引起的不一致假設(shè)在執(zhí)行I O操作之前Cache的初始狀態(tài)如圖6 10 a 所示 處理機P1和P2各自Cache中的數(shù)據(jù) 標為x 與共享存儲器中的相應(yīng)數(shù)據(jù)是一致的 若使用寫直達法 當I O處理機執(zhí)行輸入操作直接將共享存儲器中的數(shù)據(jù)x改寫成x 時 這將導(dǎo)致Cache1和Cache2與共享存儲器數(shù)據(jù)的不一致 如圖6 10 b 所示 若使用寫回法 當處理機P1對Cache1中的數(shù)據(jù)x改寫為x 時 由于Cache1數(shù)據(jù)的修改不會立即引起共享存儲器中數(shù)據(jù)x的更新 此時若此數(shù)據(jù)恰好被I O處理機輸出 就會造成輸出錯誤 如圖6 10 c 所示 這表明I O操作應(yīng)當在Cache控制器的協(xié)調(diào)下進行 圖6 10由繞過Cache的I O操作引起的不一致 由前面介紹的三種引起Cache不一致的原因 表明了在多處理機環(huán)境下共享可寫數(shù)據(jù) 進行進程遷移或I O操作時采用一致性協(xié)議的必要性 一致性協(xié)議主要有兩種 一種是基于總線的監(jiān)聽一致性協(xié)議 snoopycoherencyprotocol 此類協(xié)議需要由總線或環(huán)提供的廣播機制 通過監(jiān)聽總線 snoopybus 實現(xiàn) 主要思想是不斷地監(jiān)聽總線上處理機和存儲器模塊間的Cache操作事件 各處理機根據(jù)監(jiān)聽的信息對各自Cache中的數(shù)據(jù)采取保持一致性的措施 另一種是基于目錄的一致性協(xié)議 此類協(xié)議需要建立一個Cache目錄 記錄共享數(shù)據(jù)塊的處理機信息 當某一處理機完成寫操作后 同時通過此數(shù)據(jù)塊所在的各目錄項 把一致性命令發(fā)給存放有該數(shù)據(jù)塊拷貝的Cache 使之無效或更新 但它主要應(yīng)用于具有分布式存儲器模型的多處理機中 3 監(jiān)聽一致性協(xié)議當各處理機的Cache都連接到公共總線時 為保持Cache的一致性有兩種選擇 一種是采用寫無效 write invalidate 協(xié)議 另一種是采用寫更新 write update 協(xié)議 寫無效協(xié)議是指在某本地Cache數(shù)據(jù)被更新后使所有其它Cache中的相應(yīng)數(shù)據(jù)拷貝失效 寫更新協(xié)議是指在某本地Cache數(shù)據(jù)被更新后 廣播修改后的數(shù)據(jù)以更新所有Cache中的相應(yīng)數(shù)據(jù)拷貝 注意 這里要區(qū)分多處理機的Cache一致性協(xié)議與更新主存內(nèi)容的協(xié)議之間的區(qū)別 前者是為了保持多處理機中各Cache的一致性 而后者是為了保持某臺處理機的Cache與主存儲器之間的一致性 通常所說的寫直達 WT 法和寫回 WB 法屬于后者 A 寫無效協(xié)議在圖6 11 a 中 可以看到在寫操作前 處理機P1和P2的各自Cache中都存有共享存儲器中數(shù)據(jù)x的拷貝 圖中數(shù)據(jù)x加方框表示數(shù)據(jù)x所在的數(shù)據(jù)塊 當處理機P1想要進行寫操作時 首先它必須獲得對x訪問的獨占權(quán) 然后更新數(shù)據(jù)為x 并使Cache2中的相應(yīng)數(shù)據(jù)塊拷貝失效 標志為I 如圖6 11 b 6 11 c 所示 若使用寫直達法 該共享存儲器中的數(shù)據(jù)x將會立即更新為x 如圖6 11 b 所示 若使用寫回法 共享存儲器中數(shù)據(jù)x所在的數(shù)據(jù)塊也將被設(shè)置為無效 如圖6 11 c 所示 若使用寫直達法 當處理機P2想要訪問已修改的數(shù)據(jù)x 時 會發(fā)生Cache2不命中并從共享存儲器中讀取新值x 并調(diào)入數(shù)據(jù)x 所在的數(shù)據(jù)塊 若使用寫回法 當處理機P2想要訪問已修改的數(shù)據(jù)x 時 會發(fā)生Cache2不命中并從處理機P1的Cache1讀取新值x 并調(diào)入數(shù)據(jù)x 所在的數(shù)據(jù)塊 同時會更新主存中的相應(yīng)數(shù)據(jù)塊 圖6 11寫無效監(jiān)聽協(xié)議 B 寫更新協(xié)議假設(shè)在寫操作前 處理機P1和P2的各自Cache中都存有共享存儲器中數(shù)據(jù)x的拷貝 如圖6 12 a 所示 當處理機P1對Cache1中的數(shù)據(jù)x進行寫操作時 它必須通過廣播x 的方法來更新x在所有處理機Cache中的拷貝 當其它的處理機要訪問修改過的x 時 會在本地Cache命中 如圖6 12 b 6 12 c 所示 若使用寫直達法 則共享存儲器中數(shù)據(jù)x所在的數(shù)據(jù)塊會如圖6 12 b 中所示的立即更新 若使用寫回法 則共享存儲器中數(shù)據(jù)x所在的數(shù)據(jù)塊將會被置為無效 如圖6 12 c 所示 共享存儲器中的數(shù)據(jù)也可以立即更新 這由所使用的具體實現(xiàn)方法決定 從上述過程可以看出 寫更新協(xié)議為保持所有Cache中共享數(shù)據(jù)的高度一致性 需耗費大量的總線周期來更新所有的Cache和共享存儲器中的共享數(shù)據(jù)塊 這無疑會加重總線傳輸?shù)呢摀?因此在大多數(shù)多處理機中都選擇使用寫無效協(xié)議 圖6 12寫更新監(jiān)聽協(xié)議 MESI監(jiān)聽協(xié)議MESI屬于寫無效協(xié)議 它根據(jù)所有的讀 寫 命中或不命中和在總線上監(jiān)聽的事件來跟蹤Cache數(shù)據(jù)塊的狀態(tài) 帶有2級Cache的雙Pentium多處理器系統(tǒng)實現(xiàn)的MESI協(xié)議 如圖6 13所示 圖6 13有2級Cache的雙Pentium處理器系統(tǒng) PentiumMESI協(xié)議同時支持寫直達法和寫回法 這由一個外部信號控制 當發(fā)生Cache的寫不命中時使用不按寫分配 non write allocate 法 即不從共享的主存儲器中載入該數(shù)據(jù)所在的Cache塊 4 基于目錄的協(xié)議當某臺處理機采用寫無效協(xié)議正在更新一個變量并且其它的處理機也試圖讀該變量時 則會發(fā)生讀失效并可能導(dǎo)致總線的流量大大增加 另外 寫更新協(xié)議可以更新遠程Cache中的數(shù)據(jù) 而其它處理機可能永遠也不會使用這些數(shù)據(jù) 因此 這些問題使采用總線來構(gòu)造大型多處理機系統(tǒng)受到限制 當用多級網(wǎng)絡(luò)來構(gòu)造有數(shù)百臺處理機的大型系統(tǒng)時 就必須修改Cache的監(jiān)聽協(xié)議以適應(yīng)網(wǎng)絡(luò)的性能 由于在多級網(wǎng)絡(luò)上實現(xiàn)廣播功能的代價很大 所以把一致性命令只發(fā)給存放塊拷貝的Cache 這樣就產(chǎn)生了用于網(wǎng)絡(luò)連接的多處理機系統(tǒng)的基于目錄的協(xié)議 A 目錄結(jié)構(gòu)Cache目錄 cachedirectory DIR 實際上是一個Cache位置表 它是用目錄的形式記錄所有Cache塊和共享數(shù)據(jù)塊的位置和狀態(tài) 從而支持Cache一致性 各種基于目錄協(xié)議的不同之處主要是目錄如何維護信息和存放什么信息 Cache目錄的方案有集中式和分布式兩種 它們的主要區(qū)別就在于其Cache目錄的存放形式 由于集中式目錄記錄了Cache的當前信息和所有Cache塊的狀態(tài) 需要大量的存儲器來實現(xiàn) 因此集中式目錄只適用于具有集中式共享存儲器的小規(guī)模SMP的Cache一致性控制 在分布式目錄中 每個存儲器模塊維護了一個單獨的目錄來記錄所有的Cache塊的狀態(tài)和當前信息 無論Cache目錄采用集中方式還是分布方式來存放 其內(nèi)容都是大量的指針 用以指明塊拷貝的地址 每個目錄項還有一個污染位 dirtybit 用以指明是否只有某個唯一的Cache有此數(shù)據(jù)塊的寫權(quán)限 不同目錄協(xié)議的區(qū)別在于目錄的結(jié)構(gòu)不同 根據(jù)目錄的結(jié)構(gòu) 可以把目錄協(xié)議分成三類 全映射目錄 full mapdirectory 有限目錄 limiteddirectory 和鏈式目錄 chaineddirectory 全映射目錄存放與全局存儲器中每個Cache塊有關(guān)的數(shù)據(jù) 這樣 系統(tǒng)中的每個Cache可以同時存儲任何數(shù)據(jù)塊的拷貝 而在有限目錄中 無論系統(tǒng)的規(guī)模多大 它的每個目錄項的指針數(shù)都是固定的 所以每個數(shù)據(jù)塊能夠裝入Cache的數(shù)目是有限的 鏈式目錄的特點是把目錄分布到全部的Cache中 其余部分與全映射相同 B 全映射目錄用全映射目錄協(xié)議實現(xiàn)的目錄項中有N個處理機位和一個污染位 其中N為處理機的臺數(shù) 目錄項的結(jié)構(gòu)如圖6 14所示 處理機位表示相應(yīng)處理機對應(yīng)的Cache塊的狀態(tài)為 有效 或 無效 有效 表示該Cache塊已存在于某臺處理機的Cache中 并且為有效狀態(tài) 無效 表示該Cache塊已存在于某臺處理機的Cache中 并且為無效狀態(tài) 或者在某臺處理機的Cache中該塊根本就不存在 污染位表示某一個Cache塊是否已經(jīng)被修改過 它有 未寫 和 污染 兩種狀態(tài) 未寫 表示當前Cache塊沒有被修改過 污染 表示某一個Cache塊已被修改 如果污染位為 1 而且有且僅有一個處理位為 1 時 則允許該處理機對該塊進行寫操作 圖6 14目錄項的結(jié)構(gòu) Cache的每個數(shù)據(jù)塊有兩個狀態(tài)位 一位表示數(shù)據(jù)塊是否有效 另一位表示有效數(shù)據(jù)塊是否允許寫 Cache一致性協(xié)議必須保證目錄的狀態(tài)位與Cache數(shù)據(jù)塊的狀態(tài)位一致 圖6 15是全映射目錄的三種不同狀態(tài) 第一種狀態(tài)表示整個系統(tǒng)所有Cache中都沒有單元x的拷貝 當三臺處理機都對x有過讀請求之后 就出現(xiàn)了第二種狀態(tài) 這時 目錄項中的三個指針 處理機位 被置 1 表示這些Cache已有數(shù)據(jù)塊拷貝 在前述這二種狀態(tài)下 目錄項最左邊的污染位被置為未寫 Clean C 狀態(tài) 表示沒有一臺處理機允許寫入該數(shù)據(jù)塊 在P3處理機獲得了對x的寫權(quán)限后就出現(xiàn)了第三種狀態(tài) 這時污染位被置為污染 Dirty D 狀態(tài) 而且有一個指針指向Cache3的數(shù)據(jù)塊 下面再來詳細說明圖6 15中從第二種狀態(tài)轉(zhuǎn)換到第三種狀態(tài)的過程 一旦處理機P3向Cache3發(fā)出請求時 將發(fā)生以下事件 1 Cache3檢測出包含單元x的塊是有效的 即P3訪問x時在Cache3中命中 但Cache塊的寫允許位狀態(tài)表示不允許P3對該塊進行寫操作 2 Cache3向包含單元x的存儲器模塊發(fā)寫請求 并暫停P3的工作 3 該存儲器模塊發(fā)出一個無效請求給Cache1和Cache2 4 Cache1和Cache2接收到無效請求后 把相應(yīng)的塊置為無效狀態(tài) 并發(fā)送一個回答信號給發(fā)出請求的存儲器模塊 5 存儲器模塊接收到回答信號后 把污染位置為 D 表示此共享數(shù)據(jù)塊已被修改 并清除指向Cache1和Cache2的指針 發(fā)寫允許信號給Cache3 6 Cache3接收到寫允許信號后 更新包含單元x的塊在Cache3的狀態(tài)為寫允許狀態(tài)并且激活P3處理機 至此 全部過程結(jié)束 P3就可以寫x單元了 在P3完成寫操作之前 存儲器系統(tǒng)一直等待接收回答信號 圖6 15全映射目錄的三種狀態(tài) 由于和存儲器中數(shù)據(jù)塊有關(guān)的目錄項大小同處理機的數(shù)目成正比 所以目錄所花費的存儲器容量就同存儲器大小O N 和目錄項大小O N 的乘積成正比 因此 整個存儲器的開銷將與處理機數(shù)目的平方O N2 成正比 盡管全映射目錄協(xié)議的效率比較高 但由于過多的存儲器開銷 所以不具有可擴展性 C 有限目錄有限目錄的每個目錄項只用一定數(shù)量的指針 而不管系統(tǒng)的大小如何 這減少了Cache目錄對存儲空間的要求 因而當存儲器數(shù)據(jù)塊共享比較少時更加經(jīng)濟 但如果有大量的處理機Cache共享相同的數(shù)據(jù) 那么它有可能降低Cache 主存的更新速度 有限目錄協(xié)議的狀態(tài)與全映射目錄協(xié)議十分相似 但目錄項中的指針 處理機位 實際上是處理機的地址編碼 若共有N臺處理機 則目錄項中指針部分為log2N位 每個目錄項中指針的個數(shù)遠遠小于處理機的臺數(shù)N 正因為如此 當多于允許數(shù)目的Cache同時要求某一個數(shù)據(jù)塊的拷貝的時候 就必須進行指針的替換 這種指針替換過程稱為驅(qū)逐 eviction 由于多處理機系統(tǒng)中的處理機具有局部性 即在任何給定的時間間隔內(nèi) 只有一小部分的處理機訪問某個給定的存儲器數(shù)據(jù) 所以有限目錄足以應(yīng)付這個小的處理機組了 如圖6 16所示 假設(shè)多處理機系統(tǒng)中共有3臺處理機 目錄項中只有2個指針 存儲單元x所在的數(shù)據(jù)塊對應(yīng)的目錄項中2個指針分別指向處理機P1和P2 即在P1和P2的Cache中都有單元x所在的數(shù)據(jù)塊的拷貝 當P3請求訪問單元x時 需將單元x在共享存儲器中的數(shù)據(jù)塊調(diào)入Cache3 同時采用某種替換算法修改目錄項中的指針部分 在圖6 16中假設(shè)替換的是指向處理機P2的指針 在這里 任一時刻最多只能有2臺處理機的Cache共享一個數(shù)據(jù)塊 由于和存儲器中數(shù)據(jù)塊有關(guān)的目錄項大小同log2N成正比 所以目錄所花費的存儲器容量就同存儲器大小O N 和目錄項大小O log2N 的乘積O Nlog2N 成正比 圖6 16有限目錄的驅(qū)逐 D 鏈式目錄鏈式目錄通過將目錄信息分布到多個小規(guī)模的本地目錄中來