中 国 科 学 技 术 大 学 保 密 博 士 学 位 论 文 多 核 环 境 中 系 统 软 件 访 存 与 同 步 优 化 问 题 的 研 究 作 者 姓 名 : 学 科 专 业 : 导 师 姓 名 : 林 传 文 计 算 机 应 用 技 术 吴 曼 青 研 究 员 顾 乃 杰 教 授 完 成 时 间 : 二 一 二 年 五 月

Secret University of Science and Technology of China A dissertation for doctor s degree The System Software Optimization of Memory Access and Synchronization in Multicore Environment Author s Name: Lin Chuanwen Speciality: Supervisor: Computer Application Technology Researcher Wu Manqing Professor Gu Naijie Finished time: May 2012

中 国 科 学 技 术 大 学 学 位 论 文 原 创 性 声 明 本 人 声 明 所 呈 交 的 学 位 论 文, 是 本 人 在 导 师 指 导 下 进 行 研 究 工 作 所 取 得 的 成 果 除 已 特 别 加 以 标 注 和 致 谢 的 地 方 外, 论 文 中 不 包 含 任 何 他 人 已 经 发 表 或 撰 写 过 的 研 究 成 果 与 我 一 同 工 作 的 同 志 对 本 研 究 所 做 的 贡 献 均 已 在 论 文 中 作 了 明 确 的 说 明 作 者 签 名 : 签 字 日 期 : 中 国 科 学 技 术 大 学 学 位 论 文 授 权 使 用 声 明 作 为 申 请 学 位 的 条 件 之 一, 学 位 论 文 著 作 权 拥 有 者 授 权 中 国 科 学 技 术 大 学 拥 有 学 位 论 文 的 部 分 使 用 权, 即 : 学 校 有 权 按 有 关 规 定 向 国 家 有 关 部 门 或 机 构 送 交 论 文 的 复 印 件 和 电 子 版, 允 许 论 文 被 查 阅 和 借 阅, 可 以 将 学 位 论 文 编 入 有 关 数 据 库 进 行 检 索, 可 以 采 用 影 印 缩 印 或 扫 描 等 复 制 手 段 保 存 汇 编 学 位 论 文 本 人 提 交 的 电 子 文 档 的 内 容 和 纸 质 论 文 的 内 容 相 一 致 保 密 的 学 位 论 文 在 解 密 后 也 遵 守 此 规 定 公 开 保 密 ( 年 ) 作 者 签 名 : 导 师 签 名 : 签 字 日 期 : 签 字 日 期 :

