学位论文 > 优秀研究生学位论文题录展示

多核系统下并行节点复制垃圾收集算法研究

作　者: 吴长茂
导　师: 张聪品
学　校: 河南师范大学
专　业: 计算机软件与理论
关键词: 多核垃圾收集 Lisp 2算法节点复制算法并行
分类号: TP332
类　型: 硕士论文
年　份: 2011年
下　载: 15次
引　用: 0次
阅　读: 论文下载

内容摘要

随着面向对象语言和程序设计方法的广泛使用,垃圾收集日益受到重视。垃圾收集,即自动内存管理,是指运行时系统负责自动回收无用对象的一种―废料‖回收机制。当代流行语言如Java、C#语言等都具有垃圾收集功能。垃圾收集机制的出现,使程序员只需专注于对象的分配,而无需考虑对象何时被销毁,垃圾对象的回收由垃圾收集器在后台动态地完成而毋须程序员干预。垃圾收集避免了内存泄漏和不正确的内存操作(如悬挂引用)引起的软件错误,提高了软件健壮性。然而,垃圾收集器回收垃圾对象时造成用户程序反应迟缓,一定程度上影响了用户程序效率和用户体验。因此,如何缩短垃圾回收时间,提高垃圾收集器效率,对于提高用户程序执行效率和改善用户体验具有重要的应用价值。近年来,多核CPU和多核GPU日益普及,以及它们并行计算性能的提高,为垃圾收集并行化提供了坚实的硬件基础。在多核系统下,本文基于Lisp 2算法提出了一种新颖的节点复制算法以及该算法的并行化算法,并分别给出了该并行化算法在多核CPU和多核GPU下的一个实现。围绕多核系统下并行节点复制垃圾收集算法研究,本文重点完成了以下工作:(1)深入研究了常用垃圾收集算法。通过查阅大量的垃圾收集文献,对常用垃圾收集算法如引用计数算法、标记-清扫算法、标记-压缩算法、节点复制算法、分代式算法特别是并行垃圾收集算法进行了深入研究,比较了这些算法的优缺点及适用环境。(2)基于Lisp 2算法,提出了一种新颖的节点复制垃圾收集算法-- Lisp 2-Copying-GC-Algorithm。基本思想是把Lisp 2垃圾收集算法在整个内存堆上收集改为在节点复制算法的一个半区(称为FromSpace半区)上进行,把存活对象复制到另一个半区(称为ToSpace半区)。(3)提出了Lisp 2-Copying-GC-Algorithm算法的并行化算法--并行节点复制垃圾收集算法(Lisp 2-Parallel-Copying-GC)。基本思想是把内存堆的两个半区(FromSpace半区和ToSpace半区)划分为大小相同的块(block),为块定义了6个不同状态,这些状态标识了在垃圾收集过程中块(block)的不同地位和作用。这样,块为并行垃圾收集线程提供了一个收集尺度,而块的状态为并行垃圾收集线程间的同步提供了保障。(4)给出了并行节点复制垃圾收集算法(Lisp 2-Parallel-Copying-GC)在多核CPU环境下基于OpenMP3.0规范的一个实现。OpenMP是一种面向共享内存以及分布式共享内存的多处理器(多核)多线程并行编程语言,是一种多线程、共享内存的并行应用程序编程接口。实验数据显示,在4个逻辑核心下该算法加速比达到了2.53,提高了垃圾收集效率。(5)给出了并行节点复制垃圾收集算法(Lisp 2-Parallel-Copying-GC)在多核GPU环境下基于NVIDIA CUDA(Compute Unified Device Architecture)架构的一个实现。CUDA是NVIDIA并行计算架构,通过利用GPU使计算能力大幅提高。本文首次在垃圾收集领域利用CUDA加速进行了有益尝试。实验结果表明,得益于多核GPU数量众多的处理核心和轻量级线程设计,多核GPU相对多核CPU的加速比达到了278.13。多核环境下多线程并行垃圾收集提高了垃圾收集效率,改善了用户体验。

全文目录

摘要  4-6
ABSTRACT  6-12
第一章引言  12-18
  1.1 垃圾收集的历史  12
  1.2 垃圾收集软件的地位和层次  12-14
  1.3 课题意义  14-17
    1.3.1 课题研究背景：多核系统的普及  14
    1.3.2 垃圾收集减轻了程序员的负担  14-15
    1.3.3 垃圾收集增强了软件的健壮性  15-16
    1.3.4 并行垃圾收集提高了收集效率  16-17
  1.4 本文结构  17-18
第二章垃圾收集算法  18-28
  2.1 引用计数算法  18-19
  2.2 标记清扫算法  19-20
  2.3 标记-缩并算法  20-23
  2.4 节点复制算法  23-25
  2.5 分代式算法  25
  2.6 并行收集算法  25-26
  2.7 小结  26-28
第三章多核CPU 并行节点复制垃圾收集算法与实现  28-46
  3.1 多核CPU 概述  28-30
    3.1.1 多核CPU 的产生  28-29
    3.1.2 多核CPU 编程模型  29
    3.1.3 OpenMP 并行编程  29-30
  3.2 基于Lisp 2 算法的节点复制垃圾收集算法  30-32
  3.3 多核CPU 下基于Lisp 2 算法的并行节点复制垃圾收集  32-40
    3.3.1 Lisp 2-Copying-GC-Algorithm 算法并行化的方法  32-33
    3.3.2 并行标记阶段  33-35
    3.3.3 并行迁移地址计算阶段  35-38
    3.3.4 并行引用修正阶段  38-39
    3.3.5 并行移动对象阶段  39-40
  3.4 实验设计  40-43
    3.4.1 算法的数据结构  40-42
    3.4.2 硬件配置  42-43
    3.4.3 软件配置  43
  3.5 实验结果分析  43-44
  3.6 小结  44-46
第四章多核GPU 并行节点复制垃圾收集算法与实现  46-56
  4.1 多核GPU 概述  46-47
  4.2 CUDA 编程模型  47-49
    4.2.1 主机与设备  47-48
    4.2.2 Kernel 函数  48-49
    4.2.3 线程层次结构  49
  4.3 多核GPU 下基于LISP2 的并行节点复制垃圾收集  49-53
    4.3.1 多核GPU 下垃圾收集过程  50-51
    4.3.2 并行标记阶段  51
    4.3.3 并行迁移地址计算阶段  51-52
    4.3.4 并行引用更新阶段  52-53
    4.3.5 并行移动对象阶段  53
  4.4 实验设计  53-54
    4.4.1 硬件配置  54
    4.4.2 软件配置  54
  4.5 实验结果分析  54-55
  4.6 小结  55-56
第五章回顾与展望  56-59
  5.1 完成的工作  56-57
    5.1.1 常用垃圾收集算法的研究  56
    5.1.2 提出了Lisp 2-Copying-GC-Algorithm 算法  56
    5.1.3 提出了并行化的Lisp 2-Parallel-Copying-GC 算法  56-57
    5.1.4 Lisp 2-Parallel-Copying-GC 算法多核CPU 下的实现  57
    5.1.5 Lisp 2-Parallel-Copying-GC 算法多核GPU 下的实现  57
  5.2 垃圾收集展望  57-59
参考文献  59-64
致谢  64-65
攻读学位期间发表的学术论文目录  65
参与的科研项目  65-66

多核系统下并行节点复制垃圾收集算法研究

内容摘要

全文目录

相似论文