CPU MIC异构并行架构下基于大规模频繁子图挖掘的药物发现算法.docx

《CPU MIC异构并行架构下基于大规模频繁子图挖掘的药物发现算法.docx》由会员分享，可在线阅读，更多相关《CPU MIC异构并行架构下基于大规模频繁子图挖掘的药物发现算法.docx（17页珍藏版）》请在优知文库上搜索。

1、CPU-MIC异构并行架构下基于大规模频繁子图挖掘的药物发现算法摘要：频繁子图挖掘是许多实际应用领域中需要解决的重要问题，由于计算密集性、挖掘的图集及其结果容量大，现有的频繁子图挖掘方案无法满足时间需求，其处理效率是目前面临的主要挑战。原创性地提出了并行加速的频繁子图挖掘工具cmFSMocmFSM主要在3个层次上进行并行优化：单节点上的细粒度OpenMP并行化、多节点多进程并行化和CPU-MlC协作并行化。在单节点上cmFSM的处理速度比基于CPU的最佳算法快一倍，在多节点方案中cmFSM提供可扩展性。结果表明，即使只使用一些并行计算资源，cmFSM也明显优于现有的最先进的算法。这充分表明提出

2、的工具在生物信息学领域的有效性。关键词：频繁子图挖掘；生物信息学；并行算法；内存约束；同构；集成众核引言在生物信息学研究中，为帮助在药理学化合物数据库或生物网络的核心功能结构中寻找新药，频繁子图挖掘的解决方案尤为重要。但现有的频繁子图挖掘方案无法有效解决内存消耗与时间需求问题。LinW等人认为频繁子图挖掘问题可分为两个方面：一方面是在一个图的不同区域挖掘子图，适用于社交网络分析领域；另一方面是在大规模图集中挖掘子图，适用于计算药理学和生物信息学领域。两方面都面临共同的问题：大规模挖掘任务产生的大量挖掘结果超过了单台机器的存储器空间，且无法满足时间需求。并行技术是解决这类问题的有效方案。针对第一

3、方面，专家已经提出基于串行CPU技术、并行计算框架(M叩RedUCe、MPI、Spark)及图形处理器(graphicsprocessingunit,GPU)的解决方案。本文意在解决生物信息学领域中频繁子图挖掘的问题。2相关工作现有频繁子图挖掘方案以递归计数为基础，可以挖掘出所有频繁子图，且大部分频繁子图挖掘算法基于广度优先搜索(breadthfirstsearc,BFS)改进生成，例如基于先验的挖掘算法(apriori-basedalgorithmformining,AGM)和频繁子图挖掘(frequentsubgraphdiscovery,FSG)算法工具。但是深度优先搜索(depth-f

4、irst-search,DFS)内存需求更低、性能更优。MeinIT等人对一些典型的DFS算法(如MoFa、FFSMgSanftGaston)进行了定量比较和详细比较，发现遇到大规模挖掘任务时，它们很难满足时间需求。值得注意的是，它们都是单核串行版本。此外，BUehrerG等人提出了多核系统中的并行挖掘策略，并在多个内存处理器间划分挖掘任务。这些解决方案充分利用了单节点上的机器资源实现加速挖掘。然而，这些方案都是基于内存的，并假设内存空间适配于图集和挖掘规模。但是，随着数据量的增加以及支持度的降低，挖掘规模呈指数递增，内存空间不再适配。为解决这个问题，WangC等人和NgUyenSN等人基于磁

5、盘分别提出ADIMine算法和数据分区方法。但是这类方案又面临着访问数据的巨大开销问题。HillS等人基于M即RedUCe框架提出了IFSM算法。该算法首先计算图表集合中的所有频繁子图的支持度。其次，排除未达到设定支持度的频繁子图。与IFSMn0类似，FSM-H和mrFSM也是通过迭代方法在MapReduce框架上开发的，且更加关注每次迭代中的负载平衡。然而M叩RedUCe框架不适合迭代计算,可能会产生大量I/O和序列化开销，因此基于MapReduce的这些方案仍然会产生严重的性能问题。MaPRedUCe框架上性能更为出色的是MRFSM。MRFSM不采用迭代方法，而是根据支持度智能化地过滤频繁

