Narrow Results

Much work has been done on the problem of synthesizing a processor array from a system of recurrence equations. Some researchers limit communication to nearest neighbors in the array; others use broadcast. In many cases, neither of the above approaches result in an optimal execution time.

In this paper a technique called bounded broadcast is explored whereby an element of a processor array can broadcast to a bounded number of other processors. This technique is applied to the problems of transitive closure and all-pairs shortest distance, resulting in time complexities that are smaller than those reported previously. In general, the technique can be used to design bounded broadcast systolic arrays for algorithms whose implementation can benefit from broadcasting.

Clusters of symmetric multiprocessor nodes (SMP clusters) are one of the most important parallel architectures at the moment. The architecture consists of shared-memory nodes with multiple processors and a fast interconnection network between the nodes. New programming models try to exploit this architecture by using threads in the nodes and using message-passing-libraries for inter-node communication. In order to develop efficient algorithms, it is necessary to consider the hybrid nature of the architecture and of the programming models. We present the κNUMA-model and a methodology that build a good base for designing efficient algorithms for SMP clusters. The κNUMA-model is a computational model that extends the bulk-synchronous parallel (BSP) model with the characteristics of SMP clusters and new hybrid programming models. The κNUMA-methodology suggests to develop efficient overall algorithms by developing efficient algorithms for each level in the hierarchy. We use the problem of personalized one-to-all-broadcast and the dense matrix-vector-multiplication for the presentation. The theoretical results of the analysis of the dense matrix-vector-multiplication are verified practically. We show results of experiments, made on a Linux-cluster of dual Pentium-III nodes.

In this paper, we study broadcasting protocols where nodes use some of their neighbors to forward messages. We propose a new protocol based on a variant of neighbor elimination scheme using RNG graph to ensure a full coverage of the network. The computation of RNG uses two kinds of distance: a geometrical one and and neighborhood-based distance that permits to use our protocol without positioning system. This protocol, called RRS for RNG Relay Subset, provides a self-selecting forwarding neighbor operating mode which guarantees a fair broadcast loading. In RRS a node v is a relay for a node u if and only if v is a neighbor of u and v has a RNG-neighbor which is not covered by u transmission. Moreover, experiments with 802.11-like MAC layer show that RRS is efficient.

Our work is to study the Minimum Latency Broadcast Scheduling problem in the geometric SINR model with power control. With power control, sensor nodes have the ability to adjust transmitting power. While existing works studied the problem assuming a uniform power assignment or allowing unlimited power levels, we investigate the problem with a more realistic power assignment model where the maximum power level is bounded. To the best of our knowledge, no existing work formally proved the NP-hardness, though many researchers have been assuming that this fact holds true. In this paper, we provide a solid proof for this result.

In classical massively parallel computers, the complexity of the interconnection networks is much higher than the complexity of the processing elements themselves. However, emerging optical technologies may provide a way to reconsider very large parallel architectures where processors would communicate by optical means. In this paper, we compare some optically interconnected parallel multicomputer models with regard to their communication capabilities. We first establish a distinction of such systems, based on the independence of the communication elements embedded in the processors (transmitters and receivers). Then, motivated by the fact that in multicomputers some communication operations have to be very efficiently performed, we study communication problems, namely, broadcast and multi-broadcast, under the hypothesis of bounded fanout. Our results take also into account a bounded number of available wavelengths.

In this paper, we propose a new method of implementing bus operations on mesh wormhole routers with small additional circuits. The bus, called a virtual bus, is set up dynamically upon a request by bypassing existing datapath in wormhole routers. After bus setup, it acts as a real bus by sharing the point-to-point links of the corresponding row/column of the mesh. Simulation results show that the 2D (two-dimensional) mesh with the virtual bus outperforms the mesh with separate buses.

Collective communication performance is critical in a number of MPI applications. In this paper we focus on two widely used primitives, broadcast and reduce, and present experimental results obtained on a cluster of PC connected by InfiniBand. We integrated our algorithms in the MPICH library and we used MPICH implementation of broadcast and reduce primitives to compare the performance of our algorithms based on α-trees. Our tests show that the MPICH implementation can be improved.

In optical networks the approach called wavelength division multiplexing allows multiple data streams to be transmitted concurrently along a single optical link, with different streams assigned separate wavelengths. In this paper we refer to all-optical networks, in which each connection is totally optical except at the terminal nodes. For these networks we determine the minimum possible number of links required to perform a fault tolerant broadcast from any node, in terms of the number of nodes, the number of link failures to tolerate and the number of wavelengths to use. We also give lower and upper bounds on the number of wavelengths required for any broadcast which tolerates a given number of link failures on networks with arbitrary topologies.

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.

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.

We consider the problem of broadcasting on an n-dimensional hypercube with wormhole e-cube routing, intermediate reception capability, and one-port communication. We give an algorithm, optimal to within a multiplicative constant, that broadcasts in this model in Θ(n/log₂(n+1)) routing steps. We also give routing algorithms that achieve tight time bounds for n-cubes where n ≤ 6.

