《《多處理機(jī)》PPT課件》由會員分享，可在線閱讀，更多相關(guān)《《多處理機(jī)》PPT課件（52頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、國 防 科 技 大 學(xué) 計 算 機(jī) 學(xué) 院 一 個 問 題圖 書 館 將 一 批 新 書 上 架 ， 可 以 有 多 種 方 式 。 假 定 將 書 按類 上 架 ， 而 將 書 架 依 據(jù) 在 書 庫 中 的 位 置 分 成 一 些 組 。解 決 辦 法 若 由 一 工 人 單 獨(dú) 完 成 ， 不 能 在 要 求 的 時 間 內(nèi) 完成 任 務(wù) 。 若 由 多 個 工 人 完 成 ， 假 定 每 次 一 人 僅 往 書 架 上 放一 本 書 。 可 以 采 用 兩 種 不 同 的 方 式 ： （ 1） 將 所 有 的 書 籍 平 均 分 配 給 每 個 人 去 完 成 。 這 種 劃分 方 法

2、 不 是 太 有 效 ， 原 因 是 每 個 工 人 為 了 將 書 上 架 必 須走 遍 所 有 的 書 架 。（ 2） 將 所 有 書 架 分 成 一 些 組 ， 且 平 均 分 配 給 各 個 工 人負(fù) 責(zé) ， 同 時 將 所 有 圖 書 平 均 分 配 給 每 個 工 人 去 上 架 。 如果 工 人 發(fā) 現(xiàn) 一 本 書 屬 于 自 己 所 負(fù) 責(zé) 的 書 架 上 ， 則 將 其 放入 書 架 。 否 則 ， 將 這 本 書 傳 給 所 在 書 架 對 應(yīng) 的 工 人 。 這種 分 法 對 應(yīng) 的 效 率 比 較 高 。 結(jié) 論 將 一 個 任 務(wù) 劃 分 成 一 些 子 任 務(wù) ，

3、并 分 配 給 多 個 工人 去 完 成 ， 工 人 們 相 互 合 作 、 并 在 需 要 時 相 互 傳遞 圖 書 ， 這 種 協(xié) 調(diào) 的 工 作 方 式 可 較 快 地 完 成 任 務(wù) 。并 行 計 算 就 是 嚴(yán) 格 地 按 照 上 述 原 理 來 完 成 的 。 并 行 計 算 相 關(guān) 的 兩 個 概 念 任 務(wù) 劃 分 (task partitioning) 將 圖 書 平 均 分 配 給 所 有 工 人 為 任 務(wù) 劃 分 的 一 個 例 子 。 通 信 (communication) 工 人 之 間 傳 遞 圖 書 為 子 任 務(wù) 通 信 的 例 子 。什 么 是 并 行 計

4、算 ？并 行 計 算 是 指 同 時 對 多 個 任 務(wù) 或 多 條 指 令 、 或 對 多 個數(shù) 據(jù) 項 進(jìn) 行 處 理 。 完 成 此 項 處 理 的 計 算 機(jī) 系 統(tǒng) 稱 為 并行 計 算 機(jī) 系 統(tǒng) ， 它 是 將 多 個 處 理 器 通 過 網(wǎng) 絡(luò) 以 一 定 的連 接 方 式 有 序 地 組 織 起 來 。 并 行 計 算 的 研 究 內(nèi) 容 : (1) 并 行 計 算 機(jī) 設(shè) 計 (2) 有 效 算 法 的 設(shè) 計 (3) 評 價 并 行 算 法 的 方 法 (4) 并 行 計 算 機(jī) 語 言 (5) 并 行 編 程 環(huán) 境 與 工 具 (6) 并 行 程 序 的 可 移 植

5、性 (7) 并 行 計 算 機(jī) 的 自 動 編 程 并 行 計 算 的 應(yīng) 用 領(lǐng) 域 ： (1) 天 氣 預(yù) 報 (2) 衛(wèi) 星 數(shù) 據(jù) 處 理 (3) 石 油 數(shù) 據(jù) 處 理 （ 連 續(xù) 優(yōu) 化 問 題 ） (4) 調(diào) 度 問 題 (5) VLSI設(shè) 計 （ 離 散 優(yōu) 化 問 題 ） (6) 天 氣 預(yù) 報 考 慮 3000*3000平 方 公 里 的 范 圍 ， 垂 直 方 向 的 考慮 高 度 為 11公 里 。 將 3000*3000*11立 方 公 里 的 區(qū) 域分 成 0.13立 方 公 里 的 小 區(qū) 域 ， 則 將 近 有 1011個 不 同 的小 區(qū) 域 。 另 外 還

6、需 考 慮 時 間 因 素 ， 將 時 間 參 數(shù) 量 化 。 假定 考 慮 48小 時 天 氣 預(yù) 報 。 每 一 小 區(qū) 域 的 計 算 包 括 參 數(shù) 的 初 始 化 及 與 其 它 區(qū) 域的 數(shù) 據(jù) 交 換 。 若 每 一 小 區(qū) 域 計 算 的 操 作 指 令 為 100條 ，則 整 個 范 圍 一 次 計 算 的 指 令 為 1011*100=1013， 兩 天 的計 算 次 數(shù) 將 近 100次 ， 因 此 ， 指 令 總 數(shù) 為 10 15條 。 用 一臺 10億 次 /秒 (PIII500)計 算 ， 大 約 需 要 280小 時 。 美 國 政 府 的 HPCC計 劃 公

