research-article

Parallel exact inference on the cell broadband engine processor

Authors:

Viktor K. PrasannaAuthors Info & Claims

SC '08: Proceedings of the 2008 ACM/IEEE conference on Supercomputing

Article No.: 58, Pages 1 - 12

Published: 15 November 2008 Publication History

Abstract

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 a 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 the 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.

References

[1]

S. L. Lauritzen and D. J. Spiegelhalter, "Local computation with probabilities and graphical structures and their application to expert systems," J. Royal Statistical Society B, vol. 50, pp. 157--224, 1988.

[2]

D. Heckerman, "Bayesian networks for data mining," in In Data Mining and Knowledge Discovery, 1997.

Digital Library

[3]

S. J. Russell and P. Norvig, Artificial Intelligence: A Modern Approach (2nd Edition). Prentice Hall, 2002.

Digital Library

[4]

E. Segal, B. Taskar, A. Gasch, N. Friedman, and D. Koller, "Rich probabilistic models for gene expression," in 9th International Conference on Intelligent Systems for Molecular Biology, 2001, pp. 243--252.

[5]

D. Pennock, "Logarithmic time parallel Bayesian inference," in Proceedings of the 14th Annual Conference on Uncertainty in Artificial Intelligence, 1998, pp. 431--438.

Digital Library

[6]

A. V. Kozlov and J. P. Singh, "A parallel Lauritzen-Spiegelhalter algorithm for probabilistic inference," in Supercomputing, 1994, pp. 320--329.

Digital Library

[7]

Y. Xia and V. K. Prasanna, "Node level primitives for parallel exact inference," in Proceedings of the 19th International Symposium on Computer Architecture and High Performance Computing, 2007, pp. 221--228.

[8]

Y. Xia and V. K. Prasanna, "Parallel exact inference," in Parallel Computing: Architectures, Algorithms and Applications, vol. 38, 2007, pp. 185--192.

[9]

D. Bader and V. Agarwal, "FFTC: Fastest Fourier Transform for the IBM Cell Broadband Engine," in The 14th Annual IEEE International Conference on High Performance Computing, 2007, pp. 172--184.

Digital Library

[10]

S. Williams, J. Shalf, L. Oliker, S. Kamil, P. Husbands, and K. Yelick, "The potential of the Cell processor for scientific computing," in Proceedings of the 3rd ACM Conference on Computing Frontiers, 2006, pp. 9--20.

Digital Library

[11]

"IBM Cell BE programming tutorial." {Online}. Available: http://www.ibm.com/developer/power/cell

[12]

D. Bader, V. Agarwal, K. Madduri, and S. Kang, "High performance combinatorial algorithm design on the Cell Broadband Engine processor," Parallel Computing, vol. 33, pp. 720--740, 2007.

Digital Library

[13]

F. Petrini, O. Villa, and D. Scarpazza, "Efficient breadth-first search on the Cell BE processor," IEEE Transactions on Parallel and Distributed Systems, 2007.

[14]

R. D. Shachter, S. K. Andersen, and P. Szolovits, "Global conditioning for probabilistic inference in belief networks," in Proceedings of the Tenth Conference on Uncertainty in Articial Intelligence, 1994, pp. 514--522.

[15]

G. Buehrer and S. Parthasarathy, "The potential of the Cell Broadband Engine for data mining," Department of Computer Science and Engineering, Ohio State University, Tech. Rep. TR-2007-22, 2007.

[16]

J. JáJá, An Introduction to Parallel Algorithms. Reading, MA: USA: Addison-Wesley, 1992.

Digital Library

[17]

P. Bellens, J. Perez, R. Badia, and J. Labarta, "CellSs: a programming model for the cell be architecture," in Proceedings of the ACM/IEEE Supercomputing 2006 Conference, 2006, pp. 5--5.

Digital Library

[18]

M. Iverson and F. Ozguner, "Dynamic, competitive scheduling of multiple DAGs in a distributed heterogeneous environment," in HCW '98: Proceedings of the Seventh Heterogeneous Computing Workshop, 1998, p. 70.

Digital Library

[19]

M. Linklater, "Optimizing Cell core," Game Developer Magazine, pp. 15--18, 2007.

[20]

"Intel Open Source Probabilistic Networks Library." {Online}. Available: http://www.intel.com/technology/computing/pnl/

[21]

V. K. Namasivayam and V. K. Prasanna, "Scalable parallel implementation of exact inference in Bayesian networks," in Proceedings of the 12th International Conference on Parallel and Distributed Systems, 2006, pp. 143--150.

Digital Library

[22]

K. Murphy, "Bayes net toolbox." {Online}. Available: http://www.cs.ubc.ca/~murphyk/Software/BNT/bnt.html

[23]

