并行程序设计开题报告
院系：信息技术科学学院
成员：王亚光2120100319
田金凤1120100119
题目：串匹配算法KPM和矩阵运算的并行算法实现与分析
1.文献综述
1.1消息传递并行程序设计(MPI)介绍
(1)M assage P assing I nterface:是消息传递函数库的标准规范，由MPI论坛开发，支持Fortran和C
(2)一种新的库描述，不是一种语言。
共有上百个函数调用接口，在Fortran 和C语言中可以直接对这些函数进行调用
(3)MPI是一种标准或规范的代表，而不是特指某一个对它的具体实
(4)MPI是一种消息传递编程模型，并成为这种编程模型的代表和事实上的标准
(5)指用户必须通过显式地发送和接收消息来实现处理机间的数据交换。
(6)在这种并行编程中，每个并行进程均有自己独立的地址空间，相互之间访问不能直接进行，必须通过显式的消息传递来实现。
(7)这种编程方式是大规模并行处理机（MPP）和机群（Cluster）采用的主要编程方式。
(8)并行计算粒度大，特别适合于大规模可扩展并行算法，由于消息传递程序设计要求用户很好地分解问题，组织不同进程间的数据交换，并行计算粒度大，特别适合于大规模可扩展并行算法。
(9)消息传递是当前并行计算领域的一个非常重要的并行程序设计方式。
(10)高可移植性。
MPI已在IBM PC机上、MS Windows上、所有主要的Unix 工作站上和所有主流的并行机上得到实现。
使用MPI作消息传递的C或Fortran 并行程序可不加改变地运行在IBM PC、MS Windows、Unix工作站、以及各种并行机上。
1.2串匹配算法
以字符序列形式出现而且不能将这些字符分成互相独立的关键字的一种数据称之为字符串（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]是否匹配；若1<j<=m，则模式串右移j-next(j)位，检查T[i]和P[next(j)]是否匹配（其中next是根据模式串P[1,m]的本省局部匹配的信息构造而成的）。
重复此过程直到j=m或i=n结束。
1.3矩阵求逆和矩阵相乘
矩阵运算是数值计算中最重要的一类运算。
特别是在线性代数和数值分析
中，它是一种最基本的运算。
矩阵运算与并行结算及体系结构密切结合，并行计算模型上的有效并行算法包括矩阵转置算法，矩阵相乘算法，矩阵和向量相乘以及方针的LU分解、求逆和求解三角形线性系。
本文给出了矩阵相乘和矩阵求逆算法的并行实现，基于分块的思想实现并行。
2.本课题要研究解决的问题和拟采用的研究手段：
2.1本课题要求
最低要求：对已有算法（不能是课堂已经详细讲解的算法，应该是课外内容）进行实现，性能分析。
最好能在已有的算法基础上，有所创新，哪怕是一点细节的改进。
鼓励大家结合各自实验室的研究方向，利用并行算法、并行程序设计知识解决研究中遇到的问题。
如无法与实验室研究工作相结合，可考虑一些经典算法。
要求如下：
也要提交阅读文献列表，研究报告中应明确指出哪些是前人的工作，哪些是自己的新成果。
研究报告应详细描述所研究的问题，算法设计。
提交源码（应有充分的注释）、实验报告（详细的性能测试结果和分析）。
2.2本课题要研究或解决的问题
（1）非数值并行算法中的串匹配算法KMP算法设计
（2）数值并行算法中的矩阵求逆和相乘设计
（3）给出KMP算法的串行程序和并行程序
（4）给出矩阵求逆和相乘算法的串行程序和并行程序
（5）对以上两种算法进行相应的改进，并给出具体的实现
（6）对结果进行分析比较，给出结论
2.3本课题拟采用的方案
本课题采用基于消息传递库标准MPI和C语言，对KMP算法和矩阵求逆和相乘进行实现，并对算法做出相应的修改，分析算法的时间复杂度，分别给出串行和并行的实现，通过对不同算法的执行时间进行比较，给出最后的结论。
参考文献
•黄铠,徐志伟著,陆鑫达等译. 可扩展并行计算技术,结构与编程. 北京:机械工业出版社, P.33~56,P.227~237, 2000.
•陈国良著.并行计算—结构、算法、编程. 北京:高等教育出版社,1999. •Barry Wilkinson and Michael Allen. Parallel Programming(Techniques and Applications using Networked Workstations and Parallel Computers). Prentice Hall, 1999.
•李晓梅,莫则尧等著. 可扩展并行算法的设计与分析. 北京:国防工业出版社,2000.
•张宝琳,谷同祥等著. 数值并行计算原理与方法. 北京:国防工业出版社,1999. 都志辉著. 高性能计算并行编程技术—MPI并行程序设计. 北京:清华大学出版社, 2001.
•Knuth D E, Morris J H, Pratt V R. Fast pattern matching in strings. SIAM Journal of Computing, 1997, 6(2):323~350.
•Chen Guo-liang. Design and Analysis of Parallel Algorithm. Beijing: Higher Education Press, 1994.
•/mpi
•Boyer R S, Moore J S. A Fast String Searching Algorithm[J]. Communications of the ACM. 1977,20(10):762-772
•Sunday D M. A Very Fast Substring Search Algorithm[J]. Communications of ACM, 1990, 33(8):132-142.
•王威，刘金刚. 一种改进的字符串匹配算法[J]. 计算机工程. 2006, 32(2). •陈晶.黄曙光. 分布式并行矩阵乘算法分析[J]. -兵工自动化2005(5).
•赵一瑾. 一个改进的BM串匹配算法[J]. 计算机研究与发展. 1998, 35(1):45-48
•张学波，李晓梅. 分布式环境下几种矩阵乘并行算法分析与比较[j]. 装备指挥技术学院学报. 2003,14(2).
•吴建平.迟学斌分布式系统上并行矩阵乘法[J]. 计算数学, 1999 (01).
•莫则尧.袁国兴消息传递并行编程环境MPI . 2001。