Notes on SPMD architecture V

 Nodes' operation.

 

Seulement celui qui ne rame pas a le temps de faire vagues¹

Jean Paul Sartre

This post describes the internal operation of the nodes in the Architecture model.

--------------------

According to the composition of the nodes described in the post "Requirements" of this series, in addition to processor and memory devices, all the nodes have a communications' device that support the transfers among them (the bridge). Moreover, the input and output nodes have communications devices that support the transfers from the input link and to the output link, respectively (the input link communications device and the output link communications device).

In other words, for the input node, the input device is the input link communications device and the output device is the bridge device; for the processing nodes, input and output devices are the bridge; and for the output node, the input device is the bridge device and the output device is the output link communications device.

On the other hand, as it was previously advanced in the post "Data transferences" of this series, to allow the input and output of the node to work independently, both the input and the output must have their own memory buffers.

Taking also into account that the input device, the processor and the output device of the node work in pipeline, the functionality of a generic node can be depicted as shown in the figure below.

Figure 5-1

Additionally, input and output buffers support the fulfilling of the Architecture requirements of getting the maximum possible throughput from the MP machine and no-data-loss stated in "Requirements".

The requirement of getting the maximum possible throughput from the MP machine is fulfilled as the buffers allow the input device, processor, and output device to work independently.

The requirement of no-data-loss is fulfilled as the buffers allow that the node do not loss data during work peaks. Input buffers avoid the data-loss when the processor can’t process input data units at the rhythm required by the input device. Output buffers avoid the data-loss when the output device can’t send output data units at the rhythm required by the processor.

Moreover, input and output buffers also allows performing out-of-place processing into the nodes. In an in-place processing, the results obtained are stored in the data buffer. In an out-of-place processing, at least two buffers are necessary, one for the data to be processed and another one for the results. Following a zero-copy strategy, the processor uses input buffers for the data to be processed and output buffers for the processing results.

Let’s consider that the nodes operate in steady workload condition. In order to achieve maximum Throughput, as soon as the processor finishes the processing of a data unit, the next input data unit has to be ready in an input buffer and an empty output buffer has to be available. Than means that while the processor is processing, the input device has to receive data and to fill an input buffer and the output device has to send data and to empty an output buffer. If the nodes perform the processing in steady workload conditions over time, for overlapping the data reception, the data sending and the processing, two input buffers and two output buffers are necessary. Note that this number of buffers also fulfills the no-data-loss requirement.

If the nodes operate in non-steady workload condition, the number of input and output buffers required depends on the work peaks that the nodes have to deal with. This topic will be addressed later in this series. For the moment, we will just consider that the machine have enough buffers to work properly.

According to the above, the operation of the nodes is as follows:

• The input node stores continuously the data coming from the input link in the empty input buffer. The output node sends continuously the results of the processing from the full output buffer to the output link. 
• All the nodes start processing as soon as they have an input buffer filled with a new data block and a empty output buffer. They perform the processing using both buffers. At the end of the processing, the results will be in the output buffer. When a node finishes the processing, the input buffer is freed and the output buffer is transferred to an input buffer of the next corresponding node (input and processing nodes), or to the output link (output node). When the node finishes the transference, it frees the output buffer and goes for another input data block.

So, in order to support the nodes’ operation described above, the nodes’ devices work as follows:

• The input device accepts a new data block as long as there are input buffers available. When the transference of a data block is completed, the input device releases the control of the buffer to the Processor.
• The Processor starts processing as soon as it has an input buffer filled with a new data block and a empty output buffer. If there is no data block available, it waits for one. When the Processor completes the processing, frees the input buffer, releases the control of the output buffer to the output device and goes for a new data block to process.
• The output device tries to transfer output buffers as long there are output buffers pending. When the output device finishes a transference, releases the control of the output buffer to the Processor and the Processor frees it.

Note that both, the operation of the nodes and the operation of the devices of the nodes have been on purpose described without any reference to the type of transference. It is considered a matter of the software to offer a “neutral” interface that supports an homogeneous operation for all the types of transference.

In the writing of this article, the Escola de Gaitas de Ortigueira (A sanssonete & busildre reels. Festival Internacional do Mundo Celta, Ortigueira 2014) has collaborated in an involuntary but decisive way.

---------------------

1. Only the one who doesn't row has the time to rock the boat.
The original phrase of Mr. Sartre refers to the guy that doesn’t rows. For obvious reasons, I have chosen to adapt the quote.

2. Picture: riasbaixas.jpg, https://ribadeomuller.wordpress.com/2012/08/31/as-remeiras-galegas-estan-batallando-por-unha-nova-vitoria-na-v-bandeira-feminina-da-concha-2012/

3. I want to thank Carol G. for her revision of this text.