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

CPU-MIC异构并行架构下基于大规模频繁子图挖掘的药物发现算法摘要：频繁子图挖掘是许多实际应用领域中需要解决的重要问题，由于计算密集性、挖掘的图集及其结果容量大，现有的频繁子图挖掘方案无法满足时间需求，其处理效率是目前面临的主要挑战。原创性地提出了并行加速的频繁子图挖掘工具cmFSMocmFSM主要在3个层次上进行并行优化：单节点上的细粒度OpenMP并行化、多节点多进程并行化和CPU-MlC协作并行化。在单节点上cmFSM的处理速度比基于CPU的最佳算法快一倍，在多节点方案中cmFSM提供可扩展性。结果表明，即使只使用一些并行计算资源，cmFSM也明显优于现有的最先进的算法。这充分表明提出的工具在生物信息学领域的有效性。关键词：频繁子图挖掘；生物信息学；并行算法；内存约束；同构；集成众核引言在生物信息学研究中，为帮助在药理学化合物数据库或生物网络的核心功能结构中寻找新药，频繁子图挖掘的解决方案尤为重要。但现有的频繁子图挖掘方案无法有效解决内存消耗与时间需求问题。LinW等人认为频繁子图挖掘问题可分为两个方面：一方面是在一个图的不同区域挖掘子图，适用于社交网络分析领域；另一方面是在大规模图集中挖掘子图，适用于计算药理学和生物信息学领域。两方面都面临共同的问题：大规模挖掘任务产生的大量挖掘结果超过了单台机器的存储器空间，且无法满足时间需求。并行技术是解决这类问题的有效方案。针对第一方面，专家已经提出基于串行CPU技术、并行计算框架(M叩RedUCe、MPI、Spark)及图形处理器(graphicsprocessingunit,GPU)的解决方案。本文意在解决生物信息学领域中频繁子图挖掘的问题。2相关工作现有频繁子图挖掘方案以递归计数为基础，可以挖掘出所有频繁子图，且大部分频繁子图挖掘算法基于广度优先搜索(breadthfirstsearc,BFS)改进生成，例如基于先验的挖掘算法(apriori-basedalgorithmformining,AGM)和频繁子图挖掘(frequentsubgraphdiscovery,FSG)算法工具。但是深度优先搜索(depth-first-search,DFS)内存需求更低、性能更优。MeinIT等人对一些典型的DFS算法(如MoFa、FFSMgSanftGaston)进行了定量比较和详细比较，发现遇到大规模挖掘任务时，它们很难满足时间需求。值得注意的是，它们都是单核串行版本。此外，BUehrerG等人提出了多核系统中的并行挖掘策略，并在多个内存处理器间划分挖掘任务。这些解决方案充分利用了单节点上的机器资源实现加速挖掘。然而，这些方案都是基于内存的，并假设内存空间适配于图集和挖掘规模。但是，随着数据量的增加以及支持度的降低，挖掘规模呈指数递增，内存空间不再适配。为解决这个问题，WangC等人和NgUyenSN等人基于磁盘分别提出ADIMine算法和数据分区方法。但是这类方案又面临着访问数据的巨大开销问题。HillS等人基于M即RedUCe框架提出了IFSM算法。该算法首先计算图表集合中的所有频繁子图的支持度。其次，排除未达到设定支持度的频繁子图。与IFSMn0类似，FSM-H和mrFSM也是通过迭代方法在MapReduce框架上开发的，且更加关注每次迭代中的负载平衡。然而M叩RedUCe框架不适合迭代计算,可能会产生大量I/O和序列化开销，因此基于MapReduce的这些方案仍然会产生严重的性能问题。MaPRedUCe框架上性能更为出色的是MRFSM。MRFSM不采用迭代方法，而是根据支持度智能化地过滤频繁子图，再将所有频繁子图分配给所有机器进行挖掘，并整合最终结果。因为没有迭代，所以它能提供比IFSM、FSMH和mrFSM更好的性能。但是MRFSM使用标准I/O和数据间的交互，其性能受到严格限制。此外对于大规模挖掘任务，每台机器上会产生严重的存储压力，MRFSM无法满足时间需求。针对大规模挖掘问题，笔者提出了CmFSM算法。该算法分别在3个方面实现了并行化：单节点上的细粒度OPenMP(共享存储并行编程)并行化、多节点多进程并行化和CPU-MIC协作并行化。3算法介绍CmFSM算法实现了多级别和多粒度的并行性，并以集成众核(manyintegratedcore,MIC)为加速器，使用OPenMP实现多线程，目的是解决药物爰现过程中大规模频繁子图挖掘的时间需求和内存限制等问题。信息传递接口(messagepassinginterface,MPI)基于4种静态任务划分策略和一种基于监管的动态任务划分策略，实现最佳负载平衡。此外，在传输模式下使用MIC仅传输双边频繁子图，并备份复杂数据结构，以避免过度传输造成的瓶颈。通过充分利用MIC的多核计算能力，可以在CPU和MIC协作的情况下达到预期的执行速度。3.1 单节点上的OPenMP并行化3.1.1 并行化策略基于DFS的频繁子图算法难以控制并行粒度，且无法控制递归过程，造成程序一直调用函数的后果，从而产生大量挖掘结果，这必然会导致不同挖掘任务间的负载不平衡。为了解决这个问题，笔者采用基于OPenMP的细粒度并行策略。具体来说,挖掘频繁子图的过程将公共递归挖掘过程转化为BFS循环挖掘过程，从而实现单边增长粒度的并行性。此外，笔者创立了4个新缓冲区：原子区、t子区、1子区和C子区。原子区记录每个级别(从单边到多边的频繁级别)挖掘的子图集,并按照规定级别进行挖掘，其中同一级别的子图具有相同的边数。当原子区没有空间时，将进行下一级挖掘任务。t子区是单线程任务中的局部变量，记录每个子图边挖掘到的子图。1子区也是单线程任务中的局部变量，它记录从t子区并集中获得的每个线程的所有子图挖掘情况。c子区记录从每个级别挖掘得到的子图集。在单线程结束时，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：Ien-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：clear(cchildren);24：Ien-Size(Children);25：endwhile26-29：samewitholdalgorithm10-13;30：endfor总体来说，此操作计算规模大，但因为并行粒度小，在线程调度中不使用大多数CPU资源，而且可以通过OPenMP的动态调度策略轻松实现良好的负载均衡。此外，递归挖掘过程被循环挖掘过程替换，因此不需要系统协助管理堆栈，这会产生额外的加速。3.1.2内存管理深度优化频繁子图挖掘的主要挑战是内存约束。为了实现内存重用和内存空间的有效利用，笔者采用“动态应用和存储指针”的策略。具体来说，程序动态地挖掘子图，并在图代码结构中存储边指针，而不是存储实际边对象，以便挖掘出的频繁子图与其原子图共享大多数边，这将显著节省内存空间。内存重用示意如图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多节点多进程并行加速3.2.1 任务划分策略多节点程序的最大挑战是通信开销。使用粗粒度并行策略可有效地避免大量通信开销。其过程是先通过MPI划分频繁子图，然后每个进程在其节点中保存其挖掘结果，以避免大量输出文件造成单节点内存压力。最后，将所有输出文件整合为最终挖掘结果。此外，结合单节点的多进程可为每个MPI进程创建多个线程完成并行化，以实现良好的性能。但是这种粗粒度策略不利于负载平衡，很容易导致数据倾斜，无法充分利用系统资源实现最佳性能。基于数据集的不同特征，笔者设计并提出了4种静态任务划分（即对等、递增、单任务和循环）策略和一种基于监管的动态任务划分策略，以尽可能地实现负载均衡。具体来说，4种静态任务划分和基于监管的动态划分如下所示。对等策略（静态划分）：该策略平均分配挖掘任务，但不绝对，只需保证分配给各节点的任务相等或差值不大于1即可。然而，实验发现负载极不平衡，很容易遇到内存瓶颈。由于频繁子图按降序进行处理，大量挖掘任务集中在前端节点，同时产生大量挖掘结果，且排序越靠前的子图就越频繁，这些子图将被优先挖掘。而排在后面的子图因为瓶颈的出现，就可能不再被挖掘，而是选择一些结果并提前停止挖掘。此外，结果的规模随着顺序呈指数下降。因此，在大多数情况下，这种策略很难实现负载平衡。递增策略（静态划分）：该策略给第一个节点分配一个子图，给第二个节点分配两个子图，给第三个节点分配3个子图，依此类推，最后一个节点被分配剩余的所有子图。实施此策略可以提高性能，并实现更好的负载平衡。但是，在大规模挖掘背景下，前端节点被分配太多子图会导致负载不平衡,此策略不再适用。单任务策略（静态划分）：该策略给各节点分配一个子图，剩余子图分配给最后一个节点。这种策略有时可以实现很好的性能。循环策略（静态划分）：该策略先按照正序给各节点分配一个子图，再按照反序给各节点分配一个子图。按照这种方式一直循环，直到所有频繁子图都被分配为止。当数据集足够大且并行度不是特别高时，循环策略可实现更好的负载平衡。监管策略（动态划分）：基于任务队列按照顺序将子图依次分配给各节点，然后将剩余子图分配给最早完成任务的节点。整个过程持续到挖掘结束。理论上,动态划分策略比静态划分策略更能实现负载平衡。为了实现这种动态策略，将PrOCeSS（）视为一个“监工”,监管所有任务。当节点完成任务时，它首先向process（）询问剩余子图的信息。ProCeSS（）将搜索子图任务队列并返回信息。当任务队列不为空时，process。将为此节点分配一个新的子图。否则，它将回复“1”并计数。当计数等于节点数时，process（）将结束工作。另外，当节点收到“1”时，也将结束工作。动态策略可以实现比静态策略更好的负载平衡，但由于节点和ProCeSS（）需要通信，因此整体性能不一定更优。但是，在大多数情况下建议采用动态策略。5种划分策略的示例如图2所示。iiltttPM3.2.2 删除多节点冗余结果为了避免挖掘原子图产生多余的结果，挖掘后的频繁子图需删除。而在多节点模式中，各节点在挖掘过程中只能处理各自的频繁子图且不会删除其他节点中的子图，从而造成冗余结果。为了解决此问题，笔者将并行算法扩展到多节点模式，且分别处理分配给各节点的频繁子图。这个特性有可能在挖掘过程之前去除先于当前对象的多余频繁子图。3.3CPU-MIC协作并行优化3.3.1 cmFSM的协同并行化CPU-MlC协作采用中粒度的并行策略。总体来说，先在CPU和MIC之间划分频繁子图，并采用传输模式将频繁子图转移到MIC0通过承受一定的通信开销，并充分利用MIC的多核计算能力，可以实现负载平衡和预期的计算速度效果。CPU和MlC之间的协同过程如图3所示。值得注意的是，笔者没有使用粗粒度策略，因为在该策略下难以有效地实现负载平衡。另外，频繁子图不一定能合理地分配给每个进程。例如，有可能遇到一些进程只能负责一个子图。而且CPU和MlC之间存在计算能力差异，负载平衡将是一个巨大的挑战。此外，细粒度策略也不加以考虑，因为它不适配CPU和Mle之间的共享内存，且需要大规模的通信开销才能传输和划分子图。因此，这种策略也不利于提高整体效率。图3CPU-MIC协同并行框架3.3.2 内存重用一张MIC卡的内存大约为5OOOMB,无法与节点内存适配，而且内存分配和释放的速度比CPU慢。实验测试表明，在MlC上分配IOoOMB的内存大约需要5s。因此，必须降低MIC上的内存分配和释放效率，并最大限度地提高内存重用。除了“动态应用和存储指针”策略外，cmFSM可通过内存重用减少MIC上的内存分配时间，具体方法是创建一个计数器JObCoUnt记录工作号。如果count=1,则使用walloc_if(l)free_if(0),为列出的数组和对象分配内存;当count>l时，使用吐Ik)CJf(O)fireejf()”重用内存;最后使用"a11ocjf(0)fteejf(l)”在操作完成后释放内存。这种方式可最小化MIC上的内存分配和释放的频率。此外，当数据集相对较大且挖掘程度足够深时，仅一个频繁子图的挖掘过程也会耗尽MIC上的内存。在这种情况下，不能先传输所有要挖掘的子图，再挖掘其结果。因此笔者不是一次上传所有的频繁子图，而是采用迭代的方法，一次只上传同一频繁子图挖掘到的部分图，以方便数据压缩节省MIC的存储空间。3.3.3 数据传输优化尽管MIC支持C+STL(standardtemplatelibrary),但ICC(IntelC+compiler)不支持使用OffIoad模式传输频繁子图，它只支持没有指针的基本数据类型和数组。因此，笔者采用“拆除和恢复”的策略传输子图。在迭代中传输的n个频繁子图原理如图4所示。next neone.l首先，拆除频繁子图，并集成它们的元素，以使相同结构的频繁子图存储在同一个连续缓冲区中。然后通过Offload模式将这些缓冲区传输到MlC中，并在MIC上分配内存。最后通过填充这些缓冲区中的相应元素，在MlC中恢复子图。从图4可以发现，在传输过程中使用了7个缓冲区。因为边的代码格式是五元组(ix>iy>x、a>y),所以前5个缓冲区用于传输边。下标为0的元素代表第一个公共边。以下n个元素表示每个子图的第二条边。next缓冲区表示n个子图的节点数。gs缓冲区是数据集中频繁子图的编号列表。因为数字从0开始，笔者使用-1分隔这些列表。总体而言，笔者可以有效地组织和传输CPU和MlC之间的数据。neO11e,1gs,-1gS-IgS,H-1图4双边子图迭代传输格式另外，一些复杂的数据结构将用于整个挖掘过程，例如处理子图集可能产生巨大的传输开销和内存分配开销。因此，复杂的数据结构需要备份，这些数据结构是可重用的，并且难以最大性能化传输。具体来说，将分析参数传递给MIC,协处理器可以根据这些参数读取数据并自行构建子图集，此操作简单，可以在MlC上快速完成。在许多情况下，挖掘结果太大，无法通过。ffload模式进行传输。因此返回结果计数以显示CPU的总体结果，而不是将所有挖掘结果返回给CPUo具体挖掘结果将直接写在MlC±o这样可以轻松合并这些文件数据获得整个结果。3.3.4 CPU>MlC之间的负载平衡和数据分配根据先前的策略，只有从相同边挖掘的频繁子图才将在迭代中被转移到MICo如果继续挖掘这些频繁子图，挖掘结果将更贴合实际。因为CPU和MIC的计算能力在测试后依然紧密贴合，所以笔者简单地采用一种使用区间划分的静态策略，使具有稍强计算能力的主机设备首先启动，这是因为任务队列前端的频繁子图理论上仍然具有很多充满可能性的挖掘，以此实现CPU和MIC的负载平衡。基于3个MIC的数据划分和CPU-MIC协作挖掘过程如图5所示。虽然每个设备的挖掘深度和计算规模都不确定，但是所有过程都将持续到频繁子图不再挖掘为止。在多节点模式中，为形成不同的任务队列，只为每个节点分配不同的频繁子图。图5数据划分和CPU-MlC协作挖掘过程4实验结果笔者在5个方面评估了CmFSM的性能：单节点并行化、多节点划分策略、多节点多线程加速效率、多节点协作和多节点CPU/MIC协作。4.1 设置和数据集CmFSM使用STL在C+中实现，并使用-02编译标准进行编译。第一个实验是在高性能服务器上进行的，该服务器由8个18核XeonE7-8800v3CPU处理器、2个57核XenoPhi3120协处理器和2个K40MGPU组成，内存为2TB,操作系统是RedHatEnterpriseLinuxServer7.1版。接下来的4个实验是在天河-2超级计算机上进行的。配置见表1。«1天河-2超级计算机配置硬件参数详情节点数/个计，节点CPU内存协处理播内存通借系统文件系统操作系统160002个XeCnE5CPU和3个XeonPhltfr处理器MGB8GB互联网网络1.Ustre文件系统Kyhn2.6.3243LTH.x86j4笔者对合成数据集的实验进行了全面的性能研究。测试的第一个数据集是PrediCtiVeTOXiCOIOgy数据集（PTE）。此稀疏数据集含有340种化合物，24个不同原子，66种原子类型和4种键。第二个数据集是美国国家癌症研究所（NationalCancerInstitute,NCI）/美国国立卫生研究院（NatiOnallnStitUteSOfHealth,NIH）的发展治疗计划（developmentaltherapeuticsprogram,DTP）的艾滋病（AlDS）抗病毒筛选化合物数据集。此数据集含有43405种化合物。筛选实验的结果可分为3类：CA（高活性）、CM（中等活性）、CI（无效）。笔者仅在包含422个分子（数据集DTP）的测试中使用CA类。合成图数据集使用类似于InokUChiA等人描述的合成数据生成器。用户可以设置参数，以确定图的数量和平均大小。设定测试的3个数据集（Sl>S2、S3）分别包含IOoOO个图形、20000个图形和100（M）O个图形。表2显示了这5个数据集更多的信息。我2数据集僖息数据集Hft*边平均边最长点平均点最大PTE3402821427214DTP4224219640188Sl100002927626225S2200003221430197S310000045321382784.2 单节点并行化笔者将cmFSM与各种功能相当的频繁子图挖掘工具进行比较，如FSM>FFSM>gSpanftGastono这里笔者使用3个数据集进行分析，结果表明CmFSM可以比拥有相对较低并行化水平中的任何其他挖掘工具呈现出更好的性能。表3比较了cmFSM和其他挖掘工具在PTE数据集上的结果和运行时间。从表3中不难发现，cmFSM具有显著的性能优势。表3中的最后3列表示CmFSM分别启动2个线程、8个线程和32个线程。可以看出，即使是串行版本,CmFSM的运行时间也小于gSpan。此外，只要启动超过8个线程，cmFSM的运行时间就比其他4种工具都小。这证明即使只应用一些并行计算资源，cmFSM依然可以表现出比其他4种挖掘工具更好的性能。此外，挖掘结果的一致性也表明笔者提出的并行优化不会影响挖掘的正确性。«3PTEcn8«HSJR事小支持度沱加FSMFFSM8$PanGmonCInFSMcmFSM.2EFSMjlcmFSM.322%136949312.2178.12101.1236.5397.3268.232i.5l6.J24%593511.22S.21Z2I2.133.2B2.9«1.030.446%23264.122.012.511.0!1.251.010.420.2111%I3232.SI1.03IJI0.660710.630.270.1610%M41.690.750.930.M0.490470.210.142OH1900.66O.SB0.650.120.150.170.0o.oe30%M0.310.290.330.060.0ft0.090.070.06FFSMGaston '» gSpan cmlrSMCinFSMJtCmFSM_4t-cmFSM 8tcmFSM 16t图6反映了DTP数据集上各挖掘工具的运行时间比较。从图6中可以看出,在DTP数据集上与其他挖掘工具相比，拥有线程较少的CmFSM也可以获得更好的性能。450040003500300025002000I500I00050004%5%6%7%8%9%10%20%30%最小支持度图6DTP数据集上各挖掘工具的运行时间比较线程数/个图7反映了cmFSM的优异并行加速效果。笔者分别设定1%、2%、3%、4%作为支持度，以形成不同的挖掘规模。可以看出，随着线程数量加倍，加速效果呈线性递增。此外，支持度越小，挖掘规模越大，cmFSM的并行效率越高。这表明cmFSM可以很好地应用于大规模挖掘过程。图7并行优化实验4.3 多节点划分策略为了比较不同模式下5种划分策略的优缺点，分别设置4%、2%和1%作为支持度，对DTP、PTE和S2数据集进行了实验。另外，为了消除多线程并行化的影响，只启动单进程的单个线程。在DTP数据集上的运行结果见表4。从表4可以看出，随着进程数的增加，这5种策略的运行时间都没有显著降低。这是因为第一个频繁子图将在DTP数据集中产生80%的结果。因此，第一个频繁子图挖掘进程被视为实验瓶颈。而且对等战略是最糟糕的策略，单任务和递增策略相对更快，动态策略由于通信开销，性能略低于这两策略。然而无论挖掘深度如何，第一个频繁子图的挖掘时间始终是这种特殊数据集的瓶颈。表45种划分策略在DTP数据集上的运行结果（支持度为4%）进程数对等/$单任务/s递增/S循环/S动态/S236463183319235323203335843174318534933213435673178319134683208535523185318834523216PTE和S2数据集上的多节点运行如图8和图9所示。可以看出，对等策略是最差的策略，单任务和递增策略性能相当，循环策略的性能优势随着进程的增加而增加。而起初性能最好的动态策略随着进程的增加逐渐弱于循环策略，这是因为单边频繁子图的挖掘过程会有频繁的任务请求和通信开销。但是这不是一个明显的弱点，当挖掘规模足够大时，动态策略总是优于所有静态策略的。因此,笔者更推荐使用动态策略。图8数据集PTE分区策略结果（支持度为2%）12 00010 0008 0006 0004 0002 0002481632进程数/个图9数据集S2分区策略结果（支持度为1%）4.4 多节点多线程加速效率为了评估多节点加速效率，笔者分别对Sl、S2和S3数据集设置1%、1%和2%的支持度，并进行实验。表5为多节点可扩展性的效果。实验中采用动态策略，这是因为动态策略可以在所有的策略中实现平均最佳性能，通过这种方式简化测试。从表5可以看出，随着数据的增加，cmFSM并行效率依然很高，这意味着cmFSM可以很好地适用于大规模挖掘任务。»5多加点速效率数据集运行时间12枝2进程6炫程24犊2进程12线程48彼4进程12城程96核4迸程24战程192接8进程24我程384核16进程24域程Sl7424082231318374S2I73292!487261I6K104S322821Il76360693I*I6408714.5 单节点CPU/MIC协作使用分别以1%、1%和2%作为支持度的3个数据集来评估单节点CPU/MIC协作效果。结果见表6。由表6可知，通过2个CPU和3个MlC的并行加速，速度比单核运行提升明显。这充分表明了工具的运行加速效果。表6节点CPU/MIC协作运行时间数据集燧行时间/$1核2CPUICPUarlMIC2CPU&2MIC2CPU&3M1CSl7590382274234208S218944«75607486410S32667941162577496457580图10为不同数据集上不同CPU/MIC协作模式的比较，可以发现，挖掘任务规模越大，cmFSM加速效果就越好。此外，笔者在S3数据集上获得了50倍的加速，比预期好很多。这是因为笔者采用内存重用、数据传输等进行优化。Sl数据集实验很快就达到了加速瓶颈，2MIC模式和3MIC模式之间差距很小，这是由数据集本身特征引起的。在Sl数据集中大量挖掘任务集中在主机和第一个MIC协处理器中。不过在大多数挖掘任务中，CPU/MIC的加速效果依然显著。60图10单节点上的CPU/MIC协作4.6 多节点CPU/MIC协作笔者使用最大数据集S3,分别以2%、1%和0.8%作为支持度来评估多节点CPU/MIC的协作效果。表7表示节点充分利用2个CPU和3个MIC的结果。表7多节点CPU/MIC协作运行时间最小支持度运行时间/S1节点2节点4节点8节点2%1%0.8%532028161736993183299802550829184325223026128476295图11为S3数据集上不同支持度多节点加速的比较,从表7可看到具体情况,笔者发现在大挖掘规模下可以实现更好的多节点加速效果。总体来说，这些实验表明多节点比线性加速更弱，这是由多节点模式通信开销、进程竞争和同步引起的。但是，这种情况不影响CmFSM在大规模挖掘任务下的可扩展性。图11多节点上的CPU/MIC协作5结束语cmFSM是一个可扩展的并行频繁子图挖掘工具,它基于CPU/MIC协作实现多级别和多粒度的并行性。首先基于细粒度并行策略，将常见的递归挖掘过程转换为单节点上的BFS循环挖掘过程。除了一些特殊的数据集，cmFSM呈现出接近线性加速的效果。其次，基于粗粒度并行策略实现4种静态划分（即对等、递增、单任务和循环）策略和一种基于监管的动态划分策略，以尽可能地实现负载平衡。实验表明，特别是面对大规模挖掘任务时，动态划分策略表现出比所有静态划分策略更好的性能。此外，结合单节点上的多线程工作，cmFSM允许通过为每个MPl进程创建多个线程来生成二级并行化,这显示CmFSM的可靠扩展性。第三，基于中粒度并行策略备份数据结构，以避免过度传输出现瓶颈。通过内存重用和充分利用MIC的多核计算能力，可以在单个节点上为某些数据集获得超过50倍的加速。此外，多节点CPU/MIC协作在大规模挖掘任务下提供了出色的可扩展性。此外，几个数据集的实验评估表明，即使只使用一些并行计算资源，CmFSM明显优于现有的算法。这充分表明笔者提出的工具的有效性。但是在一些特殊的数据集中，CmFSM会显示出很大的局限性。在这种情况下，它将很快达到加速瓶颈，这需要笔者进一步改进CmFSM工具。附参考资料：频繁子图挖掘算法的应用分类关键词：应用场景顶点TIW一化合可变标过2l*-B彳 *ra袅1应用分类监金华v信IlRIJh ½2RiHu>望空学蒙代gp71*弁帙绐，翼必Xtt潭动力声Bft<nk出行大yar：摘要：频繁子图挖掘属于数据挖掘领域的一部分，越来越受到研究学者的广泛应用，目前己经成功应用于生物学、化学、社会学等领域。频繁子图算法的操作是从给定的图数据库中，根据同构测试及支持度计算判断出频繁子图。本文整理出国内外学者基于频繁子图的应用文献。根据文献，对这些应用进行分类，列表整理出各个应用领域的数据集的开源地址和图的顶点及边的标识含义。关键词：频繁子图挖掘;应用场景;顶点;边1引言在数据挖掘的领域中，频繁子图挖掘算法越来越受到国内外研究学者的关注。频繁子图将各种数据处理成顶点到顶点的逻辑关系的表示，在该模型山中，顶点和对应的边关系可以具有与它们相关联的标签，这些标签不是唯一的。使用这样的图表示，频繁模式的问题变成了在整个图上寻求频繁出现子图的问题，运用频繁子图算法挖掘其潜在的价值。频繁子图挖掘算法即在给定的图中根据设定的支持度阈值，寻找出同构子图大于等于给定支持度阈值的子图。频繁子图算法的发展历经二十年，基于频繁子图的应用也越来越广泛。2运用场景在由顶点和边构成的图中，顶点有其分类的标识，边亦有其分类的标识，我们需要在给定的图数据库中寻找出顶点标识和标识对应一致的子图，计算出支持度，若一旦支持度超过给定的阈值，便输出其子图，其子图便是一个频繁子图。LinW2等人认为频繁子图挖掘问题分为两个方面：在一个大图的不同区域挖掘子图适用于社交网络分析等领域;在大规模图集中挖掘子图适用于生物信息学和计算药理学等领域。图集上的挖掘是指在多张图的图数据库中挖掘这些图中共现的子图。在一张大图上的挖掘则是在一张图上挖掘图内出现的子图。基于图事务集合的频繁子图挖掘算法与基于单个大图的频繁子图挖掘算法不同，在计算候选子图支持度的时候，基于图事务集合的频繁子图挖掘算法只需要计算候选子图与图事务集合中满足子图同构的小图的个数，而基于单个大图的频繁子图挖掘算法需要在这个大图中找出候选子图所有的同构的子图，计算用同构的子图的候选子图支持度3。如表1所示，进行的应用分类。(1)生物学对多种分子和基因相互作用网络的研究来分析生物功能，其核心问题就发现网络的功能模块，其目的是了解生物系统如何在基本单元的基础上组织起来.并可以通过频繁子图挖掘算法产生一定的生物功能，为分析理解生命基本规律提供依据2引。其中基因调控网络是有向图。(2)化学在化学领域中，不同种类的化合物往往含有一些关键子结构从而具有某一相同的性质，这些关键字结构共同决定这一相同性质。对于由具有某一相同性质的一类化合物组成的数据集，可以通过频繁子图挖掘算法找出频繁出现的关键子结构，然后利用这些关键子结构预测其他一些化合物是否也具有这样的相同性质124o(3)社交网络社交网络分析即用户关系分析，其含义是分析预测用户之间的态度即推测出社交网络中某个使用者对另一个使用者的潜在态度，研究得到的成果对社交网络非常重要，主要体现在应用价值方面，可以通过频繁子图挖掘算法挖掘出用户关系的关系模式，进而对社交网络中的用户提供个性化的推荐、辨认网络中异常的用户，产生全新的用户聚类。(4)信息安全信息安全方面包括恶意代码检测，可疑金融交易识别，软件缺陷检测等。通过恶意代码或缺陷代码或可疑特征数据库，通过频繁子图算法去匹配检测代码或者用户交易行为，进而标记出所有恶意代码或缺陷代码或可疑交易的出处。(5)其他在频繁子图的应用中，首先需要定义顶点与顶点之间的关系及顶点信息和边信息。根据图数据库，根据顶点标识和边标识挖掘频繁的关系模式。本文根据应用方向的参考文献整理得到如下信息.如表2所示。3结论本文结合国内外学者的文献，根据应用领域将这些文献进行分类，列表整理出各个应用领域的数据集的开源地址和图的顶点及边的标识含义。众多文献表明，随着大数据的兴起,频繁子图挖掘算法结合分布式框架越来越成为主流方式。参考文献：1 KuramochiM,KarypisGFrequentsubgraphdiscoveryClPro-ceedings2001IEEEInternationalConferenceonDataMin-ing.29Nov.-2Dec.200LSanjose,CA,USA.1EEE,2001：313-320.2 1.inWQ.EfficienttechniquesforsubgraphminingandqueryprocessingD.NanyangTechnologicalUniversity,2015.DOI：10.32657/10356/62137.张天明.大图上频繁子图挖掘算法的研究D.沈阳：东北大学。2014.4谢均，尚学群，王淼，等.解决数据样本不平衡性的频繁子图挖掘算谕J.计算机工程与应用，2008,44(36)：146-149.5 MrzicA,MeysmanP,BittremieuxW,etal.GraspingfrequentsubgraphminingforbioinfonaticsapplicationsJl.BioDataMining,2018,11(1)：1-24.6 SahaTK,KatebiA,DhifliW,etal.Discoveryoffunctionalmo-tifsfromtheinterfaceregionofoligomericproteinsusingfre-quentSubgTaphminingJl.ACMTransactionsonComputationalBiologyandBioinformatics,2019,16(5)：1537-1549.7 GawronskiAR,TurcotteM.RiboFSM：Frequentsubgraphmin-ingforthediscoveryofRNAstructuresandinteractionsJl.BMCBioinformatics,2014,15(13)：1-15.汪涛.基于频繁子图挖掘的细胞器通信模式研究D.哈尔滨：哈尔滨工业大学，2014.9屠黎阳，杜俊强，接标，等.基于判别性子图重构的轻微肝性脑病分类J.模式识别与人工智能,2016,29(9)：832-839.10高正康