片上众核处理器硬件同步机制研究*徐卫志1,2刘志勇1范东睿1焦帅1,2张浩1宋风龙1雷峥蒙1,2余磊1,21（中国科学院计算技术研究所系统结构重点实验室北京 100190）2（中国科学院研究生院北京 100039）摘要同步机制是片上多核/众核处理器正确执行和协同通信的关键，其效率对处理器的性能非常重要。
本文针对片上众核体系结构，提出了两种硬件粗粒度同步机制，集中式同步机制和分布式同步机制，分别通过片上的集中式锁管理器和分布式锁管理器来实现；以片上同构众核处理器Godson-T模拟器为平台，通过量化评估程序，评估比较了提出的两种硬件支持的同步机制与基于原语的软件同步机制的性能。
结果表明，硬件支持可以使得片上众核处理器的同步机制性能明显提高，而分布式锁管理器的扩展性要好于集中式锁管理器。
关键词片上众核处理器；同步；硬件支持；集中式锁管理器；分布式锁管理器中图法分类号: TP302 文献标识码: A1 引言传统单核处理器采用指令级并行的技术提高性能，借助于超标量和流水处理提高处理器的主频，但是随着主频的提高却使得功耗和散热问题难以依靠现有的技术解决。
而半导体工艺的发展，使得片上可集成的晶体管数目日益增多，因而体系结构设计者为了在性能进一步提升的同时降低功耗和散热，提出了线程级粗粒度并行的片上多核/众核处理器[1]。
片上多核/众核处理器与传统多处理器相比，其优点是片上处理能力强、带宽高、通信距离短、传输速度快等，多个线程之间的数据通信效率高，因而需要高效的同步机制与之匹配。
同步操作保证多个线程之间的数据传播，临界区的互斥访问使得多个线程对共享存储的写操作等同于串行执行，保证程序执行语义的正确性。
因而，同步操作的性能对片上众核处理器而言非常重要，直接影响了多个线程协同执行的速度。
在传统多处理器系统中，已有许多针对于互斥操作的研究，主要可以分为两类，一类是设计更好的软件算法，第二类是为其提供专用的硬件支持等。
软件锁的缺点在于同步开销大、扩展性差、存储空间要求高等。
例如，Test&Set锁[2]是基于原子指令Test&Set的软件锁，它需要每个参与同步的线程不断地执行Test&Set指令，每一次执行Test&Set指令，就检查并修改对应的内存块，造成大量的访存操作和网络操作，当线程数增多时，Test&Set锁的扩展性很差。
虽然已经有一些改进的基于原子指令的软件同步方法，但是原子指令实现困难，代价高，当片上集成了成百上千个处理器核时，软件锁难以满足众核处理器的性能需求，势必形成“synchronization wall”。
虽然基于同步原语的软件锁相对于硬件锁较灵活，但是在众核片上支持硬件锁，可以充分利用片上通信速度快的特点，大大提高同步操作的效率，从而提高整个芯片的计算能力。
文献[3]针对于众核处理器Cyclops-64，提出了专用的硬件同步状态缓存器SSB，用于支持细粒度的同步操作，目的是有效利用众核处理器的片上处理能力。
然而，硬件支持对于片上众核处理器中粗粒度同步机制的性能影响仍没有相关的研究。
因而，我们提出了基于片上众核体系结构的两种硬件粗粒度同步机制，使用专门的片上锁管理器来实现同步，包括集中式锁管理器和分布式锁管理器，从不同角度评估了硬件支持对片上众核结构同步机制的性能提升，将集中式同步机制，分布式同步机制，以及软件同步机制进行了比较。
结果表明，硬件支持可以使得片上众核处理器的同步机制性能明显提高，而分布式锁管理器比集中式锁管理器扩展性更好。
本文如下组织：第2节介绍多核/众核同步机制的相关研究工作，包括基于原语的同步机制实现方式，硬件同步，细粒度同步，事务内存等；第3节提出片上众核结构中专用硬件支持的同步机制，包括集中式同步管理器与分布式同步管理器，为了评估需要，在片上众核结构中也实现了Ticket Lock；第4节介绍模拟平台和试验结果，并对结果进行分析，对软件锁和硬件锁，集中式锁管理器和分布式锁锁管理器进行比较；第5节总结本文，并提出进一步的工作。
*本课题得到国家自然科学基金重点项目(60736012)、国家“九七三”重点基础研究发展规划项目基金(2005CB321600)、国家“八六三”高技术研究发展计划项目基金(2009AA01Z103)、国家杰出青年科学基金(60925009 )、国家自然科学基金创新研究群体科学基金(60921002)、北京市自然科学基金（4092044）资助。
徐卫志（1982年生），男，山东龙口人，博士研究生，主要研究方向为高性能计算机体系结构、并行算法等；刘志勇(1946年生)，男，博士，研究员，博士生导师，主要研究领域为算法、计算机系统结构、并行处理、片上存储系统等；范东睿（1979年生），男，博士，副研究员，主要研究方向为低功耗处理器设计；张浩，博士，助理研究员；宋风龙，博士；雷峥蒙，硕士研究生；余磊，博士研究生。
2 相关研究互斥访问同步机制提供了共享数据的互斥访问（原子访问）方式，保证了临界区内对共享资源的整体性操作。
各种互斥访问同步机制的不同主要在于三点，即处理开销、存储开销和对网络造成的影响。
同步机制一般能够通过“读－修改－写回”的同步原语来实现，如TAS、FAA、SWAP、CMPXCHG和LL/SC等同步指令。
Test&Set锁[2]采用轮询标志位的方式，造成大量的访存操作和总线操作，当处理器核数增多时，竞争更加激烈，扩展性差。
Test&Set Lock with Backoff [2]的方法对Test&Set锁进行改进，当一个处理器核申请锁失败后，不是立刻再次申请，而是隔一段时间再去申请，这种方法减少了轮询的次数，从而减少了总线竞争，但需要设定合理的backoff 。
TEST&TEST&SET[2]也是对Test&Set锁的改进，每个处理器核在本地缓存中轮询锁变量，当有处理器核释放锁的时候，通过无效掉相应处理器核的锁变量来通知其它处理器核，然后其它处理器核执行Test&Set去抢这把锁，这种方法在本地轮询，从而减少了网络消息。
LL（load-linked）和SC（store-conditional）[4][5]是一对相关联的指令，用于实现可缓存在cache中的内存地址的原子操作。
语义是：LL指令将一个内存地址的数据取到寄存器中；随后，可以执行一系列不包含存储操作的任意指令；最后，使用SC指令对与上一个LL指令相同的内存地址进行写操作。
只有当LL指令执行后，所有其他处理器都没有对该地址进行写操作的情况下，SC指令才会执行成功。
因此，SC执行成功则表明对某个地址成功执行了一次“读－修改－写回”原子操作。
如果SC执行失败，则整个操作必须重新执行。
LL/SC指令的优点是所有处理器都在私有cache中自旋，而不必每次都到共享的存储结构中，因而不会对网络造成压力。
其缺点是，需要cache一致性的维护，即当一个处理器执行SC指令时，需要将所有自旋等待的处理器私有cache中的变量都无效，造成大量的无效操作。
Ticket Lock[2]使用两个全局的计数器ticket和turn，初始值都为0；当某个处理器申请锁时，使用原子指令Fetch&Add 将ticket增1作为自己的令牌值，并且当turn的值与ticket的值等时就可以进入临界区；某个处理器释放锁时，将turn增1，作为下一个可以获得锁变量的令牌值。
其优点是只有某个处理器的令牌值与turn的值相同时，才会在锁变量被释放时重新申请锁。
其缺点是每次释放锁并修改turn的值时，会对所有等待的处理器执行一致性操作，将缓存的turn值无效，重新读取更新后的turn值，由于竞争而造成延迟。
Array-Based Lock[6][7]的特点是，每个处理器在不同的内存地址上轮询，释放锁的处理器通过改写下一个等待者地址上的内容进行通知。
其优点是当一个处理器释放锁的时候，只会把下一个等待锁的处理器对应的缓存块无效掉，这时只有一个处理器去读取内存。
其缺点是需要O(p)的存储空间，p是处理器个数。
Ticket Lock和 Array-Based Lock都能保证各个处理器按顺序获得锁，保证了公平性，另一种“公平”锁为MCS锁[8]，它使用软件的分布式链表维护等待队列，每个等待的处理器自旋在该链表的一个独立节点上。
其优点是释放锁的处理器可以只唤醒等待在队列头的那个处理器；其缺点是空间开销和等待的处理器数目成正比。
QOLB[9][10]（Queue on Lock Bit），也是形成一个锁链表，每一个处理器的队列信息(锁的下一个申请者)保存在一个缓存块里，等待锁的处理器在本地缓存块上轮询，在内存里保存锁链表的头和尾。
其缺点是，增加了缓存块的状态数目，导致基于目录或监听的一致性协议更加复杂，因而不具有扩展性。
此外，在粗粒度同步方面，文献[11]提出了针对SMT处理器的Lock Box，文献[12]提出了Lock Cache，文献[13]提出了基于总线结构的分布式同步方法。
在细粒度同步机制的研究中，基于Full/Empty 位的同步机制已在Tera 机器中出现[14]。
Full/Empty位标记内存单元中的数据是否已经符合进一步处理的条件，即值为1表示数据可用（Full），而值为0则表示数据不可用（Empty）。
这样在访问内存时，实现了轻量级的线程同步。
文献[3]提出了使用同步状态缓存来实现细粒度同步，基于同一时刻只有少量的数据需要同步的观点，节省了存储空间。
其缺点是，一旦硬件SSB大小不够，需要软件解决时，同步的时间开销就变大，而且自旋锁的问题也没有很好的解决。
事务内存[15]采用一种lock-free的方法来访问共享数据，把一组load和store指令作为原子操作，即这一组操作要么全部执行完成，要么就全部撤销，重新开始执行。
使用事务内存可以避免锁机制导致的一些问题，如死锁。
3.片上众核处理器的同步机制本节介绍众核结构中的片上硬件粗粒度同步机制，包括集中式锁管理器和分布式锁管理器，并对这两者进行了比较，为了评估需要，也在众核结构中实现了一种软件锁——Ticket Lock。
3.1 片上集中式锁管理器图1 Godson-T混和式片上多核/众核体系结构在片上众核处理器中引入专用的硬件集中式锁管理器（Centralized Lock Manager，简记为CLM），如图1右下角所示，其中Core是片上处理器核，Core与Core之间、Core与CLM之间通过片上的router相连。
CLM将互斥访问同步操作组织为先进先出队列。
当某个处理器核发出申请锁请求时，通过片上互连网络将申请锁请求发送到CLM，CLM接收到请求后，为其分配表项，将请求信息写入表项。
