多线程

在CPU时钟频率优先的情况下，提高CPU密集型程序吞吐量的方法是同时做多个事情，有以下三种方法：

• 使用多个CPU或者多核CPU
• 使用现代CPU的乱序执行能力
• 使用现代CPU的向量操作

为了利用CPU的多个核心，需要将任务划分到不同的线程，有两个主要的方法：功能分解和数据分解。

在考虑并行处理时，区分粗粒度并行和细粒度并行非常重要，细粒度并行是指任务被划分为许多的小任务，同时任务间存在协调关系，无法在特定子任务上工作很久，由于不同内核间的通信和同步比较慢，因此粗粒度并行要比细粒度并行效率更高，粒度太细则将任务拆分为多个线程没有没有优势（无序执行和向量操作此时将更具优势）

多个CPU内核或者逻辑处理器通常共享相同的缓存（最后一级缓存），特定情况下甚至共享相同的一级缓存。
缓存共享的优点是线程之间的通信速度非常快，并且可以共享相同代码和只读数据，缺点是如果线程使用不同的内存区域，那么缓存就会被填满，如果线程写入相同的内存区域，就会发生缓存竞争。

只读数据可以在多个线程之间共享，而可修改的数据应该被每个线程单独存储。多个线程写入同一缓存会导致各个线程使彼此的缓存失效，造成较大的延迟。 使数据特定于线程的最简单办法实在线程函数中声明，使其为线程本地的，便于存储在堆栈中。

线程之间有很多通信好同步方法，比如信号量，互斥量和消息系统，但是这些方法都很耗时，应该合理组织数据和资源，以便减少线程间的必要通信。例如如果多个线程共享相同的队列、列表或其他数据结构，我们或许可以考虑给每个线程分配自己的数据，当所有线程完成耗时的数据处理后，再将多个数据合并起来。

如果在只有一个逻辑处理器的系统上运行多个线程，而这些线程会争夺相同的资源，那么可能多线程不具备优势

可以将耗时的计算放在一个优先级低于用户界面的单独线程，或者将文件和网络访问放在不同的县城中，这样让专门的线程等待硬盘和网络响应而可以让其它线程同时做事情。

同步多线程技术

许多微处理器可以在每个内核中运行两个线程，例如所谓的4核8线程CPU，intel称之为“超线程”技术，，但是同一个内核中运行的两个线程总是会争夺相同的资源，例如缓存和执行单元，那么同步多线程没有优势。

若大部分时间存在缓存不命中、分支远程错误或者长依赖链，这种情况下每个线程的运行速度会超过单线程的一般，此时同步多线程技术具有一些优势，但性能不会提高一倍，与另一个线程共享内核资源的线程总是比在内核中单独运行的线程运行的慢。

为了确定在特定应用程序中使用同步多线程是否有利，通常需要测试，如没有优势，我们可以只使用序号为偶数的逻辑处理器来避免同步多线程。

乱序执行

现代x86 CPU可以乱序执行指令或者同时执行多个操作，例如：

float a, b, c, d, y;
y = a + b + c + d;

表达式计算为((a + b) + c) + d，这是一个依赖链，每个加法都必须等待前一个的结果，可以换成如下：

y = (a + b) + (c + d);

如此一来，两个括号会独立计算，在计算完a+b之前，cpu就开始计算c + d，可以节省几个时钟周期，由于浮点表达式精度的原因，编译器基本不会对浮点表达式进行优化，因此我们必须手动添加括号。

当依赖链很长时，这个问题的影响更大，例如：

cont int N = 100;
float list[N], sum = 0;
for(int i = 0; i < N; i ++) {
    sum += list[i];
}

这里有很长的依赖链，如果如果每个浮点加法需要5个时钟周期，那么整个循环需要大约500个时钟周期，通过循环展开并将于依赖链一分为2，可以显著改善：

float sum1 = 0, sum2 = 0;
for(int i = 0; i < N; i += 2) {
    sum1 += list[i];
    sum2 += list[i + 1];
}
sum = sum1 + sum2;

如果处理器从时间T到T+5对sum1做加法，那么它可以从时间T+1到T+6对sum2做加法，节省了约一半的计算时间。

如果没有循环依赖连，则不需要循环展开并使用多个累加器，具有乱序执行功能的微处理器可以重叠迭代，并在前一个迭代完成前开始下一个迭代的计算，例如：

const int N = 100;
float a[N], b[N], c[N];
float register tmp;
for(int i = 0; i < N; i ++) {
    tmp = a[i] + b[i];
    c[i] = tmp * tmp;
}

这个循环中不存在循环依赖链，因此具有无序功能的CPU可以检测到循环每一次迭代中的寄存器临时值独立于前一次的值，使它可以在计算完前一个值之前开始计算一个新的临时值，它会为tmp分配一个新的物理寄存器来实现，即使在机器码中出现的逻辑寄存器是相同的，这个叫做寄存器重命名。

CPU能在某些条件下重命名寄存器和并行执行多个计算：

• 没有循环依赖链，一次迭代的计算不应该依赖于前一次迭代的结果（循环计数器除外，当它是整数时，其计算速度很快）
• 所有中间结果都应该保存在寄存器中而不是内存中，重命名机制只对寄存器有效，而对内存或者缓存中的变量无效
• 循环分支需要可以被预测，如果重复计数很大或者恒定，不存在此问题，如果循环技术很小并且不断变化，那么CPU可能偶尔预测循环分支已经退出了。

通常乱序执行机制是自动工作的，但是程序员也可以做一些事情来最大限度的利用乱序执行，最重要的是避免过长的依赖链。还可以混合不同类型的操作，便于CPU在不同的执行单元之间均匀的分配工作，例如可以混合整数和浮点计算（但是不要同时在整数和浮点之间转换），将简单整数与向量整数混合使用，将数学计算与内存访问混合使用等。