V. Teulire and O. Brun, "Parallelisation of the particle filtering technique and application to doppler-bearing tracking of maneuvering sources," Parallel Computing, vol. 29, no. 8, pp. 1069--1090, 2003.

Digital Library

[24]

J. Corander, M. Gyllenberg, and T. Koski, "Bayesian model learning based on a parallel MCMC strategy," Statistics and Computing, vol. 16, no. 4, pp. 355--362, 2006.

Digital Library

Cited By

Stefanovitch NFarinelli ARogers AJennings NSonenberg LStone PTumer KYolum P(2011)Resource-aware junction trees for efficient multi-agent coordinationThe 10th International Conference on Autonomous Agents and Multiagent Systems - Volume 110.5555/2030470.2030524(363-370)Online publication date: 2-May-2011
https://dl.acm.org/doi/10.5555/2030470.2030524
Su MThompson E(2011)Parallelizing a convergent approximate inference methodProceedings of the 24th Canadian conference on Advances in artificial intelligence10.5555/2018192.2018239(390-395)Online publication date: 25-May-2011
https://dl.acm.org/doi/10.5555/2018192.2018239
Yalamanchili PMohan SJalasutram RTaha T(2010)Acceleration of hierarchical Bayesian network based cortical models on multicore architecturesParallel Computing10.1016/j.parco.2010.04.00136:8(449-468)Online publication date: 1-Aug-2010
https://dl.acm.org/doi/10.1016/j.parco.2010.04.001
Show More Cited By

Index Terms

Parallel exact inference on the cell broadband engine processor

Recommendations

Accelerating computing with the cell broadband engine processor
CF '08: Proceedings of the 5th conference on Computing frontiers

In this paper, we describe our approach to utilizing the compute power of the Cell Broadband Engine™ (Cell/B.E.)¹ processor as an accelerator for computationally intensive portions of high performance computing applications. We call this approach "...
Computing discrete transforms on the Cell Broadband Engine

Discrete transforms are of primary importance and fundamental kernels in many computationally intensive scientific applications. In this paper, we investigate the performance of two such algorithms; Fast Fourier Transform (FFT) and Discrete Wavelet ...
Parallel exact inference on the Cell Broadband Engine processor

We present the design and implementation of a parallel exact inference algorithm on the Cell Broadband Engine (Cell BE) processor, a heterogeneous multicore architecture. Exact inference is a key problem in exploring probabilistic graphical models, where ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SC '08: Proceedings of the 2008 ACM/IEEE conference on Supercomputing

November 2008

739 pages

ISBN:9781424428359

Conference Chair:
Patricia Teller

Sponsors

SIGARCH: ACM Special Interest Group on Computer Architecture
IEEE-CS: Computer Society

Publisher

IEEE Press

Publication History

Published: 15 November 2008

Check for updates

Qualifiers

Research-article

Funding Sources

Division of Computer and Network Systems

Conference

SC '08

Sponsor:

SIGARCH
IEEE-CS

SC '08: International Conference for High Performance Computing, Networking, Storage and Analysis

November 15 - 21, 2008

Texas, Austin

Acceptance Rates

SC '08 Paper Acceptance Rate 59 of 277 submissions, 21%;

Overall Acceptance Rate 1,516 of 6,373 submissions, 24%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
255
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Stefanovitch NFarinelli ARogers AJennings NSonenberg LStone PTumer KYolum P(2011)Resource-aware junction trees for efficient multi-agent coordinationThe 10th International Conference on Autonomous Agents and Multiagent Systems - Volume 110.5555/2030470.2030524(363-370)Online publication date: 2-May-2011
https://dl.acm.org/doi/10.5555/2030470.2030524
Su MThompson E(2011)Parallelizing a convergent approximate inference methodProceedings of the 24th Canadian conference on Advances in artificial intelligence10.5555/2018192.2018239(390-395)Online publication date: 25-May-2011
https://dl.acm.org/doi/10.5555/2018192.2018239
Yalamanchili PMohan SJalasutram RTaha T(2010)Acceleration of hierarchical Bayesian network based cortical models on multicore architecturesParallel Computing10.1016/j.parco.2010.04.00136:8(449-468)Online publication date: 1-Aug-2010
https://dl.acm.org/doi/10.1016/j.parco.2010.04.001
Xia YPrasanna V(2010)Parallel exact inference on the Cell Broadband Engine processorJournal of Parallel and Distributed Computing10.1016/j.jpdc.2010.01.00870:5(558-572)Online publication date: 1-May-2010
https://dl.acm.org/doi/10.1016/j.jpdc.2010.01.008
Xia YFeng XPrasanna V(2009)Parallel Evidence Propagation on Multicore ProcessorsProceedings of the 10th International Conference on Parallel Computing Technologies10.1007/978-3-642-03275-2_37(377-391)Online publication date: 3-Sep-2009
https://dl.acm.org/doi/10.1007/978-3-642-03275-2_37

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents