{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T15:16:26Z","timestamp":1773414986260,"version":"3.50.1"},"reference-count":38,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2021,11,26]],"date-time":"2021-11-26T00:00:00Z","timestamp":1637884800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["1818639"],"award-info":[{"award-number":["1818639"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/R018537\/1"],"award-info":[{"award-number":["EP\/R018537\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Schlumberger (United Kingdom)","award":["1818639"],"award-info":[{"award-number":["1818639"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Resampling is a well-known statistical algorithm that is commonly applied in the context of Particle Filters (PFs) in order to perform state estimation for non-linear non-Gaussian dynamic models. As the models become more complex and accurate, the run-time of PF applications becomes increasingly slow. Parallel computing can help to address this. However, resampling (and, hence, PFs as well) necessarily involves a bottleneck, the redistribution step, which is notoriously challenging to parallelize if using textbook parallel computing techniques. A state-of-the-art redistribution takes O((log2N)2) computations on Distributed Memory (DM) architectures, which most supercomputers adopt, whereas redistribution can be performed in O(log2N) on Shared Memory (SM) architectures, such as GPU or mainstream CPUs. In this paper, we propose a novel parallel redistribution for DM that achieves an O(log2N) time complexity. We also present empirical results that indicate that our novel approach outperforms the O((log2N)2) approach.<\/jats:p>","DOI":"10.3390\/a14120342","type":"journal-article","created":{"date-parts":[[2021,11,28]],"date-time":"2021-11-28T22:19:16Z","timestamp":1638137956000},"page":"342","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["An O(log2N) Fully-Balanced Resampling Algorithm for Particle Filters on Distributed Memory Architectures"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2218-4720","authenticated-orcid":false,"given":"Alessandro","family":"Varsi","sequence":"first","affiliation":[{"name":"Department of Electrical Engineering and Electronics, University of Liverpool, Liverpool L69 3GJ, UK"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1917-2913","authenticated-orcid":false,"given":"Simon","family":"Maskell","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering and Electronics, University of Liverpool, Liverpool L69 3GJ, UK"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5396-3749","authenticated-orcid":false,"given":"Paul G.","family":"Spirakis","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Liverpool, Liverpool L69 3BX, UK"},{"name":"Department of Computer Engineering and Informatics, University of Patras, 26504 Patras, Greece"}]}],"member":"1968","published-online":{"date-parts":[[2021,11,26]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1109\/78.978374","article-title":"A Tutorial on Particle Filters for Online Nonlinear\/Non\u2013Gaussian Bayesian Tracking","volume":"50","author":"Arulampalam","year":"2002","journal-title":"IEEE Trans. Signal Process."},{"key":"ref_2","first-page":"5101","article-title":"Particle Filter Recurrent Neural Networks","volume":"34","author":"Ma","year":"2020","journal-title":"Proc. AAAI Conf. Artif. Intell."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"649","DOI":"10.1089\/cmb.2014.0003","article-title":"Estimation of Tumor Size Evolution Using Particle Filters","volume":"22","author":"Costa","year":"2015","journal-title":"J. Comput. Biol. A J. Comput. Mol. Cell Biol."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Li, Q., and Liang, S.Y. (2018). Degradation Trend Prediction for Rotating Machinery Using Long-Range Dependence and Particle Filter Approach. Algorithms, 11.","DOI":"10.3390\/a11070089"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"2335","DOI":"10.1002\/qj.3551","article-title":"Particle Filters for High-Dimensional Geoscience Applications: A Review","volume":"145","author":"Nerger","year":"2019","journal-title":"Q. J. R. Meteorol. Soc."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"965","DOI":"10.3390\/a8040965","article-title":"A Particle Filter Track-Before-Detect Algorithm Based on Hybrid Differential Evolution","volume":"8","author":"Zhang","year":"2015","journal-title":"Algorithms"},{"key":"ref_7","unstructured":"Varsi, A., Kekempanos, L., Thiyagalingam, J., and Maskell, S. (2019). A Single SMC Sampler on MPI that Outperforms a Single MCMC Sampler. arXiv."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1016\/j.ascom.2017.01.001","article-title":"astroABC: An Approximate Bayesian Computation Sequential Monte Carlo Sampler for Cosmological Parameter Estimation","volume":"19","author":"Jennings","year":"2017","journal-title":"Astron. Comput."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Liu, J., Wang, C., Wang, W., and Li, Z. (2019). Particle Probability Hypothesis Density Filter Based on Pairwise Markov Chains. Algorithms, 12.","DOI":"10.3390\/a12020031"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"4177","DOI":"10.1109\/TSP.2019.2926035","article-title":"High-Dimensional Filtering Using Nested Sequential Monte Carlo","volume":"67","author":"Naesseth","year":"2019","journal-title":"IEEE Trans. Signal Process."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1080\/00207217.2011.623276","article-title":"Distributed Multi-Sensor Particle Filter for Bearings-Only Tracking","volume":"99","author":"Zhang","year":"2012","journal-title":"Int. J. Electron."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Lopez, F., Zhang, L., Beaman, J., and Mok, A. (2014, January 8\u201311). Implementation of a Particle Filter on a GPU for Nonlinear Estimation in a Manufacturing Remelting Process. Proceedings of the 2014 IEEE\/ASME International Conference on Advanced Intelligent Mechatronics, Besan\u00e7on, France.","DOI":"10.1109\/AIM.2014.6878102"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1016\/j.compind.2015.03.013","article-title":"Particle Filtering on GPU Architectures for Manufacturing Applications","volume":"71","author":"Lopez","year":"2015","journal-title":"Comput. Ind."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Kreuger, K., and Osgood, N. (2015, January 6\u20139). Particle Filtering Using Agent-Based Transmission Models. Proceedings of the 2015 Winter Simulation Conference (WSC), Huntington Beach, CA, USA.","DOI":"10.1109\/WSC.2015.7408211"},{"key":"ref_15","first-page":"3","article-title":"A Tutorial on Particle Filtering and Smoothing: Fifteen Years Later","volume":"12","author":"Doucet","year":"2009","journal-title":"Handb. Nonlinear Filter."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Djuric, P.M., Lu, T., and Bugallo, M.F. (2007, January 15\u201320). Multiple Particle Filtering. Proceedings of the 2007 IEEE International Conference on Acoustics, Speech and Signal Processing\u2014ICASSP \u201907, Honolulu, HI, USA.","DOI":"10.1109\/ICASSP.2007.367053"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Demirel, O., Smal, I., Niessen, W., Meijering, E., and Sbalzarini, I. (2014, January 30). PPF\u2014A Parallel Particle Filtering Library. Proceedings of the IET Conference on Data Fusion Target Tracking 2014: Algorithms and Applications (DF TT 2014), Liverpool, UK.","DOI":"10.1049\/cp.2014.0529"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"789","DOI":"10.1080\/10618600.2015.1062015","article-title":"Parallel Resampling in the Particle Filter","volume":"25","author":"Murray","year":"2016","journal-title":"J. Comput. Graph. Stat."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"1570","DOI":"10.1109\/LSP.2020.3014035","article-title":"A Fast Parallel Particle Filter for Shared Memory Systems","volume":"27","author":"Varsi","year":"2020","journal-title":"IEEE Signal Process. Lett."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"2442","DOI":"10.1109\/TSP.2005.849185","article-title":"Resampling Algorithms and Architectures for Distributed Particle Filters","volume":"53","author":"Bolic","year":"2005","journal-title":"IEEE Trans. Signal Process."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1016\/j.sigpro.2016.02.028","article-title":"Parallel Particle PHD Filter Implemented on Multicore and Cluster Systems","volume":"127","author":"Zhu","year":"2016","journal-title":"Signal Process."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"481","DOI":"10.1109\/TPDS.2015.2405912","article-title":"Particle Routing in Distributed Particle Filters for Large-Scale Spatial Temporal Systems","volume":"27","author":"Bai","year":"2016","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1111\/sjos.12408","article-title":"Parallelizing Particle Filters With Butterfly Interactions","volume":"47","author":"Heine","year":"2020","journal-title":"Scand. J. Stat."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"1601","DOI":"10.1109\/TAES.2012.6178081","article-title":"An Optimization-Based Parallel Particle Filter for Multitarget Tracking","volume":"48","author":"Sutharsan","year":"2012","journal-title":"IEEE Trans. Aerosp. Electron. Syst."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Varsi, A., Kekempanos, L., Thiyagalingam, J., and Maskell, S. (2017, January 4\u20135). Parallelising Particle Filters with Deterministic Runtime on Distributed Memory Systems. Proceedings of the IET 3rd International Conference on Intelligent Signal Processing (ISP 2017), London, UK.","DOI":"10.1049\/cp.2017.0357"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Maskell, S., Alun-Jones, B., and Macleod, M. (2006, January 13\u201315). A Single Instruction Multiple Data Particle Filter. Proceedings of the IEEE Nonlinear Statistical Signal Processing Workshop, Cambridge, UK.","DOI":"10.1109\/NSSPW.2006.4378818"},{"key":"ref_27","unstructured":"Batcher, K.E. (May, January 30). Sorting Networks and Their Applications. Proceedings of the Spring Joint Computer Conference, Atlantic City, NJ, USA. AFIPS \u201968 (Spring)."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"White, S., Verosky, N., and Newhall, T. (2012, January 10\u201313). A CUDA-MPI Hybrid Bitonic Sorting Algorithm for GPU Clusters. Proceedings of the 2012 41st International Conference on Parallel Processing Workshops, Pittsburgh, PA, USA.","DOI":"10.1109\/ICPPW.2012.82"},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Baddar, S., and Batcher, K. (2011). Designing Sorting Networks: A New Paradigm, Springer. SpringerLink: B\u00fccher.","DOI":"10.1007\/978-1-4614-1851-1"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1186\/s13634-017-0505-9","article-title":"MapReduce Particle Filtering with Exact Resampling and Deterministic Runtime","volume":"2017","author":"Thiyagalingam","year":"2017","journal-title":"EURASIP J. Adv. Signal Process."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Hol, J.D., Schon, T.B., and Gustafsson, F. (2006, January 13\u201315). On Resampling Algorithms for Particle Filters. Proceedings of the 2006 IEEE Nonlinear Statistical Signal Processing Workshop, Cambridge, UK.","DOI":"10.1109\/NSSPW.2006.4378824"},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Koml\u00f3s, J., and Szemer\u00e9di, E. (1983, January 25\u201327). An 0(N Log N) Sorting Network. Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, Boston, MA, USA. STOC \u201983.","DOI":"10.1145\/800061.808726"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/BF01840378","article-title":"Improved Sorting Networks With O(logN) Depth","volume":"5","author":"Paterson","year":"1990","journal-title":"Algorithmica"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1007\/s00453-007-9025-6","article-title":"Sorting Networks of Logarithmic Depth, Further Simplified","volume":"53","author":"Seiferas","year":"2009","journal-title":"Algorithmica"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"831","DOI":"10.1145\/322217.322232","article-title":"Parallel Prefix Computation","volume":"27","author":"Ladner","year":"1980","journal-title":"J. ACM"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1006\/jpdc.2000.1698","article-title":"Optimal and Efficient Algorithms for Summing and Prefix Summing on Parallel Machines","volume":"62","author":"Santos","year":"2002","journal-title":"J. Parallel Distrib. Comput."},{"key":"ref_37","unstructured":"Gropp, W., Lusk, E., and Skjellum, A. (2014). Using MPI: Portable Parallel Programming with the Message-Passing Interface, The MIT Press."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1007\/s11227-013-0912-0","article-title":"A Compound OpenMP\/MPI Program Development Toolkit for Hybrid CPU\/GPU Clusters","volume":"66","author":"Li","year":"2013","journal-title":"J. Supercomput."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/12\/342\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T07:36:16Z","timestamp":1760168176000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/12\/342"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,26]]},"references-count":38,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2021,12]]}},"alternative-id":["a14120342"],"URL":"https:\/\/doi.org\/10.3390\/a14120342","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,11,26]]}}}