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

发布时间：2020-01-21 09:15

【摘要】：随着多核处理器的迅猛普及,计算机编程模式由传统串行编程模式向线程级并行编程模式转变,以发挥出与核数量的增长相一致的实际效果。由于多核机器具有充足的计算资源和内存容量,为了最大化资源的利用率,单台多核机器往往并发运行多个多线程应用,或者被多个运行多线程应用的虚拟机所共享,使多线程应用陷于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资源的有效利用,形成一系列面向多核竞争环境的多线程应用优化方法,可以有效保证多线程应用在多核竞争环境下的性能。
【图文】：

测试应用,间隔时间,细粒度

华中科技大学博士学位论文多核系统中的共享内存应用程序的发展趋势。图 2.6 描述了这些测试应用在测试平台上运行的 Barrier 同步之间的平均间隔时间。基于 Barrier 同步之间的平均间隔时间，本章将测试应用分为三类：细粒度应用、中等粒度应用，以及粗粒度应用。本章将细粒度应用和中等粒度应用统称为 Barrier 同步密集型应用。

并发执行,细粒度,吞吐量

尽管 BS-De 和 BS-Pa 能够在很大程度上解决 Barrier 密集型应用的性能损耗，但是，在大多数情况下，CFS-De 可以获取比这两种策略更高的系统吞吐量。正如 2.2.3小节所分析的那样，在平衡调度的支持下，EP 的所有线程都会被分配到相对较高负载的处理器核。而在 CFS 的支持下，来自 EP 的线程有可能被分配到相对较低负载的处理器核。因此，在平衡调度的支持下，由于处理器核上的负载越高，调度延时更大，EP 的性能会相对较差，从而覆盖了主应用性能的相对提升，降低了系统的整体吞吐量。除了 EP 和 EP 并发执行的组合外，Tidon 可以在不明显降低甚至提升 EP 性能的基础上，缓解 Barrier 密集型应用的性能损耗，从而在所有策略中获取了最好的系统吞吐量。例如，当 BT 和两线程的 EP 并发执行时，，与其它四种策略相比，BT 在 Tidon 支持下的性能被提升了 59%到 110%，同时 EP 的性能被提升了 40%到 163%，以至于将系统吞吐量提升了 64%到 102%。这是因为 Tidon 通过利用时间片捐献策略来加速Barrier 同步操作的完成，提高了 CFS 在系统吞吐量方面的优势，从而提升了宝贵的
【学位授予单位】：华中科技大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：TP332

【相似文献】