We consider the problem of dimension-ordered embedding of complete binary trees into 3-dimensional meshes without link contention. In this paper, the embedding problems are studied under two different network models: half-duplexed networks and full-duplexed networks. Gibbons and Paterson showed that a complete binary tree T/sub p/ could be disjointedly embedded into a full-duplexed 2-dimensional mesh of optimum size without dimension-ordered routing. Using the dimension-ordered routing, the authors showed that T/sub p/ could be embedded into a 3-dimensional mesh of optimum size with link congestion two. This paper presents the dimension-ordered embedding algorithms of the complete binary trees into the wormhole routed 3-dimensional meshes without link contention achieving expansion of no larger than 1.125 of optimum in half-duplexed network model and optimum in full-duplexed network model.

We consider the problem of broadcasting in 2- and 3-dimensional mesh networks with the wormhole-routing capability. Our model assumes that each node is capable of communicating with /spl alpha/ nodes simultaneously where /spl alpha/ is a given integer with 1/spl les//spl alpha//spl les/4 for 2-dimensional meshes and 1/spl les//spl alpha//spl les/6 for 3-dimensional meshes. We give broadcasting algorithms that use optimal number of phases (if each side of the mesh is (/spl alpha/+1)/sup +/) or at most optimal number plus two phases (otherwise). Our algorithms require the predetermined location of the source node and this assumption can be relaxed by allowing one additional initial phase.

This paper is concerned with broadcasting on 2-dimensional torus and mesh networks using circuit-switched, half-duplex, and link-bound communication. It is assumed that there are α and β physical channels in the X- and Y-dimensions, respectively, and path selection between any two nodes is done using row-column routing. Given an n × n mesh or torus, we first discuss the lower bounds of broadcasting time; any broadcasting algorithm requires at least [log(2α + 2β + 1)n2] time steps and no broadcasting algorithm achieves this lower bound if α < β(2β + 1). We then show that broadcasting on a (2α + 2β + 1)p × (2α + 2β + 1)p torus can be done in 2p time steps, which is optimum, for any α ≥ 3 and β = 1. We also present approximation algorithms for the cases of mesh when α ≥ 1 and β = 1 and torus when α ≤ 2 and β = 1. © 1996 John Wiley & Sons, Inc.

We consider the problem of broadcasting on torus and mesh networks using circuit-switched, half-duplex, and link-bound communication. In this paper, we obtain an optimal broadcasting algorithm that uses pd time steps for a d-dimensional torus with (2d+1)/sup p/ nodes in each side of the torus. Using this algorithm, we show that a broadcasting on a d-dimensional mesh with the same size can be done in pd+p+d-1 time steps.