摘 要 摘 要 多 核 架 构 以 其 性 能 和 功 耗 方 面 的 综 合 优 势, 已 经 成 为 微 处 理 器 的 主 流 结 构 多 核 架 构 通 过 在 单 个 芯 片 上 集 成 多 个 处 理 器 核 来 提 升 处 理 器 的 性 能 多 核 处 理 器 强 大 的 计 算 能 力 需 要 通 过 并 行 程 序 充 分 利 用 但 是, 由 于 访 存 和 同 步 等 因 素 的 制 约 使 得 并 行 应 用 程 序 很 难 充 分 利 用 多 核 处 理 器 的 计 算 能 力 其 中, 存 储 器 系 统 的 延 迟 和 带 宽 很 难 匹 配 多 核 处 理 器 强 大 的 计 算 能 力 ; 低 效 的 同 步 机 制 则 往 往 会 导 致 某 些 处 理 器 核 等 待 而 产 生 停 顿, 进 而 降 低 了 多 核 处 理 器 的 计 算 资 源 利 用 率 针 对 上 述 问 题, 系 统 软 件 需 要 在 访 存 和 同 步 方 面 进 行 优 化, 充 分 利 用 多 核 处 理 器 提 供 的 硬 件 资 源, 提 高 并 行 应 用 程 序 的 运 行 性 能 针 对 系 统 软 件 的 访 存 和 同 步 优 化 问 题, 本 文 主 要 研 究 编 译 器 和 Java 虚 拟 机 中 的 访 存 优 化 问 题, 以 及 Java 虚 拟 机 中 的 同 步 机 制 优 化 问 题 本 文 的 主 要 工 作 和 创 新 如 下 : 1) 分 簇 结 构 数 字 信 号 处 理 器 的 SIMD 编 译 优 化 针 对 数 字 信 号 处 理 应 用, 本 文 提 出 分 簇 结 构 数 字 信 号 处 理 器 的 SIMD 编 译 优 化 框 架 主 要 工 作 包 括 : 针 对 数 字 信 号 处 理 应 用 的 特 点, 提 出 基 于 访 存 指 令 的 SIMD 指 令 识 别 算 法 ; 针 对 分 簇 结 构 SIMD 指 令 的 特 点, 提 出 基 于 SIMD 指 令 的 指 令 分 簇 和 寄 存 器 分 配 算 法 ; 并 且 在 BWDSP100 编 译 器 中 实 现 了 上 述 优 化 算 法 实 验 结 果 表 明, 本 文 提 出 的 SIMD 优 化 方 法 能 够 在 分 簇 结 构 上 识 别 并 生 成 高 效 的 SIMD 代 码, 可 以 极 大 地 提 高 BWDSP100 处 理 器 上 应 用 程 序 的 带 宽 利 用 率 和 运 行 性 能 2) Java 虚 拟 机 中 的 动 态 锁 cache 优 化 基 于 编 译 方 法 的 调 用 规 律, 本 文 给 出 Java 虚 拟 机 中 的 动 态 锁 cache 优 化 方 法 主 要 工 作 包 括 : 通 过 分 析 Java 虚 拟 机 中 编 译 方 法 的 调 用 规 律, 得 到 编 译 方 法 的 活 跃 时 间 段 平 均 大 小 和 内 存 分 布 情 况 ; 根 据 编 译 方 法 的 上 述 规 律, 在 Java 虚 拟 机 进 行 动 态 的 锁 cache 优 化, 将 活 跃 的 编 译 方 法 锁 在 cache 中 实 验 结 果 表 明, 本 文 提 出 的 锁 cache 优 化 方 法 只 需 要 将 较 小 的 内 存 区 域 锁 在 cache 中, 就 能 够 在 Java 虚 拟 机 运 行 时 获 得 较 大 的 cache 性 能 提 升 3) Java 虚 拟 机 中 的 只 读 锁 优 化 针 对 只 读 临 界 区 的 特 点, 本 文 提 出 Java 虚 拟 机 中 的 只 读 锁 优 化 框 架 主 要 工 作 包 括 : 提 出 即 时 编 译 器 中 的 只 读 临 界 区 识 别 算 法 ; 提 出 基 于 MIPS 体 系 结 构 LL/SC 同 步 指 令 的 轻 量 级 只 读 锁 优 化 算 法 ; 提 出 重 量 级 只 读 锁 优 化 算 法 轻 量 级 只 读 锁 优 化 算 法 可 以 在 没 有 线 程 竞 争 的 情 况 下 降 低 同 步 操 作 的 开 销 ; 重 量 I

摘 要 级 只 读 锁 优 化 算 法 则 可 以 允 许 多 个 线 程 同 时 进 入 只 读 临 界 区, 提 高 线 程 竞 争 情 况 下 同 步 操 作 的 性 能 实 验 结 果 表 明, 本 文 提 出 的 只 读 锁 优 化 方 法 可 以 极 大 降 低 线 程 进 入 和 退 出 只 读 临 界 区 的 开 销, 提 高 Java 虚 拟 机 的 同 步 性 能 基 于 国 产 处 理 器 的 软 硬 件 平 台, 本 文 在 系 统 软 件 的 访 存 和 同 步 优 化 问 题 研 究 中 取 得 了 一 系 列 有 价 值 的 成 果, 有 效 地 提 高 了 国 产 处 理 器 上 应 用 软 件 的 性 能, 进 而 推 动 国 产 处 理 器 芯 片 的 市 场 化 关 键 词 : 多 核 处 理 器 分 簇 结 构 编 译 优 化 单 指 令 流 多 数 据 流 Java 虚 拟 机 锁 cache 即 时 编 译 器 只 读 锁 同 步 机 制 II

