Parallel Programming In C. Chap. V

Parallel Programming in C for the Transputer
© D. Thiébaut, 1995

5-6 Virtual Channels

We now take a look at one of the most powerful and useful features implemented by Logical Systems C: virtual channels. This feature appeared with version 91.1 of LS C, and bridges the gap between the older generation of transputers (T2XX, T4XX, and T8XX) and the newer generation of the T9000 series.

Virtual channels, as the name indicates, are channels, and they can be used the same way hard and soft channels are. This means that virtual channels can link tasks residing on the same transputer, or on different transputers. But the main difference, and this is where the power resides, is in their ability to connect transputers that may not necessarily be neighbors. Figure 5-6 illustrates these similarities and differences. In cases (a) and (b), the virtual channel acts exactly the same as the soft and hard channels, but, you may notice that the arrows on the virtual channels are directed both ways. This is the first important difference:

Rule 1
Virtual channels are full duplex
The virtual channels are full duplex channels, allowing the flow of information in both directions, at the same time.

Figure 5-6: Hard, soft and virtual channels. (a) A virtual channel can be used just as a soft channel can between two concurrent tasks running on the same transputer. Where we would require two soft channels for the two task to exchange information unilaterally, a single virtual suffices. (b) A virtual channel can be used to connect two neighboring transputers, as if it were a hard channel. Here again, the virtual channel allows bi-directional movement of information while the hard channel is unidirectional. (c) The great power of virtual channels is to connect remote transputers that do not share a link.

It may seems strange and "un-transputer"-like to talk about information flowing in two directions at the same time once we know that a transputer only contains a processor and eight DMA controllers servicing the links: how can something else "go on at the same time" with these limited resources? This is quite a subtle point, and we need to learn a little bit more about the virtual channels before fully exploring it. The main difference, though, appears in Figure 5-6(c). With hard channels,, Transputer T1 can send a message to T3 only by relaying it through T2, which means that the programmer must make sure that T2 will provide some relay task, or some relay mechanism to allow this communication. With virtual channels, however, T1 can be connected to T3, without having to program T2, or any other transputer in the network to relay information between T1 and T3.

The powerful feature of virtual channels is that they are independent of the hard channel topology, and can link transputers not in direct contact. Moreover, a transputer can have an unlimited (for all practical purposes) number of virtual channels. The memory space available being the major limitation.

How can this be possible, when the transputer is clearly limited to four hardware channels? The answer is that Logical Systems C introduces an extra layer of software, sandwiched between our code and the hardware, which manages virtual channels. At the programmer's level (our level), we simply need for T1 and T3 to declare two virtual channels (we will take a look at how this is done soon, have patience!), while no indication of this channel need to appear in the code running on T2. At the lower software level invisible to the programmer, though, each node runs a group of high priority tasks whose job is to route messages exchanged between virtual channels. So if T1 sends a message to T3 over the virtual channel, our application code on T1 will in fact pass the packet that we are sending to the low level virtual router which will consult its internal table (more on that later) to find out the destination of the message. Finding that T2 offers the shortest path to T3, the virtual router uses the hard link between T1 and T2 and routes the packet to T2. There, a copy of the same virtual router intercepts the packet, checks it destination, and passes it on the next hard link directly to T3. You will have guessed that T3 runs the same virtual router, which will get the message and pass it on to our application, just as if it had come directly from T1. In fact, if we look at the code of this application, we will find that only the code for T1 and T3 include any reference to the virtual channel, while T2's code may not refer to it at all.

Now is a good time to take a look at the code for this example.

/*
     vchan1.c
     Virtual channel first example.
*/
#include <stdio.h>
#include <stdlib.h>
#include "conc.h"

main()
{
     if (_node_number==1)
     {

          Channel *vc13;

          int     number=12345678;

          /*--- initialize virtual channel ---*/

          vc13=VChan(2);

          /*--- send integer to T3 ---*/

          VChanOutInt(vc13, number);

     }
     else if (_node_number==2)
     {
          float Fib;
          /*--- keep busy by computing Fibonacci of 54 with---*/
          /*--- doubly recursive function (VERY INEFFICIENT!)---*/
          Fib = Fibonacci(54);
     }
     else if (_node_number==3)
     {

          Channel *vc31;

          int     temp;

          /*--- initialize virtual channel ---*/

          vc31=VChan(3);

          /*--- wait for integer from virtual channel ---*/

          temp=VChanInInt(vc31);

}
}

