《計(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頁(yè)珍藏版）》請(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)的基本工作過(guò)程是執(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均接受從控制部件來(lái)的同一條指令 操作對(duì)象是來(lái)自不同數(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ù)來(lái)自所有處理機(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 每秒百萬(wàn)次指令 和MFLOPS 每秒百萬(wàn)次浮點(diǎn)運(yùn)算 也是比較常用的計(jì)算機(jī)性能評(píng)估標(biāo)準(zhǔn) ICF表示浮點(diǎn)運(yùn)算次數(shù) 4 程序訪問(wèn)的局部性原理 程序訪問(wèn)的局部性是指程序執(zhí)行中 呈現(xiàn)出頻繁重新使用那些最近已被使用過(guò)的數(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ì)語(yǔ)言層次 只需要有新的編譯器 在目標(biāo)代碼層次 則系統(tǒng)完全確定 像系列機(jī)操作系統(tǒng)要求標(biāo)準(zhǔn) 數(shù)據(jù)表示 接口 總線 網(wǎng)絡(luò)等等標(biāo)準(zhǔn)2 軟件和硬件的平衡3 符合未來(lái)發(fā)展方向 1 2 4計(jì)算機(jī)系統(tǒng)的設(shè)計(jì)步驟 計(jì)算機(jī)系統(tǒng)從概念上和功能上可看做是一個(gè)多級(jí)構(gòu)成的層次結(jié)構(gòu) 從哪個(gè)層開(kāi)始設(shè)計(jì) 對(duì)設(shè)計(jì)步驟是有影響的 通常有3種不同的設(shè)計(jì)思路 由上往下 由下往上 由中間開(kāi)始 系統(tǒng)結(jié)構(gòu)設(shè)計(jì)步驟如下 1 需求分析2 需求說(shuō)明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)過(guò)軟件映像 變換成按地址訪問(wèn)一維存儲(chǔ)器內(nèi)的各種數(shù)據(jù)表示 計(jì)算機(jī)的數(shù)據(jù)表示如何確定是一個(gè)復(fù)雜的問(wèn)題 基本的數(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ù)表示的精度等問(wèn)題 除了基本的數(shù)據(jù)表示之外 數(shù)據(jù)表示的確是關(guān)系到軟 硬件的分配問(wè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語(yǔ)言僅需一條語(yǔ)句 經(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ī)所有指令的集合 程序員用各種語(yǔ)言編寫的程序都要翻譯成 編譯或解釋 以指令形式表示的機(jī)器語(yǔ)言后才能運(yùn)行 它是反映了計(jì)算機(jī)的基本功能 是硬件設(shè)計(jì)人員和程序設(shè)計(jì)人員都能見(jiàn)到的機(jī)器的主要屬性 指令由地址碼和操作碼組成 隨著指令類型的不同 對(duì)地址碼的長(zhǎng)度要求變化很大 同一個(gè)計(jì)算機(jī)中 可以有1Byte 2Byte 3Byte 4Byte等多種長(zhǎng)度的指令 指令優(yōu)化 指令格式的優(yōu)化指的是如何用最短的位數(shù)來(lái)表示指令的操作信息和地址信息 使程序中指令的平均字長(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)概率最大的指令用最少的位來(lái)表示 而概率較小的指令用較多的位來(lái)表示 達(dá)到使平均位數(shù)縮短的目的 要采用Huffman編碼法表示操作碼 必須先知道各種指令在程序中出現(xiàn)的概率 這通?？梢酝ㄟ^(guò)對(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 的過(guò)程 直至只剩下兩個(gè)頻率 4 對(duì)最后兩個(gè)頻率分別指定代碼0和1 或1和0 5 若某一頻率由兩個(gè)頻率相加而成 則分別指定這兩個(gè)頻率的下一個(gè)代碼為0和1 或1和0 6 繼續(xù) 5 的過(guò)程 直到所有指令均已指定不同代碼為止 舉例說(shuō)明哈夫曼編碼 哈夫曼樹(shù) 將所有的指令按頻率由小到大排序 每次選擇其中最小的兩個(gè)頻率合并成 求和 一個(gè)新的結(jié)點(diǎn) 然后把它作為葉結(jié)點(diǎn) 一個(gè)新的結(jié)點(diǎn)和其它的葉結(jié)點(diǎn)再按頻率大小排序 如此重復(fù) 直至全部頻率都處理完畢最后形成一個(gè)頻率為1的根結(jié)點(diǎn) 此后 由根結(jié)點(diǎn)開(kāi)始向下延伸 對(duì)兩個(gè)分支分別用一位 1 或 0 或相反 來(lái)表示 直至遍歷所有的葉結(jié)點(diǎn)為止 把上述例子用哈夫曼數(shù)編碼 如下圖 構(gòu)造的Huffman樹(shù)以及各指令的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)化表示 而沒(méi)有在地址碼表示和尋址方式方面采取相應(yīng)的措施 程序所需總位數(shù)還是難以減少的 如果主存是按位編址 操作碼的優(yōu)化表示會(huì)直接帶來(lái)程序所需總位數(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)行 有按地址訪問(wèn) 按內(nèi)容訪問(wèn) 按堆棧訪問(wèn)等訪問(wèn)方式 還可以是按立即數(shù)方式 不同計(jì)算機(jī)的尋址方式也各不相同 常用的尋址方式有立即數(shù)尋址 寄存器尋址 直接尋址 間接尋址 基址尋址 變址尋址 相對(duì)尋址等 尋址方式有多種 相應(yīng)地 一條指令的實(shí)現(xiàn)也有多種 指令系統(tǒng)的分析 指令系統(tǒng)的設(shè)計(jì)主要是確定它的指令格式 類型 操作以及操作數(shù)的訪問(wèn)方式 硬件價(jià)格的下降 指令系統(tǒng)逐步擴(kuò)充 指令功能也逐步增強(qiáng) 指令系統(tǒng)的改進(jìn)是圍繞著縮小與高級(jí)語(yǔ)言的語(yǔ)義差異以及有利于操作系統(tǒng)優(yōu)化而進(jìn)行的 通過(guò)操作碼擴(kuò)展 各種各樣的尋址方式 可變的指令長(zhǎng)度來(lái)設(shè)計(jì)復(fù)雜指令 指令系統(tǒng)從早期的簡(jiǎn)單形式 逐步發(fā)展為多種尋址方式 多種數(shù)據(jù)格式的復(fù)雜指令集 這是為了提高計(jì)算機(jī)功能以滿足用戶日益增長(zhǎng)的需求 IBM370計(jì)算機(jī)上用不同語(yǔ)言編寫的程序所出現(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訪問(wèn)主存一次所能讀出的信息的位數(shù) 可以將主存系統(tǒng)分為以下四種類型 1 單體單字存儲(chǔ)器 即存儲(chǔ)器只有一個(gè)存儲(chǔ)體 而且存儲(chǔ)體的寬度為一個(gè)字 如圖3 1所示是一個(gè)字長(zhǎng)為W位的單體主存 一次可以訪問(wèn)一個(gè)存儲(chǔ)器字 所以主存最大頻寬Bm W TM 假設(shè) 此存儲(chǔ)器字長(zhǎng)W與CPU所要訪問(wèn)的字 數(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從主存中獲得信息的最大速率提高到原來(lái)的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ā)生分體沖突 即沒(méi)有發(fā)生兩個(gè)以上地址同屬一個(gè)分體 即使地址之間不是順序的 仍可并行讀出 使實(shí)際帶寬提高成單體單字的m倍 基本的多體交叉方法有兩種 即高位交叉訪問(wèn)存儲(chǔ)器和低位交叉訪問(wèn)存儲(chǔ)器 2 高位交叉訪問(wèn)存儲(chǔ)器圖3 3是高位交叉的四體交叉存儲(chǔ)器結(jié)構(gòu)示意圖 如果主存空間為N 2n字 那么訪問(wèn)該存儲(chǔ)器的地址為n位 若存儲(chǔ)器由M 2m個(gè)存儲(chǔ)體構(gòu)成 用高m位地址來(lái)選擇不同的存儲(chǔ)體 低n m位為體內(nèi)的地址 當(dāng)高m位不相同時(shí) 便可以訪問(wèn)不同的存儲(chǔ)體 即當(dāng)多個(gè)處理機(jī)發(fā)出的訪存地址高位不相同時(shí) 可對(duì)共享存儲(chǔ)器內(nèi)的不同存儲(chǔ)體進(jìn)行同時(shí)存取 當(dāng)多個(gè)處理機(jī)發(fā)出的訪存地址高位相同時(shí) 即訪存同一存儲(chǔ)體時(shí) 就不能并行操作了 我們稱之為存儲(chǔ)器的分體沖突 高位交叉訪問(wèn)存儲(chǔ)器一般適合于共享存儲(chǔ)器的多機(jī)系統(tǒng) 圖3 3高位交叉的四體交叉存儲(chǔ)器結(jié)構(gòu)示意圖 3 低位交叉訪問(wèn)存儲(chǔ)器圖3 4是低位交叉的四體交叉存儲(chǔ)器結(jié)構(gòu)示意圖 如果主存空間為N 2n字 那么訪問(wèn)該存儲(chǔ)器的地址為n位 若存儲(chǔ)器由M 2m個(gè)存儲(chǔ)體構(gòu)成 用低m位地址來(lái)選擇不同的存儲(chǔ)體 高n m位為體內(nèi)地址 當(dāng)?shù)蚼位不相同時(shí) 便可以訪問(wèn)不同的存儲(chǔ)體 即當(dāng)處理機(jī)發(fā)出的訪存地址訪問(wèn)不同的存儲(chǔ)體時(shí) 地址不一定連續(xù) 可對(duì)存儲(chǔ)器內(nèi)的不同存儲(chǔ)體進(jìn)行并行存取 這里的并行性指的是并發(fā)性 當(dāng)處理機(jī)訪存同一存儲(chǔ)體時(shí) 就不能并行操作了 低位交叉訪問(wèn)存儲(chǔ)器一般適合于單處理機(jī)內(nèi)的高速數(shù)據(jù)存取及帶Cache的主存 在最好的情況下 即一個(gè)模m的多體交叉訪問(wèn)存儲(chǔ)器在不發(fā)生分配沖突時(shí)的帶寬是單體帶寬的m倍 圖3 4低位交叉的四體交叉存儲(chǔ)器結(jié)構(gòu)示意圖 如果模塊的字是與數(shù)據(jù)總線等寬 W位 若模塊存取一個(gè)字的存儲(chǔ)周期是 由m個(gè)子周期 要大于或等于總線傳送周期 組成 即 m 并使用m個(gè)模塊來(lái)交叉存取 則成塊存取可按 間隔流水進(jìn)行 即每經(jīng) 時(shí)間延遲后即啟動(dòng)下一模塊 這樣 連續(xù)讀m個(gè)字所需時(shí)間為 m 1 而順序組織方式卻要m 時(shí)間 顯然加快了成塊存取速度 模四多體交叉存取存儲(chǔ)器的流水存取示意圖如圖3 5所示 圖3 5模四多體交叉存取存儲(chǔ)器的流水存取示意圖 前面講過(guò) 并行主存系統(tǒng)可達(dá)到的最大頻寬Bm W m TM 由這個(gè)式子可以看出 提高模m的值 是能提高主存系統(tǒng)的頻寬的 但主存頻寬并不是隨m值增大而線性提高 也就是說(shuō)其實(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)效率問(wèn)題 對(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é)底來(lái)源于兩者開(kāi)發(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ī)之間通過(guò)總線或互連網(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 高效率的同步原語(yǔ)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ī)適宜于求解通用算法 另外 它能靈活地開(kāi)發(fā)數(shù)據(jù)并行性和功能并行性 而SIMD并行處理機(jī)只能開(kāi)發(fā)數(shù)組和向量中存在的數(shù)據(jù)并行性 因此其通用性較差 6 主要開(kāi)發(fā)高層次作業(yè)及任務(wù)級(jí)并行性 對(duì)于高層次的并行性開(kāi)發(fā) 通常是通過(guò)算法和程序設(shè)計(jì)語(yǔ)言來(lái)描述程序中的顯式并行性 或通過(guò)編譯器 操作系統(tǒng)和硬件來(lái)開(kāi)發(fā)程序中存在的隱式并行性 而SIMD并行處理機(jī)則主要是開(kāi)發(fā)低層次 即操作一級(jí)的并行性 7 并行任務(wù)派生需要用顯式的專用指令來(lái)表示 在MIMD多處理機(jī)中 一個(gè)程序當(dāng)中就存在多個(gè)并發(fā)的程序段 需要專用的指令來(lái)表示它們的并發(fā)關(guān)系以控制它們的并發(fā)執(zhí)行 以便一個(gè)任務(wù)開(kāi)始被執(zhí)行時(shí)就能派生出可與它并行執(zhí)行的另一些任務(wù) 這個(gè)過(guò)程稱為并行任務(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í)的并行性 一般來(lái)說(shuō) 各處理機(jī)在同一時(shí)刻執(zhí)行的是不同的指令 并行任務(wù)派生后 由于空閑處理機(jī)的限制使得所有的新任務(wù)不一定能同時(shí)投入運(yùn)行 又加上各并發(fā)進(jìn)程之間可能存在數(shù)據(jù)相關(guān) 控制相關(guān)等 為保持程序所要求的正確順序 必須采取特殊的措施來(lái)實(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ī)中 程序員只需用屏蔽的手段來(lái)設(shè)置部分處理單元為不活躍狀態(tài) 來(lá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ī)是通過(guò)共享主存來(lái)實(shí)現(xiàn)處理機(jī)間的通信的 各處理機(jī)與主存之間通過(guò)一個(gè)互連網(wǎng)絡(luò)連接 在這種系統(tǒng)中 處理機(jī)間的數(shù)據(jù)通信速率將受限于主存的帶寬 而處理機(jī)的數(shù)目受限于處理機(jī) 主存互連網(wǎng)絡(luò)帶寬以及多臺(tái)處理機(jī)同時(shí)訪問(wèn)主存所引起的沖突概率 為了減少處理機(jī)訪問(wèn)主存的沖突 常采用如下方法 1 多處理機(jī)的主存采用多模塊交叉存取 模塊數(shù)越多 發(fā)生沖突的概率將越低 但必須解決好數(shù)據(jù)在各存儲(chǔ)器模塊中的定位和分配 2 讓每臺(tái)處理機(jī)擁有一個(gè)小容量的局存 用來(lái)存放頻繁使用的核心代碼等 以減少對(duì)主存的訪問(wèn) 3 讓每臺(tái)處理機(jī)都有一個(gè)Cache 以減少對(duì)主存的訪問(wèn) 但必須注意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通道連接起來(lái) 緊耦合多處理機(jī)按所用處理機(jī)類型是否相同可分為同構(gòu)型和異構(gòu)型多處理機(jī) 圖6 1緊耦合多處理機(jī)系統(tǒng)的典型結(jié)構(gòu) 在緊耦合多處理機(jī)中 如果每臺(tái)處理機(jī)在訪問(wèn)任意一個(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ī)直接訪問(wèn) 帶非對(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è)將無(wú)法被其它處理機(jī)所訪問(wèn) 例如 在圖6 2中 若處理機(jī)P1出現(xiàn)故障 則它所接的IOP1將不能被其它處理機(jī)中的任何一個(gè)所訪問(wèn) 因此在很多非對(duì)稱式多處理機(jī)中都采用了適當(dāng)?shù)娜哂噙B接 在一定程度上提高了設(shè)備的利用率 帶冗余連接的非對(duì)稱I O子系統(tǒng)的多處理機(jī)如圖6 3所示 在此圖中 若處理機(jī)P1發(fā)生故障 處理機(jī)Pp仍可以訪問(wèn)IOP1 但這是以增加一個(gè)多通路仲裁邏輯為代價(jià)的 在緊耦合多處理機(jī)中 常見(jiàn)的組合是同構(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)總線還通過(guò)總線適配器與Ethernet局域網(wǎng) SCSI相連 或通過(guò)磁盤控制器與磁盤相連 此外 系統(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ī)是通過(guò)消息傳遞方式來(lái)實(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í) 可通過(guò)網(wǎng)絡(luò)接口電路及消息傳遞系統(tǒng)進(jìn)行信息交換 由于這種相互間的耦合程度是很松散的 因此稱之為松耦合多處理機(jī) 松耦合多處理機(jī)可分為非層次式和層次式兩種結(jié)構(gòu) 1 非層次式松耦合多處理機(jī)圖6 6是一個(gè)典型的通過(guò)消息傳遞系統(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)程之間通過(guò)網(wǎng)絡(luò)接口電路NIC NetworkInterfaceCircuitry 和消息傳遞系統(tǒng)進(jìn)行通信 其中的NIC通常是由通道和仲裁開(kāi)關(guān)CAS ChannelandArbiterSwitch 組成 用于對(duì)兩個(gè)或多個(gè)計(jì)算機(jī)模塊同時(shí)請(qǐng)求訪問(wèn)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ò)開(kāi)關(guān)S經(jīng)MAP總線與其它Cm相連 每個(gè)MAP總線可連接多達(dá)14個(gè)計(jì)算機(jī)模塊Cm 構(gòu)成一個(gè)計(jì)算機(jī)模塊群 cluster 模塊群內(nèi)的各處理機(jī)用較低的通信開(kāi)銷實(shí)現(xiàn)數(shù)據(jù)共享 圖6 7Cm 層次式松耦合多處理機(jī) 與MAP總線相連的Kmap是系統(tǒng)內(nèi)各計(jì)算機(jī)模塊群間的連接器 而各模塊群間的連接是通過(guò)群間雙總線實(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與主存之間的一致性問(wèn)題 6 2 2多處理機(jī)系統(tǒng)的存儲(chǔ)器結(jié)構(gòu) 1 主存的組成 2 多處理機(jī)系統(tǒng)的Cache結(jié)構(gòu)Cache一致性問(wèn)題的原因如果多臺(tái)處理機(jī)在運(yùn)行同一程序時(shí)不存在共享數(shù)據(jù) 或共享數(shù)據(jù)不允許調(diào)入各自的Cache時(shí) 將不會(huì)出現(xiàn)Cache的一致性問(wèn)題 若允許共享數(shù)據(jù)調(diào)入各處理機(jī)的Cache中 并且允許處理機(jī)對(duì)共享數(shù)據(jù)進(jìn)行寫入操作時(shí) 就會(huì)產(chǎn)生各Cache中的共享數(shù)據(jù)之間 Cache與共享存儲(chǔ)器之間的數(shù)據(jù)的不一致 具體來(lái)說(shuō) 有以下三個(gè)方面的原因 1 共享可寫數(shù)據(jù) 2 多處理機(jī)的進(jìn)程遷移 3 繞過(guò)Cache的I O操作 以下以沒(méi)有任何Cache一致性控制的共享存儲(chǔ)器雙處理機(jī)為例說(shuō)明上述原因 處理機(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ù)不一致 由此可見(jiàn) 在多處理機(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)修改過(guò)的x 這將導(dǎo)致共享存儲(chǔ)器及Cache2與處理機(jī)P1中Cache1所緩存的數(shù)據(jù)不一致 C 由繞過(guò)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由繞過(guò)Cache的I O操作引起的不一致 由前面介紹的三種引起Cache不一致的原因 表明了在多處理機(jī)環(huán)境下共享可寫數(shù)據(jù) 進(jìn)行進(jìn)程遷移或I O操作時(shí)采用一致性協(xié)議的必要性 一致性協(xié)議主要有兩種 一種是基于總線的監(jiān)聽(tīng)一致性協(xié)議 snoopycoherencyprotocol 此類協(xié)議需要由總線或環(huán)提供的廣播機(jī)制 通過(guò)監(jiān)聽(tīng)總線 snoopybus 實(shí)現(xiàn) 主要思想是不斷地監(jiān)聽(tīng)總線上處理機(jī)和存儲(chǔ)器模塊間的Cache操作事件 各處理機(jī)根據(jù)監(jiān)聽(tīng)的信息對(duì)各自Cache中的數(shù)據(jù)采取保持一致性的措施 另一種是基于目錄的一致性協(xié)議 此類協(xié)議需要建立一個(gè)Cache目錄 記錄共享數(shù)據(jù)塊的處理機(jī)信息 當(dāng)某一處理機(jī)完成寫操作后 同時(shí)通過(guò)此數(shù)據(jù)塊所在的各目錄項(xiàng) 把一致性命令發(fā)給存放有該數(shù)據(jù)塊拷貝的Cache 使之無(wú)效或更新 但它主要應(yīng)用于具有分布式存儲(chǔ)器模型的多處理機(jī)中 3 監(jiān)聽(tīng)一致性協(xié)議當(dāng)各處理機(jī)的Cache都連接到公共總線時(shí) 為保持Cache的一致性有兩種選擇 一種是采用寫無(wú)效 write invalidate 協(xié)議 另一種是采用寫更新 write update 協(xié)議 寫無(wú)效協(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ǔ)器之間的一致性 通常所說(shuō)的寫直達(dá) WT 法和寫回 WB 法屬于后者 A 寫無(wú)效協(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訪問(wèn)的獨(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è)置為無(wú)效 如圖6 11 c 所示 若使用寫直達(dá)法 當(dāng)處理機(jī)P2想要訪問(wèn)已修改的數(shù)據(jù)x 時(shí) 會(huì)發(fā)生Cache2不命中并從共享存儲(chǔ)器中讀取新值x 并調(diào)入數(shù)據(jù)x 所在的數(shù)據(jù)塊 若使用寫回法 當(dāng)處理機(jī)P2想要訪問(wèn)已修改的數(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寫無(wú)效監(jiān)聽(tīng)協(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í) 它必須通過(guò)廣播x 的方法來(lái)更新x在所有處理機(jī)Cache中的拷貝 當(dāng)其它的處理機(jī)要訪問(wèn)修改過(guò)的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ì)被置為無(wú)效 如圖6 12 c 所示 共享存儲(chǔ)器中的數(shù)據(jù)也可以立即更新 這由所使用的具體實(shí)現(xiàn)方法決定 從上述過(guò)程可以看出 寫更新協(xié)議為保持所有Cache中共享數(shù)據(jù)的高度一致性 需耗費(fèi)大量的總線周期來(lái)更新所有的Cache和共享存儲(chǔ)器中的共享數(shù)據(jù)塊 這無(wú)疑會(huì)加重總線傳輸?shù)呢?fù)擔(dān) 因此在大多數(shù)多處理機(jī)中都選擇使用寫無(wú)效協(xié)議 圖6 12寫更新監(jiān)聽(tīng)協(xié)議 MESI監(jiān)聽(tīng)協(xié)議MESI屬于寫無(wú)效協(xié)議 它根據(jù)所有的讀 寫 命中或不命中和在總線上監(jiān)聽(tīng)的事件來(lái)跟蹤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ī)采用寫無(wú)效協(xié)議正在更新一個(gè)變量并且其它的處理機(jī)也試圖讀該變量時(shí) 則會(huì)發(fā)生讀失效并可能導(dǎo)致總線的流量大大增加 另外 寫更新協(xié)議可以更新遠(yuǎn)程Cache中的數(shù)據(jù) 而其它處理機(jī)可能永遠(yuǎn)也不會(huì)使用這些數(shù)據(jù) 因此 這些問(wèn)題使采用總線來(lái)構(gòu)造大型多處理機(jī)系統(tǒng)受到限制 當(dāng)用多級(jí)網(wǎng)絡(luò)來(lái)構(gòu)造有數(shù)百臺(tái)處理機(jī)的大型系統(tǒng)時(shí) 就必須修改Cache的監(jiān)聽(tīng)協(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ǔ)器來(lái)實(shí)現(xiàn) 因此集中式目錄只適用于具有集中式共享存儲(chǔ)器的小規(guī)模SMP的Cache一致性控制 在分布式目錄中 每個(gè)存儲(chǔ)器模塊維護(hù)了一個(gè)單獨(dú)的目錄來(lái)記錄所有的Cache塊的狀態(tài)和當(dāng)前信息 無(wú)論Cache目錄采用集中方式還是分布方式來(lái)存放 其內(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ù)塊的拷貝 而在有限目錄中 無(wú)論系統(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)為 有效 或 無(wú)效 有效 表示該Cache塊已存在于某臺(tái)處理機(jī)的Cache中 并且為有效狀態(tài) 無(wú)效 表示該Cache塊已存在于某臺(tái)處理機(jī)的Cache中 并且為無(wú)效狀態(tài) 或者在某臺(tái)處理機(jī)的Cache中該塊根本就不存在 污染位表示某一個(gè)Cache塊是否已經(jīng)被修改過(guò) 它有 未寫 和 污染 兩種狀態(tài) 未寫 表示當(dāng)前Cache塊沒(méi)有被修改過(guò) 污染 表示某一個(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中都沒(méi)有單元x的拷貝 當(dāng)三臺(tái)處理機(jī)都對(duì)x有過(guò)讀請(qǐng)求之后 就出現(xiàn)了第二種狀態(tài) 這時(shí) 目錄項(xiàng)中的三個(gè)指針 處理機(jī)位 被置 1 表示這些Cache已有數(shù)據(jù)塊拷貝 在前述這二種狀態(tài)下 目錄項(xiàng)最左邊的污染位被置為未寫 Clean C 狀態(tài) 表示沒(mé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ù)塊 下面再來(lái)詳細(xì)說(shuō)明圖6 15中從第二種狀態(tài)轉(zhuǎn)換到第三種狀態(tài)的過(guò)程 一旦處理機(jī)P3向Cache3發(fā)出請(qǐng)求時(shí) 將發(fā)生以下事件 1 Cache3檢測(cè)出包含單元x的塊是有效的 即P3訪問(wèn)x時(shí)在Cache3中命中 但Cache塊的寫允許位狀態(tài)表示不允許P3對(duì)該塊進(jìn)行寫操作 2 Cache3向包含單元x的存儲(chǔ)器模塊發(fā)寫請(qǐng)求 并暫停P3的工作 3 該存儲(chǔ)器模塊發(fā)出一個(gè)無(wú)效請(qǐng)求給Cache1和Cache2 4 Cache1和Cache2接收到無(wú)效請(qǐng)求后 把相應(yīng)的塊置為無(wú)效狀態(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ī) 至此 全部過(guò)程結(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ǔ)器的開(kāi)銷將與處理機(jī)數(shù)目的平方O N2 成正比 盡管全映射目錄協(xié)議的效率比較高 但由于過(guò)多的存儲(chǔ)器開(kāi)銷 所以不具有可擴(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)行指針的替換 這種指針替換過(guò)程稱為驅(qū)逐 eviction 由于多處理機(jī)系統(tǒng)中的處理機(jī)具有局部性 即在任何給定的時(shí)間間隔內(nèi) 只有一小部分的處理機(jī)訪問(wèn)某個(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è)指針?lè)謩e指向處理機(jī)P1和P2 即在P1和P2的Cache中都有單元x所在的數(shù)據(jù)塊的拷貝 當(dāng)P3請(qǐng)求訪問(wèn)單元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)侥夸浲ㄟ^(guò)將目錄信息分布到多個(gè)小規(guī)模的本地目錄中來(lái)