资源描述：
《并行算法及其应用前景》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、《计算机系统结构》大作业并行算法介绍及其应用前景专业计算机科学与技术指导教师蔡启先班级计081学号姓名R期2010。12。18广西工学院计算机工程系并行算法介绍及其应用前景【摘要】木论文根据作者的学习知识和相关的资料参考，首先根据并行算法列举了一个简单的并行算法的例子，再结合该例子进而介绍并行算法的基木原理，给并行算法下一个基木的定义，对并行算法进行了相关的介绍；接着根据目前并行算法的应用，提出了在计算机系统结构屮以并行算法为基础的一些并行程序设计的应用，比较了目前流行的并行程序设计的方法，并通过比较指出它
2、的不足以及并行程序设计在未來的发展趋势和前呆。通过本论文的介绍，能够给读者一些计算机系统结构并行算法方面的基础知识和并行程序结构设计的相关基础知识，为计算机系统的学习奠定一些基础。关键词：计算机系统结构并行算法并行程序设计引言并行计算机从70年代的开始，到80年代蓬勃发展和百家争鸣，再到90年代体系结构框架趋丁•统一,近年来英快速发展，并行机技术口趋成熟。首先是市场的需求，一直是推动并行计算机发展的主要动力，人暈实际应用部门，如天气预报、核武器、石汕勘探、地震数据处理、飞行器数值模拟以及其他人型事务处理等，
3、都需要每秒执行数I•万亿次乃至数百万亿此浮点运算的计算机，基于这些应川问题本身的限制，并行计算是满足它们的唯一可行途径。使用多计算机进行并行程序设计，它们Z间的通信是通过发送消息来完成的，所以消息传递需婆并行程序设计。并行程序设计使用多计算机或多个内部处理器的计算机来求解问题，它比使用单台计算机的计算速度要快得多。并行程序设计也为求解更人规模的问题提供了机会，前而所述问题需要更多的计算步或更大存储容量需求，并行程序设计以并行算法为核心，能满足这要求，因为多计算机和多处理机系统通常比单计算机有更大的总存储容量
4、。1并行算法的介绍l.1并行算法的应用一-并行矩阵乘积假定：基于A,B的不同划分，矩阵乘积的并行算法可分为行列划分，行行划分，列列划分，列行划分；m,1,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的计算是按对角线
5、进行的并行算法一:行列划分fori二0top-1j二(i+myid)modpCj二A*Bsrc二(myid+1)modpdest二(myid-1+p)modpif(i!=p-l)send(B,dest)recv(B,src)endifendfor本算法中,Cj=Cmyid,j,A=Amyid,B在处理器中每次循环向前移动一个处理器，即每次交换一个了矩阵数据块,共交换p-1次行列划分程序示例例:按行列划分并行计算矩阵乘积，其屮行行划分:A按行划分，B按行划分列列划分:A按列划分，B按列划分列行划分:A按列划分
6、，B按行划分列行划分以3X3分块为例:9个进程，进行三伦计算A,B的起始存放位置：A00A01A02A10AllA12A20A21A22B00B01B02B10BllB12B20B21B22第一轮:计算BOOB01B02A00A00A00A01A01A01AllAllAllA12A12A12A22A22A22A20A20A20BOOB01B02第三轮:计算BIOBllB12B20B21B22B20B21B22BOOB01B02Cannon算法示例BIOBllB12第二轮：计算A02A02A02BIOBllB
7、12A10A10A10B20B21B22A21A21A211.2并行算法的基本原理并行算法就是用多台处理机联合求解问题的方法和步骤，其执行过程是指将给定的问题首先分解成若干个尽量相互独立的了问题，然后使用多台计算机同时求解它，从而最终求得原问题的解。并行算法是并行计算屮一个非常重要的问题。并行算法的研究应该确立一个“理论一设计一实现一应川”的系统方法，形成一个完善的“架构一算法一编程”方法论，这样才能保证并行算法不断发展并变得更加实用。简单的说，算法就是求解问题的方法和步骤。并行算法，就是在并行机上用很多个
8、处理器联合求解问题的方法和步骤。并行计算(ParallelComputing)是指同时使用多种计算资源解决计算问题的过程。并行计算的主要冃的是快速解决大型且复杂的计算问题。此外还包括:利用非本地资源，节约成本一使用多个〃廉价〃计算资源取代大型计算机，同吋克服单个计算机上存在的存储器限制。传统地，串行计算是指在单个计算机(具冇单个中央处理单元)上执行软件写操作。CPU逐个使用一系列指令解决问题，但其中只冇一种指令可
