{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/108728"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/108728","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Massively parallel message passing on a GPU for graphical model inference","abstract":"Graphical model inference is fundamental to many problems across disciplines. However, its combinatorial nature makes it computationally challenging. For more effective inference, message passing algorithms that expose significant parallelism have been implemented to exploit graphics processing units (GPUs), albeit often tackling specific graphical model structures such as directed acyclic graphs (DAGs), grids, uniform state spaces, and pairwise models. All those implementations emphasize the importance of load balancing irregular graphs in order to fully utilize GPU parallelism. However, they do not formalize the problems and instead give ad hoc solutions. In contrast, we formalize load balancing of message passing for general, irregular graphs as a minimax problem and develop an algorithm to solve it efficiently. We show that our implementation permits scaling of message passing to meet the demands of current problems of interest in machine learning and computer vision, achieving significant speedups over state of the art.","abstract_html":"Graphical model inference is fundamental to many problems across disciplines. However, its combinatorial nature makes it computationally challenging. For more effective inference, message passing algorithms that expose significant parallelism have been implemented to exploit graphics processing units (GPUs), albeit often tackling specific graphical model structures such as directed acyclic graphs (DAGs), grids, uniform state spaces, and pairwise models. All those implementations emphasize the importance of load balancing irregular graphs in order to fully utilize GPU parallelism. However, they do not formalize the problems and instead give ad hoc solutions. In contrast, we formalize load balancing of message passing for general, irregular graphs as a minimax problem and develop an algorithm to solve it efficiently. We show that our implementation permits scaling of message passing to meet the demands of current problems of interest in machine learning and computer vision, achieving significant speedups over state of the art.","abstract_has_math":false,"creators":["Martini, Amr Mamoun"],"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":["Schwing, Alex G"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2020,"date_issued":"2020-10-07T22:50:07Z","date_published":"2020-10-07T22:50:07Z","updated_at":"2026-07-22T22:24:48Z","subjects":["graphical models","GPU","statistical inference","computational inference","coordinate descent"],"languages":["en"],"rights":["Copyright 2020 Amr Martini"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/108728","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Schwing, Alex G"]},{"key":"dc:creator","label":"Author","values":["Martini, Amr Mamoun"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2020-10-07T22:50:07Z","2022-10-07T22:50:13Z","2020-07-22","2020-08"]},{"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":["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":["graphical models","GPU","statistical inference","computational inference","coordinate descent"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2020 Amr Martini"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/108728"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Graphical model inference is fundamental to many problems across disciplines. However, its combinatorial nature makes it computationally challenging. For more effective inference, message passing algorithms that expose significant parallelism have been implemented to exploit graphics processing units (GPUs), albeit often tackling specific graphical model structures such as directed acyclic graphs (DAGs), grids, uniform state spaces, and pairwise models. All those implementations emphasize the importance of load balancing irregular graphs in order to fully utilize GPU parallelism. However, they do not formalize the problems and instead give ad hoc solutions. In contrast, we formalize load balancing of message passing for general, irregular graphs as a minimax problem and develop an algorithm to solve it efficiently. We show that our implementation permits scaling of message passing to meet the demands of current problems of interest in machine learning and computer vision, achieving significant speedups over state of the art.","Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2022-08-01","The student, Amr Martini, accepted the attached license on 2020-07-22 at 10:29.","The student, Amr Martini, submitted this Thesis for approval on 2020-07-22 at 10:37.","This Thesis was approved for publication on 2020-07-22 at 15:56.","DSpace SAF Submission Ingestion Package generated from Vireo submission #15721 on 2020-10-02 at 15:52:14","Made available in DSpace on 2020-10-07T22:50:07Z (GMT). No. of bitstreams: 3 MARTINI-THESIS-2020.pdf: 2732495 bytes, checksum: b9ed7d79b40041319839bbbdcaa1a295 (MD5) THESIS.zip: 4532000 bytes, checksum: d121c33952dbe0754da8977c4b19151c (MD5) LICENSE.txt: 4208 bytes, checksum: e22b744f4d56d54971421e9ec2c54ce3 (MD5) Previous issue date: 2020-07-22","Embargo set by: Seth Robbins for item 116357 Lift date: 2022-10-07T22:50:13Z Reason: Author requested closed access (OA after 2yrs) in Vireo ETD system","Author requested closed access (OA after 2yrs) in Vireo ETD system","Limited"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Massively parallel message passing on a GPU for graphical model inference"]}]}],"canonical_facts":{"dc:contributor":["Schwing, Alex G"],"dc:creator":["Martini, Amr Mamoun"],"dc:date":["2020-10-07T22:50:07Z","2022-10-07T22:50:13Z","2020-07-22","2020-08"],"dc:description":["Graphical model inference is fundamental to many problems across disciplines. However, its combinatorial nature makes it computationally challenging. For more effective inference, message passing algorithms that expose significant parallelism have been implemented to exploit graphics processing units (GPUs), albeit often tackling specific graphical model structures such as directed acyclic graphs (DAGs), grids, uniform state spaces, and pairwise models. All those implementations emphasize the importance of load balancing irregular graphs in order to fully utilize GPU parallelism. However, they do not formalize the problems and instead give ad hoc solutions. In contrast, we formalize load balancing of message passing for general, irregular graphs as a minimax problem and develop an algorithm to solve it efficiently. We show that our implementation permits scaling of message passing to meet the demands of current problems of interest in machine learning and computer vision, achieving significant speedups over state of the art.","Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2022-08-01","The student, Amr Martini, accepted the attached license on 2020-07-22 at 10:29.","The student, Amr Martini, submitted this Thesis for approval on 2020-07-22 at 10:37.","This Thesis was approved for publication on 2020-07-22 at 15:56.","DSpace SAF Submission Ingestion Package generated from Vireo submission #15721 on 2020-10-02 at 15:52:14","Made available in DSpace on 2020-10-07T22:50:07Z (GMT). No. of bitstreams: 3 MARTINI-THESIS-2020.pdf: 2732495 bytes, checksum: b9ed7d79b40041319839bbbdcaa1a295 (MD5) THESIS.zip: 4532000 bytes, checksum: d121c33952dbe0754da8977c4b19151c (MD5) LICENSE.txt: 4208 bytes, checksum: e22b744f4d56d54971421e9ec2c54ce3 (MD5) Previous issue date: 2020-07-22","Embargo set by: Seth Robbins for item 116357 Lift date: 2022-10-07T22:50:13Z Reason: Author requested closed access (OA after 2yrs) in Vireo ETD system","Author requested closed access (OA after 2yrs) in Vireo ETD system","Limited"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/108728"],"dc:language":["en"],"dc:rights":["Copyright 2020 Amr Martini"],"dc:subject":["graphical models","GPU","statistical inference","computational inference","coordinate descent"],"dc:title":["Massively parallel message passing on a GPU for graphical model inference"],"dc:type":["text","Thesis"],"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:48Z"}