Unstructured Sparse Matrix Dense Vector Multiplication on the DAP

Lynne Marie Stockman (1990)
Master of Science Degree Project, Queen Mary, University of London

The DAP mentioned in the title and the abstract is the Applied Memory Technology Distributed Array Processor which is a massively parallel computer of single instruction multiple data (SIMD) architecture. The DAP 600 series machine which I used in my research had 4096 single-bit processing elements arranged in a 64 × 64 array, and was attached to a host computer, in this case a Digital Equipment Corporation VAX 8350. The host machine handled all input and output as well as data transfer to and from the DAP. The host programs were written in FORTRAN 77 and the DAP programs were written in FORTRAN-PLUS, a dialect of FORTRAN specific to the DAP.

Abstract

The development and ever-increasing use of parallel computers have forced programmers to re-examine even the most basic mathematical algorithms and computational techniques in order to efficiently adapt these procedures to new computer architectures. Matrix vector multiplication is a familiar algorithm and has been implemented successfully on a variety of parallel computers. However, sparse matrices, which are common in many application areas, can be difficult to deal with in parallel because of their packed storage representations. This paper examines sixteen unstructured sparse matrix dense vector multiplication algorithms, all specifically tailored to the DAP.