面向海量数据图搜索问题的可扩展并行分布式协处理器系统

抽象的

互联网应用，如网络搜索、电子商务和现代医疗应用，产生和处理大量数据。在数据密集型应用程序的计算过程中存在着相当大的数据并行性。一种遍历算法，即广度优先搜索(BFS)，是许多图处理应用程序的基础，也是图规模增长时的指标。由于固有的不规则记忆访问模式造成的时间和空间局部性差，各种科学的编程方法被提出用于加速和并行化BFS。然而，新的并行硬件可以为科学方法提供更好的改进。为了解决小世界图问题，我们提出了一种可扩展的、新颖的基于现场可编程门阵列的异构多核科学编程系统。其核心是用于流处理的多线程。采用InfiniBand通信网络进行扩展。为了统一所有处理器地址，我们设计了一种基于地址映射的二值搜索算法。在经过1D并行混合BFS算法测试后，Graph500测试台允许的范围内，我们的8核8线程/核系统在相同并行度下取得了比之前工作更好的性能和效率。 Our system is efficient not as a special acceleration unit but as a processor platform that deals with graph searching applications.

1.介绍

信息技术，互联网和智能技术已迎来大数据时代。数据密集型应用程序，作为由图表搜索所代表的大数据应用的典型代表，已得到增加的关注[1］.许多真实世界的应用程序可以作为数百万个顶点的大图抽象，但此程序是处理的相当大的挑战。这些应用程序代表实体之间的连接，关系和互动，例如社交网络[2]，生物互动[3.]和地面运输[1］.差的数据驱动计算，非结构化组织，不规则内存访问和低计算到内存比是并行大图处理效率低下的主要原因[4］.要遍历由数据密集型应用引起的更大的图表，已经提出了各种科学编程方法[5，6］.Tithi等人[5]优化程序并使用英特尔单击++语言使用动态负载平衡。陈等。［6]提出了一种名为Codelet模型的新并行模型。他们都在加快对记忆的进步时做得很好。但是，新的并行计算机器可以为软件方法提供更好的平台。异构处理，具有可重新配置的逻辑和现场可编程门阵列（FPGA）作为节能计算系统[7]，竞争性地与多核CPU和GPGPU进行竞争性[4，8］.广度优先搜索(BFS)在大型图上的性能取决于对高延迟外部内存的访问。因此，我们设计了相当可观的并行性和相对较低的时钟频率，以实现高性能和定制的内存架构，以处理不规则的内存访问模式。

处理图形搜索的瓶颈是内存。通信是处理器扩展的主要时间开销。在本研究中，我们提出了一种用于大数据应用的可扩展和基于FPGA的异构多核系统。核心是用于流式传输处理的多线程，通信网络是InfiniBand（IB）以获得可伸缩性。地址映射是二进制搜索算法映射，存在三个级别的内存层次。

本文的其余部分组织如下：部分2详细介绍了我们的一维分解混合BFS算法。部分3.显示所提出的并行系统架构的细节。部分4描述二进制搜索地址映射的实现。部分5提供单处理器架构的详细信息。部分6展示三级内存层次结构。部分7分析实验结果。

2.相关工程

虽然具有数百万核的平行计算机已经在生产中，但趋势朝着更高的内存层次结构升高了更高的核心密度[10.]尽管其他节点资源（例如，每个核心的内存容量）也不按比例扩展[11.］.Anghel et al. (2014) [12.]分析了节点到节点的通信，表明应用程序运行时是通信绑定的，通信组成占每个BFS迭代执行时间的80% [13.］.

Traph500基准是基于图形的分析类应用程序的代表，旨在通过解决BFS图遍历问题来评估超级计算系统的性能[14.，15.］.

从一系列架构方法接近了快速图遍历。从一系列架构方法接近了快速图遍历。在通用CPU和多核/超级计算方法中[16.，17.， Agarwal等人在四套接字系统上执行局部性优化以减少内存流量[18.］.关于gpu上并行BFS实现的大量研究都集中在水平同步或定点方法上[19.，20.］.fpga簇上图遍历问题的可重构硬件方法受图大小和合成时间的限制[4，8］.betkaoui等。（2012）[4]和Attia等人。（2014）[8探索了高度并行化处理元素（PES）和解耦的计算存储器。Umuroglu等人。（2015）[11.]演示了处理BFS边界向量的密度，而不是稀疏性，从而为BFS生成更简单的内存访问模式，用冗余计算换取DRAM带宽利用率，并探索更快的图。

3. 1D测试的BFS算法

2013年，Beamer等人。［21.]提出了一种自底向上的算法，大大减少了检测边数，并将传统的自顶向下算法和一种新的自底向上算法相结合。该组合算法为水平同步并行BFS的并行计算提供了突破，并将这种自底向上的新算法应用于基于二维稀疏矩阵划分的求解。如今，2D自底向上的BFS实现是Blue Gene架构中的一个通用应用。

实验表明，在相对于一维分解的处理器数量较多的情况下，二维分解可以有效地减少处理器之间的总通信量。在二维分解中，BFS算法具有较好的性能。相比之下，在处理器数量较少的情况下，BFS算法适用于一维分解。此外，我们的系统有8个处理器并行执行统一的细粒度地址映射。算法1使用Yasui等人提出的1D分解优化的BFS算法。［22.］.在算法中1，是图形中的一组顶点，而为边的集合;也就是说, 方法和连接了。父母给出顶点的父结点在源顶点的bfs树中 ；当无法访问 ，父 ． ；如果在前线排队吗 ．给出了相同的含义(每个BFS迭代的下一个边界)和（什么时候 ，已经访问过）。大批 ， ，和存储为位图。搜索过程中出现一个新顶点;然后 ．当BFS当前迭代中没有新的顶点出现时，迭代结束。

4.大规模的并行协处理器系统架构

我们的大规模并行协处理器体系结构由单个主处理节点和用于特殊计算任务的大量协同处理节点组成。主处理节点是一个以ARM处理器为核心的嵌入式系统。我们系统的通信架构是IB通信网络。

协处理器是基于FPGA (Virtex-7)的开发板，FPGA是一种可重构的解决图问题的处理器。每块板上集成两块DDR3内存，通过内存控制器(MC)传输数据。我们修改了MC的IP核，使两个DDR3内存块可以并行访问。任何处理节点都可以通过I/O接口和目标通道适配器(target channel adapter, TCA)将任务分配给所有协处理器，目标通道适配器是我们基于IB协议实现的通信接口。来自TCA的通信数据通过IB协议通过发射器(TX)发送到IB交换机接口，来自IB交换机接口的通信数据由TCA通过接收器(RX)接收。最大理论线路速率为13.1 Gb/s，实际线路速率为10gb /s。我们有四条线;通信带宽为40gb /s。系统初始化时，主节点通过PCI-E总线将数据分发到各协处理器的DDR3内存中。系统启动后，各处理节点通过TCA接口的IB通信网络进行通信。 The program in the master node sends its instructions or data after address mapping (i.e., AM in Figure1)和每个协处理器在地址映射后进行通信。通过FPGA实现地址映射，该方案是每个节点的功能硬件单元。体系结构如图所示1．

其核心是一个使用多线程向量的流处理器。跨多线程是一种细粒度的多线程，其中线程交替执行。我们的大规模并行协处理器系统是一个可扩展的系统，是一个并行处理大数据应用的平台。

5.二进制搜索地址映射单元

我们地址映射的架构如图所示2．在我们的方案中，DDR3的内存被分为两个区域:局部数据块和全局翻译块。本地数据块存储程序从I/O请求和TCA中需要的数据。全局翻译块保存所有数据的映射。此外，每个节点中的全局翻译块是相同的，它们在一个细粒度页面中进行管理。

二分查找的基本思想是:以中间记录作为比较对象，按表的升序排列。如果给定项等于中间记录，则搜索完成。但是，如果给定的项小于中间记录，则在升序表的前半部分进行二分查找;否则，我们将在升序表的下半部分进行二分查找。

二进制搜索地址映射的实现是一个管道，其中虚拟地址为输入，输出数据为物理地址。我们将管道存储单元中的寄存器分为三组。第一组包含OMR、DVR和MTR寄存器，它们将数据的状态存储在RAM中。RAM存储访问数组的地址映射(BFS算法中的访问数组)。虚拟地址的输入是边界阵列(BFS算法中的边界阵列)。这种情况意味着我们无法在RAM中找到相应的映射，我们将从DDR3内存中获取边界数组的一个地址映射来存储在RAM中。这种情况是对象丢失(数组丢失)，即在二进制搜索的开始和第一个堆栈之后没有对象丢失，但数据丢失。数组中的虚地址范围将被输入到范围寄存器(RR)中。当输入地址不在每个RR的范围内时，会触发一个对象丢失的警告。然后，更新RR中的数据; the order of updating uses the least recently used mechanism. The pipeline then stalls, and we acquire one dataset in the frontier array to continue the search. One data item of the frontier array exists in the current stack of RAMs. Thus, when searching the next stack, the next data in RAMs are invalid. We would obtain the address mapping data of the Frontier array from the DDR3 memory to be stored in this RAMs, and the situation is that the data are missing. TheTh OMR是缺少的物体缺失指标在管道的堆栈。此外，MTR是数据缺失指示符。DVR中的1位指示当前堆叠的RAM中的64位数据。缺少对象时，DVR为0.在RAM中更新后，相应的位将设置为1。

第二组包含VAR和DVR，其是当流水线运行时将数据传递到下一个堆栈的临时存储。第三个包含LBR，RBR和汽车。在二进制搜索算法中，在每个搜索步骤中，较小的值在LBR中，较大的值在RBR中。RAM的输出提供中间元件，汽车记录所有步骤的可比结果。例如，在一个当虚拟地址在LBR范围内，并且在ram的输出范围内时CAR中的第th位为1，值为 的第th到1位的值与CAR中的值相同 堆栈。堆栈的数量等于处理器的数量。

LRU单元由一系列换档寄存器实现（位宽度是移位寄存器的数量减去1）。更新RR时，我们将1设置为相应的移位寄存器，每个寄存器向左移动。寄存器为0，最近使用了。LRU单元提供数字，并且相应的RR等待在下一个对象中更新。

与时间复杂度在直接搜索中，二叉搜索的时间复杂度为 ．当增加，方法的优点是显而易见的。

6.流式处理器的体系结构

我们的流处理器设计是基于多线程向量的。跨多线程是一种细粒度的多线程，其中线程交替执行。这种设计要求在每个时钟中切换线程，不管线程是否停止。这种机制确保管道持续运行。当线程中存在一个暂停时，后者最初会有一个请求。每次线程转到使用管道时，它都会等待，直到停止被处理。使用循环模式的线程的执行及其体系结构如图所示3.．

简化了无互锁的管道阶段（MIPS）的微处理器的架构以有效地处理图表问题。将管道分为线程选择（TS），指令获取（IF），指令解码（ID），执行（EX），并写回（WB）部分。

在线程选择部分中，将选择一个线程，并获得相应的程序计数器（PC）寄存器的值作为IF部分中的地址获得。每个线程都有其对应的PC寄存器，并且根据下一个程序（EX部分中的NPC）更新寄存器中的值。必须在选择另一个线程之前完成更新。由于FPGA资源的限制，根据循环中的指令寄存器来实现和使用八个线程。

在指令获取部分，管道根据相应的PC值获得正确的指令。有两个指令缓存:L1和L2缓存。L1缓存对于一个进程来说是私有的，而L2缓存对于多个进程来说是共享的。L1缓存大小为0.5 kB，采用全关联映射程序。L2缓存为4kb，采用直接映射程序。为每个线程设计一个指令寄存器来存储最后一条指令。当线程被阻塞时，它可以从指令寄存器中取最后一条指令。

在指令解码部分，解码控制器匹配指令并在数据寄存器中读取正确的数据。

执行部分中存在四种类型的操作：算术逻辑，加载和存储，流寄存器的访问和共享片上存储器的操作，以及分支跳转指令。在“写回”部分中，执行部分中的结果写入本地寄存器。结果可以来自LSU（负载和存储单元），ALU和SSU（流寄存器和共享片上存储单元）。地址处于指令中。

负载存储单元(LSU)是为操作访问而设计的，包括向量或标量访问。加载操作是从内存到流寄存器。存储操作是从流寄存器到内存。片上共享内存单元(SSU)是执行操作访问流寄存器或片上共享内存。LSU和SSU的结构相似。

7.三级存储器层次结构

图搜索问题中存储的数据具有存储稀疏性和内存访问缺乏局域性两个特点。缓存中的优化不能有效地利用内存访问的局部性。在借鉴流结构设计经验的基础上，提出了一种新的三层存储结构。

数字4说明第一级内存是一个本地寄存器。我们的架构是一个多核和多线程结构。本地寄存器分布在处理器内部。当多线程存在于每个进程的执行时，处理器需要保护状态。分布式线程寄存器创建每个线程，并使用它自己的私有寄存器来存储它们自己的状态。因为它们有一个本地寄存器，所以线程之间不会发生访问冲突。实现寄存器映射是不必要的。因此，地址空间中的访问量小，访问时延和功耗低。

fpga的本地寄存器是由块RAM资源实现的。在多线程执行中，本地寄存器将同时处理两个从解码中读取的请求和一个从回写中写入的请求。考虑到单个块RAM具有读写端口，我们为每个线程复制一个本地寄存器。当存在两个读取请求时，可以分别读取它们;但是，如果存在一个写请求，它们将同时被写。

第二层是流寄存器和芯片上的共享内存。流寄存器是芯片上的数据缓冲器，由块RAM实现，并结合流寄存器组来支持来自本地寄存器的多请求。一组流寄存器包含一组内存和一个控制器(如图所示)4）.银行存储器提供两个读写端口(端口A和端口B)，它们是本地寄存器和片外存储器的接口。

流寄存器的控制器有三个功能。一个是处理来自本地寄存器的数据和请求。另一个是处理来自芯片外存储器的数据和请求。最后一种方法是协调使用流寄存器中的数据读写的读写端口，使其具有正确的顺序。

片上共享内存是片上的一种特殊RAM。此外，它是通过软件控制和可编程的，这是不同于缓存。数据是通过地址访问的，处理器(如果有的话)和线程共享数据。本研究设计的片上共享存储器是处理器和线程之间的共享和通信接口。该设计的主要功能是数据处理和同步。共享片上内存由锁和数据段分割。当存在多个处理器或线程对同一个地址进行读写时，锁段支持原子锁，以确保程序顺序正确。在锁段中存在一个基址。位以基址开始，一位确定原子锁。每个进程或线程一次只能读取锁段中的一位。 The data segment is special shared data in a multithread or multiprocess program execution. Barrier synchronous counter is one of the special shared data items. The data segment is divided into several 64 bits block, and one local register is composed of 64 bits.

由于在512位的事务突发中的宽度，外部芯片存储器和流寄存器的接口之间的宽度也是512位。本地寄存器和流寄存器之间的数据宽度为64位，与本地寄存器中的数据相同。流和本地寄存器之间的有效数据事务由掩码标识。掩码由程序指令给出，其范围为0到7。

第三级内存层次结构是片外存储器。我们的片外存储器是双数据速率（DDR3），由FPGA提供。

8.结果和比较

所提出的可扩展并行分布式协处理器系统具有8个核心，每个核心有8个线程。我们使用了8个Xilinx Virtex-7 FPGA VC709评估板（XC7VX485T-2FFG1761）和一个名为Mellanox IS5030的商业交换机，基于IB协议来实现系统。Xilinx Virtex-7 FPGA VC709评估板有2个SODIMM DDR3存储器，存储容量为4 GB。包括八个通道PCIe接口和四行GTH收发器。通信带宽为40 GB / s，每个核心的存储器带宽理论为10 GB / s。此外，使用运行Linux的两台计算机。其中一个负责交换机的初始化，另一个负责生成BFS算法，加载数据和接收返回的结果。可以根据需要扩展系统中的节点数量。我们使用Verilog HDL在Xilinx Vivado 2013.4中实现并行架构系统，通过JTAG接口写入FPGA芯片。

根据Graph500基准测试，我们通过Kronecker图形生成器生成了一系列信息。然后，将信息转换为任何类型的数据结构，该数据结构是BFS算法的输入。我们在执行后验证了结果。在上述步骤中，用户可以由用户自定义数据结构和BFS算法的设计。

在图500中，使用TEPS获得具有不同测试台的处理器的公平比较。根据在Traph500中计算的性能，我们提出了计算性能的公式 ．细节显示在（1）.确定数据集和根节点时，是一个常数。

是图中的根节点的连接区域中的边的数量。是工作频率，在我们的实现中是200mhz。指示在程序开始和结束之间的时钟周期数。我们获得通过芯片范围。使用Traph500中的测试数据集。桌子1介绍我们的表现和比较。

我们运行称为算法的并行BFS算法1对我们的原型系统进行测试。使用BFS搜索图的尺度为19 ~ 23，即图数据的尺度为来 ，图的边因子是16。

在第一步实验中，我们使用Vivado 2014.1将测试数据通过计算机加载到fpga中。测试数据来自Graph500。然后在Linux下运行运行在ARM cortex上的BFS程序。ARM皮质由评估委员会提供。ARM皮层对搜索结果进行初始化，并通过PCIE总线从fpga获取搜索结果。最后使用Vivado 2014.1中的ChipScope进行性能分析。

由于大多数作品，目标高性能BFS使用MTEPS作为度量标准，比较原始的遍历性能是可能的，但硬件平台中的可用内存带宽设置了可实现的BFS性能的硬限制。我们的实验结果来自Virtex-7平台，更少（带宽的利用率为64％，理论带宽为10 GB / s，实际带宽为6.4 Gb / s）存储器带宽和工作频率（200 MHz）比平台在上班;因此，它相对较慢。我们的系统有8个核心，每个核心支持8个线程，它相当于64个并行线程。考虑到内存带宽，每单位带宽的遍历用作指标，以便与先前的工作进行公平比较。桌子1允许与RMAT图形的平均性能，可用内存带宽和遍历的平均性能，可用内存带宽和遍历的比较。

9.结论

我们可以得出以下结论：

与Betkaoui等人的方法相比。［4，我们的系统更有效率。64个并行单元的性能近似于[4］.我们在64个平行单元中的每单位带宽的遍历数据在Betkaoui等人中的256个单位和128个平行单元之间。［4］.

Attia等[8]在BFS算法优化上，我们的系统是可扩展的一般处理器平台，执行指令集解码和地址映射。Attia等[8]的规模有限，它是一种特殊的加速度单位。

我们的单位遍历数据是Hong等人的两倍[9]，性能大致相等。此外，我们提出的系统具有功率和可扩展性的优点。

该系统可作为可扩展的大数据图应用通用处理系统。

利益冲突

提交人声明有关本文的出版物没有利益冲突。

致谢

基金资助:国家自然科学基金资助项目(no。61602496)。

参考文献

1. C. Demetrescui, A. Goldberg，和D. Johnson，“最短路径问题:第九个DIMACS实现挑战，论文集。dimacs书。ams”最短路径问题的诉讼程序：第n个DIMACS实施挑战，程序.Dimacs Book.ams，第4页，2006年。视图:谷歌学术搜索
2. M. E. J. Newman和M. Girvan，“在网络中寻找和评估社区结构”，“物理评论E：统计，非线性和软质物理，第69卷，第2期2、论文编号026113,pp. 1-26113, 2004。视图:出版商网站|谷歌学术搜索
3. 卜丁，赵颖，蔡林等，“酵母中蛋白质相互作用网络的拓扑结构分析”，《中国生物医学工程学报》，核酸研究，卷。31，不。9，pp。2443-2450,2003。视图:出版商网站|谷歌学术搜索
4. B. Betkaoui, Y. Wang, D. B. Thomas, W. Luk，“一种用于高效和可扩展并行图探索的可重构计算方法”，发表于2012年IEEE第23届国际应用系统、体系结构和处理器会议论文集，ASAP 2012，页8-15，荷兰，2012年7月。视图:出版商网站|谷歌学术搜索
5. J. J. Tithi，D. Matani，G. Menghani和R. A.Chowdhury，“避免使用乐观并行化的共享内存并行BFS中的锁定和原子指令”2013 IEEE第27届国际并行和分布式处理研讨会论文集，IPDPSW 2013，pp。2013年5月1628-1637。视图:出版商网站|谷歌学术搜索
6. C. Chen，S. Koliai和G. Gao，“对精细谷物执行模型的广度首次搜索的能效的局部性，”清华科技，卷。18，不。6，第6678909号，第636-646,2013。视图:出版商网站|谷歌学术搜索
7. A. Putnam, A. M. Caulfield, E. S. Chung等人，“加速大规模数据中心服务的可重构结构”ACM / IEEE 41st International Symposium关于计算机架构（ISCA'14）的诉讼程序，pp.13-24，Ieee，Minneapolis，Minn，2014年6月。视图:出版商网站|谷歌学术搜索
8. O. G. Attia，T. Johnson，K. Townsend，P. Jones和J. Zambreno，Cygrgg：一个可重新配置的并行广度搜索架构，“第28届IEEE国际平行和分布式处理研讨会研讨会，IPDPSW 2014，pp。2014年5月228-235。视图:出版商网站|谷歌学术搜索
9. S. Hong, T. Oguntebi，和K. Olukotun，“基于多核CPU和GPU的高效并行图探索”，发表于第20届并行架构与编译技术国际会议论文集，PACT 2011，第78-88页，美国，2011年10月。视图:出版商网站|谷歌学术搜索
10. R. Pearce，M.Gokhalal和N. M. Amato，“用于分布式（外部）内存中的大规模无缝图形的缩放技术，”第27届IEEE国际平行和分布式处理研讨会，IPDPS 2013，pp.825-836，美国，2013年5月。视图:出版商网站|谷歌学术搜索
11. Y. Umuroglu, D. Morrison, M. Jahre，“单芯片FPGA-CPU异构平台上的混合广度优先搜索”，于第25届现场可编程逻辑与应用国际会议论文集，FPL 2015，英国，2015年9月。视图:出版商网站|谷歌学术搜索
12. A. Anghel，G.Rodriguez和B.Prisacari，“高性能数据分析中的沟通的重要性和特点”，2014年IEEE工作量特性国际研讨会论文集，IISWC 2014，pp.80-81，美国，2014年10月。视图:出版商网站|谷歌学术搜索
13. A. Amer, H. Lu, P. Balaji, S. Matsuoka，“描述MPI和混合MPI+线程在规模上的应用:BFS案例研究”第十五届IEEE/ACM集群、云计算与网格计算国际研讨会论文集，CCGrid 2015， pp. 1075-1083, 2015年5月。视图:出版商网站|谷歌学术搜索
14. M. Anderson，“更好地为超级计算机的基准测试：通常的尺度不是一个很好的指标，”IEEE频谱，第48卷，第48期1, pp. 12-14, 2011。视图:出版商网站|谷歌学术搜索
15. a.d. Bader, J. Berry, S. Kahan和R. Murphy，“图表500强榜单”，2010，http://graph500.org.list．视图:谷歌学术搜索
16. R. Berrendorf和M. Makulla，“多核和多处理器系统的水平同步并行广度优先搜索算法”，出版第六次国际诉讼程序。Conf。关于未来的计算技术和应用， 2014年第26期。视图:谷歌学术搜索
17. M. Ceriani，G.Palermo，S. Sechi，A.Tumeo和O. Villa，“探索了Manycore MultInode系统，为使用FPGA原型制作的不规则应用，”2013年FCCM的现场可编程自定义计算机上的21届年度国际IEEE研讨会的诉讼程序，p。2013年4月238日，美国。视图:出版商网站|谷歌学术搜索
18. V.Agarwal，F. Petrini，D. Pasetto和D. A. Bader，“多核处理器上的可扩展图探索”2010年ACM/IEEE高性能计算、网络、存储和分析国际会议论文集，SC 20102010年11月，美国。视图:出版商网站|谷歌学术搜索
19. M.Bisson，M.Bernaschi和E.Mastrostefano，“并行分布式广度首次搜索开普勒架构”，并行和分布式系统上的IEEE事务，卷。27，不。7，pp。2091-2102,2015。视图:出版商网站|谷歌学术搜索
20. U. A. Acar，A.Chargueraud和M. Rainey，快速并行图形 - 使用可分配和可达的前沿，inria搜索，2015年。
21. S. Beamer，K.Asanović和D. Patterson，“方向优化广度搜索”，科学规划，卷。21，不。3-4，pp.137-148,2013。视图:出版商网站|谷歌学术搜索
22. “多核单节点系统上numa优化的并行广度优先搜索”2013年IEEE大型数据会议2013年大数据综述2013年，pp。2013年10月394-402。视图:出版商网站|谷歌学术搜索

版权

版权所有©2017万荣Huang等人。这是分布下的开放式访问文章知识共享署名许可协议，允许在任何媒介上不受限制地使用、传播和复制，但必须正确引用原作。