基于BFS和FPGA-CPU的混合加速器设计
发布时间：2021-02-25 16:47
为了实现由软件和硬件执行小世界图搜索的加速器系统,提出了一种在单芯片FPGA-CPU异构硬件平台上基于广度优先搜索算法实现的混合加速器系统设计;提出了采用线性代数语言实现的BFS;提出了一种处理单元结构,它由一个负责与主存储器全部交互的后端、用于执行布尔塥运算的前端和一个距离生成器构成;在ZedBoard平台上设计了一种采用Xilinx Zynq Z7020 FPGA-CPU混合结构的实际加速器系统。实验结果表明,设计的混合加速器不仅能够实现小世界图的快速搜索,而且相比于目前其他先进的基于BFS算法的混合加速器结构有更好的加速性能。
【文章来源】：火力与指挥控制. 2019,44(10)北大核心
【文章页数】：6 页
【部分图文】：
稀疏xt的内存请求结构
痹げ獾腂FS步长时间对于FPGA更短时，就切换到FPGA执行。利用密集变量的可预测性来建模它的执行时钟周期如下：（1）式中，β是利用的带宽部分。FPGA继续执行直至前沿尺寸下降到低于全部图节点的θ%。之后，软件BFS接管直到搜索终止。β，θ凭经验确定。3实验结果为了评价本文提出的加速器系统，采用Graph500基准参数（A=0.57，B=0.19，C=0.19）［1，4］综合生成的RMAT图，把一个具有规模S（2S个节点）和边因子E（E×2s条边）的RMAT图称为RMAT-S-E。3.1软件BFS和基于BFS的稀疏和密集变量加速器性能比较图4RMAT-19-32上加速器和软件BFS每步执行时间先比较基于BFS的稀疏和密集变量加速器与BFS软件算法的性能。对于2种加速器变量，在有相等数目（4）的PE和时钟频率（100MHz）的RMAT-·98·1770
（总第44-）火力与指挥控制2019年第10期何时读取新的输入向量元素。一个为0的输入向量值意味着边来自于一个还未被访问过的节点，而且这个数据被简单地丢弃而无需进一步运算。加速器的控制和状态接口通过内存映射寄存器提供。虚线表示只在距离生成操作期间是激活的图2密集xt处理单元的体系结构2）稀疏x变量：根据整体架构，稀疏xt变量与密集xt变量是相同的，除了它不需要输入向量FIFO（因为稀疏处理意味着全部xt值是1）部分。图3所示为稀疏xt后端的内部结构，与密集xt变量本质上是不同的。稀疏输入向量是通过前沿滤波器内部生成，它扫描距离数组的值，并发送索引值，全部值被写入在先前的BFS步骤中。之后，每个生成索引的开始和结束指针被请求，这两个指针用于请求该节点的边数据，并生成前端的边计数信息。图3稀疏xt变量的后端结构3）失速y写入：为了保持加速器运行而无停顿，前端能够如后端生成数据一样快地消耗数据是很重要的，因此，可以抽取出前端的功能作为处理一个流写入到随机地址。如果结果向量被存储在DRAM中，则连接的写请求缓存器和存储控制器可能填满并暂停整个加速器。为了避免这种情况，解决方案是利用向量表示的稀疏性。由于本文的方法要求仅保留每个图节点的1位，故可以有效地利用片上RAM的双端口FPGA，在每个周期提供2个非常快的随机访问。4）距离生成器：在每个BFS步骤完成后，调用距离生成器来执行DistGen。这涉及到比较输入和结果向量，并找到从未被访问过的节点到访问过的节点。这些节点的索引被传递给后端作为实际写当前BFS距离到对应的存储位置，并为密集变量的下一个BFS步骤更新x向量。2.5一个实际加速器系统的构建本文构建的加速器系统采用XilinxZynqZ7020FPGA
【参考文献】：
博士论文
[1]面向异构体系结构的稀疏矩阵算法研究[D]. 邹丹.国防科学技术大学 2013
硕士论文
[1]EGPU处理单元的研究与设计[D]. 汪洋.山东大学 2016
[2]基于GPU/多核CPU平台下并行计算的实时超分辨和立体视图生成[D]. 孙增增.西安电子科技大学 2014
本文编号：3051261
【文章来源】：火力与指挥控制. 2019,44(10)北大核心
【文章页数】：6 页
【部分图文】：
稀疏xt的内存请求结构
痹げ獾腂FS步长时间对于FPGA更短时，就切换到FPGA执行。利用密集变量的可预测性来建模它的执行时钟周期如下：（1）式中，β是利用的带宽部分。FPGA继续执行直至前沿尺寸下降到低于全部图节点的θ%。之后，软件BFS接管直到搜索终止。β，θ凭经验确定。3实验结果为了评价本文提出的加速器系统，采用Graph500基准参数（A=0.57，B=0.19，C=0.19）［1，4］综合生成的RMAT图，把一个具有规模S（2S个节点）和边因子E（E×2s条边）的RMAT图称为RMAT-S-E。3.1软件BFS和基于BFS的稀疏和密集变量加速器性能比较图4RMAT-19-32上加速器和软件BFS每步执行时间先比较基于BFS的稀疏和密集变量加速器与BFS软件算法的性能。对于2种加速器变量，在有相等数目（4）的PE和时钟频率（100MHz）的RMAT-·98·1770
（总第44-）火力与指挥控制2019年第10期何时读取新的输入向量元素。一个为0的输入向量值意味着边来自于一个还未被访问过的节点，而且这个数据被简单地丢弃而无需进一步运算。加速器的控制和状态接口通过内存映射寄存器提供。虚线表示只在距离生成操作期间是激活的图2密集xt处理单元的体系结构2）稀疏x变量：根据整体架构，稀疏xt变量与密集xt变量是相同的，除了它不需要输入向量FIFO（因为稀疏处理意味着全部xt值是1）部分。图3所示为稀疏xt后端的内部结构，与密集xt变量本质上是不同的。稀疏输入向量是通过前沿滤波器内部生成，它扫描距离数组的值，并发送索引值，全部值被写入在先前的BFS步骤中。之后，每个生成索引的开始和结束指针被请求，这两个指针用于请求该节点的边数据，并生成前端的边计数信息。图3稀疏xt变量的后端结构3）失速y写入：为了保持加速器运行而无停顿，前端能够如后端生成数据一样快地消耗数据是很重要的，因此，可以抽取出前端的功能作为处理一个流写入到随机地址。如果结果向量被存储在DRAM中，则连接的写请求缓存器和存储控制器可能填满并暂停整个加速器。为了避免这种情况，解决方案是利用向量表示的稀疏性。由于本文的方法要求仅保留每个图节点的1位，故可以有效地利用片上RAM的双端口FPGA，在每个周期提供2个非常快的随机访问。4）距离生成器：在每个BFS步骤完成后，调用距离生成器来执行DistGen。这涉及到比较输入和结果向量，并找到从未被访问过的节点到访问过的节点。这些节点的索引被传递给后端作为实际写当前BFS距离到对应的存储位置，并为密集变量的下一个BFS步骤更新x向量。2.5一个实际加速器系统的构建本文构建的加速器系统采用XilinxZynqZ7020FPGA
【参考文献】：
博士论文
[1]面向异构体系结构的稀疏矩阵算法研究[D]. 邹丹.国防科学技术大学 2013
硕士论文
[1]EGPU处理单元的研究与设计[D]. 汪洋.山东大学 2016
[2]基于GPU/多核CPU平台下并行计算的实时超分辨和立体视图生成[D]. 孙增增.西安电子科技大学 2014
本文编号：3051261
本文链接：https://www.wllwen.com/kejilunwen/sousuoyinqinglunwen/3051261.html
