Yebangyu's Blog

Fond of Concurrency Programming and Machine Learning

Hardware and its habit

最近在阅读《Is parallel programming hard》这本书,本篇就是整理其中第三章《Hardware and its habit》,不是单纯的翻译,只是一个总结,略有补充。

这章介绍了影响CPU执行效率的几个因素。具体包括:

  • 流水线被打断
  • 内存访问
  • 原子操作
  • Memory Barrier
  • Cache Misses
  • IO 操作

这其中,前面两个,流水线被打断以及内存访问主要针对串行程序,而后面四个主要针对并行程序,因为在并行程序中显得更为突出。

流水线被打断

现代CPU执行指令采用流水线设计和指令预取机制,而影响流水的两种重要情况是停机等待和分支判断失败。前者是CPU没有足够的信息来判断取哪些指令(例如,涉及到C++中的虚函数时)。而分支判断失败,则是取了指令但是没取对。例如

int a = get();
if (a == 1)
{
  //A
}
else
{
  //B
}

假设CPU预取指令A。当预测失败时(a不等于1),流水线中A指令需要被冲刷(flush),继而载入B指令。冲刷流水线和载入B指令都是非常昂贵的操作,因此这深深地影响了效率。

因此,在实际编程时,应该将最有可能执行的代码放到最前面。在gcc中内置提供了likelyunlikely宏,来优化程序分支判断。

#define  likely(x)        __builtin_expect(!!(x), 1) 
#define  unlikely(x)      __builtin_expect(!!(x), 0) 

因此,上面的程序可以改写为:

int a = get();
if (unlikely(a == 1)) //根据实际情况选择unlikely或者likely
{
  //A
}
else
{
  //B
}

内存访问

这个不用说了,内存访问是昂贵操作,相对于寄存器、cache而言。

在上世纪的系统中,从内存中读一个值的速度要比CPU执行一条指令快速。后来,由于CPU的快速发展以及内存容量的增大,这种局面发生了改变。你能想象只有4KB内存的机器吗?现在,光是cache都不止4KB了。

数组通常有比较好的内存访问模式,也就是说访问了a[0],就可以将a[1],a[2],a[3]等存进cache,等访问到a[1]时不需要去访问内存了。但是一般用指针实现的链表的访问模式则比较差。恩,所谓的空间局部性。

原子操作

gcc内置提供了一系列的原子操作,包括著名的用于CAS(compare and swap)的__sync_bool_compare_and_swap等。当多个线程对一个内存变量进行原子操作时,往往依赖于硬件支持。在早期的Intel CPU里,原子操作时,锁住总线,防止其他cpu core访问该内存单元。

Memory Barrier

CPU对指令可能采取乱序执行,以达到优化的目的。但是,并发访问的锁破坏了这种机制。

//here
c = 3;
lock.lock();
a = 1;
b = 2;
lock.unlock();
d = 4;
//there

a=1绝对不会被乱序到here处执行,b=2绝对不会被乱序到there处执行。(不过需要注意的是,c=3d=4是有可能被拉到临界区里执行的)

lockunlock中包含了memory barrier。由于memory barrier和乱序执行是对着干的,用来防止乱序执行的;而乱序执行一般是优化的手段和方法,因此memory barrier往往带来性能下降。

Cache Misses

先贴一张现代CPUcache架构粗略图。

cmd-markdown-logo

多个CPU core,一个内存。cachelinecache块单位,一般在32256字节左右。cacheline是这张图中不同模块的数据交互元素。

每两个cpu coreInterconnect组成一个die,同一个die中的cpu core通过Interconnect来沟通。不同die里的cpu core通过System Interconnect来沟通。

某个core需要对内存变量进行修改时,该变量的cacheline如果位于别的corecache里,这种情况下的cache miss代价很大。

书中举了一个相对简单的例子:cpu 0需要对一个变量进行cas操作,检查自己的cache,发现没有。这时候:

1,cpu 0发送请求给Interconnect(cpu 0 & cpu 1),后者检查cpu 1cache,发现木有。

2,Interconnect(cpu 0 & cpu 1)将请求发给System Interconnect,后者检查其他的3die,得知cacheline位于由cpu 6cpu 7 组成的那个die里。

3,请求被发给由cpu 6cpu 7组成的那个die里的Interconnect(cpu 6 & cpu 7),它同时检查cpu 6cpu 7cache,得知cacheline位于cpu 7cache里。

4,cpu 7cacheline发送给Interconnect(cpu 6 & cpu 7), and flushes the cacheline from its cache,以保证cache一致性

5,Interconnect(cpu 6 & cpu 7)将cacheline发送给System Interconnect

6,System Interconnectcacheline发送给Interconnect(cpu 0 & cpu 1)

7,Interconnectcpu 0 & cpu 1)将cacheline存入cpu 0cache里。

是啊,这已经是简单的情况了。想想看,什么情况下更复杂?