A Contribution to Parallelization of Symbolic Robot Models

Abstract

This paper is focused on task scheduling in multiprocessor robot controllers. To minimize the input-output time delay our consideration is restricted to parallel architectures that include complete crossbar interconnection networks. In this paper, an efficient scheduling algorithm based on a heuristic function is considered. This function takes into account delays caused by interprocessor communication and minimizes both the execution time and the communication cost. Robot control computation based on a highly efficient customized symbolic method is decomposed into a large number of simple tasks, each involving a single floating-point operation. Starting with an empty partial schedule, each step of the search extends the current partial schedule by adding one of the tasks yet to be scheduled. The heuristic function used in the algorithm actively directs the search for a feasible schedule, i.e. it helps choose the task that extends the current partial schedule. To increase the computational rate we introduced overlapping of computations. To prove the theoretical results, the algorithm is verified by experiments on an INMOS T800 transputer network. The experimental results show that the most complicated dynamic control laws can be accomplished in hundreds of microseconds.