《毕业设计（论文）基于数据分组方法的数据仓库并行预计算和查询.doc》由会员分享，可在线阅读，更多相关《毕业设计（论文）基于数据分组方法的数据仓库并行预计算和查询.doc（41页珍藏版）》请在三一办公上搜索。
1、基于数据分组方法的数据仓库并行预计算和查询论文关键词：数据仓库并行计算消息传递接口商立方体论文摘要：目前很多数据仓库的原始数据量已经超过了T字节级，在单处理机机器上运行数据量如此庞大的数据仓库是十分困难。因此，并行计算技术对于数据仓库技术的介入是无法避免的，并行计算技术为提高运算能力和存储能力这影响数据仓库性能的两大重要因素提供了技术基础。本文详细介绍了基于数据分组方法的数据仓库并行预计算和查询的方法，其主要思想是将数据仓库基表中的数据进行分割，分发到各台计算机上后，并行地对数据进行预计算，并根据预计算完成后，立方体数据存储的分布性，并行地进行查询。本文首先介绍了数据仓库和并行计算的基本概念，
2、并根据商立方体的特点提出了基于数据分组方法的数据仓库并行预计算和查询的方法。本文对该方法的具体实现进行了描述，并分析了在刀片服务器上运行后得到的各项结果。基于数据分组方法的数据仓库预计算和查询方法的并行策略相对较简单，但在现实应用中，通过实验观察和对实验数据的分析，证明了这种方法是可行的，数据仓库的预计算性能于查询性能都得到了令人满意的提高。第一章 绪论 随着计算机应用的普及，人们的社会活动已经越来越多地依赖于计算机的使用。人类的各种社会活动，例如商品交易、科学实验都产生了巨大的数据量。这些长年累月积累下来的数据量极为巨大，虽然看似杂乱无章，但是里面却隐含着社会科学和自然科学的各种规律。如何更
3、好地去利用这些数据，从数据中寻找出这些规律来造福社会，是人们面临的另一个重要问题。传统的信息处理方式，如数据库，是以单一的数据为中心的事务处理，它可以让人们在可以接受的时间范围内完成对数据的各种事务操作，但是对于发掘数据中的规律却是无能为力。为此人们发明了很多新的计算机技术从这些数据中寻找出其隐含的规律，数据仓库便是其中的一种。 为了更好、更快速地执行用户对数据仓库的查询，需要对原始数据集进行预计算。预计算就是将人们会在查询中希望得到的，将很多记录依照其某项属性进行某种聚集操作（和、最大、最小等等）后的结果，进行预先的计算处理。这样便可以提高查询的响应速度，减少响应时间，提高人们数据仓库的利用
4、效率。由于预计算所产生的数据集合必须考虑到每条记录的聚合，所以产生的数据量是原始数据集的数百倍甚至千倍。人们对于预计算的计算量要求也是巨大的。 目前很多数据仓库的原始数据量已经超过了TB级，在单台机器上是根本支持不了数据量如此庞大的数据仓库，因此，并行计算技术的介入是无法避免的，它为提高运算能力和存储能力这两大重要因素提供了技术基础。并行计算是唯一能够处理这么大量信息的计算技术。 本文将研究如何把并行计算技术引入到数据仓库的预计算和查询中，并通过实验来支持这种做法的有效性。希望可以为数据仓库的并行处理技术提供一种新的思路。1.1目标 本文的研究目标是提出一种数据仓库并行处理技术，它使用MPI实
5、现，能够在多种平台上运行，能有效地实现立方体预计算加速以及查询加速。1.2本文安排 本文的余下部分将如下安排：第二章是介绍本文研究的相关背景，将描述本文中涉及的关于数据仓库和并行计算的概念。第三章概括性地介绍了MPI，包括MPI标准发展史，MPI编程中经常使用到的点对点通信原语和通信模式以及MPI程序的基本结构。第四章将介绍商立方体提出的目的，商立方体的特性，预计算算法以及查询算法。第五章描述了基于数据分组方法的数据仓库并行预计算和查询方法的基本思路与实现步骤，并对该方法的正确性做了初步的证明。第六章详细描述了并行预计算程序和并行查询程序的具体实现与工作流程。第七章通过实验测量的数据来说明本文
6、提出方法的有效性和对于预计算和查询性能的提高。 第八章对本文的工作进行了总结，说明了本文的主要成果和存在的不足，并为进一步的工作进行了展望。第二章 背景 自计算机发明后，人类文明进入了一个前所未有的高速发展阶段。计算机技术的应用缩短了许多新技术的研发周期，新技术往往意味着更高的生产力、更好的产品和更低的成本。计算机自身也得益于这些新技术，越来越多的商业公司和个人可以负担得起计算机的使用费用，计算机逐渐普及。随着计算机技术应用的广泛性日益增加、性能不断地提高，加上互联网等革命性技术的出现，人们开始进入信息化社会，信息已经成为人类社会不可或缺的重要资源。社会信息化使得社会活动如：商业交易，科学实验
7、，数据统计等所产生的数据急剧地增长，而在这些数量巨大，看似杂乱无章的数据中，隐藏着社会活动和自然科学的规律。例如人们的购买习惯、DNA的作用。分析数据，学习其中的规律成了人们迫切的目标。但是，数据的数量级已经远远地超过了人脑所能处理的范围，因此，人们只能将希望寄托在计算机上。2.1 数据仓库 面对爆炸性膨胀的数据和不断提升的应用要求，数据库技术也在不断地提高着数据库应用的作用和价值。传统的数据库技术主要擅长于提供以数据为中心，通过数据库对一个或一组数据记录进行查询和修改等的面向具体、特定应用的服务，它可以满足响应时间、数据可靠性和完整性等方面的要求。这些传统的事务处理系统已经比较成熟，在企业和
8、组织中应用也十分普遍，随着各种组织的日常事务处理的信息化，数据分析和决策支持应用成了必然的趋势。如何有效地利用历史数据为决策分析做支持，是近年来数据处理研究领域的热点。 对数据进行分析处理的要求使得传统的数据库技术不能满足要求，为了解决这个问题，InmonInm02提出了数据仓库的概念。他对于数据仓库是这样定义的：数据仓库就是一个用以更好地支持企业或组织的决策分析处理、面向主题的、集成的、不可更新的、随时间不断变化的数据集合。数据仓库有以下特点： 面向主题（Subject-oriented）：数据仓库中的数据是面向主题进行组织的。 集成（Integrated）：数据仓库中通常集成了多个异质数据
9、源的数据。在集成过程中，需要对数据进行清洗、转换以保证数据的一致性。 稳定（Nonvolatile）：数据仓库中的数据是反映一段相对长时间内历史数据的内容，是不同时间数据库快照的集合，以及基于这种快照进行统计、综合和重组的导出数据。所设计的操作主要是数据查询，一般不会进行修改操作。 随时间变化（Time-variant）：数据仓库随时间变化不断增加新的内容，删去旧的内容。数据仓库技术在过去的一段时间内发展迅速，已经成功地应用到电信、银行、保险等行业。随着企业信息化的不断深入，这种发展还会持续。2.1.1 联机分析处理与数据立方体 为了让决策支持人员更好地去分析处理数据仓库中的海量数据，E. C
10、odd于1993年提出了联机分析处理（OLAP: On-Line Analytical Processing）的概念CCS93a, CCS93b。OLAP工具通过对信息的多个角度（维）进行快速、一致、稳定的交互访问，决策支持人员可以深入地进行观察。OLAP工具是为了满足更高效地进行多维分析的需求而产生的，其主要功能是根据用户所选择的分析角度，事先计算好一些辅助结构，以便在查询对能够抽取到所需要的记录。OLAP系统中的数据通常会以一个多维的结构模型表现出来。表2.1是一个简单的销售数据仓库的基表（base table），基表中的一条记录称为元组（tuple），该基表中一条元组有三个属性：时间、产
11、品名称和地点，在这里被称为维度（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操作而产生的一个概括化数据集合。每
12、一个group-by操作都与一个单元（cells）的集合相关联，数据立方体关于表2.1的所有单元都在表2.2中列出，在表中，“*”表示在这一维度中，它可以匹配到这个维度值域中的任何一个值。上卷（roll-up）和下钻（drill-down）是数据立方体中的两种基本语义关系。一个较高聚集层次的单元可以下钻到一个较低聚集层次的单元，如：（GZ, *, M1）下钻到(GZ, B, M1)。一个较低聚集层次的单元可以上卷到一个较高聚集层次的单元，如：（SZ, B, M1）上卷到（*, B, *）。一个立方体中的所有单元间的上卷/下钻关系构成了一个网格结构。图2.1中表现出了表2.2中的立方体网格。地点
13、产品名称时间总和（销量）GZBM120GZFM215SZBM125GZB*20GZ*M120*BM145SZ*25*F*15*M145*60表2.2 数据立方体中的单元SHAPE * MERGEFORMAT 图2.1 数据立方体网格2.2 并行计算 大规模科学与工程计算应用使得人们对计算机性能要求不断提高。例如天气预报、空间模拟、石油勘探等科学计算对计算机的性能要求可以说是无穷无尽的。单台作业的计算机是根本无法满足这种计算需求的，因此人们便开始尝试应用新技术使得多台单独作业的计算机可以协调地共同进行工作，并行计算机便开始逐步走入人们的视野。并行计算是伴随着并行计算机的出现，在近三十年来迅速发展
14、的一门交叉学科，是指在并行计算机上，将一个应用分解成多个子任务，分配给不同的处理器，各个处理器之间相互协同，并行地执行子任务，从而达到加快求解速度，或者提高求解应用问题规模的目的ZCML06。并行计算必须具备三个基本条件： （1）并行计算机。并行计算机至少浩瀚两台或两台以上处理机，这些处理机通过互联网络相互连接，互相通信。（2）应用问题必须具有并行度。应用可以分解为多个子任务，并且这些子任务可以并行地执行。（3）并行编程。在并行计算机提供的并行编程环境上，具体实现并行算法。2.2.1 并行编程模式 编程模式是程序员和计算机之间的界面，它是建立在计算机体系结构之上的程序的抽象，它定义了程序的设计
15、与其实现之间的接口。在并行计算机发展的历史过程中，人们提出过许多适合不同并行体系结构的编程模式ST98，经过时间的淘汰，目前比较流行的并行编程模式基本上趋向于以下三种Chen99, Du01, ZCML06： 消息传递模式：程序的执行分为多个进程，用户需要显式地为每个进程分配数据和指令。进程都在自己的私有空间中运行，显式地通过发送和接收消息进行交互。有同步通信和异步通信两种方式。消息传递模式为程序员提供了更灵活的控制手段和表达并行的方法，因此消息传递并行程序往往能达到高的执行效率。但由于程序员需要显式地指定进程间的信息交换、协调和控制，编写基于消息传递模式的并行计算程序对于程序员的能力要求比较
16、高。尽管如此，消息传递仍然是目前最常用的并行编程模式。MPIMPI03a, MPI03b和并行虚拟机PVM07是其中两种广泛使用的消息传递编程标准库。 共享存储模式：程序是由运行在一个公共地址空间的一组进程所组成。用户无需进行数据分配，每个进程相对独立地运行，进程间的通信通过存放在公共存储器中的共享变量进行。所以保持变量操作的一致性和同步性是使用这种编程模式时必须考虑的关键问题。基于该模式通过手工或编译器将串行程序并行化，相对比基于消息传递模式更容易，对程序员要求也相对较低。目前使用较多的共享存储模式的实现有IEEE标准委员会的多线程接口PTP06和OpenMP标准委员会的OpenMPOMP0
17、7。 数据并行模式：程序所处理的数据被划分为多个小块，分配到系统中的各个处理单元上，每个处理单元执行相同的程序，不需要显示同步。数据并行模式的实现层次较高，一般由编译器实现，程序员只需指明怎样的并行操作和操作的对象即可。高性能FortranHPF06是一种使用较多的数据并行语言。2.2.2 并行计算机体系结构 并行计算机的分类是随着并行计算机的发展而发展的。在并行计算技术发展的不同阶段，各个计算机生产厂商发明了各种各样把多个处理器（处理单元）整合在一起的方法，从而使得系统的整体计算能力有所提高。这些技术经过不断地发展，逐渐成熟并衍生出技术分支，同时也产生出许多不同的并行计算机体系结构。描述这些
18、体系结构特征的最常用的方法是Flynn分类法Fly72。它根据指令流数目和数据流数目来分类，将计算机分成了4类：SISD、SIMD、MISD和MIMD。其中，属于并行计算机的有：(1) 单指令多数据流（SIMD）：同一指令被复制成多份，并发地发送给多个处理器，形成多个独立的进程，每个进程都具有自己的数据流（如图2.2所示），具有同步性和确定性。SHAPE * MERGEFORMAT SHAPE * MERGEFORMAT 图2.2 SIMD体系结构(2) 多指令多数据流（MIMD）：在MIMD系统中，每个处理器都具有自己的指令来操作自己的数据，与其他处理器无关。指令流可以同步或异步地执行，指令
19、流的执行具有确定性和不确定性。如图2.3所示。SHAPE * MERGEFORMAT 图2.3 MIMD体系结构随着技术的发展，曾经风行的SIMD并行计算机已经退出了历史舞台，MIMD体系的并行机已经占据了统治性的地位。目前世界上流行的并行计算机系统基本上都是属于MIMD计算机。在MIMD的分类中，按照内存访问模型、微处理器和互联网络的不同，并行计算机可分为以下5类ZCML06：(1) 对称多处理共享存储并行计算机（Symmetric Multi-Processing, SMP）:SMP系统中任何处理器都可以直接访问任何存储模块中的存储单元和I/O模块，且各自间的访问延迟、带宽都一样。整个系统
20、只有一个操作系统驻留在共享存储器中，可以动态地分配进程到各个处理器，而且每个进程都是使用共享的数据存储区来完成通信，通信的延迟较低。但是由于各个处理单元之间的耦合程度较高，所以只要总线、存储器或操作系统其中一个出错，便会导致整个系统的崩溃，而且系统的可扩张性较差。支持消息传递、共享存储并行程序设计。(2) 分布式共享存储并行计算机（Distributed Shared Memory, DSM）：系统以节点为单位，每个节点包含一个或多个CPU，每个CPU有局部的cache。存储在物理上分布，但在逻辑上是统一的内存地址空间。各个节点既可以直接访问本地的局部存储单元，也进行访问其他节点的局部存储单元
21、，但远端访问必须通过高性能互联网络，性能远不如本地访问。DSM系统的可扩展性强，可扩展至数百个节点。支持消息传递、共享存储并行程序设计。：系统由节点构成，每个节点包含24个商用处理器，节点内部共享存储。各节点通过交换机连接。当计算机是运行Linux操作系统的PC机时，这类集群则成为BeowulfBeo07集群。集群系统只支持消息传递并行程序设计。目前集群系统占据着主流地位，在世界超级计算机500强中，占据了大多数的席位。 (4) 星群系统（Constellation）：系统由节点构成，每个节点是一台SMP或DSM子系统，包含的处理器数量巨大，计算功能十分强大。节点间通过集群交换机连接，节点间分
22、布存储。各个节点运行专用的操作系统、编译系统和作业管理系统。与集群系统所不同的是，星群系统可以支持消息传递和共享存储两种并行编程模式：在节点间使用消息传递，节点内部则可以使用共享存储模式，这种混合模式充分利用了两种编程模式的特点，因此被认为是最有效率的编程模式。(5) 大规模并行计算机系统(Massively Parallel Processing, MPP)：由数百个乃至数千个结算节点和I/O节点组成，每个节点相对独立，并拥有一个或多个微处理器。这些节点的局部cache通过局部总线或互联网络与局部内存模块和I/O设备相连接。互联网络与集群互联网络不同，一般采用由多种静态拓扑结构耦合而成的混合
23、拓扑结构，通信延迟和通信带宽明显优于集群系统。每个节点均拥有不同的操作系统，允许用户在某个特定节点上作业。各节点间内存模块相互独立且没有全局内存统一编址。如果要直接访问其他节点的内存则需要有操作系统的支持。MPP支持消息传递或高性能Fortran并行程序设计，但不支持共享存储模式。 各种并行计算机对于消息传递、共享存储、数据并行三种编程模式的支持在表2.3中列出。SMPDSM集群星群MPP消息传递共享存储XX数据并行XX表2.3 各种并行计算机对与编程模式的支持2.3 小结 数据仓库的应用日渐广泛，但是数据量的增长使得OLAP系统的效率逐渐低下和数据立方体的容量呈指数上升。数据立方体的预计算需
24、要大量的计算能力和存储空间，随着并行计算技术的发展，数据仓库将会更多地使用到并行计算技术。并行计算技术带来的不仅仅是计算能力和存储空间上的扩展，并行计算技术对于计算机性能的扩展使得更多更复杂的应用技术得以实现，扩展数据仓库的功能。第三章 MPI 消息传递是一个广泛应用在并行计算机（特别是分布存储并行机：DSM、集群、星群和MPP）上的模式。自从20世纪80年代以来，经过10余年的发展，很多基于消息传递的应用系统有了长足的进步。由于基于消息传递模式的系统很多都具有效率高、适用性强等优点，所以人们认为通过定义一个核心库程序的语法与语义，将有益于广大用户，将可以在更大范围的机器上有效实现消息传递模式
25、。本章的主要内容是介绍目前最为流行的基于消息传递模式的编程环境：MPI。在以下的章节中会介绍MPI的产生、MPI的实现和关于MPI编程的基本概念。3.1 MPI的产生 早期的商用并行计算机很多是基于消息传递的，因为它的成本相对于共享存储的机器更低。人们开发了基于消息传递模式的多种不同实现的消息传递程序库，但是这些程序库就像汇编语言一样，每个硬件制造商提供的程序库都与其他的不兼容。这些不同的程序库之间的实质上的差别其实很小，有的只是语法上的不同而已，但是要想将消息传递程序从一个库移植到另一个库中时，程序往往要作出很大程度的修改。由此人们便意识到需要指定一个消息传递程序设计的接口标准，以便并行计算
26、科学的进一步发展，消息传递接口（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-2MPI03b是在对原来MPI作了重大扩充基础上，于1997年7月推出的MPI扩展部分，原来的M
27、PI各种版本改称为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)、
28、PVM (ORNL, UTK, Emory U.) 、Chameleon (ANL)、 PICL (ANL)等。MPI建立了一套有效的、可移植的、灵活的标准，并已经成为国际上应用最为广泛的并行程序设计平台。MPI可以使用于几乎所有的并行计算环境享存储和分布式存储、MPP、Cluster）和多个操作系统（UNIX、WindowsNT、Linux）。 3.2 MPI的特点与实现 如上一小节所述，MPI是一个消息传递模式下并行程序设计的标准规范。在标准的程序设计语言的基础上，加入实现进程间通信的MPI消息传递函数以及其他并行计算环境设置函数，就构成了MPI并行程序设计所依赖的并行编程环境。对于MPI
29、的定义，需要理解以下三个方面Du01：(1) MPI是一个库而不是一门语言。MPI库可以被FORTRAN77/C/Fortran90/C+调用从语法上说它遵守所有对库函数/过程的调用规则和一般的函数/过程没有什么区别。(2) MPI是一种标准或规范的代表,而不特指某一个对它的具体实现。迄今为止所有的并行计算机制造商都提供对MPI的支持，一个正确的MPI程序，可以不加修改地在所有并行机上运行。(3) MPI是一种消息传递编程模式并成为这种编程模式的代表和事实上的标准。MPI虽然很庞大，但是它的最终目的是服务于进程间通信这一目标的。由此可见，MPI是一个标准。就如同世界上其他标准一样，都会出现很多
30、基于同一标准的不同产品，MPI也不例外。很多研究机构或者公司根据MPI的标准和自己的实际情况，编写出了不同的支持MPI程序的编程环境，而这些编程环境在MPI的世界里就被称为MPI实现。目前比较重要的MPI实现有以下两种： MPICHMPI07。MPICH是一种最重要的MPI实现，是目前使用最广泛的免费MPI系统，大部分集群系统上的并行环境是MPICH。它由美国Argonne国家实验室和MSU共同进行维护。支持几乎所有Linux/UNIX以及Windows9x，NT，2000和XP系统。而且每当MPI推出新的版本时，就会有相应的MPICH实现版本。 LAMLAM07。由美国Ohio State
31、University开发，主要用于异构的计算机网络计算系统。3.3 MPI编程的基本概念 一个MPI并行程序由一组进程或线程所组成。这些进程或线程可以运行在相同的机器上，也可以运行在不同的机器上。在MPI中，一个独立参与通信的个体被定义为一个进程。每个进程所运行的代码并不需要是同样的，进程间的通信是通过调用MPI通信原语来完成。在典型情况下，每个进程都是在自己特有的地址空间中运行，尽管有时在SMP上的MPI程序并不如此。MPI程序中的每个进程都有一个序号，用于在进程组（由MPI程序中部分或全部进程所构成的一个集合）中标识该进程，这个序号被称为进程号，取值范围由0开始。MPI程序中进程间通信是通
32、过通信器（communicator）进行的，通信器提供了进程间通信的基本环境。MPI程序在启动时会自动创建两个通信器：MPI_COMM_WORLD和MPI_COMM_SELF。前者包含程序运行时的所有进程，后者则是由每个进程独自构成、仅包含自己的通信器。在MPI程序中，一个MPI进程由通信器和进程在该通信器中的进程号唯一标识，同一进程可以在不同通信器中有不同的进程号。进程可以通过调用MPI_Comm_rank函数来获得本进程在某指定通信器中的进程号。3.3.1 MPI的点对点通信 通信器使得进程间可以通过消息或同步操作来完成通信。消息指在进程间进行的一次数据交换，在MPI中，消息一般包含以下一
33、些内容：通信器、源进程、目的进程、消息标签和数据。MPI进程中使用得最频繁，最基本的一种通信模式就是一对进程相互之间进行通信，也就是一个进程发送消息，另一个进程接收消息，这种通信方式在MPI中被称作点对点通信（point to point communication）。MPI有两大类型的点对点通信函数，一种称为阻塞式（blocking），另一种则是非阻塞式（unblocking）。 阻塞式通信：阻塞式函数会等到通信操作实际完成，或者至少通信所涉及的数据已经被MPI环境处理好之后才会返回。如MPI_Send和MPI_Recv，分别是阻塞式的发送和接收函数。MPI_Send函数返回之后，表明消息已
34、经发送完毕或者已经被MPI环境处理完毕，随后对于发送缓冲区的修改不会对已经发出的消息有所影响。而MPI_Recv函数返回后，表明消息已经接收完毕并且可以立即使用。 非阻塞式通信：非阻塞式函数在调用后会立即返回，而实际的消息传递工作由MPI环境在后台执行。非阻塞式函数的命名是在阻塞式函数名的MPI_前缀之后加上一个“I”，如MPI_Isend和MPI_Irecv则是MPI_Send和MPI_Recv的对应非阻塞式通信版本。在调用非阻塞式函数之后，进程可以调用MPI_Wait函数来等待通信操作的完成，或者可以进行其他的计算工作，而不必将CPU时间浪费在通信上，但这时不能对相关的数据缓冲区进行操作。
35、因为当前操作可能会与正在后台进行的通信发生冲突，产生错误使得程序出问题。要检测通信操作是否实际完成，应该调用MPI_Test函数来查询通信操作的完成情况。在MPI中，对于点对点通信，也存在着4种发送模式。这4种模式的对应函数名称不同，但参数表是一样的，它们之间的差异，存在于它们发送消息的方式和对接收方的状态要求的不同。这4种模式分别是：标准模式、缓冲模式、同步模式和就绪模式。 标准模式：当消息长度小于或等于MPI环境预留的数据缓冲区大小时，MPI环境会将消息复制到缓冲区，然后立即返回。否则会当部分或全部消息发送完成后才返回。标准模式下，发送操作的完成需要与接收方联络。 缓冲模式：MPI环境将消
36、息复制到一个用户提供的缓冲区中，然后就立即返回，消息由MPI环境在后台执行。用户必须确保所提供的缓冲区能够容下将要发送的消息。缓冲模式下的发送操作不需要与接收方联络便可立即完成。 同步模式：同步模式是基于标准模式上，增加了一个要求。它要求确认接收方已经开始接收数据后函数调用才返回。 就绪模式：调用就绪模式发送时必须确保接收方已经正在等待接收该消息，不然就会产生错误。3.3.2 MPI程序结构 下面是C/C+语言MPI程序的典型结构：#include mpi.h.int main(int argc, char *argv) int myrank, numprocs; MPI_Init(&argc
37、, &argv); MPI_Comm_size(MPI_COMM_WORLD, &numprocs); MPI_Comm_rank(MPI_COMM_WORLD, &myrank); . MPI_Finalize(); . return 0;表3.1 MPI程序基本结构C/C+语言的MPI程序必须包含MPI的头文件mpi.h，以获得MPI函数的原型说明和MPI的预定义数据类型和常量。在使用C+作为MPI程序编程语言的时候，在编译程序时可能会遇到以下的出错信息：“SEEK_SET is #defined but must not be for the C+ binding of MPI”这个问题
38、是由于stdio.h和MPI C+接口同时都使用了SEEK_SET，SEEK_CUR，SEEK_END这些全局变量，这是MPI-2标准中的一个bug。要解决这个问题，一般会在#include “mpi.h”这句代码前加上以下三句：#undef SEEK_SET#undef SEEK_END#undef SEEK_CURMPI_Init函数用于初始化MPI系统环境。该函数应该在调用其他所有MPI函数之前（除了MPI_Initialized）调用，不然MPI环境还没建立，其他函数也无法运行。命令行参数argc和argv可以传递给MPI_Init，因为有时可以通过这些参数将运行进程的相关信息传递给M
39、PI程序。一般来说，调用MPI_Init(0, 0)也是足够的了。函数MPI_Comm_size和MPI_Comm_rank分别返回指定通信器中的进程数目和本进程的进程号。在这个例子中，使用的通信器是MPI_COMM_WORLD，它包含了所有进程。MPI_Finalize函数是用来退出MPI系统环境的。调用它之后便不能再调用任何其他的MPI函数了。程序的主体运行部分一般是在MPI_Finalize之前。进程可以通过myrank变量判断自己是哪个进程来执行不同进程所应该做的工作。3.3.3 MPI编程的主从模式 构成并行程序的进程中有一个主进程（通常是进程0）其余为从进程。主进程与从进程的分工是
40、不同的。主进程的工作一般负责整个并行程序的控制，分配数据和任务给从进程，从进程负责数据的处理和计算工作，同时主进程也可以参与数据的处理和计算工作。3.4 小结 MPI的一个最重要的特点就是免费和源代码开放，MPI可以被迅速接受和它为自己定下的高效率、方便移植和功能强大三个主要目标密不可分。它采用广为使用的语言FORTRAN和C/C+进行绑定也是它成功的一个重要因素，当然MPI的成功还因为它总结和吸收了前期大量消息传递系统的经验。一个成功的标准是需要大量的实践和艰苦的努力的，MPI就是这种实践和努力的结果。第四章 商立方体 联机分析处理（OLAP）由于要计算复杂的聚集函数，有很多的查询要从磁盘读
41、取大量的数据，而OLAP的交互特性要求系统能快速地响应查询。为了解决这对矛盾，Gray等人提出了数据立方体（Data Cube）GCB+97。数据立方体概括了可能提出的所有的查询类型，并且将查询结果预先计算出来保存到磁盘。在响应查询时，通过查询重写把用户的查询转换为对某一个实例化视图的查询，极大地提高了查询响应速度。近年来，随着数据仓库应用的广泛，数据仓库的数据量也越来越大，使得数据立方体的数据量也相应地急剧增加。数据立方体存在一个明显的缺陷：由于需要计算多个聚集函数对于所有可聚合属性的集合，数据立方体需要大量的计算和巨大的磁盘存储空间，不能很好地适用于多维度的场合。因此，减少数据立方体所占用
42、的空间成为了一个关键问题。对此，人们纷纷提出了多种数据立方体的数据压缩技术。其中一类是基于数据立方体单元间关系的压缩技术，它们利用这些关系，如上卷、下钻等，通过分析发现单元间能够去除掉的冗余信息。这样，在将这些冗余信息去除掉之后，数据立方体的存储空间得到压缩并且数据立方体元组之间的关系得以保留，这类技术是目前数据立方体压缩存储技术的主流，代表着未来数据立方体压缩存储技术的发展趋势。Wang等人提出了精简立方体（Condensed Cube）的概念WLFY02，它其中有一个关键概念叫“Base Single Tuple（BST）”。它将具有相同BST的数据立方体单元归为同一类，仅仅存储BST和对
43、应的单元集，其他不符合这些条件的元组则按原来的方式存储。通过去除相同BST的数据立方体单元间的冗余信息，精简立方体能够有效地减少数据立方体的数据量。Sismanis等人提出了一种称为Dwarf的，基于语义压缩方法的立方体结构SRD02。它通过识别出立方体结构中具有相同前缀和后缀的语义信息，并去除这两种类型的冗余信息，可以十分显著地缩减数据立方体的存储空间。Dwarf在最好的情况下可以达到1/6000的压缩率。 商立方体（Quotient Cube）的概念由Laks Lakshmanan等提出LPH02，主要是为了解决立方体压缩过程中立方体单元间上卷和下钻逻辑关系的丢失问题。在商立方体中，所有的
44、单元被划分为若干类，在同一类中的单元具有相同的聚集值。类的划分不仅仅是满足聚集值相同这个条件，同时也满足一些额外的条件。这些条件的限制，使得商立方体可以保留下数据立方体的语义结构。因此，每个类只需保存下某些能够代表本类中所有单元属性的单元，即可实现数据量的压缩。4.1 商立方体的分类 商立方体的主要思想是分类，它采用了一种单元分类方法，称为“覆盖”分类法LPH02。该方法与聚集函数类型无关，也就是说，数据立方体上的任一单元，无论它的度量值的聚集函数是哪种操作，这个单元都会被商立方体算法划分到同一类中。假设基表中的一条元组t，在数据立方体网格中，t能够通过某一存在的路径，上卷到单元c，则称c覆盖
45、（cover）t。c的覆盖集（cover set）定义为：c所覆盖的所有基表中的元组。例如，在图2.1中，单元（*, B, M1）的覆盖集是(GZ, B, M1), (SZ, B, M1)。对于单元c和单元d，当c和d的覆盖集是相等的时候，它们被称为覆盖相等。例如，图2.1中的（*, B, M1）和（*, *, M1），它们的覆盖集都是(GZ, B, M1), (SZ, B, M1)，因此这两个单元是覆盖相等的。商立方体的分类方法就是将覆盖相等的单元分为同一类。在同一类单元中，有个上界（upper bound）的概念。上界就是在该类中最小的元素，也就是说，上界是无法下钻到同类单元中其他任何一个
46、单元的。使用覆盖相等方法产生的商立方体分类，每个类有且只有一个上界，且同类的单元具有相同的聚集值LPZ03。 表4.1所示是对于图2.1中的数据立方体进行商立方体分类和各类的上界。类别类中单元上界1(*,*,*):60(*,*,*):602(GZ,*,*):35(GZ,*,*):353(*,*,M1):45, (*,B,*):45, (*,B,M1):45(*,B,M1):454(*,F,*):15, (*,*,M2):15, (GZ,F,*):15(GZ,*,M2):15, (*,F,M2):15, (GZ,F,M2):15(GZ,F,M2);155(GZ,B,*):20, (GZ,*,M1):20, (GZ,B,M1):20(GZ,B,M1):206(SZ,*,*):25, (SZ,*,M1):25, (SZ,B,*):25, (SZ,B,M1):25(SZ,B,M1):25表4.1 商立方体分类和上界集4.2 商立方体的预计算算法 商立方体的预计算算法的主要目的就是将单元分类和找出这些类的上界。为了加快预计算的速度，本文中的预计算程