7、布 的 重 大 挑 戰(zhàn) 性 應(yīng) 用1) 磁 記 錄 技 術(shù) ： 研 究 靜 磁 和 交 互 感 應(yīng) 以 降 低 高 密 度 磁 盤的 噪 音2) 新 藥 設(shè) 計 ： 通 過 抑 制 人 的 免 疫 故 障 病 毒 蛋 白 酶 的 作 用來 研 制 治 療 癌 癥 與 艾 滋 病 的 藥 物3) 高 速 民 航 ： 用 計 算 流 體 動 力 學(xué) 來 研 制 超 音 速 噴 氣 發(fā) 動機(jī)4) 催 化 作 用 ： 仿 生 催 化 劑 計 算 機(jī) 建 模 ， 分 析 合 成 過 成 中的 酶 作 用5) 燃 料 燃 燒 ： 通 過 化 學(xué) 動 力 學(xué) 計 算 ， 揭 示 流 體 力 學(xué) 的 作用 ，

8、 設(shè) 計 新 型 發(fā) 動 機(jī)6) 海 洋 建 模 ： 對 海 洋 活 動 與 大 氣 流 的 熱 交 換 進(jìn) 行 整 體 海洋 模 擬 美 國 政 府 的 HPCC計 劃 公 布 的 重 大 挑 戰(zhàn) 性 應(yīng) 用7) 臭 氧 耗 損 ： 研 究 控 制 臭 氧 損 耗 過 程 中 的 化 學(xué) 與 動 力 學(xué)機(jī) 制8) 數(shù) 字 解 析 ： 用 計 算 機(jī) 研 究 適 時 臨 床 成 像 、 計 算 層 析 術(shù) 、磁 共 振 成 像 9) 大 氣 污 染 ： 對 大 氣 質(zhì) 量 模 型 進(jìn) 行 模 擬 研 究 ， 控 制 污 染的 傳 播 ， 揭 示 其 物 理 與 化 學(xué) 機(jī) 理10)蛋 白 質(zhì)

9、結(jié) 構(gòu) 設(shè) 計 ： 對 蛋 白 質(zhì) 組 成 的 三 維 結(jié) 構(gòu) 進(jìn) 行 計 算機(jī) 模 擬 研 究11)圖 像 理 解 ： 實 時 繪 制 圖 像 或 動 態(tài)12)密 碼 破 譯 ： 破 譯 由 長 位 數(shù) 組 成 的 密 碼 ， 尋 找 該 數(shù) 的 兩個 乘 積 因 子 并 行 計 算 的 應(yīng) 用 分 類（ 1） 計 算 密 集 型 （ Compute-Intensive）這 一 類 型 的 應(yīng) 用 問 題 主 要 集 中 在 大 型 科 學(xué) 工 程 計 算 與 數(shù)值 模 擬 （ 氣 象 預(yù) 報 、 地 球 物 理 勘 探 等 ） （ 2） 數(shù) 據(jù) 密 集 型 (Data-Intensive)

10、Internet的 發(fā) 展 ， 為 我 們 提 供 了 大 量 的 數(shù) 據(jù) 資 源 ， 但 有效 地 利 用 這 些 資 源 ， 需 要 進(jìn) 行 大 量 地 處 理 ， 且 對 計 算 機(jī)的 要 求 也 相 當(dāng) 高 ， 這 些 應(yīng) 用 包 括 數(shù) 字 圖 書 館 、 數(shù) 據(jù) 倉 庫 、數(shù) 據(jù) 挖 掘 、 計 算 可 視 化 。（ 3） 網(wǎng) 絡(luò) 密 集 型 (Network-Intensive) 通 過 網(wǎng) 絡(luò) 進(jìn) 行 遠(yuǎn) 距 離 信 息 交 互 ， 來 完 成 用 傳 統(tǒng) 方 法 不 同的 一 些 應(yīng) 用 問 題 。 如 協(xié) 同 工 作 、 遙 控 與 遠(yuǎn) 程 醫(yī) 療 診 斷 等 7.1 引

11、言7.2 多 處 理 機(jī) 的 存 儲 器 體 系 結(jié) 構(gòu)7.3 互 連 網(wǎng) 絡(luò) 7.4 同 步 與 通 信7.5 并 行 化 技 術(shù) 單 處 理 機(jī) 的 發(fā) 展 正 在 走 向 盡 頭 ？并 行 計 算 機(jī) 在 未 來 將 會 發(fā) 揮 更 大 的 作 用 。1. 獲 得 超 過 單 處 理 器 的 性 能 ， 最 直 接 的 方 法 就 是 把 多 個 處 理 器 連 在 一 起 ；2. 自 1985年 以 來 ， 體 系 結(jié) 構(gòu) 的 改 進(jìn) 使 性 能 迅 速 提 高 ， 這 種 改 進(jìn) 的 速 度 能 否 持 續(xù) 下 去 還 不 清 楚 ， 但 通 過 復(fù) 雜 度 和 硅 技 術(shù) 的 提

