高性能计算实验课件-串行程序性能优化

Posted on

ILP

指令级并行（ILP）是用于在同一CPU内核中同时执行多个指令的一组技术。
（请注意，ILP与多核无关。）
问题：CPU内核有很多电路，并且在任何给定时间，大多数都处于空闲状态，这很浪费。 解决方案：让CPU内核的不同部分同时执行不同的操作：如果CPU内核能够一次执行10次操作，则该程序原则上可以运行多达10次。 （尽管实际上并没有那么多）。

指令好像是必须按照程序顺序来执行，但是独立的指令可以同时执行，不会影响程序正确性。

超标量执行：处理器在指令序列中动态选择独立的指令并并行执行他们。

  • 超标量：同时执行多项运算（例如，同时执行加，乘和加运算）。
  • 流水线：开始对一个数据执行操作，同时对另一数据完成相同的操作-同时对不同的操作数集执行同一操作的不同阶段（如组装线）。
  • 超流水线：超标量和流水线的结合–同时执行多个流水线操作。
  • 向量：将多个数据加载到特殊寄存器中，并同时对所有这些数据执行相同的操作。使用SSE，AVX等，一条指令产生多个结果。

编译器优化

Copy Propagation复制传播
从

1
2
x = y
z = 1 + x

转换成：
1
2
x = y
z = 1 + y

消除数据依赖。

Constant Folding常量折叠

1
2
3
add = 100;
aug = 200;
sum = add + aug;

变为：
1
sum = 300;

注意，sum实际上是两个常量的和，因此编译器可以对其进行预先计算，从而消除了否则会在运行时执行的加法运算。

删除死代码

1
2
3
4
var = 5;
printf("%d", var);
exit(-1);
printf("%d", var * 2);

变为：
1
2
3
var = 5;
printf("%d", var);
exit(-1);

强度降低

1
2
x = pow(y, 2.0);
a = c / 2.0;

变为：
1
2
x = y * y;
a = c * 0.5;

计算一个值的乘方或进行除法要比乘法更昂贵。 如果编译器可以判断出幂是一个小整数，或者分母是一个常数，那么它将使用乘法。

常见子表达消除

1
2
d = c * (a / b);
e = (a / b) * 2.0;

变为：
1
2
3
adivb = a / b;
d = c * adivb;
e = adivb * 2.0;

子表达式（a / b）出现在两个赋值语句中，因此没有必要进行两次计算。通常只有在通用子表达式的计算成本很高的情况下，才值得这样做。

变量重命名

1
2
3
x = y * z;
q = r + x * 2;
x = a + b;

变为：
1
2
3
x0 = y * z;
q = r + x0 * 2;
x = a + b;

原始代码具有输出依赖性，而新代码则没有输出依赖性，但是x的最终值仍然正确。

循环优化

  • 循环内不变的代码称为循环不变式。 不需要一遍又一遍地计算。
  • 我们可以通过剥离特殊的迭代来消除IF
  • 分组迭代消除IF
  • 数组元素a[i][j]和a[i][j+1]在内存中彼此靠近，而a[i+1][j]可能很远，因此使j循环为内循环。 （在Fortran中是相反的。）
  • 循环展开。上次我们看到，具有很多操作的循环可以获得更好的性能（在某种程度上），特别是在有很多算术操作但主存储器加载和存储很少的情况下。展开会创建多个操作，这些操作通常从相同或相邻的缓存行加载。 因此，展开的循环可以执行更多的操作，而不会增加太多的内存访问。同样，展开将减少循环计数器变量上比较的次数，并减少到循环顶部的分支数。

循环融合

1
2
3
4
5
6
7
8
9
for (i = 0; i < n; i++) {
	a[i] = b[i] + 1;
}
for (i = 0; i < n; i++) {
	c[i] = a[i] / 2;
}
for (i = 0; i < n; i++) {
	d[i] = 1 / c[i];
}

变为：
1
2
3
4
5
for (i = 0; i < n; i++) {
	a[i] = b[i] + 1;
	c[i] = a[i] / 2;
	d[i] = 1 / c[i];
}

