{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/97627"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/97627","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Architectural support for work-efficient relaxed priority queueing","abstract":"Limited Restriction set for Item 102680 on 2019-04-29T15:20:14Z with date 2020-08-10 by fschaef2@illinois.edu.","abstract_html":"Limited Restriction set for Item 102680 on 2019-04-29T15:20:14Z with date 2020-08-10 by fschaef2@illinois.edu.","abstract_has_math":false,"creators":["Heidarshenas, Azin"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Torrellas, Josep"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2017,"date_issued":"2017-08-10T19:52:22Z","date_published":"2017-08-10T19:52:22Z","updated_at":"2026-07-22T22:24:34Z","subjects":["Priority queues","Concurrency","Scheduling"],"languages":["en"],"rights":["Copyright 2017 Azin Heidarshenas"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/97627","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Torrellas, Josep"]},{"key":"dc:creator","label":"Author","values":["Heidarshenas, Azin"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2017-08-10T19:52:22Z","2020-08-10T09:15:09Z","2017-04-26","2017-05"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Priority queues","Concurrency","Scheduling"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2017 Azin Heidarshenas"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/97627"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Limited Restriction set for Item 102680 on 2019-04-29T15:20:14Z with date 2020-08-10 by fschaef2@illinois.edu.","Limited Restriction set for Item 102680 on 2019-04-29T15:20:29Z with date 2020-08-10 by fschaef2@illinois.edu.","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.","Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2019-05-01","The student, Azin Heidarshenas, accepted the attached license on 2017-04-25 at 14:25.","The student, Azin Heidarshenas, submitted this Thesis for approval on 2017-04-25 at 14:26.","This Thesis was approved for publication on 2017-04-26 at 09:10.","DSpace SAF Submission Ingestion Package generated from Vireo submission #11021 on 2017-08-10 at 14:32:33","Made available in DSpace on 2017-08-10T19:52:22Z (GMT). No. of bitstreams: 2 HEIDARSHENAS-THESIS-2017.pdf: 760946 bytes, checksum: 812461abc69e6470e20e176c03e27ef3 (MD5) LICENSE.txt: 4214 bytes, checksum: 4e5d3a69289d94ed974426c0a5808e16 (MD5) Previous issue date: 2017-04-26","Embargo set by: Colleen Fallaw for item 102680 Lift date: 2019-08-10T21:25:30Z Reason: Author requested closed access (OA after 2yrs) in Vireo ETD system","Limited Restriction set for Item 102680 on 2019-04-29T15:20:40Z with date 2020-08-10 by fschaef2@illinois.edu.","Limited Restriction set for Item 102680 on 2019-04-29T15:20:43Z with date 2020-08-10 by fschaef2@illinois.edu.","Limited Restriction set for Item 102680 on 2019-04-29T15:20:46Z with date 2020-08-10 by fschaef2@illinois.edu.","Limited Restriction Lifted for Item 102680 on 2020-08-10T09:15:09Z."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Architectural support for work-efficient relaxed priority queueing"]}]}],"canonical_facts":{"dc:contributor":["Torrellas, Josep"],"dc:creator":["Heidarshenas, Azin"],"dc:date":["2017-08-10T19:52:22Z","2020-08-10T09:15:09Z","2017-04-26","2017-05"],"dc:description":["Limited Restriction set for Item 102680 on 2019-04-29T15:20:14Z with date 2020-08-10 by fschaef2@illinois.edu.","Limited Restriction set for Item 102680 on 2019-04-29T15:20:29Z with date 2020-08-10 by fschaef2@illinois.edu.","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.","Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2019-05-01","The student, Azin Heidarshenas, accepted the attached license on 2017-04-25 at 14:25.","The student, Azin Heidarshenas, submitted this Thesis for approval on 2017-04-25 at 14:26.","This Thesis was approved for publication on 2017-04-26 at 09:10.","DSpace SAF Submission Ingestion Package generated from Vireo submission #11021 on 2017-08-10 at 14:32:33","Made available in DSpace on 2017-08-10T19:52:22Z (GMT). No. of bitstreams: 2 HEIDARSHENAS-THESIS-2017.pdf: 760946 bytes, checksum: 812461abc69e6470e20e176c03e27ef3 (MD5) LICENSE.txt: 4214 bytes, checksum: 4e5d3a69289d94ed974426c0a5808e16 (MD5) Previous issue date: 2017-04-26","Embargo set by: Colleen Fallaw for item 102680 Lift date: 2019-08-10T21:25:30Z Reason: Author requested closed access (OA after 2yrs) in Vireo ETD system","Limited Restriction set for Item 102680 on 2019-04-29T15:20:40Z with date 2020-08-10 by fschaef2@illinois.edu.","Limited Restriction set for Item 102680 on 2019-04-29T15:20:43Z with date 2020-08-10 by fschaef2@illinois.edu.","Limited Restriction set for Item 102680 on 2019-04-29T15:20:46Z with date 2020-08-10 by fschaef2@illinois.edu.","Limited Restriction Lifted for Item 102680 on 2020-08-10T09:15:09Z."],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/97627"],"dc:language":["en"],"dc:rights":["Copyright 2017 Azin Heidarshenas"],"dc:subject":["Priority queues","Concurrency","Scheduling"],"dc:title":["Architectural support for work-efficient relaxed priority queueing"],"dc:type":["text"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:34Z"}