An Efficient p-Fold Parallel Algorithm For Computing Robot Inverse Dynamics

This paper shows that the time lower bound of computing the inverse dynamics of an n-link robot manipulator parallelly using p processors is O(k1[n/p] + k2[log2 p]), where k1 and k2 are constants. A novel parallel algorithm for computing the inverse dynamics using the Newton-Euler equations of motion was developed to be implemented on an SIMD computer with p procesors to achieve the time lower bound. When p = n, the proposed parallel algorithm achieves the Minsky´s time lower bound O([log2n]) [22], which is the conjecture of parallel evaluation. The proposed p-fold parallel algorithm can be best described as consisting of p-parallel blocks with pipelined elements within each parallel block. The results from the computations in the p blocks form a new homogeneous linear recurrence of size p, which can be computed using the recurive doubling algorithm. A modified inverse perfect shuffle interconnection scheme was suggested to interconnect the p processors. Furthermore, the proposed parallel algorithm is susceptible to a systolic pipelined architecture, requiring three floating-point operations (Flops) per complete set of joint torques.