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

刘强 1; 董小社 1; 陈衡 1; 王寅峰 2

doi:10.7652/xjtuxb201710010

您当前的位置：

首页 >

文章列表页 >

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

更新时间：2025-07-09

- 通信密集环境下基于内存利用率的预计算方法
- A Precomputation Method Based on Memory Utilization in Intensive Communication Environments
- 西安交通大学学报 2017年51卷第10期页码：59-64
- 作者机构：
  
  西安交通大学电子与信息工程学院,西安,710049
- 作者简介：
- 基金信息：
  
  : 2017-03-07。作者简介: 刘强(1985—),男,博士生;董小社(通信作者),男,教授,博士生导师。基金项目: 国家重点研发计划资助项目(2016YFB0201402,2016YFB0201800);国家自然科学基金资助项目(61572394);深圳市科技计划资助项目(JSGG20140519141854753)
- DOI：10.7652/xjtuxb201710010
  中图分类号： TP391
- 网络首发：2017-10-10，
  
  纸质出版：2017
- 稿件说明：
移动端阅览
刘强 1, 董小社 1, 陈衡 1, 等. 通信密集环境下基于内存利用率的预计算方法[J]. 西安交通大学学报, 2017,51(10):59-64.

A Precomputation Method Based on Memory Utilization in Intensive Communication Environments[J]. 2017, 51(10): 59-64.
刘强 1, 董小社 1, 陈衡 1, 等. 通信密集环境下基于内存利用率的预计算方法[J]. 西安交通大学学报, 2017,51(10):59-64. DOI： 10.7652/xjtuxb201710010.

A Precomputation Method Based on Memory Utilization in Intensive Communication Environments[J]. 2017, 51(10): 59-64. DOI： 10.7652/xjtuxb201710010.

摘要

针对通信密集型图计算环境下原静态最大消息数阈值方法由于内存不足导致的频繁低效I/O问题

提出了一种基于内存利用率的预计算方法。该方法利用了图应用的计算满足交换律和结合律的特点

根据当前进程的内存利用率判断是否将本轮超步通信过程中的部分消息进行预计算

同时在预计算过程中使用细粒度锁以增大预计算线程的并发度; 在下轮超步的正常计算时合并上轮的预计算结果

实现了通信和计算的重叠

达到减少作业响应时间和磁盘I/O开销的目的。实验结果表明

在通信密集场景下

该方法在性能和I/O开销上均优于已有的MMT方法

作业响应时间减少了5.9%～79.0%

同时计算过程中的磁盘开销减少了9.99%～79.87%。

Abstract

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.

关键词

Keywords

references

CHING A, EDUNOV S, KABILJO M, et al. One trillion edges: graph processing at facebook-scale [J]. Proceedings of the VLDB Endowment, 2015, 8(12): 1804-1815.

MALEWICZ G, AUSTERN M H, BIK A J C, et al. Pregel: a system for large-scale graph processing [C]∥Proceedings of the 41st ACM Sigmod International Conference on Management of Data. New York, USA: ACM, 2010: 135-146.

ROY A, MIHAILOVIC I, ZWAENEPOEL W. X-stream: edge-centric graph processing using streaming partitions [C]∥Proceedings of the 24th ACM Symposium on Operating Systems Principles. New York, USA: ACM, 2013: 472-488.

GONZALEZ J E, LOW Yucheng, GU Haijie, et al. PowerGraph: distributed graph-parallel computation on natural graphs [C]∥Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation. Berkeley, CA, USA: USENIX Association, 2012: 17-30.

SHI Xuanhua, CHEN Ming, HE Ligang, et al. Mammoth: gearing hadoop towards memory-intensive mapreduce applications [J]. IEEE Transactions on Parallel and Distributed Systems, 2015, 26(8): 2300-2315.

DHIMAN G, AYOUB R, ROSING T. PDRAM: a hybrid PRAM and DRAM main memory system [C]∥Proceedings of the 46th Annual Design Automation Conference. New York, USA: ACM, 2009: 664-669.

罗乐, 刘轶, 钱德沛. 内存计算技术研究综述 [J]. 软件学报, 2016, 27(8): 2147-2167.