We address the problem of performing a pipelined broadcast on a mesh architecture. Meshes require a different approach than other topologies, and their very nature puts a tighter bound on the performance that one can hope to achieve. By using the appropriate techniques, however, one can obtain excellent performance for sufficiently long messages. The resulting algorithm will work on meshes of any dimension with any number of nodes. Our model assumes that the mesh is a torus and/or that it has bidirectional links and uses wormhole routing. Performance data from the Cray T3D are included.

In this paper, we present several optimal and nearly optimal broadcast and summation algorithms for multiprocessors whose interconnection network consists of a hierarchy of rings. Although useful heuristics have been proposed for such systems, we present the first exact analysis of broadcast and summation on hierarchical ring architectures.

Recently Akl and al. introduced a new model of parallel computation, called BSR (broadcasting with selective reduction) and showed that it is more powerful than any CRCW PRAM and yet requires no more resources (asymptotically) for implementation than even EREW PRAM [2,3,4]. The model allows constant time solutions to sorting, parallel prefix and other problems. In this paper, we describe constant time solution to the detection of repetitions (with overlapping) problem using the one criterion BSR model. This is the first constant time solution to this problem on any model of computation. If the problem is only to detect the existence of any repetition then n processors suffice, where n is the length of the string. If all repetitions are to be found then processors suffice in our algorithm.

In most distributed memory MIMD multiprocessors, processors are connected by a point-to-point interconnection network, usually modeled by a graph where processors are nodes and communication links are edges. Since interprocessor communication frequently constitutes serious bottlenecks, several architectures were proposed that enhance point-to-point topologies with the help of multiple bus systems so as to improve the communication efficiency. In this paper we study parallel architectures where the communication means are constituted solely by buses. These architectures can use the power of bus technologies, providing a way to interconnect much more processors in a simple and efficient manner.

We present the hyperpath, hypergrid, hyperring, and hypertorus architectures, which are the bus-based versions of the well used point-to-point interconnection networks. Using (hyper) graph theoretic concepts to model inter-processor communication in such networks, we give optimal algorithms for broadcasting a message from one processor to all the others. For deriving high performance communication patterns we developed a new tool called simplification. The idea is to construct a graph, to be called representative graph, from the original hyper-topology, in such a way that it will become easy to describe and perform communication schemes to the former that will fit to the latter, because the simplification concept also allows us to partially use some already known communication algorithms for usual networks.

In this paper we discuss minimum energy broadcast routing with directional antennas in ad hoc and sensor networks. We assume that the network consists of sensor nodes whose antennas are switched beam directional antennas. The problem of our concern is: a given set V with n nodes and each node v_i has l(i) transmission directions (i.e. the antenna sectors) and a broadcast request sourced at s, how to find a broadcast tree rooted at s and spanning all nodes in V such that the total energy is minimized. This problem involves with the choice of transmitting nodes and their transmission directions, which is NP-hard. We firstly propose a directed Steiner tree-based approximation algorithm for this problem and discuss its distributed implementation. Then we also propose a |V|-approximation algorithm and one heuristic with lower time complexities. Extensive simulations have demonstrated the efficiency of our algorithms.

For a given graph G, a function f : V(G) → {0, 1, …, diamG} such that for every vertex v of G, f(v) ≤ e(v) (where e(v) is the eccentricity of the vertex v and diamG is the diameter of G), is a broadcast on G. A broadcast f is a dominating broadcast if N_f[V⁺] = V(G), where V⁺ = {u | f(u) > 0}, N_f[V⁺] = ⋃_u∈V⁺N_f[u], and N_f[u] = {v | d(u, v) ≤ f(u)}. In this paper, inspired by Dunbar et al. [3], we study limited dominating broadcast in graphs and obtain some properties, bounds, and characterizations for limited broadcast domination number in graphs.

An independent broadcast on a graph $G$ is a function $f:V\to \{0,\dots ,\mathrm{\text{diam}}(G)\}$ such that (i) $f(v)\le e(v)$ for every vertex $v\in V(G)$, where $diam(G)$ denotes the diameter of $G$ and $e(v)$ the eccentricity of vertex $v$, and (ii) $d(u,v)>max\{f(u),f(v)\}$ for every two distinct vertices $u$ and $v$ with $f(u)f(v)>0$. The broadcast independence number ${\beta }_b(G)$ of $G$ is then the maximum value of ${\sum }_{v\in V}f(v)$, taken over all independent broadcasts on $G$. We prove that every circulant graph of the form $C(n;1,a)$, $3\le a\le \lfloor \frac{n}{2}\rfloor$, admits an optimal $2$-bounded independent broadcast, that is, an independent broadcast $f$ satisfying $f(v)\le 2$ for every vertex $v$, except when $n=2a+1$, or $n=2a$ and $a$ is even. We then determine the broadcast independence number of various classes of such circulant graphs, and prove in particular that ${\beta }_b(C(n;1,a))=\alpha (C(n;1,a))$, except for $C(n;1,2)$, $C(2a+1;1,a)$, or $C(2a;1,a)$ with $a\ne 2^p$ and $p\ge 0$, where $\alpha (C(n;1,a))$ denotes the independence number of $C(n;1,a)$.