Architectural support for work-efficient relaxed priority queueing
Heidarshenas, Azin
Loading…
Permalink
https://hdl.handle.net/2142/97627
Description
Title
Architectural support for work-efficient relaxed priority queueing
Author(s)
Heidarshenas, Azin
Issue Date
2017-04-26
Director of Research (if dissertation) or Advisor (if thesis)
Torrellas, Josep
Department of Study
Electrical & Computer Eng
Discipline
Electrical & Computer Engr
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
M.S.
Degree Level
Thesis
Keyword(s)
Priority queues
Concurrency
Scheduling
Abstract
Many parallel algorithms in domains such as graph analytics and simulations execute more efficiently if some parallel tasks are executed before others. To implement such priority-based task scheduling, the data structure of choice is a concurrent priority queue (PQ). Unfortunately, PQ algorithms exhibit an undesirable tradeoff. On one hand, traditional 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 often so far from the head that the resulting schedule misses the benefit of priority-based scheduling.
This thesis proposes novel architectural support for relaxing PQs without straying far from the priority-based schedule. Our architecture, called Snug, distributes the PQ and maintains a set of Work Registers that point to the highest-priority task in each subqueue. Snug provides an instruction that picks a high-quality task to execute. The instruction periodically switches between visiting all the subqueues to get an accurate global snapshot and visiting nearby subqueues to reduce traffic. Overall, Snug dequeues highquality tasks while simultaneously avoiding hotspots and excessive network traffic. We evaluate Snug on graph analytics and event simulation applications. Snug reduces the average execution time of the applications by 1.6×, 4.9× and 3.4× compared to the state-of-the-art skip list, SprayList, and software-distributed PQs, respectively.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
