Abstract We consider the offline problem of routing a permutation of tokens on the nodes of ad‐dimensional hypercube, under a queueless MIMD communication model (in which we have the constraints that each hypercube edge may only communicate one token per communication step, and each node may only be occupied by a single token between communication steps). For ad‐dimensional hypercube, it is easy to see thatdcommunication steps are necessary. We develop a theory of “separability” which enables an analytical proof thatdsteps suffice for the cased= 3, and facilitates an experimental verification thatdsteps suffice ford= 4. This result improves the upper bound for the number of communication steps required to route an arbitrary permutation on arbitrarily larged‐dimensional hypercubes to 2d‐ 4. We also find an interesting side‐result, that the number of possible communication steps in ad‐dimensional hypercube is the same as the number of perfect matchings in a (d+ 1)‐dimensional hypercube, a combinatorial quantity for which there is no closed‐form expression. Finally we present some experimental observations which may lead to a proof of a more general result for hypercubes with arbitrarily large dimensiond. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010

Given m points (sites) and n obstacles (barriers) in the plane, we address the problem of finding a straight-line minimum cost spanning tree on the sites, where the cost is proportional to the number of intersections (crossings) between tree edges and barriers. If the barriers are infinite lines then there is a spanning tree where every barrier is crossed by O(√m) tree edges (connectors), and this bound is asymptotically optimal (spanning tree with low stabbing number). Asano et al. showed that if the barriers are pairwise disjoint line segments, then there is a spanning tree such that every barrier crosses at most 4 tree edges and so the total cost is at most 4n. Constructions with 3 crossings per barrier and 2n total cost provide a lower bound.We obtain tight bounds on the minimum cost spanning tree in the most exciting special case where the barriers are interior disjoint line segments that form a convex subdivision and there is a point in every cell. In particular, we show that there is a spanning tree such that every barrier is crossed by at most 2 tree edges, and there is a spanning tree of total cost 5n/3. Both bounds are tight.

The diameter of a directed graph is the maximum of the lengths of the shortest paths between all pairs of vertices. A directed graph is said to be tightly oriented if it has the same diameter as its undirected image graph. Our main result is tight orientations for all sufficiently large toroids, except those whose sizes in both dimensions are odd. We also prove the impossibility of tightly orienting all the toroids for which we do not present tight orientations, and we give partial results for dimensionality higher than two. © 1998 John Wiley & Sons, Inc. Networks 32: 1–11, 1998

The gossip problem involves communicating a unique item from every node in a graph to every other node. The minimum time required to do this for the binary hypercube under two models of communication is studied. In the first model, all communication links may be used concurrently but each may only carry information in one direction at a time. In the second, weaker model each node may be involved in only one communication at a time either as sender or receiver. In both cases, simple algorithms exist that are close to optimal. This paper shows that neither of these algorithms is optimal by exhibiting faster algorithms. In the first case, an optimal algorithm is obtained.

The gossip problem involves communicating a unique item from each node in a graph to every other node. This paper studies the minimum time required to do this under the weakest model of parallel communication, which allows each node to participate in just one communication at a time as either sender or receiver. A number of topologies are studied, including the omplete graph, grids, hypercubes, and rings. Definitive new optimal time algorithms are derived for complete graphs, rings, regular grids, and toroidal grids that significantly extend existing results. In particular, an open problem about minimum time gossiping in complete graphs is settled. Specifically, for a graph with N nodes, at least $\log _\rho N$ communication steps, where the logarithm is in the base of the golden ratio $\rho $, are required by any algorithm under the weakest model of communication. This bound, which is approximately $1.44\log _2 N$, can be realized for some networks and so the result is optimal.

Based on experiences with various debugging tools, the authors believe that the ideal tool represents several forms of integration: integration of scope from simple debugging to advanced performance monitoring; integration of techniques such as graphical and textual displays and real-time and postmortem analysis; connections between event monitoring and execution control; coordination of instrumentation in the parallel operating system with that in the tool; and a considered user interface throughout all components of the tool. Each of these forms of integration is briefly discussed.>