广度优先搜索(BFS)是许多图形应用程序的底层内核算法,如社交网络,医疗信息学,传输系统等。因此,它已被吸收为Graph500的核心,用于评估超级计算机大数据处理的能力。本文依托广州超算中心“天河二号”提供的平台,针对分布式内存体系结构和共享内存体系结构对BFS算法进行了研究。首先,本文量化分析了分布式内存体系结构上BFS算法的性能瓶颈。并且提出了分布式内存体系结构上关于负载均衡的优化方法,在“自顶向下”阶段同步重点是否被访问过的信息,在“自底向下”阶段同步重点队列信息来达到平衡各个进程通信次数的目的。同时,本文通过对异步小消息通信库重新封装消息头的方式来减少通信消息的长度和通过本地标记的方式来减少无效通信次数的方式,减少了分布式内存体系结构上的通信量。其次,本文针对Knights Landing(KNL)芯片对共享内存体系结构的BFS算法进行了优化。对于KNL的异构存储器层次结构,本文利用KNL芯片提供的Flat模式,利用MCDRAM和DRAM的性能差异,通过将顶点数据、父节点数据分配在MCDRAM上,把边缘数据、临时变量和数组分配在DRAM上的方式来实现更快的读写数据和内存访问。同时,对于高速缓存更新策略,本文的主要工作是利用Clik来对算法的细粒度进行重新划分,来保证每个工作线程读取恰好适合一个CPU缓存行大小所对应的顶点的值,并且每个值的更新不会影响其他的缓存行。最后,我们在Tianhe-2超级计算机和KNL芯片上评估了本文的实验。实验结果表明,在分布式内存体系结构下,我们的方法有效缩短了通信时间,与自上而下的方法相比,获得了 3倍左右的加速比。在KNL平台,我们的方法有效的减少了最后一级缓存load和store指令数,在rmat图上获得了 10倍左右的加速比。