We propose STWnet, a self-routing high bandwidth optical network architecture for interconnecting users, grouped together as g groups with w users per group. STWnet uses the three dimensions of space, time, and wavelength by combining the advantages of space and temporal switching with the benefits of wavelength parallel data transmissions. Technologically difficult switching of individual wavelengths is avoided by prearranging transmissions in a way that they can be switched in a wavelength insensitive manner. Wavelengths are reused within the network thus allowing for a larger switching fabric. The proposed architecture can be internally expanded either in the spatial or temporal dimension to allow for multiple packets to be delivered to the same destination group. The expansion factor is determined based on the group knockout principle and given typical traffic patterns is a small number. STWnet allows easy group to group multicasting and broadcasting while system-wide multicasts and broadcasts can be achieved through repetitive group-to-group transmissions. The network uses readily available components such as opto-electronic directional couplers, fixed wavelength transmitters, and diffraction based parallel receivers while avoiding the use of relatively slow and expensive tunable components.

We propose TDM/TWDM de Bruijn networks and ShuffleNets by utilizing small all-optical dilated slipped banyan networks, DSBs (Thompson, 1991). The proposed networks require fewer switches than DSBs, and smaller numbers of wavelengths than WDM de Bruijn networks and ShuffleNets. Furthermore, only one fixed-wavelength transmitter and one fixed-wavelength receiver are required for each node.

We propose SXmin: a self-routing, group-knockout principle based asynchronous transfer mode (ATM) packet switch which provides comparable delay-throughput performance and packet loss probabilities at significantly reduced hardware requirements compared to earlier switches. The M/spl times/N SXmin consists of an N/spl times/N Batcher sorter followed by log/sub 2/N-1 stages of sort-expander (SX) modules arranged in the form of a complete binary tree. Each SX module consists of a column of 2/spl times/2 switches with a wraparound-unshuffle input-output interconnection. This enables the hierarchical utilization of the group-knockout principle to expand the number of inputs by a small factor at each stage, resulting in a significant reduction in overall hardware complexity. Routing at each switch is controlled by a single bit. However, in case of contention, a dual bit resolution algorithm is used locally which drops excess packets in a predetermined manner while ensuring global randomness of packet loss over the entire switching network. There are no internal buffers at the individual stages and therefore the internal delay is constant and proportional to the number of stages. The use of simple hardware components and regular interconnections in the SX modules makes the network suitable for optical implementation.

The general time-space-time switching problem in telecommunications requires the use of multichannel time slot interchangers. We propose two multichannel time slot sorters which sort N/sup 2/ time-division multiplexed (TDM) optical inputs, arranged as N frames with N time slots per frame using O(Nlog/sup 2/N) optical switch elements. The TDM optical inputs are sorted in place without expanding the space-time fabric into a space-division switch. The hardware components used are 2/spl times/2 optical switches (LiNbO/sub 3/ directional couplers) and optical delay lines connected in a feedforward fashion. Two space-time variants of the spatial odd-even merge algorithm are used to design the sorters. By maintaining the number of shift-exchange operations invariant at each stage, the proposed sorters use fewer switches than previously proposed sorters using switches with feedback line delays. The use of local control at each 2/spl times/2 switch makes the proposed sorters more practical for high-speed optical inputs than Benes-based time slot permuters with global control and high latency, which affects interframe distance. Both time slot sorters support pipelining of input frames and sorted outputs are available at each time slot after an initial frame delay. The proposed sorters find practical application in the time-domain equivalents of space-division, nonblocking, self-routing packet switches using the sort-banyan architecture, such as the Starlite switch, Sunshine switch, etc.

The authors propose optical networks TdB(d, k) and TDM ShuffleNet(d, k), which are the TDM versions of the WDM de Bruijn network and the WDM ShuffleNet(d, k), respectively. They also propose the TWdB(d, k) and TWDM ShuffleNet(d, k), variations of the TdB and TDM ShuffleNet, which combine the TDM and WDM to further reduce the hardware cost. The dilated slipped banyan networks, DSB(d)'s are used to provide a time division multiplexed operation in all four networks. The proposed networks have a simple column control and a dilated operation suitable for guided-wave and free-space technologies. Only one fixed-wavelength transmitter and one fixed-wavelength receiver are required per node. The performance in terms of channel efficiency, delay and throughput is analysed.>

