Generating multiprocessor implementations of robotics algorithms from task precedence graphs

Abstract

In complex control systems, a single processor is often inadequate to meet real-time deadline demands. A decrease in processing time can be attained by decomposing the algorithm into portions which can run concurrently on a multiprocessor. Implementing an algorithm for a multiprocessor operating system can be arduous and time-consuming; a change to multiprocessor or to the decomposition of the algorithm may require that large portions of the implementation be completely re-written. In this paper we present a utility to graphically model a process or algorithm as a directed, acyclic graph of nodes. The calculations which each node are to perform can then be entered by a programmer. The utility determines a node-to-processor allocation, then combines the node calculations allocated to each processor, and generates all initialisation and inter-node communications code. We present this utility as a tool for investigating multiprocessor multi-tasking algorithms, with application to robotics and control processes. Results of processes which have been so modelled are given.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>