Hardware architecture is described for RADCAP, the operational associative array processor (AP) facility installed at Rome Air Development Center (RADC), N.Y. Basically, this facility consists of Goodyear Aerospace STARAN parallel processor and various peripheral devices interfaced with a Honeywell Information Systems (HIS) 645 sequential computer, which runs under the Multics time-shared operating system. The hardware of STARAN/RADCAP is described with particular emphasis on the parallel processing elements.

Four SIMD multistage networks—Feng's data manipulator, STARAN flip network, omega network, and indirect binary n-cube—are analyzed. Three parameters—topology, interchange box, and control structure—are defined. It is shown that the latter three networks use equivalent topologies and differences in their capabilities result from the other parameters. An augmented data manipulator network using a modified control structure to perform more single pass interconnections than the other networks is presented. Some problems may be solved more efficiently if the 2n processing elements of an SIMD machine can be partitioned into submachines of size 2r. Single and multiple control partitioning are defined. The capabilities of these multistage networks to perform in these partioned environments are discussed.

This paper proposes a solution to air traffic control (ATC) using an enhanced SIMD machine model called an Associative Processor (AP). This differs from previous ATC systems that are designed for MIMD computers and have a great deal of difficulty meeting the predictability requirements for ATC, which are critical for meeting the strict certification standards required for safety critical software components. The proposed AP solution will support accurate and meaningful predictions of worst case execution times and will guarantee all deadlines are met. Also, the software will be much simpler and smaller in size than the current corresponding ATC software. An important consequence of these features is that the V&V (Validation and Verification) process will be considerably simpler than for current ATC software. Additionally, the associative processor is enhanced SIMD hardware and is considerably cheaper and simpler than the MIMD hardware currently used to support ATC. The ClearSpeed CSX600 accelerator is used to emulate the AP model. A preliminary implementation of the proposed method has been developed. Experimental results comparing MIMD and CSX600 approaches are presented, and show that our solution can guarantee 8 real-time ATC tasks to be finished within their hard deadlines for a large scale of aircraft. The performance of CSX600 has better scalability, efficiency, and predictability than that of MIMD.

Transcribed from an after-dinner talk given by Dr. Ken Batcher, Goodyear Aerospace Corporation, on September 24, 1986.

The flip network in each array module of STARAN scrambles and unscrambles multidimensional access (MDA) memory data. The flip network can permute data on transfers from memory to PE's (processing elements), from PE's to memory, and from PE's to PE's. Among the allowable permutations are barrel shifts, barrel shifts on substrings, and FFT-butterflies. The network can be used for such data manipulations as shifting, mirroring (flipping end-for-end), irregular spreading, or compressing and replicating. These manipulators are useful for sorting, fast Fourier transforms, image warping, and solving partial differential equations on multi-mesh regions.