基于异常检测模型的异构环境下MapReduce性能优化

针对"落伍者"的选择问题,提出利用故障诊断领域内通常使用的异常检测模型来选择"落伍者"的方法。首先,利用异常检测算法来发现集群中的"慢节点";然后改进MapReduce任务分配算法和推测执行算法,不再给"慢节点"分配任务并将"慢节点"中的任务分配至有空闲任务槽的正常节点中。在改进的推测执行算法中,因相同网段内的节点通常物理邻近,可提高数据传输速度,首次将"慢节点"中的任务分配至同网段的正常节点中,以便数据传输。实例验证结果表明,使用异常检测算法后可迅速检测出异常节点,且与Hadoop-LATE算法相比,处理相同任务量可缩短集群17%的任务处理时间,说明所提算法在集群整体性能优化中表现优异。     

Hadoop平台下改进的推测任务调度算法

研究对比Hadoop平台下默认的推测任务调度算法和异构环境下LATE调度算法的优势和不足,提出了一种基于Hadoop集群的改进的推测任务调度算法.该算法以节点历史信息对Reduce任务各阶段比例进行动态调整和更新,并对任务实时处理速率进行局部平滑处理来提高预估任务剩余完成时间的准确性,最后采用MCP模型对备份任务有效性进行验证.通过实验结果分析可知:该算法能够有效提升备份任务成功率,减少作业完成时间.     

异构环境下增强的自适应MapReduce调度算法

针对Hadoop默认调度算法和异构环境下LATE调度算法的不足,在SAMR调度算法的基础上提出了一种增强的自适应MapReduce调度算法。该算法记录了每个节点的历史信息,采用K-means聚类算法动态地调整阶段进度值以找到真正需要启动备份的落后任务。实验结果表明,增强自适应的MapReduce调度算法在提高任务执行时间的估算误差以及准确识别慢任务方面具有一定的有效性。     

异构环境下Hadoop推测执行算法

研究和分析Hadoop推测执行算法在异构环境下性能较差的问题,在深入研究源码的基础上提出改进算法。该算法根据系统负载情况自动调节后备任务的执行,实现系统负载均衡。采用Zaharia提出的历史平均剩余完成时间来估计剩余时间,并使用剩余时间值大于20%的方法来判断掉队者,进而得到更精确的掉队者队列。该算法在一定程度上提高了异构环境中推测执行的性能。      

基于MapReduce模型的并行计算平台设计

现如今人们的生活已经进入了互联网时代,每天网络上都会形成海量的数据。对于互联网企业而言,需要对大量的数据进行系统分类,以便能够找寻对自身有价值的信息。MapReduce是一款能够用于大型计算机集群并发处理大量网络数据的模型,本文对该模型进行了系统的分析与研究,提出了一种更为通用且可扩展的平台。     

Hadoop MapReduce短作业执行性能优化

Hadoop MapReduce并行计算框架被广泛应用于大规模数据并行处理.近年来,由于其能较好地处理大规模数据,Hadoop MapReduce也被越来越多地使用在查询应用中.为了能够处理大规模数据集,Hadoop的基本设计更多地强调了数据的高吞吐率.然而在处理对短作业响应性能有较高要求的查询应用时,Hadoop MapReduce并行计算框架存在明显不足.为了提升Hadoop对于短作业的执行效率,对原有的Hadoop MapReduce作出以下3点优化：1)通过优化原有的setup和cleanup任务的执行方式,成功地缩短了作业初始化环境准备和作业结束环境清理的时间;2)将首次任务分配从“拉”模式转变为“推”模式;3)将作业执行过程中JobTracker和TaskTrackers之间的控制消息通信从现有的周期性心跳机制中分离出来,采用即时传递机制.最后,采用一种典型的基于MapReduce并行化的查询应用BLAST,对优化工作进行了评估.各种不同类型BLAST作业的测试实验表明,与现有的标准Hadoop相比,优化后的Hadoop平均执行性能提升约23%.     

基于MapReduce模型的排序算法优化研究

MapReduce已经发展成为大数据领域标准的并行计算模型。为了使MapReduce系统下参与计算的所有节点高度负载均衡,并且最小化空间使用率、CPU、I/O的使用时长和网络传输开销等指标,在保持算法良好并行性的基础上,提出了一种MapReduce优化算法的设计规范,对多个指标同时进行优化。针对数据处理领域最重要的排序算法进行理论分析,给出了多指标约束下的最优算法,并证明了该优化算法满足MapReduce 优化算法规范。最后通过实验验证了该优化的排序算法在有效性和效率方面严格优于传统的排序算法。     

基于MapReduce模型的排序算法优化研究

MapReduce已经发展成为大数据领域标准的并行计算模型。理想情况下,一个MapReduce系统应该使参与计算的所有节点高度负载均衡,并且最小化空间使用率、CPU和I/O的使用时长以及网络传输开销。传统的算法往往只针对上述指标中的一种进行优化。在保持算法良好并行性基础上,对多个指标同时进行优化,提出了MapReduce优化算法的设计规范。针对数据处理领域最重要的排序算法进行理论分析,给出了多指标约束下的最后算法,并证明了该优化算法满足MapReduce优化算法规范。最后通过实验验证了优化的排序算法的有效性和效率。     

