支持高并发数据流处理的MapReduce中间结果缓存

针对面向大规模历史数据的高并发数据流处理需求,为改进MapReduce的实时处理能力,提出了一种内存Hash B树、外存SSTable文件的key/value中间结果缓存,该结构具有可划分性、可扩展性和高效性.在此基础上,利用B树的平衡性特征提出了一种基于概率的B树构造算法和多路查询算法,利用读写开销估算和缓冲区信息改造了外存文件读写策略和内外存替换算法,进一步优化了中间结果的高并发读写性能.算法分析和实验证明了该缓存的有效性.     

面向多核集群的数据流程序层次流水线并行优化方法

数据流编程语言是一种面向领域的编程语言,它能够将计算与通信分离,暴露应用程序的并行性.多核集群中计算、存储和通信等底层资源的复杂性对数据流程序的性能提出了新的挑战.针对数据流程序在多核集群上执行存在资源利用低和扩展性差等问题,利用同步数据流图作为中间表示,文中提出并实现了面向多核集群的层次性流水线并行优化方法.方法包含任务划分与调度、层次流水线调度和数据局部性优化,经过编译优化后生成基于MPI的可并行执行的目标代码.其中任务划分与调度是利用程序中数据和任务并行性将任务映射到计算核上,实现负载均衡和低通信同步开销;层次性流水线调度是利用程序中的并行性构造低延迟流水线调度;数据局部性优化是针对数据访问存在的Cache伪共享做面向存储的优化.实验以X86架构多核处理器组成的集群为平台,选取媒体处理领域的典型应用算法作为测试程序,对层次流水线优化进行实验分析.实验结果表明了优化方法的有效性.     

一种面向数据流程序的软件流水并行化方法

数据流编程被广泛应用于多媒体、图像处理和信号处理等领域.多核处理器为数据流程序提供了强大并行计算资源,如何利用多核处理器的并行性以提高数据流程序性能,对满足媒体处理等实时性需求具有重要意义.基于多核处理器提出了一种面向数据流程序的软件流水并行化方法,利用整数线性规划理论对软件流水中的计算、通信资源和流水线执行阶段等进行...     

低码率视频解码器去块效应滤波系统的设计

本文在改进MPEG-4后处理滤波顺序的基础上,优化了滤波算法,提出了一种针对低比特率视频编码后处理滤波的硬件实现结构,该结构利用中间数据缓存以重复利用数据来提高数据读写速度,并重复利用缓冲器减少硬件开销,同时在滤波算法中采取流水线设计,实现数据流控制与滤波计算并行执行。该系统较以往去块效应滤波系统具有高效率低复杂度等特点,不仅提高了低码率视频解码器后处理滤波的实时性能,而且节省了面积。     

一种面向高速度数据流的频繁模式挖掘算法

数据流频繁模式挖掘是从实时、连续、有序的数据序列中寻找频繁模式的过程,以往的相关研究通常将该过程分为两个阶段:首先监测数据流中各模式的频率,由于数据流环境对空间与时间的限制,需要对监测模式进行剪裁,因而频率的计算和剪裁需要重复进行;当用户提交查询时,从监控的模式中筛选出满足要求的输出.现有研究都注重解决如何对观测对象进行剪裁,而事实上在计算模式频率时,数据项集中不同数据项间的组合使得频率计算非常耗时.因此,对于高速数据流,算法通常没有足够的时间来处理数据流中的每个事务,这会影响挖掘结果的正确性.针对这一问题提出了一种新的面向高速数据流的频繁模式挖掘算法Delay. 在Delay算法中将模式频率的统计延迟到第2阶段进行,第1阶段只记录"必要信息",这样大大提高了算法所能处理的数据流流动速度的上限.实验结果表明,算法在效率上优于已有算法,LossyCounting和FDPM,尤其是在处理长数据项集数据流时优势更为明显.     