The recent demonstration of an all-optical, stored-program, digital computer by our group focused on high-speed optoelectronic design. It was made possible by a new digital design method known as time-of-flight design. A rudimentary, but general-purpose, proof of principle computer was built, which is all-optical in the sense that all signals connecting logic gates and all memory are optical in nature. LiNbO/sub 3/ directional couplers, electrooptic switches, are used to perform logic operations. In addition to demonstrating stored program operation in an optoelectronic digital computer, the system demonstrated the feasibility of the new design method, which does nor use any flip-flops or other bistable devices for synchronization or memory. This potentially allows system clock rates of the same order as device bandwidth. This paper describes how the time-of-flight design method was motivated by the special properties of optoelectronic digital design. The basic principles of the method we employed will be discussed along with some of its potential advantages. The experimental work with digital optical circuits leading up to and including the stored program computer experiment will then be discussed. Finally, the future potential of time-of-flight design in high-bandwidth optoelectronic systems will be discussed.>

We consider time slot interchangers (TSIs) which are built from 2/spl times/2 exchange switches and delays and which are useful for time division multiplexed (TDM) systems in telecommunications and pipelined systems such as time multiplexed optical multiprocessors. We formulate a general method for constructing TSIs based on multistage interconnection networks in the space domain via space-to-time mapping. Two types of TSIs, time slot permuters and time slot sorters, are considered. We review the time slot permuter based on the Benes network, and obtain the /spl Lambdaspl tilde/ time slot permuter based on the bit-controlled, self-routing /spl Lambda/ permutation network. The time slot sorter, S/sub N/, is obtained from the Batcher spatial sorting network. The generalized Lambda time slot permuter /spl Lambdasub Nsup q/ is obtained, in an algorithmic approach, by combining the idea of the /spl Lambdaspl tilde/ time slot permuter and Q-way bitonic decomposition (Q=2/sup q/). The numbers of switches, control complexities, and frame delays of these architectures are compared, and the problem of crosstalk in optical implementation is discussed. It is shown that control complexity can be traded against the number of switches.>

Explains why the Force parallel programming language has been easily portable between eight different shared memory multiprocessors. The authors show how a two-layer macro processor allows them to hide machine dependencies and to build machine-independent high-level language constructs. The importance of packaging low-level synchronization operations is demonstrated by a proof of mutual exclusion for asynchronous variable operations. The Force constructs enable one to write portable parallel programs largely independent of the number of processes executing them.>

The authors formulated a general method for constructing time slot permuters from spatial permutation networks. Using the method, they constructed a new time slot permuter, the Lambda time-slot permuter. The Lambda time slot permuter is obtained from the bit-controlled, self-routing permutation network, the Lambda network. While the Lambda time slot permuter requires more hardware than the time slot permuter based on the Benes network described by S.V. Ramanan et al. (1990), its control is very simple. In the Lambda time slot permuter, a single bit from the destination tag in the first of a pair of time slots entering an exchange element is used as the control bit so that the switch setting can be done before the second time slot arrives; thus, it is possible that the switch setting does not incur any delay. The Lambda time slot permuter is suitable for a class of applications where on-the-fly control of the time slot permuter is important, and is especially efficient for a pipelined operation.>

This paper describes a technique for time multi­ plexing multiple processors on a single hardware plat­ rorm. This technique should be useful whenever an archi­ tecture employs devices that have high bandwidth and simultaneously high temporal latency. These architec­ tures were explored during the development of a bit serial optical computer using optical fibers for interconnection and directional couplers as logic devices. We describe an optical counter developed in our laboratory as a proof­ ?f-principle experiment that permits two simultaneous, mdependent counts to be accumulated on the same hardware. Future machines may be envisioned imple­ menting hundreds to thousands of processors running on one optical computer.

This paper investigates two techniques for instruction scheduling, dynamic and static scheduling.A decoupled access/execute architecture consists of an execution unit and a memorv unit with seoarate nroeram counters and seuarate instiuction memoges.The v&y long instruction w&d (VLIW) architecture has only one program counter and relies on the compiler to perform stat& szheduling of multiple units.To idealize the comparison the VLIW architecture considered hsd only two units.The instruction sets and execution times for the two architectures were made as nearly the same as possible.The execution times were compared and analyzed to compare the capabilities of static and dynamic instruction scheduling.Both regular and irregular programs were constructed and optimized by hand for each architecture.The experiment showed that the two methods are nearly equally powerful.The decoupled architecture performed better on subroutine calls than the VLIW architecture.It also worked better on programs which switched from memory intensive to computation intensive code.The decouoled architecture wss zenerallv better at hidinn the floating point latency.Thcregist& sharing enable; the VLIW architecture to do more load balancing which resulted in shorter initialization times, and short& loop iteration times.

