Dense, symmetric graphs are useful interconnection models for multicomputer systems. Borel Cayley graphs, the densest degree-4 graphs for a range of diameters, are attractive candidates. However, the group-theoretic representation of these graphs makes the development of efficient routing algorithms difficult. In earlier reports, we showed that all degree-4 Borel Cayley graphs have generalized chordal ring (GCR) and chordal ring (CR) representations. We present the class-congruence property and use this property to develop the two-phase routing algorithm for Borel Cayley graphs in a special GCR representation. The algorithm requires a small space complexity of O(p+k) for n=p/spl times/k nodes. Although suboptimal, the algorithm finds paths with length bounded by 2D, where D is the diameter. Furthermore, our computer implementation of the algorithm on networks with 1,081 and 15,657 nodes shows that the average path length is on the order of the diameter. The performance of the algorithm is compared with that of existing optimal and suboptimal algorithms.

There is a continuing search for dense $( \delta ,D )$ interconnection graphs, that is, regular, undirected, degree $\delta $ graphs with diameter D and having a large number of nodes. Cayley graphs formed by Borel subgroups currently contribute to some of the densest known $( \delta = 4,D )$ graphs for a range of D [1]. However, the group theoretic representation of these graphs makes the development of efficient routing algorithms difficult. In an earlier report, it was shown that all Cayley graphs have generalized chordal ring (GCR) representations [2]. In this paper, it is shown that all degree-4 Borel Cayley graphs can also be represented by the more restrictive chordal rings (CR) through a constructive proof. A step-by-step algorithm to transform any degree-4 Borel Cayley graph into a CR graph is provided. Examples are used to illustrate this concept.

Relations among banyan multistage interconnection networks (MINs) of differing switch sizes are studied. If two N*N networks W and W' have switch sizes r and s, respectively, and if r>s, then W realizes a larger number of permutations than W'. Consequently, the two networks can never be equivalent. However, W may realize all the permutations of W', in which case W is said to functionally cover W' in the strict sense. More generally, W is said to functionally cover W' in the wide sense if the terminals of W can be relabeled so that W realizes all the permutations of W'. Functional covering is topologically characterized, and an optimal algorithm to decide strict functional covering is developed.>

It is shown that all finite Cayley graphs can be represented by generalized chordal rings (GCR). An example Borel Cayley graph is used to illustrate the generation of GCR representations. A sufficient condition is given for the representation of a Cayley graph as a chordal ring (CR). With the integer labeling of GCR representations, a straightforward, progressive routing algorithm based on table look-up is summarized.>

The routing control of Benes networks has proven to be costly. This paper introduces a new approach to fast control of N × N 3-stage Benes networks of r × r crossbar switches as building blocks, where N = r2 and r ≥ 2. The new approach consists of setting the leftmost column of switches to an appropriately chosen configuration so that the network becomes self-routed while still able to realize a given family of permutations. This approach requires that, for any given family of permutations, a configuration for the leftmost column be found. Such a family is called compatible and the configuration of the leftmost column is called the compatibility factor. In this paper, compatibility is characterized and a technique to determine compatibility and the compatibility factor is developed. The technique is used to show the compatibility and find the compatibility factor of Ω-realizable permutations, the permutations needed to emulate a hypercube, and the families of permutations required by FFT, bitonic sorting, tree computations, multidimensional mesh and torus computations, and multigrid computations. An O(log2 N) time routing algorithm for the 3-stage Benes will also be developed. Finally, as only 3 compatibility factors are required by the above families of permutations, it will be proposed to replace the first column by 3 multiplexed connections yielding a self-routing network with strong communication capabilities.

Existing procedures to decide network equivalence in log N-stage banyan networks are based on analysis of permutations, take polynomial but costly time, and do not shed light on or take advantage of the relationship between functionality and topology. This relationship is addressed and it is shown that two log N-stage banyan networks of the same switch size are functionally equivalent if and only if they have the same underlying topology. An O(N log N) algorithm is derived which decides if two N-stage banyan networks of N inputs, N outputs, and r*r crossbar switches as building blocks realize the same permutations. The algorithm works by comparing the underlying topologies of the two networks. The algorithm is optimal because the size of the networks is O(N log N).>

The k-way bitonic sort algorithm, a generalization of K.E. Batcher's bitonic sort algorithm (1968), is presented. This variation of the algorithm is based on a k-way decomposition instead of a two-way decomposition. It is proven that Batcher's bitonic sequence decomposition theorem still holds with this multiway decomposition. This leads to applications of sorting networks with bitonic sorters of arbitrary or mixed sizes.>

A computer architecture for concurrent computing is proposed which has the shared memory aspect of tightly coupled multiprocessor systems and also the connection simplicity associated with message-connected, loosely-coupled multicomputer systems. A large address space is dynamically partitioned into contiguous segments that can be accessed by a single processor. The partitioning is accomplished by switching the system buses. The completion of a concurrent process is signaled by a processor's return to an idle state and the reattachment of its memory segment to the neighboring active processor. In effect, the assignment of an address sequence and the activation of a processor is a process-fork operation, and the processor deactivation and memory segment reattachment is a process-join. Following a description of the MP/C structure and operation, programming conventions are explained and demonstrated. Applications include tree-structured multiprocessing, recursive and nondeterministic procedures, very high precision numerical calculations, process-structured operating systems, and others. The linear MP/C structure is extensible to higher dimensions. A two-dimensional system is described and its application is discussed. Finally, performance issues are presented, and the MP/C architecture is compared with related designs.

As a result of recent technological developments there is an increasing interest in the interconnection of microcomputers through networks. For general computation the interconnection graphs should have short internode communication paths and should be of low degree, systematically structured, and incrementally extensible. A family of graphs, called multitree structured (MTS) having these properties is presented. The MTS graphs of degree three have the maximum number of nodes, known to date, for given diameters.

A family of regular graphs of degree 3, called Chordal Rings, is presented as a possible candidate for the implementation of a local network of message-connected (micro) computers. For a properly constructed graph in this family having n nodes the diameter, or maximum length message path, is shown to be of 0(n 1/2). The symmetry of the graphs makes it possible to determine message routing by using a simple distributed algorithm. The given algorithm is also potentially useful for the determination of alternate paths in the event of node or link failure.

The development of microprocessors has suggested the design of distributed processing and multiprocessing computer architectures. A computer system design incorporating these ideas is proposed, along with its impact on memory management and process control aspects of the system's operating system. The key design feature is to identify system processes with microprocessors and interconnect them in a hierarchy constructed to minimize intercommunication requirements.

This paper presents a brief description of a general multiprogramming (and time-sharing) system in operation at the University of Michigan. A number of time and space distributions obtained from a typical month of operation are presented. The performance is summarized by a load diagram. Efficiency as a comparison with ideal performance is discussed and a model suitable for idealization is proposed.

The problem studied is the effect of a time-sharing environment on the structure of programs and on the addressing strategies which may be employed in the hardware. An account is given of some very recent developments toward reduction in the system overhead needed to facilitate time-sharing. One hardware-software scheme designed to implement this reduction is described in some detail.

This paper describes an algorithm for scanning Boolean expressions.Such an algorithm takes a complex, relational expression and transforms it into an optimal set of computing steps.The result is optimal in the sense that no redundant evaluations are made.The particular algorithm described is advantageous in that, as a variant of a well-known *