Assumption of non-multi threaded hardware for this paper

Problems

  • Context switching is hard
  • Synchronization is expensive
  • Compiler assumes worst case for resources/Latency
  • ILP limits
  • To get these things hardware is the limiting factor

Solution

  • Giving resources to the application its self
  • More app control over resources like
    • Execution
    • Storage
    • Synchronization
  • When we say app we may mean compiler
  • How to add this compiler control
    • Gave finer few instruction granularity for threads
  • New entity at compiler-lightweight thread of 10’s of instruction long
    • Leads to millions of threads
    • How in the world do you manage this?
    • Our current threads
      • DO loads stores complex things
    • Their threads
      • How to start and stop a thread?
      • Ending a thread is done by (We did not know this answer as a class)
        • OPTIONS to end thread
          • Any sync point stops a thread (This is done in TAM)
            • IMPORTANT: All regular threads die at a synch point and then new set of threads is kicked off
            • If thread wants to “continue” they have to be restarted
        • Control flow can stop a thread
        • Exceptions can stop a thread
        • Memory ops can stop a thread
          • ONLY loads
            • Loads can take a long time
            • Hide latency of load by context switch
            • To continue after load a NEW thread must be created
        • Arithmetic can stop a thread
    • Intents
      • Part of the thread. When all inlets are full the thread continues
    • Make threads atomic (uninterruptible) sets of instructions. (Excluding exceptions).
    • Memory is not inherently data flow (When it gets all its data it goes…)
      • I-structures try to make memory more data flowish
        • Data / ready&full bit
    • This paper wanted to have badly structured memory systems so the way they stop threads to allow the high latency loads complete stems from this
    • Led to interesting work later
      • Split-c
      • UPC
    • If you have these millions of threads how does software deal with them?
      • Only intervene after groups of threads
    • What do you need for a thread?
      • Reg
      • PC
      • Inlets ← space to drop flags
    • The Frame define reg/pc/inlet
      • Inlets done by a counter that just goes down till the thread can go
    • Scheduling
      • Activation - Tree of frames
        • Amount of storage you need
      • Quantum
        • Thread switching
        • List of threads that execute back to back
      • Frame
        • Have multiple threads
      • Scheduling and Storage
        • Anything I want to schedule must have storage available for it
        • The more storage structures live the more storage we need
        • Make sure storage is available for the amount of things that you have live
        • Thrashes the memory system if you have to many things that are trying to use too much of the storage at the same time
    • Threads are very fine grain but too hard to control so they add frame/quantum to lower the complexity of scheduling
    • Quantum is a set of frames that execute together when they all threads are ready to go.
  • Main reasons that to like the paper
    • You can do useful things out side of hardware

Users

  • Not said in the paper
  • Anyone who could use machine
  • ID language
    • Regular languages make this very hard
    • Allowed analysis they needed

Evaluation

  • C fast < TAM Medium < LISP Slow
    • They were somewhere in between a “real” language
  • Had to compile to ld/TL0 and then to C
  • Dealing with multithreaded things in 1991… Pretty early on
  • KEY POINT: Overheads of the processing stop increasing and parallelism increases so eventually they get to be better
  • I.e. we are adding things but the additions are reasonable. Their code is also parallizable.

Jmachine (next paper) is more hardware specific implementation of this.