图作为离散对象之间关系的灵活抽象,被广泛应用于很多科学计算和一些新兴的应用领域包括基因组学、天体物理学、人工智能、数据挖掘等。图的宽度搜索算法是用于探索图中具有某种属性的顶点、路径及边的集合的重要方法,也是其他一些重要图算法的基础。云计算与社交网络的兴起使得图搜索算法得到了更广泛地应用。随着图问题规模以及单一计算节点的计算和存储能力的局限性,图的分布式实现得到越来越多的关注。但是图搜索算法所具有的一些固有特征,包括数据驱动的计算、非规则的并行性、较差的数据局部性和高的通信/计算比,给集群上的高效地实现带来巨大的挑战。本文主要关注方便图搜索算法的设计与实现的并行编程模型支持及其在新型高性能计算系统上的高效实现。　　 本文针对PGAS语言(以UPC为例)对图搜索算法的表达和优化上的不足,借鉴Kashev Pingali等人提出的以数据为中心的算法抽象-Operator Formulation of Algorithms,提出了适合集群系统的Shared Work List语言扩展,并在Berkeley UPC的编译器和运行时系统中实现。Shared Work List具有三个比较重要的特征,即灵活的执行模型、统一的通信优化机制以及对集群级投机执行的支持。其次,面对曙光6000龙芯分区所具有的诸多新体系结构特征,我们扩展了UPC语言的底层通信库GASNet以支持曙光6000龙芯分区具有的三层通信网络。最后,在三种不同的平台上,包括共享存储多核平台、64节点的集群系统和曙光6000龙芯分区,实验评测了使用Shared Work List实现的Graph500基准测试程序的性能。实验结果表明,在一定的数据规模及参数下,基于Shared Work List的Graph500在不同的平台上都表现出接近甚至好于MPI和Open MP版的性能及可扩展性,具有较强的性能可移植性。