計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案課

2014.2.17 計(jì) 算 機(jī) 系 統(tǒng) 結(jié) 構(gòu) 1 3.3 非 線 性 流 水 線 調(diào) 度 技 術(shù) (P64)調(diào) 度 問 題 的 提 出 ： 一 個(gè) 任 務(wù) 在 通 過 非 線 性 流 水 線 時(shí) 對 有 些 功 能 段 要 通 過 多 次 （ 非 線 性 定義 ） ， 所 以 容 易 與 緊 跟 而 來 的 后 繼 任 務(wù) 發(fā) 生 設(shè) 備 爭 用 。 調(diào) 度 機(jī) 構(gòu) 的 作 用 就 是 合 理 安 排 前 后 任 務(wù) 進(jìn) 入 流 水 線 的 時(shí) 間 差 ， 既 要 避免 爭 用 ， 又 要 使 時(shí) 間 差 盡 可 能 少 ， 以 提 高 吞 吐 率 。 下 面 的 實(shí) 例 比 較 簡 單 ， 學(xué) 懂 以 后 再 自 行 閱 讀 教 材 上 的 實(shí) 例 。 2014.2.17 計(jì) 算 機(jī) 系 統(tǒng) 結(jié) 構(gòu) 2 算 法 ： 共 5個(gè) 步 驟第 1步 .分 析 預(yù) 約 表 R 描 述 非 線 性 流 水 線 有 2種 圖 形 ：(a)連 接 圖 ， 僅 給 出 各 段 之 間 的 靜 態(tài)空 間 連 接 關(guān) 系 ；(b)預(yù) 約 表 ， 就 是 一 個(gè) 任 務(wù) 通 過 流 水線 的 時(shí) 空 圖 ， 能 全 面 反 映 該 流 水 線的 動(dòng) 態(tài) 特 性 。 要 檢 驗(yàn) 2個(gè) 任 務(wù) 相 距 k拍 是 否 沖 突 ， 可 將 它 們 的 預(yù) 約 表 錯(cuò) 位 k列 重 疊 （ 上 圖 ） 。第 2步 .作 禁 止 表 F F是 1-N之 間 可 沖 突 拍 數(shù) 的 集 合 ， N是 預(yù) 約 表 的 列 數(shù) 減 1。 具體 操 作 是 將 同 一 行 中 任 意 2個(gè) 標(biāo) 記 之 間 的 拍 數(shù) 差 記 下 來 ， 再 將 各 行 的 這 類 數(shù) 字 匯 成 一 個(gè) 集 合 ， 即 為 禁 止 表 。 本 例 中 F = 3， 4， 6 3.3.1 單 功 能 非 線 性 流 水 線 結(jié) 構(gòu) 調(diào) 度 (P65) 時(shí) 間 段 1 2 3 4 5 6 7 S1 1 1 1 S2 1 1 S3 1 1 S4 1 時(shí) 間 段 1 2 3 4 5 6 7 S1 2 2 2 S2 2 2 S3 2 2 S4 2 2014.2.17 計(jì) 算 機(jī) 系 統(tǒng) 結(jié) 構(gòu) 3 第 3步 .作 原 始 沖 突 向 量 C 為 了 設(shè) 計(jì) 調(diào) 度 機(jī) 構(gòu) ， 需 將 禁 止 表 轉(zhuǎn) 化 為 原 始 沖 突 向 量 C（ Collision） 。 C是 含 N個(gè) 分 量 的 布 爾 向 量 ， 一 般 形 式 為 C = (cN.c1)， 其 中 N是 預(yù) 約 表的 列 數(shù) 減 1， 也 可 以 是 禁 止 表 中 的 最 大 元 素 。 第 i個(gè) 分 量 取 值 原 則 為 ： 本 例 中 C = (101100) Fi Fici ， 當(dāng)， 當(dāng)10 2014.2.17 計(jì) 算 機(jī) 系 統(tǒng) 結(jié) 構(gòu) 4 使 用 沖 突 向 量 C實(shí) 現(xiàn) 調(diào) 度 的 原 理 圖 動(dòng) 態(tài) 沖 突 向 量 （ 初 值 000000）右 移 寄 存 器 ： 0 010110 右 移 出 0“ 或 ” 運(yùn) 算 器 ： 按 位 “ 或 ” 0接 通1斷 開常 量 發(fā) 生 器 ： 101100 原 始 沖 突 向 量 時(shí) 鐘 輸 入 流 水 線 任 務(wù) 排 隊(duì)1.每 個(gè) 時(shí) 鐘 脈 沖 使 流 水 線 中 現(xiàn) 有 任 務(wù) 前 進(jìn) 一 步 ， 也 使 右 移 寄 存 器 移 出 一 位 ；2.如 果 新 任 務(wù) 進(jìn) 入 ， 則 用 它 的 原 始 沖 突 向 量 與 右 移 寄 存 器 內(nèi) 容 相 “ 或 ” 。 2014.2.17 計(jì) 算 機(jī) 系 統(tǒng) 結(jié) 構(gòu) 5 第 4步 .作 狀 態(tài) 轉(zhuǎn) 移 圖 （ P66圖 3.15） 這 是 為 了 研 究 無 窮 多 個(gè) 任 務(wù) 時(shí) 任 務(wù) 之 間 可 能 存 在 的 合 法 間 隔 情 況 。 從 表達(dá) 方 便 考 慮 ， 用 動(dòng) 態(tài) 沖 突 向 量 作 為 狀 態(tài) 變 量 。 具 體 作 圖 方 法 是 ：(1)先 畫 “ 根 結(jié) 點(diǎn) ” ， 它 就 是 第 一 個(gè) 任 務(wù) 進(jìn) 入 后 的 右 移 寄 存 器 狀 態(tài) ， 數(shù) 值 等于 原 始 沖 突 向 量 ；(2)分 析 當(dāng) 前 結(jié) 點(diǎn) 的 各 位 ， 如 果 ci=0則 發(fā) 出 一 個(gè) 旁 標(biāo) i值 的 箭 頭 ， ci=1則 不 能發(fā) 出 箭 頭 ， 因 為 1表 示 “ 禁 止 ” 。 此 外 還 發(fā) 出 一 個(gè) 旁 標(biāo) “ N+1*” 的 箭 頭 ，“ N+1*” 意 為 “ N+1” ；(3)每 個(gè) 箭 頭 末 端 產(chǎn) 生 一 個(gè) 新 的 結(jié) 點(diǎn) ， 其狀 態(tài) 等 于 原 結(jié) 點(diǎn) 狀 態(tài) 右 移 i位 后 與 原 始 沖突 向 量 相 “ 或 ” ； (4)如 果 新 結(jié) 點(diǎn) 狀 態(tài) 與 已 有 的 結(jié) 點(diǎn) 重 復(fù) ，則 取 消 它 ， 箭 頭 指 向 已 有 的 那 個(gè) 結(jié) 點(diǎn) 。 000000 初 態(tài) 1 7* 101100 7* 7* 1 5 2 7* 7* 111110 101111 1 5 2 111111 101101 5 2014.2.17 計(jì) 算 機(jī) 系 統(tǒng) 結(jié) 構(gòu) 6 第 5步 .作 平 均 延 遲 拍 數(shù) 表 （ P67表 3.1）(1)在 狀 態(tài) 轉(zhuǎn) 移 圖 中 尋 找 全 部 簡 單 循環(huán) 填 入 右 表 第 1欄 。 所 謂 簡 單 循 環(huán) 是指 其 中 各 結(jié) 點(diǎn) 僅 通 過 一 次 的 閉 合 路徑 。 注 意 它 不 一 定 要 通 過 根 結(jié) 點(diǎn) ；(2)計(jì) 算 各 簡 單 循 環(huán) 的 平 均 間 隔 拍 數(shù)填 入 右 表 第 2欄 。 平 均 間 隔 拍 數(shù) 等 于該 簡 單 循 環(huán) 中 所 有 數(shù) 字 之 和 除 以 數(shù)字 個(gè) 數(shù) ；(3)取 平 均 延 遲 拍 數(shù) 最 少 的 方 案 作 為最 優(yōu) 方 案 。 本 例 為 (1,1,7)； (4)調(diào) 度 機(jī) 構(gòu) 實(shí) 現(xiàn) ： 計(jì) 數(shù) 器 加 譯 碼 電 路 。 本 例 可 用 模 9計(jì) 數(shù) 器 ， 譯 碼 條 件 是 計(jì)數(shù) 值 等 于 0、 1、 2時(shí) 允 許 進(jìn) 入 流 水 線 。 簡 單 循 環(huán) 平 均 啟 動(dòng) 距 離（ 1,7） 4（ 1,1,7） 3（ 2,7） 4.5（ 2,5） 3.5（ 2,5,7） 4.7（ 5,7） 6（ 5） 5（ 7） 7（ 5,2,7） 4.7 2014.2.17 計(jì) 算 機(jī) 系 統(tǒng) 結(jié) 構(gòu) 7 狀 態(tài) 轉(zhuǎn) 移 圖 畫 法 N Y N Y N Y N Y 開 始 Ci = 0 ? 作 “ 根 結(jié) 點(diǎn) ” （ 填 N 位 原 始 沖 突 向 量 C） i 1 結(jié) 束 本 結(jié) 點(diǎn) 值 C右 移 i 位 ， 與 原 始 沖 突 向 量 C 相 “ 或 ” 結(jié) 果 與 已 有 結(jié) 點(diǎn) 相 同 ? 作 新 結(jié) 點(diǎn) ， 箭 頭 指 向 它 ， 標(biāo) i 箭 頭 指 向 已 有 結(jié) 點(diǎn) ， 標(biāo) i i i + 1 C N ? 箭 頭 指 向 “ 根 結(jié) 點(diǎn) ” ， 標(biāo) N+1* 找 下 一 個(gè) 未 經(jīng) 處 理 的 結(jié) 點(diǎn) 找 到 ? 2014.2.17 計(jì) 算 機(jī) 系 統(tǒng) 結(jié) 構(gòu) 8 右 移 相 “ 或 ” 運(yùn) 算 的 示 例（ 以 課 件 P100轉(zhuǎn) 移 圖 右 下 角 結(jié) 點(diǎn) 為 例 ） ：結(jié) 果 成 為 該 結(jié) 點(diǎn) 上 面 的 新 結(jié) 點(diǎn) 。 本 結(jié) 點(diǎn) 當(dāng) 前 值 ： 101101右 移 2位 之 后 ： 001011原 始 沖 突 向 量 ： 101100 “或 ”運(yùn) 算 結(jié) 果 ： 101111 2014.2.17 計(jì) 算 機(jī) 系 統(tǒng) 結(jié) 構(gòu) 9 3.3.2 多 功 能 非 線 性 流 水 線 結(jié) 構(gòu) 調(diào) 度 (P67)（ 不 講 ） 2014.2.17 計(jì) 算 機(jī) 系 統(tǒng) 結(jié) 構(gòu) 10各 次 作 業(yè) 應(yīng) 交 的 內(nèi) 容 作 業(yè) 4（ 第 4次 課 ）3.10 2 月 19 日 1.10(改 )， 1.7， 1.11(2 解 法 ) 4 月 9 日 7.14(難 題 )， 7.12(難 題 ) 2 月 26 日 2.14(補(bǔ) 充 )， 實(shí) 驗(yàn) 1， 3.8， 3.10 4 月 16 日 8.12(補(bǔ) )， 8.11(改 ) (難 題 ) 3 月 5 日 3.11(改 )， 實(shí) 驗(yàn) 2， 5.11， 5.8， 5.9 4 月 23 日 9.9(改 )， 9.13 3 月 12 日 6.8(改 )， 6.7， 7.9 4 月 30 日 10.6， 10.9(難 題 ) 4 月 2 日 7.11， 7.10