CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

The lock-free k-LSM relaxed priority queue

M. Wimmer ; J. Gruber ; J. L. Träff ; Philippas Tsigas (Institutionen för data- och informationsteknik, Nätverk och system (Chalmers) )
ACM Sigplan Notices (0362-1340). Vol. 50 (2015), 8, p. 277-278.
[Konferensbidrag, refereegranskat]

We present a new, concurrent, lock-free priority queue that relaxes the delete-min operation to allow deletion of any of the ρ+1 smallest keys instead of only a minimal one, where ρ is a parameter that can be configured at runtime. It is built from a logarithmic number of sorted arrays, similar to log-structured merge-trees (LSM). For keys added and removed by the same thread the behavior is identical to a non-relaxed priority queue. We compare to state-of-the-art lock-free priority queues with both relaxed and non-relaxed semantics, showing high performance and good scalability of our approach.

Nyckelord: Concurrent data structure relaxation, Priority-queue, Shared memory, Task-parallel programming

Denna post skapades 2015-09-17. Senast ändrad 2016-09-22.
CPL Pubid: 222631


Läs direkt!

Länk till annan sajt (kan kräva inloggning)