基于减少外存访问的多任务图处理系统研究

发布时间：2018-04-26 12:09

本文选题：外存模式图处理系统 + 多任务　；参考：《华中科技大学》2016年硕士论文

【摘要】：图处理系统正被广泛的应用于各个领域的数据分析中,随着图处理任务的增加,它们需要有效的应对多任务环境。现有的图处理系统一般针对单一任务设计,在执行并行任务时存在图数据的重复和数据访问带宽的竞争。内存模式图处理系统节点间的交换数据为图处理任务私有,执行并行任务时对网络带宽的竞争是系统的瓶颈。现有的外存模式图处理系统可以避免网络通信开销,但是并行任务对图数据访问的不一致易造成I/O争用,影响性能。通过对现有外存模式图处理系统I/O优化方法的分析,提出了基于I/O去重、图数据共享的数据访问模型,从理论上论证了在面对并行任务时相对于传统模型的优势与局限性。基于该模型,设计并实现了面向多任务环境的外存模式图处理系统GraphDeSh。GraphDeSh通过对外存数据的统一访问消除了I/O重复,通过共享缓存的设计平衡了并行任务执行速度的差异,优化了并行任务的数据等待时间。使用不同的数据集和不同的算法组合测试了GraphDeSh的性能,验证了基于I/O去重、图数据共享的模型的有效性。测试结果显示,两任务GraphDeSh相对于传统的并行方式,最大达到了理想的2倍加速比。GraphDeSh的优化效果随着图算法的计算比例下降而下降,平均加速比为1.45倍。在不同数据集上,GraphDeSh的加速比相对于并行GraphChi的加速比提高了32.5%-60.7%,相对于并行X-Stream的加速比提高了84.5%-107.1%。
[Abstract]:Graph processing systems are widely used in data analysis in various fields. With the increase of graph processing tasks, they need to deal with multi-task environment effectively. The existing graph processing systems are generally designed for a single task, and there is duplication of graph data and competition of data access bandwidth when executing parallel tasks. The exchange of data between nodes of the memory pattern graph processing system is private to the graph processing task, and the competition of network bandwidth when executing parallel tasks is the bottleneck of the system. The existing memory schema graph processing system can avoid network communication overhead, but the inconsistency of parallel task to graph data access can cause I / O contention and affect performance. Based on the analysis of the existing I / O optimization method of the external mode graph processing system, a data access model based on I / O de-reduplication and graph data sharing is proposed. The advantages and limitations of the traditional model in the face of parallel tasks are theoretically demonstrated. Based on this model, we design and implement a multitasking environment oriented memory schema graph processing system (GraphDeSh.GraphDeSh), which eliminates I / O duplication through unified access to external memory data, and balances the difference of parallel task execution speed through the design of shared cache. The data wait time of parallel task is optimized. The performance of GraphDeSh is tested by using different data sets and different algorithms, and the validity of the model based on I / O de-reduplication and graph data sharing is verified. The test results show that compared with the traditional parallel method, the optimization effect of the two-task GraphDeSh reaches the ideal speed ratio of 2 times. GraphDeSh decreases with the decrease of the calculation ratio of the graph algorithm, and the average speedup ratio is 1.45 times. The speedup ratio of GraphDeSh is 32.5-60.7 higher than that of parallel GraphChi on different data sets, and 84.5% -107.1% higher than that of parallel X-Stream.
【学位授予单位】：华中科技大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP391.41

【相似文献】