与展开一样，这具有较少的分支。 它还具有较少的总内存引用。

从理论上讲，编译器和硬件可以“理解”所有这些内容，并可以优化您的程序；实际上，他们没有。

  • 他们不会知道与处理器更好的“匹配”的不同算法
  • 但是实际上编译器可能需要您的帮助- 选择其他编译器，优化标志等，其中包括控制单处理器优化的选项：超标量，流水线，矢量化，标量优化，循环优化，内联等。
  • 重新排列代码以使事情变得更明显
  • 使用特殊功能（“固有”）或编写汇编

高级优化：过程间优化 (IPO)

  • ip: 源程序文件内部的过程间优化
  • ipo: 多个源程序的过程间优化
  • 函数内联是ipo中最重要性能优化手段

为什么循环不向量化

  • 独立
  • 循环迭代通常必须独立
  • 一些相关的限定词：
  • 某些依赖循环可以向量化。
  • 大多数函数调用无法向量化。
  • 一些条件分支会阻止矢量化。
  • 循环必须是可数的。
  • 无法对嵌套的外循环进行矢量化处理。
  • 混合数据类型无法向量化

处理内存延迟的方法

  • 通过将值保存在小型快速内存（缓存）中并重新使用它们来消除内存操作
  • 在程序中需要时间局部性
  • 通过获取一块内存并将其保存在小型快速内存（高速缓存）中并使用整个内存块，来利用更好的带宽
  • 带宽改善快于延迟
  • 在程序中需要空间局部性
  • 通过允许处理器一次向存储系统发出多次读取来利用更好的带宽
  • 指令流中的并发，例如 像矢量处理器一样加载整个数组； 或预取
  • 重叠计算和内存操作
  • 预取

如果有两个以上的内存级别怎么办？

  • 需要最小化所有级别之间的沟通
    • 在L1和L2缓存，缓存和DRAM，DRAM和磁盘之间…
  • 算法需要找到合适的块大小
    • 机器相关
    • 需要在最里面的循环中“阻止” b x b矩阵乘法
      • 1级内存->3个嵌套循环（幼稚算法）
      • 2级内存->6个嵌套循环
      • 3级内存->9个嵌套循环…
  • 缓存遗忘算法提供了另一种选择
    • 将nxn矩阵乘法视为一组较小的问题
    • 最终，这些将适合缓存
    • 将最小化在每个内存级别之间移动的＃个单词
    • “遗忘”级别的数量和大小

向量化通用准则

  • 优先考虑可计数的单入口和单出口“for”循环。它可以作为外部循环索引的功能，也可以作为嵌套循环中最里面的循环的函数。
  • 编写序列代码（避免使用诸如switch，goto或return语句之类的分支，大多数函数调用或不能视为掩码分配的“if”构造）。
  • 避免循环迭代之间的依赖关系，或者至少避免读后写依赖关系。
  • array首选使用数组表示法而不是指针，尤其是对于C语言。尽可能在数组下标中直接使用循环索引，而不是增加单独的计数器以用作数组地址。
  • 使用有效的内存访问，例如连续访问和对齐访问（16/32字节边界）。并最大程度地减少间接寻址
  • 首选结构阵列（struct of array, SoA）优于结构阵列（array of structure, AoS）
  • 尝试使用矢量化库，包括英特尔®MKL和英特尔®IPP

profiling
profiling意味着收集有关程序执行的数据。两种主要的性能分析是：

  • Subroutine profiling：插装
  • Hardware counters：统计

