Scalable exact inference in probabilistic graphical models on multi-core platforms

The recent switch to multi-core computing and the emergence of machine learning applications have offered many opportunities for parallelization. However, achieving scalability with respect to the number of cores for these applications still remains a fundamental challenge, especially for machine learning problems that have graph computational structures.;This thesis explores parallelism for exact inference in probabilistic graphical models to achieve scalable performance on multi-core platforms. Exact inference is a key problem in probabilistic reasoning and machine learning. It also represents a large class of graph computations that have sophisticated computational patterns. In this thesis, we present our proposed techniques to extract and exploit parallelism efficiently at different levels. We first exploit parallelism available from the input graph using multithreading and task scheduling. At the node level, we explore data parallelism for the computational operations within a node. Data layout and data parallel algorithms are proposed for such node level computations. At the graph level, task parallelism is explored using a directed acyclic graph (DAG) model. DAG scheduling is employed to efficiently map the tasks in the DAG to the hardware cores. In many cases, the input graph provides insufficient parallelism. To expose more parallelism, we study a relationship called weak dependency between the tasks in a DAG. A novel DAG scheduling scheme is developed to exploit weak dependency for parallelism. In addition, pointer jumping technique is employed for exact inference when the input graph offers very limited parallelism due to its chain-like structure. Given fixed-size problems, the proposed techniques can still achieve high scalability with increasing number of cores. In order to avoid the implementation complexity of many parallel techniques, we study the use of MapReduce as a higher level programming model for exact inference. Our MapReduce-based techniques not only provide the ease of use but also achieve good performance for exact inference on general purpose multi-core systems. With the high level of abstraction, our techniques can be applied for a class of graph computations with data dependency.;We implement and evaluate our techniques on state-of-the-art multi-core systems, and demonstrate their high scalability for a variety of input graphs.