{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/115730"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/115730","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Processing graphs and sparse matrices efficiently","abstract":"Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2024-05-01","abstract_html":"Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2024-05-01","abstract_has_math":false,"creators":["Yesil, Serif"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Padua, David","Hwu, Wen-mei","Torrellas, Josep","Mendis, Charith","Morrison, Adam","Moreira, Jose E."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2022,"date_issued":"2022-05","date_published":"2022-05","updated_at":"2026-07-22T22:24:55Z","subjects":["Graph Analytics","Priority Scheduling","Sparse Matrix Primitives","Sparse Matrix-Vector Multiplications","Sparse Matrix-Matrix Multiplications"],"languages":["en","eng"],"rights":["Copyright 2022 Serif Yesil"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/115730","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Padua, David","Hwu, Wen-mei","Torrellas, Josep","Mendis, Charith","Morrison, Adam","Moreira, Jose E."]},{"key":"dc:creator","label":"Author","values":["Yesil, Serif"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2022-05","2022-04-20"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"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":["Graph Analytics","Priority Scheduling","Sparse Matrix Primitives","Sparse Matrix-Vector Multiplications","Sparse Matrix-Matrix Multiplications"]}]},{"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 2022 Serif Yesil"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/115730"]}]},{"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 2024-05-01","The student, Serif Yesil, accepted the attached license on 2022-04-19 at 18:28.","The student, Serif Yesil, submitted this Dissertation for approval on 2022-04-19 at 18:42.","This Dissertation was approved for publication on 2022-04-20 at 09:12.","DSpace SAF Submission Ingestion Package generated from Vireo submission #17818 on 2022-11-11 at 12:47:31","Graph analytics applications are hard to optimize. Their performance is highly dependent on their input graph, which can vary significantly. One effective approach to solve graph analytics applications is to represent the input graph as a sparse matrix, and use the operators of sparse linear algebra. There are numerous methods developed to accelerate the resulting sparse matrix computations. Unfortunately, no single method can outperform all others for all types of matrices. In order to obtain high performance on a wide range of matrices, we need to be able to determine the best method to use for each individual matrix. In this work, we target automated optimization of graph applications. First, we consider the data-driven graph algorithms with priority scheduling. We perform a detailed performance analysis of various priority schedulers and observe that the performance is application and input graph-dependent. Based on our insights, we develop the Priority Merging on Demand (PMOD) priority scheduler, a dynamic mechanism that can adapt to graph and application characteristics at runtime. Next, we focus on topology-driven graph analytics, where all vertices of a graph are processed in every iteration. These applications can be represented as generalized Sparse Matrix-Vector multiplication (SpMV) operations. However, SpMV style computations are challenging with emerging power-law graphs due to their skewed and highly irregular memory behavior. To address these challenges, we propose Locality-Aware Vectorization (LAV), which can improve the locality and efficiency of vectorization for power-law graph analytics. Furthermore, we identify that the optimizations applied in LAV form an optimization search space encompassing many different SpMV methods. Moreover, various combinations of these optimizations can yield the best performance for matrices and graphs from different application domains. For this reason, we develop Matrix-Vector Performance Predictor (MVPP): a machine learning-based performance prediction model for SpMV predicting the best strategy for individual matrices. Finally, we note that many applications can benefit from increasing compute intensity provided by Sparse-Matrix Matrix Multiplication (SpMM). In our final work, we develop Dense Dynamic Blocks (DDB), a hybrid approach to accelerate SpMM by utilizing both vector and emerging matrix units in recent processors. However, like SpMV, we observe that not all matrices benefit from DDB, and the best SpMM method should be selected on a per-matrix basis. Hence, we develop SpMM Optimizer (SpMM-OPT), a machine learning approach to select the best SpMM strategy in functional unit-rich processors."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Processing graphs and sparse matrices efficiently"]}]}],"canonical_facts":{"dc:contributor":["Padua, David","Hwu, Wen-mei","Torrellas, Josep","Mendis, Charith","Morrison, Adam","Moreira, Jose E."],"dc:creator":["Yesil, Serif"],"dc:date":["2022-05","2022-04-20"],"dc:description":["Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2024-05-01","The student, Serif Yesil, accepted the attached license on 2022-04-19 at 18:28.","The student, Serif Yesil, submitted this Dissertation for approval on 2022-04-19 at 18:42.","This Dissertation was approved for publication on 2022-04-20 at 09:12.","DSpace SAF Submission Ingestion Package generated from Vireo submission #17818 on 2022-11-11 at 12:47:31","Graph analytics applications are hard to optimize. Their performance is highly dependent on their input graph, which can vary significantly. One effective approach to solve graph analytics applications is to represent the input graph as a sparse matrix, and use the operators of sparse linear algebra. There are numerous methods developed to accelerate the resulting sparse matrix computations. Unfortunately, no single method can outperform all others for all types of matrices. In order to obtain high performance on a wide range of matrices, we need to be able to determine the best method to use for each individual matrix. In this work, we target automated optimization of graph applications. First, we consider the data-driven graph algorithms with priority scheduling. We perform a detailed performance analysis of various priority schedulers and observe that the performance is application and input graph-dependent. Based on our insights, we develop the Priority Merging on Demand (PMOD) priority scheduler, a dynamic mechanism that can adapt to graph and application characteristics at runtime. Next, we focus on topology-driven graph analytics, where all vertices of a graph are processed in every iteration. These applications can be represented as generalized Sparse Matrix-Vector multiplication (SpMV) operations. However, SpMV style computations are challenging with emerging power-law graphs due to their skewed and highly irregular memory behavior. To address these challenges, we propose Locality-Aware Vectorization (LAV), which can improve the locality and efficiency of vectorization for power-law graph analytics. Furthermore, we identify that the optimizations applied in LAV form an optimization search space encompassing many different SpMV methods. Moreover, various combinations of these optimizations can yield the best performance for matrices and graphs from different application domains. For this reason, we develop Matrix-Vector Performance Predictor (MVPP): a machine learning-based performance prediction model for SpMV predicting the best strategy for individual matrices. Finally, we note that many applications can benefit from increasing compute intensity provided by Sparse-Matrix Matrix Multiplication (SpMM). In our final work, we develop Dense Dynamic Blocks (DDB), a hybrid approach to accelerate SpMM by utilizing both vector and emerging matrix units in recent processors. However, like SpMV, we observe that not all matrices benefit from DDB, and the best SpMM method should be selected on a per-matrix basis. Hence, we develop SpMM Optimizer (SpMM-OPT), a machine learning approach to select the best SpMM strategy in functional unit-rich processors."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/115730"],"dc:language":["en","eng"],"dc:rights":["Copyright 2022 Serif Yesil"],"dc:subject":["Graph Analytics","Priority Scheduling","Sparse Matrix Primitives","Sparse Matrix-Vector Multiplications","Sparse Matrix-Matrix Multiplications"],"dc:title":["Processing graphs and sparse matrices efficiently"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:55Z"}