图6.11 并行查询示意图
6.5 小结本章通过类图和数据流图说明了并行预计算程序和并行查询程序的具体实现。程序使用了C++和MPI为编程语言和编程环境，使得程序具有良好的封装性和可移植性。
第七章 实验
在本章中通过实验说明算法的有效性和可扩展性。实验的平台是一台有三个计算节点的刀片服务器，每个节点上的处理器主频为1.8GHz，内存容量为1GB，操作系统是Linux，内核版本2.6.9，节点间采用千兆网络连接。MPI运行环境为MPICH2.0，C++编译器g++版本为3.4.3，MPI环境下C++编译器MPICXX的版本为1.0.3。
7.1 数据描述在实验中，使用了一个来自不同气象站所收集的1985年9月的天气数据[Hahn94]。它包含了1,015,367个元组，一共20维。在这次实验中，所使用的是它前16维的数据，每个维度的依次如下表所示：
维度
维度名称
维度的势
1
时间
240
2
天空明亮度
2
3
纬度
3809
4
经度
5359
5
气象站编号
7037
6
气象站所处地点
1
7
当前天气情况
101
8
云层覆盖总量
9
9
低层云数量
10
10
低层云高度
11
11
低层云类型
13
12
中层云类型
14
13
高层云类型
11
14
中层云数量×100
24
15
高层云数量×100
24
16
中层云数量
10
表7.1 天气数据集
7.2 预计算实验在本实验中，将讨论基于数据分组方法的并行预计算程序对于串行预计算程序在性能上的提高，以及这两种方法在不同规模数据集上进行运算的性能表现。讨论并行查询程序的加速比。
在预计算实验中，在单节点环境下和三节点环境下分别对13个不同的数据进行了串行和并行预计算。这13个不同的数据的维度各不相同，从4维到16维，分别是天气数据集20维数据中的前4维到前16维等，元组条数都是1,015,367条。三节点环境下的数据分割采用平均分割，每个节点上收到的元组条数基本上是相等的。
在单节点环境下的实验使用串行的预计算程序。统计两个时间：(1)程序进行预计算写入文件的时间。(2)程序运行时间。
在三节点环境下的实验使用并行的预计算程序。因为从机不需要等待主机完全读入数据文件便可得到一部分数据进行预计算，使得从机预计算时间和主机读取文件有交叉。因此在此实验中，每台机器都会统计三个时间：（1）主机从开始读取数据文件到数据完全载入内存并发送出去的时间。（2）每台机器进行预计算的时间。（3）每台机器总的运行时间。
通过实验发现，刀片服务器的网络效率非常高，在实验中，几乎所有的MPI点对点通信时间都可以在0.2秒之内完成，加上实验中的MPI通信次数比较少，所以MPI通信的时间可以忽略不计。
7.2.1 预计算实验结果分析图7.1所示是分别在两种环境下的预计算时间，也就是程序生成立方体的计算时间。并行环境下的预计算时间是取三个节点预计算时间的平均值。如图中所示，基于数据分组的并行预计算方法能够有效地缩短预计算的时间。在数据维度少于或等于9维时，预计算的时间增长显得比较缓慢，在这个维度区间内，预计算程序的性能始终保持着较高水平。但随着数据维度的增多，预计算性能开始出现衰减。从11维数据开始，每增加一维数据，串行预计算时间便会增加约33%，而并行的预计算时间增长率为29%左右。
图7.2所示是串行预计算时间和并行平均预计算时间的比值。在4到10维之间时，串行预计算时间一直维持在并行计算时间的2.9倍左右。但在11维或更多维数据时，串行预计算时间的增长率开始大幅超过并行预计算时间，使得并行计算的加速比在11维时达到了理想状态的3倍，并且呈线性增长的趋势。可见，随着数据量的增大，DFS算法性能会相应地下降，而减少元组条数可以继续使得DFS算法保持高性能。
图7.1 预计算时间
图7.2 预计算加速比
图7.3、7.4和7.5分别是预计算程序读入数据文件时间、程序总运行时间和总运行时间的加速比。并行环境下程序总运行时间是指程序开始运行直到最后一个进程完成计算退出为止。并行程序中数据读入与数据发送是结合在一起的，数据读入一部分之后即可将该部分数据发送给相应的进程进行计算，但读入数据文件这一部分不能达到完全的并行化，所以程序总运行时间的加速比性能并没有已经完全并行化的预计算加速比那么可观。但随着维度的增多，预计算时间的增长，数据读入时间所占的总运行时间比例也相应地减少。在高维度的预计算中，并行的预计算程序最终还是可以达到3倍这个理想性能加速比。
图7.3 数据读入时间
图7.4 总运行时间
图7.5 总运行时间加速比
7.3 查询实验本实验的主要内容是在预计算生成的商立方体基础上，对4至13维的商立方体进行单节点串行和三节点并行点查询实验。讨论并行查询程序相对于单机查询程序在性能上
