In this paper, we develop generalized methods to layout homogeneous product networks with any number of dimensions, and analyze their VLSI complexity by deriving upper and lower bounds on the area and maximum wire length. In the literature, lower bounds are generally obtained by computing lower bounds on the bisection width or the crossing number of the network being laid out. In this paper, we define a new measure that we call "maximal congestion", that can be used to obtain both the bisection width and the crossing number, thereby unifying the two approaches. Upper bounds are traditionally obtained by constructing layouts based on separators or bifurcators. Both methods have the basic limitation that they are applicable only for graphs with bounded vertex degree. The separators approach generally yields good layouts when good separators can be found, but it is difficult to find a good separator for an arbitrary graph. The bifurcators approach is easier to apply, but it generally yields larger area and wire lengths. We show how to obtain "strong separators" as well as bifurcators for any homogeneous product network, as long as the factor graph has bounded vertex degree. We illustrate application of both methods to layout a number of interesting product networks. Furthermore, we introduce a new layout method for product networks based on the combination of collinear layouts. This method is more powerful than the two methods above because it is applicable even when the factor graph has unbounded vertex degree. It also yields smaller area than the earlier methods. In fact, our method has led to the optimal area for all of the homogeneous product networks we considered in this paper with one exception, which is very close to optimal. In regards to wire lengths, the results obtained by our method turned out to be the best of the three methods for all the examples we considered, again subject to one (and the same) exception. We give an extensive variety of such examples.

We generalize the well-known odd-even merge sorting algorithm, originally due to Batcher (1968), and show how this generalized algorithm can be applied to sorting on product networks. If G is an arbitrary factor graph with N nodes, its r-dimensional product contains N/sup r/ nodes. Our algorithm sorts N/sup r/ keys stored in the r-dimensional product of G in O(r/sup r/F(N)) time, where F(N) depends on G. We show that, for any factor graph G, F(N) is, at most, O(N), establishing an upper bound of O(r/sup 2/ N) for the time complexity of sorting N/sup r/ keys on any product network. For product networks with bounded r(e.g. for grids), this leads to the asymptotic complexity of O(N) to sort N/sup r/ keys, which is optimal for several instances of product networks. There are factor graphs for which F(N)=O(log/sup 2/ N), which leads to the asymptotic running time of O(log/sup 2/ N) to sort N/sup r/ keys. For networks with bounded N (e.g. in the hypercube N=2, fixed), the asymptotic complexity becomes O(r/sup 2/). We show how to apply the algorithm to several cases of well-known product networks, as well as others introduced recently. We compare the performance of our algorithm to well-known algorithms developed specifically for these networks, as well as others. The result of these comparisons led us to conjecture that the proposed algorithm is probably the best deterministic algorithm that can be found in terms of the low asymptotic complexity with a small constant.

The grid and the mesh of trees (or MOT) are among the best-known parallel architectures in the literature. Both of them enjoy efficient VLSI layouts, simplicity of topology, and a large number of parallel algorithms that can efficiently execute on them. One drawback of these architectures is that algorithms that perform best on one of them do not perform very well on the other. Thus there is a gap between the algorithmic capabilities of these two architectures. We propose a new class of parallel architectures, called the mesh-connected trees (or MCT) that can execute grid algorithms as efficiently as the grid, and MOT algorithms as efficiently as the MOT, up to a constant amount of slowdown. In particular, the MCT topology contains the MOT as a subgraph and emulates the grid via embedding with dilation 3 and congestion two. This significant amount of computational versatility offered by the MCT comes at no additional VLSI area cost over these earlier networks. Many topological, routing, and embedding properties analyzed here suggest that the MCT architecture is also a serious competitor for the hypercube. In fact, while the MCT is much simpler and cheaper than the hypercube, for all the algorithms we developed, the running time complexity on the MCT matches those of well known hypercube algorithms. We also present an interesting variant of the MCT architecture that admits both the MOT and the torus as its subgraphs. While most of the discussion in this paper is focused on the MCT architecture itself, these analyses can be easily extended to the variant of the MCT presented here.

