Time-Stamp with Window Decoupled: A Fast and Practical Lock-Free Relaxed Queue

엄격한 FIFO Lock-Free Queue의 한계를 극복하기 위해, FIFO 제약을 완화하고 병렬성을 향상시키는 방법으로 Relaxed Queue가 활발히 연구되어 왔다. 본 연구에서는 타임스탬핑 알고리즘과 Window Decoupled 구조를 통합한 새로운 Relaxed Queue인, Time-Stamped Window Decoupled Queue를 제안한다. 실험 결과, 제안한 Relaxed Queue는 모든 마이크로/매크로벤치마크에서 기존 Relaxed Queue보다 뛰어난 성능을 보였다. 특히, 마이크로벤치마크에서 Enqueue Rate가 증가할수록 다른 Relaxed Queue를 압도적으로 능가하는 성능을 달성하였다. 또한 스레드 72개로 수행하는 마이크로 벤치마크에서, 제안한 Relaxed Queue는 d-Choice Balanced Operations Queue보다 60.67% 높은 Throughput을 보였다.