Scalable Parallel Implementation of Bayesian Network to Junction Tree Conversion for Exact Inference

@inproceedings{citeulike:1379704, abstract = {We present a scalable parallel implementation for converting a Bayesian network to a junction tree, which can then be used for a complete parallel implementation for exact inference. We explore parallelism during the process of moralization, triangulation, clique identification, junction tree construction and potential table calculation. For an arbitrary Bayesian network with n vertices using p processors, the worst-case running time is shown to be O(n²w/p+-wr^wn/p+n log p), where w is the clique width and r is the number of states of the random variables. Our algorithm is scalable over 1 les p les nw/log n. We have implemented our parallel algorithm using OpenMP and experimented with up to 128 processors. We consider three types of Bayesian networks: linear, balanced and random. While the state of the art PNL library implementation does not scale, we achieve speedups of 31, 29 and 24 for the above graphs respectively on the DataStar cluster at San Diego Supercomputing Center}, author = {Namasivayam, Vasanth K. and Pathak, Animesh and Prasanna, Viktor K. }, citeulike-article-id = {1379704}, comment = {Related to the Junction Tree that we have.}, journal = {Computer Architecture and High Performance Computing, 2006. SBAC-PAD '06. 18TH International Symposium on}, keywords = {bayesian, exact, inference, junction, networks, trees}, pages = {167--176}, posted-at = {2007-06-12 05:42:05}, priority = {2}, title = {Scalable Parallel Implementation of Bayesian Network to Junction Tree Conversion for Exact Inference}, url = {http://ieeexplore.ieee.org/xpls/abs\_all.jsp?arnumber=4032429}, year = {2006} }

TY - CONF ID - citeulike:1379704 L3 - citeulike-article-id:1379704 TI - Scalable Parallel Implementation of Bayesian Network to Junction Tree Conversion for Exact Inference JF - Computer Architecture and High Performance Computing, 2006. SBAC-PAD '06. 18TH International Symposium on SP - 167 EP - 176 N2 - We present a scalable parallel implementation for converting a Bayesian network to a junction tree, which can then be used for a complete parallel implementation for exact inference. We explore parallelism during the process of moralization, triangulation, clique identification, junction tree construction and potential table calculation. For an arbitrary Bayesian network with n vertices using p processors, the worst-case running time is shown to be O(n²w/p+-wr^wn/p+n log p), where w is the clique width and r is the number of states of the random variables. Our algorithm is scalable over 1 les p les nw/log n. We have implemented our parallel algorithm using OpenMP and experimented with up to 128 processors. We consider three types of Bayesian networks: linear, balanced and random. While the state of the art PNL library implementation does not scale, we achieve speedups of 31, 29 and 24 for the above graphs respectively on the DataStar cluster at San Diego Supercomputing Center KW - bayesian KW - exact KW - inference KW - junction KW - networks KW - trees N1 - Related to the Junction Tree that we have. AU - Namasivayam, Vasanth AU - Pathak, Animesh AU - Prasanna, Viktor PY - 2006/// UR - http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4032429 ER -