University of Surrey

Test tubes in the lab Research in the ATI Dance Research

The engineering of data structures.

Colbrook, Adrian. (1990) The engineering of data structures. Doctoral thesis, University of Surrey (United Kingdom)..

Available under License Creative Commons Attribution Non-commercial Share Alike.

Download (32MB) | Preview


Abstraction in computer programming provides a means of reducing complexity by emphasising the significant information (program behaviour) whilst suppressing the immaterial (program implementation). This aids program construction, improves reliability and maintainability, and eases the application of formal correctness proofs. The importance of data abstraction in the specification, design and implementation of large systems raises the question as to whether such methods may be applied in the context of programming languages designed before the widespread use of abstraction techniques. The program structuring facilities available in FORTRAN 77 support a form of encapsulation for simple data structures. In light of this mechanism provided by the language, state-based specification was found to be most appropriate. A specification technique incorporating object-oriented techniques is particularly suitable and allows a library of object classes to be specified and then implemented in sequential FORTRAN 77. Refinement extends the object classes so as to provide the commonly occurring generators for use in iterative constructs. Therefore, the advantages of data abstraction methods may be obtained in an early procedural language such as FORTRAN 77. Data abstraction provides data independence : a change in the representation for a particular class of objects affects only the code that implements the associated operations. This allows parallel implementations to be considered, without changes to the original specification or to any user-code. The provision of such parallel data structures is required for the migration of sequential systems onto parallel distributed memory architectures. As an illustration of this approach a general 2P2-2P (for integer P≥3) search tree utilising a pipeline of processors in a distributed memory architecture is shown to provide a means of implementing the object classes. Variations in both the number of processors allocated to the pipeline and the value of P allows the optimal search structure for a given architecture to be determined. These structures are highly efficient leading to improvements in both throughput and response time as processors are added to the array. An efficient parallel implementation of object classes is therefore achieved within the tight interface provided by abstraction.

Item Type: Thesis (Doctoral)
Divisions : Theses
Authors :
Colbrook, Adrian.
Date : 1990
Contributors :
Depositing User : EPrints Services
Date Deposited : 09 Nov 2017 12:15
Last Modified : 15 Mar 2018 17:20

Actions (login required)

View Item View Item


Downloads per month over past year

Information about this web site

© The University of Surrey, Guildford, Surrey, GU2 7XH, United Kingdom.
+44 (0)1483 300800