Abstract
In this paper we address the problem of designing a high performance robot controller with multiple arithmetic processing units (APU’s). One attractive feature about this controller is that a minimum number of special purpose hardware components are needed, and in fact off the shelf components can be used. In the controller described in this paper, one main processor (MPU) schedules a number of APU’s to produce the computational throughput. In this design an efficient scheduling algorithm plays the most important role in the system performance. DF/IHS* algorithm [8] is an efficient algorithm that solves "strong" NP-hard problems of scheduling a set of particularly ordered computational tasks onto a multiprocessor system. When interprocessor communication overheads are appreciable, it is not very effective in providing a practical near optimum schedule. It fails to consider the problem of contention for shared resources. In this paper we present new multiprocessor scheduling algorithm, which minimizes the effect of overhead and by doing so it reduces the effect of contention. We used this scheduling algorithm to derive the operational instructions of the APU’s and the MPU for our multiple APU-based robot controller. Simulations show six Motorola MC 68881 APU’s can be used to generate the robotic control computations in approximately 2.5 milliseconds. The control computations involve inverse dynamic calculations, forward kinematics, inverse kinematics, and trajectory computations. *DF/IHS = Depth First/Initial Heuristic Search, this is a derivative of CP/MISF (critical path/Most Immediate Successor First) scheduling algorithm, see [8].
Date of this Version
12-1-1987