lecture13

Lecture 13: Cache V 1

Cache 大 小 Block 大 小 和 缺 失 率 的 关 系 Cache 性 能 由 缺 失 率 确 定, 而 缺 失 率 与 Cache 大 小 Block 大 小 Cache 级 数 等 有 关 Cache 大 小 :Cache 越 大,Miss 率 越 低, 但 成 本 越 高! Block 大 小 :Block 大 小 与 Cache 大 小 有 关, 且 不 能 太 大, 也 不 能 太 小!

Block Size Tradeoff ( 块 大 小 的 选 择 ) 块 大 能 很 好 利 用 spatial locality, BUT: 块 大, 则 需 花 更 多 时 间 读 块, 缺 失 损 失 变 大 块 大, 则 Cache 行 数 变 少, 缺 失 率 上 升 Average Access Time: = Hit Time x (1 - Miss Rate) + Miss Penalty x Miss Rate Miss Penalty Miss Rate Exploits Spatial Locality Fewer blocks: compromises temporal locality Average Access Time Increased Miss Penalty & Miss Rate Block Size Block Size Block Size 所 以, 块 大 小 必 须 适 中!

系 统 中 的 Cache 数 目 刚 引 入 Cache 时 只 有 一 个 Cache 近 年 来 多 Cache 系 统 成 为 主 流 多 Cache 系 统 中, 需 考 虑 两 个 方 面 : [1] 单 级 / 多 级? 片 内 (On-chip)Cache: 将 Cache 和 CPU 作 在 一 个 芯 片 上 外 部 (Off-chip)Cache: 不 做 在 CPU 内 而 是 独 立 设 置 一 个 Cache 单 级 Cache: 只 用 一 个 片 内 Cache 多 级 Cache: 同 时 使 用 L1 Cache 和 L2 Cache, 有 些 高 端 系 统 甚 至 有 L3 Cache,L1 Cache 更 靠 近 CPU, 其 速 度 比 L2 快, 其 容 量 比 L2 大 [2] 联 合 / 分 立? 分 立 : 指 数 据 和 指 令 分 开 存 放 在 各 自 的 数 据 和 指 令 Cache 中 一 般 L1 Cache 都 是 分 立 Cache, 为 什 么? L1 Cache 的 命 中 时 间 比 命 中 率 更 重 要! 为 什 么? 联 合 : 指 数 据 和 指 令 都 放 在 一 个 Cache 中 一 般 L2 Cache 都 是 联 合 Cache, 为 什 么? L2 Cache 的 命 中 率 比 命 中 时 间 更 重 要! 为 什 么? 因 为 缺 失 时 需 从 主 存 取 数, 并 要 送 L1 和 L2cache, 损 失 大!

多 核 处 理 器 中 的 多 级 Cache

多 级 cache 的 性 能 采 用 L2 Cache 的 系 统, 其 缺 失 损 失 的 计 算 如 下 : 若 L2 Cache 包 含 所 请 求 信 息, 则 缺 失 损 失 为 L2 Cache 访 问 时 间 否 则 访 问 主 存, 并 取 到 L1 Cache 和 L2 Cache( 缺 失 损 失 更 大 ) 例 子 : 某 处 理 器 在 无 cache 缺 失 时 CPI 为 1, 时 钟 频 率 为 5GHz 假 定 访 问 一 次 主 存 的 时 间 ( 包 括 所 有 的 缺 失 处 理 ) 为 100ns, 平 均 每 条 指 令 在 L1 Cache 中 的 缺 失 率 为 2% 若 增 加 一 个 L2 Cache, 其 访 问 时 间 为 5ns, 而 且 容 量 足 够 大 到 使 全 局 缺 失 率 减 为 0.5%, 问 处 理 器 执 行 指 令 的 速 度 提 高 了 多 少? 解 : 如 果 只 有 一 级 Cache, 则 缺 失 只 有 一 种 即 L1 缺 失 ( 需 访 问 主 存 ), 其 缺 失 损 失 为 :100nsx5GHz=500 个 时 钟,CPI=1+500x2%=11.0 如 果 有 二 级 Cache, 则 有 两 种 缺 失 : L1 缺 失 ( 需 访 问 L2 Cache):5nsx5GHz=25 个 时 钟 L1 和 L2 都 缺 失 ( 需 访 问 主 存 ):500 个 时 钟 因 此,CPI=1+25x2%+500x0.5%=4.0 二 者 的 性 能 比 为 11.0/4.0=2.8 倍!

