文档介绍：⑧几种互连网络上的通信问题的研究重庆大学硕士学位论文跹重庆大学计算机学院学生姓名:王磊指导教师:杨小帆教授业:计算机软件与理论学科门类:工学二欢晁脑专
篊’.,—
墨坠塑堂塑选一摘要±塞塑垩————————————————————————————一一并行计算机的基础互连网络为处理器岬之间进行数据通信提供了物理基础,其拓扑结构决定了结点间通信效率,是影响并行计算机性能的主要因素之一,因而成为并行计算领域的研究热点。当在互连网络上执行并行算法时,常常需要在结点之间进行数据通信,其通信开销是算法执行时间的重要组成部分。基于互连网络的特性来研究如何高效地完成数据通信,这是一项很有意义的研究课类超立方体是一类重要的互连网络拓扑结构,目前,关于变形超立方体通信算法方面的研究成果还很少,相应的通信问题没有得到很好的解决,因而难以开发关于变形立方体的并行算法,同时也使得变形立方体到目前为止还缺乏实用的价值。本学位论文研究变形立方体上的通信问题,取得的主要研究成果如下:首先,对一种重要的类超立方体⋯局部扭曲立方体,研究了其单点广播问题。单点广播是一个基本的通信问题,需要把一组消息从一个给定的结点发送到网络中其他所有的结点。针对这一问题,本文提出了一个能够在时间内完成植颗で⒎教迳系サ愎悴ト挝竦乃惴ǎ渲蠳”为结点数;证明了该算法在同类算法中通信时延最小。就我们所知,这还是国际上首次研究局部扭曲立方体上的单点广播问题。其次,对另一种重要的类超立方体⋯交叉立方体,研究了其独立生成树问题。容错通信和安全消息分发是互连网络领域的一项重要研究课题。普遍认为:设计多个独立生成树来作为广播方案或分发协议可以得到良好的容错性和安全性。本文提出了一个能够构造出徊媪⒎教逯忻趴枚懒⑸墒魉惴ǎ涫奔淇O,其中蔽=岬闶8盟惴ǹ梢圆⑿谢涫奔淇O滴狾该算法使独立生成树的数目达到了最大,从这个意义上讲,该算法是最优的。关键字:互连网络,局部扭曲立方体,广播算法,交叉立方体,独立生成树题。。州奠一
甒⋯甌,,琭甌瑆甦,,猟瓵,.,,,,甌..瓵,”甌瑃,..
眦瞻Ⅲ‰.善奴肺酊印甜枷阻。篒舒∞。,,妇廿,Ⅳ伧的吡坨Ⅱ盯已吐..
垩盎盔堂堡主堂位论文目录中文摘要⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯¨英文摘要⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.髀邸植颗で⒎教迳系サ愎悴ノ侍狻徊媪⒎教迳隙懒⑸墒魑侍狻并行计算⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯互连网络与图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯互连网络上与通信相关的问题⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯本文的研究工作⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯引言⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯预备知识⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯局部扭曲立方体上的单点广播算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯..算法的证明与分析⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.本章小结⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.引言⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.预备知识⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.在交叉立方体上构造独立生成树的算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯...≡⒎⒎⒎⒎⒎教迳隙懒⑸墒魉惴ǖ难芯砍晒
晒胝雇致谢⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯参考文献⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯附录⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯重庆人学硕士学位论文本章小结⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.主要研究成果⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯。研究不足与后续工作⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.髡吖ザ了妒垦黄诩浞⒈
——————————————————————————————————————±堂堡垒塞论并行计算并行计算机姆⒄箍J加兰甏笥遥钡世纪年代进入百家争鸣蓬勃发展的阶段,在世纪年代体系结构和框架都趋于统一,近十年来机群技术获得了快速的发展,并行计算机的技术日趋成熟‘。随着社会的进步和科技的发展,人们对高性能计算的需求愈发强烈和