NASA's Jet Propulsion Laboratory, Pasadena, California
A class of parallel and parallel/pipeline algorithms is presented for more effici ent computation of the manipulator inertia matrix. Efficient computation of the inert ia matrix is essential for implementing the advanced dynamic control schemes as well as the dynamic simulation of the manipulator motion. At the present, however, the fastest serial algorithms for computing the inertia matrix are far f rom adequate for efficient real-time dynamic control and simulation. Hence, the exploitation of parallelism in the computation of the inertia matrix is the key f actor in achieving the required efficiency. The parallel algorithms are derived based on a new algorithm for computing the inertia matrix, the Composite Rigid-Body Spatial Inertia algorithm, which, compared to the previous algorithms, incorporates less data dependency in the computation and hence provides a greater efficiency for parallelization. Two parallel algorithms are developed that achieve the time lower bound of O(log2n)+O(1) in the computation with O(n2) processors. These algorithms are designated as the First Parallel Algorithm and Second Parallel Algorithm (FPA and SPA). The architectural requirements, i.e., synchronization and communication mechanisms, for the implementation of these algorithms on a two-dimensional array of n(n+1)/2 processors are analyzed. It is shown that, while the FPA achieves a better computational complexity, the SPA requires a much simpler interconnection structure. Mapping the FPA and SPA on a linear array of n processors with a nearest- neighbor interconnection results in two new algorithms designated as the First and the Second Architecture-Dependent Algorithm (FADA and SADA) with the computational complexity of O(nlog2n)+O(log2n)+O(1). It is shown that the FADA is more efficient than the SADA, which implies that the FPA is more suitable than the SPA for implementing on a linear array. A Parallel/Pipeline Algorithm (PPA) is also developed with computational complexity of O(n)+O(log2n)+O(1), which represents the fastest computation time for evaluating the inertia matrix on a one-dimensional linear array of n processors. Compared to the FPA which achieves the best computation time on a two-dimensional array of n(n + 1)/2 processors, the PPA achieves a slightly smaller speedup but a significantly greater efficiency. Given this performance an d the simple architectural requirements, the PPA represents an attractive alternative for exploiting concurrency in computing the inertia matrix. The computational costs of different algorithms are presented in the table where m and a represent the cost of multiplication and addition, respectively. ([x] denot es the smallest integer greater than or equal to x; x* = x if x = 2m, and x* = 2m if 2m > x > 2m-1.) The speedup and efficiency of different algorithms (for n = 6) are also evaluated and presented in the table. In this evaluation, the cost of multiplication and addition is taken to be the same.
Point of Contact:
Antal K. Bejczy
Mail Stop 198-219
Jet Propulsion Laboratory
4800 Oak Grove Drive
Pasadena CA 91109
818-354-4568
bejczy@telerobotics.jpl.nasa.gov
Telerobotics Program
page
Please email the site webmaster
with any comments, criticisms or corrections
for this page.
Maintained by: Dave Lavery
Last updated: May 10, 1996