基于数据分组方法的数据仓库并行预计算和查询四的论文

1、基于数据分组方法的数据仓库并行预计算和查询（四）的论文第七章实验在本章中通过实验说明算法的有效性和可扩展性。实验的平台是一台有三个 计算 节点的刀片服务器，每个节点上的处理器主频为，内存容量为1gb,操作系统是linux,内核版本，节点间采用千兆 网络 连接。mpi运行环境为，C+编译器g+版本为，mpi环境下C+ 编译器mpicxx的版本为。数据描述在实验中，使用了一个来自不同气象站所收集的1985年9月的天气数据hahn94。它包含了 1,015,367个元组，一共20维。在这次实验中，所使用的是它前16维的数据，每个维度的依次如下表所示：维度维度名称维度的势1时间2402天空明亮度23纬

2、度38094经度53595气象站编号70376气象站所处地点17当前天气情况1018云层覆盖总量99低层云数量1010低层云高度1111低层云类型1312中层云类型1413高层云类型1114中层云数量X1002415高层云数量X1002416中层云数量10表天气数据集预计算实验在本实验中，将讨论基于数据分组方法的并行预计算程序对于串行预计算程序在性能上 的提高，以及这两种方法在不同规模数据集上进行运算的性能表现。讨论并行查询程序的加速比。在预计算实验中，在单节点环境下和三节点环境下分别对13个不同的数据进行了串行和并行预计算。这 13个不同的数据的维度各不相同，从 4维到16维，分别是天气数据

3、集 20维数据中的前4维到前16维等，元组条数都是 1,015,367条。三节点环境下的数据分割 采用平均分割，每个节点上收到的元组条数基本上是相等的。在单节点环境下的实验使用串行的预计算程序。统计两个时间：（1）程序进行预计算写入文件的时间。（2）程序运行时间。在三节点环境下的实验使用并行的预计算程序。因为从机不需要等待主机完全读入数据文件便可得到一部分数据进行预计算，使得从机预计算时间和主机读取文件有交叉。因此在此实验中，每台机器都会统计三个时间：（1）主机从开始读取数据文件到数据完全载入内存 并发送出去的时间。（2）每台机器进行预计算的时间。（3）每台机器总的运行时间。通过实验发现，刀片

4、服务器的网络效率非常高，在实验中，几乎所有的mpi点对点通信时间都可以在秒之内完成，加上实验中的mpi通信次数比较少，所以 mpi通信的时间可以忽略不计。预计算实验结果分析图所示是分别在两种环境下的预计算时间，也就是程序生成立方体的计算时间。并行环境下的预计算时间是取三个节点预计算时间的平均值。如图中所示，基于数据分组的并行预计算方法能够有效地缩短预计算的时间。在数据维度少于或等于 9维时，预计算的时间增长显得比较缓慢，在这个维度区间内，预计算程序的性能始终保持着较高水平。但随着数据维度的增多，预计算性能开始出现衰减。从11维数据开始，每增加一维数据，串行预计算时间便会增加约33%，而并行的预

5、计算时间增长率为29%左右。图所示是串行预计算时间和并行平均预计算时间的比值。在4到10维之间时，串行预计算时间一直维持在并行计算时间的倍左右。但在11维或更多维数据时，串行预计算时间的增长率开始大幅超过并行预计算时间，使得并行计算的加速比在11维时达到了理想状态的3倍，并且呈线性增长的趋势。可见，随着数据量的增大，dfs算法性能会相应地下降，而减少元组条数可以继续使得dfs算法保持高性能。图预计算时间图预计算加速比图、和分别是预计算程序读入数据文件时间、程序总运行时间和总运行时间的加速比。并行环境下程序总运行时间是指程序开始运行直到最后一个进程完成计算退出为止。并行程序中数据读入与数据发送是

6、结合在一起的， 数据读入一部分之后即可将该部分数据发送给相 应的进程进行计算，但读入数据文件这一部分不能达到完全的并行化，所以程序总运行时间但随着维度的增多，预计算在高维度的预计算中，并4至13维的商立方体进行单的加速比性能并没有已经完全并行化的预计算加速比那么可观。 时间的增长，数据读入时间所占的总运行时间比例也相应地减少。 行的预计算程序最终还是可以达到3倍这个理想性能加速比。图数据读入时间图总运行时间图总运行时间加速比查询实验本实验的主要内容是在预计算生成的商立方体基础上，对 节点串行和三节点并行点查询实验。讨论并行查询程序相对于单机查询程序在性能上的提 高，计算并行查询程序的加速比。首