假设您有一个hot循环，您认为应该进行矢量化，但没有进行矢量化（如在Vtune，SDE或其他热循环工具中发现的那样）。首先使用适当的编译器选项尝试基本的自动矢量化。使用“ -vec-report2”或更高版本可获取有关循环是否正在向量化的调试信息。要为Intel Xeon E5-2680要求AVX自动矢量化，请使用编译器命令行选项“ -xAVX –O3”。要为Intel Xeon Phi本机可执行文件要求Xeon Phi自动矢量化，请使用编译器命令行选项“ -mmic –O3”。离线编译通常应该给您提供–mmic自动矢量化功能，但是如果需要，您可以使用主机编译器选项-offload-option，compiler，mic，“将任何其他选项传递给Xeon Phi编译器。
其他可尝试的内容包括：
1.尝试使用“#pragma vector”来禁用编译器的矢量化成本模型。引入此选项后，请始终检查性能。您需要知道的主要事情是向量化器使用启发式算法。根据定义，启发式方法并不总是正确的。
2.如果您知道没有真正的依赖关系可以阻止矢量化，请尝试使用“ #pragma ivdep”。引入此选项后，请始终检查正确性和可能的​​崩溃。
3.尝试“ #pragma simd”。如果以上两种方法都无法为您提供矢量化代码，请尝试使用此选项。引入此选项后，请始终检查性能，正确性和可能的​​崩溃。
不要忘记通过使用编译器–S选项检查汇编并交叉检查源代码行号来“检查工作”。如果您从未编写过汇编文件，那么“检查汇编”听起来可能是一项艰巨的任务。

向量化建议：

  • 首先找到您的热循环/热基本块（Vtune，SDE等）
  • 确保数组边界对齐（如果可能）
  • 确保您没有不良依赖关系（即算法可向量化）
  • 首先尝试自动矢量化，例如：–O3 –xAVX –vec-report2 –openmp
  • 分析为什么编译器无法进行矢量化，然后尝试：#pragma vector always
  • 然后尝试：#pragma ivdep
  • 使用：#pragma vector aligned，如果编译器未注意到您的数组已对齐。
  • 然后尝试：#pragma simd：如果它是可向量化的循环，通常将对其向量化。
    • 无论安全性如何，都强制进行矢量化：检查正确性并进行彻底测试
  • 在工作时定期查阅编译器的–S程序集列表
  • 您可能需要专门标记减少操作，例如
    • 如果您知道行程计数（循环计数），请使用#pragma loop_count帮助编译器。
    • 在循环周围测试#pragma unroll(N)，以查看它是否有助于提高性能。

CP是基本3d形状匹配算法。 ICP基准相对而言一个简单的500行程序，该程序执行ICP算法的复杂度是O(N^2)。由于程序的简单性，我们不仅可以测量单精度和双精度结果，测量阵列结构（structure of array, SoA）和结构阵列（array of structure, AoS）的性能也非常容易。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#if defined(AOS)
#define AOSFLAG 1 // 1 for AoS
#else
#define AOSFLAG 0 // 0 for SoA (default)
#endif
#if defined(DOUBLEPREC)
#define FPPRECFLAG 2 // 2 for Double precision
#define FLOATINGPTPRECISION double
#else
#define FPPRECFLAG 1 // 1 for Single precision (default)
#define FLOATINGPTPRECISION float
#endif

// AoS 
typedef struct Point3d
{
FLOATINGPTPRECISION x,y,z,t; // use of t padding is optional
} Point3d,*Point3dPtr;

#if AOSFLAG == 1
Point3dPtr org = NULL;
Point3dPtr tfm = NULL;
#endif
#if AOSFLAG == 0 // SoA (set of arrays here, structure of arrays normally)
FLOATINGPTPRECISION *orgx = NULL;
FLOATINGPTPRECISION *orgy = NULL;
FLOATINGPTPRECISION *orgz = NULL;
FLOATINGPTPRECISION *tfmx = NULL;
FLOATINGPTPRECISION *tfmy = NULL;
FLOATINGPTPRECISION *tfmz = NULL;
#endif


