cache敏感的空间连接算法研究与实现word格式论文.docxVIP

ResearchandImplementationofCache-ConsciousJoinAlgorithminSpatialDatabaseCandidate：QiuXiaofengAdvisor：AssociateProf.ChenHongshengAdissertationSubmittedinpartialfulfillmentoftherequirementsforthedegreeofMasterofEngineeringinInformationandCommunicationEngineeringGraduateSchoolofNationalUniversityofDefenseTechnologyChangsha，Hunan，P.R.ChinaNovember，2011独创性声明本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论文作者签名:日期:c).J11 年(J 月J日学位论文版权使用授权书本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子(-文档，允许论文被查阅和借阅;可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。(必威体育官网网址学位论文在解密后适用本授权书。)日期:II年{/月。2日日期:以(I 年fl 月主日目录摘要iABSTRACTii第一章绪论11.1课题背景及意义11.2国内外研究现状31.2.1Cache 敏感算法的研究现状31.2.2空间连接算法研究现状41.3主要研究内容51.4论文组织结构6第二章Cache体系结构分析82.1计算机存储结构82.1.1存储器层次结构82.1.2多核处理器模型82.2Cache 性能评价92.2.1Cache 缺失92.2.2存储访问延迟102.2.3Cache优化的基本方法112.2.4理想高速缓存模型122.3局部性原理在Cache性能优化中的应用122.3.1局部性原理122.3.2局部性原理对Cache性能的影响132.3.3基于局部性原理的Cache性能优化132.4本章小结14第三章Cache敏感的空间连接算法153.1基于R树索引的空间连接算法153.1.1R树索引及其变体153.1.2空间连接算法处理流程173.2Cache 敏感的空间连接算法193.2.1空间索引结点压缩193.2.2量化压缩MBR 思想及算法设计203.3实验验证223.3.1算法执行时间及其组成233.3.2结点大小对算法性能的影响273.4本章小结29第四章空间连接算法并行优化及性能分析304.1并行编程模式分析304.1.1共享存储模式304.1.2消息传递模式304.1.3并行编程模式性能分析314.2基于OpenMP的空间连接并行算法设计324.2.1线程数对并行性能的影响324.2.2调度策略对并行性能的影响334.3实验验证354.3.1算法执行时间的并行化前后比较354.3.2并行化对空间连接算法性能的影响384.3.3线程数对并行算法性能的影响404.4本章小结425.3.1点数据集查询505.3.2线数据集查询535.3.3线面数据集查询545.4本章小结55第六章总结与展望576.1主要研究成果576.2未来工作58致谢59参考文献62攻读硕士学位期间取得的学术成果66攻读硕士学位期间参加的科研项目66表目录表2.1访问时间具体细分11表3.1实验具体硬件参数23图目录图1.1计算机存储器体系结构图2图2.1多核处理器流水线结构9图2.2理想高速缓存模型12图3.1 R 树实例15图3.2 一阶和二阶Hilbert 曲线16图3.3 Hilbert R树实例17图3.4空间查询处理流程18图3.5空间连接多步处理流程18图3.6 量化压缩MBR21图3.7基于四种索引的空间连接算法执行时间24图3.8 基于R 树的空间连接算法执行时间组成25图3.9 基于Hilbert R树的空间连接算法执行时间组成25图3.10基于Cache敏感R 树的空间连接算法执行时间组成25图3.11基于Cache敏感Hilbert R树的空间连接算法执行时间组成26图3.12算法执行时间随结点大小的变化27图3.13算法L1 Cache缺失延迟随结点大小的变化27图3.14算法L2 Cache缺失延迟随结点大小的变化28图3.15算法TLB缺失延迟随