基于迭代填充的内存计算框架分区映射算法

针对内存计算框架Spark在作业Shuffle阶段一次分区产生的数据倾斜问题,提出一种内存计算框架的迭代填充分区映射算法（IFPM）。首先,分析Spark作业的执行机制,建立作业效率模型和分区映射模型,给出作业执行时间和分配倾斜度的定义,证明这些定义与作业执行效率的因果逻辑关系;然后,根据模型和定义求解,设计扩展式数据分区算法（EPA）和迭代式分区映射算法（IMA）,在Map端建立一对多分区函数,并通过分区函数将部分数据填入扩展区内,在数据分布局部感知后再执行扩展区迭代式的多轮数据分配,根据Reduce端已分配数据量建立适应性的扩展区映射规则,对原生区的数据倾斜进行逐步修正,以此保障数据分配的均衡性。实验结果表明,在不同源数据分布条件下,算法均提高了作业Shuffle过程分区映射合理性,缩减了宽依赖Stage的同步时间,提高了作业执行效率。     

MRI:面向并行迭代的MapReduce模型

机器学习领域内的多数模型均需要通过迭代计算以求解其最优参数,而MapReduce模型在迭代计算中的缺陷不足导致其在迭代计算中无法得到广泛应用。为解决上述矛盾,基于MapReduce模型提出并实现了一种可用于模型参数求解的并行迭代模型MRI。MRI模型在保持Map以及Reduce阶段的基础上,新增了Iterate阶段以及相关通信协议,实现了迭代过程中模型参数的更新、分发与迭代控制;通过对MapReduce状态机进行增强,实现了节点任务的重用,避免了迭代过程中节点任务重复创建、初始化以及回收带来的性能开销;在任务节点实现了数据缓存,保障了数据的本地性,并在Map节点增加了基于内存的块缓存机制,进一步提高训练集加载效率,以提高整体迭代效率。基于梯度下降算法的实验结果表明:MRI模型在并行迭代计算方面性能优于MapReduce模型。     

客户端缓存策略

将相关数据缓存到客户端的文本、Excel、Access文件与客户端内存中,通过执行脚本程序启动组件程序或其他程序,以实现客户端缓存数据与Web页面的交互,并将服务器端的相关处理程序迁移到客户端,在客户端建立"写缓存"以解决ASP.NET程序运行缓慢的问题.这些策略可用于JSP与C/S模式到B/S模式迁移开发中.     

Spark并行计算框架的内存优化

以Spark为代表的集群并行计算框架在大数据、云计算浪潮中广泛应用,其运行性能优化是应用的关键。为提高运行性能,分析了Spark框架执行流程、内存管理机制,结合Spark和JVM两个层面内存管理的特点,提出3条优化策略：(1)通过序列化和压缩方式减少缓存数据大小,使得GC消耗降低,提升性能;(2)在一定范围内减少运行内存大小,用重算代替缓存,可以提升性能;(3)配置适当的JVM新生代和老生代的比例、Spark计算与缓存空间比例等内存分配参数,能够较大程度地提升性能。实验结果表明,序列化和压缩能够减少缓存占用空间42%;提交运行内存由1 000 MB减少到800 MB时,性能增加21%;优化内存配比,性能比默认参数有10%～30%的提升。     

高性能LTE终端通信协议栈缓存机制

针对LTE终端通信协议栈的处理过程中Cache缓存方式效率差,提出一种可以提高处理速度降低延时的数据缓存方式。通过利用便签式存储器(Scratch-Pad Memory,SPM)和直接内存存取方式(Direct Memory Access,DMA)的性能优势,将协议栈处理的过程中需要与处理器频繁交互的数据缓存到SPM中,实现在SPM中完成数据的包头压缩/解压、加密/解密和重组等协议功能处理,并通过DMA方式实现SPM与主存之间的数据搬运,减少处理器对大块连续数据的搬运,提高处理效率。该方式避免了CPU在通过Cache缓存方式进行数据交互容易发生缓存不命中的问题,从而提高了协议栈的数据处理效率。经过理论分析及实验对比,结果表明,在LTE协议栈处理过程中,采用SPM与DMA结合的数据缓存机制,相比Cache缓存方式可以使整体性能至少提升12.65%。     

