SCHEDULING THE PARALLEL KALMAN ALGORITHM ONTO MULTIPROCESSOR SYSTEMS - A GENETIC APPROACH

The efficiency of parallel implementations of Kalman tracking filters is known to be increased by suitably modifying the definition of the s tate vector. Using the modified state vector, a parallel Kalman algori thm is derived by partially decomposing the matrices of the 3D-3S trac king problem, and then implementing in parallel all operations involvi ng the reduced-dimension matrices. The tasks of the parallel Kalman al gorithm, represented by an acyclic task graph, are scheduled onto a mu ltiprocessor system using a genetic approach to obtain a minimum compl etion time. Quantitative genetic scheduling results are presented for the performance of the scheme, using a network of transputers. (C) 199 8 Elsevier Science Ltd, All rights reserved.