Designing a High Throughput Bounded Multi-Producer, Multi-Consumer Queue

Abstract

Multi-Producer Multi-Consumer (MPMC) Queues are the most natural way to solve the common parallel programming Producer-Consumer Problem. The problem arises when a group of entities need work to be done, and another group of entities are responsible for doing said work. The problem is then of how should work be allocated to the workers such that neither group is hindered by the communication required for work allocation. MPMC Queues can solve the problem of allocation by functioning as a global location for work requests to be posted by the former group and later removed to be acted on by the latter group joining the two, but as the amount of work to be done by a system increases, this singular connection can easily become a bottleneck preventing work from being done. Current high performance MPMC Queue implementations strictly enforce that work posted first will be scheduled to a worker first, and while this improves the latency of a system, it can greatly decrease the overall work throughput, crippling bulk data-processing application performance. This project aims to create an MPMC Queue that is focused on overall throughput and investigate what performance optimizations can be made by sacrificing the standard latency guarantees.