7、先各个维度都随机地生成了1000条点查询。生成的点查询是从基表中随机抽取出1000条元组，并随机地将元组中的某些属性改为“ *。经观察，串行查询程序与并行查询程序所得到的查询结果是一致的， 在本实验中，主要讨论并行查询程序对于串行程序的加速比， 因此，查询的具体结果便不再讨论。串行查询与并行查询的程序运行时间如图所示。图查询程序运行时间查询实验结果分析尽管在并行查询中，每台机器所查询的立方体单元数目基本上只相当于串行查询中立方 体单元数目的三分之一，如图所示，但通过实验发现，并行查询程序的性能加速比并未能够达到理想的加速比， 如图，只能达到2倍左右的性能加速。对其原因进行分析，发现这是由 于查

8、询语句未能直接命中，会造成额外开销的问题（本文节中提到）所造成的。图商立方体单元数图程序加速比在基于数据分组方法的预计算中，经过预计算的商立方体数据是分布式地存放各台机器 上的。对于一条查询语句 q，当程序用q在a机器的商立方体中进行查询时，q的覆盖集里面的所有元组在预计算时可能都没有分配到a机器上。在这种情况下， q在a上的查询便会产生巨大的额外开销：首先会从q所在层次h1里的单元中开始查找，在h1找不到的情况下， 会继续查找h1的下一层h2。但是由于q在a上是无法命中的，查询程序会一层接着一层地 往下扫描下去，直到扫描完最后一层。随机生成的1000条点查询语句是根据基表中的元组生成的，这样

9、在串行查询中，较少 会出现语句在某一层未能命中，需要扫描下一层的情况。然而在并行查询中，由于元组的分布性，产生了较多的查询不命中，使得程序必须进行额外的层次扫描，而且这种额外的层次扫描的代价十分巨大。在并行查询中，开销巨大额外的层次扫描使得查询的时间急剧地增加， 从而使得程序性能没能达到预期的效果。尽管如此，在三台机器上能够实现缩短一半的时间，并行查询程序的性能还是令人满意的。小结由于硬件平台条件的限制，实验最多只能在三个节点上运行，无法进行更多的实验来验证本文提出的基于数据分组的并行预计算和并行查询方法的可扩展性。在三个节点上进行的预 计算和查询实验的结果表明，基于数据分组方法的数据仓库并行

10、预计算和查询方法是有效的，它能够有效地提高数据仓库预计算和查询的性能，并得到正确的结果。第八章总结与展望在数据仓库数据量急剧增长的今天，并行数据仓库技术成为了解决海量数据预计算和存 储问题的一种重要的、 有效的手段。本文主要研究了一种基于数据分组的并行数据仓库预计 算和查询技术，并在串行程序基础上实现了并行预计算和查询的程序。然后通过实验数据来说明该方法的有效性和分析了这种方法的优点和存在的缺陷。结论由于实验平台的限制， 使得各项实验最多只能在三个节点的环境下运行，无法在更多节点的计算环境下进行实验，研究本文提出方法的可扩展性。 通过实验的观察和分析，本文提 出的基于数据分组的数据仓库并行预计

11、算和并行查询方法有以下一些优点：(1) 该实现方法的并行策略简单，该方法可以经过很少的修改，便可以将很多已经实现的串行程序改为并行程序。使用mpi和C+进行编程，使得程序具有良好的可移植性、面向对象性。(2) 可以更好地适用于大数据量场合。对于串行版本的预计算程序，在对于高维度数据集进行预计算时，随着数据量的增加，性能衰减得很厉害。并行预计算时的性能加速比十分 可观，在数据量很大的情况下，甚至可以超过理想加速比。(3) 预计算后生成的商立方体数据以分布式方式存储，在查询时，各台机器都可以同时对立方体数据进行读取，充分利用了各台机器的磁盘i/o带宽。同时本文提出的并行预计算和并行查询方法存在的一

12、些不足：(1) 对于并行查询，查询的效率未能达到理想的加速比。这是由于数据元组的分布性与商立方体的特性所造成的，当查询语句覆盖集中的元组没被分配到某台机器上时，该查询语句在该台机器上的查询操作便无法命中。商立方体的特性使得查询在某一层上界中找不到所覆盖的上界的时候， 必须到下一层进行查找， 如果一直找不到，便会一直找下去，直到全部都扫描过。查询语句在某台机器上无法命中的后果是会产生很多额外的层次文件扫描操作， 这样一层层的扫描操作代价是十分巨大的，但这种情况在数据元组分布式存储的情况下又是无法避免的，这样便使得并行查询程序的加速比未能达到理想状态。(2) 基表元组的映射可以提高预计算和查询的响

