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

《《計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》PPT課件.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《《計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》PPT課件.ppt（228頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

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