CMU15-418notes(10-18)

视频：https://www.bilibili.com/video/BV1Rh4y1F7aU/?spm_id_from=333.788&vd_source=463e5b3e4b18e5453477b57388c2e427

课程主页：http://15418.courses.cs.cmu.edu/spring2016/lectures

Lecture 10: Snooping-Based Cache Coherence

本节主要介绍监听式缓存一致性协议，在量化研究方法里面已经学习过了，直接回顾当时的笔记。

为多个处理器保持缓存⼀致性的协议被称为缓存⼀致性协议，协议的关键在于跟踪数据块的共享状态。缓存一致性的问题要在极短的时间解决，因此需要采取硬件方法。

实现监听⼀致性协议有两种⽅法，⼀种是写⼊失效协议，处理器执⾏写⼊操作时使其他副本失效；另⼀种是写⼊更新协议，处理器执⾏写⼊时更新所有缓存副本，这种⽅法要占⽤相当多的带宽(写⼊操作要⼴播到共享缓存线)，因此不常⽤，多处理器都选择实现写⼊失效协议。

监听⼀致性协议通常是通过有限状态控制器实施的，控制器可以改变所选缓存块的状态，并使⽤总线访问数据或使其失效。可以看作每⼀个块有⼀个关联的独⽴控制器。
在协议中，规定每个CPU的每个块有三种状态：

⽆效：所有缓存中都没有此块的有效副本
已修改(独占)：该块仅在该CPU缓存中有副本，并且被修改过
共享：该块在⼀个或多个缓存中有副本且未修改过

每个CPU都独⽴控制每个块的状态，通过监听总线转换块的状态，并进⾏读写操作。

假设⼀个CPUA中产⽣了⼀个对⼀个缓存块的读写请求，根据读写是否命中，CPU会有不同的处理⽅式，并改变该块的状态。已修改状态直接称为独占。

读命中：状态不需要发⽣改变。⽆效态不会产⽣读命中，⽽独占和共享态，读⾃⼰缓存中的块不会引起⼀致性的问题。
读不命中：发⽣读不命中，则CPUA要从主存读取该块，但是主存中的块不⼀定是最新的，所以CPU还会向总线发送⼀个读不命中信号和当前块的地址，其他CPU的控制器监听到该信号，如果都没有这个块或者有共享态的该块，说明主存中是最新的，那么从主存中读取到该块，并将其设置为共享态；如果⼀个CPUB发现⾃⼰有独占的该块，则终⽌CPUA读取主存，因为⾃⼰的数据是最新的，CPUB将提供给A这个块，并将其写回内存，此时A和B都有块的最新版本，且主存中的也是最新版本，A和B中该块的状态设置为共享态。(注意，CPUB是独占该块的，A和B以外的CPU⼀定是没有这个块的，所以也不需要改变状态。)
写命中：如果该块在CPUA上是共享态，那么要修改为独占态，且向总线发出写⼊失效信号，其他CPU中的该块都将⽆效；如果该块在CPUA是独占态，那么状态不变。
写不命中：将该块设置为独占态，并向总线发出写⼊失效信号，使其他CPU的该块⽆效，如果其他CPU独占该块，则要写回内存(这保证了写⼊操作的串⾏化)。

通过以上的分析，CPU改变⼀个块的信号的原因可能是读写事件，也可能是从总线监听到的其他CPU的读写事件。⼀个块在被写⼊后就会被修改为独占态，通过向总线发送信号使其他CPU的该块失效。在读取时，如果发⽣了不命中，则读不命中和地址被⼴播，独占块的CPU要给出该块，并将该块写回。这两个关键的⼯作保证了任何CPU总是能读取到最新的块，保证了⼀致性。

最后，以上所有的操作都没有考虑缓存替换的问题，如果发⽣了缓存替换，被替换的块如果是独占态，则要写回主存，只有⾃⼰有被替换块的数据，不需要发出其他信号。

Lecture 11: Directory-Based Cache Coherence

总线式系统的带宽存在限制，采⽤分布式系统可以降低对存储器的带宽要求。在分布式系统中，采⽤分布式的存储器，多个节点可以同时读取或写⼊数据，提⾼了存储器的带宽，不受单⼀存储器总线的限制。分布式系统没有总线，通过⽹络互连，为了避免监听式⼀致性协议的⼴播，分布式存储器系统采⽤⽬录式协议替代监听式⼀致性协议。