Abstract Abstract With the advantages of performance and power, the multicore architecture has become the mainstream structure of microprocessors. Multicore architecture integrates multiple processor cores on a single chip to improve the performance of processor. The parallel program is used to take advantage of the computing power provided by multicore processors. However, the constraints of memory access and synchronization make it difficult for parallel programs to play the full effectiveness of multicore processors. Latency and bandwidth of the memory system are difficult to match the powerful computing performance of multicore processors; and inefficient synchronization mechanisms often lead to some processor cores waiting, thus reducing the resource utilization of multicore processor. In order to overcome the above problems, it is necessary to do the optimization of memory access and synchronization in system softwares. This can take full advantage of hardware resources provided by multicore processors and improve the performance of parallel applications. For the optimization of memory access and synchronization in system softwares, this paper focuses on the research of memory access optimization in the compiler and Java Virtual Machine, and synchronization optimization in the Java Virtual Machine. The main work and innovations are as follows: 1) SIMD optimization for clustered VLIW DSP For digital signal processing applications, this paper proposes a SIMD compiler optimization framework based on clustered DSP. The main work include: a SIMD instruction identification algorithm is presented for the features of digital signal processing applications; a new cluster assignment algorithm and register allocation algorithm are given for the features of SIMD instructions on the cluster architecture and the above algorithms have been implemented on the BWDSP100 compiler. The experimental results show that the SIMD optimization methods mentioned above can effectively identify and generate efficient SIMD code on the clustered DSP, and greatly improve the bandwidth utilization and performance of the applications on BWDSP100 processor. 2) Dynamic cache locking optimization in Java Virtual Machine Based on the calling parttern of compiled methods, a dynamic cache locking optimization algorithm in JVM is presented. The main work include: according to III

Abstract analyzing the calling parttern of the compiled methods in JVM, the calling distribution parttern, average size and memory distribution of compiled methods can be obtained; based on the above partterns of compiled methods, the dynamic cache locking optimization is implemented in JVM to lock the active compiled methods in cache. The experimental results show that this cache locking method improves the run-time cache performance of JVM, just by locking a small memory area in the cache. 3) Read-Only Lock Optimization in Java Virtual Machine For the features of read-only critical section, this paper presents a read-only lock optimization framework in JVM. The main work include: a recognition algorithm of read-only critical sections in JIT; a lightweight read-only lock optimization algorithm, based on the LL/SC synchronization instructions; and a heavyweight read-only lock optimization algorithm. The read-only optimization algorithm of the lightweight lock can reduce the overhead of synchronous operations, in case there is no competition between threads; and the read-only optimization algorithm of the heavyweight lock can allow multiple threads simultaneously access to the read-only critical sections, when several threads compete at the same time. The experimental results show that the read-only lock optimization method significantly reduces the overhead when the threads enter and exit read-only critical section, and improve the synchronization performance of JVM. Based on the hardware and software platforms of domestic processors, this thesis achieves some valuable innovations in the memory access and synchronization optimization of system softwares. These can effectively improve the performance of applications in the domestic processors, and promote the marketization of the domestic processors. Key Words: Multicore Processors, Cluster Architecture, Compiler Optimization, SIMD, Java Virtual Machine, Cache Locking, Just-In-Time Compiler, Read-Only Lock, Synchronization Mechanism IV

目 录 目 录 摘 要... I 第 1 章 绪 论... 1 1.1 研 究 背 景... 2 1.1.1 多 核 处 理 器... 2 1.1.2 多 核 处 理 器 的 存 储 系 统... 3 1.1.3 多 核 处 理 器 的 核 间 同 步... 6 1.2 国 内 外 研 究 现 状... 7 1.2.1 系 统 软 件 中 访 存 优 化 相 关 研 究... 7 1.2.2 系 统 软 件 中 同 步 机 制 优 化 相 关 研 究... 9 1.3 本 文 的 研 究 内 容... 11 1.4 本 文 的 组 织 结 构... 13 第 2 章 BWDSP100 编 译 器 与 龙 芯 JAVA 虚 拟 机 研 究 平 台... 15 2.1 引 言... 15 2.2 BWDSP100 体 系 结 构... 15 2.3 BWDSP100 编 译 器... 17 2.3.1 IMPACT 编 译 器... 17 2.3.2 BWDSP100 编 译 器 的 开 发... 18 2.4 龙 芯 高 性 能 处 理 器 体 系 结 构... 22 2.4.1 GS464 处 理 器 核 的 基 本 结 构... 22 2.4.2 龙 芯 3 号 4 核 处 理 器 的 基 本 结 构... 23 2.5 龙 芯 JAVA 虚 拟 机... 24 2.5.1 Openjdk Java 虚 拟 机... 24 2.5.2 龙 芯 Java 虚 拟 机 的 开 发... 26 2.6 本 文 使 用 的 性 能 测 试 程 序... 27 2.7 本 章 小 结... 28 第 3 章 分 簇 VLIW DSP 的 SIMD 编 译 优 化... 31 3.1 引 言... 31 3.2 相 关 工 作... 32 3.3 BWDSP100 的 分 簇 结 构 SIMD 指 令... 33 V

