脑网络中关键节点计算的硬件加速技术研究

论文摘要

使用核磁共振成像（MRI）技术进行人脑网络分析是生物医学领域研究的新热点，研究人员将脑网络抽象成图，并通过分析图中关键节点来研究人脑网络的功能连接。随着脑网络研究的深入，脑网络分析的节点规模和样本数量均快速增长，运算速度成为了制约脑网络分析的主要瓶颈。在脑网络分析的计算过程中，最短路径和中介中心度是复杂度最高的两项计算，占据的时间最长，因此对这两种算法进行加速是必不可少的。本文针对最短路径和中介中心度，搭建了基于FPGA的硬件加速平台，提出相应的并行计算和流水线结构来实现高性能的硬件计算。首先，选择在稀疏图的应用背景下计算最短路径效率最高的广度优先（BFS）算法，对算法的性能和并行层次进行分析，提出了多计算单元的任务级并行系统架构，并用深度流水线结构实现了计算单元内部的数据级并行。其次，对传统的中介中心度快速算法进行分析，提出了基于BFS计算系统的前向计算加单独的后向计算单元的IP复用式系统结构，沿用了整个BFS计算系统，并对每一个BFS计算单元附加一个中介中心度计算单元实现中介中心度的计算。最后，在FPGA上完成了硬件系统的设计与验证，通过对比8核CPU系统的计算时间，对于随机生成图的BFS计算和中介中心度计算分别实现了3.16倍和3.61倍的硬件加速比。通过实验证明，利用硬件系统计算一个人脑网络的最短路径和中介中心度，实现了4.88倍和4.98倍的加速比。

论文目录

• 摘要
• Abstract
• 第1章 引言
• 1.1 基于功能磁共振成像的脑网络分析
• 1.2 利用硬件加速计算解决网络分析问题
• 1.3 本论文的主要研究内容及创新点
• 1.4 本论文的结构安排
• 第2章 最短路径算法分析与比较
• 2.1 图问题介绍
• 2.1.1 图问题的研究框架
• 2.1.2 网络的图表示
• 2.2 常用最短路径算法介绍
• 2.2.1 Floyd-Warshall 算法
• 2.2.2 Dijkstra 算法
• 2.2.3 BFS 算法
• 2.3 常用最短路径算法的性能比较
• 2.3.1 算法性能比较依据
• 2.3.2 Floyd-Warshall 算法的开销分析
• 2.3.3 Dijkstra 算法开销分析
• 2.3.4 BFS 算法开销分析
• 2.3.5 算法性能比较结果
• 2.4 本章小结
• 第3章 BFS 算法的硬件实现
• 3.1 算法分析和并行性分析
• 3.1.1 并行层次分析
• 3.1.2 算法运行时间分析
• 3.1.3 硬件实现思路
• 3.2 BFS 算法的硬件实现
• 3.2.1 图信息存储结构
• 3.2.2 计算单元设计
• 3.2.3 多计算单元并行架构
• 3.2.4 硬件计算性能
• 3.3 实验结果与分析
• 3.3.1 实验平台介绍
• 3.3.2 硬件资源占用
• 3.3.3 硬件加速比
• 3.3.4 扩展性分析
• 3.4 本章小结
• 第4章 中介中心度算法的分析与改进
• 4.1 中心度问题的描述
• 4.1.1 度中心度
• 4.1.2 紧密中心度
• 4.1.3 中介中心度
• 4.2 中介中心度快速算法的分析与改进
• 4.2.1 中介中心度快速算法
• 4.2.2 改进的中介中心度快速算法
• 4.3 改进算法效果分析
• 4.3.1 改进算法的计算误差分析
• 4.3.2 改进算法的计算时间分析
• 4.4 本章小结
• 第5章 中介中心度的硬件实现
• 5.1 算法分析&并行性分析
• 5.1.1 并行层次分析
• 5.1.2 算法运行时间分析
• 5.1.3 硬件实现思路
• 5.2 硬件实现
• 5.2.1 IP 复用思想下的系统总体结构
• 5.2.2 中介中心度计算单元设计
• 5.2.3 硬件计算性能分析
• 5.3 实验结果与分析
• 5.3.1 系统规模与资源占用
• 5.3.2 硬件加速比
• 5.3.3 扩展性分析
• 5.4 本章小结
• 第6章 基于硬件加速的脑网络分析
• 6.1 脑网络数据介绍
• 6.1.1 节点采样
• 6.1.2 相关计算
• 6.1.3 脑网络矩阵生成
• 6.2 实验结果与分析
• 6.2.1 实验方法
• 6.2.2 实验结果
• 6.2.3 扩展性分析
• 6.3 本章小结
• 第7章 总结与展望
• 7.1 本文的主要工作总结
• 7.2 展望
• 参考文献
• 致谢
• 个人简历、在学期间发表的学术论文与研究成果