网络的快速发展造成了海量数据的累积形成与信息爆炸。在网页链接和社交关系等实际问题中往往涉及大型的图算法。这些图的规模之大,可以达到数十亿顶点,上万亿条边。如何在如此巨大规模的图上进行高效的计算已经成为一个巨大的挑战欲。图是一种较为复杂的数据结构,其表示方式为G=(V,E),其中V表示图中顶点的集合,E表示两个顶点之间边的集合。
目前,很多基于图的计算都需要对图进行遍历解决,串行的编程思想下的遍历方式对于大规模的图遍历就显得力不从心。
问题的可能的解决方法有两种:提高硬件设备的性能、改善图的计算方法。硬件设备的性能包括增大设备的内存,提高CPU的频率,提高总线数据传输速度,改善磁盘I/O等等。但是,硬件设备还是比较昂贵,并且这种方式仅能应付一时,我们认为随着网络的发展数据量的继续增大是必然的。
通过改善图的计算方法,并行成为一个解决问题的突破点。在并行的思想下,就必须考虑到同步、进程(或线程)通信、调度等等问题。通过设计合理的数据存储模式,优化负载均衡,优化磁盘I/O操作,降低线程的调度开销,是可以实现以较小的资源开销解决大问题的目的的。
现在,国内外已经有很多同仁在该方向做出了积极的探索,获得了巨大的成绩。Pregel是一个将目标图类问题的运算模型归结为在图的拓扑节点(Vertex)上迭代执行特定的算法。它由Google提出,目前已经有很多不同版本的类Pregel,他们针对框架内可能存在的性能损耗问题做出优化改进,例如,Mizan等。Graphchi则更是一个令人激动的项目,它通过优化磁盘I/O,摒弃Pregel中BSP的计算模型,采用PSW的异步机制等实现在个人PC上完成大规模数据的处理。
在上述提及的两个想法中:我们更倾向于第二种。我们认为空间可以换时间,但是这不能成为一个随意耗费资源的借口。我们致力于寻找一种廉价的处理大规模图对象的方法。随着CPU芯片的集成度与主频逐渐达到一个瓶颈,多核的架构成为提高计算能力的解决方案之一。我们的目标是在多核的架构下结合操作系统的优势,充分利用系统资源,提高并行加速比,以达到提高计算能力的目的。