1引言
受到市场的竞争和需求的影响，图形处理器的计算能力在近年来，以超过摩尔定律的每年2.5-3倍的速度不断增长。随着Tesla架构的图形处理器的问世，图形处理器开始将顶点处理器和像素处理器合并为统一的标量流处理器，这意味着通用计算以及成为图形处理器的硬件设计目标之一。CUDA并行计算模型的提出，更使图形处理器通用计算的范围得到极大扩展。这一变化使得图形处理器可以在数据流处理和数据流挖掘领域发挥更大的作用。数据流是一种不同于传统数据库中静态数据的新的数据形态。它的出现源于电话通讯记录，Web点击一记录，网络数据包检测记录，金融证券交易一记录，卫星返回数据流，以及零售交易数据流等应用领域。数据流具有快速持续到达，潜在无限的容量的特点，对数据流的处理往往要求实时的，在线的处理。利用图形处理器强大的计算能力和高内存带宽的特点，协助中央处理器处理数据流具有提高数据流处理吞吐量和实时性的研究价值。本文的研究重点有两个方面，一个方面是针对图形处理器和数据流自身的特点，从理论角度分析如何更好的使用图形处理器处理数据流。另一方面则是针对数据流处理领域的两个问题，提出具体的，基于图形处理器协处理的数据流处理方法。
本文的主要工作可以归纳如下:(1)简介了图形处理器通用并行计算的发展阶段和CUDA并行计算模型;(2)简介了数据流处理和数据流挖掘技术;(3)详细的阐述和分析了图形处理器在数据流并行计算的结合问题，并提出基于图形处理器的数据流处理基本模型;(4)针对单数据流分位数维护问题，改进概构直方图分位数维护算法，使之支持滑动窗口并适于图形处理器并行计算，实现了相应的GPU内核算法;(5)针对多数据流相关系数计算问题，在基于基本窗口的滑动窗口理论的基础上，提出一种跨总线的四层滑动窗口模型。使用C++和CUDA-C语言，实现了该框架模型和并行数据流相关系数维护的GPU内核算法。1图形处理器通用并行计算和数据流图形处理通用并行计算发展历史1.1.1图形处理器的发展现状图形处理器(GraphicsProcessingUnit,GPU)是现代微型计算机上必不可少的硬件设备—显卡(DisplayCard)的核心。图形处理器是NVIDIA公司在1999年发布的3D图形处理芯片GeForce256时首先提出的概念。在此之前，计算机中处理影像输出的显示芯片，很少被视为是一个独立的运算单元。早期的图形处理设备GE其核心仅实现了简单的四维浮点运算功能，它可由一个寄存器的定制码定制出不同功能，分别用于图形输出流水线中的矩阵乘法、裁减计算、投影缩放等操作，通过用I2个GE单元完整地实现三维图形输出流水线的功能。现代图形处理的流水线主要集中在顺序处理的两大部分:第一部分是对图元实施几何变换及对图元属性进行处理，即将几何模型的多边形/三角形顶点数据流从CPU交由图形处理部件实现几何变换及属性处理(包括部分光照计算)。第二部分则是在实现扫描转换进行光栅化以后进行一系列图形绘制处理，包括各种光照效果的合成、纹理映射、遮挡处理、反混淆处理等。
图形输出处理本身具有规范的流水线操作，当越来越高级的图形绘制功能需要在光栅一级处理时，SIMD(单指令多数据)结构的处理机是最合适的并行硬件结构〔I]oGPU内核也逐渐演化成了具有顶点可编程性和子素可编程性的流处理器。(streamprocessor).市场迫切需要实时、高清晰度的3D图形，为了适应这种需求，可编程的图形处理器已发展成为一种高度并行化、多线程、多核的处理器，具有杰出的计算功率和极高的存储器带宽的计算设备。在受到激烈的市场竞争和日益增长的计算机电子娱乐领域对图形处理器的不断提升的性能需求的驱动下，过去的5年里图形处理器的性能以超越摩尔定律的每年2.5-3倍的速度在增长。这种增长速度远远超过了中央处理器(CPU)的性能提升速度。图1.1和图1.2分别给出了近5年内CPU和GPU的每秒浮点运算次数和内存带宽的对比【2]0CPU和GPU存在较大浮点运算能力的差异的根本原因是GPU是专为数据和计算密集型、高度并行化的计算而设计，GPU的设计将更多的晶体管用于数据处理，而不是数据缓存和流程控制。
参考文献
[1]吴恩华.图形处理器用于通用计算的技术现状及其挑战[J].软件学报，2004, 15 (10)1493-1504.
[2]NIVDIA.CUDA Programming Guide 2.2[EB/OL]2009-06-01[2009-05-26]
[3] Govindaraju NK, Lloyd B, Wang Wei, et al. Fast computation of database operationsusing graphics processors[C].SIGMOD, Paris, France, 2004:611-622.
[4]曹锋，周傲英.基于图形处理器的数据流快速聚类「J].软件学报，2007, 18 (2) :291-302
[5]Buck I, Foley T, Horn D, et al. Brook for GPUs:stream computing on graphicshardware[J].ACM Trans. On Graphics, 2004, 23 (3):777-786.
[6]Dotsenko Y, Govindaraju N. K, Solan P. P, et al. Fast Scan Algorithms on GraphicsProcessors[C].ICS, Island of Kos, Aegean Sea, Greece, 2008:205-213.
摘要 4-5
Abstract 5
引言 8-9
1 图形处理器通用并行计算和数据流 9-23
1.1 图形处理通用并行计算发展历史 9-14
1.1.1 图形处理器的发展现状 9-11
1.1.2 早期图形处理器通用并行计算 11-12
1.1.3 早期图形处理器通用并行计算的主要技术 12-13
1.1.4 基于高级语言的图形处理器通用并行计算 13-14
1.2 数据流简介 14-18
1.3.1 数据流管理系统 14-15
1.3.2 数据流模型 15
1.3.3 数据流窗口模型和主要技术 15-17
1.3.4 数据流挖掘技术 17-18
1.3 CUDA并行计算模型 18-20
1.3.1 CUDA的线程和内存层次结构 18-19
1.3.2 CUDA的程序执行方式 19-20
1.3.3 单指令多线程 20
1.4 图形处理器数据流并行处理的优势和研究现状 20-22
1.4.1 图形处理器数据流并行处理的优势 20-21
1.4.2 图形处理器数据流并行处理的研究现状 21-22
1.5 章节安排 22-23
2 图形处理器数据流并行计算模型 23-32
2.1 问题提出 23
2.2 基于图形处理器的数据流处理基本模型 23-25
2.3 图形处理器数据流处理模式分析 25-29
2.3.1 图形处理器处理数据流的协作模式 25-26
2.3.2 图形处理器处理数据流的数据交换模式 26-27
2.3.3 图形处理器处理数据流的模型选择 27-28
2.3.4 图形处理器处理数据流的数据概要结构维护 28-29
2.4 基于图形处理器的数据流处理的理论模型 29-31
2.5 本章小结 31-32
3 图形处理器单数据分位数计算方法 32-42
3.1 问题提出 32
3.2 基于图形处理器的并行分位数维护方法 32-38
3.2.1 一种适合并行计算的分位数维护方法 32-34
3.2.2 图形处理器数据流分位数并行维护方法 34-38
3.3 实验和实验结果分析 38-40
3.4 本章小结 40-42
4 图形处理器多数据流相关系数计算方法 42-59
4.1 问题提出 42
4.2 基于图形处理器的多数据流处理方法 42-48
4.2.1 跨总线的四层滑动窗口模型 42-46
4.2.2 多数据流并行计算抽象粒度 46-47
4.2.3 图形处理器多数据流并行计算框架 47-48
4.3 图形处理器多数据流相关系数并行计算方法 48-58
4.3.1 数学基础 48-50
4.3.2 基于图形处理器的多数据流相关系数整体算法 50-51
4.3.3 多数据流统计信息增量并行维护算法 51-52
4.3.4 多数据流相关系数精确并行算法 52-56
4.3.5 实验和实验结果分析 56-58
4.4 本章小结 58-59