LUO Le, LIU Yi, QIAN Depei. Survey on in-memory computing technology [J]. Journal of Software, 2016, 27(8): 2147-2167.

WANG Zhigang, GU Yu, BAO Yubin, et al. Hybrid pulling/pushing for I/O-efficient distributed and iterative graph computing [C]∥Proceedings of the 47th International Conference on Management of Data. New York, USA: ACM, 2016: 479-494.

KYROLA A, BLELLOCH G, GUESTRIN C. GraphChi: large-scale graph computation on just a PC [C]∥Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation. Berkeley, CA, USA: USENIX Association, 2012: 31-46.

BU Yingyi, BORKAR V, JIA Jianfeng, et al. Pregelix: big(ger)graph analytics on a dataflow engine [J]. Proceedings of the VLDB Endowment, 2014, 8(2): 161-172.

MCCUNE R R, WENINGER T, MADEY G. Thinking like a vertex: a survey of vertex-centric frameworks for large-scale distributed graph processing [J]. ACM Computing Surveys, 2015, 48(2): 1-39.

SHUN Julian, DHULIPALA L, BLELLOCH G E. Smaller and faster: parallel processing of compressed graphs with Ligra+ [C]∥Proceedings of the 25th Data Compression Conference. Piscataway, NJ, USA: IEEE Computer Society, 2015: 403-412.

VALIANT L G. A bridging model for parallel computation [J]. Communications of the ACM, 1990, 33(8): 103-111.

ZHANG Yanfeng, GAO Qixin, GAO Lixin, et al. Maiter: an asynchronous graph processing framework for delta-based accumulative iterative computation [J]. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(8): 2091-2100.

SHIRAZI J. Java performance tuning [M]. Sebastopol, CA, USA: O'Reilly Associates Inc., 2000: 45-49.

GONZALEZ J E, XIN R S, DAVE A, et al. GraphX: graph processing in a distributed dataflow framework [C]∥Proceedings of the 11th USENIX Conference on Operating Systems Design and Implementation. Berkeley, CA, USA: USENIX Association, 2014: 599-613.

张保,曹海军,董小社.面向图形处理器重叠通信与计算的数据划分方法.2011,45(4):1-4.[doi:10.7652/xjtuxb201104 001]

李健,黄庆佳,刘一阳,等.云计算环境下的大规模图状数据处理任务调度算法.2012,46(12):116-122.[doi:10.7652/xjtuxb201212020]

庄威,桂小林,林建材.云环境下基于多属性层次分析的虚拟机部署与调度策略.2013,47(2):28-32.[doi:10.7652/xjtuxb201302005]

鲍军鹏,宋楠,陶斌.依赖知识的服务组合算法.2013,47(8):1-6.[doi:10.7652/xjtuxb201308001]

李亮,王恩东,朱正东.应用动态生成树的GPU显存数据复用优化.2013,47(10):44-50.[doi:10.7652/xjtuxb201310 008]

熊金波,姚志强,马建峰,等.云计算环境中的组合文档模型及其访问控制方案.2014,48(2):25-31.[doi:10.7652/xjtuxb201402005]

马莉,唐善成,王静,等.云计算环境下的动态反馈作业调度算法.2014,48(7):77-82.[doi:10.7652/xjtuxb201407014]

郑鹏飞,尤佳莉,王劲林,等.一种多租户云的内部网络共享策略.2014,48(8):54-59.[doi:10.7652/xjtuxb201408010]

孙霞,张敏超,冯筠,等.Hadoop框架下的多标签传播算法.2015,49(5):134-139.[doi:10.7652/xjtuxb201505021]

周墨颂,朱正东,董小社,等.采用资源划分的云环境下Hadoop资源许可调度方法.2015,49(8):69-74.[doi:10.7652/xjtuxb201508012]

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

结构-语义-残差协同的图像压缩框架：面向隐私保护与高保真重建

电动车辆间接热系统快速除湿响应迟滞机理及优化控制策略

融合物理信息与深度算子网络的变压器绕组热-流场快速计算方法

扇贝仿生密封腔室内超临界二氧化碳泄漏流湍动能耗散机理研究

采用机器学习的大规模并行程序I/O性能建模与预测方法