Dataflow Architectures

Citation: Arvind, David E. Culler (1986/02/12) Dataflow Architectures. Annual Reviews of Computer Science, 1986 (RSS)
Internet Archive Scholar (search for fulltext): Dataflow Architectures
Download: http://csg.csail.mit.edu/pubs/memos/Memo-261-1/Memo-261-2.pdf
Tagged: Computer Science (RSS) computer architecture (RSS)

Summary

This work presents solutions to token storage mechanisms and data-structures for dataflow architectures. This work also presents an overview of contemporary dataflow projects.

Theoretical and Practical Relevance

Dataflow architectures never caught on explicitly, but many of the concepts live on in Tomasulo's algorithm. They may see a resurgence in the TRIPS processor and in the work of Karthikeyan Sankaralingam.

Dataflow architectures

• Basic concept
• Permits parallelism with determinacy
• Need switch and merge for loops.
• How to implement apply? Should computational graph be dynamic?

Token storage mechanisms

• Static dataflow: Fixed number of tokens per edge.
  • How to maintain fixed-number? Need ack back-edge, saying if there is room.
    • This increases token traffic by a factor of 2, less if you can prove some back-edges are redundant.
• Dynamic dataflow (aka tagged-token dataflow): Unbounded number of tokens at each edge
  • Tokens must still "pair up" for binary operators; tag tells you which operand this one "pairs with".
  • Can use tags as memory address.

Data structures

• Functional data-structures
  • Operations have to be immutable (not "in-place")
• I-structures
  • Strict operators: evaluate arguments before evaluating function
  • Non-strict operators: can evaluate function before, after, or parallel to arguments.
    • Implementation: tokens can be futures.

Current (in 1980's) dataflow projects

• Static Dataflow
  • The MIT Static Machine Dataflow Project
  • The NEC Dataflow Machines
• Tagged-Token Dataflow
  • The Manchester Dataflow Project
  • Sigma-1 at Electrotechnical Laboratory, Japan

Prognosis

• Future research directions: demand-driven evaluation, controlled program unfolding, deadlock avoidance, efficient procedure invocation, storage reclamation, parallel reduction architectures, network design/topology, semantics of languages with I-structures
• Comparison to von Neumann:
  • In dataflow, need complex circuit to say what function to dispatch; In von Neumann, it's just the $pc+1 instruction.
  • This is why von Neumann usually does more instructions per time. Does that mean von Neumann machines are faster?
  • Dataflow can be faster for multicore, where memory latency is high; Dataflow can extract ILP more easily.