Events Calendar

Nam Ma (USC), PhD Defense

Committee:
Aiichiro Nakano
Viktor K. Prasanna (Chairman)
Cauligi S. Raghavendra

Title: Scalable Exact Inference in Probabilistic Graphical Models on Multi-core Platforms

Abstract:
The recent switch to multi-core computing and the emergence of machine learning applications offer many opportunities for parallelization. A fundamental challenge is how to achieve scalability with the increasing number of cores. It is especially challenging for machine learning problems that have graph computational structure.
This thesis explores parallelism for exact inference in probabilistic graphical models to achieve scalable performance on multi-core platforms. Exact inference is widely used in probabilistic reasoning and machine learning. It also represents a large class of graph computations that have sophisticated computational patterns with large data sets. We propose parallel techniques to extract and exploit parallelism efficiently at multiple levels in the input graph.
• 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 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. With such explorations, a given fixed-size problem can still achieve high scalability with the increasing number of cores.
• In order to avoid the implementation complexity of many parallel techniques, we study the use of MapReduce as a high level programming model for exact inference. Our MapReduce-based algorithms for exact inference can also 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 scalability for a variety of input graphs.

Location: Ronald Tutor Hall of Engineering (RTH) - 324

Audiences: Everyone Is Invited

Contact: Assistant to CS chair