（计算机软件与理论专业论文）矩阵链相乘问题研究.pdf

山东师范大学硕士学位论文 矩阵链相乘问题研究 捅斐 一 矩阵是数值代数中的一个基本概念，许多科学计算问题往往都可以归结为对矩阵的操 作。在许多应用中，需要用到较长的矩阵链相乘，例如机器人，机器控制，以及计算机动 画等。矩阵链相乘的不同顺序会使数量乘法的次数相差很大，对计算效率有很大的影响。 因此，如何高效地完成矩阵链相乘的运算，对提高科学计算的效率至关重要。 。 目前，许多学者已经提出了解决矩阵链相乘问题的各种串行算法秘并行算法，并在不 断地进行改进现有的算法和提出新的算法。矩阵链相乘问题可以分为两类，即矩阵链乘序 问题和矩阵链相乘处理器调度问题。现有的解决矩阵链乘序问题的并行算法基本上是基于 p r a m 模型，而矩阵链相乘处理器调度问题的提出和解决，使在并行机上进行矩阵链相 乘更加有效。本文在对现有的解决矩阵链相乘问题的算法进行研究的基础上，创造性地提 出了三个新算法： l 、已提出的解决矩阵链乘序问题的并行算法主要基于p r a m 模型，本文在解决矩阵链 乘序问题的串行动态规划算法基础上，提出一种基于二维嗍孑乙结构的并行算法逦维网 孔结构比p 洲模型更接近实际。该算法根据串行算法逐个对角线进行计算的特点，采用 ? 上三角结构的二维网孔结构，在o ( n 2 ) 的时间内解决矩阵链相乘问题，而串行算法的时间 复杂度为秒( n3 ) ，有了显著的改进。 一 2 、如果所有的处理器按照解决矩阵链乘序问题得到的最优顺序逐个矩阵乘积来计算， 并不一定使计算时间最少，需要考虑如何调度多个处理器并行地进行矩阵乘运算。本文介 绍了矩阵链相乘处理器调度问题和离散处理器调度算法，并在此基础上描述了h e e j ol e e 等提出的解决矩阵链相乘处理器调度问题的算法，然后提出了一种解决这一问题的时间复 杂度更低的处理器调度算法，该算法的时间复杂度为o ( 1 唧l o 印) ，而h e e j ol 等提出 的算法的时间复杂度为o ( n 2 + n p ) 。新算法借鉴了自底向上归并排序的思想，采用贪心策 略，使所有的处理器都能尽量被充分利用，当处理器个数较多时，采用新算法的调度策略 使计算时间更短。 3 、随着并行机逐渐向m i m d 发展，有学者提出了m i m d 并行机上解决矩阵链乘序问 题的算法，而已提出的算法只是人工分配处理器之间的计算任务。因此，本文在描述和分 析m i m d 并行机上解决矩阵链乘序问题的算法的基础上，提出了一种合理分配任务的算 法，该算法首先计算出总的任务，然后尽量平均地分配给各个处理器，算法的时间复杂度 是o ( n ) 。最后，对本文提出的解决矩阵链相乘问题的几种算法进行了比较。 关键词：矩阵链乘序问题；动态规划；二维网孔；处理器调度；贪心算法；多指令流多 数据流；任务分配 分类号：t p 3 0 1 山东师范大学硕士学位论文 i 沁s e a r c ho nm a t r i xc h a i l lp r o d u c t a b s t r a c t m 撕xi sab 槭cc 0 n c e p ti l in 啪e r i c a lv a l u ea l g e b 仇m 觚ys c i e i l t i f i cc o m p u t i n gp r o b l 锄s c 0 m ed o w nt 0m eo p e r 龇i o n so ft h em a t r i c 韶i l lm a l l ya p p l i c a t i o n s ，al o n gc h a i no fm a t r i c e sa r e u s e d ，s u c ha sr o b o t i c s ，m a c h i n ec o n t r o la n dc o m p u t e ra l l i m a t i o n t h ed x 山的侧鲋e 印矾p 雕w 酗弘= 蓁鋈蓄霉匿雾雾萋茎蓁薷霉蚕雾l 霄霆蓁霪l | l 萋毒垂蓁雾妻霪 蒂舌妻雾蓁蓁雨型 囊翼- ! 耋冀霎鲤萎主奏匮翼藿蓁! ；誓鬻矍璧l 翻耋i 辜霎! 霎酋薹i 薹羹耵鬻羹窝型茎羹l 馐l l u l | | e 勘蠢- _ 鏖曼茎；i 童乔茴薹錾 x 山东师范大学硕士学位论文 1 1 研究背景和意义 1 1 1 矩阵链相乘的应用 第一章绪论 矩阵是数值代数中的一个基本概念，许多科学计算问题往往都可以归结为对 矩阵的操作，如数值天气预报、图像和信号处理、模式识别、地震分析等。 在许多应用中，需要用到较长的矩阵链相乘，例如机器人，机器控制，以及 计算机动画等。矩阵链相乘的不同顺序会使数量乘法的次数相差很大，对计算的 效率有很大的影响。因此，如何高效地完成矩阵链相乘的计算，对提高科学计算 的效率至关重要。 1 1 2 研究矩阵链相乘问题的重要性 n 个矩阵m t m z 坂相乘，数量乘法运算的耗费取决于n 1 个乘法执行的顺 序，使数量乘法的次数达到最小的顺序可以用许多方法找到。用蛮力方法可以计 算每种可能顺序的数量乘法，但是蛮力方法得到n 个矩阵乘积的最优方法所需 的时间是q ( 4 厅以) 【1 1 ，它甚至对于一个中等规模的n 值也是不切实际的。解决 这一问题的另外一种方法是使用动态规划，算法时间复杂度为目( 咒3 ) 【2 1 。当矩阵 个数n 不断增加时，口( ，z 3 ) 这样的时间复杂度也要花费较多的运算时间。 虽然已经提出了复杂度为o ( 1 d o 盟) 的算法【3 ，4 】，并且被认为是最优的，但是 随着并行计算的发展，通过设计并行算法来缩短计算时间、提高计算效率仍是很 有必要的，这也是并行处理技术迅速发展的必然结果。用并行算法解决矩阵链相 乘问题，就会涉及到多处理器调度问题，因此，对矩阵链相乘多处理器调度问题 的研究是很有必要的。 1 3 并行计算发展概述 7 0 年代以来，各种1 6 位、3 2 位、6 4 位微处理器的不断问世，并行向量处理机 ( p v p ) ，对称多处理机( s m p ) ，大规模并行处理机( m p p ) ，工作站集群( c o w ) 等并行机体系结构技术发展很快，硬件在不同层次上以不同方式实现了多种并行 山东师范大学硕士学位论文 1 3 创新性工作 本文对解决m c o p 和m c s p 这两个问题的各种算法进行研究、归纳、比较和 分析的基础上，提出或改进了三种解决矩阵链相乘问题的算法，并对这几种新算 法进行了分析和比较。 本论文的创新性工作如下： ( 1 ) 现有的解决矩阵链乘序问题的并行算法主要基于p r a m 模型，而这一 模型过于抽象。本文在解决矩阵链乘序问题的串行动态规划算法基础上，提出一 种基于二维网孔结构的并行动态规划算法。该算法采用一个上三角结构的二维网 孔结构，一在o ( n2 ) 的时间内解决矩阵链乘序问题，而二维网孔比以往采用的p 删 模型更接近实际。 ( 2 ) 用多个处理器计算矩阵链相乘，需要一种有效的处理器调度算法使计 算时间最短且处理器利用率最高。本文描述了矩阵链相乘处理器调度问题和离散 处理器调度算法，以及h e e o1 e e 等提出的解决m c s p 的处理器调度算法：进而提出。 了一种解决矩阵链相乘处理器调度问题的时间复杂度更低的算法，该算法借鉴了 自底向上归并排序的思想，时间复杂度为o ( n + p l o 驴) ，而h e e j ol e e 等提出的算法 的时间复杂度为o ( n 2 + n p ) 。五个矩阵相乘的实例表明，当处理器个数较多时，新 算法使处理器能尽量被充分利用，因而优于h e e j ol e e 等提出的调度算法。 ( 3 ) 由于并行机向m i m d 结构发展，研究m i m d 并行机上解决矩阵链乘序问题二 的并行算法具有重要意义。s t e v ea s t r a t e 提出了超立方结构上解决矩阵链乘序问 题动态规划算法，但没有提出任务分配算法。本文描述了m m d 并行机上解决矩 阵链乘序问题的算法，其时间复杂度为0 ( n 3 p ) 。针对处理器之间任务分配的问 题，文中提出了一种合理分配任务的算法，该算法首先计算出加法、乘法和比较 运算的总运算量，然后近似平均地分配给各个处理器，其时问复杂度是0 ( n ) 。最 后，对本文提出的解决矩阵链相乘问题的几种算法进行了比较。 1 4 本文的组织 第一章首先介绍了矩阵链相乘问题的研究背景、意义和研究现状，然后提出 了本文的创新性工作。 第二章介绍了并行处理技术。包括并行计算机体系结构、并行计算机访存模 型、并行计算性能测评和并行程序设计四个部分。 第三章介绍了矩阵链相乘问题研究进展，首先介绍了解决矩阵链乘序问题的 各种串行和并行算法，然后介绍了解决矩阵链相乘处理器调度问题的算法。 第四章首先分析了二维网孔结构的特点，然后在解决矩阵链乘序问题的串行 3 山东师范大学硕士学位论文 动态规划算法基础上，提出一种基于二维网孔结构的并行动态规划算法。 第五章首先描述了h e e ol e e 等提出的解决m c s p 的处理器调度算法，然后提 出了一种解决m c s p 的时间复杂度更低的算法，使处理器能尽量被充分利用，并与 h e e j ol e e 等提出的调度算法进行了比较分析。 第六章介绍了并行机向m i m d 的发展趋势，描述了m i m d 并行机上解决矩阵链乘 序问题的算法；针对处理器之间任务分配的问题，提出了一种合理分配任务的算 法。 4 第七章是对全文的总结，并指出】，需要进一步完善和深入研究的内容。 山东师范大学硕士学位论文 第二章并行计算基础 并行处理技术主要是以算法为核心，并行语言为描述，软硬件作为实现工具 的相互联系而又相互制约的一种结构技术。并行计算机体系结构、并行算法、并 行计算的性能测评和并行程序设计是“并行处理 研究的四大分支，它们之间是 相辅相成的【3 4 - 3 5 1 。 2 1 并行计算机体系结构 从并行算法设计的角度来看，并行计算机体系结构【3 6 】主要考虑结构模型、 访存模型、一致性模型、通信模型、同步模型、互连网络。下面主要介绍并行计 算机结构模型、并行计算机访存模型和并行计算机互联网络拓扑结构。 2 1 1 并行计算机结构模型 大型并行机系统一般可分为六类：单指令多数据流机s i m d ( s i n 酉e - i n s t m c t i o n m u l t i p l e d a t a ) 、并行向量处理机p v p ( p a m l l e lv e c t o rp r o c e s s o r ) 、对称多处理 s m p ( s ) ，1 1 1 i n e t r i cm u l t i p r o c e s s o r ) 、大规模并行处理机m p p ( m 舔s i v e l yp a r a l l e l p r o c e s s o r ) 、工作站机群c o w ( c l u s t e ro fw b d ! 【s t a t i o n ) 和分布共享存储 d s m 【d i s t r i b u t c ds h 锄甜m 锄。珂) 多处理机。在这六种并行机系统中，除了s i m d 外，其余的五种均属于多指令多数据流 m i m d ( m u l t i p l e - i i l s t m c t i o n m u l t i p l e - d a t a ) 。 这六种并行机系统之间都有异同点。p v p 与s m p 均为单地址空间，但在是否 带c a c h e 、互连网络要求、i ，o 并行度方面不同；m p p 与d s m 在多单地址空间、 通信方式、c a c h e 一致性方面不同；m p p 与c o w 在结点结构、互连网络要求、耦 合程度方面不同。 2 1 2 并行计算机访存模型 并行计算机访存模型和上节讨论的结构模型是实际并行计算机系统的两个 方面。访存模型主要有五种：均匀存储访问模型u m a ( u n i f o n i lm 锄o w a c c e s s ) 、 非均匀存储访问模型n u m a ( n o i 啪i f o 衄m e r l l o d ，a c c e s s ) 、全高速缓存存储访问 模型c o m a ( c a c h e o 1 1 1 ym 锄。巧a c c e s s ) 、高速缓存一致性非均匀存储访问模型 c c n u m a ( c o h e l l t c a c h en o i n m i f o 彻m e m o r ya c c e s s ) 、非远程存储访问模型 n o r m a 州。一r e m o t em 啪。叮a c c e s s ) 。 在这五种多处理机模型中，处理机访问存储器的模式都不同。u m a 模型中， 5 山东师范大学硕士学位论文 每个处理机访问所有存储器的时间相同，而n i m a 和c c 州7 m a 模型中，每 个处理机访问所有存储器的时间不相同。对于c o m a 模型，各处理机访问所有 高速缓存时间不相同，而n o 眦模型中，一各处理机只能访问本地存储器，不 能直接访问远程存储器( 需要通过消息传递实现间接访问) 。 2 1 3 并行计算机互联网络拓扑结构 并行计算机互联网络包括静态拓扑结构、动态拓扑结构和宽带互联网络，下 面分别对它们进行介绍。 2 1 3 1 静态拓扑结构 静态拓扑结构是指结点之间存在固定的物理联接方式，程序执行过程中，结 点问的点对点联接关系不变，静态拓扑结构包括一维阵列( 舡a y ) 、环( r i n g ) ； 多维网孔( m e s h ) 、多维环( t o m s ) ；树( t r e e ) ：二叉树、x - 树、星树、胖树； 超立方体( h y p e r c u b e ) 等等。 2 1 3 2 动态拓扑结构1 。 一动念拓扑结构足指结点之间无固定的物理联接关系，而是在联接路径的交叉 点处用电子开关、路由器或仲裁器等提供动念联接的特性，主要包含单一总线、 多层总线、交叉开关、多级互联网络等。 ? 。( d 单一总线是指联接处理器、存储模块和i o 设备等的一组导线和插座， 在主设备( 处理器) 和从设备( 存储器) 之间传递数据。单一总线的特征有： 公用总线以分时工作为基础，各处理器模块分时共享总线带宽，即在同一个 时种周期，至多只有一个设备能占有总线； 总线带宽= 总线主频总线宽度，例如a s u s 主板的总线频率= 1 5 0 m h z ，总线 宽度为6 4 位，则该总线的带宽= 1 2 g b s ； 监听协议与仲裁算法，用于选择哪个设备占有总线。 ( 2 ) 多层总线是指各设备内部存在本地总线( 结点、存储器、i o 设备) ， 本地总线之间以系统总线相互联接，系统总线一般在通信主板中实现。 一( 3 ) 交叉开关( c r o s s b a rs w i t c h e r ) 是指所有结点通过交叉开关阵列相互连 接，每个交叉开关均为其中两个结点之间提供一条专用联接通路，同时，任意两 个结点之问也能找到一个交叉开关，在它们之间建立专用联接通路。交叉丌关的 状态可根据程序的要求动态地设置为“开 和“关 。交叉开关特征有： 结点之问联接：交叉开关一般构成n n 阵列，但在每一行和每一列同时只能 有一个交叉点开关处于“开 状态，从而它同时只能接通n 对结点； 结点与存储器之间的联接：每个存储器模块同时只允许一个结点访问，故每 一列只能接通一个交叉点开关，但是为了支持并行存储访问，每一行同时可以接 6 山东师范大学硕士学位论文 通多个交叉点开关。交叉开关的成本为n 2 ，n 为端口数，限制了它在大规模并行 机中的应用，一般适合8 1 6 个处理器的情形。 ( 4 ) 多级互联网络( m 掰：m u l t i s t a g ei n t e r c o l l i l e 嘶0 nn 曲 ，o r k ) 由多个单级 交叉开关级联接起来形成大型交叉开关网络，相邻交叉开关级之间存在固定的物 理联接拓扑。为了在输入与输出之间建立联接，可以动态地设置开关状态。 2 1 3 3 宽带互联网络 宽带互联网络主要包括以下种类： 快速以太网( 1 0 m b p s ( 8 2 年) 、l o o m b p s ( 9 4 年 、l g 呐( 们年) ，其特征 类似于单一总线：分时共享、竞争仲裁，带宽1 0 0 m b p s ，8 台处理机共享，每台 处理机的平均带宽为1 2 5m b p s 。 f d d i ：光纤分布式数据接口( f i b e rd i s t r i b u t e dd a t al i l t e r e ) 采用双向光 纤令牌环，所有结点联接在该环中，提供l 。o 。2 0 0 m b p s 数据传输速度，一双向环提 供冗余通路以提供可靠性，距离可达1 0 0 米、2 公里、6 0 公里等，比快速以太网具 有更好的可靠性、适应性。 s w i t c h e r ：交叉开关，可同时为n 2 对端口提供1 0 0 m b p s 的直接联接通路，其 中n 为端口总数。多个s w i t c h e r 堆叠( 不多于7 个) 可形成多级s w i t c h e r 。b e o 硼i l f 微机机群采用这种结构互联所有结点。 朋r i 订：异步传输模式( a 1 阳v i ：a s y n c h r o n o 璐t r 趾s 断m o d e ) 是在光纤通信 基础上建立起来的一种新的宽带综合业务数字网的交换技术，众质无关的信息传 输协议，采用5 3 字节的定长短数据单元( c e l l ) 进行传输。大的数掘包进入a t m 网络时，分解成多个定长的单元，各个单元独立传输，到达目的地址后i 这些单 元汇集成原来的数据包。a t m 网络适合高速度传输声音、图像、视频和数据等 的所有形式的媒体。 m y 血e t ：专用机群互联网络，带宽可达2 0 0 m b 秒，延迟小于1 0 u s 。 i i l f i i 曲a 1 1 d ：专用机群互联网络，带宽可达1 2 5 g b 秒，延迟小于6 璐。 q u 埘c s ：专用机群互联网络，带宽可达4 0 0 m b 秒，延迟小于6 u s 。 h i p p i ：高性能并行接口( h i 曲p e r f o m a l l c ep a r a l l e l1 1 1 t e 而c e ) ，1 9 9 3 年标准 ( a n s 3 t 9 3 ) 形成。单工点对点的数据传输界面，带宽可达8 0 0 m b s 1 6 g b s 。 2 2 并行算法 2 2 1 并行计算模型 并行算法【3 7 1 是在并行计算模型上设计出的，而并行计算模型是从不同的并 行计算机体系结构模型中抽象出来的。并行计算模型主要有：p r a m 模型、异步 7 山东师范大学硕士学位论文 则称为超线性加速比。根据a m d a l l l 定律，严格的线形加速比似乎是不可能达 到的，更不用说超线性加速比了。但是在某些使用程序算法中，可能出现这一现 象。例如某些并行搜索技术允许每个处理器在不同的方向上搜索，一旦某个进程 找到了一个结果，它就向其它处理器发出信号终止搜索，这样就会比串行机的相 应算法提前取消那些无谓的搜索分支，因而出现超线性加速比。但在一般情况下， 当并行计算结果出现超线性加速比时，就要很慎重地分析原因。并行计算机系统 中各个处理器的存储方式不同，高速缓存的影响，以及并行系统的开销的均摊都 有可能出现超线性加速比的假象0 并行效率是与加速比相关联的概念，一个并行程序的效率的定义为e d s 咖， 其中p 为处理器个数。当加速比s 口接近于p 时，效率k 接近于1 。影响并行 效率的因素很多，首先不能期望一个程序的所有部分都能完全并行，例如输入输 出部分。处理器之间的通信与同步都需要时徊j 卉销j 各个处理器中所执行的运算 量也不可能完全精确相同，总会出现某些处理器的负载不均衡甚至是处于闲置等 待状态。 可扩展性是指并行算法在多大程度上能够有效利用多处理机台数增加的能 力的一个度量。随着处理机的增加，如果效率曲线基本保持不变，或者略有下降， 则称该算法在所用的并行系统上可扩展性好，如果效率曲线下降很快，则称可扩 展性差。对于用网络分布式环境做大规模并行计算而言，并行算法的可扩展性对 于效率是至关重要的，可扩展性研究己成为并行计算的一个活跃的研究方向。 2 4 并行程序设计 2 4 1 并行编程模型 并行编程模型( p a r a l l e lp r 0 酉锄m o d e l ) 是一种程序抽象的集合，它给程序 员提供了一幅计算机硬件软件系统透明的简图，程序员利用这些模型就可以为 多处理机、多计算机和工作站机群等设计并行程序。目前主要有隐式编程、数据 并行、消息传递和共享变量四种编程模型3 8 】。 隐式编程模型：这种编程模型是相对显式编程模型而言的，程序员不用显式 的说明并行性，而让编译器、运行支持系统对程序进行并行化。现在比较流行的 有以下几种形式：并行化编译器、自动并行化、用户指导和运行时间并行化。这 种模型突出要解决的问题是数据依赖和控制依赖。并行化编译技术是一个同趋活 跃的研究课题，但是由于目前这种技术不成熟，所以并行效率不高。 数据并行模型：这种模型既可以在s i m d 计算机上实现，也可以在s p m d 计算机上实现，这取决于粒度大小。s i m d 程序着重丌发指令级细粒度的并行性。 l o 山东师范大学硕士学位论文 s p 加程序着重开发子程序级中粒度的并行性。数据并行即将相同的操作同时 作用于不同的数据。这种模型是一种较高层次上的模型，它提供给编程者一个全 一局的地址空问。一般这种形式的语言本身就提供并行执行的语义，因此对于编程 者来说，只需要简单地指明执行什么样的并行操作和并行操作的对象，就实现了 数据并行的编程。 消息传递模型：指各个并行执行的部分之间通过消息传递来交换信息、协调 步伐、控制执行。消息可以是指令、数据、同步信号或中断信号等。在消息传递 并行程序中，用户必须明确地为进程调度数据和负载r 它比较适合开发大粒度的 并行性，这些程序是多线程的和异步的，要求显示同步以确保正确地执行顺序。 然而这些程序均有其分开的地址空间。消息传递一般是面向分布式内存的，但是， 它也可适用于共享内存的并行机。消息传递模型比数据并行模型灵活，两种广泛 使用的标准库p 和m p i 使消息传递程序大大地增强了可移植性。消息传递 为编程者提供了更灵活的控制手段和表达并行的方法，一些数据并行方法很难表 达的并行算法，都可以用消息传递模型柬实现。灵活性和控制手段的多样化，是： 消息传递并行程序能提供高的执行效率的重要原因。 共享变量模型：在这种模型中，驻留在各处理器上的进程可以通过读写公 共存储器中的共享变量相互通信。它与数据并行模型的相似之处在于它有一个单 一的全局名字空间；它与消息传递模型的相似之处在于它是多线程的和异步的。 然而数据是驻留在单一共享地址空间中，因此不需要显示调度数据，而下作负载 既可显示也可隐式调度。通信通过共享的读写变量隐式完成，而同步必须是显 示的，也保持进程执行的正确顺序。 2 4 2 分布存储系统并行编程 从并行程序设计的角度看，分布存储系统的主要特点是：系统通过互连网络 将多个处理器连接起来，每个处理器均有自己的局部存储器，所有的局部存储器 就构成了整个地址空间；整个地址空间有局部和全局两种编址方式，全局编址方 式是指系统的所有局部存储器统一编址，用户程序空间是一个统一的全局地址空 间，其中远程存储器的访问与局部存储器的访问一样用指令来完成，其指令地址 是由处理器号和局部存储器地址所组成。局部编址方式是系统中各局部存储器单 独编址，用户程序空间是多地址空间，远程存储器的访问要通过调用消息传递库 程序来实现的。上述的特点，导致了分布存储系统的两种并行编程模型：消息传 递模型和数据并行模型。对于消息传递模型，主要有m p i 和p v m 两种并行编程环 境，而h p f 数据并行机制则属于数据并行模型。 ( 1 ) m p i 消息传递接口 山东师范大学硕士学位论文 m p i ( m e s s a g ep a s s i n gi n t e 血c e ) 是1 9 9 4 年发布的一种消息传递接口，是目 前最重要的并行编程工具。它实际上是一个消息传递函数库的标准说明，共有上 百个函数调用接口。在f 0 l h 黜州7 7 和c 语言中可以对这些函数进行调用。由于 m p i 具有移植性好、易用性、有完备的异步通信功能、有正式和详细的精确定义 等多种优点，而且有多种不同的免费、高效、实用的实现版本，几乎所有的并行 计算机都提供对它的支持。因此，在短短几年内m p i 己成为消息传递并行编程模 式的标准。 ，m p i 是个复杂的系统，它包含了1 2 9 个函数( 根据1 9 9 4 年发布的m p i 标准) 事实上，1 9 9 7 年修订的标准j 称之为m p l 2 ，已超过2 0 0 ，目前最常用的也有约 3 0 个。然而我们可以只使用其中的6 个最基本的函数就能编写一个完整的m p i 程 序去求解问题。 ( 2 ) p v m 并行虚拟机 并行虚拟机p v m ( p a r a l l e l 咖a 1m a c h i n e ) 是由美困橡树岭国家实验室于 1 9 9 9 年丌发的二种支持网络并行计算的支撑软件。它可在同构异构型网络环境 下模拟实现一个通用的基于分：布存储的并行计算机系统，提供基于消息传递的并 行程序设计接口，使网上的用户能够集中地使用众多的机器资源来求解大规模计 算问题。p v m 虽然没有m p i 功能那么强大，但由于其出现较早，且是一个自包含 系统( m p i 不是自包含的) ，同时p v m 不是一个标准( m p i 是个标准) ，这就 意味它较易修改，所以在大犁计算应用领域中得到广莎使用。 ( 3 ) h p f 数据并行机制 高性能f o m 锄( h i 曲p e r f o m 雒c ef o n r 觚) 简称h p f ，是一个支持数据并 行的并行语言标准。它提供了全局名字空间和单线程控制，用户可以用分布和对 准说明定义所希望的数据布局，用显式的并行结构表达并行机制。h p f 中没有显 式的任务划分和通信语句，代码的定义是在高层进行的，因此具有良好的移植性， 通过具体机器上的编译器可以生成各种系统平台上的高效代码。 h p f 提供了一组扩展的说明，用于指定数据的分布和对准，可将数据显式地 定义到抽象的处理器上，能够让用户告诉编译器如何在各处理器问调度数据，以 使通信开销最小和负载划分最均匀：h p f 还定义了一组新的库，为并行操作定义 了一个标准的接口，包括归约、组合一散射、前缀及后缀、分类和位操作函数等。 但是在h p f 的使用过程中会遇到一些问题，比如说并行性问题。因为h p f 是 单线程的，所以一个数据并行的程序逻辑上只有一个进程，尽管多个节点能够对 不同的数据子域执行相同的程序。绝大多数并行问题由系统管理，用户不用担心 进程的生成、结束和有多少进程正在运行程序。因为h p f 是语句级的数据并行， 它允许在同一时问不同的节点执行不同的指令，因此可同时支持s i m d 和s p m d 并行计算，但不支持m p m d 计算。程序中的并行度是随所用的不同的数组指派或 1 2 山东师范大学硕士学位论文 p i j 个处理器顺序地计算m i m k 和m k 小一m j ，再用这氏j 个处理器把计算结果 相乘；另一种方法用p 让个处理器计算m r m 。，同时用p ，j 个处理器计算 m k + l m j ，然后把计算结果用p i ，j 个处理器相乘，其中p i k + p 川，p j ，。 所以，用“j 个处理器计算m i m j 所需的时间l ，( p “) 满足以下递归关系： 互，( p f ，) m i n f 戤( 霉t ( p f ，) + 瓦+ 1 ，( 所，) + ( 鸭，聊i + i ，脚p i ，p f ，) m a x ( 霉。i ( p i 。) ，瓦1 ，j ( p j 1 ) ) + ( 研f 掰t + 1 朋，+ l ，p ，) ) j m c s p 定义：如何找到矩阵链相乘的顺序以及处理器如何调度才能使在一个 并行系统上计算时间最少的问题。 m c s p 的时间复杂性：如果处理器个数足够多，这个问题可咀在多项式时间 内解决；当处理器个数是有限的p 个时，m c s p 是一个n p 困难问题。 3 2m c o p 研究进展 3 2 1 解决m c o p 的串行算法 ( 1 ) 用蛮力方法可以计算每一种可能顺序的数量乘法，但是蛮力方法得到n 个矩阵乘积的最优方法所需的时间是f 2 ( 矿力) ，它甚至对手二个斗等规模酌n 值也是不切实际的【i 】。 ( 2 ) s s g o d b o l e 提出了解决这一问题的动态规划算法【2 】，算法时间复杂度 为1 5 7 ( n3 ) 。当矩阵个数n 不断增加时，这样的时问复杂度要花费较大的运算时间。 因此通过对串行动态规划算法的并行化来缩短计算时间提高效率是很有必要 的。 ( 3 ) a k c h a l l d r a 提出一种启发式算法【l l 】，时间复杂度是o ( n ) ，这个算法不能 保证最终计算结果是矩阵链的最优顺序，但是如果最优顺序的矩阵链相乘需要的 时间是t 那么用这个算法得到的矩阵链相乘的顺序进行计算所花费的时间不超， 过2 t 。 ( 4 ) f y c l l i n 提出一种改进的启发式算法【2 1 ，时间复杂度也是o ( n ) ，用这 个算法得到的矩阵链顺序进行计算所花费的时间不超过1 2 5 t 。 ( 5 ) t c h u 和m t s h i n g 提出一种时间复杂度为o ( n l o 鲈) 的算法。 论文的第一部分【6 】将矩阵链相乘问题转化为凸多边形三角划分问题，提出并 证明了凸多边形划分相关的一些定理，提出筛选对角线的o n e s w e 印算法。 1 5 山东师范大学硕士学位论文 论文的第二部分【7 】提出了在只有一个局部最大顶点和一个局部最小顶点的 特殊多边形上的最优划分算法，时间复杂度是o ( n ) ；然后提出在一般的多边形上 的最优划分算法，时间复杂度是o ( n l o 印) 。这两个算法都是首先调用o n e s w e 印 算法，产生对角线的集合，然后对这个集合里的对角线进行删除和压缩操作，最 终剩下来的就是在最优划分中保留的对角线。 ( 6 ) t c h u 和m t s h i n g 在凸多边形划分相关理论的基础上提出一种能够找 到凸多边形接近最优划分的算法【1 3 】，此算法得到的凸多边形划分的耗费不超过 最优划分耗费的1 1 5 5 倍。 主要研究人员 年份方法 。 算法时自j 复杂度 h g o u l d1 9 7 7蛮力方法 q ( 4 ”石) s s g o d b o l e1 9 7 3动态规划算法 护( n 3 ) a k c h a l l d r a1 9 7 5 近似算法o ( n ) 、f y ：c h i n ：1 9 7 8近似算法o ( n ) t c h u 和1 9 8 2 ， 将该问题转化为凸 o ( n l o 印 ) m t s h i n g 1 9 8 4多边形的最优三角划分 t c h u 和1 9 8 2近似算法o ( n ) m t s h i n g 表3 1 解决m c o p 的串行算法研究进展 3 2 2 解决m c o p 的并行算法 ( 1 ) l v a l i a n t 提出花费o ( 1 0 9 21 1 ) 时间和n 9 个处理器的并行算法【1 5 1 。 ( 2 ) w r 砂t e r 在p r a m c r e w 模型上使用n6 l o 印个处理器在o ( 1 0 9 2 n ) 时间 内解决矩阵链相乘问题【1 6 1 。 ( 3 ) h u a n g ，l i ua n d s w a n a t h a n 在脚t e r 的算法基础上进行改进，也是用 o ( 1 0 9 21 1 ) 的时间，但是处理器个数减少到n6 1 0 9 5n 。而g a i l 和p 酞提出了在o ( 1 0 9 2 n ) 的时间只用n 6 l 0 9 6 n 个处理器的算法【1 7 1 。 ( 4 ) b r a d f o r d 等人提出一种基于动态规划的并行算法【18 1 。 首先将矩阵链相乘问题等三个问题转化为加括号最小花费问题，再将这一问 题转化为特殊的加权图的最短路径问题，然后运用最短路径算法解决矩阵链相乘 问题。通过对加权图的分析，文中提出三个基于p 黜w c r c w - c o m m o n 模型的 1 6 山东师范大学硕士学位论文 算法。第一个算法使用n6 1 0 盟个处理器和o ( 1 0 9 2n ) 的时间；第二个算法使用 i l l o 酉。印个处理器和o ( 1 0 酉。萨) 的时间，但是得到的只是一个近似最优解；第 三个算法用n l o 印个处理器解决矩阵链相乘问题，时间复杂度是o ( 1 0 9 3 ( n ) ) 。 ( 5 ) c z 啪画提出了一种基于凸多边形三角划分的并行算法【1 9 l ，在 p r a m c r e w 模型上使用n2 l 0 9 3 ( 1 1 ) 个处理器，时间复杂度是o ( 1 0 9 3n ) 。c 刁1 m 旬 还提卅存p r a m c r f w 模型上时间复杂度为o ( 1 6 9 n ) 和在p r a m c r c w 模型上时 闽复杂度为0 ( 1 0 苕。弘) 的两个算法【2 9 3 0 1 ，但是这两个算法只能求近似最优解 ( 6 ) r 锄趾a i l 提出一种用n 个处理器的算法【2 0 1 ，时间复杂度为o ( 1 0 9 4n ) 。 ( 7 ) s t e v ea s t r a t e 提出在超立方结构上解决矩阵链相乘问慰2 踟，这个算法 是以串行动态规划算法为基础的。 主要研究人员 年份 采川的模型 + 处理器个数时间复杂度 l 、h l i 锄t 一 1 9 8 3p r a m - 9 o 淹2 n i 。 n w r y 惭 1 9 8 8p r a m c r e w n 6 l o 印o ( 1 0 9 2n ) h u 觚g 加d l i i i 1 9 9 4p r a m o ( 1 0 9 2 n ) 6 ，t 5 n ，l o g n g a i la n d p a r k1 9 9 lp r a m n 6 l 0 9 6 n o ( 1 0 9 2n ) b r a d f i o r d1 9 9 4p r a m c r c w o m m o n 6 一 o ( 1 0 9 2n )n ，l o g n b m d f 0 柑 1 9 9 4 p r a m c r c w c o m m o n n l o 舀o g n o ( 1 0 9 l o 鲈) b r a d f 0 r d 1 9 9 4p r a m c r c w l c o m m o n n 3 l o 皿一o ( 1 0 9 3 n ) c z i l m a j 1 9 9 3 p r a m c l 也w n2 l o g3 ( n ) o ( 1 0 9 3n ) c z l 玎n 旬 1 9 9 6p r a m c l 汪w o ( 1 0 弘) c z u m a j 1 9 9 6p r a m c i t c w o ( 1 0 9 l o 龃) r a m a n a n1 9 9 2n o ( 1 0 9 4n ) s t e v ea s 仃a t e1 9 9 0 超立方结构 表3 2 解决m c o p 的并行算法研究进展 山东师范大学硕士学位论文 3 3m c s p 研究进展 h e e j ol e e 等首次提出了矩阵链相乘处理器调度问题( m c s p ) 【3 l 】，并指出 解决m c s p 的必要性。文中首先对矩阵链相乘处理器调度问题进行了形式化的描 述，并且证明这是一个n p h a r d 问题；然后提出了两个处理器调度算法，两对矩 阵乘积的离散处理器分配算法( d p a 算法) 和k 对矩阵乘积的离散处理器分配算 法( d p a k 算法) ，并在此基础上提出了一个解决矩阵链相乘处理器调度词题的 近似算法，其时恻复杂度为0 ( n 2 + n p ) 。 山东师范大学硕士学位论文 4 1 引言 第四章在二维网子l 结构上解决m c o p 的算法 许多学者已经提出了解决矩阵链乘序问题的并行算法，这些并行算法基本上 是在各种类型的p r a m 模型上实现的。p r a m 模型的优点是使用简单，将很多低级细 节均隐含于模型中，便于理论分析。缺点是不现实。一楣对于p r a m 模型，二维网孔 机器是一种分布存储的s i m d 结构，它是实际的，结构简单、规整易于扩展和v l s i 实现使得它不仅成为许多理论研究的基础模型，而旦还是许多并行机所采用的 互连结构，因此研究在二维网孔【3 9 】上的并行行算法更具有现实意义。 本章在串行动态规划算法的基础上，根据其内在的并行性，提出一种在二维 网孔互连的并行计算机系统上求解矩阵链相乘问题的算法，它的时间复杂度为 o ( n 。) ，为在实际的结构上解决矩阵链乘序问题又开辟了一条途径。 4 2 矩阵链相乘串行动态规划算法 4 2 1 矩阵链相乘串行动态规划算法描述 参见图4 1 ，由矩阵乘法的定义知，对于每一个f ，l f o ，则算法的运行时间正比于 罗罗争c = ! 鱼二丝2 智智智 6 ，因此，算法的时间复杂性为口( n3 ) ，这里c 表示 山东师范大学硕士学位论文 c 2 ，4 + c 5 ，5 + r 2 r 5 r 6 ，设它们的值分别为x ，y ，z 。如果x 是三个值中 的最小值，那么处理器p ( 2 ，5 ) 将两个处理器标号( 2 ，2 ，3 ，5 ) 保存到数组a 中，同时这两个标号也表示矩阵链m 2 m 3 m 4 m 5 加括号后成为m 2 ( m 3 m 4 m 5 ) ，然 后将x 作为c 2 ，5 的最终值，把c 2 ，5 向处理器p ( 1 ，5 ) 和处理器p ( 2 ，6 ) 广播， 即广播给行号小于2 的同列处理器p ( 1 ，5 ) 以及列号大于5 的同行处理器p ( 2 ，6 ) 。 而当d = 3 时与处理器p ( 2 ，5 ) 同时工作的还有p ( 1 ，4 ) ，p ( 3 ，6 ) ，共三个处理器。 d 二od 二ld _ 二2d = 3d = 4d = 5 i c l l ，1 c 1 2 c 1 ，3 c 【l 。4 c 1 ，5 c 1 ，6 i = l p ( 1 ，1 )p ( 1 ，2 )p ( 1 ，3 )p ( 1 ，4 )p ( 1 ，5 )p ( 1 ，6 ) c 2 ，2 c 2 ，3 c 2 ，4 c 2 ，5 c 2 ，6 i = 2 p ( 2 2 )p ( 2 ，3 )p ( 2 ，4 )p ( 2 ，5 )p ( 2 ，6 ) c 3 ，3 c 3 ，4 c 3 ，5 c 3 ，6 i = 3 p ( 3 。3 )! ) ( 3 。4 )p ( 3 ，b )p ( 3 ，6 ) c 4 ，4 ll 4 ，0 j c 4 ，6 i = 4 p ( 4 ，4 )p ( 4 ，5 )p ( 4 ，6 ) q 5 ，5 c 5 ，6 l = b p ( 5 ，5 )p ( 5 ，6 ) c 6 ，6 i _ 6 p ( 6 ，6 ) 图4 2 在二维网孔上求解八个矩阵相乘最优顺序的例子 4 3 4 算法描述 算法4 2 ：二维网孔上的并行算法 输入：每个处理器上均存有“n 输出：最少乘法次数c 1 ，p ( 1 ) f o ri = lt onp a r d o p ( i ，i ) 将c i ，i 赋值为o ，并将c i ，i 广播给同行同列的处理器 e n df o r ( 2 ) f o rd = lt on 一1 ( 2 1 )f o ri = 1t on dp a r d o c o 咖e n t ：n d 个处理器p ( i ，i + d ) 进行如下的计算( 其中j = i + d ) f o rk = i + 1t o j 山东师范大学硕士学位论文 c i ，j = m i n c i ，j ，c i ，k 1 + c k ，j 】+ r i r k r j + 1 i f ( c i ，k 1 + c k ，j + r i r k r j + 1 c i ，j ) t h e na 1 ，1 卜i a 1 ，2 卜k l a 2 。1 卜k a 2 ，2 卜j e n di f e n df o r e n d f o r ( 2 2 )f o ri = 1t on dp a r d o p ( i ，i + d ) 将计算出来的c 值同时广播给行号小于i 的同列处理器以及列号 大于n d 的同行处理器 e n df o r e n df o r 4