⽬录式⼀致性协议中，每个处理器都有⼀个⽬录，⽬录中保存了每个可缓存块的状态，信息包括哪些缓存拥有这个块的副本，是否需要更新等等。存储器的每⼀块都在⽬录中有对应的⼀项，每个⽬录项由访问状态和位向量组成，位向量记录了各个处理器是否有这个块的副本。

在⽬录式⼀致性协议中，仍然使⽤三种状态，采⽤写失效策略。状态转换也和监听式是⼀样的，只是不再通过⼴播告知其他处理器⼀个块失效，⽽是根据位向量，通知相应的CPU该块失效或完成更新该块的⼯作。并且由块所在的存储器所属的CPU作为宿主与需要沟通的处理器沟通，完成写失效通知和写回的操作。

监听法基于总线，通过⼴播信号来实现写失效，优点是不需要额外的存储空间维护⼀致性信息，缺点是可扩展性差，处理器数量越多，总线通信的压⼒就越⼤。

⽬录法采⽤集中式的⽬录维护⼀致性信息，增加了存储开销。⼀致性信息是集中式的存储在⽬录中，但⽬录结构本⾝是分布式的，因此具有可拓展性。⽬录法最⼤的优点是可以实现在分布式的系统中，不需要总线。

Lecture 12: A Basic Snooping-Based Multi-Processor Implementation

本节的主要内容是监听式多处理器的实现细节。

L1和L2的一致性

第一个问题是处理器内部缓存的一致性：

L1缓存有一致性协议的状态，L2中相应的块也必须有相同的状态。但是L2的内容并不总是包含L1，假设下图中发生了一次L1和L2的B miss，B块从内存中读入L1和L2，接下来有多次对A的访问，且都在L1命中，假设set0还映射了块C，当访问C不命中时，L1选择换出B，而L2则选择换出A，这样L1的块就不是都在L2中包含了，就会影响缓存一致性的状态更新。

解决方式是在L2中加一个in L1位，当从L2换出块时，根据这个位也使L1中的该块无效，就可以保证L1中的块在L2中一定存在。不过假设采取写回策略，L2中块的内容和L1可能不一致，因此还需要一个位，表明一个块修改过，但L2不拥有：

当监听到对X的读写时，L2从L1中读取该块，再根据协议进行相应处理。

总线上的并发问题

课程在这里还回顾了一些常见的并发问题的概念，包括活锁，死锁，饥饿问题，这里不再赘述了。

原子性总线

保证原子性的总线，在访存等操作前要先获取总线权限，然后再发送数据和命令，并接收响应。

对于缓存中的行，处理器和监听控制器都需要检查行的Tags和State位，为了保证不发生冲突，在两端都保存一份Tags和State，并保持这两份数据的一致(可以同时读，写时要同步)。(这里图里还放个snoop dog)

为了实现一致性协议，还需要一些信号线：

如果缓存能提供数据，memory就不需要响应，否则memory就要发送数据。

对于写回的情况，需要写入内存替换的块，读出需要的块，这两个操作会消耗更多时间，为了加快读取数据，在内存和缓存之间会有一个缓冲区，在写回时立即返回读取的数据，将写入的数据flush到缓冲区稍后写入内存：

在总线上会发生并发问题：

死锁：P1在等待总线权限，而P2需要P1修改过的块B，而P1无法响应，就会发生死锁。
活锁：P1和P2都要写同一个块，发出写入信号后互相使对方的操作无效。
饥饿：有处理器一直无法获取总线权限。

非原子性的总线

使用非原子性的总线，一个操作会被分为请求和响应两个部分来完成，因此产生了一些新的问题：

如何匹配请求和响应
怎么处理请求的冲突
最多可以有多少未处理的请求
监听结果应该在请求时还是响应时确定

考虑到以上问题，一个基本的设计为：

请求和响应分别处理
使用request table来匹配请求和响应，每个cache都有request table的副本
最多同时有8个请求
响应不需要和请求的顺序相同，系统的整体顺序是按照请求顺序
cache和缓存都有buffer来接收总线的数据，如果buffer满了就发送NACK稍后重试
避免冲突，如果有一个对块A读的请求，那么同时对块A的写请求就会被阻塞或放入队列等待(不要让冲突发生，请求和响应的顺序对于监听结果就无所谓了)

由于请求和响应是分别处理，可以进行流水线化：

再回到总线的并发问题，可以采用队列来保存请求，这样在请求的同时就可以继续监听(这里不是很理解)。然而如果队列满了，又会发生死锁：

解决方法是区分出request和response队列：

最后是一个访存时发生的事件练习：

