SC Conference - Activity Details

Yinglong Xia  (University of Southern California)

Viktor K. Prasanna  (University of Southern California)

Applications: Models and Analysis

Thursday,  04:30PM - 05:00PM

Room Ballroom E

We present the design and implementation of a parallel exact inference algorithm on the Cell Broadband Engine (Cell BE). Exact inference is a key problem in exploring probabilistic graphical models. In such model, the computation complexity increases dramatically with the network structure and clique size. In this paper, we exploit parallelism at multiple levels. We present an efficient scheduler to dynamically partition large tasks and allocate synergistic processing elements (SPEs). We explore potential table representation and data layout to optimize DMA transfer between the local store and main memory. We also optimized the computation kernels. We achieved linear speedup and superior performance, compared with state-of-the-art processors such as AMD Opteron, Intel Xeon and Pentium 4. The methodology proposed in this paper can be used for online scheduling of directed acyclic graph (DAG) structured computations.

The full paper can be found in the IEEE Xplore Digital Library and ACM Digital Library