Talk type: Talk

Designing fast lock-free algorithms by understanding cache coherence dynamics

  • Talk in English

The talk has several purposes:

  • Introducing MESI cache coherence;
  • Showing that lock-free algorithms aren't automatically faster than lock-based ones;
  • Explaining why this happens (due to cache coherence dynamics);
  • Introducing the idea of using non-failing atomic primitives instead of CAS as a way of speeding up lock-free algorithms.

The above goals are achieved by discussing the problem of designing a concurrent FIFO queue, starting from a simple lock-based algorithm, through a lock-free algorithm (that performs poorly), to the LCRQ algorithm, which is based on fetch-and-add (a non-failing primitive).

  • #cache-coherence
  • #concurrency
  • #lock-freedom
  • #scalability


Invited experts