Does Better Throughput Require Worse Latency?, David Ungar
Channel: RACESWorkshop
Date: 01/05/2013

Paper and additional details are available at: http://soft.vub.ac.be/races/paper/does-better-throughput-require-worse-latency/

Paper Abstract:

As we continue to make the transition from uniprocessor to multicore programming, pushed along by the changing trajectory of hardware technology and system architecture, we are seeing an explosion of techniques for crossing the chasm between sequential and parallel data structures and algorithms. In considering a spectrum of techniques for moderating application access to shared data on multicore and manycore systems, we have observed that as application synchronization latency gets closer to hardware inter-core latency, throughput decreases. The spectrum of techniques we looked at includes: locks and mutexes, lock-free approaches based on atomic instructions, RCU, and (non-deterministic) race-and-repair. Below we present definitions of our notion of synchronization latency and throughput, and describe our observation in greater detail. We conclude by wondering whether there is a fundamental law relating latency to throughput:

Algorithms that improve application-level throughput worsen inter-core application-level latency.

We believe that such a law would be of great utility as a unification that would provide a common perspective from which to view and compare synchronization approaches.