学位论文 > 优秀研究生学位论文题录展示

矩阵链相乘问题研究

作　者: 徐卫志
导　师: 王洪国
学　校: 山东师范大学
专　业: 计算机软件与理论
关键词: 矩阵链乘序问题动态规划二维网孔处理器调度贪心算法多指令流多数据流任务分配
分类号: TP301.6
类　型: 硕士论文
年　份: 2008年
下　载: 42次
引　用: 0次
阅　读: 论文下载

内容摘要

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

全文目录

摘要  6-7
ABSTRACT  7-9
第一章绪论  9-13
  1.1 研究背景和意义  9-10
    1.1.1 矩阵链相乘的应用  9
    1.1.2 研究矩阵链相乘问题的重要性  9
    1.1.3 并行计算发展概述  9-10
  1.2 研究现状  10-11
    1.2.1 MCOP 研究现状  10
    1.2.2 MCSP 研究现状  10-11
  1.3 创新性工作  11
  1.4 本文的组织  11-13
第二章并行计算基础  13-22
  2.1 并行计算机体系结构  13-15
    2.1.1 并行计算机结构模型  13
    2.1.2 并行计算机访存模型  13-14
    2.1.3 并行计算机互联网络拓扑结构  14-15
  2.2 并行算法  15-17
    2.2.1 并行计算模型  15-16
    2.2.2 并行算法的分类  16-17
  2.3 并行计算性能测评  17-18
  2.4 并行程序设计  18-21
    2.4.1 并行编程模型  18-19
    2.4.2 分布存储系统并行编程  19-21
  2.5 本章小结  21-22
第三章矩阵链相乘问题研究进展  22-27
  3.1 问题的提出  22-23
    3.1.1 MCOP 的提出  22
    3.1.2 MCSP 的提出  22-23
  3.2 MCOP 研究进展  23-26
    3.2.1 解决MCOP 的串行算法  23-24
    3.2.2 解决MCOP 的并行算法  24-26
  3.3 MCSP 研究进展  26-27
第四章在二维网孔结构上解决MCOP 的算法  27-33
  4.1 引言  27
  4.2 矩阵链相乘串行动态规划算法  27-29
    4.2.1 矩阵链相乘串行动态规划算法描述  27-28
    4.2.2 算法分析  28-29
  4.3 在二维网孔上的并行算法设计  29-32
    4.3.1 二维网孔结构  29
    4.3.2 算法原理  29
    4.3.3 算法举例  29-30
    4.3.4 算法描述  30-31
    4.3.5 复杂度分析  31-32
  4.4 本章小结  32-33
第五章解决矩阵链相乘处理器调度问题的一种新算法  33-42
  5.1 引言  33
  5.2 离散处理器调度算法和两种解决MCSP 的算法  33-37
    5.2.1 符号  33-34
    5.2.2 矩阵链相乘处理器调度问题(MCSP)的描述  34
    5.2.3 基本概念  34-35
    5.2.4 两对矩阵乘积的离散处理器调度算法（DPA 算法）  35
    5.2.5 DPA-k 算法  35-36
    5.2.6 两种解决MCSP 的算法  36-37
  5.3 解决MCSP 的一种新算法  37-39
    5.3.1 算法思想  37-39
    5.3.2 算法分析  39
  5.4 算法比较  39-41
    5.4.1 时间复杂度比较  39-40
    5.4.2 举例分析  40-41
  5.5 本章小结  41-42
第六章 MIMD 并行机上解决矩阵链乘序问题的算法研究  42-47
  6.1 引言  42
  6.2 MIMD 并行机上解决矩阵链乘序问题的算法及复杂度分析  42-44
    6.2.1 算法描述  42-43
    6.2.2 算法举例  43
    6.2.3 算法复杂度分析  43-44
  6.3 处理器之间的任务分配算法  44-45
    6.3.1 算法思想  44
    6.3.2 算法描述  44-45
    6.3.3 算法复杂度分析  45
  6.4 算法比较  45-46
  6.5 本章小结  46-47
第七章总结与展望  47-49
参考文献  49-52
攻读硕士学位期间发表的论文和参与的项目  52-53
致谢  53

矩阵链相乘问题研究

内容摘要

全文目录

相似论文