12、高 而 得 到 的 性 能 的 提 高 正 在 減 小 ；3. 并 行 計 算 機(jī) 應(yīng) 用 軟 件 已 有 緩 慢 但 穩(wěn) 定 的 發(fā) 展 。 7.1 引 言 本 章 重 點(diǎn) : 中 小 規(guī) 模 的 機(jī) 器 (處 理 器 的 個 數(shù) 100) （ 多 處 理 機(jī) 設(shè) 計 的 主 流 ）7.1.1 并 行 計 算 機(jī) 體 系 結(jié) 構(gòu) 的 分 類 1. 按 照 Flynn分 類 法 ， 可 把 計 算 機(jī) 分 成 單 指 令 流 單 數(shù) 據(jù) 流 （ SISD） 單 指 令 流 多 數(shù) 據(jù) 流 （ SIMD） 多 指 令 流 單 數(shù) 據(jù) 流 （ MISD） 多 指 令 流 多 數(shù) 據(jù) 流 （ MIM

13、D） 2. MIMD已 成 為 通 用 多 處 理 機(jī) 體 系 結(jié) 構(gòu) 的 選 擇 ， 原 因 ： (1) MIMD具 有 靈 活 性 。 (2) MIMD可 以 充 分 利 用 商 品 化 微 處 理 器 在 性 能 價 格 比 方 面 的 優(yōu) 勢 。 3. MIMD機(jī) 器 分 為 兩 類 ： （ 每 一 類 代 表 了 一 種 存 儲 器 的 結(jié) 構(gòu) 和 互 連 策 略 ） (1) 集 中 式 共 享 存 儲 器 結(jié) 構(gòu) 這 類 機(jī) 器 有 時 被 稱 為 UMA(uniform memory access)機(jī) 器 。 (2) 分 布 式 存 儲 器 結(jié) 構(gòu) 每 個 結(jié) 點(diǎn) 包 含 ： 在

14、 許 多 情 況 下 ， 分 布 式 存 儲 器 結(jié) 構(gòu) 優(yōu) 于 采 用 集 中 式 共 享 存 儲 器 結(jié) 構(gòu) 。 分 布 式 存 儲 器 結(jié) 構(gòu) 需 要 高 帶 寬 的 互 連 。 處 理 器 存 儲 器 I O 分 布 式 存 儲 器 結(jié) 構(gòu) 的 優(yōu) 點(diǎn) (1) 如 果 大 多 數(shù) 的 訪 問 是 針 對 本 結(jié) 點(diǎn) 的 局 部 存 儲 器 ， 則 可 降 低 對 存 儲 器 和 互 連 網(wǎng) 絡(luò) 的 帶 寬 要 求 ； (2) 對 局 部 存 儲 器 的 訪 問 延 遲 低 。 主 要 缺 點(diǎn) 處 理 器 之 間 的 通 信 較 為 復(fù) 雜 ， 且 各 處 理 器 之 間 訪 問 延 遲

15、 較 大 。 1. 兩 種 地 址 空 間 的 組 織 方 案 (1) 物 理 上 分 離 的 多 個 存 儲 器 可 作 為 一 個 邏 輯 上 共 享 的 存 儲 空 間 進(jìn) 行 編 址 。 這 類 機(jī) 器 的 結(jié) 構(gòu) 被 稱 為 分 布 式 共 享 存 儲 器 (DSM) 或 可 縮 放 共 享 存 儲 器 體 系 結(jié) 構(gòu) 。DSM機(jī) 器 被 稱 為 NUMA(non-uniform memory access)機(jī) 器 。 (2) 整 個 地 址 空 間 由 多 個 獨(dú) 立 的 地 址 空 間 構(gòu) 成 ， 它 們 在 邏 輯 上 也 是 獨(dú) 立 的 ， 遠(yuǎn) 程 的 處 理 器 不 能 對

16、 其 直 接 尋 址 。7.1.2 通 信 模 型 和 存 儲 器 的 結(jié) 構(gòu) 模 型 每 一 個 處 理 器 -存 儲 器 模 塊 實 際 上 是 一 個 單 獨(dú) 的計 算 機(jī) ， 這 種 機(jī) 器 也 稱 為 多 計 算 機(jī) 。2. 兩 種 通 信 模 型 共 享 地 址 空 間 的 機(jī) 器 利 用 Load和 Store指 令 中 的 地 址 隱 含 地 進(jìn) 行 數(shù) 據(jù) 通 信多 個 地 址 空 間 的 機(jī) 器 通 過 處 理 器 間 顯 式 地 傳 遞 消 息 完 成 (消 息 傳 遞 機(jī) 器 )消 息 傳 遞 機(jī) 器 根 據(jù) 簡 單 的 網(wǎng) 絡(luò) 協(xié) 議 ， 通 過 傳 遞 消 息 來

17、請 求 某 些 服 務(wù) 或 傳 輸 數(shù) 據(jù) ， 從 而 完 成 通 信 。 例 如 ： 一 個 處 理 器 要 對 遠(yuǎn) 程 存 儲 器 上 的 數(shù) 據(jù) 進(jìn) 行 訪 問 或 操 作 (1) 發(fā) 送 消 息 ， 請 求 傳 遞 數(shù) 據(jù) 或 對 數(shù) 據(jù) 進(jìn) 行 操 作 ； 遠(yuǎn) 程 進(jìn) 程 調(diào) 用 (RPC， remote process call) (2) 目 的 處 理 器 接 收 到 消 息 以 后 ， 執(zhí) 行 相 應(yīng) 的 操 作 或 代 替 遠(yuǎn) 程 處 理 器 進(jìn) 行 訪 問 ， 并 發(fā) 送 一 個 應(yīng) 答 消 息 將 結(jié) 果 返 回 。 7.1.3 通 信 機(jī) 制 的 性 能 三 個 關(guān) 鍵

