Paper Title: Fine-Grain Parralelism with Minimal Hardware Support: A Compiler-Controlled Threaded Abstract Machine

Threaded Abstract Machine

Fine-grain parallel tasks running on regular machines

David Culler (after he moved from MIT to Berkeley)

  • Need to coarse things up
  • Provide runtime/software layer

Problem

  • Fine grain parallelism without hardware support and performance as if HW support on a system with multiple CPUs
    • J-Machine : HW support is really necessary
    • TAM : Emulate (or avoid) HW support using SW
  • Hardware not flexible enough, cannot match SW needs precisely
  • Hardware has too narrow view
  • Register (memory hierarchy) too expensive (need for liveness support)
  • Reduce visible parallelism to desired level

Solution Uniqueness

  • Give compiler some responsibility over scheduling resources
  • Define a new execution model

Traditional Thread

  • Takes few miliseconds to launch
  • Control sequence of instructions
  • Lifetime of thread : creation, destruction, scheduling, context switching
  • Von Neumann context : PC (unique), set of registers (unique), memory (may be shared)

TAM Threads

  • Sequence of instructions between two any non-deterministic time or long latency instructions
  • 3–4 instructions in thread
  • Not long enough to justify software-only approach
    • Chain threads to each other (quantum)
    • Address stalls with inlets

Dynamic memory in TAM

  • Functional languages : for TAM to be useful, program needs to be written in functional language
    • Id90, Erlang, SQL, Amazon Lambda
  • I-structure
    • A way to know all dependencies
    • Each location can be written once but read multiple times
  • M-structure
    • Each location can be written and read once

Execution hierarchy Instruction < Thread < Frame < Quantum

Evaluation

  • Execution time comparison
    • Id90→TAM on uniprocessor : 6–10 time unit
    • C on uniprocessor : 1 time unit
    • LIPS on uniprocessor : 50–100 time unit
  • With TAM performance degradation from switching to dataflow is less
  • TAM was proposed to program multicomputers not uniprocessors. Therefore, it would have better performance compared to C and LIPS on such machines.
  • Instruction Count
    • #insts(TAM[TL0]) > #insts(TTDA)

Comparison of TAM and J-Machine

  • TAM was implemented using CM-5
  • CM-5 has pipeline and floating points therefore J-Machine is always expected to be slower than it.
  • In CM-5, message sizes are fixed
  • CM-5 has GAS just like J-Machine but lacks active messages, tagged memory and wake-up on write features.
  • Turns out initializing tags in J-Machine was expensive and unlike what assumed, access to multiple tags outweighs the benefit.
    • Tagged memory requires I or M structure.
    • Today we use locks, atomic instructions and transactional memory
  • Combining two approaches (J-Machine and TAM) would give the best benefit since not all features of two are required.

Conclusion

  • TAM showed that compiler interactions are very powerful.
  • Active messages concept lead to other research such as : Nomadic threads, Berkeley NOW, Split-C (splitting load and store)