资源描述：
《并行和分布式信息获取Parallel and Distributed .ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、8.并行和分布式信息检索ParallelandDistributedIR并行信息检索ParallelIR分布式信息检索DistributedIR1并行IR提纲简介回顾并行计算和并行程序性能的度量介绍在MIMD并行体系结构下实现倒排文件的基本方法结论2简介一方面，网络上地理位置分散的异构数字化信息的规模越来越大，导致标引和检索开销不断增加，检索响应时间越来越长。TheWWWcontainsover20billionspagesoftext,comprisingnearly100terabytesofdata另一
2、方面，尽管计算机软硬件技术发展迅速，但是对于大规模信息来说，单个CPU、单台计算机的处理能力仍然相对非常有限。因此，需要引入多个CPU、多台计算机进行“团队作战”--分布式并行计算！3并行计算(ParallelComputing)并行计算：用多个处理器去求解单个问题，把单个大问题分解成若干“部分”，每个“部分”采用单个处理器去解决。按照指令(Instruction)流和数据(Data)流的数目，Flynn将并行体系结构分成四类：SISD：单指令流单数据流，如传统的冯·诺依曼计算机。SIMD：单指令流多数据流，
3、N个处理器，N个数据流，但是多个处理器执行相同的操作。MISD：多指令流单数据流，N个处理器处理共享内存中的单数据流，每个处理器的操作不同，目前MISD结构已经非常少见。MIMD：多指令流多数据流，N个处理器，N个指令流和N个数据流，每个处理器都有自己的控制单元、处理单元和局部内存。多处理器可以处理不同任务或者协同处理单个任务。MIMD是目前最通用和最流行的一类并行体系结构。处理器之间交互(通信)频繁的MIMD系统称为紧耦合系统，反之称为松耦合系统。4并行程序性能度量（一）加速因子SpeedupAmdahl法
4、则：一个既定问题的最大加速率取决于该问题中只能顺序执行的部分所占的比率f，它与加速率之间的关系为其中，N是处理器的数量最佳顺序执行算法运行时间并行算法运行时间5并行程序性能度量（二）效率指标EfficiencyS是加速因子，N是处理器数量理想情况下，，即没有处理器闲置或进行着不必要的工作；实际中无法达到6并行IR算法的实现途径开发新的检索策略，并直接采用并行算法将现有的、研究较多的信息检索算法改造为并行算法7MIMD体系结构MIMD体系结构在如何定义和使用并行来解决问题上提供了很大的灵活性。Therearet
5、wowaysinwhicharetrievalsystemcanexploitaMIMDmachine:Parallelmultitasking并行多任务Partitionedparallelprocessing分割式并行处理8MIMD体系结构：并行多任务并行计算机中每个处理器运行一个分离的、独立的搜索引擎搜索引擎并不协同处理单个查询BrokerUserQueryResultUserQueryResultSearchEngineSearchEngineSearchEngineSearchEngineSearc
6、hEngine可提高系统的吞吐量，不能改变单个查询的响应时间简单，但需要对系统的硬件资源进行合理的权衡9MIMD体系结构：分割式并行处理将单个查询的计算划分为多个子任务，并分配给多个处理器执行将信息检索的计算分割归结为如何对数据进行分割中介器整合各处理器返回的查询结果BrokerUserQueryResultSubquery/ResultsSearchProcessSearchProcessSearchProcessSearchProcessSearchProcess10MIMD体系结构：数据分割方法按文档分
7、割（逻辑分割和物理分割）：N个文档分散在P个处理器上并行处理，每个并行进程处理针对N/P个文档的查询按词分割：t个索引项分散在P个处理器上并行处理，每个文档以及查询的处理是分布在多个处理器上的k1k2...ki...ktd1w1,1w2,1...wi,1...wt,1d2w1,2w2,2...wi,2...wt,2.....................djw1,jw2,j...wi,j...wt,j.....................dNw1,Nw2,N...wi,N...wt,NIndexingI
8、temsDocuments检索算法处理的基本数据元素11InvertedFiles:LogicalDocumentPartitioning数据划分从倒排索引数据结构上来说倒排索引与原单进程顺序处理没有区别。倒排索引能够支持并行进程直接访问各进程所管辖的那一部分文档对应的倒排索引部分。12ExtendeddictionaryentryfordocumentpartitioningitemiP1P2P3