Cache 性 能 评 估 与 改 善 CPU 时 间 :CPU 执 行 时 间 + 等 待 内 存 访 问 时 间 即 : CPU 时 间 =(CPU 时 钟 数 +Cache 缺 失 引 起 阻 塞 的 时 钟 数 ) X 时 钟 周 期 Cache 缺 失 引 起 阻 塞 的 时 钟 数 = 读 操 作 阻 塞 时 钟 数 + 写 操 作 阻 塞 时 钟 数 读 操 作 阻 塞 时 钟 数 =( 读 的 次 数 / 程 序 ) x 读 缺 失 率 x 读 缺 失 损 失 写 操 作 的 情 况 较 复 杂 : 回 写 (write back): 替 换 时, 需 要 一 次 性 回 写 一 个 块, 故 会 产 生 一 些 附 加 回 写 阻 塞 写 操 作 阻 塞 时 钟 数 =( 写 次 数 / 程 序 ) x 写 缺 失 率 x 写 缺 失 损 失 + 回 写 阻 塞 直 写 (write through): 包 括 写 缺 失 和 write buffer 阻 塞 两 部 分 写 操 作 阻 塞 时 钟 数 =( 写 次 数 / 程 序 ) x 写 缺 失 率 x 写 缺 失 损 失 + 写 缓 冲 阻 塞 假 定 回 写 阻 塞 或 写 缓 冲 阻 塞 可 以 忽 略 不 计, 则 可 将 读 和 写 综 合 考 虑 : 内 存 阻 塞 时 钟 数 =( 访 存 次 数 / 程 序 ) x 缺 失 率 x 缺 失 损 失 内 存 阻 塞 时 钟 数 =( 指 令 条 数 / 程 序 ) x ( 缺 失 数 / 指 令 ) x 缺 失 损 失

举 例 : 缺 失 带 来 的 损 失 到 底 多 大? 设 代 码 Cache 缺 失 率 为 2%, 数 据 Cache 缺 失 率 为 4% 假 定 一 个 CPU 在 没 有 任 何 存 储 阻 塞 时 CPI 为 2, 缺 失 损 失 为 100 个 时 钟 如 果 用 SPECint2000 衡 量, 则 使 用 无 缺 失 Cache 时 CPU 速 度 会 快 多 少? 分 析 过 程 如 下 : 指 令 的 缺 失 时 钟 数 为 :Ix2%x100=2.0xI SPECint2000 的 访 存 指 令 (Load 和 Store) 频 度 为 :36%, 所 以 数 据 的 缺 失 时 钟 数 为 :Ix36%x4%x100=1.44xI 指 令 和 数 据 总 的 缺 失 时 钟 数 为 :2xI+1.44xI=3.44I, 也 即 : 平 均 每 条 指 令 要 有 3.44 个 时 钟 处 在 存 储 器 阻 塞 状 态 因 此, 因 为 存 储 器 阻 塞 而 使 得 CPI 数 增 大 到 2+3.44=5.44. 故 : CPU time with stalls CPU time with perfect cache = IxCPIstallxClock cycle IxCPIperfectxClock cycle = 5.44 如 果 Cache 不 发 生 缺 失, 则 CPU 速 度 会 快 2.72 倍 2

举 例 : 处 理 器 速 度 提 高 而 存 储 器 不 变 时 的 情 况 例 1: 假 定 上 例 中 CPI 减 为 1, 时 钟 宽 度 不 变, 则 : 因 为 存 储 器 阻 塞 而 使 得 CPI 数 增 大 到 1+3.44=4.44. 故 : CPU time with stalls CPU time with perfect cache = IxCPIstallxClock cycle = 4.44 IxCPIperfectxClock cycle 1 由 此 可 知 : 存 储 器 阻 塞 所 花 时 间 占 整 个 执 行 时 间 的 比 例 从 : 3.44 / 5.44=63% 上 升 到 3.44 / 4.44=77% 结 论 :CPI 越 小,Cache 阻 塞 的 影 响 越 大

