International Journal of High Speed Computing

The Fast Fourier Transform is a mainstay of certain numerical techniques for solving fluid dynamics problems. The Connection Machine CM-2 is the target for an investigation into the design of multidimensional SIMD parallel FFT algorithms for high performance. Critical algorithm design issues are discussed, necessary machine performance measurements are identified and made, and the performance of the developed FFT programs are measured. Our FFT programs are compared to the currently best Cray-2 FFT library program, CFFT2.

Four totally parallel algorithms for the solution of a sparse linear system have common characteristics which become quite apparent when they are implemented on a highly parallel hypercube such as the CM2. These four algorithms are Parallel Superconvergent Multigrid (PSMG) of Frederickson and McBryan, Robust Multigrid (RMG) of Hackbusch, the FFT based Spectral Algorithm, and Parallel Cyclic Reduction. In fact, all four can be formulated as particular cases of the same totally parallel multilevel algorithm, which we will refer to as TPMA. In certain cases the spectral radius of TPMA is zero, and it is recognized to be a direct algorithm. In many other cases the spectral radius, although not zero, is small enough that a single iteration per timestep keeps the local error within the required tolerance.

Matrix multiplication is a computation and communication intensive problem. Six parallel algorithms for matrix multiplication on the Connection Machine are presented and compared with respect to their performance and processor usage. For n by n matrices, the algorithms have theoretical running times of O(n² log n), O(n log n), O(n), and O(log n), and require n, n², n², and n³ processors, respectively. With careful attention to communication patterns, the theoretically predicted runtimes can indeed be achieved in practice. The parallel algorithms illustrate the tradeoffs between performance, communication cost, and processor usage.

This paper presents the results of the Connection Machine implementation of a number of preconditioners for the preconditioned conjugate gradient method. The preconditioners implemented include those based on the incomplete LU factorization, the modified incomplete LU factorization, the symmetric successive overrelaxation, and others such as several polynomial preconditioners and the hierarchical basis preconditioner. Results based on numerical experiments show that both the degree of parallelism inherent in a preconditioner and its convergence rate improvement play important roles on the overall execution time performance on parallel computers. Factors that affect the performance of the preconditioners will also be discussed. We conclude that to search for the best preconditioner on a parallel machine, we have to consider the tradeoffs between fast convergence rate and high degree of parallelism as well as the architecture of the target parallel computer.

This paper reports on our early experience with solving large scale finite element dynamic problems on the Connection Machine. We describe a distributed data structure that allows very efficient massively parallel computations on irregular two and three dimensional finite element meshes. The often encountered mesh irregularities inhibit the use of the NEWS communication package. We propose an alternative approach to interprocessor communication that is based on an optimal mapping of the processors onto the finite elements of the irregular mesh. Our parallel data structure and processor mapping are applied to finite element wave propagation problems on the CM-2.

We have implemented pure gauge Quantum Chromo-dynamics (QCD) on the massively-parallel Connection Machine, in *Lisp. We describe our program in some detail, and give performance measurements for it. With no tuning or optimization, the code runs at approximately 500 to 1000 Mflops on a 64K CM-2, depending on the VP ratio.

Two implementations of the molecular dynamics method on the Connection Machine are given demonstrating the advantage of using NEWS communication over the general router. Timing comparisons are also made with the Cray 2.

Supercomputers are coming into wider use for generating realistic imagery for commercial animation, special effects, and scientific simulation. The Connection Machine requires a more radical rethinking of rendering algorithms than previous supercomputers since it is not intended to function as a scalar processor. A fascinating mix of changes from conventional approaches is emerging. Some procedures can run virtually unchanged while others must be turned completely inside out. We have confidence in the viability of the Connection Machine as an architecture for high-end computer graphics. For complex scenes resulting in at least tens of thousands of polygons per frame, most steps of the rendering pipeline can make effective use of the massive number of processors available.

Early approaches to massively parallel graphics systems have focused on processor per pixel organizations. We show that a dynamic mix of organizations, including processor per pixel, processor per vertex, and processor per polygon are necessary. Additionally, we note that an apparent consequence of the style of algorithm enforced by the Connection Machine is an enormously increased appetite for memory. We explore standard algorithms for image generation and note the differences that arise in an implementation for the Connetion Machine. We conclude by attempting a comparison of the viability of alternative computing environments for our application.

The advent of the Connection Machine profoundly changes the world of supercomputers. Its highly nontraditional architecture makes possible the exploration of algorithms that were impractical for standard Von Neumann architectures. Kanerva’s sparse distributed memory (SDM) is an example of such an algorithm.

Sparse distributed memory is a particularly simple and elegant formulation for an associative memory. In this paper I describe the foundations for sparse distributed memory, and give some simple examples of using the memory. I continue by showing the relationship of sparse distributed memory to random-access memory. Finally, I discuss the implementation of the algorithm for sparse distributed memory on the Connection Machine.

We develop an analytical model of grid communication on the connection machine for arbitrary grid geometries over exact power-of-two distances. There is excellent agreement between the model and the measured performance of the CM2. We propose some conceptually simple enhancements to the virtual processor mechanism and to the grid communication microcode which could lead to substantial performance improvements for several important numerical algorithms.