Listing 5: Listing of vchan1.c

Declaring a virtual channel

We have highlighted the three main actions required for using a virtual channel: its declaration, initialization, and use. Declaring a virtual channel is done in exactly the same way we would declare a soft channel. We access the virtual channel through a Channel * pointer. Note that T1 declares the virtual channel as vc13, while T3 declares it as vc31:

Rule 2
Unrestricted names
The name given to a virtual channel by a node is independent of the name given to the same channel by the node at the other end. The rule is to adopt some convention that makes sense to the programmer.

Initializing the virtual channel

Node T1 could have called the channel MyChannel, and T2 could have called it ChanToT1, without any restriction. What makes a difference, though, is the index associated to the channel via the function VChan().

          vc13 = VChan(2);
          ...
          vc31 = VChan(3);

Vchan stands for Virtual Channel, and assigns a number to each channel extremity. Under version 93.1 of LS C, this number can range between 2 and 32767, and is used internally by the virtual mapper to index its routing table[1]. We will refer to these numbers as channel handles, or handles for short. Each virtual channel is thus defined by a pair of handles, both assigned independently via VChan by the nodes linked by the channels. The choice of number is unrestricted, as long as each one is unique within a node. We could have initialized the channels as follows:

          vc13 = VChan(7);
          ...
          vc31 = VChan(105);

Or as follows:

          vc13 = VChan(2);
          ...
          vc31 = VChan(2);

As long as the channels are created on different nodes, they can have identical handles. However, if Node 1 had declared several virtual channels, all of them should have been assigned different handles.

Rule 3
Unique VChan numbers
The numbers associated to the channels ends with VChan must be unique within each node. Always use lower numbers before using larger ones in order to minimize memory use.

In other words, if the program runs on a network of N transputers, then two separate transputers can call VChan with the same argument, but any given transputer cannot call VChan twice with the same number. We will see shortly why this requirement is so strict. Before we see how the routing from T1 to T2 actually take place, let's take a look at the third action: the data exchange.

     if (_node_number==1)
     {
          ...
          /*--- send integer to T3 ---*/
          VChanOutInt(vc13, number);
     }
     ...
     else if (_node_number==3)
     {
          ...
          /*--- wait for integer from virtual channel ---*/
          temp=VChanInInt(vc31);
     }

We recognize the ChanIn and ChanOut forms for integer exchange, but this time the functions display a "V" prefix, characteristic of the virtual channel functions. With virtual channels, we have a new set of message passing functions (ChanIn, ChanOut, and ProcAlt families) that are syntactically identical to their hard-channel and soft-channel counterpart, but with a "V" prefix. We refer to them as the "V" functions. You may be worried that suddenly you will have another level of complexity added to your coding by having to associate functions to channels by type. Fortunately, all the LS C "V"-functions for message passing accept also hard and soft channels for arguments. This is a blessing for the programmer, and we will adopt the following rule when we develop programs from now on.

Rule 4
One kind of message-passing functions
When writing a parallel program, use only one kind of message-passing functions. If the program makes use of virtual channels, use "V" functions throughout the program, otherwise use the standard functions.

Of course there will be exceptions, but this rule will simplify our coding effort[2 ]. Before we move on to defining the network, there is another important rule that we must always enforce while working with virtual and soft channels .

Rule 5:
Byte counts must match
When exchanging information over a virtual or soft channel, the number of bytes sent by the VChanOut function (or one of the functions derived from it) must match exactly the number of bytes received by the VChanIn function (or one of the functions derived from it)

Defining the network

Take another look at the example program above. There is a magical feel to it The magic lies in the fact that we execute a VChanOutInt in one transputer, a VChanInInt in another one, and somehow, the integer finds a way to go from one to the other automatically... You may argue that since there are two virtual channels (in fact two ends of a virtual channel), defined in two places, only one path exists, and the integer has no other way but to reach T3. The magic here simply results from the fact that what we see in the program is only part of the total picture and that more information about how the virtual channel connects the transputers is hidden somewhere else. The virtual network is defined where the physical one is, in the network information file (nif file). Here is the nif file for our demonstration program:

buffer_size     200;
host_server     CIO.EXE;
level_timeout   400;
decode_timeout  2000;

vchan;

  1, vchan1, R0,  0     ,        ,   2[1] ,         ;
  2, vchan1, R1,  3[1]  ,   1[2] ,          ,         ;
  3, vchan1, R2,        ,   2[0] ,          ,         ;