举 例 : 处 理 器 速 度 提 高 而 存 储 器 不 变 时 的 情 况 例 2: 假 定 上 例 中 时 钟 频 率 加 倍, CPI 不 变, 则 : 主 存 速 度 不 会 改 变, 故 绝 对 时 间 不 变, 所 以 缺 失 损 失 为 200 个 时 钟 每 条 指 令 发 生 的 总 缺 失 时 钟 数 为 2%x200+36%x(4%x200)=6.88 故 : 存 储 器 阻 塞 使 得 CPI 数 增 大 到 2+6.88=8.88 时 钟 快 的 机 器 的 性 能 时 钟 慢 的 机 器 的 性 能 = IxCPIslow xclock cycle IxCPIfast xclock cycle/2 = 5.44 8.88/2 =1.23 由 此 可 知 : 时 钟 快 的 机 器 的 性 能 只 是 较 慢 时 钟 机 器 的 1.2 倍 如 果 没 有 Cache 缺 失 的 话, 应 该 是 2 倍! 结 论 :CPU 时 钟 频 率 越 高,Cache 缺 失 损 失 就 越 大 上 述 两 个 例 子 说 明 : 处 理 器 性 能 越 高, 高 速 缓 存 的 性 能 就 越 重 要!

设 计 支 持 Cache 的 存 储 器 系 统 指 令 执 行 若 发 生 Cache 缺 失, 必 须 到 DRAM 中 取 数 据 或 指 令 在 DRAM 和 Cache 之 间 传 输 的 单 位 是 Block 问 题 : 怎 样 的 存 储 器 组 织 使 得 Block 传 输 最 快 ( 缺 失 损 失 最 小 )? 假 定 存 储 器 访 问 过 程 : CPU 发 送 地 址 到 内 存 :1 个 总 线 时 钟 访 问 内 存 的 初 始 化 时 间 :10 个 总 线 时 钟 从 总 线 上 传 送 一 个 字 :1 个 总 线 时 钟 CPU MM 可 以 有 三 种 不 同 的 组 织 形 式! 假 定 一 个 Block 有 4 个 字, 则 缺 失 损 失 各 为 多 少 时 钟?

设 计 支 持 Cache 的 存 储 器 系 统 假 定 存 储 器 访 问 过 程 : CPU 发 送 地 址 到 内 存 :1 个 总 线 时 钟 内 存 访 问 时 间 :10 个 总 线 时 钟 从 总 线 上 传 送 一 个 字 :1 个 总 线 时 钟 4x(1+10+1)=48 缺 失 损 失 为 48 个 时 钟 周 期 代 价 小, 但 速 度 慢!

假 定 存 储 器 访 问 过 程 : 设 计 支 持 Cache 的 存 储 器 系 统 CPU 发 送 地 址 到 内 存 :1 个 总 线 时 钟 内 存 访 问 时 间 :10 个 总 线 时 钟 从 总 线 上 传 送 一 个 Block:1 个 总 线 时 钟 Two-word: 2x(1+10+1)=24 Four-word: 1+10+1=12 缺 失 损 失 各 为 24 或 12 个 时 钟 周 期 速 度 快, 但 代 价 大!

设 计 支 持 Cache 假 定 存 的 储 存 器 访 储 问 器 过 系 程 : 统 CPU 发 送 地 址 到 内 存 :1 个 总 线 时 钟 内 存 访 问 时 间 :10 个 总 线 时 钟 从 总 线 上 传 送 一 个 字 :1 个 总 线 时 钟 Interleaved four banks one-word: 1+1x10+4x1=15 缺 失 损 失 为 15 个 时 钟 周 期 代 价 小, 而 且 速 度 快!

复 习 :SPARCstation 20 s Memory Module DRAM Chip 15 512 cols DRAM Chip 0 256K x 8 = 2 Mb One page 512 rows 256K x 8 = 2 Mb 8 bits 512 8 SRAM bits<127:120> 行 缓 冲 512 8 SRAM bits<7:0> 交 叉 编 址 方 式! Memory Bus<127:0> Cache 行 读 从 内 存 读 一 块 连 续 数 据 区 只 要 给 定 一 个 首 地 址, 后 续 数 据 连 续 读 出, 称 为 突 ( 猝 ) 发 传 输 方 式

