J-machine

  • J(Jeally), meant to be constructed out of large-scale many cheap nodes.
  • many processors in a single computer.
  • working towards a single solution.
  • parallel computer system
  • multithreading

Purpose:

  • explore parallelism in applications.
  • enable fine-grained co-operation of processors.
  • general programming model.

History of parallel processing:

  • 50s and early 60s.
  • single program with ILP/ SIMD.
  • late 80s - MIMD
  • processors on single chip technology.
  • first terms- “massively parallel processing”

Parallel programming techniques:

  • SPMD- explicit message passing.
  • pipelining- workflows/streaming, generalized to graphs, form of dataflow.

Requirements of a parallel computing system:

  • communication
  • synchronization
  • naming: necessary for communication.

Mechanisms used by J-machine for the above:

  • namespace:
segmented global virtual address space.
physical locations
naming- nodes and local address within the node.
way to define translation between local and global address space- explicitly done by the programmer.
  • synchronization:
- wake-up on write.
- send message: event occurs when a message is received 
       - run the message handler (Explicit synchronization)  	 
       - control-based synchronization
- FIFO: 
- full-empty bit for each location. 
- rule: producer cannot read from empty location 
- consumer cannot write to a full location
- mutual exclusion- form of synchronization.  
- data/address based synchronization: write/read location from memory.
  • communication: cause the message to travel through the system.
- explicit messages (sends) : 
- remote procedure call (called active messages)
- data + handler (program counter corresponding to the handler code) + priority 
- hardware support: message queue, message handler.
- future wake-up: waking up threads when data is available.
- alternative: shared memory (implicit, not implemented by J-machine).
- access memory across global address space (GAS).

Implementation:

  • communication:
why hardware? 
- less context switches, less checking by OS for waiting for messages.  
- low overhead. 
- interrupts implemented instead.
  • network 
- network processing built into the ISA
- reduces overhead on send messages.
  • data tagging
metadata to indicate whether the data is valid or not.
why hardware? 
- need not be atomic 
- appropriate consistency model required in software.
- more overhead with software and polling.

Users:

  • parallel processing

Evaluation:

  • Prototype built. 
- Even today simulating machine consisting of 512 nodes is not easy (even just boot sequence!)
- At the time, cost of developing simulator would have been probably same as building prototype.
  • Network performance- latency, bandwidth. 
- Network must not slow down other processes. 
- Proves network is not the bottleneck.
  • Synchronization 
- Tagging vs non-tagging.
  • Didn’t compare with software.
  • Performance vs scaling of the code. 
- They justified curves with slope of less than one via limitations of network, especially with bisection bandwidth (worst-case bandwidth between parts of network divided to two equal sections)
- They observed superlinear speed-up for TSP which was caused by limited number of experiments. (Always average results from multiple runs for performance evaluation) (If you cannot repeat the experiment, at least build two sensors/monitors)
  • Verified the mechanisms to have lesser overhead.

Scaling problems

  • Weak scaling problem 
- Size of problem scales with machine
- Fixed time to solution for growing problems
  • Strong scaling problem 
- Fixed problem size with machine scale-up
- Faster solution for fixed problem

Identifying bottleneck

  • High network utilization, low CPU utilization => bandwidth-limited
  • Low network utilization, low CPU utilization => synchronization-limited

Thinking of J-Machine as research project

  • Architecture J-machine processor
  • Built processor
  • Designed and built board
  • Backplane
  • Chassis
  • Programs (assembly, tuned CST)
  • Compiler

Current systems similar to J-Machine

  • Xeon Phi
  • Sensor Networks
  • Warehouse-scale Computers

Mission of J-Machine

  • Providing vision into future.
  • Their vision did not came out.
  • Most of our applications today are not limited by communication or synchronization.
  • It turned out that software was good enough to implement all the mechanisms they manifested in J-Machine.