通信密集环境下基于内存利用率的预计算方法

A Precomputation Method Based on Memory Utilization in Intensive Communication Environments

针对通信密集型图计算环境下原静态最大消息数阈值方法由于内存不足导致的频繁低效I/O问题,提出了一种基于内存利用率的预计算方法。该方法利用了图应用的计算满足交换律和结合律的特点,根据当前进程的内存利用率判断是否将本轮超步通信过程中的部分消息进行预计算,同时在预计算过程中使用细粒度锁以增大预计算线程的并发度;在下轮超步的正常计算时合并上轮的预计算结果,实现了通信和计算的重叠,达到减少作业响应时间和磁盘I/O开销的目的。实验结果表明,在通信密集场景下,该方法在性能和I/O开销上均优于已有的MMT方法,作业响应时间减少了5.9%~79.0%,同时计算过程中的磁盘开销减少了9.99%~79.87%。

A precomputation method based on memory utilization（MUP）is proposed to improve the I/O-inefficient problem caused by limited memory of the static maximum message threshold method（MMT）in intensive communication environments.The method leverages both the associative law and commutative law of graph computations,and precomputes some partial incoming messages of current super-step based on the process memory utilization. The precomputed results are then combined in the next super-step＇s normal computations.Moreover,a find-grained lock mechanism is used to increase the parallel granularity of precomputation threads.The method reduces the job response time and the expensive disk I/O costs incurred by messages through overlapping computation and communication.Experimental results show that MUP is better than the original MMT method in both the performance and I/O costs.The job response time is improved by 5.9%~79.0% and high redundant disk I/O costs are reduced by 9.99%~79.87% in intensive communication environments.