18、 的 性 能 指 標(biāo) ： 1. 通 信 帶 寬 理 想 狀 態(tài) 下 的 通 信 帶 寬 受 限 于 處 理 器 、 存 儲 器 和 互 連 網(wǎng) 絡(luò) 的 帶 寬 。 2. 通 信 延 遲 理 想 狀 態(tài) 下 通 信 延 遲 應(yīng) 盡 可 能 地 小 。 通 信 延 遲 發(fā) 送 開 銷 跨 越 時 間 傳 輸 延 遲 接 收 開 銷 3. 通 訊 延 遲 的 隱 藏 如 何 才 能 較 好 地 將 通 信 和 計 算 或 多 次 通 信 之 間 重 疊 起 來 ， 以 實 現(xiàn) 通 信 延 遲 的 隱 藏 。 通 常 的 原 則 是 ： 只 要 可 能 就 隱 藏 延 遲 。 通 信 延 遲 隱 藏

19、是 一 種 提 高 性 能 的 有 效 途 徑 ， 但 它 對 操 作 系 統(tǒng) 和 編 程 者 來 講 增 加 了 額 外 的 負(fù) 擔(dān) 。 1.共 享 存 儲 器 通 信 的 主 要 優(yōu) 點(diǎn) (1) 與 常 用 的 集 中 式 多 處 理 機(jī) 使 用 的 通 信 機(jī) 制 兼 容 。 (2) 當(dāng) 處 理 器 通 信 方 式 復(fù) 雜 或 程 序 執(zhí) 行 動 態(tài) 變 化 時 易 于 編 程 ， 同 時 在 簡 化 編 譯 器 設(shè) 計 方 面 也 占 有 優(yōu) 勢 。 (3) 當(dāng) 通 信 數(shù) 據(jù) 較 小 時 ， 通 信 開 銷 較 低 ， 帶 寬 利 用 較 好 。 (4) 通 過 硬 件 控 制 的

20、Cache減 少 了 遠(yuǎn) 程 通 信 的 頻 度 ， 減 少 了 通 信 延 遲 以 及 對 共 享 數(shù) 據(jù) 的 訪 問 沖 突 。 7.1.4 不 同 通 信 機(jī) 制 的 優(yōu) 點(diǎn) 2. 消 息 傳 遞 通 信 機(jī) 制 的 主 要 優(yōu) 點(diǎn) (1) 硬 件 較 簡 單 。 (2) 通 信 是 顯 式 的 ， 從 而 引 起 編 程 者 和 編 譯 程 序 的 注 意 ， 著 重 處 理 開 銷 大 的 通 信 。 在 共 享 存 儲 器 上 支 持 消 息 傳 遞 相 對 簡 單 ， 但 在 消 息 傳 遞 的 硬 件 上 支 持 共 享 存 儲 器 就 困 難 得 多 。 所 有 對 共 享

21、存 儲 器 的 訪 問 均 要 求 操 作 系 統(tǒng) 提 供 地 址 轉(zhuǎn) 換 和 存 儲 保 護(hù) 功 能 ， 即 將 存 儲 器 訪 問 轉(zhuǎn) 換 為 消 息 的 發(fā) 送 和 接 收 。 并 行 處 理 面 臨 著 兩 個 重 要 的 挑 戰(zhàn) ： （ 可 通 過 Amdahl定 律 解 釋 ）1. 有 限 的 并 行 性 使 機(jī) 器 要 達(dá) 到 好 的 加 速 比 十 分 困 難 。 程 序 中 有 限 的 并 行 性 相 對 較 高 的 通 信 開 銷7.1.5 并 行 處 理 面 臨 的 挑 戰(zhàn) 例 7.1 如 果 想 用 100個 處 理 器 達(dá) 到 80的 加 速 比 ， 求 原 計 算

22、程 序 中 串 行 部 分 所 占 比 例 。解 ： 動 畫 演 示2. 面 臨 的 第 二 個 挑 戰(zhàn) 主 要 是 指 多 處 理 機(jī) 中 遠(yuǎn) 程 訪 問 的 較 大 延 遲 。 在 現(xiàn) 有 的 機(jī) 器 中 ， 處 理 器 之 間 的 數(shù) 據(jù) 通 信 大 約 需 要 50 10000個 時 鐘 周 期 。 機(jī) 器 通 信 機(jī) 制 互 連 網(wǎng) 絡(luò) 處 理 機(jī) 數(shù) 量 典 型 遠(yuǎn) 程 存 儲器 訪 問 時 間SPARC Center 共 享 存 儲 器 總 線 20 1sSG I Challenge 共 享 存 儲 器 總 線 36 1sCray T3D 共 享 存 儲 器 3維 環(huán) 網(wǎng) 32

23、2048 1sConvex Exemplar 共 享 存 儲 器 交 叉 開 關(guān) 環(huán) 8 64 2sK SR-1 共 享 存 儲 器 多 層 次 環(huán) 32 256 2-6s CM-5 消 息 傳 遞 胖 樹 32 1024 10sIntel Paragon 消 息 傳 遞 2維 網(wǎng) 格 32 2048 10-30sIBM SP-2 消 息 傳 遞 多 級 開 關(guān) 2 512 30-100s 遠(yuǎn)程訪問一個字的延遲時間 例 7.2 一 臺 32個 處 理 器 的 計 算 機(jī) ， 對 遠(yuǎn) 程 存 儲 器 訪 問 時 間 為2000ns。 除 了 通 信 以 外 ， 假 設(shè) 計 算 中 的 訪 問 均

