Lecture 6 Notes - WaveScalar (part 2)

See part 1 for introduction to WaveScalar.

()

General problems being solved

  • Increased scalability using completely distributed architecture
  • Performance should be similar or better than traditional superscalar (e.g. parallel out-of-order execution of sequential source code)
  • Source level compatibility, maintains existing programming models

Solutions to problems

  • Dataflow architecture
    • Maintain total memory ordering
    • Distributed tag management
    • Indirect branching
  • Store buffer
    • Generates memory ordering
    • Compiler forms chains of operations based on program order, and hardware ensures the ordering provided by the compiler
  • Branching (ø−1)
    • Instructions for both paths brought onto processor, but only one side is executed
  • Waves
    • Essentially hyperblocks (single entry, multiple exit, no loops)
    • Scheduled/allocated based on resource constraints (e.g. memory buffer)

WaveCache

WaveCache is an implementation of the WaveScalar ISA.

  • Arranged into grid of processing elements (PEs)
  • PEs are grouped into clusters (16 PEs/cluster in paper)
  • Each PE contains storage for instructions, input/output queues, ALU, control logic, and interconnect
  • Instructions are bound to PE, and fire when operands are ready
    • No traditional fetch/decode/writeback stages, no program counter
  • When no more space in WaveCache, instructions must be thrown out to bring in new instructions
    • Everything must be spilled - operands, condition codes, etc., thus slow and heavyweight
  • Waves assigned to clusters statically
  • Instructions from different waves can execute simultaneously if there are no dependencies, but must complete in-order
    • If wave has load/store, the ordering must be maintained, so cannot advance to next wave until everything before is done
  • Interrupts are not precise
    • Can run interrupt handler, but cannot stop currently executing program
    • To provide precise exceptions, program must check explicitly for interrupts in order to stop

Evaluation

  • Ignored communication costs, used perfect L1, ignored spills/fills
    • Unconvincing, because original claims were to reduce communication costs, increase locality, but in evaluation, these factors were ignored
  • Used subset of SPEC benchmarks
    • Couldn’t compile some programs
    • Many benchmarks are those that are generally parallel, and not necessarily the more difficult sequential programs.
  • Used aggressive 16-wide superscalar for comparison; didn’t talk much about WaveCache architecture
  • Used Alpha-equivalent IPC (i.e. only instructions in original binary are counted)

Misc

  • Information on traditional dataflow architectures
    • Yuba, et. al, The SIGMA-1 Dataflow Computer, Proceedings of the 1987 Fall Joint Computer Conference on Exploring technology: today and tomorrow, p.578–585, 1987.
    • Dennis, J.B., Data Flow Computer Architecture, Technical Report, Laboratory for Computer Science, MIT, TR-385 Oct., 1987.
  • Perfect branch prediction and memory disambiguation
    • Helped performance when enabled, but didn’t explain why
  • Debugging
    • Programs difficult to debug on WaveScalar. However, if programs worked correctly (i.e. already debugged) on superscalar, it should also work on WaveScalar
  • Parallelism in dataflow machines
    • Sometimes, there is too much parallelism, which requires too much state to be stored
    • Needs to be managed and limited (e.g. by memory)
  • Unique ideas, but evaluation did not prove usefulness
    • Decentralized, partitioned architecture
    • Statically determined data flow