International Journal of High Speed Computing

Two new parallel integer sorting algorithms, queue-sort and barrel-sort, are presented and analyzed in detail. These algorithms do not have optimal parallel complexity, yet they show very good performance in practice. Queue-sort is designed for fine-scale parallel architectures which allow the queueing of multiple messages to the same destination. Barrel-sort is designed for medium-scale parallel architectures with a high message passing overhead. The performance results from the implementation of queue-sort on a Connection Machine CM-2 and barrel-sort on a 128 processor iPSC/860 are given. The two implementations are found to be comparable in performance but not as good as a fully vectorized bucket sort on the Cray YMP.

The CM-2 is an example of a connection machine. The strengths and problems of this implementation are considered. Important issues in the architecture and programming environment of connection machines in general are discussed. These are contrasted with the same issues in MIMD multiprocessors and multicomputers.

In this paper we present a comprehensive analysis of the performance of a variety of sparse Cholesky factorization methods on hierarchical-memory machines. We investigate methods that vary along two different axes. Along the first axis, we consider three different high-level approaches to sparse factorization: left-looking, right-looking and multifrontal. Along the second axis, we consider the implementation of each of these high-level approaches using different sets of primitives. The primitives vary based on the structures they manipulate. One important structure in sparse Cholesky factorization is a single column of the matrix. We first consider primitives that manipulate single columns. These are the most commonly used primitives for expressing the sparse Cholesky computation. Another important structure is the supernode, a set of columns with identical non-zero structures. We consider sets of primitives that exploit the supernodal structure of the matrix to varying degrees. We find that primitives that manipulate larger structures greatly increase the amount of exploitable data reuse, thus leading to dramatically higher performance on hierarchical-memory machines. We observe performance increases of two to three times when comparing methods based on primitives that make extensive use of the supernodal structure to methods based on primitives that manipulate columns. We also find that the overall approach (left-looking, right-looking, or multifrontal) is less important for performance than the particular set of primitives used to implement the approach.

With the increasing availability of multiprocessor platforms based on different types of architectures (shared memory, distributed memory, network based), users will be increasingly faced with heterogeneous and distributed multiprocessor computing facilities. Programming environment concepts have to be found which enable the user to program and use these heterogeneous computing resources, consisting of different multiprocessor architectures, in a transparent manner. Topics which have to be addressed and tools which have to be developed are parallel programming models, monitoring systems, debuggers, performance analyzers, animation systems and dynamic load-balancing schemes. The paper describes the integrated tool environment TOPSYS (TOols for Parallel SYStems), available for the iPSC/2 and iPSC/860 hypercube, as well as its adaptation to a network of UNIX-based workstations.

The problem of preemptive scheduling a set of periodic tasks on multiprocessors is studied from the point of view of meeting their service requirements before their respective deadlines. Sufficient conditions which permit full utilization of the multiprocessor using the given scheduling algorithms are derived. The complexity of the scheduling algorithms in terms of the number of scheduled tasks and the number of processors and upper bounds on the number of preemptions in a given time interval and for any single task are also derived. We also give a schema for modifying existing schedules at little run-time cost when tasks arrive or leave the system on-line.

We describe APE-100, a SIMD, modular parallel processor architecture for large scale scientific computation. The largest configuration that will be implemented in the present design will deliver a peak speed of 100 Gflops. This performance is, for instance, required for high precision computations in Quantum Chromo Dynamics, for which APE-100 is very well suited.