Data Association Shared Memory Parallelization

October 1997 No Comments

Shared Memory Parallelization of the Data Association Problem in Multi-Target Tracking

Author: Popp, R., Pattipati, K., Bar-Shalom, Y. & Ammar, R.

Abstract

The focus of this paper is to present the results of our investigation and evaluation of various shared-memory parallelizations of the data association problem in multitarget tracking. The multitarget tracking algorithm developed was for a sparse air traffic surveillance problem, and is based on an Interacting Multiple Model (IMM) state estimator embedded into the (2D) assignment framework. The IMM estimator imposes a computational burden in terms of both space and time complexity, since more than one filter model is used to calculate state estimates, covariances, and likelihood functions. In fact, contrary to conventional wisdom, for sparse multitarget tracking problems, we show that the assignment (or data association) problem is not the major computational bottleneck. Instead, the interface to the assignment problem, namely, computing the rather numerous gating tests and IMM state estimates, covariance calculations, and likelihood function evaluations (used as cost coefficients in the assignment problem), is the major source of the workload. Using a measurement database based on two FAA air traffic control radars, we show that a “coarse-grained” (dynamic) parallelization across the numerous tracks found in a multitarget tracking problem is robust, scalable, and demonstrates superior computational performance to previously proposed “fine-grained” (static) parallelizations within the IMM.

Conclusion

We have presented our investigation and evaluation of various shared-memory parallelizations of the data asso- ciation problem in multitarget tracking for general- purpose shared-memory MIMD multiprocessor systems. A sparse measurement database, based on two FAA air traffic control radars, served as the data for our multitar- get tracking problem. We showed that, for sparse multi- target tracking problems, the assignment (or data asso- ciation) problem is not the major computational bottle- neck. Instead, the interface to the assignment problem, namely, computing the rather numerous gating tests and IMM state estimates, covariance calculations, and likeli- hood function evaluations (used as cost coefficients in the assignment problem), is the major source of the workload. Because of the shortcomings associated with previously proposed fine-grained parallelizations of the IMM estimator in a multitarget tracking problem, we proposed a scalable, robust coarse-grained paralleliza- tion across tracks that has excellent performance. Ana- lytically and empirically, we showed that the coarse- grained parallelization has superior execution time per- formance over the fine-grained parallelization for any number of filter models used in the IMM estimator. Furthermore, we showed that the coarse-grained paral- lelization can realize superlinear speedups independent of the number of filter models used in the IMM estima- tor. On the other hand, the performance of the fine- grained parallelization, being dependent on the number of filter models used, yielded negligible throughput for any number of filter models, marginal speedups when many models were used, and worse execution time than sequential time when three or less filter models were used.

Citation

Popp, R., K. Pattipati, Y. Bar-Shalom and R. Ammar, “Shared-Memory Parallelization of the Data Association Problem in Multi-target Tracking,” IEEE Trans. Parallel and Distributed Systems, vol. 8, no. 10, pp. 993–1005, Oct 1997.