基于并行计算的通风网络角联结构识别分析.pdf

第34卷第9期煤 炭 学 报Vol . 34 No. 9 2009年9月JOURNAL OF CH I NA COAL SOCIETYSep. 2009 文章编号 0253 - 9993 2009 09 - 1208 - 04 基于并行计算的通风网络角联结构识别分析 赵 丹 1 ,刘 剑 1 ,潘竞涛 2 ,马 恒 1 1 1辽宁工程技术大学 安全科学与工程学院,辽宁 阜新 123000; 21煤炭科学研究总院 沈阳研究院,辽宁 沈阳 110016 摘 要提出了基于并行思想的角联结构自动识别的数学模型及算法,利用PC组成局域网并行 集群系统,采用Linux操作系统和消息传递接口MPI作为并行编程环境,对矿井通风网络的角联 结构的识别问题进行了分析.实验数据表明,随着节点数的增加,执行时间得到了大幅度降低. 关键词矿井通风系统;角联结构;并行集群系统 中图分类号TD725 文献标识码 A 收稿日期 2008-11-20 责任编辑毕永华 基金项目国家自然科学基金资助项目60772159 作者简介赵 丹1982 , 女,辽宁阜新人,博士研究生.E - mailzhaosixiaojie_201631com Analysis of identifying diagonal structure of ventilation network based on parallel computing ZHAO Dan 1 , L I U Jian 1 ,PAN Jing2tao 2 , MA Heng 1 11College of Safety Science and Engineering, Liaoning TechnicalUniversity,Fuxin 123000,China;21Shenyang B ranch, China Coal Research Insti2 tute, Shenyang 110016,China Abstract Set up by PC LAN consisting ofparallel computer clusters system, used Linux operating system andMPI Message Passing Interface as a parallel computing environment, analyzed to the diagonal structuralofmine venti2 lation network successfully . Experimental data show that the cution ti me is reduced significantlywith the number of nodes increasing . Key words mine ventilation systems; diagonal structure; parallel cluster system 在通风网络角联结构的算法研究中,尽管笔者已经提出了用通路法确定有向图的角联结构和路径法确 定无向图的角联结构及其数学模型 [1 ] ,但由于其庞大的计算量,还无法算出井下大型网络的全部角联结 构.对于采用超级计算机则是相当的昂贵,因此本文将并行计算应用于通风网络角联识别中具有十分重大 的意义. 系统中各进程通过互联网络实现通信、共享内存和传递消息,从而实现分布式并行计算,为求解大规 模计算问题提供足够的内存和运算能力,大大提高了运行速度,节省了运算时间.目前它已应用于各个学 科领域,但矿井通风网络的并行处理和并行计算技术还是一个较新的领域.本文应用并行计算寻找矿井通 风网络角联结构,进一步降低程序的时间复杂度和空间复杂度. 1 角联结构的数学模型 角联结构七元组 [2 - 3 ]表示为 θ PL, PR, PD, z, z,;,; , 其中, PL, PR, PD分别为左右通路和角联通 路;z, z分别为分流节点和汇流节点;;,;分别为左右关联点. 第9期赵 丹等基于并行计算的通风网络角联结构识别分析 PL P x i, PR P x j, PD E V P[k ] [y ] a≤y≤b -1, V P[k ] [a ]∈V x ik, V P[ k ] [ b]∈V x jk, V x ik V x jk 1, E V P[k ] [y ] 1时,形成的θ结构情形是很复杂的,如图1所示,可能形成多个 θ结 构,这时要按照一定的次序逐段确定PD以及对应的θ结构. 对于有向通风网络图G V, E , m V, n E, vi到vj的 全部通路数为s ∑ m -1 k 1 a k ij a 1 ij a 2 ij⋯ a m -1 ij ,其中,a k ij是A k 中的第i行 第j列的元素,而A k AA k- 1 ,是有向图节点邻接矩阵A相乘k次. 2 并行通路法数学模型及算法 通路集合中的任意2个通路P[ i], P[ j]构成的子图Gij V P[ i] V P[ j] , P[ i] P[ j]与第3 条通路P[k ], k≠i, k≠j构成角联结构的并行算法如图2所示,当模块[19 ]中的V x ik 1,V x jk 1时,模块[20 ]要按一定次序逐段计算,否则将不能正确地确定所有的角联结构. 3 并行计算平台的搭建和实验测试 311 硬件环境 系统由通用PC机组成.采用星形拓扑结构,构造100 Mbps高速交换式以太网.每台机器上都安装 Linux操作系统,对操作系统进行网络配置.机群中有一个主节点,其余为从节点 [4 ]. 将节点微机上计划 安装MPI开发环境和存储并行程序的硬盘分区或文件夹设置为网络共享. 312 操作系统与并行编程环境 由于Linux操作系统其内核源代码的公开性以及机器之间容易互访,因此Linux操作系统要比W in2 dows系统更适合于网络并行计算.故本文在并行计算平台的搭建上选用了Linux操作系统,发行版是 RedHat - 9 [5 ]. 目前通用的消息传递环境主要有Express, Linda,PARMACS,P4,PVM,Zipcode与MPI等几种.使 用最为广泛的是PVM和MPI [6 ]. 笔者采用MPI作为并行程序设计平台.它具有移植性好、功能强大、效 率高等多种优点,而且有多种不同的免费、高效和实用的实现版本,几乎所有的并行计算机厂商都提供对 它的支持,这是其它并行环境所无法比拟的,它成为消息传递并行环境的标准. 313 实验测试 本实验先用4台PC分析小规模通风网络的铁法大明煤矿的角联结构. 9021 煤 炭 学 报 2009年第34卷 图2 并行通路法程序 Fig12 The type of diagonal structure 表1 实验结果 Table 1 The experi mental results 进程个数运行时间/s加速比并行效率 1317311 411941192301641 1601675156701348 从表1实验结果也可以看出,采用MPI并行处理的效 果较为满意,执行时间得到了大幅的降低.随着节点的逐渐 增加,节点间的数据交换和同步等待消耗时间逐渐增多,并 行的效率也随着CPU数量的增加而逐渐降低.由于每个节 点的软硬件配置都完全相同,简化了并行计算任务分配的难 度,否则需要评估每个节点的计算能力,恰当的分配计算任 务.实验目的是计算超大型通风网络,现以吕家陀煤矿通风网络为例 [7 ] ,测试在实验室的集群并行环境 中计算.一共分配20个节点,每台节点分配1个进程, 1个进程计算1个子域,共用时间9814 h.由于系 统庞大, 1台机器计算需要的时间无法估量,在此对加速比和并行效率不做计算. 4 结 论 1根据角联结构七元组特点,分析与设计了算法. 2利用Linux系统,基于现有的PC和局域网资源,在MPI并行环境下,成功搭建了并行集群系统. 3建立了并行通路法数学模型,先在小规模通风网络下,对不同进程个数的运行时间、加速比和 并行效率进行了对比,并解决了超大规模通风网络的角联结构识别问题. 参考文献 [1] 刘 剑,贾进章,郑 丹.流体网络理论[M ].北京煤炭工业出版社, 2002 138 - 140. 0121 第9期赵 丹等基于并行计算的通风网络角联结构识别分析 Liu Jian, Jia Jinzhang, Zheng Dan.Fluid network theory [M ].Beijing China Coal Industry Publishing House, 2002 138 - 140. [2] 苏清政,刘 剑.矿井通风仿真理论与实践[M ].北京煤炭工业出版社, 2006 127 - 135. Su Qingzheng, Liu Jian. Analysisof industry safetymanagementmodel [M ]. Beijing China Coal Industry PublishingHouse, 2006 127 - 135. [3] 刘 剑,李舒伶,徐瑞龙.角联风路的自动识别[J ].中国安全科学学报, 1996, 6 12 139 - 142. Liu Jian, Li Shuling, Xu Ruilong . Automatic distinction of angle connection air way [J ]. Beijing China Safety Science Jour2 nal, 1996, 6 12 139 - 142. [4] 张 帆.基于消息传递的并行计算环境设计与实现[D ].成都四川大学, 2006 39 - 41. Zhang Fan. Design and i mplementation of parallel computing environment based on message passing [D ]. Chengdu Sichuan University, 2006 39 - 41. [5] 张林波,迟学斌,莫则尧,等.并行计算导论[M ].北京清华大学出版社, 2006 60 - 64. ZhangLinbo, ChiXuebin, Mo Zeyao, et al . Parallel computing introduction [M ]. Beijing TsinghuaUniversity Press, 2006 60 - 64. [6] RajkumarBuyya.高性能集群计算编程与应用[M ].郑纬民,等译.北京电子工业出版社, 2001 34 - 48. RajkumarBuyya. High2perfor mance cluster computing programming and application [M ].ZhengWeimin, et al trans . Bei2 jing Electronics Industry Publishing House, 2001 34 - 48. [7] 赵 丹.并行计算在角联识别中的应用研究[D ].阜新辽宁工程技术大学, 2008 3 - 6. Zhao Dan. The application research of parallel computing in diagonal identification [D ]. Fuxin Liaoning TechnicalUniversi2 ty, 2008 3 - 6. 2010年 煤炭学报 征订启事 煤炭学报 是中国煤炭学会主办的、向国内外发行的煤炭科学技术方面的综合性学术刊物.主要刊 载煤田地质与勘探、煤矿开采、矿山测量、矿井建设、煤矿安全、煤矿机械工程、煤矿电气工程、煤炭加 工利用、煤矿环境保护等方面的科学研究成果论著和学术论文,以及煤矿生产建设、企业管理经验的理论 总结,也刊载重要学术问题的讨论及国内外煤炭科学技术方面的学术活动简讯. 煤炭学报 刊载的论文具有较高的学术价值和文献收藏价值,被Ei、IEA CoalAbstractCD2ROM、中 国科学引文数据库、科学技术文摘速报日本、Coal Highlights、中国学术期刊文摘等国内外20多种重 要文摘检索系统所收录.1992年荣获首届全国优秀科技期刊评比二等奖,获中国科学技术协会优秀学术 期刊二等奖,获北京市新闻出版局、北京市科学技术期刊编辑学会全优期刊奖.1996年荣获第二届全国 优秀科技期刊评比一等奖,获中国科学技术协会优秀科技期刊一等奖.1999年荣获首届国家期刊奖. 2004, 2007年分别入选第三、第六届百种中国杰出学术期刊.2008年荣获 “ 中国精品科技期刊 ”称号. 煤炭学报 深受广大作者、读者的爱护和支持,也受到各级部门的重视,在学术水平上具有较高的 地位,很多单位都将在 煤炭学报 发表的论文作为作者学术水平考核指标之一. 煤炭学报 为月刊,每期176页,每册订价31元,全年共收费372元.欲订阅者可直接与本编辑部 联系,编辑部随时办理订阅手续. 本刊地址北京市和平里煤炭科学研究总院内 煤炭学报 编辑部 邮政编码 100013 联系电话010 84262930 联系人毕永华 E - mail mtxbbyh1261com, mtxbvip11631com 1121