Narrow Results

We show that the edges of the modified Knödel graph can be grouped into dimensions which are similar to the dimensions of hypercubes. In particular, routing, broadcasting and gossiping, can be done easily in modified Knödel graphs using these dimensions.

Fast and efficient communication is one of the most important requirements in today's multicomputers. When reaching a larger scale of processors, the probability of faults in the network increases, hence communication must be robust and fault tolerant. The recently introduced family of folded Petersen networks, constructed by iteratively applying the cartesian product operation on the well-known Petersen graph, provides a regular, node– and edge-symmetric architecture with optimal connectivity (hence maximal fault-tolerance), and logarithmic diameter. Compared to the closest sized hypercube, the folded petersen network has a smaller diameter, lower node degree and higher packing density.

In this paper, we study fundamental communication primitives like single routing, permutation routing, one-to-all broadcasting, multinode-broadcasting (gossiping), personalized communications like scattering, and total exchange on the folded Petersen networks, considering two communication models, namely single link availability (SLA) and multiple link availability (MLA). We derive lower bounds for these problems and design optimal algorithms in terms of both time and the number of message transmissions. The results are based on the construction of minimal height spanning trees in the fault-free folded Petersen network. We further analyze these communication primitives in faulty networks, where processing nodes and transmission links cease working. This analysis is based on multiple arc-disjoint spanning trees, a construct also useful for analyzing other families of multicomputer networks.

A heuristic has shown that the results achieved by earlier algorithms for gossiping on cube-connected-cycles (CCCs) in the unit-cost telephone model were not optimal, but no general pattern was revealed. In this paper new gossiping algorithms are presented that apply to CCCs of all sizes. Most importantly, we show that for gossiping on the "k-dimensional" network, CCC_k, with k even, gossiping can be performed in 5/2 · k - 2 communication rounds, which exactly matches the lower bound, thus completely solving the gossiping problem for these networks. For odd k we improve upon the best previous algorithm without matching the lower bound.

In this paper, we introduce a new information dissemination problem in which gossiping is to occur continuously but with restricted use of the network. In this problem, information continues to be generated by each member of the network and, thus, the gossip process must be ongoing. However, in order to allow the network to be used for other purposes, the communications used by the gossip process are limited to k calls per time unit. We present some preliminary results on this new problem.

This paper considers the gossiping problem in mesh-bus computers, in which n² nodes arranged on an n×n array are connected by n column-buses and n row-buses. The algorithm we propose in this paper completes the gossiping in [n/2]+[log₂ n]+1 steps. Since a lower bound on the number of steps for this problem is shown to be [n/2]+[log₂ n]−1, it takes at most only 2 more steps than an optimal algorithm.

Gossiping is proposed as the preferred communication primitive for replicating pivot data in dense matrix factorization on message passing multicomputer. Performance gains are demonstrated on a hypercube for LU factorization algorithms based on gossiping as opposed to broadcasting. This finding has consequences for the design of numerical software libraries.

In this note, we continue the study of messy broadcasting. We obtain exact values for the messy broadcasting time of complete graphs, paths, cycles, and complete d-ary trees. For hypercubes, we obtain exact values for messy broadcasting time under two of the models and present upper and lower bounds for the third model. We compare these times with (regular) broadcasting times in these graphs. We also present some simple bounds for arbitrary graphs which we use to compare the messy broadcasting times of cube-connected cycles, shuffle-exchange graphs, butterfly graphs, and DeBruijn graphs with their (regular) broadcasting times.

In this paper, we investigate the uses of virtual channels and multiple communication ports to improve the performance of global communication algorithms for cycles and multi-dimensional toroidal meshes. We use a linear cost model to compare the performances of the best single-port algorithms for broadcasting, scattering, gossiping, and multi-scattering with algorithms that can use multiple ports simultaneously. We conclude that the use of multiple ports can enhance performance when propagation costs are dominant and virtual channels can reduce the total start-up costs. The two mechanisms interact to produce different types of trade-offs for the different communication patterns.

In the neighbourhood gossiping problem, each node of a network starts with a unique message and must learn the messages of all of its neighbours. In this paper, we prove upper and lower bounds for neighbourhood gossiping in hypercubes under the single-port half-duplex and single-port full-duplex communication models.