24、 命 中 局 部存 儲 器 。 當(dāng) 發(fā) 出 一 個 遠(yuǎn) 程 請 求 時 ， 本 處 理 器 掛 起 。 處 理器 時 鐘 時 間 為 10ns， 如 果 指 令 基 本 的 CPI為 1.0(設(shè) 所 有訪 存 均 命 中 Cache)， 求 在 沒 有 遠(yuǎn) 程 訪 問 的 狀 態(tài) 下 與 有0.5%的 指 令 需 要 遠(yuǎn) 程 訪 問 的 狀 態(tài) 下 ， 前 者 比 后 者 快 多 少 ?解 有 0.5%遠(yuǎn) 程 訪 問 的 機(jī) 器 的 實 際 CPI為 CPI 基 本 CPI 遠(yuǎn) 程 訪 問 率 遠(yuǎn) 程 訪 問 開 銷 1.0 0.5% 遠(yuǎn) 程 訪 問 開 銷 遠(yuǎn) 程 訪 問 開 銷 遠(yuǎn) 程 訪

25、 問 時 間 /時 鐘 時 間 2000ns/10ns 200個 時 鐘 CPI 1.0 0.5% 200 2.0它 為 只 有 局 部 訪 問 的 機(jī) 器 的 2.0 1.0 2倍 ， 因 此 在 沒 有 遠(yuǎn) 程 訪 問 的 狀 態(tài) 下 的 機(jī) 器 速 度 是 有 0.5%遠(yuǎn) 程 訪 問 的 機(jī) 器 速 度 的 2倍 。 問 題 的 解 決 并 行 性 不 足 ： 通 過 采 用 并 行 性 更 好 的 算 法 來 解 決 遠(yuǎn) 程 訪 問 延 遲 的 降 低 ： 靠 體 系 結(jié) 構(gòu) 支 持 和 編 程 技 術(shù) 反 映 并 行 程 序 性 能 的 一 個 重 要 的 度 量 計 算 與 通 信

26、 的 比 率 計 算 通 信 比 率 隨 著 處 理 數(shù) 據(jù) 規(guī) 模 的 增 大 而 增 加 ； 隨 著 處 理 器 數(shù) 目 的 增 加 而 降 低 。7.1.6 并 行 程 序 的 計 算 通 信 比 率 7.2 多 處 理 機(jī) 的 存 儲 器 體 系 結(jié) 構(gòu) 多 個 處 理 器 共 享 一 個 存 儲 器 。 當(dāng) 處 理 器 規(guī) 模 較 小 時 ， 這 種 機(jī) 器 十 分 經(jīng) 濟(jì) 。 支 持 對 共 享 數(shù) 據(jù) 和 私 有 數(shù) 據(jù) 的 Cache緩 存 。 私 有 數(shù) 據(jù) 供 一 個 單 獨(dú) 的 處 理 器 使 用 ， 而 共 享 數(shù) 據(jù) 供 多 個 處 理 器 使 用 。 共 享 數(shù) 據(jù)

27、 進(jìn) 入 Cache產(chǎn) 生 了 一 個 新 的 問 題 ：7.2.1 集 中 式 共 享 存 儲 器 體 系 結(jié) 構(gòu) 1. 多 處 理 機(jī) 的 一 致 性 (1) 不 一 致 產(chǎn) 生 的 原 因 （ Cache一 致 性 問 題 ） I O操 作Cache中 的 內(nèi) 容 可 能 與 由 I O子 系 統(tǒng) 輸 入 輸 出形 成 的 存 儲 器 對 應(yīng) 部 分 的 內(nèi) 容 不 同 。 共 享 數(shù) 據(jù)不 同 處 理 器 的 Cache都 保 存 有 對 應(yīng) 存 儲 器 單 元 的內(nèi) 容 。 例 兩 個 處 理 器 Cache對 應(yīng) 同 一 存 儲 器 單 元 產(chǎn) 生 出 不 同 的 值 (2) 存

28、儲 器 是 一 致 的 （ 非 正 式 地 定 義 ）如 果 對 某 個 數(shù) 據(jù) 項 的 任 何 讀 操 作 均 可 得 到 其 最 新 寫 入的 值 ， 則 認(rèn) 為 這 個 存 儲 系 統(tǒng) 是 一 致 的 。 存 儲 系 統(tǒng) 行 為 的 兩 個 不 同 方 面 返 回 給 讀 操 作 的 是 什 么 值 什 么 時 候 才 能 將 已 寫 入 的 值 返 回 給 讀 操 作 滿 足 條 件 處 理 器 P對 X進(jìn) 行 一 次 寫 之 后 又 對 X進(jìn) 行 讀 ， 讀 和 寫 之 間 沒 有 其 它 處 理 器 對 X進(jìn) 行 寫 ， 則 讀 的 返 回 值 總 是 寫 進(jìn) 的 值 。 一 個

