这篇文档属于类型a（单篇原创研究论文），以下是针对该研究的学术报告：

LPRQ算法：一种无需CAS2指令的高性能并发队列研究

一、作者与发表信息

本研究由Raed Romanov（俄罗斯高等经济研究大学）和Nikita Koval（荷兰JetBrains公司）共同完成，发表于PPoPP ‘23（ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming）会议，会议时间为2023年2月25日至3月1日，地点为加拿大蒙特利尔。论文标题为《The State-of-the-Art LCRQ Concurrent Queue Algorithm Does Not Require CAS2》。

二、学术背景

研究领域：并发数据结构（Concurrent Data Structures），具体聚焦于无锁队列（Lock-Free Queue）的设计与优化。

研究动机：
现代高负载应用（如分布式系统、实时数据处理）依赖高效的并发队列，但现有最优算法LCRQ（Concurrent Ring Queue）依赖CAS2（双地址比较交换，Compare-and-Swap on Two Contiguous Memory Locations）指令。然而，CAS2在多数编程语言（如Java、Kotlin、Go）和硬件架构中未被支持，导致LCRQ的移植性受限。

研究目标：
提出一种无需CAS2的LCRQ改进算法LPRQ（Portable Ring Queue），仅通过标准原子指令（如CAS和FAA）实现同等性能，同时解决现有替代方案（如FAAArrayQueue、LSCQ）的性能缺陷。

三、研究流程与方法

1. 问题分析与算法设计

• 研究对象：LCRQ算法的核心缺陷（CAS2依赖）及其同步机制（环形缓冲区+epoch计数器）。
  
• 改进策略：
  
  • 步骤1：消除dequeue()中的CAS2，改为通过CAS（单地址比较交换）和FAA（Fetch-and-Add）实现同步。
    
  • 步骤2：通过线程唯一令牌（Thread-Unique Token）模拟CAS2功能：
    
  • 保留单元格：enqueue()先将线程令牌写入目标单元格。
    
  • 提升epoch：原子更新单元格的epoch至当前操作周期。
    
  • 发布元素：用元素替换令牌，确保epoch一致性。
    

2. 算法实现

• 代码重构：基于C++实现LPRQ，保留LCRQ的高层结构（环形缓冲区链表），但替换底层CRQ（Concurrent Ring Queue）为PRQ（Portable Ring Queue）。
  
• 关键优化：
  
  • 无CAS2的dequeue()：通过双重检查（读取epoch与值的一致性快照）避免竞态条件。
    
  • 令牌机制：利用线程引用（如JVM的Thread.currentThread()）作为令牌，避免硬件依赖。
    

3. 实验验证

• 基准测试：
  
  • 工作负载：
    
  • enqueue-dequeue对：模拟均衡生产-消费场景。
    
  • 生产者-消费者模型：测试不同比例（1:1、1:2、2:1）下的吞吐量。
    
  • 对比算法：LCRQ、FAAArrayQueue、LSCQ、CC-Queue（基于Flat Combining）。
    
  • 环境：AWS c6i.32xlarge实例（128线程，Intel Xeon 8375C），10次重复实验。
    
• 性能指标：吞吐量（元素传输速率）、L1缓存未命中率。
  

四、主要结果

1. 性能对标LCRQ：

   • LPRQ在所有测试场景中与LCRQ性能持平（误差%），证明CAS2消除未引入额外开销。
     
   • 关键数据：在128线程下，enqueue-dequeue对的吞吐量达2.5×10^7次/秒，与LCRQ一致。
     

2. 超越替代方案：

   • 相比LSCQ（基于32位epoch打包），LPRQ快1.3–1.6倍（1:2生产者-消费者场景）。
     
   • 相比FAAArrayQueue（无epoch复用），LPRQ在高争用下快1.6倍。
     

3. 缓存效率：

   • LPRQ的L1未命中率与LCRQ无显著差异（见图9），说明三阶段CAS操作未增加缓存压力。
     

五、结论与价值

科学价值：
- 首次实现无需CAS2的高性能无锁队列，解决了LCRQ的移植性瓶颈。
- 提出线程令牌+epoch协同的同步范式，为其他并发数据结构设计提供新思路。

应用价值：
- 可直接集成至Java、Go等语言的标准库，提升高并发场景下的队列性能。
- 适用于低延迟系统（如金融交易、实时流处理）。

六、研究亮点

1. 算法创新：通过令牌机制模拟CAS2，避免硬件依赖，同时保持原子性。
   
2. 性能无损：LPRQ在保留LCRQ所有优点的前提下，兼容性更广。
   
3. 实验严谨性：多场景、多线程基准测试，覆盖生产-消费模型的典型负载。
   

七、其他贡献

• 开源实现：提供完整代码库与Docker化测试环境，支持复现实验。
  
• 理论证明：形式化验证了LPRQ的线性化（Linearizability）与无阻塞（Obstruction-Free）特性。
  

（报告总字数：约1800字）