PhD Thesis:

The design of numerical algorithms for Transputer systems

July 1993

It may amuse you to look at my PhD thesis.

The abstract is as follows:

This thesis discusses techniques for the design and implementation of parallel numerical algorithms for distributed memory MIMD architectures. The algorithms are targeted at machines based on the INMOS transputer family of microprocessors which include the T4, T8 and T9000 processors. We investigate how features of each member of the transputer family affect the design of numerical algorithms. Run-time cost models are developed to give predictions of the total execution time of algorithms. These cost models allow us to study the run-time characteristics of algorithms and the impact of the computer architecture on algorithm run-time. occam implementations of algorithms are developed and their performance is compared with the predictions given by the cost models to see how much credence can be given to the models. The algorithms are designed for both efficiency and portability between a wide range of distributed memory MIMD architectures. The cost models can help to estimate the performance of an algorithm on a different distributed memory architecture and on future generations of machines.

The portability of algorithms is maximised by the use of modular programming. Algorithms use low-level library routines for communications and computation. These routines are optimised for each target architecture to achieve reasonable performance for the complete algorithm.

Algorithms from a wide range of numerical programming fields have been investigated. Each area highlights different techniques that can be employed in the design of good parallel algorithms. In linear algebra we look at the Gaussian elimination algorithm. This algorithm is very important and illustrates many techniques applicable to parallel linear algebra algorithms. Another very important field is sorting. Designing good parallel sorting algorithms is very difficult because of the low computation cost compared with data size. Finally, we look at two algorithms from non-linear numerical optimisation. These algorithms clearly illustrate the use of low-level communications and computation routines to achieve portable and efficient algorithms. They indicate the way in which larger, more complicated programs may be developed from simpler, existing routines thus reducing software development time.

The Design of Numerical Algorithms for Transputer Systems
PhD thesis.
Tim Oliver. July 1993.

Get Acrobat Reader These documents are in Adobe Acrobat format.
You need to download the free Acrobat Reader to view and print them.

Last updated May 26, 2004
Copyright © Tim Oliver. All rights reserved.