基于并行计算的数据流处理方法研究

雩风三日

基于并行计算的数据流处理方法研究
. }7 S/ B  \8 P" u
    量大流速快的数据流挖掘己经成为当今国际学术界大数据处理的研究热点，与静态存储的数据相比，这些数据是连续实时获得的单次扫描数据。对于快速时变的数据流，在有限的内存资源下无法存储全部的数据流数据，如何精确地增量挖掘其连续变化趋势和发现隐藏的相关性对数据流的实时分析与处理带来了巨大的挑战，另一方面，数据流处理时滞也成为制约数据流挖掘的一个尖锐瓶颈问题。基于以上问题，本文研究了数据流趋势和相关性分析的融合并行计算模型和算法，将数据流挖掘与基于CPU (Central Process Unit)和GPU(Graphic Process Unit)的高性能计算有机地结合起来，实现动态连续的高效数据流处理方法。论文的主要研究内容可归纳如下:
    1、针对非线性非平稳时间序列数据流的预测能力不足问题，研究了基于HHT( Hilbert-Huang Transform)的Online-HHT分析方法，进一步结合RBF (Radial Basis Function)神经网络理论，研究了适合在线预测的时间序列数据流模型。该方法通过引入CPU多线程的并行处理方法，设计了时间序列数据流链式可重写滑动窗口的数据读写技术，实现了细粒度分段数据的并行预测分量和分段结果的合成算法。Online-HHT方法既能发挥其对时间序列数据流的时频自适应分析能力，又具有更快的计算处理速度，Online-HHT得到的数据流本征模分量也降低了RBF神经网络预测结构的输入复杂性，对时间序列数据流的趋势预测能力起到很大地提高。实验结果表明，通过与其他方法相比较，本文提出的方法能够处理数据流的短期趋势预测，并且处理速度更快，可应用于在线预测。
& j# J( |- H" c    2、针对在数据流频繁项挖掘中使用模式树造成空间复杂度过大的问题，提出了一种嵌套滑动窗口遗传算法NSWGA (Nested Sliding Window Genetic Algorithm)的数据流频繁项挖掘方法。本算法在滑动窗口中的数据流上分割出嵌套窗口，利用基于MPI的遗传算法并行处理嵌套窗口中的数据流，以及改进初始种群获得方法，实现了嵌套窗口中数据流的频繁模式快速挖掘。在数据流动过程中，采用定期删除过期数据的方法，更新滑动窗口中最新的频繁项集，进而实现增量维护，提高执行效率，快速发现数据流中的频繁项。
  l7 R+ X6 f  }# f8 Q+ D    3、针对由于资源约束造成的数据流处理时滞和效率问题，研究了最新超算技术GPU并行计算结构，根据数据流数据属性的特点和处理的高性能需求，提出了基于GPU的数据流通用处理模型。根据GPU并行计算结构的SIMT模式，采用基本窗口技术的滑动窗口模型，给出了粗粒度和细粒度两个并行计算层面的数据流处理结构，将数据流的数据划分为粒度合适的数据块，然后进行概要数据结构和各种挖掘算法的并行处理。粗粒度并行主要负责任务分工并行化，而细粒度并行负责抽取数据流概要数据结构的并行化，也负责在GPU上完成数据流挖掘和计算密集的线程网格，达到高效率的数据交换和高性能的并行算法。在这个通用数据流处理模型上，提出了基于GPU的数据流分位数并行计算方法GSQ(GPU Stream Quartiles)，调用GPU内核程序，使用哈希方法对数据流的数据块并行计算生成概要数据直方图，最后查询得到数据流分位数，实验验证了从处理带宽、响应时间和加速比都有很大的提高。
% U; r2 r2 s. X; h    4、针对在CPU上多条数据流相关性分析受到资源和执行顺序的实时性约束限制问题，本文研究提出了CPU和GPU协同处理的跨总线四层滑动窗口框架，用于处理多条数据流的并行计算，把多条数据流完全映射到GPU内存空间，建立数据流SID索引，使用基本子窗口偏移量可以实现不同级别的并行操作。构造了适合多数据流的多级并行计算处理，使用s→ Thread的细粒度并行计算和s→Block中粒度的方式，给出了单维多数据流的相关性分析并行算法GSSCCA(GPU Single-Dimensional Stream CanonicalCorrelation Analysis)，实验验证了算法有很好的准确度，极大提高了计算速度。
& O8 W% ~' W' ?7 `    5、对由多数据属性记录实时复杂信息的高维多数据流来说，在计算准确性和性能会出现比单维多数据流处理更为复杂的资源和执行顺序约束问题。针对这个问题，进一步深入研究了高维多数据流的相关性分析数学模型，提出了GPU上的高维多数据流相关性处理的模型与实施的架构以及并行计算方法GMSCCA(GPU Multi-Dimensional Stream Canonical Correlation Analysis)。使用数据立方体和维度约简的技术，在计算资源受限和高效率要求的环境下，可以快速精确地完成计算，并且在高性能和近似精度之间能够很好地平衡。
  B) ^- C! s/ a$ z# C% @
9 [& |, l/ W. t3 P 关键词:数据流;并行计算;图形处理器通用计算;趋势预测;频繁项集;数据流相关性