分布式多维大图迭代计算性能优化方法

Optimization Methods for Distributed Iterative Computing Performance over Multi-Dimensional Large Graph

大规模图的复杂挖掘算法通常需要高频迭代分析,而在计算与存储方面扩展性良好的分布式计算是提高处理效率的有效方案.然而,图顶点之间存在自由分布的边关系,会在分布式计算任务之间产生大量消息,由此在迭代过程中产生的巨大通信开销严重制约性能收益.已有工作在传统消息推送框架下采用合并和备份等技术降低通信代价,但主要面向结构简单、易优化的单维消息类算法,并不适用于结构复杂的多维消息类算法,也难以与当前最先进的消息按需拉取框架兼容.因此提出一种新型轻量级顶点备份机制,通过备份顶点的按需同步以及本地消息的按需生成,可完美继承拉取框架在容错和内存管控等方面的系统优势,同时显著降低通信代价.此外,通过考虑通信收益与负载偏斜代价,可计算最优阈值以提高整体性能.最后在大量真实数据集上验证了相关技术的有效性.

Complex mining algorithms over large-scale graphs usually require highly frequent iterative analysis,while distributed computing with scalable computing power and storage capacity is a preferred solution for efficiency.However,the edges freely connecting vertices generate a lot of messages across distributed computing tasks and hence incurs communication costs during iterations,which heavily limits the performance improvement of distributed computing.To alleviate the negative impact of communication bottleneck,existing research basically employs combining and replicating techniques on top of the traditional pushing framework design.However,they mainly focus on easy-to-be-optimized single-dimensional-message algorithms with simple message data structure,and are not suitable for other important multi-dimensional-message algorithms with complex structure.Also,they cannot be seamlessly integrated into the-state-of-the-art pulling framework where messages are generated on demand.We thereby propose a lightweight vertex replication mechanism to synchronize replicated vertices and generate messages based on such replications on demand.The mechanism can work well under the pulling framework with inherent advantages in terms of fault-tolerance and memory consumption,and also greatly optimize the communication costs.Moreover,by considering the communication benefits and the costs incurred by possible workload imbalance,it can select an optimal replication threshold for best performance.Finally,extensive experiments over various real-world graphs validate the effectiveness of the lightweight vertex replication framework and the threshold analysis model.