29、處 理 器 對 X進(jìn) 行 寫 之 后 ， 另 一 處 理 器 對 X進(jìn) 行 讀 ， 讀 和 寫 之 間 無 其 它 寫 ， 則 讀 X的 返 回 值 應(yīng) 為 寫 進(jìn) 的 值 。 對 同 一 單 元 的 寫 是 順 序 化 的 ， 即 任 意 兩 個 處 理 器 對 同 一 單 元 的 兩 次 寫 ， 從 所 有 處 理 器 看 來 順 序 都 應(yīng) 是 相 同 的 。 假 設(shè) 直 到 所 有 的 處 理 器 均 看 到 了 寫 的 結(jié) 果 ， 一 次 寫 操 作 才 算 完 成 ； 允 許 處 理 器 無 序 讀 ， 但 必 須 以 程 序 規(guī) 定 的 順 序 進(jìn) 行 寫 。 2. 實 現(xiàn) 一

30、致 性 的 基 本 方 案 在 一 致 的 多 處 理 機(jī) 中 ， Cache提 供 兩 種 功 能 。 共 享 數(shù) 據(jù) 的 遷 移 降 低 了 對 遠(yuǎn) 程 共 享 數(shù) 據(jù) 的 訪 問 延 遲 。 共 享 數(shù) 據(jù) 的 復(fù) 制 不 僅 降 低 了 訪 存 的 延 遲 ， 也 減 少 了 訪 問 共 享 數(shù) 據(jù) 所 產(chǎn) 生 的 沖 突 。小 規(guī) 模 多 處 理 機(jī) 不 是 采 用 軟 件 而 是 采 用 硬 件 技 術(shù)實 現(xiàn) Cache一 致 性 。 (1) Cache一 致 性 協(xié) 議 對 多 個 處 理 器 維 護(hù) 一 致 性 的 協(xié) 議(2) 關(guān) 鍵 ： 跟 蹤 共 享 數(shù) 據(jù) 塊 的 狀

31、態(tài) (3) 共 享 數(shù) 據(jù) 狀 態(tài) 跟 蹤 技 術(shù) 目 錄 物 理 存 儲 器 中 共 享 數(shù) 據(jù) 塊 的 狀 態(tài) 及 相 關(guān) 信 息 均 被 保 存 在 一 個 稱 為 目 錄 的 地 方 。 監(jiān) 聽 每 個 Cache除 了 包 含 物 理 存 儲 器 中 塊 的 數(shù) 據(jù) 拷 貝 之 外 ， 也 保 存 著 各 個 塊 的 共 享 狀 態(tài) 信 息 。 監(jiān) 聽 ： Cache通 常 連 在 共 享 存 儲 器 的 總 線 上 ， 各 個Cache控 制 器 通 過 監(jiān) 聽 總 線 來 判 斷 它 們 是 否 有 總 線 上 請求 的 數(shù) 據(jù) 塊 。 3. 兩 種 協(xié) 議 (1) 寫 作 廢

32、協(xié) 議 在 一 個 處 理 器 寫 某 個 數(shù) 據(jù) 項 之 前 保 證 它 對 該 數(shù) 據(jù) 項有 唯 一 的 訪 問 權(quán) 。 例 ： 在 寫 回 Cache的 條 件 下 ， 監(jiān) 聽 總 線 中 寫 作 廢 協(xié) 議 的 實 現(xiàn) 。 (2) 寫 更 新 協(xié) 議 當(dāng) 一 個 處 理 器 寫 某 數(shù) 據(jù) 項 時 ， 通 過 廣 播 使 其 它 Cache 中 所 有 對 應(yīng) 的 該 數(shù) 據(jù) 項 拷 貝 進(jìn) 行 更 新 。 例 : 寫 回 Cache條 件 下 ， 監(jiān) 聽 總 線 中 寫 更 新 協(xié) 議 的 實 現(xiàn) 。 處 理 器 行 為 總 線 行 為 CPUA Cache內(nèi) 容 CPUB Cach

33、e內(nèi) 容 主 存 X單 元內(nèi) 容 0CPU A 讀 X Cach失 效 0 0CPU B 讀 X Cach失 效 0 0 0 CPUA將 X單 元 寫 1 廣 播 寫 X單 元 1 1 1CPU B 讀 X 1 1 1 (3)寫 作 廢 和 寫 更 新 協(xié) 議 性 能 上 的 差 別 對 同 一 數(shù) 據(jù) 的 多 個 寫 而 中 間 無 讀 操 作 的 情 況 ， 寫 更 新 協(xié) 議 需 進(jìn) 行 多 次 寫 廣 播 操 作 ， 而 在 寫 作 廢 協(xié) 議 下 只 需 一 次 作 廢 操 作 。 對 同 一 塊 中 多 個 字 進(jìn) 行 寫 ， 寫 更 新 協(xié) 議 對 每 個 字 的 寫 均 要 進(jìn)

34、 行 一 次 廣 播 ， 而 在 寫 作 廢 協(xié) 議 下 僅 在 對 本 塊 第 一 次 寫 時 進(jìn) 行 作 廢 操 作 。 從 一 個 處 理 器 寫 到 另 一 個 處 理 器 讀 之 間 的 延 遲 通 常 在 寫 更 新 模 式 中 較 低 。 而 在 寫 作 廢 協(xié) 議 中 ， 需 要 讀 一 個 新 的 拷 貝 。 在 基 于 總 線 的 多 處 理 機(jī) 中 ， 寫 作 廢 協(xié) 議 成 為 絕 大 多 數(shù) 系統(tǒng) 設(shè) 計 的 選 擇 。4. 監(jiān) 聽 協(xié) 議 的 基 本 實 現(xiàn) 技 術(shù) (1) 小 規(guī) 模 多 處 理 機(jī) 中 實 現(xiàn) 寫 作 廢 協(xié) 議 的 關(guān) 鍵利 用 總 線 進(jìn) 行

