We conduct a general study of the topological properties of optical transpose interconnection systems (OTIS). We first obtain their basic topological metrics of size, degree, shortest distance and diameter, and then we obtain results related to the recursive structure and efficient embedding of meshes, cubes, spanning trees and cycles. We also present minimal one-to-one routing and optimal broadcasting algorithms, and we show how to construct node-disjoint paths between any two nodes of an OTIS network. Recent studies have addressed only particular members of the general class of OTIS networks. In this paper, we present unified tools for obtaining the topological properties of an arbitrary OTIS network based on the properties of the corresponding factor network.

We present a number of results related to the fault tolerance of Cartesian product networks. We start by presenting a method for building containers (i.e., sets of node-disjoint paths) between any two nodes of a product network based on given containers for the factor networks. Then, we show that the best achievable fault diameter (i.e., diameter under maximum fault conditions), under reasonable network regularity and connectivity conditions, is equal to the fault-free diameter plus one. The concept of high fault resilience is then defined. We then prove that if each factor network is highly resilient, then their Cartesian product has minimal fault diameter. We derive from these results that Cartesian products of several popular networks are highly resilient and have minimal fault diameter equal to diameter plus one. These results spare future efforts that would be needed to individually determine the fault diameter of such networks as has been the practice with previously studied networks.

We study the cross product as a method for generating and analyzing interconnection network topologies for multiprocessor systems. Consider two interconnection graphs G/sub 1/ and G/sub 2/ each with some established properties such as symmetry, low degree and diameter, scalability, simple optimal routing, recursive structure (partitionability), fault tolerance, existence of node-disjoint paths, low cost embedding, and efficient broadcasting. We investigate and evaluate the corresponding properties for the cross product of G/sub 1/ and G/sub 2/ based on the properties of G/sub 1/ and those of G/sub 2/. We also give a mathematical characterization of product families of graphs which are closed under the cross product operation. This investigation is useful in two ways. On one hand, it gives a new tool for further studying some of the known interconnection topologies, such as the hypercube and the mesh, which can be defined using the cross product operation. On the other hand, it can be used in defining and evaluating new interconnection graphs using the cross product operation on known topologies.

We present and evaluate, for the first time, a parallel algorithm for solving the LU decomposition problem on the star graph. The proposed parallel algorithm is of O(N/sup 3//n!) computation complexity and uses O(Nn) communication time to decompose a matrix of order N on a star graph of dimension n, where N/spl ges/(n-1)!. The incurred communication time is better than the best known results for the hypercube, O(Nlogn!), and the mesh, O(N/spl radic/n!), each with approximately n! nodes. The proposed parallel algorithm takes advantage of the attractive topological qualities of the star graph in order to reduce the communication time involved in tasks such as pivoting, row/column interchanges, and pivot row and multipliers column broadcasts.

We obtain the fault diameter of k-ary n-cube interconnection networks (also known as n-dimensional k-torus networks). We start by constructing a complete set of node-disjoint paths (i.e., as many paths as the degree) between any two nodes of a k-ary n-cube. Each of the obtained paths is of length zero, two, or four plus the minimum length except for one path in a special case (when the Hamming distance between the two nodes is one) where the increase over the minimum length may attain eight. These results improve those obtained by B. Bose et al. (1995) where the length of some of the paths has a variable increase (which can be arbitrarily large) over the minimum length. These results are then used to derive the fault diameter of the k-ary n-cube, which is shown to be /spl Delta/+1 where /spl Delta/ is the fault free diameter.