6、子图，再将所有频繁子图分配给所有机器进行挖掘，并整合最终结果。因为没有迭代，所以它能提供比IFSM、FSMH和mrFSM更好的性能。但是MRFSM使用标准I/O和数据间的交互，其性能受到严格限制。此外对于大规模挖掘任务，每台机器上会产生严重的存储压力，MRFSM无法满足时间需求。针对大规模挖掘问题，笔者提出了CmFSM算法。该算法分别在3个方面实现了并行化：单节点上的细粒度OPenMP(共享存储并行编程)并行化、多节点多进程并行化和CPU-MIC协作并行化。3算法介绍CmFSM算法实现了多级别和多粒度的并行性，并以集成众核(manyintegratedcore,MIC)为加速器，使用OPenM

7、P实现多线程，目的是解决药物爰现过程中大规模频繁子图挖掘的时间需求和内存限制等问题。信息传递接口(messagepassinginterface,MPI)基于4种静态任务划分策略和一种基于监管的动态任务划分策略，实现最佳负载平衡。此外，在传输模式下使用MIC仅传输双边频繁子图，并备份复杂数据结构，以避免过度传输造成的瓶颈。通过充分利用MIC的多核计算能力，可以在CPU和MIC协作的情况下达到预期的执行速度。3.1 单节点上的OPenMP并行化3.1.1 并行化策略基于DFS的频繁子图算法难以控制并行粒度，且无法控制递归过程，造成程序一直调用函数的后果，从而产生大量挖掘结果，这必然会导致不同挖掘

8、任务间的负载不平衡。为了解决这个问题，笔者采用基于OPenMP的细粒度并行策略。具体来说,挖掘频繁子图的过程将公共递归挖掘过程转化为BFS循环挖掘过程，从而实现单边增长粒度的并行性。此外，笔者创立了4个新缓冲区：原子区、t子区、1子区和C子区。原子区记录每个级别(从单边到多边的频繁级别)挖掘的子图集,并按照规定级别进行挖掘，其中同一级别的子图具有相同的边数。当原子区没有空间时，将进行下一级挖掘任务。t子区是单线程任务中的局部变量，记录每个子图边挖掘到的子图。1子区也是单线程任务中的局部变量，它记录从t子区并集中获得的每个线程的所有子图挖掘情况。c子区记录从每个级别挖掘得到的子图集。在单线程结束

9、时，1子区被视作关键区域中的C子区。同时C子区和原子区将释放空间，以便进行下一级迭代挖掘。值得注意的是，在并行计算中无法确保每个线程中的所有挖掘任务同时结束，尚未完成任务的线程将继续使用原子区数据。C子区存在的意义在于不能直接将1子区应用于原子区，否则可能导致挖掘失败。新并行算法伪代码如下。算法：新并行算法。Feequent_Subgraph_Mining(GS,S)1-6：samewitholdalgorithml1-6;7：foredgeeinSldo8：initialize1-edgegraphgwithe;9：One_edge_growth(GS,S,g,children);10：Ie

10、n-size(children);11：whileIen0do12：#pragmaompparallel13：#pragmaompparallelfor14：forgraphcinchildren15：One_edge_growth(GS,S,c,tchildren);16：IChiIdren-IchildrenUtchildren;17:clear(tchildren);18：endfor19：#pragmaompcritical20：cchildrenCchildrenU!children;21：#endparallel22：swap(children,cchildren);23：clea

11、r(cchildren);24：Ien-Size(Children);25：endwhile26-29：samewitholdalgorithm10-13;30：endfor总体来说，此操作计算规模大，但因为并行粒度小，在线程调度中不使用大多数CPU资源，而且可以通过OPenMP的动态调度策略轻松实现良好的负载均衡。此外，递归挖掘过程被循环挖掘过程替换，因此不需要系统协助管理堆栈，这会产生额外的加速。3.1.2内存管理深度优化频繁子图挖掘的主要挑战是内存约束。为了实现内存重用和内存空间的有效利用，笔者采用“动态应用和存储指针”的策略。具体来说，程序动态地挖掘子图，并在图代码结构中存储边指针，而