It is shown that a frame of N time slots can be arbitrarily permuted with 2log/sub 2/N-1 controlled exchange switches with associated delay elements. This is an improvement over previously known interconnection networks that require O(N) exchange elements. The proof utilizes the recursive algorithm of V.E. Benes (1965) and the time interchange properties of a particular configuration of a single exchange element. The architecture is especially applicable in optical systems, since optical exchange switches are among the simplest optical logic devices to build, are inherently very fast, and are the best developed, although expensive.>

The solution of a system of linear equations Ax = b is an important application in scientific computation. It arises for the numerical solution of self adjoint problems using finite difference or finite element methods for discretization. For realistic problems the coefficient matrix A is sparse most of the times, i.e. a large number of its elements are zero. The three commonly used classes of algorithms to solve the linear system of equations are direct methods, semi-iterative methods and iterative methods which differ in their numerical properties and their computer implementations. The multiprocessor L/U Decomposition for sparse systems was implemented by Gita Alaghband [Git85] as an example for a parallelized direct method. In this paper we will present examples for efficient parallelizations of iterative and semi-iterative algorithms and their implementations on various MIMD shared memory architectures. The iterative methods generate a sequence of approximate solutions which converge to the exact solution. To improve the rate of convergence the Multigrid approach [Hac80] is used as an accelerator. Semi-iterative methods operate in an iterative manner with the property of finite termination in exact arithmetic. The Conjugate Gradient methods shown in this paper are among the most popular representatives of this class of algorithms. They are usually not as robust as direct methods but there are computational advantages over methods that require the factorization of the coefficient matrix A.

A technique for combining produce and consume operations is proposed. An Omega network was designed to work with a pipelined micro multiprocessor system, and each of its nodes to be implemented on a single chip. Without a significant increase in hardware complexity, the nodes combine produce and consume messages in an unbounded way. The combining technique that was developed guarantees that every produce and consume message that is combined will always succeed, adding a new benefit to combining. Results of several simulation runs are presented.

It is shown that in sparse matrices arising from electronic circuits, it is possible to do computations on many diagonal elements simultaneously. A technique for obtaining an ordered compatible set directly from the ordered incompatible table is given. The ordering is based on the Markowitz number of the pivot candidates. This technique generates a set of compatible pivots with the property of generating few fills. A novel heuristic algorithm is presented that combines the idea of an order-compatible set with a limited binary tree search to generate several sets of compatible pivots in linear time. An elimination set for reducing the matrix is generated and selected on the basis of a minimum Markovitz sum number. The parallel pivoting technique presented is a stepwise algorithm and can be applied to any submatrix of the original matrix. Thus, it is not a preordering of the sparse matrix and is applied dynamically as the decomposition proceeds. Parameters are suggested to obtain a balance between parallelism and fill-ins. Results of applying the proposed algorithms on several large application matrices using the HEP multiprocessor are presented and analyzed.>

A pipelined implementation of MIMD operation is embodied in the HEP computer. This architectural concept should be carefully evaluated now that such a computer is available commercially. This paper studies the degree of utilization of pipelines in the MIMD environment. A detailed analysis of two extreme cases indicates that pipeline utilization is quite high. Although no direct comparisons are made with other computers, the low pipeline idle time in this machine indicates that this architectural technique may be more beneficial in an MIMD machine than in either SISD or SIMD machines.

Several languages have been developed for or applied to the problem of describing digital hardware systems. This paper points out some of the problems encountered in hardware descriptions, particularly where they are distinct from concepts appearing in programming languages.

A formula is found for the distribution of the number of ones in a subsequence of a maximal-length shift-register sequence. The formula relates the distribution to the binomial distribution with probability 1/2 with a difference that depends on the structure of the set of linear recurrences satisfied by the sequence. Considerations are discussed that aid in the choice of a shift register to be used in generating an approximately binomially distributed random variable.