（计算机软件与理论专业论文）基于mpi的分布式搜索引擎系统研究.pdf

摘要 摘要 伴随着互联网的普及和网络信息的爆炸式增长，人们查阅资料己不是依靠有限范围 内的网站来寻找，而是依靠搜索引擎对信息海洋中的海量数据进行访问了。搜索引擎技 术已经成为互联网发展必不可少的核心技术，它的作用越来越重要。然而现有的搜索引 擎大多是集中式的，已经不能很好地适应网络的进一步发展，分布式技术是下一代搜索 引擎的发展趋势。 本文在分析传统搜索引擎技术不足的基础上，提出一种基于m p i ( m e s s a g ep a s s i n g i n t e r f a c e ) 的分布式搜索引擎系统。该系统主要由并行网页抓取和分布式建立索引两部分 组成。首先，详细介绍了网页并行抓取的设计和实现，包括它的系统框架、主要模块、 运行流程和u r l 调度算法。u r l 调度算法采用散列计算，不仅实现了负载平衡，而且 在一定程度上避免了冲突。然后，通过分析索引数据库在搜索引擎时效性及有效性方面 的重要作用，提出一种多进程并行分词建立索引的方法。该方法以中文网页数据库为基 本语料库，采用正向最大匹配法进行中文分词，并用一种高效的倒排索引方式存储索引 表。这种方法能够加快索引建立与更新的速度，并且在空间效率上也有较大的提高。 分布式中文搜索引擎架设在基于m p i 的分布式网络结构之上，利用m p i 良好的分 布式特性，使搜索引擎从集中式走向分布式。采用静态和动态相结合的任务分配策略， 提高了时间和空间效率并使系统易于扩展，实现了网页快速抓取和索引的建立与更新。 该搜索引擎能更深度、更广度地搜索互联网上用户可用的信息，更准确、更迅速的返回 用户查询结果。 关键词：搜索引擎，分布式，网页抓取，中文分词，倒排索引，负载平衡 a b s t r a c t a b s t r a c t w i t ht h ep o p u l a r i z a t i o no fi n t e r n e ta n dr a p i di n c r e a s eo fi n f o r m a t i o n ，p e o p l ed on o t s e a r c ht h ei n f o r m a t i o nb ys e v e r a lw e b s i t e sa n ym o r e ，t h e r e f o r em e yu s es e a r c he n g i n et o m a t c ht h e i rn e e d s s e a r c he n g i n et e c h n o l o g yh a sb e c o m eo n eo ft h ec o r et e c h n o l o g i e sf o r i n t e r a c td e v e l o p m e n t ，a n di tb e c o m e sm o r ea n dm o r ei m p o r t a n t c u r r e n ts e a r c he n g i n e sa r e c e n t r a l i z e di nc o m p u t i n ga n dd o n ta d a p tt ot h ef u r t h e rd e v e l o p m e n to fi n t e r n e t d i s t r i b u t e d t e c h n o l o g yi st h ed e v e l o p m e n tt r e n do ft h en e x tg e n e r a t i o ns e a r c he n g i n e t h i sp a p e r a n a l y z e st h es h o r t c o m i n g si nt h et r a d i t i o n a ls e a r c he n g i n e sa n db r i n g s f o r w a r das e a r c he n g i n eu s i n gd i s t r i b u t e dt e c h n o l o g y t h es y s t e mc o n s i s t so fp a r a l l e lw e bc r a w l e ra n dd i s t r i b u t e di n d e x i n g f i r s t ，ah i g h p e r f o r m a n c ep a r a l l e lc r a w l e ri si n t r o d u c e di nd e t a i l ，i n c l u d i n gi t so v e r a l la r c h i t e c t u r e ，m a j o r c o m p o n e n t sa n dw o r k i n gp r o c e s s t h eu r ls c h e d u l i n ga l g o r i t h mu s i n gh a s h i n gn o to n l y r e a l i z e sl o a db a l a n c e , b u ta l s oa v o i d sc o l l i s i o n t h e n , an e wi n d e xa p p r o a c hi sp r e s e n t e dw h i c h c a r r i e so u tc h i n e s ew o r ds e g m e n t a t i o n sb ym u l t i p l ep r o c e s s i n g c o n c u r r e n t l yb a s e do n a n a l y s i n gt h ei m p o r t a n c eo ft h ei n d e x e ri n r e a l t i m ea n de f f e c t i v e n e s so ft h es e a r c h e n g i n e t h em a x i m u mm a t c h i n gm e t h o di su s e dt oc r e a t ei n d e xd a t ao fc h i n e s ew e bp a g e sa n d t h ei n v e r t e di n d e xt a b l ei sc a r r i e dt os t o r ei n d e xd a t a t h i sm e t h o da c c e l e r a t e st h es p e e do ft h e i n d e x i n ga n du p d a t i n g ，a sw e l la st h ee f f i c i e n c yi ns p a c ei se n h a n c e d t h em p i b a s e dd i s t r i b u t e dc h i n e s es e a r e he n g i n ec o n s t r u c t ss e a r c h e n g i n eo nm p i d i s t r i b u t e dn e t w o ks t r u c t u r e ，a n dm a k e su s eo fm p i sg o o dd i s t r i b u t e dt r a i tt op u ts e a r c h e n g i n et od e v e l o pf r o mc o n c e n t r a t i v es t r u c t u r et od i s t r i b u t e ds t r u c t u r e b yc o m b i n i n gt h es t a t i c a n dd y n a m i ct a s k si nt h ea l l o c a t i o ns t r a t e g y , t h ee f f i c i e n c yo ft i m ea n ds p a c ei si m p r o v e d t h e s y s t e mb e c o m e se a s yt oe x t e n da n dp v i d e st h eu s e a b l ei n f o r m a t i o nt ou s e r s s p e e d l ya n d w i d e l y k e y w o r d s ：s e a r c he n g i n e ，d i s t r i b u t e d ，c r a w l ，i n v e r t e di n d e x ，c h i n e s ew o r ds e g m e n t a t i o n ，l o a d b a l a n c i n g i i 独创性声明 本人声明所呈交的学位论文是苓人在导师指导下进行的研究工作及取 得的研究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含本人为获得江南 大学或其它教育机构的学位或证书而使用过的材料与我一同工作的同志 对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意 签 名：主迭望蠢璺 日 期：趁! 宰。f 至! 雏 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规定： 江南大学有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅，- j - 以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文， 并且本人电子文档的内容和纸质论文的内容相一致 保密的学位论文在解密后也遵守此规定 签 名：当磋游哮 导师签名：兰堑2 ：墨笙 、k 日 期：丝22 2 1 丝 第一章绪论 第一章绪论 1 1 论文选题的目的和意义 搜索引擎是指根据一定的策略、运用特定的计算机程序搜集互联网上的信息，对信 息进行组织和处理后，用户提供网页检索服务的系统。搜索引擎的核心是如何在可以接 受的时间范围内在用户需求和海量的数字化文档之间构造一个合理的、有效的匹配，也 就是信息定位问题。 然而随着数字化信息的发展，网络信息爆炸性增长，传统的集中式的搜索引擎对大 型数据资源的检索已经无法满足用户的需要。搜索引擎将搜集来的数据相对集中地存放 在特定的数据库中，当用户进行查询时，系统在数据库中进行统一检索，并将检索结果 返回给用户。这种集中式的体系结构在面对大信息量时有些不堪重负，况且随着网络信 息的进一步膨胀，系统维护的数据库变得非常庞大，对这样的数据库进行查询操作耗时 巨大，从而造成性能瓶颈。因此，分布式技术是下一代搜索引擎的发展趋势。 本文着眼于中型规模，力求实现具有高度系统灵活性和扩展性的并行网页抓取系统 和分布式建立索引系统。网页抓取时考虑节点之间的分布式并行。分布在一个局域网内 的多台节点机共同完成整个网络的遍历任务，彼此之间互不重复，并将下载的网页分布 存储。然后，各台节点机对已下载到本机的网页进行中文切词处理，分布式地建立一个 索引数据库，提高了搜索引擎的整体效率。 1 2 本文主要内容和工作 本文针对网页抓取和索引建立，在基于m p i ( 消息传递接口) 并行环境下，开发出 了一个完整的网页并行抓取和分布式索引建立系统。系统能够部署在多台计算机上，各 台计算机能够同时运行抓取网页和建立索引文件的功能，各节点也能提供搜索功能，完 成对本地存储器中索引文件的搜索。运行搜索端的机器，能够向这些节点搜索需要的信 息。本文同时也对相关技术做了深入的探讨。该系统能够跨平台使用，是一个灵活而又 快速的分布式搜索引擎。 本文主要分为五章，各部分主要内容如下： 第一章，主要介绍了论文的研究背景，阐述了研究的目的和意义。 第二章，对集群系统和m p i 技术做了简要介绍，叙述了m p i 的特点和优势，对基 于m p i 的并行计算环境进行测试。 第三章，详细介绍了搜索引擎主要组成部分和工作原理，在分析集中式搜索引擎不 足的基础上提出了一种分布式搜索引擎。设计了分布式搜索引擎框架，并叙述了其优势。 第四章，主要论述了并行抓取网页的必要性和可行性，提出一种并行抓取方案。采 用散列的方法分配u r l ，取得较好的负载平衡。 第五章，提出一种分布式建立索引方法，采用基于词典的中文分词和倒排索引存储分 词结果。采用一种集中式动态负载平衡策略，提高并行计算效率。 江南大学硕士学位论文 第二章m p i 并行程序设计 2 1 集群系统 2 1 1 集群概述 集群( 一组协同工作的计算机) 是充分利用计算资源的一个重要概念，节点间通过高 速网络连接协同工作，表现成一个单一的、集中的计算资源供并行计算使用。集群系统 的处理能力可与专用计算机( 小型机、大型机) 相比，而性价比却高于专用计算机，不但 易于构架，而且具有良好的可扩展性。根据不同的标准，常见的集群分类有以下几种【4 1 ： 1 高性能集群 这种集群可以包含上千个p c 机或工作站，使用高速的网络设备，提供接近甚至超 过传统超级计算机的计算能力。在对时间有较高要求的情况下，被用来运行并行程序，同 时处理复杂的计算问题。所以高性能集群在科学领域中比较受欢迎，科学家们通常会想 在普通的硬件上以较少的时间运行仿真器和其它对运算能力有高要求的程序。 2 高可用性集群 高可用性集群的主要功能就是提供不间断的服务。最简单的情况是只有两个节点， 即保持活动的节点和保持等待并不断监视活动的节点，一旦活动节点崩溃，等待节点便立 即代替它，保证一个系统能在紧急情况下持续发挥作用。 3 负载平衡集群 该集群通常用在繁忙的网站服务器，具有一个中央控制节点，负责任务指派以及对其 余节点工作负载的监控，以得到快速的事务处理和响应能力。 集群的节点可以是工作站也可以是p c 机，本论文所建立的试验坏境为p c 机。另 外，分布式存储并行系统主要使用的是基于消息传递的编程。所谓消息传递就是指并行 执行的各部分通过消息传递来交换信息、控制执行。消息传递一般是面向分布式存储结 构，提供了灵活的控制手段和表达并行的方法，这也是消息传递并行程序能提供高的执 行效率的重要原因。 并行应用程序的开发是一个很复杂的任务。首先，在很大程度上依赖于可用软件工 具和环境；其次，并行程序开发中还会遇到一些未知问题，包括不确定性、通信、同步、 数据划分和分配、负载平衡、容错、异构、共享和分布存储、死锁等等。 并行程序的一个主要问题是移植现有串行程序还是开发新的并行程序。现有三种策 略用来开发并行应用程序：自动并行化、调用并行库和重新编译代码。其中调用并行库的 并行化方法( 如图2 1 ) 是最受欢迎的，也是目前开发并行应用程序最流行的方法。本文中 的算法都是采用调用并行库的方法。 2 1 2 集群系统优点 集群系统的优点主要表现在以下几个方面： 高性价比：集群系统的并行性降低了处理的瓶颈，提供了全面改进的性能，也就是 2 第二章m p i 并行程序设计 说，集群系统提供了更好的性能价格比。 资源共享：集群系统能有效地支持不同位置的用户对信息和资源( 硬件和软件) 的 共享。 灵活性和可扩展性：集群系统可以增量扩展，并能方便地修改或扩展系统以适应变 化的环境而无需中断其运行。 实用性和容错性：依靠存储单元和处理单元的多重性，集群系统具有在系统出现故 障的情况下继续运行的潜力。 可伸缩性：集群系统能容易地扩大以包括更多的资源( 硬件和软件) 。 并行程序 并行编程环境 串行应用 p v m 、m p i 集群中问件 ( 单系统映像和可用性低层结构) 操作系统 操作系统 操作系统 节点节点节点 【：二二：二二。声连戛隧圈。二。一。二捌 图2 - 1 并行化方法 f i g 2 1t h em e t h o do f p a r a l l e l i z a t i o n 2 2m p i 简介 2 2 1m p i 的定义 m p i ( m e s s a g ep a s s i n gi n t e r f a c e ) 是消息传递并行程序设计的标准之一。它实际上是一 个消息传递库的标准说明，吸取了众多消息传递系统的优点，是目前国际上最流行的并 行编程环境之一。 对于m p i 的定义，必须明确以下几点【习： m p i 是一个库而不是一门语言。 m p i 是一种标准或规范的代表，而不是特指某一个对它的具体实现。迄今为止，所有 的并行计算机制造商都提供对m p i 的支持，m p i 可以在不同的并行计算机上实现，一 个j 下确的m p i 程序，可以不加修改地在所有的并行机上运行。 m p i 是一种消息传递编程模型，并成为这种编程模型的代表和事实上的标准。m p i 虽然很庞大，但是它的最终目的还是为了服务于进程间通信。 m p i 提供了一种与语言和平台无关的编写消息传递程序的标准，用它来编写消息传 递程序不仅实用、可移植、高效、灵活，而且和当前已有的实现没有太大的变化。因此， 江南大学硕士学位论文 通过定义核心库的语法、语义，这将在大范围计算机上有效实现，将有益于广大用户， 这是m p i 产生的重要原因。 2 2 2m p i 的产生 1 9 9 2 年4 月2 9 日至3 0 日在威吉尼亚的威廉姆斯堡召开的分布存储环境中消息传递 标准的讨论会上，d o n g a r r a 、h e m p e l 、h e y 和w a l k e r 提出m p i 的初始草案。这个草案 于1 9 9 2 年1 1 月推出，并在1 9 9 3 年2 月完成了修订版，这就是m p l l 0 。为了促进m p i 的发展一个称为m p i 论坛的非官方组织应运而生，该论坛对m p i 的发展起了重要的作 用。 1 9 9 5 年6 月推出的m p i1 1 对原来的m p i 作了进一步的修改、完善和扩充。但是 当时推出m p i 标准时，为了能够使它尽快实现并迅速被接受，许多需要但实现起来比较 复杂的功能都没有定义，比如并行i o 。当m p i 被广泛接受之后，扩充并提高m p i 功能 的要求就越来越迫切了。 于是在1 9 9 7 年的7 月，推出了m p i 的扩充部分m p i 2 ，而把原来的m p i 各种版本 称为m p i 1 m p i 2 主要扩充三个方面：并行i o 、远程存储访问和动态进程管理。 此时m p i 可以实现以下功能： 设计一个应用编程接口( 不必为编译器或一个系统实现库) 。 允许有效的通信：避免存储器到存储器的拷贝，而允许计算和通信的重叠，尽可能 给通信协同处理器卸载。 对于接口允许方便的c 语言和f o r t r a n7 7 连接。 设定一个可靠的通信接口：用户不必处理通信失败。这些失败由基本的通信子系统 处理。 定义一个接口，它能在基本的通信和系统软件无重大改变时，在许多生产商的平台 上实现。接口的语义是独立于语言的。 2 2 3m p i 的基本组成函数 在m p i 1 中共有1 2 8 个调用接口，在m p i 2 中有2 8 7 个。m p i 比较庞大，完全掌握 这么多的调用是比较困难的。但是从理论上说m p i 所有的通信功能可以用它的6 个基本 的调用来实现。m p i 对参数 兑明的方式有三种分别是i no u t 和i n o u t 它们的含义分 别是： i n ( 输入) ：调用部分传递给m p i 的参数，m p i 除了使用该参数外不允许对这一参 数做任何修改。 o u t ( 输出) ：输出m p i 返回给调用部分的结果参数，该参数的初始值对m p i 没 有任何意义。 i n o u t ( 输入输出) ：输入输出调用部分首先将该参数传递给m p i ，m p i 对这一参 数引用、修改后，将结果返回给外部调用，该参数的初始值和返回结果都有意义。 如果某一个参数在调用前后没有改变，比如某个隐含对象的旬柄，但是该句柄指向 的对象被修改了，这一参数仍然被说明为o u t 或i n o u t 。m p i 的定义在最大范围内避 4 第二章m p i 并行程序设计 免i n o u t 参数的使用，因为这些使用易于出错，特别是对标量参数。 m p i 六个基本调用函数如下，可以实现所有的消息传递并行程序的功能。 m p i i n i t o m p i 初始化； m p i _ c o m m _ r a n k ( c , o m m ，r a n k )当前进程标 识： i ng o m m 该进程所在的通信域句柄； o u tr a n k 调用进程在c , o m m 中的标识号： m p i c o m m _ s i z e ( c o m m ，s i z e ) 数； i nc o m m 通信域句柄 o u ts i z e通信域c o m m 内包括的进程数整数 m p i _ s e n d ( b u f , c o u n t ，d a t a t y p e ，d e s t ，t a g ，c o m m ) i nb u f 发送缓冲区的起始地址( 可选类型) i nc o u n t将发送的数据的个数( 非负整数) i nd a t a t y p e 发送数据的数据类型( 句柄) i nd e s t 目的进程标识号( 整型) i nt a g 消息标志( 整型) i nc o m n l 通信域( 句柄) m p i r e c v ( b u f , c o u n t ，d a t a t y p e ，s o u r c e ，t a g ，c o m m ，s t a t u s ) o u tb u f接收缓冲区的起始地址( 可选数据类型) 通信域包含的进程 消息发送； 消息接收 i nc o u n t 最多可接收的数据的个数( 整型) i nd a t a t y p e 接收数据的数据类型( 句柄) i ns o u r c e接收数据的来源即发送数据的进程的进程标识号( 整型) i nt a g消息标识与相应的发送操作的表示相匹配相同( 整型) i nc o n r l l 本进程和发送进程所在的通信域( 句柄) o u ts t a t u s返回状态( 状态类型) m p i f i n a l i z e ( )m p i 结束 2 2 4m p i 通信分析 1 阻塞通信 在阻塞通信中，接收进程在接收消息时要求接收到的消息的消息信封和接收操作自 身的消息信封相一致，还要求它接收到的消息是最早发送给自己的消息。若两个消息的 消息信封都和自己的消息信封吻合则必须先接收首先发送的消息，即使后发送的消息首 先到达，该接收操作也必须等待第一个消息。 例如，进程0 先后发送两条消息给进程1 ，进程1 的第一个接收语句可以与任何一 个发送语句的消息相匹配，但是根据有序接收的语义约束，由进程0 发送的第一个消息 必须被进程l 的第一个接收语句接收，而由进程0 发送的第二个消息必须被进程1 的第 二个接收语句接收。即使进程0 的第二个消息先到达，进程l 的第一条接收语句也不能 5 江南大学硕士学位论文 接收它。 2 非阻塞通信 由于通信时间经常比较长，在阻塞通信还没有结束的时候处理机只能处于等待状 态，这样就浪费了处理机的计算资源。为了使计算与通信重叠，一种常见的技术就是非 阻塞通信。这种通信方式主要用于计算和通信的重叠，从而提高整个程序执行的效率。 此外，非阻塞通信还可以实现一些特殊的控制功能。 对于非阻塞通信，不必等到通信操作完全完成便可以返回。该通信操作可以交给特 定的通信硬件去完成，在该通信硬件完成该通信操作的同时处理机可以同时进行计算操 作，这样便实现了计算与通信的重叠。通过计算与通信的重叠可以大大提高程序执行的 效率这一方法和通过异步i o 实现i o 与计算的重叠思路是完全一样的。 2 3m p i 并行程序设计模式 在并行程序设计中，任务被划分为若干个子任务，并将它们分配到相应的计算节点上 执行。由于子任务之间需要进行通信，为了减少通信开支，保持负载平衡，可以根据具体 情况适当控制子任务的大小以提高程序效率。m p l 支持多种并行计算模型，其中最基本 的并行计算模式是主从模式和对等模式，绝大部分的m p i 的程序都是这两种模式之一或 二者的组合。 2 3 1 主从模式 主从模式又称为m a s t e r s l a v e 模式由一个单独执行控制程序的主进程( m a s t e r ) 和若 干个从进程( s l a v e r ) 组成。通常进程0 为主进程，负责任务的划分、分派、结果的收 集，以及所有进程间的协调和网络调度，并且在其它结点机调用s l a v e r 程序等。从进程负 责子任务的接收、计算和结果的发送。在这种模式下，一个程序由m a s t e r 程序和s l a v e r 程序两部分构成。主进程执行m a s t e r 程序，各子进程分别执行各自的s l a v e r 程序。主 进程通过消息传递通信函数完成与各子进程之间的数据传输。m a s t e r 和s l a v e r 程序各自 框架如图2 2 所示： 6 第二章m p i 并行程序设计 主进程 开始 上 数据初始化 l 打包待发送数据 声面 f 砝乎 厂占一 从进程 开始 。多 l 从主进程接收数据 图2 2 主从模式 f i g 2 - 2m a s t e r - s l a v em o d e 2 3 2 对等模式 对等模式又称为s p m d 模式，在这种模式的并行程序中，各个进程地位和功能相同， 所有进程执行同一个程序，只是各进程处理的对象和数据不同，控制和处理都在计算节 点上，各节点使用消息实现同步或异步通讯。对等模式程序基本框架如2 - 3 所示： 开始 上 是 、 否 确定足否为d 、， 上涛上 i 初始化发送 接收数据 缓冲区 山士 l 打包待发 躺包数据 送数据 士 一 i 广播数据i 一调嗣 算程序、 0 输出许。1 娃击 算结果 7 1 酾术 图2 - 3 对等模式 f i g 2 3p e e r - t o - p e e rm o d e 7 江南大学硕十学位论文 2 4m p i 的优点 m p i 的优点主要有【6 】： ( 1 ) m p i 的可移植性好，易于使用 m p i 是一种消息传递编程模型，并成为这种编程模型的代表和事实上的标准。消息 传递标准的定义给生产商提供了清晰定义的程序库，他们能有效地实现这些库或在某些 情况下为库程序提供硬件支持，因此加强了m p i 的可扩展性。 m p i 虽然很庞大，但是它最终还是服务于进程间通信，因此在m p i 上很容易移植 其它的并行代码。它是目前应用最广的、健壮的、扩展良好的标准并行消息传递平台， 几乎被所有并行计算环境( 共享和分布式存储并行机、m p p ) 和流行的多进程操作系统 ( u n i x 、w i n d o w s ) 所支持，能在m p p 与工作站机群上有效运行，具有最佳的可移植性。 m p i 标准有两个文档m p i 1 和m p i 2 。m p i 1 是m p i 消息服务内核，它提供了m p i 工进程间消息传递的抽象语义和机制，同时提供了一些对通常并行计算的有帮助的附加 特性。m p i 2 提供了m p i - 1 没有提供的功能扩展，如动态进程控制、单边消息传递( o n e s i d e dm e s s a g ep a s s i n g ) 和并行i o 等。 ( 2 ) m p i 有完备的异步通信 m p i 通信集的构造和管理能够在异步执行时保护用户的其它串行或并行进程不受 影响，有效地管理消息缓存区，能实现完全的异步通信。m p i 具有完备的异步通信接口， 使得进程间接收和发送消息能与计算重叠，能够满足m p m d 算法计算模式的要求。 、( 3 ) m p i 拓扑结构的优势 m p i 的虚拟拓扑反映了应用程序所申请的一组结点的通信模式，在m p p 上实现的 m p i 便可以利用这种信息来优化处理器间的通信路径。 2 5 并行计算环境性能评判标准 要评判并行环境计算性能的优劣就需要一定的标准。通用方法是记录在不同计算节 点个数的情况下运行程序的响应时间a ，计算程序运行的加速比印和并行效率印，用 这三个参数表示并行环境性能。 响应时间 计算机完成某一任务所花的全部时间就是响应时间，也称为周转时间。计算机性能 测量的一个主要标准是响应时间。其公式如下： a 2 t c + t i 0 ( 2 1 ) 上式中：厶是c p u 处理一个程序所消耗的时间，它包含操作系统和执行程序的时间 的开销，f ，d 是系统的输入输出时间。在并行计算环境中，不同节点间并行执行同一个 任务，数据需要在节点之间相互传递，决定程序效率的最大因素往往就是网络通信。合 理的分配任务，最大限度地降低通信开销， c p u 的利用率就可以得到大幅度提高，响 应时间自然就会降低【6 】。 加速比印和并行效率印 并行处理系统性能的主要评测指标就是加速比，用印表示，其计算公式如下： 8 第二章m p i 并行程序设计 j p2 吩印 ( 2 2 ) 其中：璐是指单处理机上某一个程序的执行时间；a p 是指在并行处理系统上，多个 处理机共同执行相同的程序所需要的时间。设p 为相同处理器的个数，在最理想的状态 下，加速的倍数可以为p 。但是在实际情况下，加速比品一般都要小于p f 们。 另外，定义并行效率印来反映并行的效率，其计算公式如下【6 】： 2 p ( 2 3 ) 算法的并行效率越高，印就越接近于1 。一般情况下印的取值范围是在( o ，1 ) 之间。 2 6m p c h 2 环境配置与测试 2 6 1m p i c h 2 安装与配置 本文实验环境是由8 台p c 机组成的一个小型集群系统，使用1 0 1 0 0 m 的交换机构 建的局域交换网络并使用t c p i p 网络协议通信，并用m p i 搭建并行计算平台啊。各台 主机配置如表l 所示。 表2 - 1 实验环境 t a b 2 - 1e x p e r i m e n t a le n v i r o n m e n t m p l 只是一个标准，提供各个函数的功能概述，并没有具体实现。m p i c h 就是在 符合m p i 标准的基础上具体实现m p i 的各个函数。它是当前最重要的m p i 实现，与 m p i 规范同步，每当m p i 推出新的版本就会有相应的m p i c h 的实现版本。m p i c h 广 泛应用于各种系统之上，支持并行及分布式程序设计。 m p i c h 2 是与m p i 2 相对应的m p i c h 实现版本，包含了m p i 2 相对于m p i 1 扩充 后的一些功能，如动态任务管理、并行i o 等。本文使用的版本是m p i c h 2 1 0 8 w i n i a 3 2 。 由于m p i c h 2 只是提供的m p i 的运行编译环境，而不是一个编译器，因此还要借助其 它的编译器。在w i n d o w s 系统中，最常用的c c + + 编译器就是v i s u a lc + + 6 0 所带的编 译器，它具有良好的用户界面，容易使用。 安装配置步骤如下： 第一步，以管理员身份登录每台计算机，建立一个用户名和密码都相同的账户，然 后分别在每台计算机上安装m p i c h 2 。安装完毕后，可以在任务管理器中查看是否有 m p d e x e 进程在运行，若有则安装成功。 第二步，将先前在每台计算机上建立的账号与密码注册到m p i c h 2 中，m p i c h 2 才 能在网络环境中访问每台主机。运行m p i c h l r n p d b i n k m p i r e g i s t e r e x e ，按提示输入用户 9 江南大学硕士学位论文 名和密码即完成。 第三步，将m p i c h 2 与v i s u a l e + + 6 0 集成。在编写m p i 并行程序时设置以下参数： 启动v i s u a l c + + 6 0 ，新建一个w i n 3 2 c o n s o l ea p p l i c a t i o n 工程； 打开工程 设置，选中c 卅选项卡，选中p r e p r o c e s s o r ，在p r e p r o c e s s o r 框中输入 h a v en ov a r i a b l er e t u r nt y p es u p p o r t 。在a d d i t i o n a li n c l u d ed i r e c t o r i e s 框 中输入c ：p r o g r a mf i l e s m p i c h 2 i n c l u d e ( m p i 安装目录) 。 选择l i n k 选项卡，选中i n p u t ，添加c x x 1 i b 和m p i 1 i b 到o b j e c t l i b r a r ym o d u l e s 框中， 添加c a p r o g r a mf i l e s l m p i c h 2 q i b ( m p i 安装目录) 到a d d i t i o n a ll i b r a r yp a t h 框中。 完成后点击o k 按钮，即完成配置，可以编写m p i + c c + + 并行程序。 2 6 2m p i c h 2 测试与分析 1 测试实验一 1 使用并行方式计算丌的值，令函数厂( 工) = 4 ( 1 + x 2 ) ，则j 6 厂( x ) 出= 万。这种方法是 利用在微小间隔内用求和运算近似积分运算。设n 值为【o ，1 】区间所分的间隔数，消息传 递的对象只涉及n 以及各个从节点计算得到的部分和，通信开销比较小，具有很好的可 并行性。并行时间复杂度为o ( n ) ，但比串行程序的数量级要小。根据每个进程的进程号， 将已划分的连续的数据块按照某种规律分配给各个进程。 本实验只测试4 台节点机，数据划分时每台节点机数据块首项各不相同，等差为4 ， n = 1 0 0 0 0 0 0 0 ，兀= 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 。表2 2 给出了在不同数量的处理机下的 实验结果： 表2 - 2 求值结果 t a b 2 - 2t h er e s u l t so fp 由于本程序计算量与通信量都较小、并行效率较高，影响算法的主要因素只是每个 节点的计算能力。本实验采用的连续数据块按首项不同的等差数列分配方法取得较好的 效果。 2 测试实验二 将一个文件中的若干个数据相加，结果存放于各个节点硬盘上的记事本文件中。处 理机个数为8 ，设总共有n 个数据( 本程序中取n = 1 0 0 0 0 ) 。本程序中根进程将n 个数据 广播给所有进程，各进程将部分计算结果汇集给根进程，共涉及两次消息传递。故总的 通信时间包括各个进程并行计算部分和的时间以及一次根进程对部分和求和的时间。由 此看来，本程序中通信时间在总的执行时间中占的比例相对较大。对通信延迟比较大的 工作站网络来说，多机处理的效率未必优于单机。在相同的条件下，程序运行结果如表 l o 第二章m p i 并行程序设计 2 3 所示： 表2 - 31 - 1 0 0 0 0 求和结果 t a b 2 - 3t h es u mr e s u l t so fl - 1 0 0 0 0 分析运算结果可知：对于通信量大计算量小的行程序，采用并行计算并不一定能加 快速度，有可会因为通信时间过大反而影响效率。 经过反复多次高负荷运算证明，基于m p i 的并行集群系统能提供运算速度快、系统 稳定、操作方便的并行计算服务。 2 7 小结 本章主要介绍了关于m p i 的一些基本概念，分析了m p i 并行计算的优点，并对 m p i c h 2 环境进行测试。 江南大学硕士学位论文 第三章分布式搜索引擎 在互联网发展初期，网站相对较少，信息查找比较容易。然而伴随互联网爆炸性的 发展，各种w e b 信息激增，用户要在海量的数据和异构的信息里查找所需要的信息， 犹如大海捞针。搜索引擎技术的出现，却解决了这一难题，它可以为用户提供信息检索 服务，为满足大众信息检索需求的专业搜索网站便应运而生。目前，搜索引擎技术正成 为计算机应用界和学术界争相研究、开发的对象。 3 1 搜索引擎简介 搜索引擎是根据一定的策略、运用特定的计算机程序搜集互联网上的信息，在对信 息进行分析、组织和处理后，通过用户接口界面，为用户提供检索服务的系统。通过使 用搜索引擎，人们检索信息的能力获得了极大的提高。 1 9 9 0 年，蒙特利尔大学学生a l a ne m t a g e 发明的a r c h i e 是现代搜索引擎的祖先， 它依靠脚本程序自动在网上搜索文件，然后对相关信息进行索引，提供给用户一定的表 达式查询，因此它的工作原理己经很接近现在的搜索引擎。1993 年美国内华达s y s t e m c o m p u t i n gs e r v i c e s 大学的m a t t h e wg r a y 开发了世界上第一个利用h t m l 网页之间的链 接关系来搜集网页的程序：w o r dw i d ew e bw a n d e r e r 。1 9 9 4 年，m i c h a e lm a u l d i n 将蜘 蛛程序接入到其索引程序中创建了第一个具有现代意义的搜索引擎l y c o s 。l y c o s 提 供了前缀匹配和字符相近限制，第一个在搜索结果中使用了网页自动摘要，现在已经可 以提供网站评论、图象及包括m p 3 在内的压缩音频文件下载链接等功能。1 9 9 8 年l o 月之前，g o o g l e 只是s t a n f o r d 大学的一个小项目b a e k r u b 。1 9 9 9 年2 月，g o o g l e 完成 了从a l p h a 版到b e a t 版的蜕变。g o o g l e 使用p a g e r a n k 技术检查整个网络链接结构，并 确定网页的重要性；然后进行超文本匹配分析，以确定网页与正在执行的特定搜索相关 程度；在多语言支持、用户界面等功能上的革新，再一次永远改变了搜索引擎的定义。 目前，g o o g l e 可以为用户能够访问一个包含超过8 0 亿个网址的索引。 随着互联网规模的急剧扩大，搜索引擎技术也在不断提高，搜索引擎已成为一个新 的研究、开发领域。目前就是要采用新兴的信息技术，包括分布式处理、数据库、数据 挖掘等，为用户提供更方便易用、更精确的搜索工具，来满足用户查询信息的需要。 3 2 搜索引擎工作原理 搜索引擎的实现过程【l o 】包括4 个部分：网页的抓取、索引的建立、索引的检索和用 户的查询，其处理流程见图3 1 。 1 2 第二章分布式搜索引擎 蜘蛛拄制一 u r l 数据库斗1 i + +蚓页抓耳_ c 器 u r l 提取j m 户 压蠢i 卜一链矗蕊取 蔓! 信息 i 童女夔i _ l - 日* l v j 固3 1 搜索 i 肇工作原理 f i g3 - lw o r k i n g p r i n c i p l e o f s e a r c he n g i n e 3 2 1 搜索器 搜索器的土要功能足从互联嘲上获舣m 页和链接结构信息。它要尽可能多、尽可能 快地搜集各种类型的最新网页信息，还要定期更新已经搜集过的旧信息以避免产牛死 链。q ：联网结构可以看做是一个以网页为节点，超链为边的有向图。因此，嘲页抓取的 运行可以拙象为个有向图的遍历过程。 3 2 2 索引器 索引器的丰要功能是分析收集的信息，建立索引库以供查询。首先，按照特定的中 文分1 日算法，对已经搜集获得的嘲页文本信息进行切词处理，汜求关键词、网页链接地 址等相关信息。然后，对已分析好的网页的抽象数据巾抽出索引项，o f 成索引表并以特 定的格式存储在索引数据库，供检索器榆索。 3 2 3 检索器 检索器接收查询接门传束的请求，根据查拗条件在索引库中快速检出满足条件的文 件，根据用户制定的约束条件，对将要输出的结果进行排序返回给查询接口以显示给 用户。 3 2 4 查询接口 查询接口的主要功能是输入用，、鸯询条件、显示查咖结果，它是搜索引警为用户提 供使用的入u 。为了充分适应人的思维方式，它还提供用户相关性反馈机制，为用户提 了 江南大学硕士学位论文 供更高效、多样的信息。 3 3 搜索引擎的性能指标 3 3 1 索引建立的方法 索引器在建立索引表时一般都是按照倒排文档的格式存放，然而不同的搜索引擎她 们的索引选项是不同的。有些搜索引擎建立索引时只考虑网页文章的摘要部分或者是较 为重要的段落，而有些则对信息页面建立全文索引。还有些搜索引擎( 如g o o g l e ) 建立 索引时，会考虑到不同的超文本标记所表示的不同含义。例如粗体、大字体显示的内容 往往比较重要，放在锚链中的信息也经常概括了它所指向页面的信息。g o o g l e 、i n f o s e e k 还在建立索引的过程对页面进行分析处理，提取其中的u r l ，该网页信息之间的空间结 构就可以用这些超链接来反映，可以利用这些提高页面相关度判别时的精确度。索引的 结构是决定整个搜索引擎效率的最主要原因之一。 3 3 2 检索的功能 直接决定检索效果的好坏的原因就是搜索引擎所支持的检索功能的多少及其实现 的优劣。网络上信息资源是经常变化的，所以网络检索工具除了要支持基本的检索功能 如诸如邻近检索、字段检索等之外，更应该及时地应用新技术、新方法来提供高级检索 功能。搜索引擎检索的质量提高了，自然会得到用户的支持。 3 3 3 检索的效果 检索效果可以从响应时间、查全率、查准率、相关度等方面来衡量