源代码如下，因此我们将列出一个简单的循环以显示程序中的代码类型。 点集的简单旋转和平移明确表示如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#if AOSFLAG == 1
#pragma omp parallel for shared(tfm,Rf,Tf,nxfmpts) private(x,y,z)
for(i=0;i<nxfmpts;i++)
{
	x = tfm[i].x; y = tfm[i].y; z = tfm[i].z;
	tfm[i].x = Rf[0][0]*x + Rf[0][1]*y + Rf[0][2]*z + Tf[0];
	tfm[i].y = Rf[1][0]*x + Rf[1][1]*y + Rf[1][2]*z + Tf[1];
	tfm[i].z = Rf[2][0]*x + Rf[2][1]*y + Rf[2][2]*z + Tf[2];
}
#endif
#if AOSFLAG == 0
#pragma omp parallel for shared(tfmx,tfmy,tfmz,Rf,Tf,nxfmpts) private(x,y,z)
for(i=0;i<nxfmpts;i++)
{
	x = tfmx[i]; y = tfmy[i]; z = tfmz[i];
	tfmx[i] = Rf[0][0]*x + Rf[0][1]*y + Rf[0][2]*z + Tf[0];
	tfmy[i] = Rf[1][0]*x + Rf[1][1]*y + Rf[1][2]*z + Tf[1];
	tfmz[i] = Rf[2][0]*x + Rf[2][1]*y + Rf[2][2]*z + Tf[2];
}
#endif

SoA is better than AoS on “Intel Xeon Phi and Intel Xeon_E5-2680 for both Single and Double Precision.
该代码的属性可帮助实现此应用程序的源代码，如下所示：

  • 几乎所有读和写都发生第1步访问。
  • 所有数组都是64字节对齐的，并且编译器知道它们是64字节对齐的。
  • 编译器成功地向量化了所有热循环。
  • 循环是高速缓存友好的，以减少内存访问。
  • 主循环中没有除法。
  • 循环非常简单。

MPI编程模型：全局地址空间

  • 程序由一组命名线程组成。
    • 通常在程序启动时固定
    • 本地和共享数据，如共享内存模型中一样
    • 但是，共享数据在本地进程中分区
    • 成本模型表明远程数据非常昂贵
  • 示例：UPC，Co-Array Fortran
  • 全局地址空间编程是消息传递和共享内存之间的中间点
    • 线程等全局地址空间（可编程性）
    • SPMD并行性，例如MPI（性能）
    • 本地/全局区别，即布局很重要（性能）

主流并行程序模型－数据并行

  • 单线程模式
    • 并行操作于聚合数据结构上，一般是数组
    • 隐式相互作用，不需要显式同步
    • 隐式数据分配
  • 缺点
    • 相对严格的计算结构要求，不是所有应用模式都适合这种模型
    • 在粗粒度的并行机上难于映射

现代机器中的“自动”并行性

  • 位级并行
    • 在浮点运算等中
  • 指令级并行性（ILP）
    • 每个时钟周期执行多个指令
  • 内存系统并行
    • 内存操作与计算重叠
  • OS并行性
    • 在商品SMP上并行运行多个作业

常见的并行开销有哪些？

  • 创建和销毁并行进程、线程的开销
    • 创建和销毁进程本身是高开销的工作
      • PowerPC 700MHz(每个周期 15ns 执行4flops; 创建一个进程1.4ms，可执行372,000flops)
    • 创建和销毁多个进程的开销在系统中随进程数增加
      • 启动万规模进程需要s级时间
  • 通信开销是并行开销的主要部分
    • 多机间的通信开销相对于计算很大
    • 通信模型参数会因很多因素不同而变化
      • 同时通信的进程数
      • 同时发送的消息数
      • 消息的大小
      • 网络的拓扑结构
      • 网络的拥挤程度
      • 不同的MPI实现
      • 群集消息通信算法
      • 之前发送的消息情况
  • 并行化过程中引入的空间和相应的时间开销
    • 多进程并行化过程中引入的空间和相应的时间开销
      • 消息缓冲区准备
      • 交叠数据的分配和使用

回顾编程模型1：共享内存

  • 程序是控制线程的集合。
  • 可以在某些语言中执行时动态创建
  • 每个线程都有一组私有变量，例如局部堆栈变量
  • 还有一组共享变量，例如静态变量，共享公共块，全局堆。
  • 线程通过读写共享来隐式通信变量。
  • 线程通过共享变量同步来协调。