缓存是以行为单位存储的，通常为64字节。存在一种情况，多个线程操作不同的成员变量，但是这些变量在相同的缓存行，这样二者都需要改动时，就会导致不同核都要修改这一行，然后都要另一个缓存的该行失效，这就导致了两个变量没有关联，但每次修改一个变量时，下次访问另一个变量都要重新从下一级缓存或memory读取，导致性能下降。

解决伪共享的方式就是进行填充，将变量填充为64个字节，这样就能避免上述情况的发生，不过伪共享这种情况很难发现，也并不是都需要解决。

Lecture 13: Memory Consistency

本节所描述的Memory Consistency是处理器在对不同的位置进行读写的行为，这不是保证一个位置的值的正确，而是保证处理器在修改不同值时，能够在不改变语义的同时通过重排序来优化性能，并且重排序不影响其他线程的行为。

如果能保证读后写，读后读，写后写，写后写这四个情况都是顺序发生的，那么可以说访存保证串行一致性，内存中的值始终是和程序中的顺序相同。为了提高性能，可以适当放松一致性的四个要求。最常见的操作就是使用写缓冲区，这样就可以减少写的延迟。

在多线程程序中，读写的重排序会导致其他线程看到的读写顺序和程序中是不一致的，因此需要由程序员和编译器来保证必要的同步。

对于四种顺序情况，有不同的要求，越是放松对四种顺序的要求，一致性就越弱。

C++的atomic库提供了原子性操作，可以保证一致性。

Lecture 14: Performance Monitoring Tools

通过测量才能分析程序，找到程序中最有价值可优化的部分。

time和top可以看到CPU的占用率，以及是否有其他人在使用CPU。

辅助分析程序运行时间的工具有两种，一种是编译时注入代码，一种是在程序运行时工作，对于程序优化，有这样一些工具：

程序优化
- Gprof
- Perf
- VTune
debug
- Valgrind
- Santizers
Advanced Analysis
- Pin
- Contech

根据Amadahl’s Law，应该找到程序运行时间占比最大的部分进行优化，以最快的提升程序性能。因此需要找到程序中的hot code部分。

Gprof可以统计各个函数被调用的次数和时间，是编译时注入的工具，只需要在编译时添加-pg选项，然后运行程序，运行后会出现一个统计文件，再运行gprof progname就可以查看统计结果。

/image-20231101150226101.png)

Perf则是基于现代体系结构的性能分析，可以得出缓存命中，分支预测的情况等。而粒度最细可达指令级。Vtune也是一个类似的工具。

这一节只是一些概述，所以这些工具详细的使用单独开一篇笔记再学习记录。

Lecture 15: Interconnection Networks

本节的内容是内部节点之间的网络结构，这些网络连接了不同内核，核与内存，缓存与缓存等，I/O设备等。

网络结构决定着系统的扩展性，也影响着系统的性能。在设计网络时，要考虑的问题有：

拓扑结构：影响路由，延迟，复杂度等
路由：消息是怎么传递的，是静态路径还是动态确定路径
缓存和流量控制

共有两种拓扑结构，一种是直接的，一种是间接的，间接的需要switch。同时还有blocking和non-blocking的选择(假设同时只能传递一条消息)。

拓扑结构

这里看起来是网格，但实际上是全连接的。

本节的最后一下部分是介绍缓存和流控制的，讨论了分组交换和电路交换，和计网的概念是完全一样的。

最后的总结，interconnection网络对于现代多处理器是非常重要的，因为bus扩展性差，并且现今都开始在芯片上设计网络了。不同的拓扑结构的性能表现不同，开销等其他方面也不同。

Lecture 16: Implementing Synchronization

在本节的开始首先复习了超线程。超线程技术下，每个核的两个线程指令流执行是由硬件处理的，有两个上下文同时存在。例如一个支持超线程技术的两个CPU(每个六核)的系统，显示的processor数量有24个，实际上是有12个核，24个执行执行上下文，因此逻辑上有24个核。

本节的内容是关于同步的实现的。

最简单的同步方式是忙等待和阻塞：

//忙等待
while (condition X not true){}	
logic that assumes X is true;
//阻塞
if	(condition	X	not	true)	
	block until true;

如果是短时锁，使用自旋锁更好，因为不会等待太长时间，阻塞调度会产生开销浪费时间。

Implementing Locks

最基本的锁是test-and-set原语实现的自旋锁：

1
2
3

lock: 
ts R0,mem[addr]								//	load	word	into	R0				
bnz R0,lock									//	if	0,	lock	obtained

