中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 并行计算实验室  > 学位论文
学科主题: 计算机科学技术基础学科
题名:
并行最优路径算法及并行层次通信模型LogGP(h)研究
作者: 唐雨新
答辩日期: 2009-06-04
导师: 张云泉
授予单位: 中国科学院研究生院
授予地点: 中国科学院软件研究所
学位: 硕士
关键词: 最优路径、并行算法、通信模型、并行计算模型、通信层次性、LogP、LogGP,LogGP(h)
摘要: 随着以数据为中心的超级计算时代的到来,在各种以图为数据结构的应用中数据规模日益增大,数据量的急剧增加使得串行最优路径算法成为应用的性能瓶颈,已不能满足大规模最优路径求解的实时性要求。然而,最优路径求解算法的并行化却对图的类型有高度的敏感性,尤其是对一些稀疏图,如交通网络图,目前并没有很好的算法提供足够的并行性[1]。对此,本文提出、实现和优化了一种新的基于网络划分和迭代更新的并行最优路径算法,并用真实的交通网络数据在IBM JS21集群和曙光5000A两种平台上对算法进行了评测。测试结果表明,该算法具有较好的性能,在IBM JS21集群上,使用16个进程会出现约15倍的加速比;而在曙光5000A上,算法使用同一节点内的16个核获得了约20倍的超线性加速比。 本文的另一部分研究工作集中在新的并行计算模型方面。研究者所提出的并行计算模型有很多,从基于共享存储器结构的第一代并行计算模型,到针对于分布式存储结构的第二代并行模型,再到考虑存储层次性的第三代并行计算模型,却较少有模型考虑到通信的层次性。 大规模集群系统往往由几百到几千、甚至上万个节点构成,网络拓扑结构复杂。在这样的大规模集群系统中,点对点通信的性能并不总是一致的。这种非一致的通信性能随着网络拓扑的复杂化呈现层次性的变化,本文首先提出了层次化非一致性带宽和延迟(Hierarchical Communication Latency and Bandwidth:HCLB)的概念,并以进程映射对MPI Allgather的四种算法性能影响说明了由多核结构引起的通信层次性;之后,本文将大规模集群系统中的HCLB现象模型化,提出LogGP(h)并行通信模型。LogGP(h)在LogGP模型基础上,通过参数h将网络拓扑结构抽象到模型中,很好的表达了通信层次性。本文在具有8个刀片的IBM JS21集群上对点对点通信和集合通信开销进行模型分析和实际测试,实验结果表明,LogGP(h)较未引入参数h的LogGP模型更精确。
语种: 中文
内容类型: 学位论文
URI标识: http://ir.iscas.ac.cn/handle/311060/180
Appears in Collections:并行计算实验室 _学位论文

Files in This Item:
File Name/ File Size Content Type Version Access License
【毕业论文_唐雨新】并行最优路径算法及并行层次通信模型LogGP(h)研究.pdf(1390KB)----限制开放 联系获取全文

Recommended Citation:
唐雨新. 并行最优路径算法及并行层次通信模型LogGP(h)研究[D]. 中国科学院软件研究所. 中国科学院研究生院. 2009-06-04.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[唐雨新]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[唐雨新]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 

Valid XHTML 1.0!
Copyright © 2007-2017  中国科学院软件研究所 - Feedback
Powered by CSpace