ATC系统中高速内存缓存的设计与实现

由于空中交通管制系统在航空领域里的特殊应用,系统中部分数据实时性强,并且不需要长期存储,针对这一存储需求设计并实现了基于高速内存缓存的数据存储模型.模型基于key-value的内存池的内存管理方法,采用预申请和分组方式管理内存.通过实验分析比较了T数索引和哈希表索引的优点和适用范围,最终选择T树索引作为模型的索引数据结构.实验结果表明,该模型极大的提高了系统对该类数据的存取能力和系统性能.     

基于混合内存的Apache Spark缓存系统实现与优化

随着大数据时代数据规模的激增,内存计算框架得到了长足发展。主流内存计算框架Apache Spark使用内存来缓存中间结果,大幅度地提升了数据处理速度。同时,具有较快的读写速度和较大容量的非易失性存储器NVM在内存计算领域展现出了巨大的发展前景,使用DRAM和NVM构建Spark混合缓存系统成为一种可行方案。文中提出了一种基于DRAM-NVM混合内存的Spark缓存系统,该系统选择平面混合缓存模型作为设计方案,然后为缓存块管理系统设计了专用的数据结构,并提出了适用于Spark的混合缓存系统整体设计架构。另外,为了将频繁访问的缓存块保存在DRAM缓存中,提出了基于缓存块最小重用代价的混合缓存管理策略。首先从DAG信息中获取RDD的未来重用次数,未来重用次数多的缓存块将被优先保存在DRAM缓存中,并在缓存块迁移时考虑了迁移成本。设计实验表明,DRAM-NVM混合缓存相比原有缓存系统的性能平均提升了53.06%,对于相同的混合内存,所提策略相比默认缓存策略有平均35.09%的提升。同时,使用文中设计的混合系统只需要1/4的DRAM和3/4的NVM作为缓存,就能达到全部DRAM缓存约79%的性能...     

基于分布式数据集的并行计算框架内存优化方法

随着科学计算和人工智能技术的快速发展，分布式环境下的并行计算已成为解决大规模理论计算和数据处理问题的重要手段。内存容量的提高以及迭代算法的广泛应用，使得以Spark为代表的内存计算技术愈发成熟。但是，当前主流的分布式内存模型和计算框架难以兼顾易用性和计算性能，并且在数据格式定义、内存分配、内存使用效率等方面存在不足。提出一种基于分布式数据集的并行计算方法，分别从模型理论和系统开销两个角度对内存计算进行优化。在理论上，通过对计算过程进行建模分析，以解决Spark在科学计算环境下表达能力不足的问题，同时给出计算框架的开销模型，为后续性能优化提供支持。在系统上，提出一种框架级的内存优化方法，该方法主要包括对跨语言分布式内存数据集的重构、分布式共享内存的管理、消息传递过程的优化等模块。实验结果表明，基于该优化方法实现的并行计算框架可以显著提升数据集的内存分配效率，减少序列化/反序列化开销，缓解内存占用压力，应用测试的执行时间相比Spark减少了69%～92%。     

Spark任务间消息传递方法研究

当今诸多工程问题及科学研究中,都面临着大数据处理和高性能计算任务的双重挑战。基于内存计算技术提出的分布式处理框架Spark已在学术和工业界得到了广泛的应用,但其MapReduce-like的编程模型在任务间无法进行通信,导致科学计算中的数值算法无法进行高效实现。针对上述问题,研究了一种Spark内存计算与MPI消息传递模型相结合的解决方案,充分利用内存访问存取快速的特点和MPI的多种高性能通信机制,解决了Spark编程模型表达能力不足的缺陷,同时为MPI提供了面向数据的DAG计算方式。通过对Spark内部的运行环境和调度系统进行修改,使得MPI在Spark中得以无缝融合,为高性能计算和大数据任务提供了一个统一的内存计算系统。测试结果表明,在数值计算和迭代算法上相比Spark至少有50%的性能提升。     

