面向大数据中图搜索问题的流处理器实现与评测

摘要

随着计算机应用的发展，人们迎来了“大数据时代”。在大数据时代，应用所表现出的负载特性是访存局部性差，访存延迟大等。传统的通用微处理器处理这类应用往往性能不佳。这给微处理器结构设计带来了巨大挑战。通过深入研究大数据中图搜索问题的负载特点，本课题对适于处理图搜索问题的微处理器结构设计及优化展开研究。
　　本文针对图搜索问题访存局部性差的特点，引入流处理器设计思想，设计流式寄存器缓存结构，建立了“局部寄存器文件——流寄存器文件和片内共享存储——内存”三级存储层次框架GEM，GEM使得程序员能够通过软件方式显示地控制数据的局部性。
　　针对图搜索问题访存延迟大的特点，设计基于交叉多线程执行机制的处理器核心GE-Core。重点介绍了GE-Core流水线各阶段的结构和功能，以及算术逻辑运算部件ALU、访存部件LSU等核心部件的设计实现。
　　进一步，课题实现了流处理器原型平台。为验证该原型，本文设计了3种基于位图结构的并行BFS算法：基于位图结构的Top-dwon并行BFS算法、基于位图结构的Bottom-up并行BFS算法和基于位图结构的混合并行BFS算法。本文具体分析了3种算法的设计思想、搜索过程，并评估其性能。实验表明，基于位图结构的混合并行BFS算法性能最优。
　　最后，通过实验测试验证了流处理器原型系统的正确性，测试性能数据。从数据分析发现问题，对原型系统的部分硬件结构、操作机制进行优化和完善。从性能角度看，这些优化措施达到了预期的优化效果。

目录

声明

第一章 绪论

1.1 课题研究背景

1.2 相关研究工作

1.3 课题的研究内容与创新

1.4 论文结构

第二章 面向图搜索问题的流处理器存储层次GEM设计

2.1 问题提出

2.2 GEM框架设计

2.3 GEM接口设计

2.4 本章小结

第三章 面向图搜索问题的流处理器核心GE-Core设计

3.1 问题提出

3.2 GE-Core流水线

3.3 GE-Core流水线核心功能部件

3.4 本章小结

第四章 基于流处理器原型平台的并行BFS算法设计

4.1 问题描述

4.2 基于流处理器原型平台的并行BFS算法设计

4.3 性能评估

4.4 本章小结

第五章 系统级验证与软硬件协同优化

5.1 系统验证环境

5.2 验证方案与测试

5.3 软硬件协同优化

5.4 本章小结

第六章 结束语

6.1 工作总结

6.2 课题研究展望

致谢

参考文献

作者在学期间取得的学术成果