Interference among multiple vector streams that access memory concurrently is the major source of performance degradation in main memory of pipelined vector processors. While totally eliminating interference appears to be impossible, little is known on how to design a memory system that can reduce it. In this paper, we introduce a concept called memory access reordering for reducing interference. This technique reduces interference by means of making the multiple vector streams access memory in an orderly fashion. Effective algorithms for memory access reordering are presented and their efficient hardware implementations are described.>

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.

In this paper, we study prime-way inter leaved memory in the context of vector multiproces sor systems. Practical, efficient techniques for imple mentation of prime-way interleaved memory are pre sented. A method for minimizing access contention among multiple vector streams is described.

The problem of constructing an array processor with N processing elements, N memories, and an interconnection network which provides conflict-free access and alignment of various N-vectors including rows, columns, diagonals, contiguous blocks, and distributed blocks of N*N arrays, where N is any even power of two, is discussed. The use of linear skewing schemes offers no solution to this problem. The solution developed makes use of a nonlinear skewing scheme. The solution leads to a simple, efficient array processor architecture. In particular, the memory organization requires O(log N) gates to generate memory addresses for any of the N-vectors simultaneously in O(1) time. The interconnection structure is able to accomplish data alignment for any of the N-vectors with a single pass through a network of O(N log N) gates. As the system uses the minimum number of memories, it allows both processing elements and memories to achieve the highest utilization possible.>

Let T be a collection of data templates of an N ×N matrix, T = {row, column, forward diagonal, backward diagonal}.In the context of parallel processing, the question of whether it is possible or not for a parallel processor with N processing elements, N memory modules, and an interconnection network to allow parallel, conflict-free access to any instance of any data templates in T for N = 2" and any n > 1 has been open for a long time.The problem essentially concerns whether there exists any valid skewing scheme that can be realized in terms of interconnection networks.In this paper we will answer this open question by presenting a valid skewing scheme and a simple interconnection network that efficiently implements the skewing scheme in question.

A scrambled storage scheme is proposed for storage arrays of N*N elements in N=2/sup n/ parallel memory-modules to allow conflict-free access to various array partitions. It is shown that the scheme allows conflict-free access to rows, columns, square blocks, and distributed blocks of stored arrays. An alternative way of achieving the desired accessibility would use P. Budnik and D.J. Kuck's (1971) nonuniform skewed storage; in this case, addressing hardware would require O(n*2/sup n/) exclusive-OR circuits. The proposed scheme has, however, the advantage of simplifying address generation; addressing hardware requires n exclusive-OR circuits only. Some of the important questions of scrambling/unscrambling data through a proposed interconnection network are discussed.>

The problem of retrieving an ordered list of k words that satisfy a given search condition from an associative memory of m words of n bits each is addressed. A fast ordered retrieval algorithm is proposed, along with a logic design for a cellular associative memory which mechanizes the algorithm. The algorithm is of time complexity O(n+k). By contrast, the fastest previously known algorithms, by M.H. Lewis (see RCA Rev., vol.23, p.215-29 (1962)) and C.V. Ramamoorthy, J.L. Turner, and B.W. Wah (see ibid., vol.27, no.9, p.800-15 (1978)), are of time complexities O(k*log n) and O(k*n), respectively.>

A new scheme for constructing search algorithms for bit-parallel associative memories of m n-bit words is described. The resulting equivalence searches, threshold searches, and double-limit searches achieve the time bound of O(log n), compared to O(n), the recent result of Ramamoorthy et al. [12]. The extremum search algorithm by Frei and Goldberg [2] is modified and generalized so that the number of memory interrogations is reduced by 30 percent over the initial algorithm in the average case.