In this paper, we give an overview of the Cedar multiprocessor and present recent performance results. These include the performance of some computational kernels and the Perfect Benchmarks. We also present a methodology for judging parallel system performance and apply this methodology to Cedar, Cray YMP-8, and Thinking Machines CM-5.

The development of vector and multiprocessor language constructs in Fortran is outlined. The significant architectures, their languages, and optimizers are described. A description is given of Cedar Fortran, the language for the Cedar multiprocessor, a hierarchical, shared-memory, vector multiprocessor currently under development.>

In this paper, cache design is explored for large high-performance multiprocessors with hundreds or thousands of processors and memory modules interconnected by a pipe-lined multi-stage network. The majority of the multiprocessor cache studies in the literature exclusively focus on the issue of cache coherence enforcement. However, there are other characteristics unique to such multiprocessors which create an environment for cache performance that is very different from that of many uniprocessors.

When a large number of processors try to access a common variable, referred to as hot-spot accesses in [6], not only can the resulting memory contention seriously degrade performance, but it can also cause tree saturation in the interconnection network which blocks both hot and regular requests alike. It is shown in [6] that even if only a small percentage of all requests are to a hot-spot, these requests can cause very serious performances problems, and networks that do the necessary combining of requests are suggested to keep the interconnection network and memory contention from becoming a bottleneck.

Performance of a class of multistage interconnection networks employing redundant paths is investigated. Redundant path networks provide significant tolerance to faults at minimal costs; in this paper improvements in performance and very graceful degradation are also shown to result from the availability of redundant paths. A Markov model is introduced for the operation of these networks in the circuit-switched mode and is solved numerically to obtain the performance measures of interest. The structure of the networks that provide maximal performance is also characterized.

No abstract available.

We present an algorithm for solving banded positive defimte linear systems on a multiprocessor computer whose number of processors p is much less than the order of the system n.Assuming that the banded matrix, of bandwidth 2m + 1, is stored in the global memory by diagonals as several onedlmensmnal arrays, we consider the time required by several alignment networks for allocating the appropriate data to the local memory of each processor.We demonstrate that the time required in this preprocessmg stage does not exceed that required by the algorithm provided we use a shuffle exchange, a plpelmed shuffle exchange, or a crossbar switch.Once the data are allocated in the local memories, the algorithm requires only a "nearest neighbor" alignment network to achieve a total time of O(m'~n/p).The total cost of the algorithm is minimized when p ~ ~.

A general class of fault-tolerant multistage interconnection networks is presented, wherein fault-tolerance is achieved by providing multiple disjoint paths between every input and output. These networks are derived from the Omega networks and as such retain all the connection properties of the parent networks in the absence of faults. An R-path network in this class can tolerate (R-1) arbitrary faults in the intermediate stages of the network at a cost that is far less than providing R copies of the original network. Different techniques for constructing such networks are presented and relevant properties and control algorithms are investigated.

In this paper we describe a memory system designed for parallel array access. The system is based on the use of a prime nwnber of memories and a powerful combination of indexing hardware and data alignment switches. Particular emphasis is placed on the indexing equations and their implementation.

An algorithm is presented for a more efficient and implementable solution of triangular systems on a parallel (SIMD) computer which requires 0(log (N)) fewer processing cycles than the best previous results, where N is the system size. We will also show that the data can be accessed and aligned in the same order of time using as many memory units as processors and Ω networks for data alignment. (Previous results dealing with this type of algorithm have not dealt in any detail with the problem of data access and alignment.)

It is possible to improve the paging performance of a program by applying transformations to the source program that improve data access locality. We discuss this subject in general terms, including automation of these transformations, and present a number of such transforms. This is followed by experimental results which indicate that these transformations are indeed effective. Use of practical, simple memory management policies like the fixed allocation local lru replacement algorithm leads to average improvements over untransformed programs of a factor of 10 in space-time cost, and a factor of 5 in memory size. Multiprogramming questions are also discussed.

A π network, which is a concatenation of 2 Ω networks [2], along with a simple control algorithm is proposed. This network is capable of performing all Ω network realizable permutations and the bit-permute-complement (BPC) class of permutations[5] in 0(log N) time. The control algorithm is actually a multiple-pass control algorithm on the Ω network, which is more general than Pease's LU decomposition method [6] and Lenfant's decomposition method[4].

The purpose of this paper is to present some ideas on multiprocessor design and on automatic translation of sequential programs into parallel programs for multiprocessors. With respect to machine design, two subjects are discussed. First, a multiprocessor allowing parallelism at a very low level is sketched and then, a brief discussion on the interconnection network is presented.

The object of this paper is to bring together several models of interleaved or parallel memory systems and to expose some of the underlying assumptions about the address streams in each model. We derive the performance for each model, either analytically or by simulation, and discuss why it yields better or worse performance than other models (e.g., because of dependencies in the address stream or hardware queues, etc.). We also show that the performance of a properly designed system can be a linear rather than a square root function of the number of memories and processors.

This paper discusses the design of a primary memory system for an array processor which allows parallel, conflict-free access to various slices of data (e.g., rows, columns, diagonals, etc.), and subsequent alignment of these data for processing. Memory access requirements for an array processor are discussed in general terms and a set of common requirements are defined. The ability to meet these requirements is shown to depend on the number of independent memory units and on the mapping of the data in these memories. Next, the need to align these data for processing is demonstrated and various alignment requirements are defined. Hardware which can perform this alignment function is discussed, e.g., permutation, indexing, switching or sorting networks, and a network (the omega network) based on Stone's shuffle-exchange operation [1] is presented. Construction of this network is described and many of its useful properties are proven. Finally, as an example of these ideas, an array processor is shown which allows conflict-free access and alignment of rows, columns, diagonals, backward diagonals, and square blocks in row or column major order, as well as certain other special operations.