Vectored updates in the Glasgow Parallel Haskell Implementation

[Haskell List Moderator]

[Forwarded from Haskell list]

I have got a rather special question about the implementation of
Glasgow Parallel Haskell (GPH). GPH uses the `par` operator to
specify expressions which can be evaluated in parallel by another
processing element. Closures representing such an expression are
shipped on demand to a processor looking for work. The remote
processor evaluates the received closure and transmits the result
back to the sender or to any processor which demands this result.

GPH is based on the Spineless Tagless G-Machine (STGM). This abstract
machine uses a rather sophisticated mechanism to pass results of
evaluations to the calling function. The caller pushes a
return-(continuation-) frame to the control stack and enters the
callee. When the callee reaches whnf it passes the result to the
topmost return-frame on the stack and the caller can continue its
computation. One of the efficient features of the STGM is the
handling of updates in the same way as returns. When a closure needs
to be updated with a result an update-frame is placed on the stack.
Update- and return-frames have the same interface for the callee. So
the callee does not need to distinguish the type of the continuation.
It simply enters the topmost frame.

This mechanism uses, depending on the type of the result, different
return conventions. In many cases the vectored return is the most
efficient convention. If it is used, the frames on the stack contain
a vector of continuations; one for each possible constructor of the
result type. The callee simply uses an index in this vector. As a
consequence, an update-frame needs to know the type of the closure to
be updated. But this condition is not always satisfied. In the case
of polymorphic updatable closures the type is not known when the
update-frame is pushed onto the stack. This problem is solved by the
STGM by using special generic update-frames, which defer the update
until the next return-frame is entered. Since they are only created
by case-expressions, return-frames always know the type of the
returned value.

After this long introduction my question:
Suppose a polymorphic closure is evaluated in parallel by another
processing element. If the resulting type is a type which uses a
vectored return, the remote processor needs to know this type in
order to send a result back or  store it for later demands from other
processors. The trick from the sequential STGM does not work, since
there is no return-frame on the remote processor.

The only solution for this problem I can imagine, is to store the
index and a complete copy of all registers and pass this data back to
all processors which demand the value. A processor which demands the
value has a return-frame and therefore knows about the type. But this
solution has at least two drawbacks. A complete copy of all registers
is rather big and influences the garbage collection by producing a
lot of live cells.

Can anybody explain how this problem is solved in the GPH
implementation?


Matthias Horn