{"data":{"id":"10.6084/m9.figshare.1486461","type":"dois","attributes":{"doi":"10.6084/m9.figshare.1486461","prefix":"10.6084","suffix":"m9.figshare.1486461","identifiers":[],"alternateIdentifiers":[],"creators":[{"name":"Murray, Lawrence M.","nameType":"Personal","givenName":"Lawrence M.","familyName":"Murray","affiliation":[],"nameIdentifiers":[]},{"name":"Lee, Anthony","nameType":"Personal","givenName":"Anthony","familyName":"Lee","affiliation":[],"nameIdentifiers":[]},{"name":"Jacob, Pierre E.","nameType":"Personal","givenName":"Pierre E.","familyName":"Jacob","affiliation":[],"nameIdentifiers":[]}],"titles":[{"title":"Parallel Resampling in the Particle Filter"}],"publisher":"Taylor \u0026 Francis","container":{},"publicationYear":2016,"subjects":[{"subject":"Space Science"},{"subject":"Molecular Biology"},{"subject":"Biotechnology"},{"subject":"19999 Mathematical Sciences not elsewhere classified","subjectScheme":"FOR"},{"subject":"FOS: Mathematics","schemeUri":"http://www.oecd.org/science/inno/38235147.pdf","subjectScheme":"Fields of Science and Technology (FOS)"},{"subject":"FOS: Mathematics","subjectScheme":"Fields of Science and Technology (FOS)"},{"subject":"Cancer"},{"subject":"111714 Mental Health","subjectScheme":"FOR"},{"subject":"FOS: Health sciences","schemeUri":"http://www.oecd.org/science/inno/38235147.pdf","subjectScheme":"Fields of Science and Technology (FOS)"},{"subject":"FOS: Health sciences","subjectScheme":"Fields of Science and Technology (FOS)"},{"subject":"60506 Virology","subjectScheme":"FOR"},{"subject":"FOS: Biological sciences","schemeUri":"http://www.oecd.org/science/inno/38235147.pdf","subjectScheme":"Fields of Science and Technology (FOS)"},{"subject":"FOS: Biological sciences","subjectScheme":"Fields of Science and Technology (FOS)"}],"contributors":[],"dates":[{"date":"2015-07-17","dateType":"Created"},{"date":"2016-08-05","dateType":"Updated"},{"date":"2016","dateType":"Issued"}],"language":null,"types":{"ris":"DATA","bibtex":"misc","citeproc":"dataset","schemaOrg":"Dataset","resourceType":"Dataset","resourceTypeGeneral":"Dataset"},"relatedIdentifiers":[{"relationType":"IsSupplementTo","relatedIdentifier":"10.1080/10618600.2015.1062015","relatedIdentifierType":"DOI"}],"relatedItems":[],"sizes":["289751 Bytes"],"formats":[],"version":null,"rightsList":[{"rights":"Creative Commons Attribution 4.0 International","rightsUri":"https://creativecommons.org/licenses/by/4.0/legalcode","schemeUri":"https://spdx.org/licenses/","rightsIdentifier":"cc-by-4.0","rightsIdentifierScheme":"SPDX"}],"descriptions":[{"description":"Modern parallel computing devices, such as the graphics processing unit (GPU), have gained significant traction in scientific and statistical computing. They are particularly well-suited to data-parallel algorithms such as the particle filter, or more generally sequential Monte Carlo (SMC), which are increasingly used in statistical inference. SMC methods carry a set of weighted \u003ci\u003eparticles\u003c/i\u003e through repeated propagation, weighting, and resampling steps. The propagation and weighting steps are straightforward to parallelize, as they require only independent operations on each particle. The resampling step is more difficult, as standard schemes require a collective operation, such as a sum, across particle weights. Focusing on this resampling step, we analyze two alternative schemes that do not involve a collective operation (Metropolis and rejection resamplers), and compare them to standard schemes (multinomial, stratified, and systematic resamplers). We find that, in certain circumstances, the alternative resamplers can perform significantly faster on a GPU, and to a lesser extent on a CPU, than the standard approaches. Moreover, in single precision, the standard approaches are numerically biased for upward of hundreds of thousands of particles, while the alternatives are not. This is particularly important given greater single- than double-precision throughput on modern devices, and the consequent temptation to use single precision with a greater number of particles. Finally, we provide auxiliary functions useful for implementation, such as for the permutation of ancestry vectors to enable in-place propagation. Supplementary materials are available online.","descriptionType":"Abstract"}],"geoLocations":[],"fundingReferences":[],"xml":"PD94bWwgdmVyc2lvbj0iMS4wIiBlbmNvZGluZz0iVVRGLTgiPz4KPHJlc291cmNlIHhtbG5zPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCIgeG1sbnM6eHNpPSJodHRwOi8vd3d3LnczLm9yZy8yMDAxL1hNTFNjaGVtYS1pbnN0YW5jZSIgeHNpOnNjaGVtYUxvY2F0aW9uPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCBodHRwOi8vc2NoZW1hLmRhdGFjaXRlLm9yZy9tZXRhL2tlcm5lbC00LjEvbWV0YWRhdGEueHNkIj4KICA8aWRlbnRpZmllciBpZGVudGlmaWVyVHlwZT0iRE9JIj4xMC42MDg0L005LkZJR1NIQVJFLjE0ODY0NjE8L2lkZW50aWZpZXI+CiAgPGNyZWF0b3JzPgogICAgPGNyZWF0b3I+CiAgICAgIDxjcmVhdG9yTmFtZT5MYXdyZW5jZSBNLiBNdXJyYXk8L2NyZWF0b3JOYW1lPgogICAgPC9jcmVhdG9yPgogICAgPGNyZWF0b3I+CiAgICAgIDxjcmVhdG9yTmFtZT5BbnRob255IExlZTwvY3JlYXRvck5hbWU+CiAgICA8L2NyZWF0b3I+CiAgICA8Y3JlYXRvcj4KICAgICAgPGNyZWF0b3JOYW1lPlBpZXJyZSBFLiBKYWNvYjwvY3JlYXRvck5hbWU+CiAgICA8L2NyZWF0b3I+CiAgPC9jcmVhdG9ycz4KICA8dGl0bGVzPgogICAgPHRpdGxlPlBhcmFsbGVsIFJlc2FtcGxpbmcgaW4gdGhlIFBhcnRpY2xlIEZpbHRlcjwvdGl0bGU+CiAgPC90aXRsZXM+CiAgPGRlc2NyaXB0aW9ucz4KICAgIDxkZXNjcmlwdGlvbiBkZXNjcmlwdGlvblR5cGU9IkFic3RyYWN0Ij4mbHQ7cCZndDtNb2Rlcm4gcGFyYWxsZWwgY29tcHV0aW5nIGRldmljZXMsIHN1Y2ggYXMgdGhlIGdyYXBoaWNzIHByb2Nlc3NpbmcgdW5pdCAoR1BVKSwgaGF2ZSBnYWluZWQgc2lnbmlmaWNhbnQgdHJhY3Rpb24gaW4gc2NpZW50aWZpYyBhbmQgc3RhdGlzdGljYWwgY29tcHV0aW5nLiBUaGV5IGFyZSBwYXJ0aWN1bGFybHkgd2VsbC1zdWl0ZWQgdG8gZGF0YS1wYXJhbGxlbCBhbGdvcml0aG1zIHN1Y2ggYXMgdGhlIHBhcnRpY2xlIGZpbHRlciwgb3IgbW9yZSBnZW5lcmFsbHkgc2VxdWVudGlhbCBNb250ZSBDYXJsbyAoU01DKSwgd2hpY2ggYXJlIGluY3JlYXNpbmdseSB1c2VkIGluIHN0YXRpc3RpY2FsIGluZmVyZW5jZS4gU01DIG1ldGhvZHMgY2FycnkgYSBzZXQgb2Ygd2VpZ2h0ZWQgJmx0O2kmZ3Q7cGFydGljbGVzJmx0Oy9pJmd0OyB0aHJvdWdoIHJlcGVhdGVkIHByb3BhZ2F0aW9uLCB3ZWlnaHRpbmcsIGFuZCByZXNhbXBsaW5nIHN0ZXBzLiBUaGUgcHJvcGFnYXRpb24gYW5kIHdlaWdodGluZyBzdGVwcyBhcmUgc3RyYWlnaHRmb3J3YXJkIHRvIHBhcmFsbGVsaXplLCBhcyB0aGV5IHJlcXVpcmUgb25seSBpbmRlcGVuZGVudCBvcGVyYXRpb25zIG9uIGVhY2ggcGFydGljbGUuIFRoZSByZXNhbXBsaW5nIHN0ZXAgaXMgbW9yZSBkaWZmaWN1bHQsIGFzIHN0YW5kYXJkIHNjaGVtZXMgcmVxdWlyZSBhIGNvbGxlY3RpdmUgb3BlcmF0aW9uLCBzdWNoIGFzIGEgc3VtLCBhY3Jvc3MgcGFydGljbGUgd2VpZ2h0cy4gRm9jdXNpbmcgb24gdGhpcyByZXNhbXBsaW5nIHN0ZXAsIHdlIGFuYWx5emUgdHdvIGFsdGVybmF0aXZlIHNjaGVtZXMgdGhhdCBkbyBub3QgaW52b2x2ZSBhIGNvbGxlY3RpdmUgb3BlcmF0aW9uIChNZXRyb3BvbGlzIGFuZCByZWplY3Rpb24gcmVzYW1wbGVycyksIGFuZCBjb21wYXJlIHRoZW0gdG8gc3RhbmRhcmQgc2NoZW1lcyAobXVsdGlub21pYWwsIHN0cmF0aWZpZWQsIGFuZCBzeXN0ZW1hdGljIHJlc2FtcGxlcnMpLiBXZSBmaW5kIHRoYXQsIGluIGNlcnRhaW4gY2lyY3Vtc3RhbmNlcywgdGhlIGFsdGVybmF0aXZlIHJlc2FtcGxlcnMgY2FuIHBlcmZvcm0gc2lnbmlmaWNhbnRseSBmYXN0ZXIgb24gYSBHUFUsIGFuZCB0byBhIGxlc3NlciBleHRlbnQgb24gYSBDUFUsIHRoYW4gdGhlIHN0YW5kYXJkIGFwcHJvYWNoZXMuIE1vcmVvdmVyLCBpbiBzaW5nbGUgcHJlY2lzaW9uLCB0aGUgc3RhbmRhcmQgYXBwcm9hY2hlcyBhcmUgbnVtZXJpY2FsbHkgYmlhc2VkIGZvciB1cHdhcmQgb2YgaHVuZHJlZHMgb2YgdGhvdXNhbmRzIG9mIHBhcnRpY2xlcywgd2hpbGUgdGhlIGFsdGVybmF0aXZlcyBhcmUgbm90LiBUaGlzIGlzIHBhcnRpY3VsYXJseSBpbXBvcnRhbnQgZ2l2ZW4gZ3JlYXRlciBzaW5nbGUtIHRoYW4gZG91YmxlLXByZWNpc2lvbiB0aHJvdWdocHV0IG9uIG1vZGVybiBkZXZpY2VzLCBhbmQgdGhlIGNvbnNlcXVlbnQgdGVtcHRhdGlvbiB0byB1c2Ugc2luZ2xlIHByZWNpc2lvbiB3aXRoIGEgZ3JlYXRlciBudW1iZXIgb2YgcGFydGljbGVzLiBGaW5hbGx5LCB3ZSBwcm92aWRlIGF1eGlsaWFyeSBmdW5jdGlvbnMgdXNlZnVsIGZvciBpbXBsZW1lbnRhdGlvbiwgc3VjaCBhcyBmb3IgdGhlIHBlcm11dGF0aW9uIG9mIGFuY2VzdHJ5IHZlY3RvcnMgdG8gZW5hYmxlIGluLXBsYWNlIHByb3BhZ2F0aW9uLiBTdXBwbGVtZW50YXJ5IG1hdGVyaWFscyBhcmUgYXZhaWxhYmxlIG9ubGluZS4mbHQ7L3AmZ3Q7PC9kZXNjcmlwdGlvbj4KICA8L2Rlc2NyaXB0aW9ucz4KICA8c3ViamVjdHM+CiAgICA8c3ViamVjdD5TcGFjZSBTY2llbmNlPC9zdWJqZWN0PgogICAgPHN1YmplY3Q+TW9sZWN1bGFyIEJpb2xvZ3k8L3N1YmplY3Q+CiAgICA8c3ViamVjdD5CaW90ZWNobm9sb2d5PC9zdWJqZWN0PgogICAgPHN1YmplY3Qgc2NoZW1lVVJJPSJodHRwOi8vd3d3LmFicy5nb3YuYXUvYXVzc3RhdHMvYWJzQC5uc2YvMC82QkI0MjdBQjk2OTZDMjI1Q0EyNTc0MTgwMDA0NDYzRSIgc3ViamVjdFNjaGVtZT0iRk9SIj4xOTk5OSBNYXRoZW1hdGljYWwgU2NpZW5jZXMgbm90IGVsc2V3aGVyZSBjbGFzc2lmaWVkPC9zdWJqZWN0PgogICAgPHN1YmplY3Q+Q2FuY2VyPC9zdWJqZWN0PgogICAgPHN1YmplY3Qgc2NoZW1lVVJJPSJodHRwOi8vd3d3LmFicy5nb3YuYXUvYXVzc3RhdHMvYWJzQC5uc2YvMC82QkI0MjdBQjk2OTZDMjI1Q0EyNTc0MTgwMDA0NDYzRSIgc3ViamVjdFNjaGVtZT0iRk9SIj4xMTE3MTQgTWVudGFsIEhlYWx0aDwvc3ViamVjdD4KICAgIDxzdWJqZWN0IHNjaGVtZVVSST0iaHR0cDovL3d3dy5hYnMuZ292LmF1L2F1c3N0YXRzL2Fic0AubnNmLzAvNkJCNDI3QUI5Njk2QzIyNUNBMjU3NDE4MDAwNDQ2M0UiIHN1YmplY3RTY2hlbWU9IkZPUiI+NjA1MDYgVmlyb2xvZ3k8L3N1YmplY3Q+CiAgPC9zdWJqZWN0cz4KICA8cHVibGlzaGVyPlRheWxvciAmYW1wOyBGcmFuY2lzPC9wdWJsaXNoZXI+CiAgPHB1YmxpY2F0aW9uWWVhcj4yMDE2PC9wdWJsaWNhdGlvblllYXI+CiAgPGRhdGVzPgogICAgPGRhdGUgZGF0ZVR5cGU9IkNyZWF0ZWQiPjIwMTUtMDctMTc8L2RhdGU+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iVXBkYXRlZCI+MjAxNi0wOC0wNTwvZGF0ZT4KICA8L2RhdGVzPgogIDxyZXNvdXJjZVR5cGUgcmVzb3VyY2VUeXBlR2VuZXJhbD0iRGF0YXNldCI+RGF0YXNldDwvcmVzb3VyY2VUeXBlPgogIDxzaXplcz4KICAgIDxzaXplPjI4OTc1MSBCeXRlczwvc2l6ZT4KICA8L3NpemVzPgogIDxyZWxhdGVkSWRlbnRpZmllcnM+CiAgICA8cmVsYXRlZElkZW50aWZpZXIgcmVsYXRlZElkZW50aWZpZXJUeXBlPSJET0kiIHJlbGF0aW9uVHlwZT0iSXNTdXBwbGVtZW50VG8iPjEwLjEwODAvMTA2MTg2MDAuMjAxNS4xMDYyMDE1PC9yZWxhdGVkSWRlbnRpZmllcj4KICA8L3JlbGF0ZWRJZGVudGlmaWVycz4KICA8cmlnaHRzTGlzdD4KICAgIDxyaWdodHMgcmlnaHRzVVJJPSJodHRwczovL2NyZWF0aXZlY29tbW9ucy5vcmcvbGljZW5zZXMvYnkvNC4wLyI+Q0MgQlkgNC4wPC9yaWdodHM+CiAgPC9yaWdodHNMaXN0Pgo8L3Jlc291cmNlPg==","url":"https://tandf.figshare.com/articles/dataset/Parallel_resampling_in_the_particle_filter/1486461","contentUrl":null,"metadataVersion":3,"schemaVersion":"http://datacite.org/schema/kernel-4","source":"mds","isActive":true,"state":"findable","reason":null,"viewCount":0,"viewsOverTime":[],"downloadCount":0,"downloadsOverTime":[],"referenceCount":0,"citationCount":0,"citationsOverTime":[],"partCount":0,"partOfCount":0,"versionCount":0,"versionOfCount":0,"created":"2015-07-17T18:44:16.000Z","registered":"2015-07-17T18:44:17.000Z","published":"2016","updated":"2020-09-04T16:30:45.000Z"},"relationships":{"client":{"data":{"id":"figshare.ars","type":"clients"}},"provider":{"data":{"id":"otjm","type":"providers"}},"media":{"data":{"id":"10.6084/m9.figshare.1486461","type":"media"}},"references":{"data":[]},"citations":{"data":[]},"parts":{"data":[]},"partOf":{"data":[]},"versions":{"data":[]},"versionOf":{"data":[]}}}}