The data structure used for the database is the same as for the sequential algorithm, except that each processor contains only a part of the entire array. An element of a buffer represents one update message and specifies the address of a parent entry and the final value of the child that is sending the message. Each processor contains one input buffer containing messages sent to it and one output buffer for every other processor.
Every processor uses two threads.
A worker thread performs the actual computations. Whenever this thread has determined the final value for an entry, it generates messages for the parents of this entry and stores them in the appropriate output buffers. A second thread, the communication thread repeatedly copies messages from these buffers over the network to the input buffers of other processors, where they will be picked up by the worker threads. The overall structure of the parallel algorithm is illustrated in Figure 1 . It processes the messages in the input buffer.