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

doi:10.11959/j.issn.2096-0271.2019016

大数据 ›› 2019, Vol. 5 ›› Issue (2): 89-103.doi: 10.11959/j.issn.2096-0271.2019016

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

彭绍亮¹,牛琦¹,李肯立¹,邹权²

¹ 湖南大学信息科学与工程学院，湖南长沙 410082
² 电子科技大学基础与前沿研究院，四川成都 610054

出版日期:2019-03-15 发布日期:2019-04-04
作者简介:彭绍亮（1979- ），男，博士，湖南大学信息科学与工程学院教授，国家超级计算长沙中心（湖南大学）副主任。长期从事高性能计算、大数据、生物信息、人工智能、区块链等技术研究工作，担任国防科技大学“天河”生命科学方向负责人，深圳华大基因研究院“特聘教授”，湖南大学“岳麓学者”三级教授。发表学术论文上百篇。参与“天河”系列超级计算机应用软件研发工作，参与国家“973”项目、“863”项目、军队重大型号项目等13项，获军队科技进步奖一等奖1项，中国计算机学会（CCF）科学技术奖自然科学二等奖，2016年荣立三等功。|牛琦（1995- ），男，湖南大学信息科学与工程学院硕士生，主要研究方向为计算生物学。|李肯立（1971- ），男，湖南大学信息科学与工程学院院长，国家超级计算长沙中心主任，教育部“长江学者”特聘教授、国家杰出青年科学基金获得者、国家“万人计划”科技创新领军人才。学术兼职有教育部“高效能计算学科创新引智基地”负责人、数据分析湖南省工程技术研究中心主任。担任国家超级计算创新联盟副理事长、新一代人工智能产业技术创新战略联盟专家委员会委员、IEEE高级会员、CCF杰出会员、CCF高性能计算专业委员会常务委员、湖南省计算机学会秘书长等。主要研究方向为并行分布式处理、超级计算与云计算、面向大数据和人工智能的高效能计算等。|邹权（1982- ）男，电子科技大学基础与前沿研究院教授，IEEE会员，ACM会员，CCF高级会员，中国人工智能学会会员（粗糙集与软计算专业委员会委员、生物信息学与人工生命专业委员会委员、机器学习专业委员会通讯委员），中国运筹学会会员，中国自动化学会会员。主要研究方向为生物信息学、机器学习和并行计算，现主要研究基于并行计算方法的下一代测序数据的蛋白质分类、基因组装配、注释和功能分析。
基金资助:
国家重点研发计划基金资助项目(2017YFB0202602);国家重点研发计划基金资助项目(2018YFC0910405);国家重点研发计划基金资助项目(2017YFC1311003);国家重点研发计划基金资助项目(2016YFC1302500);国家重点研发计划基金资助项目(2016YFB0200400);国家重点研发计划基金资助项目(2017YFB0202104);国家自然科学基金资助项目(61772543);国家自然科学基金资助项目(U1435222);国家自然科学基金资助项目(61625202);国家自然科学基金资助项目(61272056)

A scalable CPU-MIC coordinated drug-finding tool by frequent subgraph mining

Shaoliang PENG¹,Qi NIU¹,Kenli LI¹,Quan ZOU²

¹ College of Computer Science and Electronic Engineering,Hunan University,Changsha 410082,China
² Institute of Fundamental and Frontier Sciences,University of Electronic Science and Technology of China,Chengdu 610054,China

Online:2019-03-15 Published:2019-04-04
Supported by:
National Key Research and Development Program of China(2017YFB0202602);National Key Research and Development Program of China(2018YFC0910405);National Key Research and Development Program of China(2017YFC1311003);National Key Research and Development Program of China(2016YFC1302500);National Key Research and Development Program of China(2016YFB0200400);National Key Research and Development Program of China(2017YFB0202104);The National Natural Science Foundation of China(61772543);The National Natural Science Foundation of China(U1435222);The National Natural Science Foundation of China(61625202);The National Natural Science Foundation of China(61272056)

摘要/Abstract

摘要：

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

关键词: 频繁子图挖掘, 生物信息学, 并行算法, 内存约束, 同构, 集成众核

Abstract:

Frequent subgraph mining is an important issue to be solved in many practical fields.Due to the computational intensiveness,the mining of the atlas and the large capacity of the results,the existing solutions can not meet the time requirements,and its efficiency is currently the main challenge.The frequent subgraph mining tool cmFSM for parallel acceleration was originally proposed.cmFSM performs parallel optimization on three levels:fine-grained OpenMP parallelization on a single node,multi-node multi-process parallelization and CPU-MIC collaborative parallelization.cmFSM is twice as fast as the best CPU-based algorithm on a single node and provides scalability in a multi-node approach.In the future,we will continue to improve the scalability of multiple solutions.The results show that even with only a few parallel computing resources,cmFSM is significantly better than the most advanced algorithms available.This fully demonstrates the effectiveness of the proposed tool in the field of bioinformatics.