基于矩阵分解的协同过滤算法的并行化研究

基于矩阵分解的协同过滤算法是近几年提出的一种协同过滤推荐技术,但其每项预测评分的计算都要综合大量评分数据,同时在计算时还需要存储庞大的特征矩阵,用单一节点来进行推荐将会遇到计算时间和计算资源的瓶颈。通过对现有的基于ALS(最小二乘法)的协同过滤算法在Hadoop上并行化实现的原理和特点进行深入的研究,得到了传统的迭代式算法在Hadoop上运算效率不高的原因。根据迭代式MapReduce思想,提出了循环感知任务调度算法、缓存静态数据、任务循环控制、迭代终止条件检测等方法。通过在Netflix数据集上的实验表明,迭代式MapReduce思想提高了基于ALS的协同过滤算法的并行化计算的效率。     

iMapReduce: A Distributed Computing Framework for Iterative Computation

Iterative computation is pervasive in many applications such as data mining, web ranking, graph analysis, online social network analysis, and so on. These iterative applications typically involve massive data sets containing millions or billions of data records. This poses demand of distributed computing frameworks for processing massive data sets on a cluster of machines. MapReduce is an example of such a framework. However, MapReduce lacks built-in support for iterative process that requires to parse data sets iteratively. Besides specifying MapReduce jobs, users have to write a driver program that submits a series of jobs and performs convergence testing at the client. This paper presents iMapReduce, a distributed framework that supports iterative processing. iMapReduce allows users to specify the iterative computation with the separated map and reduce functions, and provides the support of automatic iterative processing within a single job. More importantly, iMapReduce significantly improves the performance of iterative implementations by (1) reducing the overhead of creating new MapReduce jobs repeatedly, (2) eliminating the shuffling of static data, and (3) allowing asynchronous execution of map tasks. We implement an iMapReduce prototype based on Apache Hadoop, and show that iMapReduce can achieve up to 5 times speedup over Hadoop for implementing iterative algorithms.     

一种基于本体KNN的分布式缓存数据交换策略

以国家开放大学教务管理系统为例,以减少数据资源获取的时间开销以及提高数据质量作为目标,提出了一种基于本体KNN的分布式缓存数据交换策略,用于解决分布式系统在不同节点之间进行数据交换时产生的性能优化问题。仿真实验结果表明,该策略具有较为出色的优化访问性能,可以实现数据交换过程的进一步优化,进而提升系统的整体性能,具有一定的实用价值。     

基于周期性无线网络数据传输的缓存管理技术研究

网络缓存管理是一种降低Internet流量和提高终端用户响应时间的网络技术。它来自于计算机和网络的其他领域,如目前流行的Intel架构的CPU中就存在缓存,用于提高内存存取的速度;各种操作系统在进行磁盘存取时也会利用缓存来提高速度;分布式文件系统通常也通过缓存来提高客户机和服务器之间的速度。无线网络数据的缓存可以在客户端,也可以在网络上,该文基于此,对周期性网络数据传输过程中的缓存管理技术进行了初步研究。     

分布式和缓存技术在大并发量网站中的应用

对于高访问量网站,Web服务器端经常面临大并发量和海量数据流请求的问题,导致用户访问延时,利用负载均衡和内存缓存相结合技术可以解决这一问题。在服务器端采用集群下的负载均衡策略,将工作任务相对均衡地分配到各个节点上执行;采用内存缓存机制,通过优先读取内存中的缓存数据以减少对数据库的访问次数,进而减轻数据库负载。性能测试结果和用户体验反馈信息显示,该方法在大并发量访问时能极大地提高系统的吞吐量。     

一种并行内存缓冲系统及其实现技术