1[2],3[3];

Listing 6: nif file for vchan1.c

We recognize the header with the buffer size and time-out values, and the description of the physical network: Link 2 of Node 1 connects to Link 1 of Node 2, and Link 0 of Node 2 connects to Link 1 of Node 3.

The new elements are the highlighted statements. The first one, "vchan;" tells the loader that the program will make use of virtual channels. The last statement defines the virtual network, and in particular how nodes are connected by virtual channels. Here we see that Node 1 and Node 3 are linked together: "1[],3[];" by a virtual channel with one end defined by the handle 2, and the other by the handle 3.

Creating virtual channels and linking nodes with them is therefore done in four steps (illustrated below with an example with a single variable and an array of dimension four):

Declaration: the channel is defined as a (Channel *) variable in the code.
```
Channel *VirtChan, *FromRoot[4];
```

Initialization: the channel is first given a unique handle:

VirtChan = VChan(6);
for (i=0; i<3; i++)
     FromRoot[i] = VChan(10+i); /* the handle can be given
                             by an expression.  The only 
                             requirement is that its value
                             be unique over the whole application*/
FromRoot[3]=NULL;

Use: The channel can then be used the same way hard and soft channels would, except that a V-function is introduced instead:
```
VChanOut(VirtChan, &i, (int) sizeof(int));
i=VProcAltList(FromRoot);
x=VChanInInt(FromRoot[i]);
```
Define network topology: The topology of the network of virtual channels is then defined in the nif file.
```
1[6],2[7];
1[11],3[15];
1[12],4[16];
1[13],5[17];
```

More magic!

These four points are necessary and sufficient for a program to use virtual channels. You will note that we listed the definition of the network last. Although listing it first may have seemed more appropriate, there is a reason to do so: There is still some magic left in the nif file. Can you see where it lies? Before we expose this surprising feature, let us develop a more complicated example, but this time we will concentrate on the network supporting our code.

A virtual star network

Figure 5-7 shows a three by three mesh along with its network information file. Note the close relationship between the hardware network and the virtual one defined by the nif file.

buffer_size 200; host_server cio.exe; level_timeout 400; decode_timeout 2000; vchan; 1, exmpl2, R0, 0, 2[2], , 4[0]; 2, exmpl2, R1, , 3[2], 1[1], 5[0]; 3, exmpl2, R2, , , 2[1], 6[0]; 4, exmpl2, R1, 1[3], 5[2], , 7[0]; 5, exmpl2, R2, 2[3], 6[2], 4[1], 8[0]; 6, exmpl2, R3, 3[3], , 5[1], 9[0]; 7, exmpl2, R4, 4[3], 8[2], , ; 8, exmpl2, R5, 5[3], 9[2], 7[1], ; 9, exmpl2, R6, 6[3], , 8[1], ; 5[2],1[10] 5[3],2[11] 5[4],3[12] 5[5],4[13] 5[6],6[15] 5[7],7[16] 5[8],8[17] 5[9],9[18]

Figure 5-7: The 3 by 3 hardware network (top-left), its associated nif file (right), and the resulting virtual network (bottom left).

The code used by the transputers to initialize their virtual channel handles is shown below (one of many possible versions):


#define n          3
#define STARCENTER 5
#define N          (n*n)

if (_node_number==STARCENTER)
{
     Channel *FromCenter[NONODES-1];
     int     i, j, k;

     for (i=0, j=2, k=0; i<NONODES-1; i++)
     {
         if (i==STARCENTER)
              continue;
         FromCenter[k++] = VChan(j++);
     }
     ...
}
else
{
     Channel *ToCenter;

     ToCenter = VChan(_node_number+N);
     ...
}

Take a look now at Figure 5-8. The hardware network is now a ring and the nif file defines the same virtual connections as in Figure 5-7. As a result the virtual network is again a star.

buffer_size 200; host_server cio.exe; level_timeout 400; decode_timeout 2000; vchan; 1, ex mpl2, R0, 0, 2[0], , ; 2, exmpl2, R1, 1[1], 3[0], , ; 3, exmpl2, R2, 2[1], 4[0], , ; 4, exmpl2, R3, 3[1], 5[0], , ; 5, exmpl2, R4, 4[1], 6[0], , ; 6, exmpl2, R5, 5[1], 7[0], , ; 7, exmpl2, R6, 6[1], 8[0], , ; 8, exmpl2, R7, 7[1], 9[0], , ; 9, exmpl2, R8, 8[1], , , ; 5[2],1[10] 5[3],2[11] 5[4],3[12] 5[5],4[13] 5[6],6[15] 5[7],7[16] 5[8],8[17] 5[9],9[18]

