Lecture 9 ( 10/01/2007) --- Dataflow: Passing the Token

()

Introduction

  • The performance of large scale multiprocessor systems have been limited by the fundamental principles of the von Neumann architecture. Dataflow architectures, which directly use the dataflow graph, are an alternative to the von Neumann architecture and potentially provide better scaling.
  • Guest lecture given by Derek Chiou (slides)

Background

  • Dataflow architectures were inspired by Jack Dennis in the 1970s & 1980s.
  • Two types of Dataflow Machines:
    • Static - mostly for signal processing (not general-purpose enough)
    • Dynamic (as easy to build as a simple pipelined processor)
  • Software Influences
    • Parallel Compilers
    • Functional Languages
    • Active Messages (David Culler)
    • Compiling for FPGAs (Bohm, Goldstein)
    • Synchronous Dataflow (Lustre, Signal)

Dataflow Graphs (DFG)

  • DFGs are a graphical representation of data dependencies between operations.
    • Values in the DFG are represented as tokens: <ip, p, v>
      • ip = instruction pointer
      • p = port
      • v = data
    • DFGs allow us to exploit much more parallelism compared to a standard superscalar machine. Very elegant way to express parallelism.
  • Dataflow Operators
    • An operator executes when all input tokens present (no separate control flow)
    • Only a small set of operators are needed:
  • Well Behaved Schemas
    • one-in-one-out & self cleaning: Don’t leave tokens unconsumed!
    • need way of limiting too much parallelism: Bounded Loop

Static Dataflow Machines

  • Instruction Templates
    • Each arch in DFG has a operand slot in the program. See following diagram (table based on DFG in previous section):
  • Example of a Static Dataflow Machine (Jack Dennis, 1973):
  • Problems/Limitations
    • Not very general-purpose.
    • Mismatch between model & implemenation
    • Cannot support: Function Calls, Data Structures

Dynamic Dataflow Machines

  • Instructions templates (a frame) dynamically for each loop iteration and procedure call
    • To support this, context information needs to be added to the token (called the frame pointer): <fp, ip, port, data>
      • fp = frame pointer
      • ip = instruction pointer
      • p = port
      • v = data
  • An example frame in a dynamic dataflow machine:
  • Only need to provide storage for one operand/operator
  • Need valid bit for destination (highlighted in yellow)
  • Frame needs to be as big as the amount of parallelism we can exploit in one cycle!

Example: Monsoon Dataflow Machine

  • Instructions directly control the pipeline
    • Opcode specifies an operation for each pipeline stage
    • Easy to implement, no hazard detection!
  • Procedure Linkage Operators
    • Extract tag from F
    • Change tag = old frame ptr to new frame ptr

Software View

  • Parallel Language Model
  • I-structures
    • You do not want memory that you can write multiple times → introduce Id (I-structures)
    • Write-once, Read multiple times
    • Not a problem if a reader arrives before the writer at the memory location

Locality in Dataflow Machines

  • How do you deal with Locality in Dataflow Machines?
    • Make sure you have enough bandwith to memory
    • No coherency problem since write-once
    • Simpler to add caches to heirarchy
  • Dataflow designed to work without locality!!!