Answers are grounded in this paper and cite their sources.
We describe a simd technique for drawing values from multiple discrete distributions, such as sampling from the random variables of a mixture model, that avoids computing a complete table of partial sums of the relative probabilities. A table of alternate (“butterfly-patterned”) form is faster to compute, making better use of coalesced memory accesses; from this table, complete partial sums are computed on the fly during a binary search. Measurements using cuda 7.5 on an nvidia Titan Black gpu show that this technique makes an entire machine-learning application that uses a Latent Dirichlet Allocation topic model with 1,024 topics about 13% faster (when using single-precision floating-point data) or about 35% faster (when using double-precision floating-point data) than doing a straightforward matrix transposition after using coalesced accesses.
No takes yet. Share an insight, caveat, or question.
Steele et al. (2019) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: