论文 关键词：数据仓库 并行 计算 消息传递接口 商立方体
论文摘要：目前很多数据仓库的原始数据量已经超过了t字节级，在单处理机机器上运行数据量如此庞大的数据仓库是十分困难。因此，并行计算技术对于数据仓库技术的介入是无法避免的，并行计算技术为提高运算能力和存储能力这影响数据仓库性能的两大重要因素提供了技术基础。本文详细介绍了基于数据分组方法的数据仓库并行预计算和查询的方法，其主要思想是将数据仓库基表中的数据进行分割，分发到各台计算机上后，并行地对数据进行预计算，并根据预计算完成后，立方体数据存储的分布性，并行地进行查询。本文首先介绍了数据仓库和并行计算的基本概念，并根据商立方体的特点提出了基于数据分组方法的数据仓库并行预计算和查询的方法。本文对该方法的具体实现进行了描述，并分析了在刀片服务器上运行后得到的各项结果。基于数据分组方法的数据仓库预计算和查询方法的并行策略相对较简单，但在现实应用中，通过实验观察和对实验数据的分析，证明了这种方法是可行的，数据仓库的预计算性能于查询性能都得到了令人满意的提高。
第一章 绪论
随着计算机应用的普及，人们的社会活动已经越来越多地依赖于计算机的使用。人类的各种社会活动，例如商品交易、 科学 实验都产生了巨大的数据量。这些长年累月积累下来的数据量极为巨大，虽然看似杂乱无章，但是里面却隐含着社会科学和 自然 科学的各种 规律 。如何更好地去利用这些数据，从数据中寻找出这些规律来造福社会，是人们面临的另一个重要问题。wWW.11665.Com传统的信息处理方式，如数据库，是以单一的数据为中心的事务处理，它可以让人们在可以接受的时间范围内完成对数据的各种事务操作，但是对于发掘数据中的规律却是无能为力。为此人们发明了很多新的计算机技术从这些数据中寻找出其隐含的规律，数据仓库便是其中的一种。
为了更好、更快速地执行用户对数据仓库的查询，需要对原始数据集进行预计算。预计算就是将人们会在查询中希望得到的，将很多记录依照其某项属性进行某种聚集操作（和、最大、最小等等）后的结果，进行预先的计算处理。这样便可以提高查询的响应速度，减少响应时间，提高人们数据仓库的利用效率。由于预计算所产生的数据集合必须考虑到每条记录的聚合，所以产生的数据量是原始数据集的数百倍甚至千倍。人们对于预计算的计算量要求也是巨大的。
目前很多数据仓库的原始数据量已经超过了tb级，在单台机器上是根本支持不了数据量如此庞大的数据仓库，因此，并行计算技术的介入是无法避免的，它为提高运算能力和存储能力这两大重要因素提供了技术基础。并行计算是唯一能够处理这么大量信息的计算技术。
本文将研究如何把并行计算技术引入到数据仓库的预计算和查询中，并通过实验来支持这种做法的有效性。希望可以为数据仓库的并行处理技术提供一种新的思路。
1.1 目标
本文的研究目标是提出一种数据仓库并行处理技术，它使用mpi实现，能够在多种平台上运行，能有效地实现立方体预计算加速以及查询加速。
1.2 本文安排
本文的余下部分将如下安排：
第二章是介绍本文研究的相关背景，将描述本文中涉及的关于数据仓库和并行计算的概念。
第三章概括性地介绍了mpi，包括mpi标准 发展 史，mpi编程中经常使用到的点对点通信原语和通信模式以及mpi程序的基本结构。
第四章将介绍商立方体提出的目的，商立方体的特性，预计算算法以及查询算法。
第五章描述了基于数据分组方法的数据仓库并行预计算和查询方法的基本思路与实现步骤，并对该方法的正确性做了初步的证明。
第六章详细描述了并行预计算程序和并行查询程序的具体实现与工作流程。
第七章通过实验测量的数据来说明本文提出方法的有效性和对于预计算和查询性能的提高。
第八章对本文的工作进行了 总结 ，说明了本文的主要成果和存在的不足，并为进一步的工作进行了展望。
第二章 背景
自计算机发明后，人类文明进入了一个前所未有的高速发展阶段。计算机技术的应用缩短了许多新技术的研发周期，新技术往往意味着更高的生产力、更好的产品和更低的成本。计算机自身也得益于这些新技术，越来越多的商业公司和个人可以负担得起计算机的使用费用，计算机逐渐普及。
随着计算机技术应用的广泛性日益增加、性能不断地提高，加上互联网等革命性技术的出现，人们开始进入信息化社会，信息已经成为人类社会不可或缺的重要资源。社会信息化使得社会活动如：商业交易，科学实验，数据统计等所产生的数据急剧地增长，而在这些数量巨大，看似杂乱无章的数据中，隐藏着社会活动和自然科学的规律。例如人们的购买习惯、dna的作用。分析数据，学习其中的规律成了人们迫切的目标。但是，数据的数量级已经远远地超过了人脑所能处理的范围，因此，人们只能将希望寄托在计算机上。
2.1 数据仓库
面对爆炸性膨胀的数据和不断提升的应用要求，数据库技术也在不断地提高着数据库应用的作用和价值。传统的数据库技术主要擅长于提供以数据为中心，通过数据库对一个或一组数据记录进行查询和修改等的面向具体、特定应用的服务，它可以满足响应时间、数据可靠性和完整性等方面的要求。这些传统的事务处理系统已经比较成熟，在 企业 和组织中应用也十分普遍，随着各种组织的日常事务处理的信息化，数据分析和决策支持应用成了必然的趋势。如何有效地利用 历史 数据为决策分析做支持，是近年来数据处理研究领域的热点。
对数据进行分析处理的要求使得传统的数据库技术不能满足要求，为了解决这个问题，inmon[inm02]提出了数据仓库的概念。他对于数据仓库是这样定义的：数据仓库就是一个用以更好地支持企业或组织的决策分析处理、面向主题的、集成的、不可更新的、随时间不断变化的数据集合。数据仓库有以下特点：
● 面向主题（subject-oriented）：数据仓库中的数据是面向主题进行组织的。
● 集成（integrated）：数据仓库中通常集成了多个异质数据源的数据。在集成过程中，需要对数据进行清洗、转换以保证数据的一致性。
● 稳定（nonvolatile）：数据仓库中的数据是反映一段相对长时间内历史数据的内容，是不同时间数据库快照的集合，以及基于这种快照进行统计、综合和重组的导出数据。所设计的操作主要是数据查询，一般不会进行修改操作。
● 随时间变化（time-variant）：数据仓库随时间变化不断增加新的内容，删去旧的内容。
数据仓库技术在过去的一段时间内发展迅速，已经成功地应用到电信、银行、保险等行业。随着企业信息化的不断深入，这种发展还会持续。
2.1.1 联机分析处理与数据立方体
为了让决策支持人员更好地去分析处理数据仓库中的海量数据，e. codd于1993年提出了联机分析处理（olap: on-line analytical processing）的概念[ccs93a, ccs93b]。olap工具通过对信息的多个角度（维）进行快速、一致、稳定的交互访问，决策支持人员可以深入地进行观察。olap工具是为了满足更高效地进行多维分析的需求而产生的，其主要功能是根据用户所选择的分析角度，事先计算好一些辅助结构，以便在查询对能够抽取到所需要的记录。
olap系统中的数据通常会以一个多维的结构模型表现出来。表2.1是一个简单的销售数据仓库的基表（base table），基表中的一条记录称为元组（tuple），该基表中一条元组有三个属性：时间、产品名称和地点，在这里被称为维度（dimension），这些维用来表示和区分开不同的数据。销量属性是一个数值类型的度量值（measure），是人们想要去分析的数据。维度通常也会分层次（hierarchy），例如时间维度可能会分为年、月、日、季度等层次。
地点
产品名称
时间
销量
广州(gz)
篮球(b)
2007.5(m1)
20
广州(gz)
足球(f)
2007.6(m2)
15
深圳(sz)
篮球(b)
2007.5(m1)
25
表2.1销售数据仓库的基表
数据立方体（data cube）是由gray等人提出[gcb+97]。它是对所有维度的所有可能结合，根据不同聚集粒度进行group-by操作而产生的一个概括化数据集合。每一个group-by操作都与一个单元（cells）的集合相关联，数据立方体关于表2.1的所有单元都在表2.2中列出，在表中，“*”表示在这一维度中，它可以匹配到这个维度值域中的任何一个值。
上卷（roll-up）和下钻（drill-down）是数据立方体中的两种基本语义关系。一个较高聚集层次的单元可以下钻到一个较低聚集层次的单元，如：（gz, *, m1）下钻到(gz, b, m1)。一个较低聚集层次的单元可以上卷到一个较高聚集层次的单元，如：（sz, b, m1）上卷到（*, b, *）。一个立方体中的所有单元间的上卷/下钻关系构成了一个网格结构。图2.1中表现出了表2.2中的立方体网格。
地点
产品名称
时间
总和（销量）
gz
b
m1
20
gz
f
m2
15
sz
b
m1
25
gz
b
*
20
gz
*
m1
20
*
b
m1
45
…
…
…
…
sz
*
*
25
*
f
*
15
*
*
m1
45
*
*
*
60
表2.2 数据立方体中的单元
shape \* mergeformat
图2.1 数据立方体网格
2.2 并行计算
大规模科学与工程计算应用使得人们对计算机性能要求不断提高。例如天气预报、空间模拟、石油勘探等科学计算对计算机的性能要求可以说是无穷无尽的。单台作业的计算机是根本无法满足这种计算需求的，因此人们便开始尝试应用新技术使得多台单独作业的计算机可以协调地共同进行工作，并行计算机便开始逐步走入人们的视野。
并行计算是伴随着并行计算机的出现，在近三十年来迅速发展的一门交叉学科，是指在并行计算机上，将一个应用分解成多个子任务，分配给不同的处理器，各个处理器之间相互协同，并行地执行子任务，从而达到加快求解速度，或者提高求解应用问题规模的目的[zcml06]。并行计算必须具备三个基本条件：
（1）并行计算机。并行计算机至少浩瀚两台或两台以上处理机，这些处理机通过互联 网络 相互连接，互相通信。
（2）应用问题必须具有并行度。应用可以分解为多个子任务，并且这些子任务可以并行地执行。
（3）并行编程。在并行 计算 机提供的并行编程环境上，具体实现并行算法。
2.2.1 并行编程模式
编程模式是程序员和计算机之间的界面，它是建立在计算机体系结构之上的程序的抽象，它定义了程序的设计与其实现之间的接口。在并行计算机 发展 的 历史 过程中，人们提出过许多适合不同并行体系结构的编程模式[st98]，经过时间的淘汰，目前比较流行的并行编程模式基本上趋向于以下三种[chen99, du01, zcml06]：
● 消息传递模式：程序的执行分为多个进程，用户需要显式地为每个进程分配数据和指令。进程都在自己的私有空间中运行，显式地通过发送和接收消息进行交互。有同步通信和异步通信两种方式。消息传递模式为程序员提供了更灵活的控制手段和表达并行的方法，因此消息传递并行程序往往能达到高的执行效率。但由于程序员需要显式地指定进程间的信息交换、协调和控制，编写基于消息传递模式的并行计算程序对于程序员的能力要求比较高。尽管如此，消息传递仍然是目前最常用的并行编程模式。mpi[mpi03a, mpi03b]和并行虚拟机[pvm07]是其中两种广泛使用的消息传递编程标准库。
● 共享存储模式：程序是由运行在一个公共地址空间的一组进程所组成。用户无需进行数据分配，每个进程相对独立地运行，进程间的通信通过存放在公共存储器中的共享变量进行。所以保持变量操作的一致性和同步性是使用这种编程模式时必须考虑的关键问题。基于该模式通过手工或编译器将串行程序并行化，相对比基于消息传递模式更容易，对程序员要求也相对较低。目前使用较多的共享存储模式的实现有ieee标准委员会的多线程接口[ptp06]和openmp标准委员会的openmp[omp07]。
● 数据并行模式：程序所处理的数据被划分为多个小块，分配到系统中的各个处理单元上，每个处理单元执行相同的程序，不需要显示同步。数据并行模式的实现层次较高，一般由编译器实现，程序员只需指明怎样的并行操作和操作的对象即可。高性能fortran[hpf06]是一种使用较多的数据并行语言。
2.2.2 并行计算机体系结构
并行计算机的分类是随着并行计算机的发展而发展的。在并行计算技术发展的不同阶段，各个计算机生产厂商发明了各种各样把多个处理器（处理单元）整合在一起的方法，从而使得系统的整体计算能力有所提高。这些技术经过不断地发展，逐渐成熟并衍生出技术分支，同时也产生出许多不同的并行计算机体系结构。
描述这些体系结构特征的最常用的方法是flynn分类法[fly72]。它根据指令流数目和数据流数目来分类，将计算机分成了4类：sisd、simd、misd和mimd。其中，属于并行计算机的有：
(1) 单指令多数据流（simd）：同一指令被复制成多份，并发地发送给多个处理器，形成多个独立的进程，每个进程都具有自己的数据流（如图2.2所示），具有同步性和确定性。
shape \* mergeformat
shape \* mergeformat
图2.2 simd体系结构
(2) 多指令多数据流（mimd）：在mimd系统中，每个处理器都具有自己的指令来操作自己的数据，与其他处理器无关。指令流可以同步或异步地执行，指令流的执行具有确定性和不确定性。如图2.3所示。
shape \* mergeformat
图2.3 mimd体系结构
随着技术的发展，曾经风行的simd并行计算机已经退出了历史舞台，mimd体系的并行机已经占据了统治性的地位。目前世界上流行的并行计算机系统基本上都是属于mimd计算机。
在mimd的分类中，按照内存访问模型、微处理器和互联 网络 的不同，并行计算机可分为以下5类[zcml06]：
(1) 对称多处理共享存储并行计算机（symmetric multi-processing, smp）:smp系统中任何处理器都可以直接访问任何存储模块中的存储单元和i/o模块，且各自间的访问延迟、带宽都一样。整个系统只有一个操作系统驻留在共享存储器中，可以动态地分配进程到各个处理器，而且每个进程都是使用共享的数据存储区来完成通信，通信的延迟较低。但是由于各个处理单元之间的耦合程度较高，所以只要总线、存储器或操作系统其中一个出错，便会导致整个系统的崩溃，而且系统的可扩张性较差。支持消息传递、共享存储并行程序设计。
(2) 分布式共享存储并行计算机（distributed shared memory, dsm）：系统以节点为单位，每个节点包含一个或多个cpu，每个cpu有局部的cache。存储在物理上分布，但在逻辑上是统一的内存地址空间。各个节点既可以直接访问本地的局部存储单元，也进行访问其他节点的局部存储单元，但远端访问必须通过高性能互联网络，性能远不如本地访问。dsm系统的可扩展性强，可扩展至数百个节点。支持消息传递、共享存储并行程序设计。
(3) 集群系统（cluster）：系统由节点构成，每个节点包含2－4个商用处理器，节点内部共享存储。各节点通过交换机连接。当计算机是运行linux操作系统的pc机时，这类集群则成为beowulf[beo07]集群。集群系统只支持消息传递并行程序设计。目前集群系统占据着主流地位，在世界超级计算机500强中，占据了大多数的席位。
(4) 星群系统（constellation）：系统由节点构成，每个节点是一台smp或dsm子系统，包含的处理器数量巨大，计算功能十分强大。节点间通过集群交换机连接，节点间分布存储。各个节点运行专用的操作系统、编译系统和作业管理系统。与集群系统所不同的是，星群系统可以支持消息传递和共享存储两种并行编程模式：在节点间使用消息传递，节点内部则可以使用共享存储模式，这种混合模式充分利用了两种编程模式的特点，因此被认为是最有效率的编程模式。
(5) 大规模并行计算机系统(massively parallel processing, mpp)：由数百个乃至数千个结算节点和i/o节点组成，每个节点相对独立，并拥有一个或多个微处理器。这些节点的局部cache通过局部总线或互联网络与局部内存模块和i/o设备相连接。互联网络与集群互联网络不同，一般采用由多种静态拓扑结构耦合而成的混合拓扑结构，通信延迟和通信带宽明显优于集群系统。每个节点均拥有不同的操作系统，允许用户在某个特定节点上作业。各节点间内存模块相互独立且没有全局内存统一编址。如果要直接访问其他节点的内存则需要有操作系统的支持。mpp支持消息传递或高性能fortran并行程序设计，但不支持共享存储模式。
各种并行计算机对于消息传递、共享存储、数据并行三种编程模式的支持在表2.3中列出。
smp
dsm
集群
星群
mpp
消息传递
√
√
√
√
√
共享存储
√
√
x
√
x
数据并行
√
√
x
x
√
表2.3 各种并行计算机对与编程模式的支持
2.3 小结
数据仓库的应用日渐广泛，但是数据量的增长使得olap系统的效率逐渐低下和数据立方体的容量呈指数上升。数据立方体的预计算需要大量的计算能力和存储空间，随着并行计算技术的发展，数据仓库将会更多地使用到并行计算技术。并行计算技术带来的不仅仅是计算能力和存储空间上的扩展，并行计算技术对于计算机性能的扩展使得更多更复杂的应用技术得以实现，扩展数据仓库的功能。
第三章 mpi
消息传递是一个广泛应用在并行计算机（特别是分布存储并行机：dsm、集群、星群和mpp）上的模式。自从20世纪80年代以来，经过10余年的发展，很多基于消息传递的应用系统有了长足的进步。由于基于消息传递模式的系统很多都具有效率高、适用性强等优点，所以人们认为通过定义一个核心库程序的语法与语义，将有益于广大用户，将可以在更大范围的机器上有效实现消息传递模式。本章的主要内容是介绍目前最为流行的基于消息传递模式的编程环境：mpi。在以下的章节中会介绍mpi的产生、mpi的实现和关于mpi编程的基本概念。
3.1 mpi的产生
早期的商用并行计算机很多是基于消息传递的，因为它的成本相对于共享存储的机器更低。人们开发了基于消息传递模式的多种不同实现的消息传递程序库，但是这些程序库就像汇编语言一样，每个硬件制造商提供的程序库都与其他的不兼容。这些不同的程序库之间的实质上的差别其实很小，有的只是语法上的不同而已，但是要想将消息传递程序从一个库移植到另一个库中时，程序往往要作出很大程度的修改。由此人们便意识到需要指定一个消息传递程序设计的接口标准，以便并行计算 科学 的进一步发展，消息传递接口（mpi：message passing interface）便是这个标准的产物。
mpi的标准化开始于1992年4月底，在美国弗吉尼亚州的williamsburg召开的“分布式存储环境中消息传递标准”的讨论会上[mpi03a]。mpi1.0标准由dongarra, hempel, hey以及walker在1992年11月提出的初始草案和于1993年2月完成的修订版本所规定。为了促进mpi的发展，mpi 论坛 （mpi forum）因此而诞生，负责mpi的完善和维护工作。
mpi-2[mpi03b]是在对原来mpi作了重大扩充基础上，于1997年7月推出的mpi扩展部分，原来的mpi各种版本改称为mpi-1。mpi-2的扩充很多，但最主要的是以下三部分：并行i/o，远程存储访问和动态进程管理。
mpi的标准化是多个组织和个人的努力成果，他们主要是来自美国和欧洲，大约60名来自40个不同组织的工作人员为此付出了辛勤的劳动。这其中包括了并行计算机大多数的并行计算机生产商、大学、政府实验室和工厂的研究人员。他们有venus (ibm) 、nx/2 (intel) express (parasoft)、 vertex(ncube)、 p4 (anl)、 parmacs (anl)， 还包括zipcode (msu)、 chimp (edinburgh university)、 pvm (ornl, utk, emory u.) 、chameleon (anl)、 picl (anl)等。
