A simple method for rejection sampling efficiency improvement on SIMT architectures
Abstract We derive a probability distribution for the possible number of iterations required for a SIMT (single instruction multiple thread) program using rejection sampling to finish creating a sample across all threads. This distribution is found to match a recently proposed distrib...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer US
2021
|
| Online Access: | https://hdl.handle.net/1721.1/132084 |
| _version_ | 1826190359470800896 |
|---|---|
| author | Ridley, Gavin Forget, Benoit |
| author2 | Massachusetts Institute of Technology. Department of Nuclear Science and Engineering |
| author_facet | Massachusetts Institute of Technology. Department of Nuclear Science and Engineering Ridley, Gavin Forget, Benoit |
| author_sort | Ridley, Gavin |
| collection | MIT |
| description | Abstract
We derive a probability distribution for the possible number of iterations required for a SIMT (single instruction multiple thread) program using rejection sampling to finish creating a sample across all threads. This distribution is found to match a recently proposed distribution from Chakraborty and Gupta (in: Communications in statistics: theory and methods, 2015) that was shown as a good approximation of certain datasets. This work demonstrates an exact application of this distribution. The distribution can be used to evaluate the relative merit of some sampling methods on the GPU without resort to numerical tests. The distribution reduces to the expected geometric distribution in the single thread per warp limit. A simplified formula to approximate the expected number of iterations required to obtain rejection iteration samples is provided. With this new result, a simple, efficient layout for assigning sampling tasks to threads on a GPU is found as a function of the rejection probability without recourse to more complicated rejection sampling methods. |
| first_indexed | 2024-09-23T08:38:49Z |
| format | Article |
| id | mit-1721.1/132084 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T08:38:49Z |
| publishDate | 2021 |
| publisher | Springer US |
| record_format | dspace |
| spelling | mit-1721.1/1320842023-02-16T20:41:42Z A simple method for rejection sampling efficiency improvement on SIMT architectures Ridley, Gavin Forget, Benoit Massachusetts Institute of Technology. Department of Nuclear Science and Engineering Abstract We derive a probability distribution for the possible number of iterations required for a SIMT (single instruction multiple thread) program using rejection sampling to finish creating a sample across all threads. This distribution is found to match a recently proposed distribution from Chakraborty and Gupta (in: Communications in statistics: theory and methods, 2015) that was shown as a good approximation of certain datasets. This work demonstrates an exact application of this distribution. The distribution can be used to evaluate the relative merit of some sampling methods on the GPU without resort to numerical tests. The distribution reduces to the expected geometric distribution in the single thread per warp limit. A simplified formula to approximate the expected number of iterations required to obtain rejection iteration samples is provided. With this new result, a simple, efficient layout for assigning sampling tasks to threads on a GPU is found as a function of the rejection probability without recourse to more complicated rejection sampling methods. 2021-09-20T17:41:52Z 2021-09-20T17:41:52Z 2021-03-30 2021-03-31T03:35:18Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/132084 Statistics and Computing. 2021 Mar 30;31(3):30 en https://doi.org/10.1007/s11222-021-10003-z Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ The Author(s), under exclusive licence to Springer Science+Business Media, LLC part of Springer Nature application/pdf Springer US Springer US |
| spellingShingle | Ridley, Gavin Forget, Benoit A simple method for rejection sampling efficiency improvement on SIMT architectures |
| title | A simple method for rejection sampling efficiency improvement on SIMT architectures |
| title_full | A simple method for rejection sampling efficiency improvement on SIMT architectures |
| title_fullStr | A simple method for rejection sampling efficiency improvement on SIMT architectures |
| title_full_unstemmed | A simple method for rejection sampling efficiency improvement on SIMT architectures |
| title_short | A simple method for rejection sampling efficiency improvement on SIMT architectures |
| title_sort | simple method for rejection sampling efficiency improvement on simt architectures |
| url | https://hdl.handle.net/1721.1/132084 |
| work_keys_str_mv | AT ridleygavin asimplemethodforrejectionsamplingefficiencyimprovementonsimtarchitectures AT forgetbenoit asimplemethodforrejectionsamplingefficiencyimprovementonsimtarchitectures AT ridleygavin simplemethodforrejectionsamplingefficiencyimprovementonsimtarchitectures AT forgetbenoit simplemethodforrejectionsamplingefficiencyimprovementonsimtarchitectures |