首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 171 毫秒
1.
Stojmenovic introduced three different honeycomb tori by adding wraparound edges on honeycomb meshes, namely honeycomb rectangular torus, honeycomb rhombic torus, and honeycomb hexagonal torus. These honeycomb tori have been recognized as an attractive alternative to existing torus interconnection networks in parallel and distributed applications. In this paper, we propose generalized honeycomb tori. The three different honeycomb tori proposed by Stojmenovic are proved to be special cases of our proposed generalized honeycomb tori. We also discuss the Hamiltonian property of some generalized honeycomb tori.  相似文献   

2.
The honeycomb mesh, based on hexagonal plane tessellation, is considered as a multiprocessor interconnection network. A honeycomb mesh network with n nodes has degree 3 and diameter ≈1.63√n-1, which is 25 percent smaller degree and 18.5 percent smaller diameter than the mesh-connected computer with approximately the same number of nodes. Vertex and edge symmetric honeycomb torus network is obtained by adding wraparound edges to the honeycomb mesh. The network cost, defined as the product of degree and diameter, is better for honeycomb networks than for the two other families based on square (mesh-connected computers and tori) and triangular (hexagonal meshes and tori) tessellations. A convenient addressing scheme for nodes is introduced which provides simple computation of shortest paths and the diameter. Simple and optimal (in the number of required communication steps) routing, broadcasting, and semigroup computation algorithms are developed. The average distance in honeycomb torus with n nodes is proved to be approximately 0.54√n. In addition to honeycomb meshes bounded by a regular hexagon, we consider also honeycomb networks with rhombus and rectangle as the bounding polygons  相似文献   

3.
《国际计算机数学杂志》2012,89(15):3344-3358
The honeycomb torus HT(m) is an attractive architecture for distributed processing applications. For analysing its performance, a symmetric generalized honeycomb torus, GHT(m, n, n/2), with m≥2 and even n≥4, where m+n/2 is even, which is a 3-regular, Hamiltonian bipartite graph, is operated as a platform for combinatorial studies. More specifically, GHT(m, n, n/2) includes GHT(m, 6m, 3m), the isomorphism of the honeycomb torus HT(m). It has been proven that any GHT(m, n, n/2)?e is Hamiltonian for any edge eE(GHT(m, n, n/2)). Moreover, any GHT(m, n, n/2)?F is Hamiltonian for any F={u, v} with uB and vW, where B and W are the bipartition of V(GHT(m, n, n/2)) if and only if n≥6 or m=2, n≥4.  相似文献   

4.
在大规模并行系统中,系统级互连网络的设计至关重要.InfiniBand作为一种高性能交换式网络被广泛应用于大规模并行处理系统中.mesh/torus拓扑结构相较于目前普遍应用于InfiniBand网络的胖树拓扑结构拥有更好的性能与可扩展性.尽管如此,研究发现,用传统的mesh/torus拓扑结构构建InfiniBand互连网络存在诸多问题.分析了传统网络拓扑结构的缺陷,并提出了一种基于InfiniBand的多链路mesh/torus互连网络.这种改进型的拓扑结构通过充分利用交换机间的多链路可以获得比传统mesh/torus网络更高的带宽.另外,同时给出了与该网络拓扑结构相配套的高效路由算法.最后,通过网络仿真技术对提出的算法进行了评估,实验结果显示提出的路由算法相较于其他路由算法拥有更好的性能与可扩展性.  相似文献   

5.
The interconnection network considered in this paper is the k-ary n-cube that is an attractive variance of the well-known hypercube. Many interconnection networks can be viewed as the subclasses of the k-ary n-cubes include the cycle, the torus and the hypercube. A bipartite graph is Hamiltonian laceable if there exists a Hamiltonian path joining every two vertices which are in distinct partite sets. A bipartite graph G is strongly Hamiltonian laceable if it is Hamiltonian laceable and there exists a path of length N − 2 joining each pair of vertices in the same partite set, where N = |V(G)|. We prove that the k-ary n-cube is strongly Hamiltonian laceable for k is even and n  2.  相似文献   

6.
The Pyramid network is a desirable network topology used as both software data-structure and hardware architecture. In this paper, we propose a general definition for a class of pyramid networks that are based on grid connections between the nodes in each level. Contrary to the conventional pyramid network in which the nodes in each level form a mesh, the connections between these nodes may also be according to other grid-based topologies such as the torus, hypermesh or WK-recursive. Such pyramid networks form a wide class of interconnection networks that possess rich topological properties. We study a number of important properties of these topologies for general-purpose parallel processing applications. In particular, we prove that such pyramids are Hamiltonian-connected, i.e. for any arbitrary pair of nodes in the network there exists at least one Hamiltonian path between the two given nodes, and pancyclic, i.e. any cycle of length 3, 4 … and N, can be embedded in a given N-node pyramid network. It is also proven that two link-disjoint Hamiltonian cycles exist in the torus-pyramid and hypermesh-pyramid networks.  相似文献   