数据流历史数据的存储与聚集查询处理算法

目前数据流的研究成果主要集中在分析处理存储于内存中的最近一段时间内的数据流数据,忽略了对数据流历史数据的分析处理与存储管理.提出了一种数据流历史数据的存储管理及聚集查询处理方法,通过对历史数据实施多层递阶抽样存储,并在内存中建立存储数据流历史数据聚集值的HDS-Tree索引,实现对无限数据流历史数据的存储管理,有效地支持各种聚集查询同时,还给出了基于HDS-Tree的聚集查询算法的时间复杂性分析和查询误差分析.理论分析与实验结果表明,该方法可以有效地用于数据流历史数据的存储与分析.     

数据流优化匹配在数字海洋中的应用

提出一种利用图形处理单元(GPU)协同CPU的实时数据流分析匹配机制,将海洋实时数据流与国家标准数据进行比对,分析水质是否异常.该方法将存储到分布式基站上的数据分类规整并阶段化存储,接受数据流匹配请求后,在实时数据流匹配分析系统中利用GPU进行匹配分析处理,并自动生成分析结果.实验结果表明,该方法可以缩短海洋监测的检测...     

高速连续数据流记录系统中并行处理接口的研究

为了解决高速数据流的连续记录/读取与存储介质速度慢之间的矛盾,文中用FPGA设计了基于RAID结构的并行处理接口,实现了高速数据的分割降速、合并/恢复、纠错重构,解决了高速数据流连续存储中的I/O瓶颈问题。并行处理接口采用了流水线的设计方式及动态的逻辑配置,使得系统性能得到很大的优化,解决了高速数据处理中的延迟、数据错误、工作时序不同步等问题。并行处理接口最终在实验系统中实现了对高达160MB/S连续实时数据流的处理。     

在线-离线数据流上复杂事件检测

随着数据采集和处理技术的发展,在物联网对象跟踪、网络监控、金融预测、电信消费模式等领域中进行事件检测显得越发重要.事件检测在一次扫描数据流的假设下完成,数据流在被处理完后丢弃.事实上,很多应用场景中,历史数据流因含有丰富的信息而不能简单丢弃,且一些事件检测查询需要同时在实时和历史数据流上进行.鉴于已有复杂事件检测很少考虑同时在实时-历史数据流上进行模式匹配,作者研究了在线-离线数据流上复杂事件检测的关键问题.主要工作如下:(1)针对滑动窗口内产生的大量模式匹配中间结果,提出利用时态关系和时空关系管理中间结果的方法 TPM和STPM.STPM以中间结果的时态和状态信息为权值对中间结果进行管理,将最近的、最有可能更新状态的中间结果置于内存,极大地减少了中间结果的读取操作代价.(2)给出了基于选择度的在线-离线复杂事件检测优化算法;(3)给出了算法的复杂性分析和代价模型;(4)在基于时空关系的中间结果管理模型下,在一个在线-离线复杂事件检测原型系统中进行实验,对多个参数(子窗口大小,选择度,匹配率,命中率)进行了算法对比分析.实验结果充分验证了所提出的算法的可行性和高效性.     

一种面向大规模数据密集计算的缓存方法

随着高性能计算机逐步应用在大规模数据处理领域,存储系统将成为制约数据处理效率的主要瓶颈。在分析了影响数据密集型计算 I/O 性能若干关键因素的基础上,提出使用计算结点本地存储构建协作式非易失缓存、以分布式存储架构加速集中式存储架构的方法。该方法基于应用层协同使用分布化的本地存储资源,使用非易失存储介质构成大缓存空间,存放大规模数据分析的中间过程结果,以此实现高缓存命中率,并利用并发度约束控制等手段避免 I/O 竞争,充分利用本地存储的特定性能优势保证缓存加速效果,从而有效地提高了大规模数据处理过程的 I/O 效率。基于多平台多种 I/O 模式的测试结果证实了该方法的有效性,聚合 I/O 带宽具有高扩展性,典型数据密集应用的整体性能最大可提升6倍。     

