Fine-grain parallelism with Minimal Hardware Support: A Compiler-Controlled Threaded Abstract Machine (TAM)

Problem:

  • The point of the paper is to expose more to the compiler to increase synchronization and control granularity. This is an opposite approach from WaveScalar
  • Dataflow execution model on a conventional architecture
  • Dataflow overview:
  1. No explicit ordering, just dependency graph
  2. Once inputs are ready, operation fires
  3. Loops in a dataflow graph create deadlock. This is fixed with tagging (i.e. warps)
  • Dataflow challenges:
  1. Locality
    • restrict parallelism to control locality
    • group threads into quantums to not execute concurrently
  2. Dynamic scheduling and evaluation of firings
    • fixed by coarsening control
  3. Synchronization
    • A naive implementation has to synchronize on each op

Dataflow has a problem of too much parallelism and it is difficult for HW to determining what needs to be local and what needs to be spilled out to memory. Programming system must be careful to not expose too much parallelism to the HW

The paper called the parallelism fine-grained because they started with fine-grained and used the scheduling hierarchy to group ops into sequential quanta.

Users:

  • Interpreted functional programs
  • No real user was specified, this was more of an experiment

Readers:

  • System designers: make better decisions on HW/SW partitioning for fine-grained parallelism support

Unique:

  1. Explicit compiler control over
    • Storage
    • Synchronization
    • Scheduling
    • Before this work, it was believed that these all need to be handled in HW to be efficient.
  2. How are storage, synchronization, and scheduling all related?
    • Need to make a scheduling decision when a running thread stops or is stalled. The latency is unpredictable.
      • Stalls: load, store (sometimes), some arithmetic, atomic ops/syncs, I/O
      • Go find another thread to run when stalled
    • May also make scheduling decision for fairness reasons
  3. Unique way threads become unstalled
    • Before TAM, HW needs to keep track of stalled threads and detect when dependencies are satisfied either through HW interlock or scanning through threads and hoping they are ready
    • TAM solves this using split-phase fetches and stores
      • When the thread hits a fetch, it is done and stops
      • When response arrives, it starts a new thread
      • Inlets:
        • spawn a new thread
        • Accept a value
        • Checks if the waiting thread is ready
        • A later paper compared TAM running on J-Machine to CM5. J-Machine handled inlets well, but had other limitations like small number of registers and lack of some control instructions
  4. HW multi-threading didn’t really exist at the time TAM was created
  5. Each thread has multiple inputs it has to wait for, not just the loads

Definitions:

Quanta - collection of threads that will be executed together

Activation - group of quantums, decided by the compiler.

Handling state in functional languages:

  • Pure functional languages don’t have state
  • I-Structures - array that maintains functional semantics
    • Array element has (value, ready)
    • Instead of doing a regular load from an array, load, check ready, and register a callback of not ready

Evaluation:

  1. Compared the TAM runtime vs C and Lisp on sequential machine
    • C was an order of magnitude better than Id
    • Id was an order of magnitude better than Lisp
    • Future evaluations did self comparisons on different machines, but there was no comparison to different languages on those machines.
    • Wrote algorithms in Id90 to expose a lot of parallelism
  2. Examined Dynamic Instruction Mix
    • Compared to instruction mix of explicitly dataflow machine
    • Authors tried to extract what the overhead was of their implementation running on a sequential machine.
    • Id has to execute 50% more instructions, but show they get a 10x speedup by adding HW
  3. Try to project what will happen on a parallel system
    • Show numbers for Quanta/Activation, Threads/Quanta, Instructions/Quanta
    • I/T - they have a small number of Instructions per Thread, so there is some overhead of the small threads since thread queue manipulation is not trivial
      • J-machine has some HW queue support
    • I/Q and T/Q - Reasonable and remained reasonable even with more processors. Means quanta scheduling overhead is amortized well across instructions

Summary:

  • Like the idea of exposing more scheduling to compiler to reduce the amount of synchronization required. Scheduling hierarchy can reduce the synchronization overhead, and some of the synchronization is removed by grouping instructions into threads
  • Scheduling storage: Within a quantum, you know what will be spilled. Registers can remain resident across threads.
  • Split fetch allows the system to handle network latencies while out-of-order processors only handle/hide latencies of L1 misses
  • This was a theoretical paper with interesting work, but not a final solution.