论文部分内容阅读
矩阵是数值代数中的一个基本概念,许多科学计算问题往往都可以归结为对矩阵的操作。在许多应用中,需要用到较长的矩阵链相乘,例如机器人,机器控制,以及计算机动画等。矩阵链相乘的不同顺序会使数量乘法的次数相差很大,对计算效率有很大的影响。因此,如何高效地完成矩阵链相乘的运算,对提高科学计算的效率至关重要。目前,许多学者已经提出了解决矩阵链相乘问题的各种串行算法和并行算法,并在不断地进行改进现有的算法和提出新的算法。矩阵链相乘问题可以分为两类,即矩阵链乘序问题和矩阵链相乘处理器调度问题。现有的解决矩阵链乘序问题的并行算法基本上是基于PRAM模型,而矩阵链相乘处理器调度问题的提出和解决,使在并行机上进行矩阵链相乘更加有效。本文在对现有的解决矩阵链相乘问题的算法进行研究的基础上,创造性地提出了三个新算法:1、已提出的解决矩阵链乘序问题的并行算法主要基于PRAM模型,本文在解决矩阵链乘序问题的串行动态规划算法基础上,提出一种基于二维网孔结构的并行算法,而二维网孔结构比PRAM模型更接近实际。该算法根据串行算法逐个对角线进行计算的特点,采用上三角结构的二维网孔结构,在O(n2 )的时间内解决矩阵链相乘问题,而串行算法的时间复杂度为θ(n3),有了显著的改进。2、如果所有的处理器按照解决矩阵链乘序问题得到的最优顺序逐个矩阵乘积来计算,并不一定使计算时间最少,需要考虑如何调度多个处理器并行地进行矩阵乘运算。本文介绍了矩阵链相乘处理器调度问题和离散处理器调度算法,并在此基础上描述了Heejo lee等提出的解决矩阵链相乘处理器调度问题的算法,然后提出了一种解决这一问题的时间复杂度更低的处理器调度算法,该算法的时间复杂度为O(n+plogn),而Heejo lee等提出的算法的时间复杂度为O(n2+np)。新算法借鉴了自底向上归并排序的思想,采用贪心策略,使所有的处理器都能尽量被充分利用,当处理器个数较多时,采用新算法的调度策略使计算时间更短。3、随着并行机逐渐向MIMD发展,有学者提出了MIMD并行机上解决矩阵链乘序问题的算法,而已提出的算法只是人工分配处理器之间的计算任务。因此,本文在描述和分析MIMD并行机上解决矩阵链乘序问题的算法的基础上,提出了一种合理分配任务的算法,该算法首先计算出总的任务,然后尽量平均地分配给各个处理器,算法的时间复杂度是O(n)。最后,对本文提出的解决矩阵链相乘问题的几种算法进行了比较。