Analyzes some general properties of product networks that are pertinent to parallel architectures and then focuses on three case studies. These are products of complete binary trees, shuffle-exchange and de Bruijn networks. It is shown that all of these are powerful architectures for parallel computation, as evidenced by their ability to efficiently emulate numerous other architectures. In particular, r-dimensional grids and r-dimensional meshes of trees can be embedded efficiently in products of these graphs, i.e. either as a subgraph or with small constant dilation and congestion. In addition, the shuffle-exchange network can be embedded in an r-dimensional product of shuffle-exchange networks with dilation cost 2r and congestion cost 2. Similarly, the de Bruijn network can be embedded in an r-dimensional product of de Bruijn networks with dilation cost r and congestion cost 4. Moreover, it is well known that shuffle-exchange and de Bruijn graphs can emulate the hypercube with a small constant slowdown for "normal" algorithms. This means that their product versions can also emulate these hypercube algorithms with constant slowdown. Conclusions include a discussion of many open research areas.>

In a network of high performance workstations, many workstations are underutilized by their owners. The problem of using these idle cycles for solving computationally intensive tasks by executing a large task on many workstations has been addressed before and algorithms with O(N/sup 2/) time and O(N) space for choosing the optimal subset of workstations out of N workstations were presented. We improve these algorithms to reduce the running time to O(N log N), while keeping the space requirement the same. The proposed algorithms are particularly useful for SPMD parallelism where computation is the same for all workstations and the data space is partitioned between the workstations.>

Recently, the mesh connected trees (MCT) network has been proposed as a possible architecture for parallel computers. MCT networks are obtained by combining complete binary trees using the cross product operation. This paper focuses on structural, embedding, routing, and layout properties of the MCT networks. We show that MCT networks are computationally more powerful than grids and complete binary trees, and at least as powerful as meshes of trees (MOT). Analysis of VLSI complexity shows thai the additional power is obtained without asymptotically increasing the layout area with respect to the grid of at least 3 dimensions or to the MOT of any number of dimensions. A variation of the basic architecture with same maximum vertex degree and same asymptotic area complexity is also investigated. This variation contains the torus as a subgraph as well as the MOT, further increasing the computational power of the basic architecture. These results suggest that the basic MCT network and its variant are suitable architectures for a large class of massively parallel computations.

We consider a connected set of workstations as a “pool of processors” and develop a queueing model to analyze the performance of optimal co-scheduling algorithms. The pool of processors model was originally developed for the Amoeba operating system. It was also used in the design of the recent IBM supercomputer model 9076 SP1. Recently, co-scheduling has been suggested as an approach for scheduling computationally intensive tasks in the pool of processors model. Co-scheduling algorithms select the best possible subset of workstations for a task to minimize its completion time.

In a set of high performance workstations connected by a network, many workstations may be underutilized by their owners. While each workstation may be primarily responsible for executing its owner's tasks with the highest priority, the unused processing capacity may be made available to computationally intensive tasks submitted externally to the system. Static co-scheduling for such an environment has been considered previously (M.J. Atallah et al., 1991), where the goal was to maximize the speedup by partitioning the task among many workstations. The authors consider the problem from the system point of view, and develop a queuing model and efficient algorithms to minimize the mean response time. The results obtained show that significant improvements in the mean response time can be obtained through co-scheduling over that of the M/M/m system where each task would be assigned to a single workstation as a whole.>

The ability to embed arbitrarily large graphs in smaller graphs has important applications in mapping problems which require more processors than is available in a parallel architecture. We address this problem with the main focus on balancing processor loads. We show that maximum level of system utilization can be obtained when each host node emulates an equal number of "busy" guest nodes for each step of computation. While the embedding methods used are applicable to a variety of guest graphs, the main focus of the paper is on meshes of tree due to their importance as parallel architectures. Methods are also developed for embedding arbitrarily large complete binary trees and grids.

