【作者】 徐志广；

【导师】 顾乃杰；

【作者基本信息】 中国科学技术大学 ， 计算机系统结构， 2009， 硕士

【摘要】 近年来,随着高性能并行计算的迅速发展,多级互连网作为现代并行计算机和交换系统的核心连接网络,需要更好的支持在并行分布计算机系统里多个要求协作的处理器之间的通信——会议组通信。在多级互连网上无阻塞并发实现会议组通信受到越来越广泛的关注,成为重要的研究课题。本文主要研究多级互连网络上各种模式下的通信特点,并基于典型的互连网络结构构造具有良好通信能力和最优硬件代价的无阻塞会议网络。具体研究内容如下:论文首先研究了全连接交叉开关和Clos网络等两种结构上无阻塞支持会议通信的实现,给出了Clos网络上会议通信的实现策略和无阻塞条件,得到小规模情况下低延迟无阻塞实现的会议网络结构。接着为了得到更小硬件代价的会议网络结构,结合Omega复制网受限多播可以无阻塞并发的性质,讨论了Omega -1汇集网的结构及其上的自适应路由规约通信策略,进而得到Omega -1汇集网受限多对一规约连接无阻塞并发的结论。通过串接Omega -1汇集网和Omega复制网提出新的2-Omega结构的会议功能网络结构(GBCCN),并证明了其上受限多会议可以无阻塞的并发实现。进而按照会议网络三明治策略“置换网+会议功能网络+置换网”构造出新的会议网络。新的会议网络中位于两端的置换网采用Omega+Omega重排结构,位于中间的会议功能网络采用本文提出的2-Omega结构的GBCCN,从而得到一个6-Omega的会议网络。该网络可以实现会议成员任意分布的多会议无阻塞并发通信,硬件复杂度为3NlogN,传输延迟为6logN ,路由时间为O(NlogN) ,均达到已有无阻塞网络的最优量级。新构造的6-Omega会议网络具有更好的整体对称性,可以折叠为3-Oemga的会议网络,进一步降低硬件代价。论文提出的6-Omega会议网络的构造无论在方法上还是在结果上与现有研究成果相比,都具有一定的优势和创新。由于在设计与实现上具有很好的通用性,因此对于进一步研究多级互连网上实现各种通信尤其是会议组通信具有积极的意义。更多还原

【Abstract】 MINS(Multistage interconnection networks), as important elements in parallel computing computer and switching system, need to effectively sopport conference communication within a cluster of processors collaborating. For decades, realizing concurrent multipe conferences nonblockingly on the MINS becomes an important issue. This dissertation focuses on how to create a new conference network with better performance and lowest costing which can realize concurrent conferences nonblockingly. The specific studies are as follows:Firstly, this dissertation analyses the strategy and nonblocking conditions of conference communication on Clos network. On Clos network we can easily design nonblocking conference network with relatively lower latency.Secondly, for getting a lower hardware cost, this dissertation extends the basis on Omega replicating network to Omega -1 merging network. It comes to the conclusion that Omega -1 is nonblocking merging network for constrained concurrent many-to-one connections. Then, by concatenating Omega -1 merging network and Omega replicating network, we propose a novel 2-Omega structure named GBCCN (Gathering&Broadcasting conference component network), and prove that multiple constrained conferences can be nonblockingly realised on GBCCN.Finally, according to the sandwich strategy of conference network, by using rearrangeable Omega + Omega as replacing network and GBCCN as the conference component network, a 6-Omega conference network is designed, which is based upon analysing how the struture of 5-Omega realises arbitrary multicast. It can realize concurrent multiple disjoint conferences distributed arbitrarily. Then, it has 3NlogN hardware cast、6logN communication delay, O(NlogN) routing time. Moreover, the 6-Omega structure has better integrated symmetry to be folded into 3-Oemga, which further reduces the cost of hardware.The new conference network is superior to existing designs, has advantages and innovations in the ways and structures. It contributes to further studying on MINS.更多还原