35、 作 廢 操 作 每 個 塊 的 有 效 位 使 作 廢 機(jī) 制 的 實 現(xiàn) 較 為 容 易 。 (2) 寫 直 達(dá) Cache， 因 為 所 有 寫 的 數(shù) 據(jù) 同 時 被 寫 回 主 存 ， 則 從 主 存 中 總 可 以 取 到 最 新 的 數(shù) 據(jù) 值 。 (3) 對 于 寫 回 Cache， 得 到 數(shù) 據(jù) 的 最 新 值 會 困 難 一 些 ， 因 為 最 新 值 可 能 在 某 個 Cache中 ， 也 可 能 在 主 存 中 。 (4) 在 寫 回 Cache條 件 下 的 實 現(xiàn) 技 術(shù) 用 Cache中 塊 的 標(biāo) 志 位 實 現(xiàn) 監(jiān) 聽 過 程 。 給 每 個 Cache塊

36、 加 一 個 特 殊 的 狀 態(tài) 位 說 明 它 是 否 為 共 享 。 因 為 每 次 總 線 任 務(wù) 均 要 檢 查 Cache的 地 址 位 ， 這 可 能 與 CPU對 Cache的 訪 問 沖 突 。 可 通 過 下 列 兩 種 技 術(shù) 之 一 降 低 沖 突 ： 復(fù) 制 標(biāo) 志 位 采 用 多 級 包 含 Cache。 存 儲 器 分 布 于 各 結(jié) 點(diǎn) 中 ， 所 有 的 結(jié) 點(diǎn) 通 過 網(wǎng) 絡(luò) 互 連 。 訪 問 可 以 是 本 地 的 ， 也 可 是 遠(yuǎn) 程 的 。 不 支 持 Cache一 致 性 ： 規(guī) 定 共 享 數(shù) 據(jù) 不 進(jìn) 入 Cache， 僅 私 有 數(shù) 據(jù) 才

37、 能 保 存 在 Cache中 。 優(yōu) 點(diǎn) ： 所 需 的 硬 件 支 持 很 少 (因 為 遠(yuǎn) 程 訪 問 存 取 量 僅 是 一 個 字 (或 雙 字 )而 不 是 一 個 Cache塊 )7.2.2 分 布 式 共 享 存 儲 器 體 系 結(jié) 構(gòu) 缺 點(diǎn) ： (1) 實 現(xiàn) 透 明 的 軟 件 Cache一 致 性 的 編 譯 機(jī) 制 能 力 有 限 (2) 沒 有 Cache一 致 性 ， 機(jī) 器 就 不 能 利 用 取 出 同 一 塊 中 的 多 個 字 的 開 銷 接 近 于 取 一 個 字 的 開 銷 這 個 優(yōu) 點(diǎn) ， 這 是 因 為 共 享 數(shù) 據(jù) 是 以 Cache塊 為

38、單 位 進(jìn) 行 管 理 的 。 當(dāng) 每 次 訪 問 要 從 遠(yuǎn) 程 存 儲 器 取 一 個 字 時 ， 不 能 有 效 利 用 共 享 數(shù) 據(jù) 的 空 間 局 部 性 。 (3) 諸 如 預(yù) 取 等 延 遲 隱 藏 技 術(shù) 對 于 多 個 字 的 存 取 更 為 有 效 ， 比 如 針 對 一 個 Cache塊 的 預(yù) 取 。 解 決 Cache一 致 性 問 題 的 關(guān) 鍵 ： 目 錄 協(xié) 議 目 錄 ： 用 一 種 專 用 的 存 儲 器 所 記 錄 的 數(shù) 據(jù) 結(jié) 構(gòu) ， 它 記 錄 著 可 以 進(jìn) 入 Cache的 每 個 數(shù) 據(jù) 塊 的 訪 問 狀 態(tài) 、 該 塊 在 各 個 處 理

39、 器 的 共 享 狀 態(tài) 以 及 是 否 修 改 過 等 信 息 。 對 每 個 結(jié) 點(diǎn) 增 加 目 錄 表 后 的 分 布 式 存 儲 器 的 系 統(tǒng) 結(jié) 構(gòu) 。 (1) 目 錄 協(xié) 議 的 基 本 點(diǎn) 在 每 個 結(jié) 點(diǎn) 增 加 了 目 錄 存 儲 器 用 于 存 放 目 錄 ； 存 儲 器 的 每 一 塊 在 目 錄 中 對 應(yīng) 有 一 項 ； 每 一 個 目 錄 項 主 要 有 狀 態(tài) 和 位 向 量 兩 種 成 分 。 狀 態(tài) 描 述 該 目 錄 所 對 應(yīng) 存 儲 塊 的 當(dāng) 前 情 況 ； 位 向 量 共 有 N位 ， 其 每 一 位 對 應(yīng) 于 一 個 處 理 器 的 局 部

40、Cache， 用 于 指 出 該 Cache中 有 無 該 存 儲 塊 的 拷 貝 共 享 在 一 個 或 多 個 處 理 器 上 具 有 這 個 塊 的 拷 貝 ， 且 主 存 中 的 值 是 最 新 值 (所 有 Cache均 相 同 )。 未 緩 沖 所 有 處 理 器 的 Cache都 沒 有 此 塊 的 拷 貝 。 專 有 僅 有 一 個 處 理 器 上 有 此 塊 的 拷 貝 ， 且 已 對 此 塊 進(jìn) 行 了 寫 操 作 ， 而 主 存 的 拷 貝 仍 是 舊 的 。 這 個 處 理 器 稱 為 此 塊 的 擁 有 者 。 (2) 目 錄 必 須 跟 蹤 每 個 Cache塊 的

