{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/114094"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/114094","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Speeding-up graph processing on shared-memory platforms by optimizing scheduling and compute","abstract":"Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2023-12-01","abstract_html":"Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2023-12-01","abstract_has_math":false,"creators":["Heidarshenas, Azin"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Torrellas, Josep","Chen, Deming","Hwu, Wen-mei","Kumar, Rakesh","Misailovic, Sasa","Morrison, Adam"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2022,"date_issued":"2022-04-29T21:58:36Z","date_published":"2022-04-29T21:58:36Z","updated_at":"2026-07-22T22:24:54Z","subjects":["Engineering"],"languages":["en","eng"],"rights":["Copyright 2021 Azin Heidarshenas"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/114094","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Torrellas, Josep","Chen, Deming","Hwu, Wen-mei","Kumar, Rakesh","Misailovic, Sasa","Morrison, Adam"]},{"key":"dc:creator","label":"Author","values":["Heidarshenas, Azin"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2022-04-29T21:58:36Z","2024-04-29T21:58:46Z","2021-12","2021-12-02"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"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":["Engineering"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en","eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2021 Azin Heidarshenas"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/114094"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2023-12-01","The student, Azin Heidarshenas, accepted the attached license on 2021-12-01 at 14:42.","The student, Azin Heidarshenas, submitted this Dissertation for approval on 2021-12-01 at 15:02.","This Dissertation was approved for publication on 2021-12-02 at 15:20.","DSpace SAF Submission Ingestion Package generated from Vireo submission #17337 on 2022-04-29 at 16:10:18","Made available in DSpace on 2022-04-29T21:58:36Z (GMT). No. of bitstreams: 3 HEIDARSHENAS-DISSERTATION-2021.pdf: 3212586 bytes, checksum: 6a638d5593e66694a65f9c79a42e9744 (MD5) LICENSE.txt: 4214 bytes, checksum: 495fe180856cfd4d2a8f0cafc16b3f8c (MD5) PROQUEST_LICENSE.txt: 4560 bytes, checksum: bc34ec3f5e286621cc190f2aff207f83 (MD5) Previous issue date: 2021-12-02","Embargo set by: Seth Robbins for item 123459 Lift date: 2024-04-29T21:58:46Z Reason: Author requested closed access (OA after 2yrs) in Vireo ETD system","Author requested closed access (OA after 2yrs) in Vireo ETD system","Limited","Graph processing workloads are being widely used in many domains such as computational biology, social network analysis, and financial analysis. As DRAM technology scales down into higher densities, shared-memory platforms gain increasing importance in handling large graph sizes. We study two main categories of graph algorithms from an implementation perspective. Topology-driven algorithms process all vertices of the graph at each iteration, while data-driven algorithms only process those vertices that make a substantial contribution to the output. Furthermore, the performance of a graph algorithm execution can be broken down into three components, namely, pre-processing, compute, and scheduling. For data-driven algorithms, the work of each thread is driven by the dependencies between vertex values that are known only at run-time. Hence, the scheduling will take a significant portion of execution. However, for topology-driven algorithms, the scheduling time is negligible since the work of each thread can be determined at compile-time. In this dissertation, we present three techniques to address the performance bottlenecks in both data-driven and topology-driven algorithms. First, we present Snug, which is a chip-level architecture that mitigates the trade-off between synchronization and wasted work in data-driven algorithms. Second, we present V-Combiner, which is a software-only technique to mitigate the trade-off between performance and accuracy of topology-driven algorithms using novel vertex-merging and recovery mechanisms. Finally, we present KeepCompressed, which is a set of algorithms to speed-up compute for topology-driven algorithms using vertex clustering for dynamic graphs."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Speeding-up graph processing on shared-memory platforms by optimizing scheduling and compute"]}]}],"canonical_facts":{"dc:contributor":["Torrellas, Josep","Chen, Deming","Hwu, Wen-mei","Kumar, Rakesh","Misailovic, Sasa","Morrison, Adam"],"dc:creator":["Heidarshenas, Azin"],"dc:date":["2022-04-29T21:58:36Z","2024-04-29T21:58:46Z","2021-12","2021-12-02"],"dc:description":["Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2023-12-01","The student, Azin Heidarshenas, accepted the attached license on 2021-12-01 at 14:42.","The student, Azin Heidarshenas, submitted this Dissertation for approval on 2021-12-01 at 15:02.","This Dissertation was approved for publication on 2021-12-02 at 15:20.","DSpace SAF Submission Ingestion Package generated from Vireo submission #17337 on 2022-04-29 at 16:10:18","Made available in DSpace on 2022-04-29T21:58:36Z (GMT). No. of bitstreams: 3 HEIDARSHENAS-DISSERTATION-2021.pdf: 3212586 bytes, checksum: 6a638d5593e66694a65f9c79a42e9744 (MD5) LICENSE.txt: 4214 bytes, checksum: 495fe180856cfd4d2a8f0cafc16b3f8c (MD5) PROQUEST_LICENSE.txt: 4560 bytes, checksum: bc34ec3f5e286621cc190f2aff207f83 (MD5) Previous issue date: 2021-12-02","Embargo set by: Seth Robbins for item 123459 Lift date: 2024-04-29T21:58:46Z Reason: Author requested closed access (OA after 2yrs) in Vireo ETD system","Author requested closed access (OA after 2yrs) in Vireo ETD system","Limited","Graph processing workloads are being widely used in many domains such as computational biology, social network analysis, and financial analysis. As DRAM technology scales down into higher densities, shared-memory platforms gain increasing importance in handling large graph sizes. We study two main categories of graph algorithms from an implementation perspective. Topology-driven algorithms process all vertices of the graph at each iteration, while data-driven algorithms only process those vertices that make a substantial contribution to the output. Furthermore, the performance of a graph algorithm execution can be broken down into three components, namely, pre-processing, compute, and scheduling. For data-driven algorithms, the work of each thread is driven by the dependencies between vertex values that are known only at run-time. Hence, the scheduling will take a significant portion of execution. However, for topology-driven algorithms, the scheduling time is negligible since the work of each thread can be determined at compile-time. In this dissertation, we present three techniques to address the performance bottlenecks in both data-driven and topology-driven algorithms. First, we present Snug, which is a chip-level architecture that mitigates the trade-off between synchronization and wasted work in data-driven algorithms. Second, we present V-Combiner, which is a software-only technique to mitigate the trade-off between performance and accuracy of topology-driven algorithms using novel vertex-merging and recovery mechanisms. Finally, we present KeepCompressed, which is a set of algorithms to speed-up compute for topology-driven algorithms using vertex clustering for dynamic graphs."],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/114094"],"dc:language":["en","eng"],"dc:rights":["Copyright 2021 Azin Heidarshenas"],"dc:subject":["Engineering"],"dc:title":["Speeding-up graph processing on shared-memory platforms by optimizing scheduling and compute"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:54Z"}