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. Runtime cost models are developed to give predictions of
the total execution time of algorithms. These cost models allow us to study the
runtime characteristics of algorithms and the impact of the computer
architecture on algorithm runtime. 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 lowlevel 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 nonlinear numerical
optimisation. These algorithms clearly illustrate the use of lowlevel
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.
These documents are in Adobe Acrobat format. You need to
download the free Acrobat
Reader to view and print them.
