最近一段时间，有关超算的话题成为热门，一时间大家都开始讨论超算，然而，笔者发现在所有这些讨论中，从没有在任何时间任何地点发现任何人问出就连小学生都经常问的问题：超算到底是怎么算的？不得不说是一件可悲的事情。

　　【并行计算怎么算】

　　我们知道，单个CPU核心只能串行计算，也就是一条一条的把机器指令读出来执行。要理解的一点是，串行执行并不表示指令顺序执行，跳转指令可以让CPU跳到其他地址执行，但是整个过程CPU只在执行一个单一的指令流，也就是一个线程，thread。某个线程完成某种任务，而线程对应的代码中的多个函数又各自分工完成对应的工序。要想同时执行多个线程的话，有两个办法，一个是增设额外的一个或者多个CPU，这样，在时间上可以做到Parallel/并行，同一时刻有多个任务同时执行；另一种办法则是让单个CPU执行一段时间线程1，然后再强行跳转到线程2执行一段时间，然后再跳回到线程1，这样就可以实现多个线程的Concurrency/并发，但是却不是并行，因为同一个时刻还是只有一个线程在执行，只不过每个线程执行的时间非常短，一般比如10ms的时间，就会跳转到其他线程执行，这样从表面看来，一段时间内，多个线程似乎是“同时”执行的。

　　前者的方式看上去性能更高，但是其有2个惨痛的代价，第一个是线程之间的同步，第二个是缓存一致性。如果多个线程运行在同一个核心上，那么它们只能一个接一个的执行，执行线程1时线程2不可能得到执行，如果线程1和线程2要操作同一个变量，那么就轮流操作，不会有问题。但是多个线程运行在不同的核心上，事情就发生很大变化了，比如有两个线程，都需要操作某个变量，比如同时运行a=a+1这个逻辑，期望结果是线程1对a加了1，线程2要在线程1输出结果的基础上继续+1，而由于这两个线程运行在两个独立核心上彼此之间没有协调，可能导致线程1读到的a的初始值0，加1之后还没来得及将最新结果更改到a所在的地址之前，线程2也读到了a的初始值0，加1之后也尝试写入同样的地址，最后a的结果是1，而不是期望中的2。解决办法则是对变量a加互斥锁，当某个线程操作a之前，先将锁（也是个变量）置为1，其他线程不断的扫描锁是不是已经被置为0，如果是1则表示其他人正在操作a，如果是0则表示其他人已经释放了，那么其将锁改为1，也就是锁上，自己操作a，此时读到的a就会是被其他线程更新之后的最新数据了。这个过程叫做Consistency。所以，如果多个线程之间完全独立各干各的，没有任何交互，这是最理想的场景，这就像多台无须联网的独立的计算机各干各的一样，只不过共用了CPU和内存。

　　然而，如果使用了缓存，又使用了共享变量，事情又变得复杂了。线程1所在的核心1抢到变量a的锁之后会将a的内容缓存到核心1的缓存中，更新了a内容之后，该更新也依然留在缓存中而不是被flush到主存。其释放锁之后，线程2抢到a的锁并将a读入核心2的缓存，此时如果不做任何处理，核心2从主存中读到的将是a的旧内容，从而计算出错。可以看到，即便是使用了锁来保证Consistency，也无法避免缓存所带来的一致性问题，后者则被称为Coherency。

　　Consistency由软件来负责，而Coherency则要由硬件来负责保证，具体做法是将每一笔数据更新同步广播出去给所有其他核心/CPU，将它们缓存中的旧内容作废，收到其他所有核心的回应之后，该更新才被认为成功。所以核心/CPU之间需要一个超低时延的网络用于承载这个广播。这个过程对软件完全透明。除了需要广播作废外，当其他核心需要访问该变量时，拥有该变量最新内容的核心必须做出应答将该内容推送到发出访问请求的核心。

　　在很早期的SMP/UMA架构下，由于那时的SMP总线本身就是一个广播域，任何核心的访存请求都会被其他所有核心收听到，包括更新了某个地址、读取某个地址，这样很天然的可以实现Coherency，比如，当某个核心更新了某个地址之后，其他核心后台默默的收听（或者说嗅探，Snoop），并在自己缓存中查询自己有没有缓存这个地址的内容，有则作废无则不动作。当某个核心发起对某个地址读的时候，其他核心收听之后也默默的搜索自己的缓存看看是否有该内容最新版本，有则使用特殊的信号抢占总线并压制主存控制器对总线的抢占，将数据返回到总线上，与此同时主存控制器也收听该内容并将该内容同步更新到该地址在主存中的副本。此时，该地址将拥有三个副本，分别位于：之前缓存它的那个核心的缓存、刚刚读它的那个核心的缓存、主存，而且内容一致。如果此时之前缓存它的那个核心再次发起读操作，就没有必要将读请求发送到总线上，而浪费电，同时也浪费其他核心的搜索运算耗费的电能以及对其他正常缓存访问的抢占。所以人们想了个办法，每个缓存条目（Cache Line，缓存行）增加一个字段，专门用来描述”该缓存当前处于什么状态“，上述状态称为Share态，而如果有人更新了某个地址，其他核心嗅探到之后，便将自己缓存里这份内容改为”Invalid“态，而刚刚更新内容的那个核心里缓存的该条目被改为”Modified“态，Invalid态的条目已经作废，再读就得走总线，M态的条目可以直接读，因为此时没有其它人有比你新的内容了。如果加电之后某个核心第一个抢到总线并发起该地址的读，则读入之后该条目就是Exclusive态，因为只有它一个人缓存了该条目，当另外核心再发起读之后，该核心嗅探到这个事件，于是将自己缓存里的该条目发送给刚才发起读的核心，那个核心从而知道其他核心也有该内容，于是两个核心一起将自己本地的该条目改为Share态，这两个核心中任何一个如果再发起该地址的读，就不用走总线了，直接缓存命中。可以看到，当某个核心需要访问的数据在其他核心的缓存中时，硬件会自动传递这份数据，软件根本无需关心。所以多个线程之间引用共享变量的时候，直接引用即可。

　　上述方式被称为MESI协议，其目的是为了提升效率，不需要每一笔访问都走外部总线。后来过渡到NUMA架构之后，NUMA是通过一个分布式交换网络来广播同步这些消息以及进行变量内容传送的，由于该网络并非一跳直达的广播网络，所以过滤不必要的广播就更加重要了。不同的CPU厂商有不同的方式，MESI协议也有不少变种，比如MESIF等等。另外，由于失去了天然的总线嗅探机制，如果某个缓存行处于Invalid态，读取该缓存行之前硬件需要发出Probe操作，探寻，主动广播这个Probe请求给所有核心的缓存控制器，缓存了该行的缓存控制器会返回最新数据并将自己该行的状态改为S态。如果要更新某行，该行本地处于E或者M态则直接更新，处于S态则需要发出Probe请求作废其他缓存中的该行。总之，当MESI遇到NUMA，就是个非常复杂的状态机，笔者就不继续展开了，要想与笔者深聊NUMA和Cache Coherency，可接受预约面聊，前提是你得拿出笔者看得上的干货来咱们互换一下。