7.
新型互连网络NIN研究   总被引:4,自引:0,他引:4  
以通信延迟和网络吞吐率这两个重要参数为出发点,以大规模并行处理系统的新型互连网络(NIN)进行了理论分析和模拟测试,并与二维网格、环形网以及反图拓扑互连网络进行了比较,结果表明:与其它三种网络相比,NIN不仅保持了反图拓扑互连网络可以连接更多处理机的优点,同时还具有较短的通信延迟和较高的网络吞吐率。  相似文献   

8.
六角形蜂窝网格是一种具有良好网络拓扑性质的并行多处理机互连网络.蜂窝网格在某些特性上优于二维网格.不过,这种网络不存在单信道最短路径无死锁路由算法.文中针对该网络设计了两个部分自适应无死锁虫孔路由算法.一个是基于转弯模型单信道非最短路径路由算法,另一个则是采用了虚拟双信道的最短路径路由算法.对第二个算法,还进一步使用转弯模型对其改进.通过仿真实验,结果显示这两个路由算法都具有较好的性能.  相似文献   

9.
研究了太比特路由器核心交换网络拓扑的一种新结构-E-2Dtorus网络.该网络具有简单,对称,可扩展等优势.提出了适用于该网络结构的两种路由算法NPN(NoPositivetoNegative)和IDO(ImprovedDimensionOrder).部分自适应的NPN和确定性的IDO都是无死锁,无活锁且最短的路由算法.同时给出了无死锁无活锁的证明.最后,在8×8的E-2Dtorus网络上对路由算法进行仿真,结果表明E-2Dtorus是一种有潜力的网络拓扑结构,两种路由算法具有良好的性能.  相似文献   

10.
The torus network is one of the most popular interconnection networks for massively parallel computing systems. The strong matching preclusion number of a graph is the minimum number of vertices and edges whose deletion results in a graph that has neither perfect matchings nor almost perfect matchings. In this paper, we establish the strong matching preclusion number and classify all optimal solutions for the two-dimensional torus network with an odd number of vertices.  相似文献   

11.
Geyong  Mohamed   《Performance Evaluation》2005,60(1-4):255-273
The efficiency of a large-scale multicomputer is critically dependent on the performance of its interconnection network. Current multicomputers have widely employed the torus as their underlying network topology for efficient interprocessor communication. In order to ensure a successful exploitation of the computational power offered by multicomputers it is essential to obtain a clear understanding of the performance capabilities of their interconnection networks under various system configurations. Analytical modelling plays an important role in achieving this goal. This study proposes a concise performance model for computing communication delay in the torus network with circuit switching in the presence of multiple time-scale correlated traffic which is found in many real-world parallel computation environments and has strong impact on network performance. The tractability and reasonable accuracy of the analytical model demonstrated by extensive simulation experiments make it a practical and cost-effective evaluation tool to investigate network performance with various alternative design solutions and under different operating conditions.  相似文献   

12.
随着单个芯片上集成的处理器的个数越来越多,传统的电互连网络已经无法满足对互连网络性能的需求,需要一种新的互连方式,因此光互连网络技术应运而生.目前,电互连的片上网络在功耗、性能、带宽、延迟等方面遇到了瓶颈,而光互连作为一种新的互连方式引用到片上网络具有低损耗、高吞吐率、低延迟等无可比拟的优势.本文主要探讨了片上光网络的...  相似文献   

13.
An enhanced pyramid network is an alternate hierarchical structure for a pyramid network. This structure is created in a pyramid network by replacing each mesh with a torus at layers greater than one. This work studies the fault-tolerant Hamiltonian problem on the enhanced pyramid network and demonstrates that an enhanced pyramid network with two faulty nodes is Hamiltonian. The result is optimal, because edge connectivity and node connectivity of the enhanced pyramid network are both 4.  相似文献   

14.
MPP互连网络在T比特路由器设计中的应用   总被引:1,自引:1,他引:1       下载免费PDF全文
互连网络是MPP系统的重要组成部分,目前关于互连网络的研究已经取得了许多成果,并且在应用上积累了丰富的经验。因特网的迅速发展使对T比特交换技术的研究成为热点。本文着重分析将目前成熟的、具有较好扩展能力的MPP互连技术用于T比特路由器设计的可行性以及仍需解决的问题,并介绍三雏Torus网络在AVICI TSR路由器设计中的应用。  相似文献   

