A class of parallel algorithms for computation of the manipulator inertia matrix

Abstract

A class of parallel and parallel/pipeline algorithms for computation of the manipulator inertial matrix is presented. An algorithm based on the composite rigid-body spatial inertia method, which results in less data dependency and hence better parallelization efficiency, is used for computation of the inertia matrix. Two parallel algorithms are developed which achieve the time lower bound of O((log/sub 2/ n))+O(1) in the computation with O(n/sup 2/) processors. The architectural features required for perfect mapping of these algorithms and their communication complexity are analyzed. The performance of the algorithms when mapped on two- and one-dimensional (linear) processor arrays with nearest-neighbor connection is investigated. Mapping on the linear array results in new algorithms with a computational complexity of k/sub 1/n(log/sub 2/n)+k/sub 2/(log/sub 2/n)+k/sub 3/. A parallel/pipeline algorithm is also presented which achieves the computation time of k/sub 1/n+k/sub 2/(log/sub 2/ n)+k/sub 3/ on the linear array. An architecture-oriented approach is used in the design of the algorithms.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>