41、 狀 態(tài) 。 Cache塊 狀 態(tài) 有 三 種 ： (3) 由 于 寫 作 廢 操 作 的 需 要 ， 還 必 須 記 錄 共 享 此 塊 的 處 理 器 信 息 。 方 法 ： 對 每 個 主 存 塊 設(shè) 置 一 個 位 向 量 。 當(dāng) 此 塊 被 共 享 時 ， 每 個 位 指 出 與 之 對 應(yīng) 的 處 理 器 是 否 有 此 塊 的 拷 貝 。 當(dāng) 此 塊 為 專 有 時 ， 可 根 據(jù) 位 向 量 來 尋 找 此 塊 的 擁 有 者 。 (4) 宿 主 結(jié) 點(diǎn) 存 放 有 存 儲 器 塊 和 對 應(yīng) 地 址 目 錄 項 的 結(jié) 點(diǎn) 。 2. 目 錄 協(xié) 議 的 基 本 實 現(xiàn) 技 術(shù)

42、 基 于 目 錄 的 協(xié) 議 中 ， 目 錄 承 擔(dān) 了 一 致 性 協(xié) 議 操 作 的 主 要 功 能 。 (1) 發(fā) 往 一 個 目 錄 的 消 息 會 產(chǎn) 生 兩 種 不 同 類 型 的 動 作 更 新 目 錄 狀 態(tài) 發(fā) 送 消 息 滿 足 請 求 服 務(wù)(2) 目 錄 項 可 能 接 收 到 三 種 不 同 的 請 求 讀 失 效 寫 失 效 數(shù) 據(jù) 寫 回 讀 失 效 將 存 儲 器 數(shù) 據(jù) 送 往 請 求 方 處 理 器 ， 且 本 處 理 器 成 為 此 塊 的 唯 一 共 享 結(jié) 點(diǎn) ， 本 塊 的 狀 態(tài) 轉(zhuǎn) 換 為 共 享 。 寫 失 效 將 存 儲 器 數(shù) 據(jù) 送 往

43、請 求 方 處 理 器 ， 此 塊 成 為 專 有 。(3) 在 各 個 狀 態(tài) 下 所 接 收 到 的 請 求 和 相 應(yīng) 的 操 作 當(dāng) 一 個 塊 處 于 未 緩 沖 狀 態(tài) 時 ， 對 此 塊 發(fā) 出 的 請 求 及 處 理 操 作 為 : 當(dāng) 一 個 塊 是 共 享 狀 態(tài) 時 ， 存 儲 器 中 的 數(shù) 據(jù) 是 其 當(dāng) 前 最 新 值 ， 對 此 塊 發(fā) 出 的 請 求 及 處 理 操 作 為 : 讀 失 效 將 存 儲 器 數(shù) 據(jù) 送 往 請 求 方 處 理 器 ， 并 將 其 加 入 共 享 集 合 。 寫 失 效 將 數(shù) 據(jù) 送 往 請 求 方 處 理 器 ， 對 共 享 集

44、 合 中 所 有 的 處 理 器 發(fā) 送 寫 作 廢 消 息 ， 且 將 共 享 集 合 置 為 僅 含 有 此 處 理 器 ， 本 塊 的 狀 態(tài) 變 為 專 有 。 當(dāng) 某 塊 處 于 專 有 狀 態(tài) 時 ， 本 塊 的 最 新 值 保 存 在 共 享 集 合 指 出 的 擁 有 者 處 理 器 中 ， 從 而 有 三 種 可 能 的 目 錄 請 求 。 讀 失 效 將 “ 取 數(shù) 據(jù) ” 的 消 息 發(fā) 往 擁 有 者 處 理 器 ， 使 該 塊 的 狀 態(tài) 轉(zhuǎn) 變 為 共 享 ， 并 將 數(shù) 據(jù) 送 回 目 錄 結(jié) 點(diǎn) 寫 入 存 儲 器 ， 進(jìn) 而 把 該 數(shù) 據(jù) 返 送 請 求 方

45、 處 理 器 ， 將 請 求 方 處 理 器 加 入 共 享 集 合 。 寫 失 效 本 塊 將 有 一 個 新 的 擁 有 者 。 數(shù) 據(jù) 寫 回 擁 有 者 處 理 器 的 Cache要 替 換 此 塊 時 必 須 將 其 寫 回 ， 從 而 使 存 儲 器 中 有 最 新 拷 貝 (宿 主 結(jié) 點(diǎn) 實 際 上 成 為 擁 有 者 )，此 塊 成 為 非 共 享 ， 共 享 集 合 為 空 。3. 對 基 于 目 錄 的 Cache一 致 性 的 多 種 改 進(jìn) 有 限 映 射 目 錄 鏈 式 結(jié) 構(gòu) 目 錄4. 基 于 目 錄 的 Cache一 致 性 協(xié) 議 是 完 全 由 硬 件 實 現(xiàn) 的 。 此 外 ， 還 可 以 用 軟 硬 結(jié) 合 的 辦 法 實 現(xiàn) 。