目 录 3.4 基 于 访 存 指 令 的 SIMD 指 令 识 别 算 法... 35 3.4.1 循 环 检 测... 36 3.4.2 循 环 展 开... 36 3.4.3 常 规 优 化... 36 3.4.4 变 量 重 命 名... 36 3.4.5 循 环 不 变 量 和 累 加 变 量 扩 展... 37 3.4.6 合 成 SIMD 指 令... 37 3.4.7 实 例 分 析... 39 3.5 基 于 SIMD 指 令 的 指 令 分 簇 算 法... 40 3.6 基 于 SIMD 指 令 的 寄 存 器 分 配 算 法... 41 3.7 实 验 结 果... 42 3.7.1 循 环 展 开 因 子 的 确 定... 43 3.7.2 SIMD 优 化 效 果... 44 3.8 本 章 小 结... 46 第 4 章 JAVA 虚 拟 机 中 的 动 态 锁 CACHE 优 化... 47 4.1 引 言... 47 4.2 相 关 工 作... 48 4.2.1 提 高 程 序 确 定 性 的 锁 cache 优 化 相 关 研 究... 48 4.2.2 提 高 程 序 性 能 的 锁 cache 优 化 相 关 研 究... 49 4.3 龙 芯 3A 的 锁 CACHE 机 制... 50 4.4 JAVA 虚 拟 机 的 即 时 编 译 系 统... 51 4.5 JAVA 虚 拟 机 的 编 译 方 法 调 用 规 律... 53 4.5.1 编 译 方 法 的 调 用 分 布... 53 4.5.2 编 译 方 法 的 大 小... 54 4.5.3 编 译 方 法 的 内 存 分 布... 55 4.6 JAVA 虚 拟 机 中 的 动 态 锁 CACHE 优 化 算 法... 56 4.7 实 验 结 果 和 分 析... 58 4.7.1 Java 虚 拟 机 的 运 行 时 cache 命 中 率 提 升... 58 4.7.2 Java 虚 拟 机 的 运 行 时 性 能 提 升... 59 4.8 本 章 小 结... 60 第 5 章 JAVA 虚 拟 机 中 的 只 读 锁 优 化... 61 5.1 引 言... 61 5.2 相 关 工 作... 62 5.3 JAVA 虚 拟 机 HOTSPOT 的 锁 机 制 简 介... 63 5.4 即 时 编 译 器 中 的 只 读 临 界 区 识 别 算 法... 65 VI

目 录 5.5 JAVA 虚 拟 机 中 的 只 读 锁 优 化 方 法... 66 5.5.1 Java 虚 拟 机 的 只 读 锁 优 化 框 架... 66 5.5.2 基 于 LL/SC 同 步 指 令 的 轻 量 级 只 读 锁 优 化 算 法... 68 5.5.3 Java 虚 拟 机 中 的 重 量 级 只 读 锁 优 化 算 法... 70 5.6 实 验 结 果 和 分 析... 71 5.6.1 单 线 程 Java 程 序 的 性 能 提 升... 72 5.6.2 多 线 程 Java 程 序 的 性 能 提 升... 73 5.6.3 与 Openjdk 读 写 锁 的 性 能 对 比... 74 5.6.4 SPECjvm2008 测 试 用 例 的 性 能 提 升... 75 5.7 本 章 小 结... 76 第 6 章 总 结... 77 6.1 引 言... 77 6.2 本 文 工 作 总 结... 77 6.3 本 文 的 主 要 创 新... 78 6.4 下 一 步 研 究 工 作... 79 参 考 文 献... 81 致 谢... 91 在 读 期 间 发 表 的 学 术 论 文 与 取 得 的 研 究 成 果... 93 VII

