基于GPU加速的进化归纳并行计算

### 基于GPU加速的进化归纳并行计算 在当今的数据科学领域，高效处理大规模数据是一项关键挑战。GPU（图形处理单元）凭借其强大的并行计算能力，为进化数据挖掘提供了一种极具潜力的加速方案。本文将深入探讨基于GPU的加速方法在进化决策树和模型树归纳中的应用。 #### 1. GPU加速的优势 与计算集群相比，GPU在计算成本和性能方面具有显著优势。尽管并非所有算法和应用都适合GPU生态系统，但在进化数据挖掘中，GPU的性价比表现出色。 #### 2. 加速GPU版本的方法 为了进一步提升GPU版本的性能，可消除两类重复计算： - **利用迭代间树的相似性**：在典型的变异操作后，新树与原树仅在受影响的子树部分不同。因此，可限制实例在评估树中的传播范围，以估计个体适应度。例如，当内部节点被修剪为叶子节点时，只需重新计算该叶子节点的预测值，并更新到根节点路径上的统计信息。在分类树中，CPU可仅将受影响子树及从根到该子树的路径信息发送给GPU，减少不必要的计算。 - **利用当前种群中树的相似性**：在选择过程中，更优个体存活概率更高，导致种群中出现具有共同上部结构的树。通过实现两棵树的共同表示结构，可避免学习实例在这些共同部分的重复传播。具体算法为：首先，两棵树的根节点测试必须相同；然后，同时遍历两棵树，遇到节点差异时设置分叉节点并结束该路径。对于给定的树种群，可根据根测试的一致性轻松选择相似树对，并将其作为双树表示发送给GPU处理，其余个体则以标准方式处理。 #### 3. 多GPU实现 单GPU实现虽有诸多优势，但受限于可用内存。随着计算站配备多个GPU的机会增多，多GPU系统为克服单GPU解决方案的固有局限提供了灵活机制。主要有两种实现方法： - **每个GPU处理不同子集的个体**：当GPU数量较少（最多八个）时，每个GPU可分配至少几个个体并依次处理。此方法易于实现，主进程只需将连续个体分配给不同GPU。若个体数量能被GPU数量整除且树大小相似，可减轻负载不平衡问题。但该方法无法处理无法加载到GPU内存的大型数据集。 - **所有GPU并行处理一个个体**：将训练数据集划分为等大小的部分，每个GPU负责处理其中一部分。主进程将树广播到所有GPU，各GPU在自己的子集上运行相同的内核。处理后的树副本及统计信息返回主进程进行归约操作。该方法可处理更大的数据集，且在一定程度上能有效扩展。实现时，只需对单GPU代码进行小扩展，在进化前将数据集分区并发送到相应GPU，进化过程中广播树并为每个GPU创建OpenMP线程，最后实现部分结果的归约操作。 #### 4. 实验结果 为验证GPU加速的有效性，进行了一系列实验，使用了三种NVIDIA GPU卡：GeForce GTX 780、GeForce GTX Titan X和Tesla P100。 ##### 4.1 加速分类树归纳 - **速度提升**：在chess3x3问题中，分析不同大小的数据集（从100万到1亿个实例），所有GPU的加速比均达数百倍，最佳测量加速比接近700。对于真实数据集Suzy和Higgs，即使使用最便宜的GPU，加速比也比无GPU加速的OpenMP版本高出两个数量级。 - **绝对归纳时间**：顺序版本的GDT系统在Intel Xeon CPU上处理Suzy和Higgs数据集分别需要约两天和四天，而GPU加速解决方案的最短时间分别仅为3.5分钟和8.5分钟。 - **时间分配分析**：以Tesla P100为例，分析执行时间的五个部分：两个内核、GPU内存操作、CPU与GPU之间的数据传输以及仅在CPU上运行的指令。随着数据集增大，第一个内核时间逐渐占主导，从5000万个实例开始，其他操作时间可忽略不计。 - **部分树重新计算的影响**：部分树重新计算可显著提高加速比，对于最小数据集，GTX 780卡的加速比提高5.5%，通常约为20%，对于最大数据集，可超过30%。 - **特征数量的影响**：在Tesla P100上，随着特征数量增加，加速比也随之增长。但过多不相关和嘈杂的特征会减慢进化归纳速度，可能需要更多迭代才能获得有竞争力的分类器。 - **数据集大小限制**：在一分钟内，最弱的GPU卡可分析约50万个实例的数据集，更强的卡可处理两倍大小的数据集；一小时内，限制可增长到超过5000万个实例。同时，GPU卡的可用内存也限制了