基于MapReduce的并行PageRank算法实现

分布式网络爬虫的广泛应用使得搜索引擎的数据规模呈几何式增长,面对数以TB甚至PB量级的数据,单机模式下的PageRank算法由于CPU、I/O和内存的开销过大导致效率低下。为此,提出一种基于MapReduce框架的并行PageRank算法。在算法的一次迭代过程中,利用Map函数对网页拓扑信息文件进行解析,使用Reduce函数计算网页得分,从而并行化PageRank算法的中间迭代过程。通过计算全局网页得分控制迭代次数,得到较精确的网页排序结果。实验结果表明,该算法在保持原有单机PageRank算法整体网页排序精度的基础上,具有较好的集群性能和较快的执行速度。     

基于MapReduce模型的分布式天文交叉证认*

交叉证认是实现多波段数据融合的关键技术,目前还缺乏对其分布式算法的研究。快速增长的数据规模使该问题必须要依赖分布式并行计算技术解决。提出了一种基于MapReduce分布式模型的新方法,根据Map-Reduce的要点,尽量减少了任务间的通信量,并通过合理设置划分粒度保证了效率与存储间的平衡。实验结果表明,该方法对海量数据交叉证认的效率提升明显,在大规模集群上达到了接近线性的加速比。该方法为交叉证认提供了一种快速有效的解决途径。     

基于蚁群算法的猜测符号执行的路径搜索

符号执行作为一种基本的程序分析技术,已被广泛应用于软件测试领域。研究表明,即使在现有的查询优化技术的支持下,约束求解也仍然是符号执行中最耗时的部分。猜测符号执行的思想是将多次约束求解合并成一次求解,从而减少约束求解消耗的时间。但是,猜测的成功率受猜测深度和路径搜索方向的影响,尤其是路径搜索的方向在较大程度上决定了整体猜测的成功率。因此,引导路径搜索向成功率高的方向进行,对提高猜测符号执行的整体效率至关重要。在猜测符号执行的路径搜索过程中引入蚁群算法,根据节点条件信息初次确定分支路径的权重,在多次迭代中根据分支路径的覆盖情况更新权重,通过权重决定路径搜索的方向。实验表明,该方法有效提升了猜测符号执行的效率。     

Improving MapReduce Performance with Partial Speculative Execution

The MapReduce framework has become the de facto standard for big data processing due to its attractive features and abilities. One is that it automatically parallelizes a job into multiple tasks and transparently handles task execution on a large cluster of commodity machines. The increasing heterogeneity of distributed environments may result in a few straggling tasks, which prolong job completion. Speculative execution is proposed to mitigate stragglers. However, the existing speculative execution mechanism could not work efficiently as many speculative tasks are still slower than their original tasks. In this paper, we explore an approach to increase the efficiency of speculative execution, and further improve MapReduce performance. We propose the Partial Speculative Execution (PSE) strategy to make speculative tasks start from the checkpoint. By leveraging the checkpoint of original tasks, PSE can eliminate the costs of re-reading, re-copying, and re-computing the processed data. We implement PSE in Hadoop, and evaluate its performance in terms of job completion time and the efficiency of speculative execution under several kinds of classical workloads. Experimental results show that, in heterogeneous environments with stragglers, PSE completes jobs 56 % faster than that with no speculation and 12 % faster than that with LATE, an improved speculative execution algorithm. In addition, on average PSE can improve the efficiency of speculative execution by 24 % compared to LATE.     

FP—Growth算法MapReduce化研究

随着云计算概念的盛行,以及数据挖掘技术在分布式环境下的应用问题,该文献针对当前业界中流行的大规模并行计算模型MapReduce,将其引入数据挖掘领域关联规则算法的并行化改进中,提出基于FP-Growth算法并行化改进的MR—FP算法,为并行化关联规则挖掘提供节点可扩展、可容错、故障可恢复的运行保证。并通过案例分析得出系统在事务数呈数量级级别增长下仍可保持较高的性能。通过理论分析和案例实验表明,数据挖掘理论和方法在云计算环境下可以充分发挥能力,具有广阔的、有价值的研究空间。     

GPU平台下针对SAR地面快视系统的RD算法优化与实现

针对SAR地面系统实时关键成像技术进行研究,采用GPU(Graphic Processing Unit)硬件平台CUDA(Computer Uniformed Device Architecture)编程模型,对传统合成孔径雷达的RDA(Range Doppler Algorithm)算法核心部分进行了针对性的设计与实现,并在GPU专用科学计算平台Tesla C1060上进行了实验。结果表明其处理速度是一台主流4核心8线程CPU的20倍以上,并且相对RadarSat\|1卫星可以达到10倍左右的实时率;基于GPU的处理方式较好地实现了SAR实时成像系统。     

MapReduce with communication overlap (MaRCO)