因为lock值是volatile的，其他处理器的线程会持续请求从内存读写lock数据并独占lock，占用总线资源，如果刚好持有锁的处理器释放锁，也可能被其他线程占用总线而延迟释放锁。

解决方式是等有机会获得锁再进行testandset操作，这种锁称为TTAS锁。尽管读取lock的值仍然要从内存获取，但不会再产生独占缓存行的流量了。

避免持续尝试获得锁的流量，可以进行退避：

TTAS实现的锁释放后，其他处理器都会尝试TAS写操作来独占锁，也会引起总线的大量流量。并且上述锁都不保证公平性，可能会有饥饿产生，更公平的锁是使用队列：

这样每个锁的获取只需要一次原子操作，此后就不需要其他原子操作了。不过释放锁的时候会使所有处理器的l->now_serving缓存行失效，还可以进一步优化：

这样每个尝试获取锁的处理器就只等待一个内存地址的值的修改了，进一步减少了总线流量。

Additional primitive atomic operations

LL/SC指令

链接加载和条件存储指令，在arm架构中同样的是LDREX and STREX指令。LL指令加载后的地址如果没有被修改过，SC指令会完成store操作，如果被修改过，就不会进行store操作。

C++ 11 atomic

提供原子性读写，实现方式可能是锁，如果类型是基本类型，也可能是硬件原语。

atomic<int>	i;
i++;										//atomically increment i	
int	a = i;	
//do stuff
i.compare_exchange_strong(a, 10);			//if i has same value as a, set i to 10
bool b = i.is_lock_free();					//true if implementation of atomicity is lock free

Implementing Barriers

以下是一个错误的barrier实现，由第一个到达的线程清空flag，最后一个线程设定flag，但是如果最后一个线程设定后，有线程没有离开barrier，其他线程就到达了下一个barrier，又清空了flag，这个线程就被卡在第一个barrier里了。

解决问题的一个办法是设定leave_counter，等所有线程离开barrier再重新清空flag。

以上是正确的barrier实现，但是有两个忙等待，更好的方式是更改flag的定义，让flag在一个barrier中为0表示未全部到达，在下一个barrier中为0表示已全部到达，线程需要知道自己在的临界区中barrier对应flag的值应该是多少才可以继续，这样通过一个barrier后，第一个进入下一个barrier的线程修改flag的值，不会导致其他线程卡在barrier当中：

以上的barrier都是中心化的，需要通过counter值判断是否全部到达barrier，这就导致写counter必须上锁，如果改为树形结构，就可以减少延迟(获取每个锁的线程少了)：

Lecture 17: Fine-grained synchronization & lock-free programming

以链表为例，如果对整个操作上锁，数据结构就会编程串行操作。如果采用细粒度的锁，让每个节点都有锁，在操作时只上操作节点的锁，就可以提高并发度，在移动过程中，只有持有当前节点的锁，才能获取下一个节点的锁，获取后再释放这个节点的锁：

细粒度的锁仍然是基于锁的，在某些情况下，可以实现无锁的数据结构。以一个队列为例，如果已知只有一个读者和一个写者，就可以实现无锁队列，方法是将唯一修改节点的能力写在push中，而pop操作只移动指针，另外增加一个reclaim指针用于释放节点：

再考虑栈的无锁实现，对于一个基于链表的栈，所有的操作都是对表头指针进行的，即栈的top，最基本的处理方式就是用原子指令判断top是不是进入操作时的top，如果是就可以完成操作，不是就重新获取栈顶元素指针：

但是这种方法会出现ABA问题，即指针被复用了，但指向的节点不同了：

/image-20231116103832471.png)

解决方式是添加pop_count，以防止中间发生pop后，指针复用导致的ABA问题，不过这需要硬件对DOUBLE CAS的支持，才能同时对pop_count和top进行CAS：

另外一个问题是在进行pop时，要修改栈指针为old_top->next，然而此时old_top可能已经被释放掉了(对应上述代码，还Node* new_top = top->next)，解决方式是加一个harzard ptr，把pop掉的节点通过harzard ptr添加到一个队列，足够多了再一起进行释放，这样就延迟了old_top的释放，不会出现上述问题。(下面的实现使用doubleword CAS，直接对oldstack和newstack进行CAS，逻辑和上面的代码是一样的。)

/image-20231116104636333.png)

无锁数据结构可以避免锁的开销，但仍然需要memory fence保证内存的一致性，并且具体的使用情况要根据情况决定，并不能消除竞争。