目 录 图 目 录 图 1.1 处 理 器 中 晶 体 管 数 量 的 增 长 曲 线... 2 图 1.2 处 理 器 与 存 储 器 的 性 能 差 距... 4 图 1.3 存 储 器 系 统 的 层 次 结 构... 4 图 1.4 龙 芯 4 核 架 构 的 cache 层 次 结 构... 5 图 1.5 Intel 4 核 Sandy Bridge 架 构 的 cache 层 次 结 构... 5 图 1.6 英 特 尔 的 单 芯 片 云 计 算 机 架 构... 7 图 2.1 BWDSP100 的 基 本 结 构... 16 图 2.2 IMPACT 编 译 器 的 基 本 框 架... 18 图 2.3 BWDSP100 编 译 器 的 代 码 生 成 模 块... 20 图 2.4 GS464 处 理 器 核 的 基 本 结 构... 23 图 2.5 龙 芯 3A 处 理 器 的 基 本 结 构... 24 图 2.6 HotSpot 虚 拟 机 的 基 本 体 系 结 构... 25 图 2.7 HotSpot 虚 拟 机 的 执 行 引 擎 基 本 结 构... 26 图 3.1 BWDSP100 的 SIMD 汇 编 代 码 段... 34 图 3.2 BWDSP100 中 SIMD 指 令 的 执 行 过 程... 35 图 3.3 BWSIMD 算 法 构 架... 35 图 3.4 SIMD 指 令 识 别 的 实 例... 39 图 3.5 SIMD_RegAlloc 算 法 流 程... 42 图 3.6 convolution 实 验 结 果... 44 图 3.7 dot_product 实 验 结 果... 44 图 3.8 DSPstone 实 验 结 果... 45 图 4.1 Java 虚 拟 机 的 即 时 编 译 系 统... 52 图 4.2 Java 虚 拟 机 中 编 译 方 法 的 执 行 频 率... 54 图 4.3 Java 虚 拟 机 中 编 译 方 法 的 本 地 代 码 段 大 小... 55 图 4.4 Java 虚 拟 机 运 行 时 编 译 方 法 的 内 存 分 布... 56 图 4.5 Java 虚 拟 机 中 的 动 态 锁 cache 优 化 算 法... 57 图 4.6 动 态 锁 cache 优 化 前 后 直 接 读 内 存 操 作 对 比... 59 图 4.7 动 态 锁 cache 优 化 前 后 SPECjvm2008 的 性 能 对 比... 60 图 5.1 HotSpot 中 标 记 字 的 状 态... 63 图 5.2 HotSpot 虚 拟 机 中 的 同 步 状 态 转 换... 64 图 5.3 只 读 临 界 区 识 别 算 法... 66 图 5.4 HotSpot 虚 拟 机 锁 操 作 的 层 次 结 构... 67 图 5.5 Java 虚 拟 机 只 读 锁 操 作 的 层 次 结 构... 68 图 5.6 轻 量 级 锁 只 读 锁 申 请... 69 图 5.7 轻 量 级 锁 只 读 锁 释 放... 69 图 5.8 重 量 级 锁 只 读 优 化 算 法... 71 图 5.9 重 量 级 锁 只 读 优 化 算 法... 71 图 5.10 单 线 程 Java 测 试 用 例 运 行 时 间 对 比... 72 图 5.11 只 读 锁 优 化 前 后 多 线 程 Java 测 试 用 例 的 性 能 加 速 比... 73 图 5.12 Java 虚 拟 机 只 读 锁 与 Openjdk 读 写 锁 的 性 能 加 速 比... 74 VIII

目 录 图 5.13 SPECjvm2008 中 锁 操 作 的 频 率... 75 图 5.14 只 读 锁 优 化 前 后 SPECjvm2008 性 能 对 比... 76 IX

目 录 表 目 录 表 2.1 DSPstone 测 试 程 序 的 功 能 描 述... 29 表 2.2 SPECjvm2008 测 试 程 序 功 能 描 述... 29 表 4.1 二 级 Cache 的 锁 窗 口 寄 存 器 组... 51 X