12、不是存储实际边对象，以便挖掘出的频繁子图与其原子图共享大多数边，这将显著节省内存空间。内存重用示意如图1所示。由图1可看出，只有边指针存储在图形代码中，而且每个子图只存储一个实例在存储器中，从而达到内存重用的目的。PlrO(0.LA,a,B)ptrl(1.2,B,a,A)tr2(L3.B,a,A)ptr3d,4,B,b,B)ptr4(3.4,A,c,B)PE) (OJAa,B)图形代码1 条边Iptr2条边IPIiOIPtrT、I7)3 条边IptrItrlptr2|-4 条边IPIrOIPlrIlplr21Pii5 条边Ipi)IPtrIlplr21ptr3ptr41图1内存重用示意6 .2

13、多节点多进程并行加速3.2.1 任务划分策略多节点程序的最大挑战是通信开销。使用粗粒度并行策略可有效地避免大量通信开销。其过程是先通过MPI划分频繁子图，然后每个进程在其节点中保存其挖掘结果，以避免大量输出文件造成单节点内存压力。最后，将所有输出文件整合为最终挖掘结果。此外，结合单节点的多进程可为每个MPI进程创建多个线程完成并行化，以实现良好的性能。但是这种粗粒度策略不利于负载平衡，很容易导致数据倾斜，无法充分利用系统资源实现最佳性能。基于数据集的不同特征，笔者设计并提出了4种静态任务划分（即对等、递增、单任务和循环）策略和一种基于监管的动态任务划分策略，以尽可能地实现负载均衡。具体来说，4

14、种静态任务划分和基于监管的动态划分如下所示。对等策略（静态划分）：该策略平均分配挖掘任务，但不绝对，只需保证分配给各节点的任务相等或差值不大于1即可。然而，实验发现负载极不平衡，很容易遇到内存瓶颈。由于频繁子图按降序进行处理，大量挖掘任务集中在前端节点，同时产生大量挖掘结果，且排序越靠前的子图就越频繁，这些子图将被优先挖掘。而排在后面的子图因为瓶颈的出现，就可能不再被挖掘，而是选择一些结果并提前停止挖掘。此外，结果的规模随着顺序呈指数下降。因此，在大多数情况下，这种策略很难实现负载平衡。递增策略（静态划分）：该策略给第一个节点分配一个子图，给第二个节点分配两个子图，给第三个节点分配3个子图，依

15、此类推，最后一个节点被分配剩余的所有子图。实施此策略可以提高性能，并实现更好的负载平衡。但是，在大规模挖掘背景下，前端节点被分配太多子图会导致负载不平衡,此策略不再适用。单任务策略（静态划分）：该策略给各节点分配一个子图，剩余子图分配给最后一个节点。这种策略有时可以实现很好的性能。循环策略（静态划分）：该策略先按照正序给各节点分配一个子图，再按照反序给各节点分配一个子图。按照这种方式一直循环，直到所有频繁子图都被分配为止。当数据集足够大且并行度不是特别高时，循环策略可实现更好的负载平衡。监管策略（动态划分）：基于任务队列按照顺序将子图依次分配给各节点，然后将剩余子图分配给最早完成任务的节点。整

16、个过程持续到挖掘结束。理论上,动态划分策略比静态划分策略更能实现负载平衡。为了实现这种动态策略，将PrOCeSS（）视为一个“监工”,监管所有任务。当节点完成任务时，它首先向process（）询问剩余子图的信息。ProCeSS（）将搜索子图任务队列并返回信息。当任务队列不为空时，process。将为此节点分配一个新的子图。否则，它将回复“1”并计数。当计数等于节点数时，process（）将结束工作。另外，当节点收到“1”时，也将结束工作。动态策略可以实现比静态策略更好的负载平衡，但由于节点和ProCeSS（）需要通信，因此整体性能不一定更优。但是，在大多数情况下建议采用动态策略。5种划分策略的示例如图2所示。iiltttPM3.2.2 删除多节点冗余结果为了避免