caa a22 4500 445852461 CHVBK 20180317145417.0 cr unu---uuuuu 170323e20110801xx s 000 0 eng 10.1007/s11227-010-0415-1 doi (NATIONALLICENCE)springer-10.1007/s11227-010-0415-1 Parallel evidence propagation on multicore processors [Elektronische Daten] [Yinglong Xia, Viktor Prasanna] We propose a parallel evidence propagation method on general-purpose multicore processors. Evidence propagation is a major step in exact inference, a key problem in exploring probabilistic graphical models. We explore the parallelism in evidence propagation at various levels. First, given an arbitrary junction tree, we construct a directed acyclic graph (DAG) with weighted nodes, each denoting a computation task for evidence propagation. Since the execution time of the tasks varies significantly, we develop a workload-aware scheduler to allocate the tasks to the cores of the processors. The scheduler monitors the workload of each core and dynamically allocates tasks to support load balance across the cores. In addition, we integrate a module in the scheduler to partition the tasks converted from cliques with large potential tables so as to achieve improved load balance. We implemented the proposed method using Pthreads on both AMD and Intel quadcore processors. For a representative set of junction trees, our method achieved almost linear speedup. The execution time of our method was around twice as fast as an OpenMP-based implementation on both the platforms. Springer Science+Business Media, LLC, 2010 Exact inference nationallicence Multicore processor nationallicence Junction tree nationallicence Scheduling nationallicence DAG-structured computation nationallicence Xia Yinglong Computer Science Department, University of Southern California, 90089, Los Angeles, CA, USA aut Prasanna Viktor Ming Hsieh Department of Electrical Engineering, University of Southern California, 90089, Los Angeles, CA, USA aut The Journal of Supercomputing Springer US; http://www.springer-ny.com 57/2(2011-08-01), 189-202 0920-8542 57:2<189 2011 57 11227 https://doi.org/10.1007/s11227-010-0415-1 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s11227-010-0415-1 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Xia Yinglong Computer Science Department, University of Southern California, 90089, Los Angeles, CA, USA aut NATIONALLICENCE 700 1- Prasanna Viktor Ming Hsieh Department of Electrical Engineering, University of Southern California, 90089, Los Angeles, CA, USA aut NATIONALLICENCE 773 0- The Journal of Supercomputing Springer US; http://www.springer-ny.com 57/2(2011-08-01), 189-202 0920-8542 57:2<189 2011 57 11227 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer