Contents

• Contents
• Introduction
  • Recursive Functions
  • Distributed Recursive Datatypes
    • Aliases
    • Mapping
  • Aims
• Describing Structures
  • Introduction
  • Recursive Pointer Based Data Structures
    • Nested recursive structures
    • Sharing nodes
    • Structures considered
  • Example Structures
• Naming the Nodes
  • Introduction
  • An example
  • The Problem
  • Normalised Paths
    • The Algorithm
  • Correctness Proof
• Mapping Nodes to Processors
  • Introduction
  • The Issues
    • Locality
    • Fair Division
    • Parallelism
  • The Mapping System
  • The allocation algorithm
    • Tree-like
  • List-like
  • With commuting directions
  • Example
  • Pseudocode for mapping function
  • Pseudocode for `Estimate Range' function
• Implementation on the Cray T3D
  • Introduction
  • The Implementation
  • The user interface to the library
    • The Data class
    • Describing the structure
    • The main Dtype Structure
  • The Dist class
• Analysis of Method
  • Introduction
  • Redundancy in a Data type
  • Predicting the amount of parallelism in the evaluation
• Experimental Results
  • The Example
    • Running the implementation
    • Running without exploiting commutativity
• Conclusions
  • Further work
• References
• Code Listings