Massively parallel message passing on a GPU for graphical model inference

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.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Electrical & Computer Engr

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2020

Author dc:creator

• Martini, Amr Mamoun

Contributors dc:contributor

• Schwing, Alex G

• graphical models
• GPU
• statistical inference
• computational inference
• coordinate descent

Statement dc:rights

• Copyright 2020 Amr Martini

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/108728

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/108728