Key words: frequent subgraph mining, bioinformatics, parallel algorithm, memory constraints, isomorphism, many integrated core

中图分类号:

TP31

彭绍亮, 牛琦, 李肯立, 邹权. CPU-MIC异构并行架构下基于大规模频繁子图挖掘的药物发现算法[J]. 大数据, 2019, 5(2): 89-103.

Shaoliang PENG, Qi NIU, Kenli LI, Quan ZOU. A scalable CPU-MIC coordinated drug-finding tool by frequent subgraph mining[J]. Big Data Research, 2019, 5(2): 89-103.

图/表 18

图1

图2

图3

图4

图5

表1

表2

表3

图6

图7

表4

图8

图9

表5

表6

图10

表7

图11

参考文献 24

[1]	LIN W . Efficient techniques for subgraph mining and query processing[D]. Singapore:Nanyang Technological University, 2015.
[2]	HUAN J , WANG W , PRINS J ,et al. SPIN:mining maximal frequent subgraphs from graph databases[C]// The 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,August 22-25,2004,Seattle,USA. New York:ACM Press, 2004: 581-586.
[3]	JIANG X , XIONG H , WANG C ,et al. Mining globally distributed frequent subgraphs in a single labeled graph[J]. Data and Knowledge Engineering, 2009,68(10): 1034-1058.
[4]	KURAMOCHI M , KARYPIS G . Finding frequent patterns in a large sparse graph[J]. Data Mining ＆ Knowledge Discovery, 2005,11(3): 243-271.
[5]	KANG U , TSOURAKAKIS CE , FALOUTSOS C . PEGASUS:mining peta-scale graphs[J]. Knowledge ＆ Information Systems, 2011,27(2): 303-325.
[6]	REINHARDT S , KARYPIS G . A multi-level parallel implementation of a program for finding frequent patterns in a large sparse graph[C]// 2007 IEEE International Parallel and Distributed Processing Symposium,March 26-30,2007,Rome,Italy. Piscataway:IEEE Press, 2007: 1-8.
[7]	WU B , BAI Y L . An efficient distributed subgraph mining algorithm in extreme largegraphs[C]// The 2010 International Conference on Artificial Intelligence and Computational Intelligence,October 23-24,2010,Sanya,China. Heidelberg:Springer, 2010: 107-115.
[8]	YAN Y , DONG Y , HE X ,et al. FSMBUS:a frequent subgraph mining algorithm in single large-scale graph using spark[J]. Journal of Computer Research and Development, 2015,52(8): 1768-1783.
[9]	LIN W , XIAO X , XIE X ,et al. Network motif discovery:a GPU approach[C]// IEEE 31st International Conference on Data Engineering,April 13-17,2015,Seoul,Korea. Piscataway:IEEE Press, 2015: 831-842.
[10]	HILL S , SRICHANDAN B , SUNDERRAMAN R . An iterative MapReduce approach to frequent subgraph mining in biological datasets[C]// The ACM Conference on Bioinformatics,Computational Biology and Biomedicine,October 7-10,2012,Orlando,USA. New York:ACM Press, 2012: 661-666.
[11]	INOKUCHI A , WASHIO T , MOTODA H . An apriori-based algorithm for mining frequent substructures from graph data[C]// The 4th European Conference on Principles of Data Mining and Knowledge Discovery,September 13-16,2000,London,UK. London:SpringerVerlag, 2000: 13-23.
[12]	KURAMOCHI M , KARYPIS G . Frequent subgraph discovery[C]// IEEE International Conference on Data Mining,November 29-December 2,2001,San Jose,USA. Piscataway:IEEE Press, 2001: 313-320.
[13]	MEINL T , FISCHER I , PHILIPPSEN M . A quantitative comparison of the subgraph miners mofa,gspan,FFSM,and gaston[C]// European Conference on Principles and Practice of Knowledge Discovery in Databases,October 3-7,2005,Porto,Portugal. Heidelberg:Springer, 2005: 392-403.
[14]	BORGELT C , BERTHOLD M R . Mining molecular fragments:finding relevant substructures of molecules[C]// 2002 IEEE International Conference on Data Mining,December 9-12,2002,Maebashi City,Japan. Piscataway:IEEE Press, 2002: 51-58.
[15]	HUAN J , WANG W , PRINS J . Efficient mining of frequent subgraphs in the presence of isomorphism[C]// The 3rd IEEE International Conference on Data Mining,November 19-22,2003,Melbourne,USA. Washington,DC:IEEE Computer Society, 2003: 549-552.
[16]	YAN X , HAN J . gSpan:graph-based substructure pattern mining[C]// 2002 IEEE International Conference on Data Mining,December 9-12,2002,Maebashi City,Japan. Piscataway:IEEE Press, 2002: 721-724.
[17]	NIJSSEN S , . A quickstart in frequent structure mining can make a difference[C]// The 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,August 2225,2004,Seattle,USA. New York:ACM Press, 2004: 647-652.
[18]	BUEHRER G , PARTHASARATHY S , CHEN Y K . Adaptive parallel graph mining for CMP architectures[C]// The 6th International Conference on Data Mining,December 18-22,2006,Hong Kong,China. Piscataway:IEEE Press, 2006: 97-106.
[19]	WANG C , WANG W , PEI J ,et al. Scalable mining of large disk-based graph databases[C]// The 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,August 22-25,2004,Seattle,USA. New York:ACM Press, 2004: 316-325.
[20]	NGUYEN S N , ORLOWSKA M E , LI X . Graph mining based on a data partitioning approach[C]// The 19th Conference on Australasian Database,December 3-4,2007,Gold Coast,Australia.Darlinghurst:Australian Computer Society,Inc. , 2008: 31-37.
[21]	DEAN J , GHEMAWAT S . MapReduce:simplified data processing on large clusters[C]// The 6th Conference on Symposium on Opearting Systems Design ＆ Implementation,December 6-8,2004,San Francisco,USA. Berkeley:USENIX Association, 2004: 107-113.
[22]	BHUIYAN M A , AL H M . An iterative MapReduce based frequent subgraph mining algorithm[J]. IEEE Transactions on Knowledge＆ Data Engineering, 2013,27(3): 608-620.
[23]	LU W , CHEN G , TUNG A K H ,et al. Efficiently extracting frequent subgraphs using MapReduce[C]// 2013 IEEE International Conference on Big Data,October 6-9,2013,Silicon Valley,USA. Piscataway:IEEE Press, 2013: 639-647.
[24]	LIN W , XIAO X , GHINITA G . Largescale frequent subgraph mining in MapReduce[C]// 2014 IEEE 30th International Conference on Data Engineering,March 31-April l4,2014,Chicago,USA. Piscataway:IEEE Press, 2014: 844-855.

