工作站集群上I/O密集型数据挖掘应用的实现问题

### 工作站集群上 I/O 密集型数据挖掘应用的实现问题 #### 1. 引言 数据挖掘（DM）应用会利用存储在文件或数据库中的大量数据。为了发现对各种目的有用的模式和相关性，尤其是在商业领域指导战略决策，需要访问这些数据。许多 DM 应用是强 I/O 密集型的，因为它们需要多次读取和处理输入数据集。为了提高 DM 应用的性能，人们提出了多种技术，其中很多基于并行处理，主要目标是减少计算时间和/或减少访问内存外数据的时间。 自 20 世纪 90 年代初以来，出现了一种从昂贵且专用的并行超级计算机转向工作站集群（COWs）的趋势。历史上，COWs 主要用于科学和工程应用，但它们的低成本、可扩展性和通用性为新的应用领域提供了广泛的机会，DM 就是其中之一，因为 DM 算法通常具有大量的数据并行性。不过，要有效利用 COWs，并行实现需要适应机器的特定特征，例如要考虑现代硬件/软件架构采用的内存层次结构和缓存策略。 特定的离核（OoC）技术（也称为外部内存技术）可用于解决需要大量内存的 DM 问题。OoC 技术适用于无法完全放入物理内存的所有应用，其主要目标是通过绕过操作系统虚拟内存系统并显式管理 I/O 来减少内存层次结构开销。通过将数据集拆分为多个小块，可以实现对主内存和二级存储之间数据移动的直接控制。这些小块被加载到肯定能放入物理内存的数据结构中进行处理，必要时再写回磁盘。 本文研究了在经济实惠的并行架构（如配备有限主内存的 PC 集群）上可扩展的 I/O 密集型 DM 算法的实现，这些内存不足以存储整个数据集（甚至是其一个分区）。用于验证我们方法的测试用例 DM 应用基于在线 K-means 算法，这是一种著名的 DM 聚类算法。测试平台 COW 由三个对称多处理机（SMP）组成，通过 100BaseT 交换以太网互连，每个 SMP 配备两个奔腾 II - 233 MHz 处理器、128 MB 主内存和一个 4GB UW - SCSI 磁盘，操作系统为 Linux，内核版本 2.2.5 - 15。 #### 2. I/O 密集型 DM 应用的实现 我们关注的是多次顺序访问同一数据集的 DM 算法。重复扫描整个数据集具有良好的空间局部性，但时间局部性较差。只有当整个数据集完全适合物理内存时，才能利用时间局部性。然而，在实际中，由于“现实生活”中的数据集通常非常大，且物理内存有限，同时还有其他运行进程竞争内存使用，因此这种条件通常无法满足。所以，采用 OoC 算法是必要的，它可以利用软件驱动程序和磁盘控制器实现的预取策略，并允许利用多任务或多线程策略来重叠 I/O 延迟和有用计算。 一种看似最佳的策略是仅当数据集无法放入物理内存时才采用 OoC 算法。当内存足够大时，内核内方法似乎更高效，因为整个数据集只需从磁盘读取一次，然后可以在不进行进一步 I/O 操作的情况下重复访问。但当其他进程使用主内存导致磁盘交换时，这种内核内策略可能会失败。实际上，即使数据集相对于内存大小较小，“智能”的 OoC 方法也总是优于内核内方法。这是因为现代操作系统（如 Linux）中存在块设备的缓冲区缓存，内核和进程未使用的可用物理内存会根据需求动态加入缓冲区缓存。当对主内存的需求增加时，分配给缓冲区的内存会减少。 我们进行了实验，比较了一个简单测试程序的内核内和离核版本，该程序重复扫描一个适合物理内存的数据集。结果发现，这两个版本的程序性能相似。对于 OoC 版本的程序，在第一次扫描结束时，缓冲区缓存包含了整个数据集的块，后续扫描实际上不会访问磁盘，因为所有要读取的块都在主内存（即缓冲区缓存）中。此外，OoC 程序在第一次扫描数据集时可以利用操作系统的预取功能，在处理一个块时预取下一个块，从而隐藏一些 I/O 时间，而内核内程序在开始计算前必须读取整个数据集，无法将 I/O 时间与有用计算重叠。 综上所述，OoC 方法不仅适用于小数据集，当问题规模超过物理内存大小时也能扩展，而内核内算法在这种情况下会因内存交换而失败。为了提高大数据集的可扩展性，还可以结合 OoC 技术利用多任务技术来隐藏 I/O 时间。利用多任务时，需要将整个数据集的非重叠分区分配给不同的任务，同样的技术也可用于将应用程序并行化，将这些任务映射到不同的机器上。这种数据并行范式通常对于实现 DM 算法非常有效，因为计算通常是均匀的，任务之间的数据交换有限，并且通常在每次扫描整个数据集结束时需要进行全局同步，以检查终止条件并恢复一致的全局状态。 最后，在 COWs 上实现的并行 DM 算法还需要处理负载不平衡问题。负载不平衡可能源于所涉及机器的不同容量或外部作业的意外到达。由于采用的数据并行编程范式，一个可能的解决方案是动态更改分区大小。 #### 3. 测试用例 DM 算法及其实现 从营销到生物学、天体物理学等各种应用都需要识别具有同质性特征的记录子集（簇）。本文使用著名的聚类算法 K -