非规则流中高维数据流典型相关性分析并行计算方法

为了满足在计算资源受限的环境下高维数据流处理的实时性要求,提出一种方法——基于GPU(graphic processing unit)的非规则流中高维数据流的处理模型和具体的可行架构,并分析设计了相关的并行算法.该六层模型是将GPU处理数据的高宽带性能结合进滑动窗口中数据流的分析,进而在该框架下基于统一计算设备架构(compute unified device architecture,简称CUDA),使用数据立方模型以及降维约简技术并行分析了多条高维数据流的典型相关性.理论分析和实验结果均表明,该并行处理方法能够在线精确地识别同步滑动窗口模式下高维数据流之间的相关性.相对于纯CPU方法,该方法具有显著的速度优势,很好地满足了高维数据流的实时性需求,可以作为通用的分析方法广泛应用于数据流挖掘领域.     

基于流式计算的空间科学卫星数据实时处理

针对空间科学卫星探测数据的实时处理要求越来越高的问题,提出一种基于流计算框架的空间科学卫星数据实时处理方法。首先,根据空间科学卫星数据处理特点对数据流进行抽象分析;然后,对各处理单元的输入输出数据结构进行重新定义;最后,基于流计算框架Storm设计数据流处理并行结构,以适应大规模数据并行处理和分布式计算的要求。对应用该方法开发的空间科学卫星数据处理系统进行测试分析,测试结果显示,在相同条件下数据处理时间比原有系统缩短了一半;数据局部性策略比轮询策略具有更高的吞吐率,数据元组吞吐率平均提高29%。可见采用流式计算框架能够大幅缩短数据处理延迟,提高空间科学卫星数据处理系统的实时性。     

分布式流数据加载和查询技术优化

分布式流查询是一种基于数据流的实时查询计算方法,近年来得到了广泛的关注和快速发展。综述了分布式流处理框架在实时关系型查询上取得的研究成果;对涉及分布式数据加载、分布式流计算框架、分布式流查询的产品进行了分析和比较;提出了基于Spark Streaming和Apache Kafka构建的分布式流查询模型,以并发加载多个文件源的形式,设计内存文件系统实现数据的快速加载,相较于基于Apache Flume的加载技术提速1倍以上。在Spark Streaming的基础上,实现了基于Spark SQL的分布式流查询接口,并提出了自行编码解析SQL语句的方法,实现了分布式查询。测试结果表明,在查询语句复杂的情况下,自行编码解析SQL的查询效率具有明显的优势。     

支持实时流计算应用的关键技术研究进展

信息系统在进行知识的挖掘和管理时,需要处理各种形式的数据,流数据便是其中之一.流数据具有数据规模大、产生速度快且蕴含的知识具有较强时效性等特点,因而发展支持实时处理应用的流计算技术对于信息系统的知识管理十分重要.流计算系统可以追溯到29世纪90年代,至今已经经历了长足的发展.然而,当前多样化的知识管理需求和新一代的硬件架构为流计算系统带来了全新的挑战和机遇,催生出了一系列流计算领域的技术研究.首先介绍流计算系统的基本需求以及发展脉络,再按照编程接口、执行计划、资源调度和故障容错4个层次分别分析流计算系统领域的相关技术;最后,展望流计算技术在未来可能的研究方向和发展趋势.     

基于图形处理器的数据流快速聚类

