Snug: Architectural support for relaxed concurrent priority queueing in chip multiprocessors

Many parallel algorithms in domains such as graph analytics and simulations rely on priority-based task scheduling. In such environments, the data structure of choice is a concurrent priority queue (PQ). Unfortunately, PQ algorithms exhibit an undesirable tradeoff. On one hand, strict PQs always dequeue the highest-priority task, and thus fail to scale because of contention at the head of the queue. On the other hand, relaxed PQs avoid contention by dequeuing tasks that are sometimes so far from the head that the resulting schedule misses the benefit of priority-based scheduling. We propose a novel architecture for relaxing PQs without straying far from the priority-based schedule. Our chip-level architecture, called Snug, distributes the PQ into subqueues, and maintains a set of Work registers that point to the highest-priority task in each sub-queue. Snug provides an instruction that picks a high-quality task to execute. The instruction periodically switches between obtaining an accurate global snapshot, and visiting only local subqueues to reduce traffic. Overall, Snug dequeues high-quality tasks while avoiding both hotspots and excessive network traffic. We evaluate Snug on graph analytics and event simulation programs. On a simulated 64-core chip, Snug reduces the average execution time of the programs by 1.4X, 2.4X and 3.6X compared to state-of-the-art concurrent skip list, SprayList, and software-distributed PQs, respectively.