基于多核并行的全文检索动态后继树模型相关算法研究

摘要

随着多核处理器的快速普及，广大的程序开发者们面临着极大的机遇与挑战。在过去，由于缺乏并行开发的环境，大多数的开发者们通常只能在单核单线程的平台上进行程序开发，所以在大多数情况下是不会考虑程序的并发执行问题。但是，随着时间的推移，可以预见单核处理器在不久即将淡出人们的生活，多核处理器在近年来取得极大发展和普及，大多数开发者们都拥有了多核开发环境，在进行程序开发的时候，如果再不考虑程序的并行执行相关问题，将不能发挥多核平台拥有多线程并行执行能力的特点，不能进一步的提高程序的运行效率。
　　 除此之外，伴随着互联网普及速度的进一步加快，搜索引擎成为了互联网上最受欢迎的应用之一，而搜索引擎就是全文检索系统的一个常见应用。伴随着多核平台的普及以及硬件价格的下降，建立适用于行业特色的检索系统将不再是一件遥不可及的事情。而过去对于全文检索索引模型的研究主要是通过对于索引结构的修改来提高索引的性能，而本文则希望通过另一种思路，通过对全文检索系统中动态后继树索引模型相关算法进行基于多核平台的并行化改进，从而提高索引生成以及检索的效率，本文主要从事了以下工作:
　　 1、研究多核处理器的主要特点以及在进行多核编程的时候会遇到的问题;比较了多核平台并行运算与传统的多机分布式并行运算的不同，以此来作为进行算法并行化研究的指导。
　　 2、分析研究全文检索系统中不同的索引结构及特点，并与动态后继树索引进行比较，从生成速度、检索效率以及更新的复杂度等角度出发，选择了动态后继树索引进行算法的相关研究。
　　 3、结合多核编程的特点，研究了动态后继树索引创建算法的任务分配方法，在每个线程拥有各自私有内存空间的基础上，通过任务分配管理分配不同的对象，让每个并行线程都能以最合理的工作方式工作，最大程度发挥程序的并行性能。通过在原始索引结构创建算法的基础上，加入OpenMP指导语句以实现程序的并行化
　　 4、分析了动态后继树的检索算法的特点，在多分词查找算法中加入OpenMP指导语句，研究了更适合多核平台的检索算法。
　　 5、通过对动态后继树原始创建算法与修改后的并行创建算法以及动态后继树多分词查找原始算法与多分词并行查找算法的实验结果进行比较，证明经过了并行化处理的算法，在多核平台上的运行效率有显著提升。

目录

声明

摘要

第一章 引言

1．1 研究背景

1．2 研究内容

1．3 论文结构

第二章 基础知识研究

2．1 多核平台介绍

2．2 多核编程会遇到的问题

2．2．1 并发问题

2．2．2 饥饿问题

2．2．3 任务分解和调度的问题

2．3 多核并行编程与多机分布式并行编程的区别

2．4 OpenMP

2．5 全文检索系统介绍

2．6 全文检索系统常用的索引模型

2．6．1 签名文件

2．6．2 倒排文件

2．6．3 位图

2．6．4 Pat树和Pat数组

2．6．5 互关联后继树

2．7 本章小节

第三章 全文检索系统和动态后继树并行算法研究

3．1 动态后继树模型

3．2 动态后继树索引的并行创建算法

3．2．1 索引的创建算法

3．2．2 并行索引创建算法设计

3．3 索引查找算法

3．3．1 索引查找原始算法

3．3．2 多分词查找算法设计

3．3．3 并行查找算法模块

3．4 实验结果及分析

3．5 小节

第四章 总结与展望

4．1 全文总结

4．2 下一步工作

参考文献

致谢

攻读硕士学位期间已发表、录用的论文及参与的科研项目