复 习 :128MB 的 DRAM 存 储 器 ( 行 地 址 i, 列 地 址 j) 交 叉 编 址 方 式! DRAM 0 8 个 芯 片 同 时 读 出! 若 再 构 DRAM 7 成 多 个 模 块, 地 址 A 4096 行 则 可 轮 流 启 动 每 个 模 块 进 行 bits 56-63 bits 48-55 bits 40-47 bits 32-39 bits 24-31 bits 16-23 bits 8-15 bits 0-7 读 写! 芯 片 容 量 : 16MB=4096X4096X8 位 63 56 55 48 47 40 39 32 31 24 23 16 15 8 7 主 存 储 器 地 址 A 处 的 64-bit 数 据 64-bit 双 字 0 存 储 控 制 器 : 行 列 地 址 为 (i,j) 的 8 个 单 元

实 例 : 奔 腾 机 的 Cache 组 织 主 存 :4GB=2 20 x 2 7 块 x 2 5 B/ 块 Cache:8KB=128 组 x2 行 / 组 替 换 算 法 : LRU, 每 组 一 位 LRU 位 该 位 为 0, 下 次 淘 汰 第 0 路 ; 该 位 为 1, 下 次 淘 汰 第 1 路 写 策 略 : 默 认 为 Write Back, 可 动 态 设 置 为 Write Through Cache 一 致 性 : 支 持 MESI 协 议

是 MIPS 结 构 的 嵌 入 式 微 处 理 器 Hit V Tag 18 tag 实 例 : 内 置 FastMATH 处 理 器 31 Index Memory Address 2 18 8 4 2 Byte offset 1 512 data 各 Cache 有 : 256 (16KB / 64B) 行 0 Byte 5 Block offset Mux Word 256 lines 1 8 32 32 32 = 3 Mux 3 2 4 Data 写 比 读 复 杂! CPU 提 供 了 写 通 过 和 写 回 两 种 方 式, 由 OS 决 定 采 用 何 种 策 略 SPEC2000int 的 指 令 数 据 和 综 合 缺 失 率 分 别 为 :0.4%, 11.4%, 3.2%

前 端 总 线 总 线 接 口 部 件 预 取 控 制 逻 辑 L2 cache (48GB/s) 实 例 :Pentium 4 的 cache 存 储 器 64 位, 时 钟 频 率 有 3 个 cache, 分 成 两 级 : L1cache 指 令 cache 及 指 令 预 取 部 件 数 据 缓 存 (L1 数 据 cache), ),8KB 指 令 缓 存, 8KB L2 cache, 容 量 为 256 KB~2MB 256 位, 时 钟 频 率 L1 数 据 cache(8kb)

缓 存 在 现 代 计 算 机 中 无 处 不 在 问 题 : 缓 存 技 术 可 以 应 用 在 哪 些 方 面? 问 题 : 缓 存 技 术 的 实 现 手 段 和 目 的 各 是 什 么?

小 结 引 入 Cache 的 基 础 是 程 序 访 问 的 局 部 化 特 性 引 入 Cache 减 少 了 对 内 存 的 访 问,CPU 能 在 快 速 的 Cache 中 得 到 信 息 Cache 和 主 存 之 间 的 映 射 方 式 直 接 映 射 ( 模 映 射 ): 地 址 = 标 记 行 索 引 块 内 地 址 全 相 联 映 射 ( 全 映 射 ): 地 址 = 标 记 块 内 地 址 组 相 联 映 射 ( 组 间 模 映 射, 组 内 全 映 射 ): 地 址 = 标 记 组 索 引 块 内 地 址 如 何 提 高 cache 的 命 中 率? 增 大 cache 容 量, 适 中 的 块 大 小 采 用 多 级 cache 技 术 (L1 / L2 / L3) 采 用 快 速 查 找 算 法, 并 采 用 并 行 判 定 是 否 命 中 缺 失 时, 采 用 有 效 替 换 算 法, 淘 汰 cache 中 暂 不 使 用 的 内 容 编 译 器 优 化 目 标 程 序 程 序 员 写 出 cache-friendly 的 程 序 Cache 的 写 策 略 Write Back 和 Write Through