March 30, 2007
Conference Paper

Probability Convergence in a Multithreaded Counting Application

Abstract

We introduce the PDtree, a data structure for fast counting of any specified combinations of a given set of variables. We describe a static implementation that provides speedup linear in the number of processors on the multithreaded Cray MTA-2 machine. Finally, we prove a general convergence property that bounds the nondeterministic deviation of probability estimates relative to a sequential implementation. This convergence result is relevant for any counting application that takes a multithreaded streaming approach.

Revised: July 13, 2007 | Published: March 30, 2007

Citation

Scherrer C., N. Beagley, J. Nieplocha, A. Marquez, J. Feo, and D. Chavarría-Miranda. 2007. Probability Convergence in a Multithreaded Counting Application. In Parallel and Distributed Processing Symposium (IPDPS 2007), 1-5. Piscataway, New York:IEEE. PNNL-SA-53295. doi:10.1109/IPDPS.2007.370688