几个线程库/系统

  • PTHREADS是POSIX标准
    • 相对较低的水平
    • 便携式但可能很慢； 相对较重
  • 用于应用程序级编程的OpenMP标准
    • 支持对共享内存进行科学编程

POSIX线程概述

  • POSIX：便携式操作系统接口
    • 与操作系统实用程序的接口
  • PThreads：POSIX线程接口
    • 系统调用以创建和同步线程
    • 在类似UNIX的OS平台上应该相对统一
  • PThread包含对以下几点的支持
    • 创建并行
    • 同步
    • 不明确支持通信，因为共享内存是隐式的；指向共享数据的指针被传递给线程

OpenMP的主要特点

  • 面向共享存储体系结构，特别是SMP系统
  • 显式并行方法
  • 基于fork-join的多线程执行模型，但同样可以开发SPMD（Single Program Multi-Data )类型的程序
  • 可以进行增量式并行开发( Incremental development )，支持条件编译( Conditional Compilation )和条件并行
  • 允许嵌套的并行性（nested Parallelism )和动态线程
    • 并不是在所有的编译器实现中支持

线程数目的讨论

  • 通常情况下线程组内线程数目由环境变量OMP_NUM_THREADS控制
  • 如果parallel语句有num_threads子句，或者用户调用了omp_set_num_threads函数，线程数目由它们给出，num_threads具有高优先级
  • 上述三种设置方法作用域分别为系统、并行块级以及程序级
  • 这里给出的线程数目可以大于系统中处理器个数，它是一个上限值
  • 系统实际产生的线程数目可能由于资源的限制而比上限值要小

并行结构：Work-sharing Construct(1) - loop

  • 为线程分配了一组独立的迭代
  • 线程必须在工作共享结构的末尾等待
1
2
3
4
#pragma omp parallel
#pragma omp for
	for(i = 1, i < 13, i++)
		c[i] = a[i] + b[i]

Work-sharing Construct(2): Parallel Sections
section中代码的独立部分可以同时执行。

1
2
3
4
5
6
7
8
9
#pragma omp parallel sections
{
	#pragma omp section
	phase1();
	#pragma omp section
	phase2();
	#pragma omp section
	phase3();
}

Work-sharing Construct(3): Single Construct
表示仅由一个线程执行的代码块

  • 选择第一个到达的线程
  • 隐式障碍
1
2
3
4
5
6
7
8
9
#pragma omp parallel
{
	DoManyThings();
	#pragma omp single
	{
		ExchangeBoundaries();
	} // threads wait here for single
	DoManyMoreThings();
}

分配迭代：schedule子句影响循环迭代如何映射到线程上

  • schedule(static [,chunk])
    • 线程大小为“块”的迭代块
    • 循环分配
    • 默认值= N / t
    • 对于Ni个迭代和Nt个线程，每个线程获得Ni/Nt个循环迭代的一个块：
  • schedule(dynamic[,chunk])
    • 线程获取“块”迭代
    • 完成迭代后，线程将请求下一组请求
    • 默认值= 1
    • 对于Ni个迭代和Nt个线程，每个线程都会获得k个循环迭代的固定大小的块，当特定线程完成其迭代块时，将为其分配新的块。因此，迭代与线程之间的关系是不确定的。
      • 优势：非常灵活
      • 缺点：高开销–关于哪个线程获取每个块的大量决策
  • schedule(guided [，chunk])
    • 动态计划以大块开始
    • 块的尺寸缩小； 不小于“块”
    • 默认值= 1
    • 对于Ni迭代和Nt线程，最初，每个线程都会获得k <Ni/Nt循环迭代的固定大小的块：
    • 每个线程完成其k次迭代的块之后，它将获得k / 2次迭代的块，然后是k / 4个，依此类推。当线程完成其先前的块时，将动态分配块。
      • 优于静态：可处理不平衡负载
      • 动态优势：更少的决策，因此更少的开销
  • schedule(runtime)
    • OMP_SCHEDULE

现在的消息传递系统多使用三种通信模式:

  • 同步的消息传递 (Synchronous Message Passing)
  • 阻塞的消息传递 (Blocking Message Passing)
  • 非阻塞的消息传递 (Nonblocking Message Passing)

非阻塞模式为计算和通信重叠带来机会，但本身也会带来一些额外开销:

  • 作为临时缓冲区用的内存空间
  • 分配缓冲区的操作
  • 将消息拷入和拷出临时缓冲区
  • 执行一个额外的检测和等待函数

消息缓冲(message buffer, 简称buffer), 在不同的消息传递使用场合有不同的含义. 下面给出一些例子:

  • 消息缓冲指的是由程序员定义的应用程序的存储区域, 用于存放消息的数据值.例如, 在Send(A, 16, Q, tag)中, 缓冲A是在用户应用程序中声明的变量.
  • 缓冲的起始地址在消息例程中被使用.
  • 消息缓冲也可以指由消息传递系统(而非用户)创建和管理的一些内存区, 它用于发送消息时暂存消息. 这种缓冲不在用户的应用程序中出现, 有时被称为(消息传递)统消息缓冲(或系统缓冲).
  • MPI允许第三种可能的定义. 用户可以划出一定大小的内存区, 作为出现在其应用中的任意消息的中间缓冲.

用在MPI中的通信模式(communication mode)：

  • 同步的(synchronous)：直到相应的接收已经启动，发送才返回
    • 阻塞的同步发送：发送缓冲区可用，发送完成
    • 非阻塞的同步发送：它的返回不意味着消息已经被发出! 它的实现不需要在接收端有附加的缓冲, 但需要在发送端有一个系统缓冲. 为了消除额外的消息拷贝, 应使用阻塞的同步发送
  • 缓冲的(buffered)：缓冲的发送假定能得到一定大小的缓冲空间, 它必须事先由用户程序分配和管理。通过调用子例程MPI_Buffer_attch(buffer,size)来定义, 由它来分配大小为size的用户缓冲. 这个缓冲可以用MPI_Buffer_detach(*buffer, *size )来实现.无缓冲区时，返回错误.
  • 就绪的(ready)：
    • 在肯定相应的接收已经开始才进行发送. 它不像在同步模式中那样需要等待. 这就允许在相同的情况下实际使用一个更有效的通信协议.使用较少，程序员要保证程序正确性
  • 标准的(standard)：最常用的模式。发送可以是同步的或缓冲的(系统缓冲), 取决于实现，给予系统以灵活选择的机会；发送的返回意味着消息缓冲区可用

常见错误调试心得

  • 确保栈空间分配的有效性
    • ulimit –s unlimited (可以根据需要调整)
    • export KMP_STACKSIZE=16000000 (可以根据需要调整)
  • 确保串行程序的正确执行（OMP_NUM_THREADS=1）
  • 验证private变量使用的正确性
  • 逐项确保变量的使用了然于胸，特别是f90: SAVE, DATA, default(none), private(…), shared(…)
  • 利用增量级开发的特性进行代码二分查找
  • 确认是否由于舍入误差导致
  • 对于连加等可能由于计算次序导致不同计算结果的操作，不使用reduction子句，将加法部分放到串行区完成
  • 借助Intel Inspector，totalview等工具寻找数据竞争问题

处理器：多核时代

  • 想法1：使用增加的晶体管数量添加更多处理器核心，而不是使用晶体管来增加。先进的处理器逻辑加速单个指令流（例如，乱序和投机操作）
  • 想法2：添加ALU以提高计算能力。摊销跨多个ALU管理指令流的成本/复杂性。SIMD处理，一条指令，多个数据向所有ALU广播相同的指令在所有ALU上并行执行

指令流一致性（“一致性执行”）

  • 相同的指令序列适用于同时操作的所有元素
  • 要有效利用SIMD处理资源，必须执行一致的执行
  • 由于每个内核都具有获取/解码不同指令流的能力，因此对于内核之间的高效并行化而言，一致性执行不是必需的
  • “分散”执行
    • 缺乏指令流一致性

