Parallel Processing Letters

In the postal model of message passing systems, the actual communication network between processors is abstracted by a single communication latency factor, which measures the inverse ratio of the time it takes for a processor to send a message and the time that passes until the recipient receives the message. In this paper we examine the problem of broadcasting multiple messages in an order-preserving fashion in the postal model. We prove lower bounds for all parameter ranges and show that these lower bounds are within a factor of seven of the best upper bounds. In some cases, our lower bounds show significant asymptotic improvements over the previous best lower bounds.

Multicast communication refers to the delivery of the same message from one source node to an arbitrary number of destination nodes. Two multicast wormhole routing methods have been presented in [13] for multicomputers with 2D-mesh and hypercube topologies. Also, a theory for the design of deadlock-free adaptive routing algorithms for wormhole networks has been proposed in [7, 8]. This theory supplies the sufficient conditions for an adaptive routing algorithm to be deadlock-free, even when there are cyclic dependencies between channels.

This paper analyses the additional channel dependencies produced by multicast routing algorithms on wormhole networks. Then, the theory proposed in [7, 8] is extended by considering them. As an example, the multicast routing algorithms presented in [13] are extended, taking advantage of the alternative paths offered by the network.

We present a class of efficient algorithms for global combine operations in k-port message-passing systems. In the k-port communication model, in each communication round, a processor can send data to k other processors and simultaneously receive data from k other processors. We consider algorithms for global combine operations in n processors with respect to a commutative and associative reduction function. Initially, each processor holds a vector of m data items and finally the result of the reduction function over the n vectors of data items, which is also a vector of m data items, is known to all n processors. We present three efficient algorithms that employ various trade-offs between the number of communication rounds and the number of data items transferred in sequence. For the case m=1, we have an algorithm which is optimal in both the number of communication rounds and the number of data items transferred in sequence.

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.

Generalized de Bruijn and Kautz networks are important since they allow networks of any size with vertices of fixed degree. Communication issues are related to easy construction/enumeration of shortest paths between vertex-couples. An easy method based on residue calculation is introduced to find multiple shortest paths if they exist, allowing better communication schemes. The main results concern the properties of multiple shortest paths (especially disjunction) and the number of vertex-couples separated by several shortest paths as a function of the graph size. Conditions to get or avoid networks with multiple shortest paths are proposed which can be useful for the design of communication schemes.

We give a constructive proof that there are d−1 arc-disjoint Hamiltonian circuits in the d-ary De Bruijn graph when d is a power of 2. We also demonstrate the existence of at least arc-disjoint Hamiltonian circuits in the general case, where is the prime factorization of d

In this paper, we provide a specification for a class of communication networks that are immune to single site failures, not only maintaining the ability to transfer messages between operable sites but doing so with no additional delay (i.e. no increase in length of communication path). We call these networks self-repairing and refer to their underlying topologies as self-repairing graphs. Our specification includes a constructive characterization of a class of minimal self-repairing graphs and an algorithmic determination of associated routing tables that can be used by a simple message transfer procedure to realize the desired immune behavior.

In this paper we study the fault-tolerant properties of the Supercube, a new inter-connection network recently introduced by Sen [15]. The Supercube is a generalization of the Hypercube that can be realized for any number of nodes and not only for powers of 2. Moreover, it has the same diameter and connectivity of the Hypercube.

We shall prove that the diameter of the surviving route graph of the N-node Supercube S_N, if less than [log₂ N] nodes or edges fail, is at most 4 for any minimal routing, and exhibit a minimal routing for which the surviving route graph has diameter 2. Then, we will show that, when 2^s+2^s−1≤N<2^s+1 the failures are [log₂ N], the diameter of the surviving route graph is at most 5 for any minimal routing.

We will also prove that the fault diameter of S_N is exactly [log₂ N]+1 when N∉{2^s+1−1, 2^s+1−2, 2^s+2^s−1+1} and [log₂ N]+2 otherwise.