MapReduce is a programming model from Google for cluster-based computing in domains such as search engines, machine learning, and data mining. MapReduce provides automatic data management and fault tolerance to improve programmability of clusters. MapReduce’s execution model includes an all-map-to-all-reduce communication, called the shuffle, across the network bisection. Some MapReductions move large amounts of data (e.g., as much as the input data), stressing the bisection bandwidth and introducing significant runtime overhead. Optimizing such shuffle-heavy MapReductions is important because (1) they include key applications (e.g., inverted indexing for search engines and data clustering for machine learning) and (2) they run longer than shuffle-light MapReductions (e.g., 5x longer). In MapReduce, the asynchronous nature of the shuffle results in some overlap between the shuffle and map. Unfortunately, this overlap is insufficient in shuffle-heavy MapReductions. We propose MapReduce with communication overlap (MaRCO) to achieve nearly full overlap via the novel idea of including reduce in the overlap. While MapReduce lazily performs reduce computation only after receiving all the map data, MaRCO employs eager reduce to process partial data from some map tasks while overlapping with other map tasks’ communication. MaRCO’s approach of hiding the latency of the inevitably high shuffle volume of shuffle-heavy MapReductions is fundamental for achieving performance. We implement MaRCO in Hadoop’s MapReduce and show that on a 128-node Amazon EC2 cluster, MaRCO achieves 23% average speed-up over Hadoop for shuffle-heavy MapReductions.     

Prophet推测多线程系统设计与实现

推测多线程技术通过推测执行的方式开发应用程序的线程级并行性,以提高程序执行性能。该技术一般通过执行模型来检测运行时可能的线程推测错误情况,并采取合适的机制恢复程序正确运行。描述的Prophet是一种基于硬件实现的推测多线程执行模型。重点描述了Prophet执行模型针对执行模型设计的关键问题的解决方案,包括Prophet的线程状态控制和多版本的Cach。系统,Prophet的多版本Cache系统提供了推测数据缓存功能,并使用基于总线监听的Cache协议实现了数据依赖违规检测。还给出了使用Olden基准程序对Prophet执行模型进行功能和性能测试的结果,并分析说明了Prophet系统可以有效地开发应用程序的线程级并行性。     

消息代理机制下的MapReduce数据流优化

MapReduce编程模型是广泛应用于云计算环境下处理海量数据的一种并行计算框架。然而该框架下的面向数据密集型计算,集群节点间的数据传输依赖性较强,造成节点间的消息处理负载过重。提出基于消息代理机制的MapReduce改进模型,优化数据流。经实验数据表明,基于消息代理机制的MapReduce框架能提高数据密集型应用上的负载均衡。     

SHadoop: Improving MapReduce performance by optimizing job execution mechanism in Hadoop clusters

As a widely-used parallel computing framework for big data processing today, the Hadoop MapReduce framework puts more emphasis on high-throughput of data than on low-latency of job execution. However, today more and more big data applications developed with MapReduce require quick response time. As a result, improving the performance of MapReduce jobs, especially for short jobs, is of great significance in practice and has attracted more and more attentions from both academia and industry. A lot of efforts have been made to improve the performance of Hadoop from job scheduling or job parameter optimization level. In this paper, we explore an approach to improve the performance of the Hadoop MapReduce framework by optimizing the job and task execution mechanism. First of all, by analyzing the job and task execution mechanism in MapReduce framework we reveal two critical limitations to job execution performance. Then we propose two major optimizations to the MapReduce job and task execution mechanisms: first, we optimize the setup and cleanup tasks of a MapReduce job to reduce the time cost during the initialization and termination stages of the job; second, instead of adopting the loose heartbeat-based communication mechanism to transmit all messages between the JobTracker and TaskTrackers, we introduce an instant messaging communication mechanism for accelerating performance-sensitive task scheduling and execution. Finally, we implement SHadoop, an optimized and fully compatible version of Hadoop that aims at shortening the execution time cost of MapReduce jobs, especially for short jobs. Experimental results show that compared to the standard Hadoop, SHadoop can achieve stable performance improvement by around 25% on average for comprehensive benchmarks without losing scalability and speedup. Our optimization work has passed a production-level test in Intel and has been integrated into the Intel Distributed Hadoop (IDH). To the best of our knowledge, this work is the first effort that explores on optimizing the execution mechanism inside map/reduce tasks of a job. The advantage is that it can complement job scheduling optimizations to further improve the job execution performance.     

MapReduce框架下的朴素贝叶斯算法并行化研究

研究朴素贝叶斯算法MapReduce的并行实现方法, 针对传统单点串行算法在面对大规模数据或者参与分类的属性较多时效率低甚至无力承载大规模运算, 以及难以满足人们处理海量数据的需求等问题, 本文在朴素贝叶斯基本理论和MapReduce框架的基础上, 提出了一种基于MapReduce的高效、廉价的并行化方法. 通过实验表明这种方法在面对大规模数据时能有效提高算法的效率, 满足人们处理海量数据的需求.