连通分量问题的多机并行算法研究

来源 :湖北大学 | 被引量 : 0次 | 上传用户:13439718
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
连通分量问题作为图论中的经典问题,在许多领域的应用中起到了重要的作用。由于应用范围的扩大,信息的增加,其串行算法的性能也受到影响。随着VLSI技术的发展和并行计算机的出现,为人们快速求解图论问题提供了一条新的途径。本文首先介绍了当代并行计算机体系结构,分析了各种并行计算模型和并行算法编程模型的特点。接下来讨论了在MPI中,解决消息传递过程中的异构性问题,以及在多种不同通信模式下的操作方式。然后对求解连通分量问题的几种并行算法进行了性能分析,列表比较其时间复杂性和并行计算成本。选择了其中的一种算法——顶点倒塌算法做进一步研究,编写出基于MPI的C语言程序,在多机并行环境中对程序进行性能分析,分析数据显示该程序取得了较好的并行计算效果。
其他文献
数据库知识发现(KnowledgeDiscoveryinDatabase,KDD)是从大量数据中发现潜在规律、提取有用知识的方法和技术。近年来,KDD受到了国内外普遍关注,已经成为信息系统和计算机科学领
本课题是针对近年来山东省医疗卫生资源的现状与山东省经济发展状况,人民生活发展水平,以及山东省医疗卫生体制适应性而提出的。在改革开放之前,我国医疗卫生体系是与计划经济体
本文针对目前国内对回采巷道围岩稳定性预测的研究现状,采用数值分析、工程验证、数值模拟等多种研究方法,提出并建立了基于支持向量机(SVM)的回采巷道围岩稳定性预测模型,研究了
本文通过对荣华二采区10
随着能源与环境问题的日益凸显,分布式发电技术不断发展,但是由于分布式发电自身的局限性和传统电网的薄弱性,分布式发电大规模并网存在不少困难。将分布式发电供能系统以微网的形式运行,与大电网互为支撑,是发挥分布式发电供能系统能效的最有效方式。风力发电是重要的可再生能源形式,本文针对并入交流微电网的双馈风力发电系统的控制策略进行了研究。在微网并网和孤岛状态下风力发电系统采用最大风能追踪和矢量定向控制策略,
随着组件技术的发展,组件式GIS在地理信息系统的二次开发中获得了广泛的应用。但是组件式GIS缺乏专有的概念建模方法,这对使用GIS组件进行二次开发带来了不便之处。首先,系统设
与汽车物流、医药物流、烟草物流这样专业的特殊物流相比,易腐商品物流(Deteriorating Items Logistics,DIL)这个概念对多数人还比较陌生,但它却与人们的生活息息相关。基于此,论
本文是对广州美术学院视觉传达设计专业新开设的《主题考察》课程所作的教学档案,包含教学内容、方法、过程和作业及效果的完整记录和讨论。通过对本课程的尝试,令师生体验到
通信系统对电力系统安全经济运行起着不可或缺的支撑作用,随着电力市场需求不断提高和光纤通信技术的飞速发展,建设智能电网已成为必然趋势,“光进铜退”已成为电力通信技术的必然选择。EPON技术以其天然的技术和成本优势成为最广泛的光纤接入技术,而且它和配电网有着浑然相似的网络架构,非常适合应用于配电自动化系统。EPON网络的OLT置于变电子站,电力ONU置于配电终端,之间通过无源光网络进行连接。电力ONU
为了缩短开发时间,减少织物设计开销,并在企业和客户间建立起有效的沟通,使得设计人员可以在设计之初就对所设计产品的效果进行模拟,这种纺织CAD软件发展的现状需要专门开发