在现代CPU上执行SIMD

  • SSE指令：128位操作：4x32位或2x64位（4宽格式向量）
  • AVX2指令：256位操作：8x32位或4x64位（8宽格式向量）
  • AVX512指令：512位操作：16x32位…
  • 指令由编译器生成
    • 程序员使用内在函数明确要求的并行性
    • 使用并行语言语义传达的并行性（例如，forall示例）
    • 通过对循环的依赖性分析推断出并行性（困难的问题，即使是最好的编译器也不能在任意C / C ++代码上使用）
  • 术语：“显式SIMD”：SIMD并行化在编译时执行

在许多现代GPU上执行SIMD

  • “隐含SIMD”
    • 编译器生成标量二进制（标量指令）
    • 但是程序的N个实例始终在处理器上一起运行，execute(my_function，N)，执行my_function N次
  • 换句话说，硬件本身的接口是数据并行的
  • 硬件（不是编译器）负责同时从多个实例对SIMD ALU上的不同数据执行同一条指令
  • 大多数现代GPU的SIMD宽度为8到32
  • 分歧可能是个大问题（写得不好的代码可能以机器峰值能力的1/32执行！）

摘要：并行执行

  • 现代处理器中的几种并行执行形式
    • 多核：使用多个处理核
      • 提供线程级并行性：在每个内核上同时执行完全不同的指令流
      • 软件决定何时创建线程（例如，通过pthreads API）
    • SIMD：使用同一指令流（在内核内）控制的多个ALU
      • 高效的数据并行工作负载设计：控制可摊销许多ALU
      • 矢量化可以由编译器（显式SIMD）完成，也可以在运行时由硬件完成
      • [缺乏]依赖关系在执行之前就已经知道（通常由程序员声明，但可以通过高级编译器的循环分析来推断）
    • 超标量：在指令流中利用ILP。 处理来自相同的指令流并行（在内核内）
      • 硬件在执行过程中自动动态发现并行性（程序员看不到）

多线程减少了停顿

  • 想法：对同一核心上的多个线程进行交错处理以隐藏停顿
  • 与预取一样，多线程隐藏了延迟，而不是减少延迟的技术

硬件支持的多线程

  • Core管理多个线程的执行上下文
    • 从可运行线程运行指令（处理器决定每个时钟运行哪个线程，而不是操作系统的运行）
    • 核心仍然具有相同数量的ALU资源：多线程仅在面对诸如内存访问之类的高延迟操作时才有助于更有效地使用它们
  • 交错多线程（也称为时间多线程）
    • 每个时钟，内核都会选择一个线程，并在ALU上运行来自该线程的指令（交织多线程）
  • 同时多线程（SMT，同时多线程）
    • 每个时钟，内核从多个线程中选择指令以在ALU上运行
    • 扩展超标量CPU设计
    • 示例：英特尔超线程（每个内核2个线程）

多线程摘要

  • 优势：更有效地利用核心的ALU资源
    • 隐藏内存延迟
    • 填充超标量架构的多个功能单元（当一个线程的ILP不足时）
  • 劣势
    • 需要额外存储线程上下文
    • 增加任何单线程的运行时间（通常不是问题，我们通常关心并行应用程序中的吞吐量）
    • 需要程序中的其他独立工作（比ALU更加独立！）
    • 严重依赖内存带宽
    • 更多线程→更大的工作集→每个线程更少的缓存空间
    • 可能会更频繁地进入内存，但可以隐藏延迟

带宽是至关重要的资源。高性能并行程序将：

  • 组织计算以减少从内存中获取数据的频率
    • 重用先前由同一线程加载的数据（传统的线程内时间局部性优化）
    • 跨线程共享数据（线程间协作）
  • 减少请求数据的频率（取而代之的是做更多的算术：“免费”）
    • 有用的术语：“算术强度” —指令流中数学运算与数据访问运算的比率
    • 要点：程序必须具有很高的算术强度才能有效利用现代处理器