2026-09-19T10:48:41Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/114094 2023-07-11 col_2142_5131 col_2142_8888 com_2142_5130 com_2142_8887 com_2142_234

Torrellas, Josep Torrellas, Josep Chen, Deming Hwu, Wen-mei Kumar, Rakesh Misailovic, Sasa Morrison, Adam 2022-04-29T21:58:36Z 2024-04-29T21:58:46Z 2021-12 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 application/pdf en text Speeding-up graph processing on shared-memory platforms by optimizing scheduling and compute Heidarshenas, Azin 2021-12-02 Engineering 2022-04-29T21:58:36Z 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. Thesis eng http://hdl.handle.net/2142/114094 Copyright 2021 Azin Heidarshenas Electrical & Computer Eng Electrical & Computer Engr University of Illinois at Urbana-Champaign Dissertation Ph.D.