Figure 5-8: The ring network (top left), its associated nif file (right), and the resulting virtual network (bottom left).

To initialize their virtual channels, the transputers can run the same code listed on the previous page. This feature has the remarkable property that once our program is written for the three by three hardware network, we do not need to recompile it for it to run on the chain network. The connection between virtual channel handles is made at load time.

This is one area where the power of virtual channels is helpful. The program can be written in such a way that it can be made totally independent of the network on which it will be mapped, and one may not even know ahead of time the shape of the network. For example, assume that we create a program module for a single transputer, assuming that this transputer will be part of an square mesh. The module assumes communication with an up, low, right, and left neighbor through virtual channels that it declares as follows:

        Channel *up, *down, *right, *left;

        up    = (_node_number*4)+0;
        right = (_node_number*4)+1;
        down  = (_node_number*4)+2;
        left  = (_node_number*4)+3;

Once the module is created and compiled, a square mesh of transputers of any given size can be put together by simply creating a nif file where the actual physical connections of the network are defined (which might be a mesh, a ring, a chain, or any other network, irrespective of what we are implementing), and where the virtual mesh is constructed. Of course, we assume that the module will be programmed in such a way that the application that it implements is scalable, so that the program is written to work in meshes of size N by N by simply redefining N and recompiling the program.

Multiple I/O Paths

One of the tremendous bonus offered by a virtual channel router implemented as part of our parallel programs, is that it automatically sets up a path between each node in our network and the host. For this reason, virtual channels allow any node on the network to do concurrent Input/Output operations with the host. This means that we are not restricted to having printf and scanf statements executed by only one task in the root anymore. All nodes in the network can issue simultaneous printf statements. The statements will be all processed and will get their information displayed (not necessarily in a repeatable order) on the screen. In fact this applies to all the I/O functions supported by stdio.h, and represents quite a feat in implementation details on the part of Logical Systems.

With the virtual channels turned on, a programmer can get direct feedback from the nodes during the computation, and can record the moments when different parts of the computation start.

A price to pay

This power comes at a price, however. Because virtual channels use the hard links in a multiplex fashion, with routers automatically controlling the traffic, a program making use of virtual channels cannot use hard links directly. LINK0IN, LINK0OUT, and the other six links cannot be used when virtual channels are in effect. This is understandable. If we program a node to output information directly to a hard link monitored on the other side by a virtual router, then the router will be totally confused by the information that it receives. It will not match its protocol, and unpredictable results will occur.

The simultaneous I/O feature makes it appealing to take a buggy program not using virtual channels and to insert a vchan line in the nif file, just before the physical network description, and to add printf statements in the code running on all the nodes. This will unfortunately not work because any ChanIn or ChanOut to a hard link will intercept "virtual" packets.

This leads us to our last rule on the use of virtual channels:

Rule 6
Use none or all
A program using virtual channels must use only virtual and soft channels, and must relinquish the direct use of hard channels[3]

Performance issue

The virtual router adds an extra level of software that is involved with every bit of information that is exchanged between two tasks (remote or not) over a virtual channel. Hence, some performance loss is to be expected, since the virtual router must grab some of the processor quanta for its own use. Moreover, when a message is sent over a virtual channel, it is packetized in units that may be much smaller than the packet, adding some additional overhead. This last point might not be as bad as one think, as we will see in Chatper 8. Indeed, the packetization reduces the granularity of the communication which, under some conditions, may result in lower latencies.

Parallel Programming in C for the Transputer© D. Thiébaut, 1995

5-6 Virtual Channels

Rule 1 Virtual channels are full duplex

Rule 2Unrestricted names

Rule 3Unique VChan numbers

Rule 4 One kind of message-passing functions

Rule 5:Byte counts must match

Rule 6Use none or all

Parallel Programming in C for the Transputer
© D. Thiébaut, 1995

Rule 1
Virtual channels are full duplex

Rule 2
Unrestricted names

Rule 3
Unique VChan numbers

Rule 4
One kind of message-passing functions

Rule 5:
Byte counts must match

Rule 6
Use none or all