清华大学提出新型并发控制算法，大幅提升事务内存系统性能，获顶会最佳论文提名

10月12日~16日，第52届国际微架构会议(International Symposium on Microarchitecture，简称MICRO)在美国俄亥俄州哥伦布市召开。清华大学魏少军教授、刘雷波教授团队在会上做了题为《应用于事务内存的乐观并发控制算法的FPGA加速》（FPGA-Accelerated Optimistic Concurrency Control for Transactional Memory）的报告，介绍了团队设计的新型并发控制算法以及使用可重构架构加速算法执行的方法，在评估事务内存系统性能的STAMP测试集上，该算法相比Intel处理器内置的TSX（Transactional Synchronization Extension, 事务同步扩展）指令集获得了8倍以上的性能提升。

该论文是亚洲高校及科研机构在MICRO 52年历史上第二次获得最佳论文提名，论文的第一作者是李兆石博士，通讯作者是刘雷波教授。

图1 清华大学李兆石博士在MICRO 2019上作报告

事物内存是解决多任务并行时线程间同步问题的主流方案之一，规避了使用锁时出现的优先级反转、死锁、护航等问题，极大的提高了任务并行度。但是，现有事务内存并发控制算法在实现可串行化一致性时存在固有缺陷——由于判断算法的简化和不精确，引起许多不必要的访问撤销，导致性能受限。

该项研究立足于并行编程使用的事务内存方法，利用数学的序关系理论分析了常见的事务内存一致性模型，然后为了解决上述固有缺陷设计了新型并发控制算法，并利用可重构架构的空间计算特性加速该算法。如图2所示，事务之间的读写依赖关系在可重构架构上的Manager模块以矩阵的形式在空间上平铺开来，这样算法可以更高效地检索并更新事务间读写依赖关系。之后在CPU-FPGA异构可重构系统上实现了基于该算法的高性能的事务内存系统的原型系统，在评估事务内存系统性能的STAMP测试集上相比Intel处理器内置的TSX（Transactional Synchronization Extension, 事务同步扩展）指令集获得了8.05倍的性能提升。该研究分析一致性模型的方法不仅限于事务内存系统，还可推广到分布式系统、多处理器缓存一致性等问题的研究中。

图2 该研究提出的新型并发控制算法在可重构架构上的实现

过去10余年，清华大学魏少军教授、刘雷波教授团队聚焦可重构芯片技术研究，在国家自然科学基金重点项目、重点研发计划项目、863计划重点项目及其它国家计划项目的支持下，在可重构芯片领域取得了多项重大技术突破。在JSSC/TIFS/TPDS等领域顶级期刊上发表论文200多篇，在ISCA/HOT CHIPS/DAC/VLSI等领域顶级会议发表论文20余篇；授权发明专利60余项；出版学术专著5部；参与制定国家标准1项，参与国际标准化组织提案1项；相关技术曾获得国家技术发明二等奖、教育部技术发明一等奖、中国电子学会技术发明一等奖、中国发明专利金奖、世界互联网大会15项世界互联网领先科技成果等重要科技奖励。

关于MICRO

国际微架构大会，the International Symposium on Microarchitecture (MICRO)，是计算机体系结构领域的重要会议，与ISCA、HPCA、ASPLOS并列计算机体系结构四大顶级会议，论文录取率通常在21%左右。神经网络加速器、专用加速器结构、DRAM、持久性内存、GPU加速器、近内存加速器等，都在MICRO上被首次提出。