Amdahl定律

我们先从amdahl定律[1]说起，这是一个经验公式，描述了一个系统中，任务执行的延迟加速比。任务的延迟加速描述如下：

其中，p是整个任务中可以被并行的部分，s则是执行任务的并行线程数。假设当p=1/2时，也是说一个任务中可并行的部分占比整个任务的一半，这个时候即使并行的线程数s=∞，加速比也只有2，任务只能快一倍。所以在一个多核处理器系统中，即使核数再多，线程再多，任务可并行的部分决定了最大的加速比。因此并发编程中最关键的部分是将尽可能地扩大任务中可并行的部分，这也是后续内容的核心。

上一节中，我举过一个累加的例子，在线程数增加的情况下，延迟反而没有减少。原因就是对内存中同一个变量的加一操作本身就是一个不可并行的任务，再加上多线程并行执行的情况下，该变量更新的cache冲突会变得很严重（后续讲解cache coherence protocol[2]的时候会细说这里），导致延迟不但没有得到优化，反而还下降了。这里我用c++代码展示这个累加的例子：

void th(int* cnt)
{
  while (__sync_fetch_and_add(cnt, 1) < max_cnt) {}
  return;
}
void Test(const int thread_cnt)
{
  vector<thread> ths;
  int cnt = 0;
  uint64_t c = rdtscp();
  for (int i = 0; i < thread_cnt; i++) {
    ths.push_back(thread(&th, &cnt));
  }
  for (int i = 0; i < thread_cnt; i++) {
    ths.at(i).join();
  }
  uint64_t d = rdtscp();
  cout<<"thread cnt" << thread_cnt <<" used:"<<d - c<<endl;
}
int main()
{
  Test(1000);//为了预热
  Test(1);   //latency : 1702538261
  Test(10);  //latency : 4816327883
  Test(100); //latency : 5773059772
  Test(1000);//latency : 5850909219
  return 0;
}

结果：

用amdahl定律作为指导思想，我们需要扩大任务中可并行的部分。为了达到这个目标，需要将原本单个变量拆解为多个变量，将原本累加100000000次的任务，拆解为n个累加100000000/n次的任务，从而增加amdahl定律中，可并行化的部分p，因而提升任务执行的加速比。c++代码如下：

struct CacheAlignT
{
int cnt = 0;
} __attribute__ ((aligned (64)));
void th(int target_cnt, CacheAlignT* t)
{
  while (__sync_fetch_and_add(&t->cnt, 1) < target_cnt) {}
  return;
}
void Test(const int thread_cnt)
{
  vector<thread> ths;
  vector<CacheAlignT> cnts(thread_cnt);
  uint64_t c = rdtscp();
  for (int i = 0; i < thread_cnt; i++) {
    ths.push_back(thread(&th, max_cnt / thread_cnt, &cnts[i]));
  }
  for (int i = 0; i < thread_cnt; i++) {
    ths.at(i).join();
  }
  uint64_t d = rdtscp();
  cout<<"thread cnt" << thread_cnt <<" used:"<<d - c<<endl;
}
int main()
{
  Test(10);//为了预热
  Test(1);   // latency : 1699145424
  Test(10);  // latency : 171877508
  Test(100); // latency : 104265484
  Test(1000);// latency : 102759167
  return 0;
}

结果：

可以看到将累加任务拆开后，加大并发线程数是可以减少延迟的。但是细心的同学应该发现了，我将CacheAlignT指定为64Byte也就是cache line对齐。如果不把CacheAlignT指定cache line对齐结果又如何呢？

可以看到，只是简单的拆开变量并不能提升性能，必须将拆开的变量打散到不重复的cache line上，才会有性能的提升。后面的章节会详细介绍cache coherence protocol的相关内容，再来解答这其中的奥秘。

[1] https://en.wikipedia.org/wiki/Amdahl%27s_law
[2] https://en.wikipedia.org/wiki/Cache_coherence