from the city of Vienna: Notes for a multiprocessor skeleton IV

Channels.

Il progresso... Sempre tardi arriva!¹

Alfredo (Cinema Paradiso)

This post provides a high-level description of the different types of Channels required for the Skeleton. These Channels support the Data transferences required for the Architecture model described in “Notes on SPMD architecture” series. The Data transferences required for the Architecture model are described in the post "Data transferences" of that series.

The Channels were previously introduced in the post “Introduction“ of this series. The simple SPMD topology with Data redistribution capability presented there in Figure 1-1, is included below for consistency (see Figure 4-1).

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

The Skeleton has to support the transfers needed by the application. These transfers are performed through channels. The channels are software objects managed by the nodes’ software. They support unidirectional transferences of data blocks from the source node/s to the destination node/s. As mentioned in "Introduction", the channel’s library is either supplied, recommended or supported by the MP machine provider.

Processors, bridge devices (bridges) and memories of the source and destination nodes are involved in the transfer of data. For the transference to be performed in the more convenient way in the different cases addressed in “Data transferences”, the management of the transference may vary in different aspects. These aspects are implemented by means of parameters and are described below.

As a software object, the channel encapsulates the necessary code to perform the transference offering an interface similar to that of a First-In-First-Out (FIFO) queue of buffers. A FIFO is managed by means of two operations, one to enqueue (insert) a buffer (put(buffer)) and the other to dequeue (extract) a buffer (get(buffer)).

On the other hand, a channel is defined in the nodes it connects. In the source node/s is defined the source endpoint/s of the channel and in the destination node/s, the destination endpoint/s.

Let us consider that the channels internally manage the pools of empty and full buffers used for the data transfer. As stated throughout the “Notes on SPMD architecture” series, each pool must have a minimum number of buffers. Pools of buffers are required at both endpoints, source, and destination. These pools of buffers are organized as FIFOs, and hereinafter referred as the e-queue (empty buffers queue) and the f-queue (full buffers queue).

Note that both, the e-queue and the f-queue can be considered as parts of a single pipe. Initially, the pipe consists only of empty buffers. Over time, buffers are first getting filled and then emptied, but the total number of buffers remains constant. As stated in "Requirements", that number has to be calculated to get the maximum Throughput from the machine and guarantee no-data-loss. Anyway, for the sake of clarity, we will continue referring to the e-queue and the f-queue as single FIFOs.

The total number of buffers, as well as its size, are parameters that characterize a channel.

At the source endpoint, the processor uses the e-queue to get buffers to be filled with a data block, and the f-queue to pass the data blocks to be transmitted to the bridge. At the destination endpoint, the processor uses the e-queue to provide the bridge with memory buffers that will be used in the reception of data blocks, and the f-queue to get the received data blocks from the bridge.

As stated in “Requirements”, the channels support a flow control mechanism at data block level in order to guarantee no-data-loss. This means that the transference starts when the f-queue in the source node and the e-queue in the destination nodes are not empty.

Depending on the endpoint that starts the transference we will consider two types of channels, push and pull. In the push channels, the data transfer is started by the source node, and in the pull channels by the destination node.

The operations put(buffer) and get(buffer) work in different way depending on whether the channel is push or pull and the endpoint where they are executed.

In a push channel,

In the source node, get(buffer) is used to dequeue a buffer from the e-queue and put(buffer) to queue a buffer in the f-queue.
In the destination node, get(buffer) is used to dequeue a buffer from the f-queue and put(buffer) to queue a buffer in the e-queue.

In a pull channel,

In the destination node, get(buffer) is used to dequeue a buffer from the f-queue and put(buffer) to queue a buffer in the e-queue.
In the source node, get(buffer) is used to dequeue a buffer from the e-queue and put(buffer) to queue a buffer in the f-queue.

In the source endpoint of the channel, a transfer is blocking when the software, after starting the transfer, waits for the data block transmission to be completed in order to continue. In the destination endpoint of the channel, a transfer is blocking when the software waits for the data block reception to be completed in order to continue.

The choice of the blocking or non-blocking transference option for the channels depends on the operation expected for the machine is in steady or non-steady workload (see Appendix “Nodes’ workload over time”, “Notes on SPMD architecture” series). Certainly, in steady workload non-blocking operation does not contribute with any advantage, and conversely, it can make the debugging more difficult. However, in non-steady workload, non-blocking operation can help to clear the f-queues to the minimum level as fast as possible.

In “Data transferences”, the following types of data transfers among nodes were identified

Data distribution, which are the transfers from the input node to the processing nodes.
Data collection, which are the transfers from the processing nodes to the output node.
Data redistribution, which are the transfers among the processing nodes.

Following, different types of channels are defined for each type of transference.

In Figure 4-1, the Data distribution channel is represented by the straight arrows that connect the input node and the processing nodes, the Data collection channel by the straight arrows that connect the processing nodes and the output node, and the Data redistribution channel by the gray curved arrow that connect the output and the input of the processing nodes (note that the source nodes set and the destination nodes set are the same).

Figure 4-1

So, the Data distribution channel consists of one source endpoint and many (N) destination endpoints, the Data collection channel of many (N) source endpoints and one destination endpoint and the Data redistribution channel of many (N) source endpoints and many (N) destination endpoints.

The definition of the source and destination endpoints includes the identification of the source and destination nodes, respectively. This means, that depending on the type of channel, the following information must be specified:

Data distribution channel, the source node and the destination nodes’ set
Data collection channel, the source nodes’ set and the destination node
Data redistribution channel, the source nodes’ set and the destination nodes’ set

A nodes’ set definition includes both the number of nodes that comprise it and the identification of each one of said nodes. The order in which the nodes are defined determines the sequence for the rotatory arbitration mechanisms.

In the Data distribution channel, a rotatory arbitration mechanism decides to which destination node the input node transfers the current data block. Similarly, in the Data collection channel, a rotatory arbitration mechanism decides which source node will transfer the current data block to the output node.

We will consider that the Data distribution channel is a channel type push and the Data collection channel is a channel type pull.

The Data redistribution channel supports the transposition of the distributed matrix taking into account its dimensions and the number of processing nodes. As it will be seen below, this channel is built using Data distribution channels.

The following figure illustrates the distributed matrix transposition as described in “Data transferences”. Processing node n_pi (i=1,…,N) holds –before the Corner Turn– the submatrices A_i1,A_i2,..,A_iN, and after the Corner Turn the submatrices A^T_i1,A^T_i2,...,A^T_iN.

Figure 4-2

The distributed matrix transposition consists on two operations. The submatrices transposition and the submatrices transferences.

As said in “Data transferences”, the submatrices transposition can be performed both in the source nodes or in the destination nodes. In addition, this transposition can be performed by the processor or by the bridge.

Regarding the submatrices transferences, every source node n_pi (i=1,…,N) transfers every submatrix to the corresponding destination node using a Data distribution channel type push. This Data distribution channel makes use of a two-steps arbitration mechanism. In the first step, the rule “first come, first served” is used. Potential conflicts are solved in the second step using the original sequential rotatory mechanism afore described for the input node.

According to this, note that the transferences will begin as soon as an output buffer is ready but the destination buffers will not be completed until the transfers from the last source node are performed.

So, if the buffer has to be managed as a vector or a matrix, and in this last case, the dimensions of the whole distributed matrix, are also parameters characteristics of a channel.