Contents

• Contents
• List of Figures
• List of Tables
• Introduction
  • Contributions of the Research
  • Benefits of Scheduled Routing
    • Cycle Speed
    • Hotspot Avoidance
    • In-Router Algorithms
    • Stream Prioritization
    • Header Traffic
    • Non-Cartesian Networks
    • Faulty Networks
    • Multiple Applications
  • Drawbacks to Scheduled Routing
  • Scheduled Routing
    • Scheduling Virtual Finite State Machines
    • Flow Control in Scheduled Routing
    • Router Reprogramming
    • Other Characteristics of Scheduled Routing
  • Thesis Outline
• The Communications Language
  • Motivation
  • Expressing Communications as Operators
  • Supporting Phases
    • Choosing Optimal Phase Boundaries
    • Expressing Time
  • Grouping Operators Together
    • Multiple Operators
    • Continuing Operators
    • Multiple Threads of Control
  • Communicating in Subsets of the Mesh
  • Expressing Run-Time Values
    • Constraining Run-Time Values
  • Computational Model
    • The I/O Functions
    • The Load Function
    • COP/HLL Integration Example
  • Extensibility
  • Example COP Code
  • COP Language Design Issues
    • Message Streaming
    • Exposing I/O Wait Time
    • Hidden State
    • Loop and Branch Prediction
    • Schedule Generation
    • Message Passing or Shared Memory?
  • Summary
• Related Work
  • Communication Languages
    • The Gabriel Project
    • OREGAMI/LaRCS
    • The PCS Tool Chain
    • The CrOS Project
    • Chaos and PARTI
    • Other Communication Languages
  • Scheduled Routing Architectures
    • iWarp
    • GF11
  • Scheduled Communication
    • Agrawal-Shukla
    • Bianchini-Shen
    • Other Scheduling Work
• Managing Data Dependency
  • Operator Implementations
    • Approaches to Data Dependency
      • Pure Compile-Time
      • Multiple Path Allocation$\dagger$
      • Output Discarding
      • Dynamic Destination Selection$\dagger$
      • Multiple Schedules$\dagger$
      • Run-Time Specification
      • Run-Time Operator-Specific Scheduling$\dagger$
      • General Run-Time Scheduling$\dagger$
      • Processor Intervention
      • Online Routing
    • Implementation Types
      • Dynamic-Routing Implementations
      • Stream-Alias Implementations
      • Schedule-Generator Implementations
      • Replacement Implementations
    • Meta-Implementations
  • Online Scheduled Routing
    • Implementation
    • Resource Allocation
    • Future Extensions
• Managing Multiple Phases
  • Continuing Operators
    • Simple Continuation
    • Continuation to Multiple Phases
    • Continuing Online-Routing Operators
  • Changing Phases
    • Operator Termination
      • Message-Bound Implementations
      • Processor-Bound Implementations
    • Determining Which Operators are Terminating
      • Optional Operators
      • Deriving `Terminating' and `Last' Status
    • Barriers for Phase Termination
      • Message-Bound Synchronization
      • Hijack Synchronization
      • Explicit Barrier Synchronization
      • Local Synchronization
    • Alternate Subset Specifiers
  • Inter-Phase Wire Constraints
    • Finding `Live' Communications Edges
    • Allowing Write Reuse with Barriers
    • Other Wire-Reuse Considerations
    • Dependency Analysis to Minimize `Live' Edges
      • Creating the Dependency Graph
      • Computing Wire-Reuse Dependency
  • Managing a Scheduled Router as a Cache
    • Caching for Router Schedules
    • Caching for Router VFSMs
    • Runtime Cache Management
  • Finding Load Operators
    • Choosing a Load Operator for a Phase
    • Associating Multiple Phases with a Load Function
• The Compiler Search Engine
  • Multiple Threads of Control with Scheduled Routing
    • Restricting the Set of Nodes for Routing
    • Deriving Spatial Extent Information
    • Restructuring COP Parallelism with Spatial Extents
      • Restructuring Parallel Groups
      • Restructuring Sequential Groups
    • Sequential Descendants of Parallel Groups
  • Searching the Implementation Space
    • The Search Model
    • Structuring the Phase Tree
      • Sequential and Parallel Groups
      • Disjoint Groups
    • Picking Implementations for Phases
    • Closing a Phase
    • Computing Timings for an Implementation Set
      • Computing I/O Time
      • Computing Phase-Change Timings
      • Computing Router-Loading Time
    • A Cost Metric for Stream Bandwidths
  • Stream Routing
    • Basic Stream Router Interface
    • Stream Router Cost Function
• Back-End Implementations
  • Scheduled-Routing Backend
    • The NuMesh Hardware
      • Pipeline Stages
      • Processor Interface
      • VFSM Scheduling
      • Reprogramming
      • Data-Transfer Restrictions
      • NuMesh Topology
    • NuMesh Phase-Changing Restrictions
    • The NuMesh Stream Router
    • Cost Function Constraints for NuMesh
      • Processor-Interface Access
      • MEMADR Access
      • Co-Scheduling Streams
    • NuMesh Caching Restrictions
  • Dynamic-Routing Backend
    • Disambiguating Messages
    • Dependency Analysis for Interface Address Allocation
    • Supporting Virtual Interface Addresses
• Results
  • Experimental Methodology
    • Compilation
    • Simulation
    • Data Collection
  • Communication Kernels
    • Hotspot Avoidance: Results
      • Transpose
      • Bitreverse
    • In-Router Algorithms: Results
  • Data-Dependent Communications Techniques
    • Latency
    • Bandwidth
    • Online Scheduled Routing
  • Application Benchmarks
    • Matrix Multiplication
    • Gaussian Elimination
• Conclusions
  • Managing Multiple Phases
    • Continuing Operators
    • Changing Phases
    • Inter-Phase Wire Constraints
    • Managing a Scheduled Router as a Cache
    • Finding Load Operators
    • Results
  • Managing Data Dependency
    • Operator Implementations
    • Online Scheduled Routing
    • Results
  • The Compiler Search Engine
    • Multiple Threads of Control
    • Searching the Implementation Space
    • Stream Routing
    • Back Ends
  • COP
    • Communication Languages
    • High-Level Operators
    • Abstract Operator Sequencing
    • Run-Time Values
  • Future Work
    • Dynamic-Routing Support
    • Schedule Length Selection
    • Operators and Implementations
    • Language Features
• COP
  • Primitive COP Operators
  • Compound COP Operators
  • Optional Operator Arguments
  • (runtime)
  • COP Grouping Constructs
  • Predefined COP Variables and Functions
  • COP Extensibility
    • Lisp Implementations
    • C Implementations
  • Sample COP Idioms
• Operator Implementations
  • Implementations
    • broadcast
    • collect
    • reduce, prefix
    • barrier
    • cshift, eoshift, permute
    • stream, seqread, seqwrite
  • Generating Reduction Trees
• References