An Architecture for Parallel Symbolic Processing Based on Suspending Construction

Copyright (C) 1995 Eric R. Jeschke

To Charmaine
 

Contents

• Abstract
• Acknowledgements
• 1. Introduction
  • 1.1 Overview of the Dissertation
  • 1.2 Parallel Symbolic Processing
  • 1.3 Suspending Construction
    • 1.3.1 A Concurrent Computation Model
    • 1.3.2 Suspensions and Evaluation Semantics
    • 1.3.3 Side-effects and Parallelism
    • 1.3.4 Identifying Parallelism
    • 1.3.5 A Cost Analysis of Suspending Construction
  • 1.4 History of the Daisy/DSI Project
• 2. A Primer
  • 2.1 Virtual Machine Issues
  • 2.2 Kernel Issues
    • 2.2.1 Memory Management
    • 2.2.2 Process Management
    • 2.2.3 Device Management
  • 2.3 Daisy
    • 2.3.1 Syntax
      • 2.3.1.1 Special Forms
      • 2.3.1.2 An Example
    • 2.3.2 Semantics
    • 2.3.3 Annotation
• 3. Architecture of the DSI Machine
  • 3.1 Memory Interface
    • 3.1.1 Tags and Types
  • 3.2 Processor State
  • 3.3 Instruction Set
  • 3.4 Signals
    • 3.4.1 Signal Routing
    • 3.4.2 Per-process Signals
  • 3.5 Interconnection Topology
    • 3.5.1 LiMP
    • 3.5.2 The BBN Butterfly Architecture
  • 3.6 Summary
• 4. The DSI Kernel
  • 4.1 Resource Management in Symbolic Programs
  • 4.2 Kernel Structure
    • 4.2.1 Monolithic vs. Micro Kernel
    • 4.2.2 Distributed vs. Non-Distributed
    • 4.2.3 Kernel Organization
  • 4.3 The Kernel Interface
    • 4.3.1 Message Requests
      • 4.3.1.1 Implementation
    • 4.3.2 Traps
    • 4.3.3 Interruption
  • 4.4 Summary
• 5. Memory Management
  • 5.1 Memory Organization
  • 5.2 Storage Allocation
    • 5.2.1 Data Distribution
    • 5.2.2 Load Balancing
      • 5.2.2.1 Considerations for Load Balancing
    • 5.2.3 Locality
  • 5.3 Storage Reclamation
    • 5.3.1 Garbage Collection
      • 5.3.1.1 Initialization
      • 5.3.1.2 The Mark Phase
      • 5.3.1.3 The Compaction Phase
      • 5.3.1.4 The Update Phase
      • 5.3.1.5 Cleaning Up
    • 5.3.2 Minor Phases
    • 5.3.3 Garbage Collection: Observations
  • 5.4 Summary
• 6. Process Management
  • 6.1 The Process Life Cycle
  • 6.2 Interprocess Synchronization
  • 6.3 Tracking Dependences
    • 6.3.1 Distributed Demand-Driven Scheduling
  • 6.4 Creating Parallelism
  • 6.5 Static vs. Dynamic Parallelism
  • 6.6 Controlling Parallelism
  • 6.7 Conservative vs. Speculative Parallelism
    • 6.7.1 Managing Speculative Computation
    • 6.7.2 Demand Coefficients
  • 6.8 Sharing and Cycles
    • 6.8.1 Embedding Dependences
    • 6.8.2 Cycles
  • 6.9 Increasing Granularity
• 7. Device Management
  • 7.1 The DSI I/O Model
  • 7.2 Device Drivers
  • 7.3 Input Devices
    • 7.3.1 The Device Manager
    • 7.3.2 I/O Signals
    • 7.3.3 Garbage Collecting Devices
    • 7.3.4 Flavors of Input Devices
      • 7.3.4.1 Disk Input
      • 7.3.4.2 Keyboard Input
  • 7.4 Output Devices
    • 7.4.1 Flavors of Output Devices
      • 7.4.1.1 Disk Output
      • 7.4.1.2 Terminal Output
    • 7.4.2 Output Driven Computation
  • 7.5 Bidirectional Devices
    • 7.5.0.1 Sockets
    • 7.5.0.2 Unix Pipes
  • 7.6 Limitations of 's I/O Model
    • 7.6.1 Interleaved Terminal I/O
    • 7.6.2 Non-Character Mode Devices
    • 7.6.3 Stateful Devices
• 8. An Analysis of Daisy
  • 8.1 Demand Driven Computation
  • 8.2 Limitations of Suspending Construction
  • 8.3 Excessive Laziness
    • 8.3.1 Bounded Eagerness
    • 8.3.2 Granularity Revisited
    • 8.3.3 Strictness Analysis
  • 8.4 Program Annotations
• 9. Conclusion
  • 9.1 Summary of Results
    • 9.1.1 Implementation Notes
  • 9.2 Future Work
    • 9.2.1 Incremental Enhancements
      • 9.2.1.1 Storage Management
      • 9.2.1.2 Global Namespaces
      • 9.2.1.3 User-Defined Exceptions
    • 9.2.2 Implementing Other Languages
      • 9.2.2.1 Scheme
      • 9.2.2.2 Communicating Sequential Processes
  • 9.3 Related work
    • 9.3.1 Parallel Functional Languages
    • 9.3.2 General-Purpose Symbolic Processing Kernels
      • 9.3.2.1 STING
      • 9.3.2.2 The Chare Kernel
    • 9.3.3 Parallel Lisp
      • 9.3.3.1 Multilisp
      • 9.3.3.2 MultiScheme
      • 9.3.3.3 Mul-T
      • 9.3.3.4 QLisp
      • 9.3.3.5 Butterfly Portable Standard Lisp
    • 9.3.4 Parallel Lisp: Summary
      • 9.3.4.1 Machine Design
      • 9.3.4.2 Kernel Design
      • 9.3.4.3 Distributed Allocation
      • 9.3.4.4 Load Balancing
      • 9.3.4.5 Process Management
      • 9.3.4.6 Speculative Computation
      • 9.3.4.7 Parallel I/O
  • 9.4 Conclusion
• Bibliography
• Index
• About this document ...