2022年并行程序设计开题 .pdf
《2022年并行程序设计开题 .pdf》由会员分享,可在线阅读,更多相关《2022年并行程序设计开题 .pdf(4页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、并行程序设计开题报告院系:信息技术科学学院成员:王亚光2120100319 田金凤1120100119 题目:串匹配算法KPM 和矩阵运算的并行算法实现与分析名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页,共 4 页 - - - - - - - - - 1. 文献综述1.1 消息传递并行程序设计 (MPI)介绍(1) Massage Passing Interface:是消息传递函数库的标准规范,由 MPI 论坛开发,支持 Fortran和 C (2) 一种新的库描述,不是一
2、种语言。共有上百个函数调用接口,在Fortran和 C 语言中可以直接对这些函数进行调用(3) MPI 是一种标准或规范的代表,而不是特指某一个对它的具体实(4) MPI 是一种消息传递编程模型,并成为这种编程模型的代表和事实上的标准(5) 指用户必须通过显式地发送和接收消息来实现处理机间的数据交换。(6) 在这种并行编程中,每个并行进程均有自己独立的地址空间,相互之间访问不能直接进行,必须通过显式的消息传递来实现。(7) 这种编程方式是大规模并行处理机(MPP)和机群( Cluster)采用的主要编程方式。(8) 并行计算粒度大,特别适合于大规模可扩展并行算法,由于消息传递程序设计要求用户很
3、好地分解问题, 组织不同进程间的数据交换, 并行计算粒度大,特别适合于大规模可扩展并行算法。(9) 消息传递是当前并行计算领域的一个非常重要的并行程序设计方式。(10)高可移植性。MPI 已在 IBM PC 机上、MS Windows 上、所有主要的 Unix工作站上和所有主流的并行机上得到实现。使用MPI 作消息传递的 C 或 Fortran并行程序可不加改变地运行在IBM PC、MS Windows、Unix 工作站、以及各种并行机上。1.2 串匹配算法以字符序列形式出现而且不能将这些字符分成互相独立的关键字的一种数据称之为字符串( Strings) 。字符串十分重要、常用的一种操作是串匹
4、配(String Matching) 。串匹配分为字符串精确匹配(Exact String Matching)和字符串近似匹配(Approximate String Matching)两大类。字符串匹配技术在正文编辑、文本压缩、数据加密、数据挖掘、图像处理、模式识别、Internet 信息搜索、网络入侵检测、网络远程教学、 电子商务、生物信息学、 计算音乐等领域具有广泛的应用。而且串匹配是这些应用中最好时的核心问题,好的串匹配算法能显著的提高应用的效率。因此研究并设计快速的串匹配算法具有重要的理论价值和实际意义。串匹配问题实际上就是一种模式匹配问题,即在给定的文本串中找出与模式串匹配的子串的起
5、始位置。 本文对已有的基于分布存储系统上的并行的串匹配算法(KMP)进行了分析和实现,并与串行的算法进行了比较。KMP 算法首先是由 D.E. Knuth、J.H. Morris 以及 V.R. Pratt分别设计出来的, 所以该算法被命名为KMP 算法。 KMP 串匹配算法的基本思想是:对给出的文本串T1,n与模式串P1,m,假设在模式匹配的进程中,执行Ti 和 Pj的匹配检查。若Ti=Pj ,则继续检查 Ti+1 和 Pj+1是否匹配。若 Ti Pj,则分成两种情况:若j=1,则模式串右移一位,检查 Ti+1 和 P1是否匹配;若 1j=m, 则模式串右移 j-next(j)位,检查 Ti
6、 和 Pnext(j)是否匹配(其中next 是根据模式串 P1,m的本省局部匹配的信息构造而成的) 。重复此过程直到j=m 或 i=n 结束。1.3 矩阵求逆和矩阵相乘矩阵运算是数值计算中最重要的一类运算。特别是在线性代数和数值分析名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页,共 4 页 - - - - - - - - - 中,它是一种最基本的运算。 矩阵运算与并行结算及体系结构密切结合,并行计算模型上的有效并行算法包括矩阵转置算法,矩阵相乘算法, 矩阵和向量相乘以及方针
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2022年并行程序设计开题 2022 并行 程序设计 开题
限制150内