随着大数据时代的到来,以数据为中心的应用在当代社会表现出越来越重要的作用。图算法,包括图搜索和图分解,在大数据应用中起着关键作用,具有数据量大,有效数据少,数据分布无规则,处理实时要求高等新的特点。处理器技术的发展在解决“存储墙”问题上进展缓慢,在处理图问题上远达不到其实时性的要求。现有的高性能计算在达到图搜索实时性的前提下,存在功耗高,成本高等不能市场化应用的瓶颈。当前面向图搜索问题的处理平台主要为异构多核分布式处理器,但是可扩展性不好。因此,面向大规模稀疏图问题,探索适合处理图算法应用的分布式并行处理器,具有十分重要的实践意义。本文在重点分析图搜索基础算法Breadth First Search算法和图分解算法Cholesky算法访存和通信特性的前提下,提出了BFS算法可扩展性分析模型及Cholesky算法性能模型,在可重构平台上设计并实现了基于二分查找的虚实地址转换。设计并实现了一个基于图搜索算法的分布式并行处理系统,最后建立了一个参数化性能模型,用于指导Multi-Frontal-Cholesky分解算法向量化实现大规模加速部件的设计。具体而言,本文的主要工作和创新点体现在:(1)建立了面向BFS算法的分布式并行协处理器可扩展性分析模型目前,国际上针对BFS算法的通信模型研究较多,系统可扩展性分析多是初步判断,并未结合存储研究。本文首次将分布式并行协处理系统的通信和存储作为一个整体,研究其存储随着协处理节点增多的性能表现,研究其通信缓冲大小与单节点的性能表现,针对具体问题进行函数拟合确定参数,量化最优缓冲区大小。研究通信和存储结合的处理时间模型,找到存储规模和通信规模的最佳平衡点。(2)设计实现基于二分查找的虚实地址转换虚实地址转换一般由操作系统实现。由于图数据寻址的无规则性使访存失效率较高,采用硬件实现可以加快寻址时间。适应图搜索问题的特点。本文虚实地址间的模式采用块连续地址的直接映射,充分利用片上资源,以数组为单位将地址映射存储在片上存储中,采用流水线实现基于二分查找算法的寻址。将数据的失效划分为数据项失效和数组项的失效,针对BFS算法数组项少,访问数组具有局部性的特点,以数组为单元在线上替换。虚实地址转换采用大页机制,三级页表索引,根据系统结点的数量决定流水线级数,使得寻址时间固定而高效,减少访存,提高虚实地址转换时间,实现处理器基本功能。(3)设计并实现了面向BFS算法的分布式并行处理系统目前,国际上处理BFS算法的高性能计算平台和协处理存在的主要问题是,其不具有可扩展性或扩展性不好。本文设计实现可面向BFS算法的分布式并行处理系统,整体结构为一个以ARM处理器核为主的开发板作为主要处理结点,以及8个以FPGAs芯片为协处理器的从结点。单结点通信带宽达到40Gbps,采用Infiniband网络架构。通过协处理结点开发板高速收发器与Infiniband交换机相连,FPGAs芯片通信接口实现了一个Infiniband协议的转换模块。处理器采用流处理结构,五级流水线,向量交叉多线程。存储采用三级存储,第一级存储为各线程私有寄存器,第二级存储包含流寄存器和片上共享存储,片上共享存储被系统所有线程和进程共享,第三级存储为片下存储DDR3,该系统在Graph500测试集测试下,性能和功耗对比当前最新研究均有一定优势。(4)建立了一个稀疏矩阵Cholesky分解算法的参数化模型Cholesky分解是重要的矩阵分解应用,特别是随着图数据增大,稀疏矩阵稀疏矩阵Cholesky分解算法成为研究热点。本文基于Cholesky分解算法的Multifrontal向量实现算法,为了评估多结点下加速部件性能,建立了一个稀疏矩阵Multi-frontal Cholesky分解算法向量化实现的参数化模型,通过常用矩阵集测试对比,证实了在特定应用中该模型的准确性,预测了规模与性能的关系,从而为加速部件的设计和规模选择提供指导。