并行程序设计开题.docVIP

并行程序设计开题报告 院系：信息技术科学学院 成员：王亚光 2120100319 田金凤 1120100119 题目：串匹配算法KPM和矩阵运算的并行算法实现与分析Massage Passing Interface:是消息传递函数库的标准规范，由MPI论坛开发，支持Fortran和C 一种新的库描述，不是一种语言。共有上百个函数调用接口，在Fortran和C语言中可以直接对这些函数进行调用 MPI是一种标准或规范的代表，而不是特指某一个对它的具体实 MPI是一种消息传递编程模型，并成为这种编程模型的代表和事实上的标准 指用户必须通过显式地发送和接收消息来实现处理机间的数据交换。 在这种并行编程中，每个并行进程均有自己独立的地址空间，相互之间访问不能直接进行，必须通过显式的消息传递来实现。 这种编程方式是大规模并行处理机（MPP）和机群（Cluster）采用的主要编程方式。 并行计算粒度大，特别适合于大规模可扩展并行算法，由于消息传递程序设计要求用户很好地分解问题，组织不同进程间的数据交换，并行计算粒度大，特别适合于大规模可扩展并行算法。 消息传递是当前并行计算领域的一个非常重要的并行程序设计方式。 高可移植性。MPI已在IBM PC机上、MS Windows上、所有主要的Unix工作站上和所有主流的并行机上得到实现。使用MPI作消息传递的C或Fortran并行程序可不加改变地运行在IBM PC、MS Windows、Unix工作站、以及各种并行机上。 串匹配算法 以字符序列形式出现而且不能将这些字符分成互相独立的关键字的一种数据称之为字符串（Strings）。字符串十分重要、常用的一种操作是串匹配（String Matching）。串匹配分为字符串精确匹配（Exact String Matching）和字符串近似匹配(Approximate String Matching)两大类。字符串匹配技术在正文编辑、文本压缩、数据加密、数据挖掘、图像处理、模式识别、Internet信息有哪些信誉好的足球投注网站、网络入侵检测、网络远程教学、电子商务、生物信息学、计算音乐等领域具有广泛的应用。而且串匹配是这些应用中最好时的核心问题，好的串匹配算法能显著的提高应用的效率。因此研究并设计快速的串匹配算法具有重要的理论价值和实际意义。 串匹配问题实际上就是一种模式匹配问题，即在给定的文本串中找出与模式串匹配的子串的起始位置。本文对已有的基于分布存储系统上的并行的串匹配算法（KMP）进行了分析和实现，并与串行的算法进行了比较。KMP算法首先是由D.E. Knuth、J.H. Morris以及V.R. Pratt分别设计出来的，所以该算法被命名为KMP算法。KMP串匹配算法的基本思想是：对给出的文本串T[1,n]与模式串P[1,m]，假设在模式匹配的进程中，执行T[i]和P[j]的匹配检查。若T[i]=P[j]，则继续检查T[i+1]和P[j+1]是否匹配。若T[i]≠P[j]，则分成两种情况：若j=1，则模式串右移一位，检查T[i+1]和P[1]是否匹配；若1j=m，则模式串右移j-next(j)位，检查T[i]和P[next(j)]是否匹配（其中next是根据模式串P[1,m]的本省局部匹配的信息构造而成的）。重复此过程直到j=m或i=n结束。 矩阵求逆和矩阵相乘 矩阵运算是数值计算中最重要的一类运算。特别是在线性代数和数值分析中，它是一种最基本的运算。矩阵运算与并行结算及体系结构密切结合，并行计算模型上的有效并行算法包括矩阵转置算法，矩阵相乘算法，矩阵和向量相乘以及方针的LU分解、求逆和求解三角形线性系。本文给出了矩阵相乘和矩阵求逆算法的并行实现，基于分块的思想实现并行。 本课题要研究解决的问题和拟采用的研究手段： 本课题要求 最低要求：对已有算法（不能是课堂已经详细讲解的算法，应该是课外内容）进行实现，性能分析。最好能在已有的算法基础上，有所创新，哪怕是一点细节的改进。鼓励大家结合各自实验室的研究方向，利用并行算法、并行程序设计知识解决研究中遇到的问题。如无法与实验室研究工作相结合，可考虑一些经典算法。要求如下： 也要提交阅读文献列表，研究报告中应明确指出哪些是前人的工作，哪些是自己的新成果。研究报告应详细描述所研究的问题，算法设计。提交源码（应有充分的注释）、实验报告（详细的性能测试结果和分析）。本课题采用基于消息传递库标准MPI和C语言，对KMP算法和矩阵求逆和相乘进行实现，并对算法做出相应的修改，分别给出串行和并行的实现，通过对不同算法的执行时间进行比较，给出黄铠,徐志伟著,陆鑫达等译. 可扩展并行计算技术,结构与编程. 北京:机械工业出版社, P.33~56,P.227~237, 2000. 陈国良著.并行计算—结构