On vector supercomputers, vector register processors share a global highly interleaved memory. In order to optimize memory throughput, a single-instruction, multiple-data (SIMD) synchronization mode may be used on vector sections. We present an interleaved parallel scheme (IPS). Using IPS ensures an equitable distribution of elements on a highly interleaved memory for a wide range of vector strides. Access to memory may be organized in such a way that conflicts are avoided on memory and on the interconnection network.>

Using a prime number of N of memory banks on a vector processor allows a conflict-free access for any slice of N consecutive elements of a vector stored with a stride not multiple of N.

On many commercial supercomputers, several vector register processors share a global highly interleaved memory in a MIMD mode. When all the processors are working on a single vector loop, a significant part of the potential memory throughput may be wasted due to the asynchronism of the processors.

Selection of elements and alignment of operands are fundamental operations on data, just as are arithmetic operations. Whereas sophisticated algorithms have been devised for the latter, vector processors usually lack a flexible and efficient routing unit. This is especially true of SIMD computers, to which the present study is devoted. Examples of required manipulations are: transfer, shift, diffusion, compression, expansion, mesh, perfect shuffle, and bit reversal. Using a method described in a previous paper of ours [15] we present algorithms to control a Benes network and perform these manipulations on vectors whose length is equal to the number of processing elements. Then we dispense with this constraint and propose a mechanism to rearrange vectors of any size, stored according to several schemes.

The Benes binary network can realize any one-to-one mapping of its 2ninlets onto its 2noutlets. Several authors have proposed algorithms which compute control patterns for this network from any bijection assignment. However, these algorithms are both time-consuming and space-consuming. In order to meet the time constraints arising from the use of a Benes network as the alignment network of a parallel computer, another approach must be chosen. In this paper, we consider typical functions and show that the set of needed permutations of data is very small, as compared to the whole symmetric group. We gather frequently used bijections into five families. For each family we present an algorithm that can control the two-state switches on the fly, as the vector of data passes through the network. Finally, we describe one possible scheme to implement an instruction "Trigger a Frequently Used Bijection."

Aho and Ullman have proposed an access mechanism for dynamic memories by which each item of a block after the first two can be accessed in a single step. Recently, this organization has been enhanced by Stone, whose memory scheme allows, on the average, random access in 1.5 log2 n steps; whereas, in the case of a sequential access, a single step is required for each item after the first. However, both methods can only be used for memories of size n = 2k - 1. We generalize Stone's technique in order to eliminate this severe restriction. The very large number of solutions that can be obtained for each memory size implies that an optimization procedure is valuable if the cost constraints of a particular implementation are known.

The allocation of the central processing unit (CPU) of a computer system in quanta of fixed length in round-robin fashion favors jobs with shorter total CPU processing time by reducing the time they spend waiting in queue below what it would be if all the lobs were served in first-come-first-served order This effect can be accentuated by the use of short quanta. The main disadvantage of this allocation policy is the resulting time the CPU spends in overhead activities when switching from one task to the other, this too will increase with smaller quanta. Thus, it appears useful to consider adaptive CPU allocation policies to reduce the overhead during high traffic conditions when saturation of this resource is more likely while keeping a small quantum during periods of low arrival traffic. In this paper we analyse such a policy, it is assumed that each time at least r (a threshold) arrivals occur during a quantum, the job currently using the CPU is allocated an additional quantum (if It is needed). Thus, the number of job arrivals during a quantum is used as a sensor of the intensity of arrival traffic. This policy, which can be easily implemented in hardware, is analysed using a mathematical model yielding the average response time for jobs as a function of mean total CPU time, the quantum size, r, and a fixed overhead for switching tasks, with a Poisson arrival process. Numerical results to illustrate the effect of this policy are presented.

Due to the practical complexity of addressing variable length records placed in arbitrary locations of a fixed-head disk (or drum), and because of difficulty of managing secondary memory space in such cases, variable length records are often stored with their first address at a fixed location of the magnetic support. We present a queuing model of such a scheme, assuming a Poisson arrival stream and arbitrary distributed record lengths. The stationary probability distribution of the number of transfer requests in queue and the expected response time are obtained. Numerical examples illustrating the results are presented.