《并行算法及其应用前景》由会员分享，可在线阅读，更多相关《并行算法及其应用前景（7页珍藏版）》请在金锄头文库上搜索。
1、计算机系统结构大作业并行算法介绍及其应用前景并行算法介绍及其应用前景专 业 计算机科学与技术 指导教师 蔡启先 班 级 计 081 学 号 姓 名 日 期 2010。12。18 广西工学院计算机工程系并行算法介绍及其应用前景并行算法介绍及其应用前景【摘要摘要】 本论文根据作者的学习知识和相关的资料参考，首先根据并行算法列举了一个简单的并行算法的例子，再结合该例子进而介绍并行算法的基本原理，给并行算法下一个基本的定义，对并行算法进行了相关的介绍；接着根据目前并行算法的应用，提出了在计算机系统结构中以并行算法为基础的一些并行程序设计的应用，比较了目前流行的并行程序设计的方法，并通过比较指出它的不足
2、以及并行程序设计在未来的发展趋势和前景。通过本论文的介绍，能够给读者一些计算机系统结构并行算法方面的基础知识和并行程序结构设计的相关基础知识，为计算机系统的学习奠定一些基础。关键词：关键词：计算机系统结构 并行算法 并行程序设计引言引言并行计算机从 70 年代的开始，到 80 年代蓬勃发展和百家争鸣，再到 90 年代体系结构框架趋于统一，近年来其快速发展，并行机技术日趋成熟。首先是市场的需求，一直是推动并行计算机发展的主要动力，大量实际应用部门，如天气预报、核武器、石油勘探、地震数据处理、飞行器数值模拟以及其他大型事务处理等，都需要每秒执行数十万亿次乃至数百万亿此浮点运算的计算机，基于这些应用
3、问题本身的限制，并行计算是满足它们的唯一可行途径。使用多计算机进行并行程序设计，它们之间的通信是通过发送消息来完成的，所以消息传递需要并行程序设计。并行程序设计使用多计算机或多个内部处理器的计算机来求解问题，它比使用单台计算机的计算速度要快得多。并行程序设计也为求解更大规模的问题提供了机会，前面所述问题需要更多的计算步或更大存储容量需求，并行程序设计以并行算法为核心，能满足这要求，因为多计算机和多处理机系统通常比单计算机有更大的总存储容量。1 1 并行算法的介绍并行算法的介绍1.11.1 并行算法的应用并行算法的应用-并行矩阵乘积并行矩阵乘积假定: 基于 A,B 的不同划分,矩阵乘积的并行算法
4、可分为行列划分,行行划分,列列划分,列行划分；m, l, n 均能能 p 整除,其中 p 为进程个数。行列划分:A 按行划分, B 按列划分。令 C = (Cij),其中 Cij = AiBj 将 Ai, Bj 和 Cij ( j = 0, 1, ., p-1) 存放在第 i 个处理器中(这样的存储方式使得数据在处理器中不重复) Pi 负责计算 Cij ( j = 0, 1, ., p-1) 由于使用 p 个处理器,每次每个处理器只计算一个 Cij, 故计算出整个 C 需要 p 次完成Cij 的计算是按对角线进行的并行算法一:行列划分for i=0 to p-1 j=(i+myid) mod
5、pCj=A*Bsrc = (myid+1) mod pdest = (myid-1+p) mod pif (i!=p-1) send(B,dest)recv(B,src)end if end for本算法中,Cj = Cmyid, j , A = Amyid , B 在处理器中每次循环向前移动一个处理器,即每次交换一个子矩阵数据块,共交换 p-1 次行列划分程序示例例:按行列划分并行计算矩阵乘积,其中行行划分:A 按行划分, B 按行划分 列列划分:A 按列划分, B 按列划分列行划分:A 按列划分, B 按行划分列行划分 以 33 分块为例:9 个进程,进行三轮计算 A,B 的起始存放位置:
6、A00 A01 A02A10 A11 A12A20 A21 A22B00 B01 B02B10 B11 B12B20 B21 B22第一轮:计算A00 A00 A00A11 A11 A11A22 A22 A22B00 B01 B02B10 B11 B12B20 B21 B22Cannon 算法示例第二轮:计算B10 B11 B12B20 B21 B22B00 B01 B02A01 A01 A01A12 A12 A12A20 A20 A20第三轮:计算B20 B21 B22B00 B01 B02B10 B11 B12A02 A02 A02A10 A10 A10A21 A21 A211 12 2
7、并行算法的基本原理并行算法的基本原理并行算法就是用多台处理机联合求解问题的方法和步骤，其执行过程是指将给定的问题首先分解成若干个尽量相互独立的子问题，然后使用多台计算机同时求解它，从而最终求得原问题的解。并行算法是并行计算中一个非常重要的问题。并行算法的研究应该确立一个“理论设计实现应用”的系统方法，形成一个完善的 “架构算法编程” 方法论，这样才能保证并行算法不断发展并变得更加实用。简单的说，算法就是求解问题的方法和步骤。并行算法，就是在并行机上用很多个处理器联合求解问题的方法和步骤。并行计算(Parallel Computing)是指同时使用多种计算资源解决计算问题的过程。并行计算的主要目
8、的是快速解决大型且复杂的计算问题。此外还包括:利用非本地资源，节约成本 使用多个“廉价“计算资源取代大型计算机，同时克服单个计算机上存在的存储器限制。传统地，串行计算是指在单个计算机(具有单个中央处理单元)上执行软件写操作。CPU 逐个使用一系列指令解决问题，但其中只有一种指令可提供随时并及时的使用。并行计算是在串行计算的基础上演变而来，它努力仿真自然世界中的事务状态:一个序列中众多同时发生的，复杂且相关的事件。 并行计算的特点:将工作分离成离散部分，有助于同时解决；随时并及时地执行多个程序指令；多计算资源下解决问题的耗时要少于单个计算资源下的耗时。并行计算是相对于串行计算来说的，所谓并行计算
9、分为时间上的并行和空间上的并行。 时间上的并行就是指流水线技术，而空间上的并行则是指用多个处理器并发的执行计算。 并行计算机的分类：并行计算科学中主要研究的是空间上的并行问题。 空间上的并行导致了两类并行机的产生，按照 Flynn 的说法分为:单指令流多数据流(SIMD)和多指令流多数据流(MIMD)。我们常用的串行机也叫做单指令流单数据流(SISD)。并行计算机的存储结构：共享内存，分布式内存，混合型分布式共享内寸关注的问题:通信 同步 数据依赖 负载平衡 I/O并行计算的性能分析:加速比(speedup) 并行效率实际上，在自然界中并行是客观存在的普遍现象，关键问题在于能不能很好的利用。由
10、于人们的思维能力以及思考问题的方法对并行不太习惯，且并行算法理论不成熟，所以总是出现了需求再来研究算法，不具有导向性，同时实现并行算法的并行程序性能较差，往往满足不了人们的需求。并行算法的研究历史可简单归纳为：上世纪 70 到 80 年代，并行算法研究处于高潮；到上世纪 90 年代跌入低谷；目前，又处于研究的热点阶段。现在，人们已经可以自己搭建 PC cluster，利用学习到的理论知识来解决实际问题，不再是纸上谈兵，这也为我们提供了新的机遇和挑战。2 2 并行程序设计并行程序设计2.12.1 目前的相关并行程序设计目前的相关并行程序设计开发并行程序设计语言一般有三种方法：一是库函数法，除了串
11、行语言所包含的库函数外，一组新的支持并行性和交互操作的库函数(如 MPI 消息传递库和 POSIXPthreads 多线程库)引入到并行程序设计中；二是新语言结构法：采用某些新的语言结构来帮助并行程序设计以支持并行性和交互操作(如 Fortran 90 中的聚集数组操作)； 三是编译制导法：程序设计语言保持不变，但是将称之为编译制导的格式注释引入到并行程序中。当我们在实际的并行机上设计并行程序时，绝大部分均是采用扩展 Fortran 和 C语言的办法， 目前有的就是以上三种扩展办法。针对这三种不同方法开发的并行程序设计语言，一般相应地采用下述几种编译器实现方法来完成并行程序设计语言的编译处理:
12、设计新语言的编译器；利用通用编译器，加入预编译,使用通用编译器，链接并行函数(类)库；针对传统顺序程序，设计并行化编译系统。机群系统由于结点计算机一般都带有常用语言编译器，如 C 语言、Fortran 语言等，因此其并行程序设计语言的实现往往采用上述的后三种编译途径实现。2.1.1 新语言编译器新的并行程序设计语言是针对并行程序设计特点而开发的语言，比较著名的有 Occam 与 Ada 语言。它们都提出了一套崭新的语言文法，不仅包括并行任务、通信同步等的文法描述，还包括串行成分的文法描述，如类型、过程、函数等。对于新设计的语言，人们要设计相应的新语言编译器。2.1.2 预编译处理扩展传统语言实
13、现并行程序设计是并行系统开发人员常用的方法。通常采用的编译实现方法是在传统语言的编译器上设计预编译器。通过预编译，将扩展语言的并行成分用传统语言加以实现，再通过传统语言编译器编译生成可执行代码。在机群系统上利用结点计算机原有的编译器，采用预编译技术实现并行程序设计语言，既提供较强的并行性描述能力，又比较实用，有利于推广。作为扩展语言的基础语言常常是 Fortran、 C、 C+，如 Concurrent C 语言与 Thread C 语言。Concurrent C 是 AT&T 贝尔试验室的 Gehani 和 Roome 提出来的。2.1.3 并行函数与类库不改变传统语言，不改动编译器，而为程
14、序员提供并行程序开发所需的函数库或类库，在编译生成可执行代码时，再将其链接进来。这是并行程序设计中出现的一种新动向，比较著名的有 PVM 系统。清华大学在 PVM 的基础上实现了一个 C+语言的并行程序开发类库 mpc+，它提供并行进程、通信邮件等类函数，以提高用户程序开发效率，减少错误。2.1.4 并行化编译系统将用传统顺序语言编写的应用程序自动并行化是并行程序设计领域的一个重要问题。它不开发新的程序设计语言，而是设计新的编译系统，使传统的用顺序语言编写的应用程序经过编译处理就能并行执行。这种方法使用户能方便地将过去的串行应用系统移植到并行系统上，培训费用和重开发费大大降低。因此，它具有良好
15、的应用前景。2.22.2 并行程序设计的不足及原因并行程序设计的不足及原因由上述的并行程序设计方法中可以得知，设计一种新语言虽然有比较强的并行性描述能力，但是兼容性不好，不易推广，因此现在采用该方法的系统较少。对现有的顺序语言加以扩展，提供并行性描述机制，该方法具有兼容性好、编程简便等特点，现在常常被采用。不改变现有顺序语言，而由用户提供的函数库、类库或并行化编译系统等方法实现并行程序设计。该方法简单灵活，易于推广。目前并行程序设计的状况是:并行软件的发展落后于并行硬件；和串行系统的应用软件相比，现今的并行系统应用软件甚少且不成熟；并行软件的缺乏是发展并行计算的主要障碍；而且这种状态仍在继续。 其原因是:并行程序设计不但包含了串行程序设计，而且还包含了更多的富有挑战性的问题；串 行程序设计仅有一个普遍被接受的冯*诺依曼模型，而并行计算模型虽有好多，但没有一个被共同认可；并行程序设计对环境工具的要求远比串行程序设计先进得 多；串行程序设计比较适合于自然习惯，且人们在过去积累了大量的编程知识和宝贵的软件财富。至今并行算法范例不能被很好地理解和广泛地接受；并行程序设计是建立在不同的计算模型上的，而它们没有能像冯.诺依曼模型那样被普遍接受和认可。2.32.3 发展趋势及应用前景发展趋势及应用前景 随着时代的进步，我们需要不断调整研究方向。目前并行算法研究的新走向是：并