A common arising problem in many parallel algorithms is broadcast. Many multiprocessors do not have dedicated hardware for this purpose. In this paper, we address the problem of simulating multiple-item broadcast by point-to-point message transmission, where a source processor has many messages which it wishes to disseminate to P−1 other processors. In a step, a processor can send at most one item from among those in its possession and receive at most one item. An item is received at most L steps after it is sent. The goal is to find a schedule that achieves the broadcast in minimum time. We improve on previous results by developing a simpler and almost optimal solution which makes no assumptions about L or P. We also provide a bound on the performance degradation when the latency, L, is allowed to vary.

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.

The computation of upper bounds of the bandwidth of graphs is mainly based on the giving of a numbering which achieves these bounds. In [9], Harper proposed such a numbering for the binary hypercube, based on the Hamming weights and binary values of the hypercube vertices.

By defining an extended Hamming weight, this numbering can lead to an equivalent proof for the d-ary de Bruijn graph. We present in this paper an approach, based on the use of the continuous domain and Laplace’s theorem for asymptotically evaluating integrals, which leads to the enumeration of the vertices of the same extended Hamming weight in the non-binary case. This result allows the computation of an upper bound of the bandwidth of the unoriented de Bruijn graph, as well as an upper bound of its vertex-bisection when both the diameter and the degree are even.

A dynamic memory is a storage medium constituted by an array of cells and an interconnection network between them. It is characterized by the constant circulation of the stored data. The objective is to design the interconnection network in order to have small access times and a simple memory control. Several interconnection schemes have been proposed in the literature. This paper presents a quite general model for such structures that greatly facilitates both the design and the control of the memory. Most previous proposals of dynamic memory interconnection networks are particular instances of our model. Moreover, our approach is used to obtain new proposals of interconnection topologies for dynamic memories and fast cyclic shift registers. Namely, a model that optimizes both the access time and the size of the memory and two memory organizations for sequential access are presented.

Given a graph G, a spanning subgraph H of G is a t-spanner if for every edge xy of G, the distance in H between x and y is at most t. Spanners have applications in communication networks, distributed systems, parallel computation, and other areas. This paper is concerned with the complexity of determining whether a graph contains a t-spanner whose maximum degree is at most Δ, where Δ, t≥2 are fixed integers. The problem is shown to be NP-complete for any fixed Δ≥4 and t≥2, and linear for Δ=2 and any fixed t≥2. The problem for Δ=3 is open. Furthermore, if the t-spanner in the problem is required to be a tree, then the problem becomes linear. The problem also becomes linear when input graphs are partial k-trees for some fixed integer k.

The performance of the communication network of a massively parallel processor depends, among other parameters, on the network topology, the message flow control and the routing mechanisms. This paper analyses the gains in average message latency and maximum sustained throughput that can be achieved using an adaptive routing strategy instead of an oblivious one. Two different bidimensional topologies have been studied, mesh and torus, using cut-through message flow control. First, we have simulated an ideal case in which there is no limit to the temporary storage capacity of the routing node. Then, a more realistic design, that implies the implementation of a deadlock avoidance technique, is analysed. To assure deadlock-free routing, the network is split into several virtual networks. Results show that adaptive routing is not a good election with this kind of networks. The torus topology shows potentially better results than the mesh. In any case, a different deadlock avoidance technique should be implemented if these potential gains are to be exploited.

This paper presents recent results on the MP1 router chip designed to implement scalable parallel computers. We survey design considerations used in order to reduce message delivery latency to a minimum. Results will be presented of simulations of the MP1 network which back up these considerations. It will be shown that there are many degrees of freedom in implementation and that implementation issues will often overwhelm other considerations, those on which simulation is focused, leading to anomalous predictions from those results. An example will be given on this. Even ultra-low latency networks will still have access times to remote data which are 10 to 100 times that for access to local data and architectures which tolerate low latency data-access must be exploited if scalable performance is to be obtained in these parallel machines based on networks.

A new family of interconnection networks, designed for massively parallel computers, is presented. Their main feature is a diameter smaller than the diameter of the hypercube up to networks of large sizes. As their degrees are fixed, they appear to be good challengers to other possible interconnection networks.