15.
The selection of a topology is essential to the performance of interconnection networks, so designing a new, cost-effective topology is very significant. 2D mesh is one of the most popular topologies. However, the diameter and average distance of a 2D mesh are large enough to greatly influence the performance of the network. This paper presents a novel topology called TM, which combines the advantages of both a 2D torus and a 2D mesh. For an n×n network, the total number of links in a TM is the same as that in a mesh, while the diameter of a TM is extremely close to that of a torus. Besides, the average distance of a TM is at the middle of that of a torus and that of a mesh. To prevent deadlocks in TMs, a virtual network partitioning scheme is adopted into the TM network. Moreover, both of the deterministic and fully-adaptive routing techniques in TMs are proposed in this paper. Compared to mesh, the TM network provides average distance and diameter reduction, which contributes to the performance enhancement. Sufficient simulation results are presented to show the effectiveness of the TM network, and the new routing schemes proposed for it, by comparing with the mesh network. Compared to the torus, which requires at least 3 virtual channels to support fully-adaptive routing, the TM network can support fully-adaptive routing with only 2 virtual channels. Seen from the experimental results, in most cases, the performance of TM is worse than the torus, while in some cases, the performance of TM is comparable to torus or even better than the torus.  相似文献   

16.
A routing policy is the method used to select a specific output channel for a message from among a number of acceptable output channels. An optimal routing policy is a policy that maximizes the probability of a message reaching its destination without delays. Optimal routing policies have been proposed for several regular networks, including the mesh and the hypercube. An open problem in interconnection network research has been the identification of an optimal routing policy for the torus. In this paper, we show that there is no optimal routing policy for the torus. Our result is demonstrated by presenting a detailed example in which the best choice of output channel is dependent on the probability of each channel being available. This result settles, in the negative, a conjecture by Wu concerning an optimal routing policy for the torus.  相似文献   

17.
The foundation of information society is computer interconnection network, and the key of information exchange is communication algorithm. Finding interconnection networks with simple routing algorithm and high fault-tolerant performance is the premise of realizing various communication algorithms and protocols. Nowadays, people can build complex interconnection networks by using very large scale integration (VLSI) technology. Locally exchanged twisted cubes, denoted by (s + t + 1)-dimensional LeTQs,t, which combines the merits of the exchanged hypercube and the locally twisted cube. It has been proved that the LeTQs,t has many excellent properties for interconnection networks, such as fewer edges, lower overhead and smaller diameter. Embeddability is an important indicator to measure the performance of interconnection networks. We mainly study the fault tolerant Hamiltonian properties of a faulty locally exchanged twisted cube, LeTQs,t − ( fv + fe), with faulty vertices fv and faulty edges fe. Firstly, we prove that an LeTQs,t can tolerate up to s−1 faulty vertices and edges when embedding a Hamiltonian cycle, for s≥2, t≥3, and s≤t. Furthermore, we also prove another result that there is a Hamiltonian path between any two distinct fault-free vertices in a faulty LeTQs,twith up to (s − 2) faulty vertices and edges. That is, we show that LeTQs,t is (s−1)-Hamiltonian and (s−2)- Hamiltonian-connected. The results are proved to be optimal in this paper with at most (s − 1)-fault-tolerant Hamiltonicity and (s − 2) fault-tolerant Hamiltonian connectivity of LeTQs,t.  相似文献   

18.
Torus连接Petersen图互连网络及路由算法   总被引:3,自引:0,他引:3  
可扩展性和短直径是设计大规模并行计算机系统互连网络的两个重要因素.基于Petersen图的短直径和正规性和Torus拓扑结构的可扩展性,提出了一种新的互连网络拓扑结构,称为Torus连接Petersen图互连网络.该互连网络拓扑结构具有短直径、正规性、对称性和良好的扩展性.网络节点采用混合编码方法,使得路由算法设计简单.分别设计了基于混合编码的单播、广播路由算法.分析表明提出的互连网络具有较好的拓扑性质.  相似文献   

19.
A new methodology named CALMANT (CC-cube Algorithms on Meshes and Tori) for mapping a type of algorithm that we call CC-cube algorithm onto multicomputers with hypercube, mesh, or torus interconnection topology is proposed. This methodology is suitable when the initial problem can be expressed as a set of processes that communicate through a hypercube topology (a CC-cube algorithm). There are many important algorithms that fit into the CC-cube type. CALMANT is based on three different techniques: (a) the standard embedding to assign the processes of the algorithm to the nodes of the mesh multicomputer; (b) the communication pipelining technique to increase the level of communication parallelism inherent in the CC-cube algorithms; and (c) optimal message-scheduling algorithms proposed in this work in order to avoid conflicts and minimizing in this way the communication time. Although CALMANT is proposed for multicomputers with different interconnection network topologies, the paper only focuses on the particular case of meshes.  相似文献   

20.
Generalized honeycomb torus (GHT) is recognized as an attractive alternative to existing torus interconnection networks in parallel computing systems. Assume that m and d are integers with m ? 2 and d ? 8. This paper addresses the fault-tolerant hamiltonicity of GHT(m, 2d, d) with fault set F = {(w, y), (x, y)}, where w < x, w + y is even and x + y is odd. We show that such a faulty GHT is hamiltonian by presenting a systematic method for constructing a fault-free hamiltonian cycle. This result reveals another appealing feature of GHTs.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号