The MASC (Multiple Associative Computing) model is a generalized associative-style computational model that naturally supports massive data-parallelism and also control-parallelism. A wide range of applications has been developed on this model. Recent research has compared its power to the power of other popular parallel models such as the PRAM and MMB models using simulations. However, the simulation of MMB has identified some important issues regarding the cost of certain basic MASC operations required for associative computing such as broadcasts, reductions, and associative searches. This paper investigates these issues and gives background information and an analysis of timings for these operations, based on implementation techniques and comparison fairness with respect to other models. It aims to provide justification and clarify arguments on the timings for these constant-time or nearly constant-time basic MASC operations.

This paper presents bitonic sorting schemes for special-purpose parallel architectures such as sorting networks and for general-purpose parallel architectures such as SIMD and/or MIMD computers. First, bitonic sorting algorithms for shared-memory SIMD and/or MIMD computers are developed. Shared-memory accesses through the interconnection network of shared memory SIMD and/or MIMD computers can be very time consuming. A scheme is introduced which reduces the number of such accesses. This scheme is based on the parity strategy which is the main idea of the paper. By reducing the communication through the network, a performance improvement is achieved. Second, a recirculating bitonic sorting network is presented, which is composed of one level of N/2 comparators plus an /spl Omega/-network of (log N-1) switch levels. This network reduces the cost complexity to O(N log N) compared with the O(N log/sup 2/ N) of the original bitonic sorting network, while preserving the same time complexity. Finally, a simplified multistage bitonic sorting network, is presented. For simplifying the interlevel wiring, the parity strategy is used, so N/2 keys are wired straight through the network.

A multiway merge sorting network is presented, which generalizes the technique used in the odd-even merge sorting network. The merging network described here is composed of m k-way mergers and a combining network. It arranges k ordered lists of length n each into one ordered lists in T(k)+[log/sub 2/k] [log/sub 2/m] [log/sub 2/m] steps, where T(k) is the number of steps needed to sort k keys in order; and k and m are any integers no longer restricted to 2.>

Bitonic sorters sort a single bitonic sequence into an ascending sequence. A multi-bitonic sorter is presented here, which sorts k bitonic sequences of n keys each into an ascending sequence in at most \left( {\left\lceil {\log _2 \left( {k + \left\lceil {\frac{k} {2}} \right\rceil } \right)} \right\rceil + 1} \right)\left( {\left\lceil {\log _2 n} \right\rceil - 1} \right)+T(1,k)+\left\lceil {\log _2 k} \right\rceil +1 time delay, where T(1,k) is the time delay needed to sort k keys in order; and k is any integer not restricted to 1.

Generalized cube networks are limited to single-fault tolerance with respect to permutation connections. The vector space approach presented here yields many fault-tolerance schemes that can tolerate two and three faults. In each scheme, redundant switches and links are added to networks and interconnected in certain ways. These redundancies are represented by a matrix called the redundancy matrix. A fault-free network without redundancy is represented by an identity matrix. As faulty switches and links are discovered, the remaining switches and links are remapped to establish an intact network. The remapping is analogous to converting an invertible redundancy matrix back to an identity matrix.>

Bitonic sorting networks can be implemented with a bit-level cost complexity of O(N log^2 N) using comparators with bit-level O(1) time and cost complexities. Items to be sorted are pipelined (worm-hole routed) bit-serially most-significant-bit first through the network. The cost complexity can be reduced to O(N log N) by recirculating items of length O(logN) through logN stages.

The bitonic sorting network will sort N-2^m keys in O(log^2N) time with 0(Nlog^2N) comparators. Developments on the sorter enable the network to sort N-pq keys, a composite number. However, there has been no general method for sorting a bitonic sequence of N keys, N a prime, or N a composite that decomposes into primes larger than 3. The oddmerge method removes this constraint while maintaining the same cost and delay, using a uniform and efficient decomposition.

About a decade ago, a bit-serial parallel processing system STARAN®1 was developed. It used standard integrated circuits that were available at that time. Now, with the availability of VLSI, a much greater processing capability can be packed in a unit volume. This has led to the recent development of two bit-serial parallel processing systems: an airborne associative processor and a ground based massively parallel processor.

The massively parallel processor (MPP) system is designed to process satellite imagery at high rates. A large number (16 384) of processing elements (PE's) are configured in a square array. For optimum performance on operands of arbitrary length, processing is performed in a bit-serial manner. On 8-bit integer data, addition can occur at 6553 million operations per second (MOPS) and multiplication at 1861 MOPS. On 32-bit floating-point data, addition can occur at 430 MOPS and multiplication at 216 MOPS.

STARAN® has a number of array modules, each with a multidimensional access (MDA) memory. The implementation of this memory with random-access memory (RAM) chips is described. Because data can be accessed in either the word direction or the bit-slice direction, associative processing is possible without the need for costly, custom-made logic-in-memory chips.