为支持数据挖掘应用,对NOW机群系统的分布式共享存储管理机制进行了适当的简化1～2,结合数据挖掘中数据处理的特点,设计了一个并行内存缓冲系统。该缓冲系统为应用程序提供上下两层应用接口,既可以保证内存操作的透明性,又为应用程序自主操作数据提供了极大的灵活性。缓冲系统可以充分利用网络结点的存储空间为应用程序实现网络虚拟存储环境,同时也可以很好地支持应用程序对数据文件的并行化处理。     

Cache-Aware Multigrid Methods for Solving Poisson's Equation in Two Dimensions

Conventional implementations of iterative numerical algorithms, especially multigrid methods, merely reach a disappointing small percentage of the theoretically available CPU performance when applied to representative large problems. One of the most important reasons for this phenomenon is that the need for data locality due to poor main memory latency and limited bandwidth is entirely neglected by many developers designing numerical software. Only when most of the data to be accessed during the computation are found in the system cache (or in one of the caches if the machine architecture comprises a cache hierarchy) fast program execution can be expected. Otherwise, i.e. in case of a significant rate of cache misses, the processor must stay idle until the necessary operands are fetched from main memory, whose cycle time is in general extremely large compared to the time needed to execute a floating point instruction. In this paper, we describe program transformation techniques developed to improve the cache performance of two-dimensional multigrid algorithms. Although we merely consider the solution of Poisson's equation on the unit square using structured grids, our techniques provide valuable hints towards the efficient treatment of more general problems. Received January 31, 1999; revised October 17, 1999     

用于二级缓存的一种改进的自适应缓存管理算法

在机群系统或数据库服务器等应用环境下,由于本地内存资源限制,某些大内存应用与磁盘交互过多,会严重损害其性能.在高速网络支持下,把其他节点内存或采用专门的内存服务器作为系统的二级缓存,可减少对磁盘访问并提高应用性能.在二级缓存应用模式下,基于LIRS算法并对其存在的缺点进行改进,提出了一种自适应缓存管理算法LIRS-A.LIRS-A可根据应用访问特征自适应调整,避免了LIRS不适应某些具有时间局部性模式的情况.在TPC-H应用中,LIRS-A比LIRS最多有7.2%的性能提升;在网络流分析数据库的典型Groupby查询中,LIRS-A比LIRS的命中率最多可提高31.2%.     

基于动态profiling技术的流水粒度调优

结点间流水是解决数据分布和计算分割不一致时的一种重要的并行发掘技术.结点间流水通过计算与通信的重叠获得并行度.精确的流水粒度是获得良好的流水性能的关键.流水分块取决于很多因素,如程序规模、程序的访问模式、结点规模、结点的计算能力和存储体系、通信系统的性能、通信库开销等等.提出了动态profiling方式并实现在流水粒度的推导中,运行时信息收集部分典型分块,结合代价模型推导流水粒度,该模型考虑局部性优化;探索如何减少插桩执行的开销的同时保证代价模型的精度.实验证明,这种方式有更好的适应性,能获得较好的流水并行.     

基于分布式数据缓存技术的Web-OLAP系统研究

为了解决在分布式环境下,Web-OLAP系统并发访问量急剧增加导致OLAP服务器负担过重的问题,提出一种基于分布式数据缓存技术的Web-OLAP系统。给出了该系统的总体框架和分布式缓存数据的表示,并设计了分布式缓存数据的管理算法。具体的应用实例表明,该方法可以有效地提高分布式环境下Web-OLAP系统的访问效率,较大缩短系统的响应时间。     

分布数据缓存体系

讨论了一种在分布信息访问环境下提高数据利用率和减少通信流量的分布缓存体系.缓存节点能缓存多个数据源的信息,使多个用户相互重用数据缓存,从而提高缓存的命中率.该缓存体系采用了多种不同的方法来解决数据缓存的一致性问题.最后提出了一种虚缓存节点的概念,用于扩展原来的体系.虚节点可以减少全局缓存访问优化计算的成本.