共查询到20条相似文献,搜索用时 0 毫秒
1.
《Journal of Parallel and Distributed Computing》1995,28(1):19-31
The issues of adaptive multicast wormhole routing in 2D mesh multicomputers are studied. Three adaptive multicast wormhole routing strategies are proposed and evaluated. The methods include minimal partially adaptive, minimal fully adaptive, and nonminimal adaptive routing. All the algorithms are shown to be deadlock-free. A study has been conducted that compares the performance of these multicast algorithms. The results show that the minimal fully adaptive routing method creates the least traffic; however, double vertical channels are required in order to avoid deadlock. The nonminimal routing algorithm exhibits the best adaptivity, although it creates more network traffic than the other methods. 相似文献
2.
《Journal of Parallel and Distributed Computing》1994,23(1):80-93
Fault-tolerant message routing mechanism is a key to the performance of reliable multicomputers. Multicast refers to the delivery of the same message from a source node to an arbitrary number of destination nodes. This paper presents two types of partially adaptive fault tolerant multicast algorithms. The Type A algorithm can deliver messages to all destinations through shortest paths if each fault-free node has at most one faulty neighbor. The Type B algorithm can deliver messages to all destinations if the total number of faulty links and faulty nodes is less than the dimension of the hypercube. The proposed algorithms have the following important features: they are distributed, they only require local information to determine the paths, and they need very little additional message overhead. The performance of the algorithms, measured by the traffic created by the communication, is very close to that in fault-free hypercubes. 相似文献
3.
用最优通路矩阵实现超立方体多处理机系统的容错路由 总被引:13,自引:1,他引:13
针对拓扑结构为超立方体的多处理机系统提出了最优通路矩阵(OPM)的概念,并约出了一个基于最优通路矩阵的路由算法。存储于超产方体各节点中的最优通路矩阵记录系统中的故障信息,用于判定消息的源节点和目的节点之间是否存在最优通路(长度等于两节点间Hamming距离的通路)。对于n维超方立体,每个节点所需的存储开销为n^2个字,基于最优通路矩阵的路由算法所选的通路的长度不超过两点间的Hamming距离加2。 相似文献
4.
5.
《Journal of Parallel and Distributed Computing》1995,27(1):56-70
A deadlock-free fully adaptive minimal routing algorithm for meshes that is optimal in the number of virtual channels required and in the number of restrictions placed on the use of these virtual channels is presented. It is also proved that, ignoring symmetry, this routing algorithm is the only fully adaptive routing algorithm with uniform routers that achieves both of these goals. This new algorithm requires only 4n-2 virtual channels for an n-dimensional mesh. In addition, if more than the minimum number of virtual channels is available, the routing algorithm can use these additional channels with the fewest possible number of restrictions. The proofs are first presented for the 2D mesh and then generalized to n-dimensional meshes. 相似文献
6.
林柏钢 《小型微型计算机系统》2005,26(9):1556-1559
根据n-cube超立方体互连网络的并行特点,分析了任意当前结点相邻集合类的求解方法,并给出一种自适应优化盲寻径搜索算法,即通过任一当前结点的Hamming距离相邻测度,寻找从任一始发结点到目标结点的所有可能的自适应盲寻径优化算法. 相似文献
7.
8.
9.
《Journal of Parallel and Distributed Computing》1999,58(1):26-43
This paper presents a new dynamic load-balancing algorithm for hypercube multicomputers with faulty nodes. The emphasis in our method is on obtaining global load information and performing task migration using “short paths” in a synchronous manner so that a minimal amount of communication overhead is required. To accomplish this, we present an algorithm for constructing a new logical topology from a hypercube topology with faulty nodes. This new topology is used to obtain the global load information and to perform task migration. Simulation results are used to evaluate the performance of our dynamic load balancing method when compared with previous methods 相似文献
10.
Mesh网络耐故障虫孔路由 总被引:1,自引:1,他引:0
耐故障是互连网络设计中的一个重要问题。本文提出了一种新的耐故障路由算法,并将其应用于使用虫孔交换技术的Mesh网络。由于使用了较低的路由限制,这一算法具有很强的自适应性,可以在各种不同故障域的Mesh网络中保持路由的连通性和无死锁性;由于使用了最小限度的虚拟通道,这一算法所需的缓冲器资源很少,非常适宜构建低成本的耐故障互连网络;由于根据本地故障信息进行绕行故障节点的决策,这一算法的路由决策速度较快并且易于在互连网络中实现。最后网络仿真试验显示,这一算法具有良好的平滑降级使用的性能。 相似文献
11.
《Journal of Parallel and Distributed Computing》1994,20(3):317-329
In this paper a hierarchical task scheduling strategy for assigning parallel computations with dynamic structures to large hypercube multicomputers is proposed. Such computations represent a wide range of recursive and divide/conquer algorithms for which structure of the problem varies dynamically. To achieve load balancing and reduce processor contentions, the system is divided into multiple regions of processors for which the first level of scheduling is done by the host computer that spreads out the initial computations into these regions. The second level scheduling is done by a set of median processors of these regions which enable the processors of their regions to optimally balance the dynamically created load and to communicate with each other with reduced overhead. The results of an extensive simulation study are presented that exhibit the performance of the proposed strategy under different loading conditions, varying degrees of depth and parallelism, and communication costs. The proposed dual-level hierarchical scheduling is shown to outperform a well known distributed scheduling strategy. 相似文献
12.
13.
虫孔网络中的自适应路由算法 总被引:2,自引:0,他引:2
互连网络是大规模并行计算机的重要组成部分,路由算法是其中决定网络性能的重要因素,自适应路由算法视网络工作状态可以在源到目的结点之间存在的多条路径中选择合适的一条传送消息,因此选径的灵活性和通道利用率高,提高了网络效率,增强了网络容错能力。文中在直接网络结构基础上对采用虫孔路由的自适应算法进行讨论,给出了一个总结综述。 相似文献
14.
Mike Barnett David G. Payne Robert A. van de Geijn Jerrell Watts 《Journal of Parallel and Distributed Computing》1996,35(2):111
We address the problem of broadcasting on two-dimensional mesh architectures with an arbitrary (non-power-of-two) number of nodes in each dimension. It is assumed that such mesh architectures employ cut-through or wormhole routing. The primary focus is on avoiding network conflicts in the various proposed algorithms. We give algorithms for performing a conflict-free minimum-spanning tree broadcast, a pipelined algorithm that is similar to Ho and Johnsson's EDST algorithm for hypercubes, and a novelscatter–collectapproach that is a natural choice for communication libraries due to its simplicity. Results obtained on the Intel Paragon system are included. 相似文献
15.
Sarbazi-Azad Hamid Ould-Khaoua Mohamed Mackenzie Lewis M. 《The Journal of supercomputing》2002,22(2):139-159
Several analytical models of fully adaptive routing in wormhole-routed k-ary n-cubes under the uniform traffic pattern have recently been proposed in the literature. Although the uniform reference model has been widely used by researchers, it is not always true in practice as there are many applications that exhibit traffic nonuniformity. There has hardly been any study that describes an analytical model of fully adaptive routing under nonuniform traffic conditions. This paper describes the first analytical model of fully adaptive routing in k-ary n-cubes in the presence of nonuniform traffic generated by the digit-reversal permutation, which is an important communication operation found in many matrix computation problems. Results obtained through simulation experiments confirm that the model predicts message latency with a good degree of accuracy under different working conditions. 相似文献
16.
17.
网络中的蛀孔寻径技术 总被引:1,自引:0,他引:1
文章从网络通信的角度研究了大规模并行计算机系统(Massivelyparallelprocessingsystem)中实时网络的通信问题,介绍了蛀孔寻径技术的原理和相应的算法。 相似文献
18.
19.
20.
《Journal of Parallel and Distributed Computing》1993,19(2):125-130
Rearrangeable hypercube architectures and routing algorithms are developed to realize arbitrary permutations in circuit switching. We prove that if each connection between two neighboring nodes consists of two pairs of links (two full-duplex communication lines), the hypercube can handle two arbitrary permutations simultaneously. We also prove that a hypercube is rearrangeable if one additional pair of links is provided in any one dimension of connections. 相似文献