并行编程模型与非对称多核调度算法研究

### 并行编程模型与非对称多核调度算法研究 在计算机科学领域，并行编程和多核调度一直是研究的热点。本文将探讨三种流行的并行编程模型的比较，以及一种用于非对称多核系统的新型调度算法。 #### 三种并行编程模型的比较 在并行计算中，OpenMP、Cilk和TBB是三种广为人知的并行编程方法。研究人员在Xeon Phi协处理器上对这三种方法的性能方面进行了比较，包括加速比、CPU平衡和总CPU时间。 为了进行比较，使用了三个不同的并行基准测试：斐波那契数列、归并排序和矩阵乘法。每个基准测试都有不同的特点，这凸显了所研究方法的优缺点。多程序场景是在系统上同时运行这三个基准测试，观察不同编程模型对这种情况的反应。 基于单程序场景的结果，特别是总CPU时间，研究人员预测Intel TBB方法更适合多程序环境，实验也证实了这一预测。 同时，运行时库的开销在并行计算中起着重要作用，特别是在多程序系统中。它不仅会增加系统的额外能耗，还会对多程序工作负载的性能产生显著影响。 目前，研究人员正在开发一种名为Glasgow Parallel Reduction Machine (GPRM)的方法。GPRM允许应用程序使用默认数量的线程（即与核心数量相同），同时通过全局共享一些信息来提高周转时间。GPRM主要关注任务而不是线程，以减少运行时系统的开销。 #### 非对称多核系统的吞吐量 - 公平性权衡 单指令集架构（ISA）的非对称性能多核处理器（AMPs）比对称芯片多处理器（CMPs）每瓦和每面积能提供更高的性能。然而，现有的在AMPs上实现公平性和优先级执行的调度方案，没有考虑到多程序工作负载中的应用程序可能从系统中的快速核心获得不同的好处。因此，它们可能会进行线程到核心的映射，从而降低系统吞吐量。 为了解决这个问题，研究人员提出了Prop - SP调度算法，旨在改善AMPs上的吞吐量 - 公平性权衡。 ##### 动机 研究人员对以前提出的AMPs调度算法的系统吞吐量和公平性进行了分析研究。结果表明，现有的试图优化一个指标的调度器会显著降低另一个指标，从而实现不可接受的权衡。 为了评估系统吞吐量，使用了聚合加速比（Aggregate Speedup）指标，其定义为： \[Aggregate\ Speedup = \sum_{i = 1}^{n} \left(\frac{CT_{slow,i}}{CT_{sched,i}} - 1\right)\] 其中，\(n\)是工作负载中的应用程序数量，\(CT_{slow,i}\)是应用程序\(i\)在系统中单独运行且仅使用慢速核心时的完成时间，\(CT_{sched,i}\)是应用程序\(i\)在给定调度器下的完成时间。 关于公平性，使用了不公平性（Unfairness）指标，定义为： \[Unfairness = \frac{MAX(Slowdown_1, \cdots, Slowdown_n)}{MIN(Slowdown_1, \cdots, Slowdown_n)}\] 其中，\(Slowdown_i = \frac{CT_{sched,i}}{CT_{fast,i}}\)，\(CT_{fast,i}\)是应用程序\(i\)在AMP中单独运行（所有快速核心可用）时的完成时间。 研究人员在一个由两个快速核心（FC）和两个慢速核心（SC）组成的AMP系统上，对几个合成多程序工作负载进行了不同调度算法的有效性评估。 | 工作负载 | SF1 | SF2 | SF3 | SF4 | | ---- | ---- | ---- | ---- | ---- | | W1 | 3.4 | 3.4 | 1.2 | 1.2 | | W2 | 3.4 | 3.4 | 2.3 | 2.3 | | W3 | 2.3 | 2.3 | 1.9 | 1.9 | | W4 | 3.4 | 3.4 | 2.7 | 2.7 | | W5 | 3.4 | 3.4 | 3.4 | 3.4 | | W6 | 2.5 | 2.1 | 1.6 | 1.2 | | W7 | 3.0 | 2.1 | 2.1 | 2.1 | | W8 | 3.4 | 3.0 | 2.5 | 2.1 | | W9 | 2.9 | 2.5 | 2.1 | 1.2 | 这些工作负载由四个单线程应用程序组成，假设应用程序的快速 - 慢速性能比在1.2到3.4之间。 研究人员还推导了一组分析公式来计算工作负载在给定工作守恒调度器下的不公平性和聚合加速比： | 指标 | 定义 | | ---- | ---- | | 聚合加速比 | \(\sum_{i = 1}^{n} \left(\frac{