PARALLELIZATION OF A MULTIPLE MODEL MULTITARGET TRACKING ALGORITHM WITH SUPERLINEAR SPEEDUPS

The interacting multiple model (IMM) estimator has been shown to be ve ry effective when applied to air traffic surveillance problems. Howeve r, because of the additional filter modules necessary to cover the pos sible target maneuvers, the IMM estimator also imposes an increasing c omputational burden. Hence, in an effort to design a real-time multipl e model multitarget tracking algorithm that is independent of the numb er of modules used in the state estimator, we propose a ''coarse-grain ed'' (dynamic) parallelization that is superior, in terms of computati onal performance, to a ''fine-grained'' (static) parallelization of th e state estimator, while not sacrificing tracking accuracy. In additio n to having the potential of realizing superlinear speedups, the propo sed parallelization scales to larger multiprocessor system and is robu st, i.e., it adapts to diverse multitarget scenarios maintaining the s ame level of efficiency given any one of numerous factors influencing the problem size. We develop and demonstrate the dynamic parallelizati on on a shared-memory MIMD multiprocessor for a civilian air traffic s urveillance problem using a measurement database based on two FAA air traffic control radars.