Parallel Tracking Algorithm with Super-linear Speedups

January 1997 No Comments

Parallelization of a Multiple Model Multi-target Tracking Algorithm with Super-linear Speedups

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

Abstract

The interacting multiple model (IMM) estimator has been shown to be very effective when applied to air traffic surveillance problems. However, because of the additional filter modules necessary to cover the possible target maneuvers, the IMM estimator also imposes an increasing computational burden. Hence, in an effort to design a real-time multiple model multitarget tracking algorithm that is independent of the number of modules used in the state estimator, we propose a “coarse-grained” (dynamic) parallelization that is superior, in terms of computational performance, to a “fine-grained” (static) parallelization of the state estimator, while not sacrificing tracking accuracy. In addition to having the potential of realizing superlinear speedups, the proposed parallelization scales to larger multiprocessor systems and is robust, i.e., it adapts to diverse multitarget scenarios maintaining the same level of efficiency given any one of numerous factors influencing the problem size. We develop and demonstrate the dynamic parallelization on a shared-memory MIMD multiprocessor for a civilian air traffic surveillance problem using a measurement database based on two FAA air traffic control radars.

Conclusion

We have proposed a robust, scalable, coarse-grained (dynamic) parallelization of a multiple model multitarget tracking algorithm that realizes superlinear speedups on shared-memory MIMD multiprocessors. The advantage of the dynamic parallelization presented here shows up in a reasonably large multitarget problem where hundreds of candidate measurement-to-track associations must be processed; indeed, the parallelization cannot be efficiently utilized in the case of a single target tracking problem which is inherently static. In this case, however, the fine-grained parallelization is extremely inefficient, unless the number of filter modules used in the estimator is unrealistically high. We demonstrated the computational superiority of the proposed parallelization over the static parallelization via several performance measures utilizing a measurement database based on two FAA air traffic control radars.

Citation

Popp, R., K. Pattipati, Y. Bar-Shalom and M. Yeddanapudi, “Parallelization of a Multiple Model Multi-target Tracking Algorithm with Super-linear Speedups,” IEEE Trans. Aerospace and Electronic Systems, vol. 33, no. 1, pp. 281–290, Jan 1997.