Wright, Patrick John; (1994) Optimised Redundant Cell Collection for Graph Reduction. Doctoral thesis (Ph.D), UCL (University College London).

Text Optimised_redundant_cell_colle.pdf Download (32MB)

Abstract

Parallel processing offers a route to more powerful computation, but many problems have arisen on the path to the realisation of practical implementations of such architectures. One of the most important stumbling blocks in preventing parallel processors reaching widespread commercial fruition, is the problem of programming. Standard procedural languages, even when modified, offer an inadequate programming paradigm for such machines. A promising technique, combining the power of parallel processing with the software advantages of functional programming, is graph reduction. In the development of reduction architectures designed for functional programming, one of the most important implementation issues, affecting operational efficiency, is that of garbage collection. Of the three main methods of collection available, the most promising appears to be reference counting. This, however, suffers from a number of drawbacks: it involves a large memory overhead to support the scheme, it will not intrinsically deal with self-referencing (cyclic) structures and it is not real time in nature. The thesis starts with a short historical perspective on parallel processing, briefly presenting some of the major milestones in parallel architecture research. The discussion continues by introducing functional languages and the problems raised by garbage collection. The major garbage collection techniques are discussed and the reasons for exploring reference counting are explained. The first aspect of reference counting collection to be addressed is the memory overhead. An architecture for alleviating this problem is presented, based upon limited-width reference count fields. The chapter concludes with analysis of the new techniques and contrasts the worst case performance against the standard methods. A short chapter then introduces real time systems, with particular reference to functional programming and the attempts to make standard garbage collection techniques suitable for real time systems. The discussion continues with a novel technique for the collection of large redundant data structures in real time. A system is then discussed for implementing the collection of redundant cyclic structures, within the graph, in real time. As each aspect of the technique is explored, algorithms are presented. The thesis continues by presenting a worse case temporal analysis of the major services offered by the collector to a graph mutator. A formal verification of the basic real time collector, using the MALvern Program Analysis Suite (MALPAS) is presented. A simulator for the system has been written, which was used to test the techniques developed and to ascertain if the theoretical predictions are valid. This software implementation of the collector is described and some of the results obtained are presented and discussed. The performance of the new reference counting techniques are compared with an implementation of Baker's algorithm. The thesis concludes with a critical appraisal of the work carried out, and a discussion of how the research could progress, to realise a practical collector in a viable commercial parallel graph reduction machine.

Download activity - last month

Export as CSVXMLJSON

Download activity - last 12 months

Export as CSVXMLJSON

Downloads by country - last 12 months

Export as CSVXMLJSON

Archive Staff Only

View Item