A dynamic two-stage Delta network (N inputs and outputs) is introduced and analyzed for permutation routing. The notion of evil twins is introduced and a deterministic procedure is given to route any permutation in no more than 2/sup 4//spl radic/N network cycles. Two limited randomized routing schemes are then analyzed. The first called Single Randomization yields on average at most N!+1 (N!=O(logN/loglogN)/sup 1/ and is the greatest integer such that (N!)!/spl les/N) network cycles and the second called Multiple Randomization yields on average at most upper bound [log(logN+1)]+2+1/N network cycles for any input permutation. The probability of any permutation requiring at least c network cycles more than the above average bounds is then shown to be at most 1/(c+1) for Single Randomization and 1/N/sup r/ for Multiple Randomization, respectively. It is then shown how the dynamic two-stage network can be physically realized as a three-stage network. Both the evil twin and Multiple Randomization algorithms have been integrated into an off-the-shelf ASIC from PMC-Sierra, Inc. (PM-73488) which has been designed as a building block for such a three-stage implementation. These routing schemes are also adapted to run on a recirculating network. Recirculation is used to effect a reshuffling of data as in the dynamic network, but with a considerable reduction in network cost.

We analyze a generalization of the traditional delta network, dubbed Expanded Delta Network (EDN), which provides multiple paths that can be exploited to reduce contention. In massively parallel SIMD computers, the trend is to put a large number of processors on a chip, but due to I/O constraints only a subset of the processors may have access to the network at any time. This leads to the Restricted Access Expanded Delta Network of which the MasPar MP-1 router network is an example.

A simple but powerful architecture based on the classical associative processor model is proposed. By distributing logic among slices of storage cells such that a number of bit-planes share a simple logic unit, bit-parallel arithmetic for massively parallel processing becomes feasible. For m-bit operands, this architecture enables complex operations such as multiplication and division to execute in O(m) cycles as opposed to O(m/sup 2/) for bit-serial machines. Algorithms which utilize this bit-parallel property to efficiently perform operations on floating point data have been developed. The simplicity of the architecture enables its implementation using VLSI technology, and hence allows the construction of a word-parallel, bit-parallel, massively parallel (P/sup 3/) computing system. Implementations of the fast Fourier transform and matrix multiplication are presented to illustrate the operation of this system.>