首页> 外文OA文献 >Parallel algorithms and architecture for computation of manipulator forward dynamics
【2h】

Parallel algorithms and architecture for computation of manipulator forward dynamics

机译:机械手正向动力学计算的并行算法和体系结构

摘要

Parallel computation of manipulator forward dynamics is investigated. Considering three classes of algorithms for the solution of the problem, that is, the O(n), the O(n exp 2), and the O(n exp 3) algorithms, parallelism in the problem is analyzed. It is shown that the problem belongs to the class of NC and that the time and processors bounds are of O(log2/2n) and O(n exp 4), respectively. However, the fastest stable parallel algorithms achieve the computation time of O(n) and can be derived by parallelization of the O(n exp 3) serial algorithms. Parallel computation of the O(n exp 3) algorithms requires the development of parallel algorithms for a set of fundamentally different problems, that is, the Newton-Euler formulation, the computation of the inertia matrix, decomposition of the symmetric, positive definite matrix, and the solution of triangular systems. Parallel algorithms for this set of problems are developed which can be efficiently implemented on a unique architecture, a triangular array of n(n+2)/2 processors with a simple nearest-neighbor interconnection. This architecture is particularly suitable for VLSI and WSI implementations. The developed parallel algorithm, compared to the best serial O(n) algorithm, achieves an asymptotic speedup of more than two orders-of-magnitude in the computation the forward dynamics.
机译:研究了机械手正向动力学的并行计算。考虑解决问题的三类算法,即O(n),O(n exp 2)和O(n exp 3)算法,分析了问题中的并行性。结果表明,该问题属于NC类,时间和处理器范围分别为O(log2 / 2n)和O(n exp 4)。但是,最快的稳定并行算法可以达到O(n)的计算时间,并且可以通过O(n exp 3)串行算法的并行化来得出。 O(n exp 3)算法的并行计算需要针对一系列根本不同的问题开发并行算法,这些问题包括牛顿-欧拉公式,惯性矩阵的计算,对称正定矩阵的分解,以及三角系统的解。针对这一系列问题的并行算法得以开发,可以在独特的体系结构上有效地实现,该体系结构是n(n + 2)/ 2个处理器的三角形阵列,具有简单的近邻互连。该体系结构特别适用于VLSI和WSI实现。与最佳串行O(n)算法相比,开发的并行算法在正向动力学计算中实现了超过两个数量级的渐近加速。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号