2.4 多 线 程 编 程 的 原 则 及 要 点 : 随 着 多 核 CPU 的 出 世, 多 核 编 程 方 面 的 问 题 将 摆 上 了 程 序 员 的 日 程, 有 许 多 老 的 程 序 员 以 为 早 就 有 多 CPU 的 机 器, 业 界 在 多 CPU 机 器 上 的 编 程 已 经 积 累 了 很 多 经 验, 多 核 CPU 上 的 编 程 应 该 差 不 多, 只 要 借 鉴 以 前 的 多 任 务 编 程 并 行 编 程 和 并 行 算 法 方 面 的 经 验 就 足 够 了 但 是, 多 核 机 器 和 以 前 的 多 CPU 机 器 有 很 大 的 不 同, 以 前 的 多 CPU 机 器 都 是 用 在 特 定 领 域, 比 如 服 务 器, 或 者 一 些 可 以 进 行 大 型 并 行 计 算 的 领 域, 这 些 领 域 很 容 易 发 挥 出 多 CPU 的 优 势, 而 现 在 多 核 机 器 则 是 应 用 到 普 通 用 户 的 各 个 层 面, 特 别 是 客 户 端 机 器 要 使 用 多 核 CPU, 而 很 多 客 户 端 软 件 要 想 发 挥 出 多 核 的 并 行 优 势 恐 怕 没 有 服 务 器 和 可 以 进 行 大 型 并 行 计 算 的 特 定 领 域 简 单 多 核 CPU 中, 要 很 好 地 发 挥 出 多 个 CPU 的 性 能 的 话, 必 须 保 证 分 配 到 各 个 CPU 上 的 任 务 有 一 个 很 好 的 负 载 平 衡 否 则 一 些 CPU 在 运 行, 另 外 一 些 CPU 处 于 空 闲, 无 法 发 挥 出 多 核 CPU 的 优 势 来 要 实 现 一 个 好 的 负 载 平 衡 通 常 有 两 种 方 案, 一 种 是 静 态 负 载 平 衡, 另 外 一 种 是 动 态 负 载 平 衡 1 静 态 负 载 平 衡 静 态 负 载 平 衡 中, 需 要 人 工 将 程 序 分 割 成 多 个 可 并 行 执 行 的 部 分, 并 且 要 保 证 分 割 成 的 各 个 部 分 能 够 均 衡 地 分 布 到 各 个 CPU 上 运 行, 也 就 是 说 工 作 量 要 在 多 个 任 务 间 进 行 均 匀 的 分 配, 使 得 达 到 高 的 加 速 系 数 2 动 态 负 载 平 衡 动 态 负 载 平 衡 是 在 程 序 的 运 行 过 程 中 来 进 行 任 务 的 分 配 达 到 负 载 平 衡 的 目 的 实 际 情 况 中 存 在 许 多 不 能 由 静 态 负 载 平 衡 解 决 的 问 题, 比 如 一 个 大 的 循 环 中, 循 环 的 次 数 是 由 外 部 输 入 的, 事 先 并 不 知 道 循 环 的 次 数, 此 时 采 用 静 态 负 载 平 衡 划 分 策 略 就 很 难 实 现 负 载 平 衡 动 态 负 载 平 衡 中 对 任 务 的 调 度 一 般 是 由 系 统 来 实 现 的, 程 序 员 通 常 只 能 选 择 动 态 平 衡 的 调 度 策 略, 不 能 修 改 调 度 策 略, 由 于 实 际 任 务 中 存 在 很 多 的 不 确 定 因 素, 调 度 算 法 无 法 做 得 很 优, 因 此 动 态 负 载 平 衡 有 时 可 能 达 不 到 既 定 的 负 载 平 衡 要 求 3 负 载 平 衡 的 难 题 在 那 里? 负 载 平 衡 的 难 题 并 不 在 于 负 载 平 衡 的 程 度 要 达 到 多 少, 因 为 即 使 在 各 个 CPU 上 分 配 的 任 务 执 行 时 间 存 在 一 些 差 距, 但 是 随 着 CPU 核 数 的 增 多 总 能 让 总 的 执 行 时 间 下 降, 从 而 使 加 速 系 数 随 CPU 核 数 的 增 加 而 增 加 负 载 平 衡 的 困 难 之 处 在 于 程 序 中 的 可 并 行 执 行 块 很 多 要 靠 程 序 员 来 划 分, 当 然 CPU 核 数 较 少 时, 比 如 双 核 或 4 核, 这 种 划 分 并 不 是 很 困 难 但 随 着 核 数 的 增 加, 划 分 的 粒 度 将 变 得 越 来 越 细, 到 了 16 核 以 上 时, 估 计 程 序 员 要 为 如 何 划 分 任 务 而 抓 狂 比 如 一 段 顺 序 执 行 的 代 码, 放 到 128 核 的 CPU 上 运 行, 要 手 工 划 分 成 128 个 任 务, 其 划 分 的 难 度 可 想 而 知
负 载 划 分 的 误 差 会 随 着 CPU 核 数 的 增 加 而 放 大, 比 如 一 个 需 要 16 个 时 间 单 位 的 程 序 分 到 4 个 任 务 上 执 行, 平 均 每 个 任 务 上 的 负 载 执 行 时 间 为 4 个 时 间 单 位, 划 分 误 差 为 1 个 时 间 单 位 的 话, 那 么 加 速 系 数 变 成 16/(4+1)=3.2, 是 理 想 情 况 下 加 速 系 数 4 的 80% 但 是 如 果 放 到 一 个 16 核 CPU 上 运 行 的 话, 如 果 某 个 任 务 的 划 分 误 差 如 果 为 0.5 个 时 间 单 位 的 话, 那 么 加 速 系 数 变 成 16/(1+0.5) = 10.67, 只 有 理 想 的 加 速 系 数 16 的 66.7%, 如 果 核 数 再 增 加 的 话, 由 于 误 差 的 放 大, 加 速 系 数 相 比 于 理 想 加 速 系 数 的 比 例 还 会 下 降 负 载 划 分 的 难 题 还 体 现 在 CPU 和 软 件 的 升 级 上, 比 如 在 4 核 CPU 上 的 负 载 划 分 是 均 衡 的, 但 到 了 8 核 16 核 上, 负 载 也 许 又 变 得 不 均 衡 了 软 件 升 级 也 一 样, 当 软 件 增 加 功 能 后, 负 载 平 衡 又 会 遭 到 破 坏, 又 需 要 重 新 划 分 负 载 使 其 达 到 平 衡, 这 样 一 来 软 件 设 计 的 难 度 和 麻 烦 大 大 增 加 了 难 题 一 : 串 行 化 方 面 的 难 题 1) 加 速 系 数 衡 量 多 处 理 器 系 统 的 性 能 时, 通 常 要 用 到 的 一 个 指 标 叫 做 加 速 系 数, 定 义 如 下 : S(p) = 使 用 单 处 理 器 执 行 时 间 ( 最 好 的 顺 序 算 法 )/ 使 用 具 有 p 个 处 理 器 所 需 执 行 时 间 2)Amdahl 定 律 并 行 处 理 时 有 一 个 Amdahl 定 律, 用 方 程 式 表 示 如 下 : S(p) = p / (1 + (p-1)*f) 其 中 S(p) 表 示 加 速 系 数 p 表 示 处 理 器 的 个 数 f 表 示 串 行 部 分 所 占 整 个 程 序 执 行 时 间 的 比 例 当 f = 5%, p = 20 时, S(p) = 10.256 左 右 当 f = 5%, p = 100 时, S(p) = 16.8 左 右 也 就 是 说 只 要 有 5% 的 串 行 部 分, 当 处 理 器 个 数 从 20 个 增 加 到 100 个 时, 加 速 系 数 只 能 从 10.256 增 加 到 16.8 左 右, 处 理 器 个 数 增 加 了 5 倍, 速 度 只 增 加 了 60% 多 一 点 即 使 处 理 器 个 数 增 加 到 无 穷 多 个, 加 速 系 数 的 极 限 值 也 只 有 20 如 果 按 照 Amdahl 定 律 的 话, 可 以 说 多 核 方 面 几 乎 没 有 任 何 发 展 前 景, 即 使 软 件 中 只 有 1% 的 不 可 并 行 化 部 分, 那 么 最 大 加 速 系 统 也 只 能 到 达 100, 再 多 的 CPU 也 无 法 提 升 速 度 性 能 按 照 这 个 定 律, 可 以 说 多 核 CPU 的 发 展 让 摩 尔 定 律 延 续 不 了 多 少 年 就 会 到 达 极 限 3)Gustafson 定 律 Gustafson 提 出 了 和 Amdahl 定 律 不 同 的 假 设 来 证 明 加 速 系 数 是 可 以 超 越 Amdahl 定 律 的 限 制 的,Gustafson 认 为 软 件 中 的 串 行 部 分 是 固 定 的, 不 会 随 规 模 的 增 大 而 增 大, 并 假 设 并 行 处 理 部 分 的 执 行 时 间 是 固 定 的 ( 服 务 器 软 件 可 能 就 是 这 样 ) Gustafson 定 律 用 公 式 描 述 如 下 : S(p) = p + (1-p)*fts 其 中 fts 表 示 串 行 执 行 所 占 的 比 例 如 果 串 行 比 例 为 5%, 处 理 器 个 数 为 20 个, 那 么 加 速 系 数 为 20+(1-20)*5%=19.05
如 果 串 行 比 例 为 5%, 处 理 器 个 数 为 100 个, 那 么 加 速 系 数 为 100+(1-100)*5%=95.05 Gustafson 定 律 中 的 加 速 系 数 几 乎 跟 处 理 器 个 数 成 正 比, 如 果 现 实 情 况 符 合 Gustafson 定 律 的 假 设 前 提 的 话, 那 么 软 件 的 性 能 将 可 以 随 着 处 理 个 数 的 增 加 而 增 加 4) 实 际 情 况 中 的 并 行 化 分 析 Amdahl 定 律 和 Gustafson 定 律 的 计 算 结 果 差 距 如 此 之 大, 那 么 现 实 情 况 到 底 是 符 合 那 一 个 定 律 呢? 我 个 人 认 为 现 实 情 况 中 既 不 会 象 Amdahl 定 律 那 么 悲 观, 但 也 不 会 象 Gustafson 定 律 那 么 乐 观 为 什 么 这 样 说 呢? 还 是 进 行 一 下 简 单 的 分 析 吧 首 先 需 要 确 定 软 件 中 到 底 有 那 么 内 容 不 能 并 行 化, 才 能 估 计 出 串 行 部 分 所 占 的 比 例,20 世 纪 60 年 代 时,Bernstein 就 给 出 了 不 能 进 行 并 行 计 算 的 三 个 条 件 : 条 件 1:C1 写 某 一 存 储 单 元 后,C2 读 该 单 元 的 数 据 称 为 写 后 读 竞 争 条 件 2:C1 读 某 一 存 储 单 元 数 据 后,C2 写 该 单 元 称 为 读 后 写 竞 争 条 件 3:C1 写 某 一 存 储 单 元 后,C2 写 该 单 元 称 为 写 后 写 竞 争 满 足 以 上 三 个 条 件 中 的 任 何 一 个 都 不 能 进 行 并 行 执 行 不 幸 的 是 在 实 际 的 软 件 中 大 量 存 在 满 足 上 述 情 况 的 现 象, 也 就 是 我 们 常 说 的 共 享 数 据 要 加 锁 保 护 的 问 题 加 锁 保 护 导 致 的 串 行 化 问 题 如 果 在 任 务 数 量 固 定 的 前 提 下, 串 行 化 所 占 的 比 例 是 随 软 件 规 模 的 增 大 而 减 小 的, 但 不 幸 的 是 它 会 随 任 务 数 量 的 增 加 而 增 加, 也 就 是 说 处 理 器 个 数 越 多, 锁 竞 争 导 致 的 串 行 化 将 越 严 重, 从 而 使 得 串 行 化 所 占 的 比 例 随 处 理 器 个 数 的 增 加 而 急 剧 增 加 所 以 串 行 化 问 题 是 多 核 编 程 面 临 的 一 大 难 题 5) 可 能 的 解 决 措 施 对 于 串 行 化 方 面 的 难 题, 首 先 想 到 的 解 决 措 施 就 是 少 用 锁, 甚 至 采 用 无 锁 编 程, 不 过 这 对 普 通 程 序 员 来 说 几 乎 是 难 以 完 成 的 工 作, 因 为 无 锁 编 程 方 面 的 算 法 太 过 于 复 杂, 而 且 使 用 不 当 很 容 易 出 错, 许 多 已 经 发 表 到 专 业 期 刊 上 的 无 锁 算 法 后 来 又 被 证 明 是 错 的, 可 以 想 象 得 到 这 里 面 的 难 度 有 多 大 第 二 个 解 决 方 案 就 是 使 用 原 子 操 作 来 替 代 锁, 使 用 原 子 操 作 本 质 上 并 没 有 解 决 串 行 化 问 题, 只 不 过 是 让 串 行 化 的 速 度 大 大 提 升, 从 而 使 得 串 行 化 所 占 执 行 时 间 比 例 大 大 下 降 不 过 目 前 芯 片 厂 商 提 供 的 原 子 操 作 很 有 限, 只 能 在 少 数 地 方 起 作 用, 芯 片 厂 商 在 这 方 面 可 能 还 需 要 继 续 努 力, 提 供 更 多 功 能 稍 微 强 大 一 些 的 原 子 操 作 来 避 免 更 多 的 地 方 的 锁 的 使 用 第 三 个 解 决 方 案 是 从 设 计 和 算 法 层 面 来 缩 小 串 行 化 所 占 的 比 例 也 许 需 要 发 现 实 用 的 并 行 方 面 的 设 计 模 式 来 缩 减 锁 的 使 用, 目 前 业 界 在 这 方 面 已 经 积 累 了 一 定 的 经 验, 如 任 务 分 解 模 式, 数 据 分 解 模 式, 数 据 共 享 模 式, 相 信 随 着 多 核 CPU 的 大 规 模 使 用 将 来 会 有 更 多 的 新 的 有 效 的 并 行 设 计 模 式 和 算 法 冒 出 来 第 四 个 解 决 方 案 是 从 芯 片 设 计 方 面 来 考 虑 的 主 要 的 想 法 是 在 芯 片 层 面 设 计 一 些 新 的 指 令, 这 些 指 令 不 象 以 前 单 核 CPU 指 令 那 样 是 由 单 个 CPU 完 成 的, 而 是 由 多 个 CPU 进 行 并 行 处 理 完 成 的 一 些 并 行 指 令, 这 样 程 序 员 调 用 这 些 并 行 处 理 指 令 编 程 就 象 编 写 串 行 化 程 序 一 样, 但 又 充 分 利 用 上 了 多 核 的 优 势
前 面 我 们 提 到 了 锁 竞 争 会 让 程 序 中 的 串 行 化 比 例 随 使 用 的 CPU 的 核 数 增 多 而 加 剧 的 现 象, 现 在 我 们 就 来 对 多 核 编 程 中 的 锁 竞 争 进 行 深 入 的 分 析 为 了 简 化 起 见, 我 们 先 看 一 个 简 单 的 情 况, 假 设 有 4 个 对 等 的 任 务 同 时 启 动 运 行, 假 设 每 个 任 务 刚 开 始 时 有 一 个 需 要 锁 保 护 的 操 作, 耗 时 为 1, 每 个 任 务 其 他 部 分 的 耗 时 为 25 这 几 个 任 务 启 动 运 行 后 的 运 行 情 况 如 下 图 所 示 : 图 2.9: 对 等 任 务 的 锁 竞 争 示 意 图 在 上 图 中, 可 以 看 出 第 1 个 任 务 直 接 执 行 到 结 束, 中 间 没 有 等 待, 第 2 个 任 务 等 待 了 1 个 时 间 单 位, 第 3 个 任 务 等 待 了 2 个 时 间 单 位, 第 3 个 任 务 等 待 了 3 个 时 间 单 位 这 样 整 个 任 务 总 计 等 待 了 6 个 时 间 单 位, 如 果 这 几 个 任 务 是 采 用 OpenMP 里 的 所 有 任 务 都 在 同 一 点 上 进 行 等 待 到 全 部 任 务 执 行 完 再 向 下 执 行 时, 那 么 总 的 运 行 时 间 将 和 第 四 个 任 务 一 样 为 29 个 时 间 单 位, 加 速 系 数 为 :( 1 + 4 25)/ 29 = 3.48 即 使 以 4 个 任 务 的 平 均 时 间 27.5 来 进 行 计 算, 加 速 系 数 =101/27.5 = 3.67 按 照 Amdahl 定 律 来 计 算 加 速 系 数 的 话, 上 述 应 用 中, 串 行 时 间 为 1, 并 行 处 理 的 总 时 间 转 化 为 串 行 后 为 100 个 时 间 单 位, 如 果 放 在 4 核 CPU 上 运 行 的 话, 加 速 系 数 =p / (1 + (p-1)*f) = 4/(1+(4-1)*1/101) = 404/104 = 3.88 这 就 产 生 了 一 个 奇 怪 的 问 题, 使 用 了 锁 之 后, 加 速 系 数 连 阿 姆 尔 达 定 律 计 算 出 来 的 加 速 系 数 都 不 如, 更 别 说 用 Gustafson 定 律 计 算 的 加 速 系 数 了 其 实 可 以 将 上 面 4 个 任 务 的 锁 竞 争 情 况 推 广 到 更 一 般 的 情 况, 假 设 有 锁 保 护 的 串 行 化 时 间 为 1, 可 并 行 化 部 分 在 单 核 CPU 上 的 运 行 时 间 为 t,cpu 核 数 为 p, 那 么 在 p 个 对 等 任 务 同 时 运 行 情 况 下, 锁 竞 争 导 致 的 总 等 待 时 间 为 :1+2+ +p = p*(p-1)/2
耗 时 最 多 的 一 个 任 务 所 用 时 间 为 : (p-1) + t/p 使 用 耗 时 最 多 的 一 个 任 务 所 用 时 间 来 当 作 并 行 运 行 时 间 的 话, 加 速 系 数 如 下 S(p) = t / (p-1 + t/p) = p*t / (p*(p-1)+t) ( 锁 竞 争 下 的 加 速 系 数 公 式 ) 这 个 公 式 表 明 在 有 锁 竞 争 情 况 下, 如 果 核 数 固 定 情 况 下, 可 并 行 化 部 分 越 大, 那 么 加 速 系 数 将 越 大 在 并 行 化 时 间 固 定 的 情 况 下, 如 果 CPU 核 数 越 多, 那 么 加 速 系 数 将 越 小 还 是 计 算 几 个 实 际 的 例 子 来 说 明 上 面 公 式 的 效 果 : 令 t=100, p=4, 加 速 系 数 =4 100 / (4*(4-1)+100) = 3.57 令 t=100, p=16, 加 速 系 数 =16 100 / (16*(16-1)+100) = 4.7 令 t=100, p=64, 加 速 系 数 =64 100 / (64*(64-1)+100) = 1.54 令 t=100, p=128, 加 速 系 数 =128 100 / (128*(128-1)+100) = 0.78 从 以 上 计 算 可 以 看 出, 当 核 数 多 到 一 定 的 时 候, 加 速 系 数 不 仅 不 增 加 反 而 下 降, 核 数 增 加 到 128 时, 加 速 系 数 只 有 0.78, 还 不 如 在 单 核 CPU 上 运 行 的 速 度 上 面 的 例 子 中, 锁 保 护 导 致 的 串 行 代 码 是 在 任 务 启 动 时 调 用 的, 其 实 对 等 任 务 中 在 其 他 地 方 调 用 的 锁 保 护 的 串 行 代 码 也 是 一 样 的 对 等 型 任 务 的 锁 竞 争 现 象 在 实 际 情 况 中 是 很 常 见 的, 比 如 服 务 器 软 件, 通 常 各 个 客 户 端 处 理 任 务 都 是 对 等 的, 如 果 在 里 面 使 用 了 锁 的 话, 那 么 很 容 易 造 成 上 面 说 的 加 速 系 数 随 CPU 核 数 增 多 而 下 降 的 现 象 以 前 的 服 务 器 软 件 一 般 运 行 在 双 CPU 或 四 CPU 机 器 上, 所 以 锁 竞 争 导 致 的 加 速 系 数 下 降 现 象 不 明 显, 进 入 多 核 时 代 后, 随 着 CPU 核 数 的 增 多, 这 个 问 题 将 变 得 很 严 重, 所 以 多 核 时 代 对 程 序 设 计 提 出 了 新 的 挑 战 以 前 的 多 任 务 下 的 编 程 思 想 放 到 多 核 编 程 上 不 一 定 行 得 通 所 以 简 单 地 认 为 多 核 编 程 和 以 前 的 多 任 务 编 程 或 并 行 计 算 等 同 的 话 是 不 切 实 际 的 当 然 由 于 目 前 市 面 上 销 售 的 多 核 CPU 还 是 双 核 和 四 核 的, 等 到 16 核 以 上 的 CPU 大 规 模 进 入 市 场 可 能 还 有 几 年 时 间, 相 信 业 界 在 未 来 的 几 年 内 能 够 对 于 上 面 对 等 任 务 上 的 锁 竞 争 问 题 找 到 更 好 的 解 决 方 案