面向多核竞争环境的多线程应用优化方法研究

摘要

随着多核处理器的迅猛普及，计算机编程模式由传统串行编程模式向线程级并行编程模式转变，以发挥出与核数量的增长相一致的实际效果。由于多核机器具有充足的计算资源和内存容量，为了最大化资源的利用率，单台多核机器往往并发运行多个多线程应用，或者被多个运行多线程应用的虚拟机所共享，使多线程应用陷于CPU资源的竞争。例如，VMware于2010年发表的研究成果表明，在云计算环境下，平均每个处理器核被4个虚拟CPU（Virtual CPU，VCPU）时分复用。在这种多核竞争环境下，多线程应用中的无用线程（比如同步操作中的忙等线程）会浪费原本可以分配给有用线程的CPU资源，严重影响应用的性能。因此，如何有效地利用宝贵的CPU资源，是使多线程应用在多核竞争环境下高效执行的关键问题。
　　首先，大量多线程应用是基于单个程序多数据（Single Program Multiple Data，SPMD）编程模型实现的。SPMD编程模型由计算阶段和强制障碍（Barrier）同步通信交替组成。因此，多线程应用的性能很大程度上取决于Barrier同步延时。但是，在多应用并发执行的环境下，Barrier同步延时会被极大延长。这是因为当前大多数操作系统无法感知到多线程应用中的同步操作，以至于尚未到达Barrier同步点的线程没有被及时调度。在Barrier同步期间，处于忙等状态的线程可能会浪费CPU资源；当忙等线程被阻塞后，它们又可能将自己的CPU资源让给其它应用。这会极大地影响系统的整体吞吐量和公平性。为了解决这些问题，一种多核竞争环境下的Barrier同步策略（代号为Tidon）将等待线程的时间片捐献给它们被抢占、落后的姊妹线程。其中，姊妹线程是指来自相同应用的线程。在这种方式下，等待线程可以直接辅助同步操作的完成。实验结果表明，在多应用并发执行的环境下，Tidon能够为Barrier密集型应用带来最高17.9倍的性能加速，同时不损害甚至提升非Barrier密集型应用的性能，从而保障并发应用之间的性能公平性。此外，Tidon在虚拟化环境下同样有效。
　　其次，平衡线程间的任务量是保障多线程应用高效运行于多核平台的重要手段。这是因为多线程应用通常要等待所有线程完成分配的任务后，才算运行完毕。任务窃取（Work-stealing）技术是广泛用于动态保障多线程应用负载均衡的方法。但是，前人的工作证明，Work-stealing技术在诸如传统多应用并发和虚拟化环境这样的竞争环境下，存在效率低下的问题。这是因为Work-stealing中的小偷线程会浪费CPU资源。尽管目前存在优化Work-stealing在传统多应用并发环境下性能的方法，但是尚未存在改善Work-stealing在虚拟化环境下性能的有效方法。虚拟化引入的语义鸿沟和两层调度问题，增加了虚拟化环境下Work-stealing优化的困难。为此，一种虚拟化环境下面向Work-stealing的性能优化方法（代号为Robinhood）在客户操作系统和虚拟机监控器这两个层面，利用小偷线程的CPU资源来加速有用线程的执行进度，以致于减少应用的执行时间。实验结果表明，与Cilk++和BWS（Balanced Work Stealing）相比，Robinhood能够分别为Work-stealing带来最高90％和72%的性能提升。
　　最后，数据并行应用是云计算环境下的典型应用。多核平台强大的处理能力和迅猛的发展趋势使其在数据并行应用领域有着极为广阔的前景。MapReduce作为最初针对集群平台设计和实现的数据并行编程模型，亦被许多研究者证明可作为单机多核环境下易用、高性能的并行编程模型。与此同时，随着云计算环境下运行于单机多核平台的虚拟机数量不断增加，CPU资源变得越来越宝贵。但是，现有单机多核平台上的MapReduce系统更多的关注于通用性而缺乏针对性，使其在某些应用领域和计算需求下会产生不必要的开销，以至于浪费CPU资源。为此，一种面向单机多核平台的可定制MapReduce系统（代号为Peacock）通过建立一种应用分类模型，将基于MapReduce的多线程应用划分为四种不同的类型，并为不同类型的应用定制高效的执行流程，从根本上减少应用中的不必要开销。实验结果表明，与当前单机多核平台最为成功的MapReduce系统Phoenix++相比，Peacock能够为不产生具有相同键的中间数据对应用带来最高3.6倍的性能加速。
　　综上所述，通过从不同角度研究如何增强多线程应用对CPU资源的有效利用，形成一系列面向多核竞争环境的多线程应用优化方法，可以有效保证多线程应用在多核竞争环境下的性能。

目录

封面

声明

中文摘要

英文摘要

目录

1 绪论

1.1 研究背景

1.2 面向多核竞争环境的多线程应用优化关键问题

1.3 国内外研究现状

1.4 研究内容与意义

1.5 论文组织结构

2 多核竞争环境下的Barrier同步策略

2.1 引言

2.2 Barrier同步在多核竞争环境下的研究动机

2.3 Tidon：基于时间片捐献的Barrier同步策略

2.4 Tidon实现

2.5 性能评估

2.6 本章小结

3 虚拟化环境下面向Work-stealing的性能优化方法

3.1 引言

3.2 Work-stealing在虚拟化环境下的研究动机

3.3 Robinhood：面向Work-stealing优化的调度框架

3.4 系统设计

3.5 基于Linux和Xen的系统实现

3.6 性能评估

3.7 本章小结

4 面向单机多核平台的可定制MapReduce系统

4.1 引言

4.2 背景知识与问题分析

4.3 应用分类

4.4 系统设计与实现

4.5 易用性和性能评估

4.6 本章小结

5 总结与展望

致谢

参考文献

附录1 攻读博士学位期间发表的论文目录

附录2 攻读博士学位期间发明专利

附录3 攻读博士学位期间参与的科研项目

附录4 本文常用英文术语说明