Abstract
The design of an efficient distributed memory transputer network is a difficult issue. In order to construct successfully highly concurrent systems with a large number of processors, their interconnection networks have to be as universal as possible and provide adequate connectivity for most applications. To satisfy these requirements, these communication networks should possess: an ease of expansion, a high bandwidth, a low latency, a deadlock freedom and an acceptable degree of reliability. This thesis presents a new type of interconnected network based on a multiple bus organisation and routing resources (gateways) that offers significant improvements in bandwidth over previously accepted bus-oriented topologies (i.e. multi-bus and spanning bus) and in latency over most directly-connected transputer networks (e.g. ring and mesh configurations). Besides, it has an easier expansion than hypercube-like structures. Relatively high bandwidth, low latency, good processor scalability, semi-adaptive routing and deadlock freedom are the fundamental features by which of our proposal contributes to the design of an efficient interconncetion network for transputers. They have been achieved by separating the routing (gateways) from the computational resources (processors). Although this topology can be exploited by general purpose parallel processors based on shared or distributed memory techniques, transputers and an OCCAM-like programming methodology have been considered as a case study in this project as it is the primary objective of the thesis. Simulation models and analytical results, mainly based on gap equations we have developed, exhibit conclusively the superior performance of our system compared to most transputer topologies. The detail of this architecture is presented in a design form that embodies many of the concepts discussed and proposed throughout the course of this research. As it is important to address uniquely each processor within the network, a dynamic address assignment algorithm that preserves the features of the proposed architecture is also suggested.