硬件参数	详情
节点数/个	16 000
计算节点	2个Xeon E5 CPU 和 3个 Xeon Phi协处理器
CPU内存	64 GB
协处理器内存	8 GB
通信系统	互联网网络
文件系统	Lustre文件系统
操作系统	Kylin 2.6.32-431.TH.x86_64

数据集	图数量/个	边平均	边最长	点平均	点最大
PTE	340	28	214	27	214
DTP	422	42	196	40	188
S1	10 000	29	276	26	225
S2	20 000	32	214	30	197
S3	100 000	45	321	38	278

最小支持度	挖掘结果					运行时间/s
最小支持度	挖掘结果	FSM	FFSM	gSpan	Gaston	cmFSM	cmFSM_2t	cmFSM_8t	cmFSM_32t
2%	136 949	312.21	78.12	101.12	36.53	97.32	68.23	21.51	6.32
4%	5 935	11.22	5.21	7.21	2.13	3.28	2.98	1.03	0.44
6%	2 326	4.12	2.01	2.31	1.01	1.25	1.01	0.42	0.21
8%	1 323	2.51	1.03	1.21	0.66	0.71	0.63	0.27	0.16
10%	844	1.69	0.75	0.83	0.38	0.49	047	0.21	0.14
20%	190	0.66	0.58	0.65	0.12	0.15	0.17	0.08	0.06
30%	68	0.31	0.29	0.33	0.06	0.08	0.09	0.07	0.06

进程数	对等/s	单任务/s	递增/s	循环/s	动态/s
2	3 646	3 183	3 192	3 532	3 203
3	3 584	3 174	3 185	3 493	3 213
4	3 567	3 178	3 191	3 468	3 208
5	3 552	3 185	3 188	3 452	3 216

数据集				运行时间/s
数据集	12核2进程6线程	24核2进程12线程	48核4进程12线程	96核4进程24线程	192核8进程24线程	384核16进程24线程
S1	742	408	223	131	83	74
S2	1 732	921	487	261	161	104
S3	22 821	11 763	6 069	3 135	1 640	871

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

A scalable CPU-MIC coordinated drug-finding tool by frequent subgraph mining

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 18

参考文献 24

相关文章 2

Metrics

推荐阅读 0

[1]	赵文明, 张思思, 唐碧霞, 陈婷婷, 郝丽丽, 桑健, 李茹姣, 肖景发, 章张. 面向国际的生命组学大数据管理体系建设[J]. 大数据, 2016, 2(6): 43-52.
[2]	詹晓娟,姚登举,朱怀球. 高通量DNA测序数据的生物信息学方法[J]. 大数据, 2016, 2(2): 76-87.

数据集			运行时间/s
数据集	1核	2CPU	2CPU＆1MIC	2CPU＆2MIC	2CPU＆3MIC
S1	7 590	382	274	234	208
S2	18 944	875	607	486	410
S3	266 794	11 625	7 749	6 457	5 320

最小支持度		运行时间/s
最小支持度	1节点	2节点	4节点	8节点
2%	5 320	2 816	1 736	993
1%	18 329	9 802	5 508	2 918
0.8%	43 252	23 026	12 847	6 295