并行数据挖掘与知识发现系统的优化与实现

### 并行数据挖掘与知识发现系统的优化与实现 在当今的数据处理领域，并行计算和知识发现是两个重要的研究方向。本文将介绍在 ATM 连接的 PC 集群上进行并行数据挖掘以及知识发现系统 INDED 的并行化相关内容。 #### 1. TCP 重传参数优化 在 PC 集群上运行 HPA 程序时，TCP 重传参数的设置对程序性能有重要影响。TCP 重传在协议中会在 MAX 和 MIN 限制范围内动态变化。实验发现，默认的 MAX 值（60000[ms]）不太适合集群，可能导致不必要的长重传间隔。因此，建议将 MAX 设置为比默认值小的值，例如 MAX = MIN + 100[msec]，并且 MIN 最好设置为随机值，这样可以防止 ATM 交换机处的单元冲突。 使用优化后的参数，在多达 100 台 PC 上运行 HPA 程序时能获得相当不错的加速效果。由于应用本身未改变，性能差异主要来自于 TCP 重传，这与屏障同步和全对全数据广播相关。 #### 2. 动态远程内存获取 在关联规则挖掘的第 2 遍扫描中，候选项集的数量比其他遍扫描要大得多，且其数量强烈依赖于用户指定的条件，如最小支持度值，在执行前很难预测其大小。当所需内存超过实际内存大小时，部分内存内容必须被交换出去。但由于每个数据项的大小较小且数据几乎是随机访问的，将数据交换到存储设备会严重降低整体性能。 为了解决这个问题，我们进行了相关实验，在需要大量内存时，将远程节点的可用内存用作交换区域。具体操作步骤如下： 1. 在每个节点设置候选项集内存使用的限制值。 2. 当 HPA 程序执行到第 2 遍扫描，内存使用量超过该限制值时，将部分内容交换到远程节点的可用内存中，即应用执行节点动态获取远程内存。 3. 当应用执行节点尝试访问已交换出去的项时，会发生页面错误。 实验参数设置如下： | 参数 | 值 | | ---- | ---- | | 事务数量 | 1,000,000 | | 不同项的数量 | 5,000 | | 最小支持度 | 0.1% | | 应用执行节点数量 | 8 | | 可用内存节点数量 | 1 - 16 | 在这些条件下，第 2 遍扫描中的候选项集总数为 4,871,881，每个候选项集总共占用 24 字节，每个节点大约有 14 - 15MB 的内存被这些候选项集占用。 #### 3. 远程更新方法 当内存使用受到限制时，执行时间会比无内存限制时长很多，这是因为交换操作的数量极大。从表 1 中可以看到每个应用执行节点的页面错误数量。由于大部分内存内容会被反复访问，在这种情况下似乎会出现一种抖动现象。 为了防止这种现象，提出了一种限制交换操作的方法。当节点的内存使用达到限制值时，它会获取远程内存并交换出部分内存内容。如果后续需要访问这些数据，会将其交换回来。但有时，当发生页面错误时，将更新信息发送到远程内存会更好。也就是说，一旦某些内容被交换到远程节点的内存中，它们就固定在那里，只能通过库函数提供的远程内存访问接口进行访问。这种远程更新方法目前仅应用于项集计数阶段。 | 内存使用限制（MB） | 节点 1 | 节点 2 | 节点 3 | 节点 4 | 节点 5 | 节点 6 | 节点 7 | 节点 8 | | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | | 12 | 1606258 | 2925254 | 1306521 | 2361756 | 1671840 | 1723410 | 2166277 | 2545003 | | 13 | 885798 | 1896226 | 593000 | 1374688 | 932374 | 896150 | 1326941 | 1375398 | | 14 | 254094 | 1003757 | 512984 | 286945 | 191102 | 601657 | 407628 | - | | 15 | 268039 | - | - | - | - | - | - | -