February 17, 2023
Matthew Rodriguez will present "Solving Graph Problems Efficiently on Modern Hardware with a Relaxation-First Priority Queue". Free lunch and everyone welcome to attend.
Graphs are a flexible and powerful abstraction which are capable of representing many different problem spaces. Many different graph algorithms powered by priority queues have been developed to solve various problems. However, in the era of multi-core CPUs, strict priority queues have an unavoidable contention bottleneck on the head which seriously limits parallelism and therefore performance. This can be addressed through relaxation, a strategy by which a priority queue does not always return the absolute highest priority element. While this can cause work to be wasted through reprocessing of nodes, the gains that result from increased parallelism often more than make up for that. Furthermore, in many real-world workloads, the degree of key repetition is so high that an extreme degree of relaxation can be tolerated with almost no cost. Thus, we propose a design for a relaxed concurrent priority queue consisting of a linked list of vectors which utilize atomic integer operations for concurrent access. An index is maintained for fast insertion, and contention on the head is reduced by extracting an entire vector at once, and popping elements out of it one-by-one until it is empty. Teams of threads, organized by hardware considerations, share extracted chunks. We examine preliminary experimental results against the recent relaxed priority queue SprayList, and next steps for the project.
Further information
- Location: Tome 115
- Time: 12:30 pm - 1:30 pm
- Cost: Free