科创中国

电子信息技术

本发明公开了一种基于磁盘的分布式图计算方法，该方法采用基于磁盘的分布式计算模型，用图分割算法将原始图分割成P个子图，通过N次迭代完成一个图算法作业，子图的一次执行为一个任务，共包括(P×N)个任务；一个任务包括(1)子图加载和构建；(2)子图的计算；(3)结果存储、向其它子图发送相关数据的步骤；本方法以流水的方式调度任务，通过任务之间的重叠执行，可隐藏系统执行过程中磁盘读写与通讯的时延，这种执行过程使整个系统的运行时间几乎缩短到计算时间，大大提高了系统的性能，面对不同规模的图，系统可始终保持极小的系统规模，从而大大节省系统的硬件成本。

基于内存的大规模异步并行计算模型(Bulk Asynchronous Parallel model，BAP)：BAP计算模型也以顶点为单位进行并行计算，顶点在计算过程中可以观察到本轮迭代邻居顶点的最新值；BAP计算模型取消了同步的消息交换过程，顶点在计算过程中直接更新其邻居顶点及边的值；该方法存在以下缺陷：两个顶点不能同时对同一个顶点进行更新操作，顶点间数据相关性使大规模并行处理能力得不到充分发挥，系统效能低，对于越大规模的图，系统需要越大规模的集群。

冯丹，1970年5月生，湖北京山人，华中科技大学计算机学院院长，教授，博士生导师。信息存储系统教育部重点实验室副主任，武汉光电国家实验室（筹），兼任中国计算机学会外部设备专业委员会委员，中国计算机学会信息存储技术专业委员会委员，中国电子工业标准化技术协会海量存储标准工作委员会副主任委员武汉市科学技术协会常委，武汉市政协委员，第十三届全国人大代表。