The construction of a dynamic cube network architecture that extends the capabilities of hypercube architectures with only a small increase in hardware complexity is described. The network is self-routing in the sense that there is a simple distributed routing algorithm which guarantees optimal paths between any pair of the vertices. This, together with other improvements in embedding properties, makes the dynamic cube an attractive alternative to the ordinary hypercube for massively parallel architectures.>

The construction of a crossed cube which has many of the properties of the hypercube, but has diameter only about half as large, is discussed. This network is self-routing, in the sense that there is a simple distributed routing algorithm which guarantees optimal paths between any pair of vertices. This fact, together with other properties such as regularity, symmetry, high connectivity, and a simple recursive structure, suggests that the crossed cube may be an attractive alternative to the ordinary hypercube for massively parallel architectures, SIMD algorithms, which utilize the architecture are developed, and it is shown that the CQ/sub n/ architecture can profitably emulate the ordinary hypercube. It is also shown that addition of simple switches can improve the capabilities of the system significantly. For instance, the dynamic reconfiguration capability allows hypercube algorithms to be executed on the proposed architecture. The use of these switches also improves the embedding properties of the system.>

A massively parallel optimization approach based on simple neighborhood search techniques was developed and applied to the problem of VLSI cell placement. Statistical models are developed to analyze the performance of the approach in general, and to derive statistical bounds on the quality of obtainable results. The results of these analyses suggest a simple framework for approximate solution of difficult problems. The approach is inherently parallel, and it can be implemented on any type of parallel computer. It was implemented on a simulated hypercube MIMD machine using Cosmic C on a network of Sun workstations. The method is empirically verified.>

A detailed analytical and simulation model that accurately captures the effect of communication delay for local area networks is presented. To demonstrate the framework, load sharing algorithms are presented and evaluated both with and without the effect of the communication network delay. The algorithms use the Ethernet communication protocol to their advantage and provide superior performance compared to several published algorithms. The strong performance results for the new algorithms demonstrate that a load sharing algorithm can cooperate rather than compete with a communication network.>

A new interconnection structure is proposed as a basis for distributed-memory parallel computer architectures. The network is a variation of the hypercube and preserves many of its desirable properties, including regularity and large vertex connectivity. It has the same node and link complexity, but has a diameter only about half of the hypercube's. Some of the basic properties of this topology are discussed. Efficient routing and broadcasting algorithms are presented.>

A network is proposed that preserves all of the properties of the hypercube, but has a diameter which is only about half of that of the hypercube. This network is self-routing, in the sense that there is a simple distributed routing algorithm which guarantees optimal paths between any pair of vertices. This fact, together with other properties such as regularity, symmetry, high connectivity, and a simple recursive structure, implies that the multiply twisted cube is an alternative to the ordinary hypercube for massively parallel architectures. Single-input multiple-data stream algorithm were developed which utilize the new architecture. The multiply-twisted hypercube architecture can be used to profitably emulate the ordinary hypercube. Some of the basic properties of this network are discussed, the programming issues are emphasized, and it is shown that any hypercube algorithm can be mapped to run on the new architecture. In many cases this mapping results in a substantial reduction in the running time due to more efficient routing of data between processors.>

Two algorithms are developed for minimizing control overheads in exchanging state information arising from the control messages used in determining the load levels at other servers. In the first algorithm, the load levels at other servers are guessed using a simple heuristic algorithm. Such a model is found to provide significant improvements compared to the no-load sharing case. The second algorithm improves upon the first one by replacing some unnecessary task transfers by a single probe. The simulation results obtained from these algorithms are presented and compared to an algorithm based on random selection of destinations for transfer tasks. It was concluded that a load sharing policy should try to maximize the success rate in finding good destinations for transfer tasks while minimizing the control overheads.>