Performance enhancement of architectures with Random Access List Structured Memory

The work presented in this thesis investigates how existing and future computer architectures can be enhanced to exploit the potential of Random Access List Structured Memory. While most existing memory architectures can only offer a limited choice of possible data access mechanisms, Random Access List Structured Memory, as a new memory architecture, offers good support in both numerical and symbolic computing. A fast random access mechanism allows the manipulation of data elements stored in array structures, while the dimensions of these arrays can be dynamically modified. At the same time array elements can hold different data types and therefore allow the user to store complex data structures on the basic array structure. This way of expressing complex data structures as arrays can be used to avoid the use of conventional linked lists and their insufficient random access facilities. The regular data structure of the arrays used in this memory concept offers new, elegant, ways to structure the data of common applications and should simplify many algorithms manipulating other large data structures. Any CPU designed to operate on a Random Access List Structured Memory architecture needs to achieve good results when manipulating individual data elements of these structures. However a general purpose processor can not be expected to achieve an optimal performance when manipulating large complex data structures. The requirement for high system performance, in a system architecture using complex list manipulations on a frequent basis, provided the motivation to investigate the potential of co-processors for these list manipulations. A useful co-processor has to support the large variety of complex list manipulations, required for different fields of application. To meet this demand, a co-processor design using a micro-programmable instruction set is suggested. The large number of supported manipulations does not contradict with a specialised co-processor as long as the algorithms are closely related. The development of such a co-processor is reported in this thesis. Starting with an explanation of the Random Access List Structured Memory concept, and the way it can be used in a computer architecture, the nature of complex list manipulations is explained. It is then indicated how a co-processor can be used to accelerate complex list manipulations as well as communication and memory management tasks. These general concepts are then applied to the tree shaped concept of Random Access List Structured Memory used in the experimental SPRINT architecture. Various hardware alternatives for the integration of such a co-processor, operating on Random Access List Structured Memory, are considered. A design study for a basic co-processor architecture following these ideas is performed, applying a newly developed database method. This study includes the simulation of algorithms and co-processor hardware at various abstraction levels. The simulation results are then used to evaluate the performance advantages of the co-processor