随着信息时代的迅速发展,大数据应用日益火热。图搜索问题是大数据应用中的经典问题,BFS算法是图搜索中的核心算法也是Graph500测试基准中的核心搜索程序。BFS算法具有访存量大、运算简单、每访存字节操作比低的特征,另外地,BFS算法中的访存呈现出不规律的特征,其时空局部性较差,这导致商用处理器中在运行BFS算法时cache的失效率过高。基于上述考虑,课题组参考流处理器中的结构,开发了多核交叉多线程的流处理器原型,用SRF来替代cache在存储层次中的位置,然而在该原型中,一方面由于SRF延迟过高导致SRF的实际带宽过低;另一方面由于算法访存过多导致性能不高。本课题采用软硬件协同优化的方法,首先在商用处理器上对BFS算法进行了分析和优化,然后对流处理器原型中的SRF进行了设计与实现,最后在该流处理器上对BFS算法进行了设计和优化,最终提高流处理器原型的性能。首先,本文在商用处理器上对并行BFS算法进行了分析和优化。分别从减少访问延迟、减少访问次数、增大数据的局部性等方面来减少访存的开销,以提高程序的性能。先后实现了混合算法、面向NUMA结构的算法、采用数据预处理技术的算法,提出了关键数据结构的混合表示的优化方法,并通过pthread、OpenMP两种并行编程语言进行了实现,比较了在两种语言下,各种优化技术对算法的加速比。然后,针对流处理器原型中SRF指令访问延迟较高的问题,设计并实现了私有SRF和共享SRF两种结构。私有SRF结构下SRF指令可以实现无延迟,共享SRF结构可以使核间在SRF中实现共享。文章重点对共享SRF结构中的交叉开关进行了设计,在无SRF体访问冲突时,访问并发度可以达到8。最后,针对两种不同SRF结构的流处理器特征,分别设计了基于私有SRF结构的BFS算法以及基于共享SRF结构的BFS算法。在基于共享SRF的结构中,重新设计了SRF指令格式,并设计了关键数据在SRF中的组织,对BFS算法进行了优化。实验测试表明,私有SRF结构下,算法性能比原流处理器的算法性能提高了92%,共享SRF结构下的算法性能比私有SRF结构下的算法性能提高了13.8%。