13、应效率，但是对于映射这个步骤还不能完全地并行化处理。未来的改进对于本文提出的并行预计算和并行查询方法存在的一些不足和缺点，可以存在这样一些补充和改进的地方：(1) 预计算算法还需要做出一些修改以适应立方体分布式存储环境，如聚集操作中的平均操作，除了对该维度量值做平均值计算之外， 还应该同时加上计算总和的计算。 这样才能 保证元组条数的信息不至于丢失，在主进程最终做统计运算的时候才能得到正确的结果。(2) 对于基于顺序查询方法的并行查询，可以预先判断一下是否在该机上命中查询。如果可以预先判断出查询不命中，则可以减少许多额外的层次扫描开销，提高效率。预先的判断应该可以通过扫描本地预计算输入基表里有

14、没有查询语句覆盖集内的元组进行。(3) 改进查询程序的算法。顺序查询是最简单、易行的查询方法，但这种方法的效率确 实不高。(4) 改进立方体数据结构，商立方体存在着查询效率不高的问题，对此人们提出了各种基于商立方体的改善型立方体数据结构，如qc-treelpz03和semi-closed cubelw05，基于此类型的立方体结构应该能够改善查询的响应速度。参考文献beo07: the beowulf cluster siteccs93a e. codd, s. codd, c. salley. bey ond decisi on support. computer world, 27(30):

15、 87-89, 1993ccs93b e. codd, s. codd, c. salley. providi ng olap to user-a nalysts. pc world, (9), 1993chen99陈国良.并行计算一一结构算法 编程.北京，高等 教育 出版社，1999du01都志辉.高性能计算并行编程技术一一mpi并行程序设计.北京，清华大学出版社，2001fly72 m. flynn. some computer organizations and their effectiveness. ieee transactions on computers, c21(9), 19

16、72gcb+97 j. gray, s. chaudhuri, a. bosworth, a. layma n, d. reichart, m. ven katrao, f. pellow and h. pirahesh. data cube: a relational aggregation operator generalizing group-by, cross-tab, and sub-totals. jo urnal of data mining and kno wledge discovery, 1(1): 29-53, 1997ggkk03 a. grama, a. gupta,

17、 g. karypis, v. kumar. i ntroduct ion to parallel comput ing (sec ond edition). pearson education, 2003.张武，毛国勇，程海英 等译.并行计算导论.北京，机 械工业出版社,2005hah n94 c. hah n et. al. edited syn optic cloud reports from ships and land stati ons over the globe, 1982-1991. /ftp/ndp026b/, 1994.hpf06 high performa nee fo

18、rtra n foruminm02 w. h. inmon. building the data warehouse (third edition), john wiley & sons, inc. 2002.王志海，林友芳等译.数据仓库.北京，机械工业出版社，2003lam07 lam-mpi parallel comput inglph02 l. lakshma nan, j. pei and quotie nt cube: how to summarize the sema ntics of a data cube. in vldb ' 02lpz03 l. lakshm

19、anan, j. pei and y. zhao. qc-trees: an efficient summary structure for sema ntic olap. in proceedi ngs of the 2003 acm sigmod intern ati onal conference on man ageme nt of data, acm, 2003lw05 s. li and s. wang. semi-closed cube: an effective approach to trad ing off data cube size and query resp ons

20、e time. jo urnal of computer scie nee and tech no logy, , , , 2005mpi03a mpi: a message-pass ing in terface sta ndard.mpi03b mpi-2: exte nsions to the message-pass ing in terface.mpi07 mpich2 home pageomp07 ope nmp: simple, portable, scalable smp program mingptp06 posix thread program mingpvm07 para

21、llel virtual mach ine web sitesrd02 y. sismanis, n. roussopoulos, a. deligiannakis and y. kotidis. dwarf: shrinking the petacube. in proceedi ngs of the 2002 acm sigmod intern ati onal conference on man ageme nt of data, acm, 2002st98 d. skillicorn and d. talia. models and Ianguages for parallel com

22、putation. acm computi ng surveys, 30(2): 123-169, 1998wlfy02 w. wang, h. lu, j. feng and j. yu. conden sed cube: an effective approach to reduc ing data cube size. in proceedings of the 18th international conference on data engineering, ieee computer society, 2002.zcml06张林波，迟学斌，莫则尧，李若.并行计算导论.北京，清华大学出版社， 2006附录时间（秒）维