DATA TOKEN HEURISTIC SCHEDULING OF THE KALMAN ALGORITHM ONTO A MESSAGE-PASSING MULTIPROCESSOR SYSTEM

Scheduling the tasks of a parallel algorithm onto a network of process ors to minimize the completion time of the task graph is an NP-hard pr oblem, and heuristic methods are commonly used to solve this problem. Published works in this area, however, do not take advantage of the fo llowing aspects of the problem: (i) the availability of the full knowl edge of the data that is being transferred during inter-task communica tion, and (ii) the availability of full duplex high-speed communicatio n links in many multiprocessors (such as transputers). The scheduling approach presented in this paper, the data token heuristic (DTH) appro ach, exploits the above features, leading to a reduced schedule length . This is achieved by checking the pool of data tokens in the processo rs, and routing the required data token to the processor through the d ynamic shortest path. The DTH approach is then used to find the best t ransputer network topology that gives the minimum schedule length for the parallel implementation of the Kalman algorithm. Quantitative resu lts of scheduling the Kalman algorithm on a 4-transputer network with T-805 transputers are presented. Copyright (C) 1997 Elsevier Science L td.