ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2017, Vol. 54 ›› Issue (4): 787-803.doi: 10.7544/issn1000-1239.2017.20160049

• 系统结构 • 上一篇    下一篇

内存计算框架局部数据优先拉取策略

卞琛1,于炯1,修位蓉1,钱育蓉1,英昌甜1,廖彬2   

  1. 1(新疆大学信息科学与工程学院 乌鲁木齐 830046); 2(新疆财经大学统计与信息学院 乌鲁木齐 830012) (bianchen0720@126.com)
  • 出版日期: 2017-04-01
  • 基金资助: 
    国家自然科学基金项目(61262088,61462079,61363083,61562086);新疆维吾尔自治区高校科研计划(XJEDU2016S106)

Partial Data Shuffled First Strategy for In-Memory Computing Framework

Bian Chen1, Yu Jiong1, Xiu Weirong1, Qian Yurong1, Ying Changtian1, Liao Bin2   

  1. 1(College of Information Science and Engineering, Xinjiang University, Urumqi 830046); 2(College of Statistics and Information, Xinjiang University of Finance and Economics, Urumqi 830012)
  • Online: 2017-04-01

摘要: 内存计算框架的低延迟特性大幅提高了集群的计算效率,但Shuffle过程的性能瓶颈仍不可规避.宽依赖的同步操作导致大多数工作节点等待慢节点的计算结果,同步过程不仅浪费计算资源,更增加了作业延时,这一现象在异构集群环境下尤为突出.针对内存计算框架Shuffle操作的同步问题,建立了资源需求模型、执行效率模型和任务分配及调度模型.给出了分配效能熵(allocation efficiency entropy, AEE)和节点贡献度(worker contribution degree, WCD)的定义,提出了算法的优化目标.根据模型的相关定义求解,设计了局部数据优先拉取算法(partial data shuffled first algorithm, PDSF),通过高效节点优先调度,提高流水线与宽依赖任务的时间重合度,减少宽依赖Shuffle过程的同步延时,优化集群资源利用率;通过适度倾斜的任务分配,在保障慢节点计算连续性的前提下,提高分配任务量与节点计算能力的适应度,优化作业执行效率;通过分析算法的相关优化原则,证明了算法的帕累托最优性.实验表明:PDSF算法提高了内存计算框架的作业执行效率,并使集群资源得到有效利用.

关键词: 内存计算, 任务分配, 作业调度, 分配效能熵, 节点贡献度, 异构环境

Abstract: In-memory computing framework has greatly improved the computing efficiency of cluster, but the low performance of Shuffle operation cannot be ignored. There is a compulsory synchronous operation of wide dependence node on in-memory computing framework, and most executors are obliged to delay their computing tasks to wait for the results of slowest worker, and the synchronization process not only wastes computing resources, but also extends the completion time of jobs and reduces the efficiency of implementation, and this phenomenon is even worse in heterogeneous cluster environment. In this paper, we establish the resource requirement model, job execution efficiency model, task allocation and scheduling model, give the definition of allocation efficiency entropy (AEE) and worker contribution degree (WCD). Moreover, the optimization objective of the algorithm is proposed. To solve the problem of optimizing, we design a partial data shuffled first algorithm (PDSF) which includes more innovative approaches, such as efficient executors priority scheduling, minimize executor wait time strategy and moderately inclined task allocation and so on. PDSF breaks through the restriction of parallel computing model, releases the high performance of efficient executors to decrease the duration of synchronous operation, and establish adaptive task scheduling scheme to improve the efficiency of job execution. We further analyze the correlative attributes of our algorithm, prove that PDSF conforms to Pareto optimum. Experimental results demonstrate that our algorithm optimizes the computational efficiency of in-memory computing framework, and PDSF contributes to the improvement of cluster resources utilization.

Key words: in-memory computing, task allocation, job scheduling, allocation efficiency entropy (AEE), worker contribution degree (WCD), heterogeneous environment

中图分类号: