论文部分内容阅读
随着面向对象语言和程序设计方法的广泛使用,垃圾收集日益受到重视。垃圾收集,即自动内存管理,是指运行时系统负责自动回收无用对象的一种―废料‖回收机制。当代流行语言如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。多核环境下多线程并行垃圾收集提高了垃圾收集效率,改善了用户体验。