第六章  并行化算法的实现 6.1   串行预 计算 程序结构
　　在串行预计算程序中，一共有cubing、dfhandle、quotientcube和tuplehandle4个类，其中dfhandle和tuplehandle两个类是辅助功能类。它们的类图如图6.1所示。dfhandle的主要功能是打开关闭数据文件，将数据文件中的元组一条一条地读进来，然后将该条元组交给tuplehandle处理，tuplehandle将元组的各维数据分割开来，每次处理一维，并将该维数据存在程序指定的一个内存区域中。关于cubing类和quotientcube类的详细介绍，将在以下的章节中给出。

图6.1     dfhandle类和tuplehandle类

　　6.1.1 cubing类
　　cubing类的类图如图6.2所示，其中loaddata()的作用是使用dfhandle类，打开指定的数据文件，将元组读出之后，使用tuplehandle来将各个维度和度量值的数据拆分开来，然后对所有的维度做映射操作，写入映射文件，同时将映射后的维度数据存在data这个二维数组里，度量值存在msrdata中，直到把所有数据文件都读入data和msrdata中。在读数据之前，loaddata还会先统计基表中有多少条元组，元组有多少维和多少个度量值，某度量值上的聚集操作分别是哪种，这些数据分别存在tuplesnum，dimsnum，msrsnum和aggfunorder中。www.11665.com

　　avgfun()、maxfun()、minfun()、sumfun()和countfun()里面分别是平均、最大值、最小值、和、计数等聚集操作的实现。

图6.2     cubing类

　　cubing类的工作主要是完成预计算真正开始之前的准备工作，把所有数据都读入内存之后，quotientcube类便可以使用这些数据来进行预计算工作。cubing类的precompute()函数是一个虚函数，它的具体实现在quotientcube中。quotientcube类是cubing类的一个子类。

　　6.1.2 quotientcube类
　　quotientcube类public继承于cubing。它的类图如图6.3所示。通过调用precompute()开始预计算工作。

图6.3     quotientcube类

　　程序首先会创建dimsnum+1个aggdimdatax文件，用来存放不同层次的上界，同时也创建同样多个的aggmsrdatax文件，用来存放相对应的度量值。data[0]中存放cubing从数据文件读出的data内容，同样msrdata[0]中存放相应的度量值，data[1]和msrdata[1]中将存放的是将data[0]、msrdata[0]里数据排序后的结果，用来排序的算法在partition()中实现。

　　precompute()接下来便会调用dfs()开始计算上界并将上界与其所对应的度量值写入相应层次的文件中。dfs()的具体算法详见本文4.2节。

       预计算程序的数据流图如图6.4所示。

 

图6.4     串行预计算程序中的数据流

　　6.2   预计算并行化
　　并行预计算程序中，在串行程序的基础上增加了两个类：分别是dispatchmanager类和dispatchworker类。顾名思义，dispatchmanager类中的方法是为主从模式中的主进程所调用，dispatchworker类中的方法是在从进程中调用。根据本文5.1节中的描述，dispatchmanger类主要的工作是完成数据读入、映射和数据分发工作。dispatchworker的工作是接收主进程发送过来的数据。

　　6.2.1 dispatchmanager类和dispatchworker类
　　dispatchmanager类和dispatchworker类的类图如图6.5所示。数据的读入工作将由cubing类转移到dispatchmanager类中，但由于从进程无法接触到文件信息，因此，主进程必须将与数据文件相关的数据预先得出并发送给每个从进程。dispatchmanager在初始化时便会调用getdatafilenum()和getconfig()。

　　getdatafilenum函数使用dfhandle和tuplehandle来完成工作。首先打开数据文件，将第一行读出。数据文件的第一行是用来写明基表有多少个维度和度量值，每个维度和度量值的名称分别是什么。getdatafilenum里会根据里面的信息分辨出哪些是维度数据，哪些是度量值，分别有多少个，度量值以何种方式进行聚集操作等，然后把这些数据保存下来。最后是统计整个数据文件有多少条元组。这些操作基本和cubing::loaddata中前面部分的操作相同。

图6.5     dispatchmanager和dispatchworker类图

　　getconfig函数的作用是将保存着各个进程数据分配比例的配置文件内容读出，并根据getdatafilenum中得到的元组条数，计算出每个进程应当接收的元组条数。计算完之后，将这些信息保存在pconfig中。

　　接下来，dispatchmanager便会将pconfig里的数据连同度量值操作方式和文件夹名称发送到每个相应的进程中，如图6.6所示。同时，在从进程中运行的dispatchworker也调用了recvconfig()。主从进程间通过mpi的点对点通信，完成配置数据的发送和接收。dispatchworker接收完配置数据之后，将配置数据存如pconfig里。

