Robot control computation in microprocessor systems with multiple arithmetic processors using a modified DF/IHS scheduling algorithm

Abstract

The problem of designing a high-performance robot controller with multiple arithmetic processing units (APUs) is addressed. One attractive feature of the controller is that a minimum number of special-purpose hardware components are needed, and off-the-shelf components can be used. One main processor unit (MPU) schedules a number of APUs to produce the computational throughput. The depth-first/initial-heuristic-search (DF/IHS) algorithm is an efficient algorithm that solves the difficult nonpolynomial- (NP-) complete problem of scheduling a set of ordered computational tasks onto a multiprocessor system. When interprocessor communication overheads are appreciable, however it is not very effective in providing a practical near-optimum schedule, it fails to consider the problem of contention for shared resources. A multiprocessor scheduling algorithm which minimizes the effects of overhead and thus reduces the effect of contention is presented. The algorithm is used to derive the operational instructions for the APUs and the MPU for a multiple-APU-based robot controller. Simulations show that six MC68881 APUs can be used to generate the robot control computations in approximately 2.5 ms.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>