宽度优先搜索(Breadth-first Search,简称BFS)是一种基础的图形算法,是众多算法的核心组件,在大量领域中得到广泛应用,如网络安全、医学信息、数据挖掘、社交网络、语义网等等。宽度优先搜索算法还是一种典型的数据密集型应用,Graph 500即使用其对超级计算机处理数据密集型应用的能力进行排名。近年来,得益于较低的功耗和较高的性价比,众核体系结构的加速器在高性能计算领域得到广泛应用。MIC(Many Integreated Core)作为最新的众核体系结构协处理器,相对于其它加速器来说,具有和传统并行编程模型兼容的优势。随着采用CPU+MIC的“天河二号”登上Top 500榜首,MIC在高性能计算领域得到广泛重视。宽度优先搜索算法的并行实现具有数据竞争较严重、问题不规则和访存局部性差等特点,而MIC具有大量线程和宽向量处理能力且每线程的平均缓存较小,因而要充分发挥MIC硬件的优势高效实现宽度优先搜索,将面临线程间竞争开销较大,向量部件利用率不高,缓存利用率差等问题。本文即面向这些问题,研究利用MIC高效实现宽度优先搜索算法,主要取得了如下成果:1)设计并实现了自上向下和自下向上相结合的混合BFS算法。该算法根据图形的特点,在不同的搜索层使用不同的搜索策略,能够结合两种搜索策略的优势,性能分别为自上向下和自下向上策略的3.21和2.15倍。2)提出了一种面向MIC优化的多线程BFS算法。该算法以混合BFS算法为基础,通过减少数据竞争,消除原子操作,并采用动静相结合的线程调度方式,能够很好地利用MIC提供的大量线程处理能力。3)提出了一种使用宽向量部件进一步加速BFS的方法。该方法在自上向下搜索部分采用SIMD指令同时扫描顶点的邻居,在自下向上搜索部分采用SIMD指令并行查找未访问的顶点,能够进一步加速BFS算法,最高加速比达到1.85。4)设计并实现了CPU和MIC协同计算的异构混合BFS算法。该算法以混合BFS算法为基础,在搜索层中任务较多时采用CPU和MIC协同计算,通过比例可调的任务划分方法以及重叠计算的通信设计,解决了协同计算中任务不均衡和通信开销较大的问题,相对于CPU的加速比达到1.4倍左右。实验结果表明,本文在MIC中实现的BFS算法性能约为GPU的5.31倍;CPU+MIC异构混合算法的最高加速比达到1.46倍。