　　在完成配置数据的交互之后，dispatchworker将会利用收到的数据，如元组条数、维度数和度量值数来决定该分配多大的内存空间以存下将要收到的数据，并开始等待接收数据。而dispatchmanager则会调用loaddata()来将数据文件载入内存。

　　dispatchmanager在loaddata()时是将数据存入两个长度分别为idimnum*ituplenum和imsrnum*ituplenum的一维数组中，它们分别是pdimdata和pmsrdata。与串行预计算程序中的cubing作用类似，dispatchmanager会在载入数据的同时完成映射的工作。但当dispatchmanager准备好要发送到其中一个从进程的数据之后，它便会调用senddata()，指明将要发送的进程号，将数据发送出去。如图6.7所示。
 

图6.6     发送和接收配置数据示意图

 

图6.7     发送和接收数据示意图

　　在每个从进程都接收完数据和主进程完成loaddata之后，每个进程都会有装着维度数据和度量值的两个一维数组。在并行程序的cubing中，由于不再需要与文件打交道，所以将cubing::loaddata()重载，将它的输入参数由数据文件名改为文件夹名称、pdimdata、pmsrdata和paggfun。在这个函数中，cubing将会把pdimdata和pmsrdata这两个一维数组的数据读出，存成二维数组。这样，数据发送过程已经完结，预 计算 开始之前的数据准备工作已经完成，接下来便是各个进程调用quotientcube里的precompute()函数，开始预计算工作。接下来在每个进程中的工作情况，和串行环境下的情况一致。

　　6.3   串行查询程序结构
　　在串行查询程序中，同样也有dfhandle和tuplehandle这两个辅助类。实现查询功能主要由以下三个类完成：aggstorage、closecubequery、querycomputation。它们的类图如图6.8所示。

图6.8     查询程序类

　　aggstorage类的主要功能是面向立方体数据的操作。它封装了读入预计算所产生文件的方法，如loadmapdata是将map文件读入，用来映射查询语句。loadaggdata用来将某一层立方体文件内容读进内存。

　　 串行查询程序首先会通过querycomputation::getqueryrecord()将查询语句批量地读入，存在queryrecords里，然后调用closecubequery::query()。在closecubequery::query()中，程序通过aggstorage所实例化的aggstorage对象将映射关系文件读入，并调用mapstoi()将查询语句映射为整型数组。映射后的查询语句存在tqryobj中，然后将tqryobj中的内容，一次一条地递交给pointquery()进行查询。大致的流程如图6.9所示。

 图6.9  串行查询流程

       pointquery首先会确定该条查询语句的层次，然后判断该层次的数据是否已经载入内存，如果没，则调用aggstorage::loadaggdata()将其载到内存中。然后开始顺序扫描各条上界，使用iscovered来判断该上界是否被查询语句所覆盖。如果扫描完一层还找不到所覆盖的上界，则继续扫描下一层文件。具体流程在本文4.3节。

　　6.4   并行查询
　　在并行查询程序中，增加了两个类，分别是querymanager类和queryworker类。串行程序中的querycomputation类被取消，它的功能将在querymanager类中实现，closecubequery中的mapstoi()函数也放在querymanager类中实现。图6.10中所示为querymanager类和queryworker类的类图。

　　6.4.1 querymanager类和queryworker类
　　并行查询程序首先会在主进程中调用querymanager::loadquery()来将查询语句全部存入内存queryrecords二维数组中。接着就是调用querymanager::mapquery()将查询语句映射成整型数组，存入querymanager::pquery中。与并行预计算程序类似，并行查询程序中，主进程也会预先将一些配置数据发送给从进程，其中包括了查询语句的条数、数据的维度和度量值数。从进程在接收完这些数据之后，做一些初始化工作，为即将发送过来的查询数据做准备。实现这个功能的是querymanager::broadcastconfig()和queryworker::receiveconfig()。

　　在配置数据发送完毕之后，便是开始发送查询数据，主进程调用querymanager::broadcastquery()将查询数据分发到各个从进程上，从进程接收完之后，将查询语句存入queryworker::pquery中。

　　结果的指针。主进程与从进程分别调用closecubequery::query(querymanager::pquery, querymanager::pqueryresults[0])和closecubequery::query(queryworker::pquery, queryworker::pqueryresult)开始进行查询工作。

图6.10    querymanager类和queryworker类

　　查询的流程如图6.11所示，在query()中的实现过程基本与串行程序过程一致。在查询完毕之后，各个从进程将会把存放着查询结果的数组，pqueryresult发送回主进程。主进程调用querymanager::collectresults()将所有信息收集起来，并将其存在pqueryresults二维数组中。最后，querymanager将会调用statistics()来统计并得到最终的查询结果，并行查询程序返回。

 

图6.11    并行查询示意图

　　6.5   小结
　　本章通过类图和数据流图说明了并行预计算程序和并行查询程序的具体实现。程序使用了c++和mpi为编程语言和编程环境，使得程序具有良好的封装性和可移植性。