Load distribution

• An idle PE tries to schedule a spark from its spark pool. If that spark is under evaluation by another PE or has already been evaluated (orphan) then the PE tries another spark (in FIFO). A useful spark is turned into a thread by allocating a fresh TSO and SO and starting to execute it.
• If no useful local sparks are available, the PE seeks work from other PEs. No PE is left idle while there are sparks waiting to be evaluated in other PE spark pools. A message passing mechanism using a sequence of FISH , SCHEDULE and ACK messages migrates unevaluated sparks between requesting and supplying PEs. A FISH message sent out by an idle PE looking for work, goes from one PE to another until work is found. To avoid swamping the system with too many circulating FISH messages, some kind of ageing mechanism that increments a count field in the message for each PE visited unsuccessfully is used. This is used to determine whether a previously set limit on the number of PEs that a FISH message is allowed to visit is reached. In that case, the last visited PE returns the message back to the PE that originated the message. Retransmission of the FISH message is allowed only after a certain delay interval. Also, one PE may have at any time at most one outstanding FISH message. If a PE that receives a FISH message has a useful spark, it sends a SCHEDULE message back to the originator of the FISH message. The SCHEDULE message contains the spark thunk packaged with ``nearby'' graph. The originating PE unpacks the graph and adds the newly acquired thunk into its local spark pool and sends ACK message to the sender of SCHEDULE . The spark may not be evaluated straightaway as the PE may no longer be idle, because it might have received a message unblocking some thread, in the meantime.