在数据流环境下,聚类算法不仅需要有较高的聚类质量,同时需要有实时处理速度.因而,提出了一类基于图形处理器(graphics processing unit,简称GPU)的快速聚类方法,包括基于K-means的基本聚类方法、基于GPU的数据流聚类以及数据流簇进化分析方法.这些方法的共同特点是充分利用了GPU强大的处理能力和流水线特性.与以往具有独立框架的数据流聚类算法不同,这些基于GPU的聚类算法具有同一框架和多种聚类分析功能,为数据流聚类分析提供了统一的平台.从分析可知,数据流聚类分析的核心操作实际上就是距离计算和比较.基于这一认识,利用GPU的子素向量处理功能进行距离计算.性能验证实验是在配有Pentium IV 3.4G CPU和NVIDIA GeForce 6800 GT显卡的PC上进行的.综合分析和实验结果表明,基于GPU的数据流聚类算法比传统的CPU算法平均快7倍,从而为高速数据流应用提供了良好的支持.     

面向股票交易分析场景的流式大数据系统测试框架

分布式集群环境使得数据实时计算更为复杂,流式大数据处理系统的正确性难以保障.现有的大数据基准测试框架可以测试流式大数据处理系统的性能表现,但是普遍存在应用场景设计简单、评价指标不充分等不足.针对这一挑战,本文构造了一个面向股票交易场景的流式大数据基准测试框架,通过生成股票高频交易数据,测试系统在高流速场景下的延迟、吞吐量、GC时间、CPU资源等的性能表现.同时,通过横向测试验证流式大数据系统的扩展性.本文以Apache Spark Streaming为待测系统进行测试,实验结果表明,高流速场景下出现延迟增加、GC时间提高等性能下降问题,原因是系统输入速率的提高及并行度的增加.     

基于FPGA与Sobel算法的实时图像处理

如今,图像处理算法的复杂度越来越高,图像处理的数据量越来越大,图像处理的实时性显得十分重要。为了解 决图像预处理、视频流数据实时性存在的问题,给出了一种基于FPGA和OV5640以Sobel算子进行边缘检测的图像采集与处 理系统设计方法,FPGA将OV5640摄像头采集到的视频流数据传送至SDRAM,由Sobel算子模板处理后通过VGA显示视频 图像。该设计基于Intel公司的Cyclone IV系列FPGA芯片EP4CE10F17C8进行了验证。实验结果表明,基于FPGA和Sobel边 缘检测算法,使用流水线设计和乒乓操作,可实现视频流数据处理的实时性。     

基于Storm的大数据指标实时计算方法

大数据时代,面对爆发式增长的海量异构大数据,企业指标数据的实时供给能力亟待全面提升.基于流处理技术的大数据指标实时计算方法,主要由日志采集、消息管理、协调管理、实时处理等部分构成,使用Hadoop、Zookeeper、Storm、Kafka、Redis等开源软件,综合应用了数据库日志分析,流处理、内存计算等技术.本文详细论述了采用Storm技术的大数据指标实时计算方法的技术架构,实现方法及路径,同时给出了算法验证的过程和结果分析.     

基于流式计算的遥感卫星数据快视处理方法

随着高分辨率遥感卫星数据获取能力和地面数传接收能力的提高，现有遥感卫星快视处理系统的处理负载增大，实时性要求越来越难以满足。针对这些问题，采用流式计算思想提出了一种新的遥感卫星数据快视处理系统设计方法。在分析遥感卫星数据快视处理数据流特点的基础上，应用Storm框架对现有系统进行并行优化，设计遥感数据流处理任务拓扑结构，同时利用消息队列中间件Kafka改进处理单元间数据交换和数据缓存方式。实验表明，该系统在数据吞吐率和可靠性方面测试效果良好。     

一种数据流上截止期敏感的滑动窗口处理策略

在数据流上定义了截止期作为连续查询的实时约束，并建立了基于截止期的滑动窗口处理模型；提出了一种基于预测的截止期敏感的滑动窗口处理策略；在多滑动窗口查询处理环境中，提出了一种（k,m ）截止期约束机制，在提高查询实时性的前提下，尽可能的满足不同查询对结果丢失率的不同约束。实验结果表明该处理策略能够有效提高数据流上滑动窗口查询的截止期满足率。