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



EXERCISES

 
5-6

Hot potato! Harness as many transputers as you can on your multi-transputer machine, and implement a fully-connected virtual network. A fully connected network is one where each node in the network is connected to every other node. Implement a version of the game of "hot-potato," where players (the nodes of the network) keep passing each other a "hot potato" (a message) that is too hot to handle. That is every time someone receives the potato it must pass it on to someone else, as fast as possible before getting burnt.

Select one node in your network which will introduce the hot potato in the network, and have each receiving node select at random the next destination of the potato. Make the potato a message that will contain the number of hops it is making, along with the list of the Id of the nodes encountered (in most systems a byte, or even a nibble, can be sufficient to store the _node_number of the nodes of a network).

When the Root receives the hot-potato, it will display the list of nodes visited during the last tour, and then it will clear the contents of the potato message.

.


 
 
5-7
Implement the hot-potato program with virtual channels and make each node display its Id on the screen when it receives the hot-potato.


 
 
5-8
Complete Exercise 5-5 by implementing a virtual ring over the hardware ring. Use the same topology as in Exercise 5-5 so that the three implementations (hard, soft and virtual rings) can be compared. Vary the size of the packets (from a few bytes to a few kilobytes) and plot the most accentuated variation for the three schemes.


 
 
5-9
Same as the previous exercise, but implement the ring within the root transputer, and replace the soft channels by virtual channels.


 

5-7 Concluding Remarks

Multitasking is implemented on the transputer by encapsulating the code of the task in a standard void-returning function which must have a pointer to its workspace (Process *) as the first argument in its parameter list. Once the code is defined, a function can spawn the concurrent task by creating a process pointer and by combining it with three other elements:

Communication between tasks can be achieved by three mechanisms: channels, shared variables and semaphores. Independently of where they reside (on the same transputer or on two neighboring ones), two concurrent tasks can always use message passing functions (ChanIn, ChanOut and alternation functions) to communicate. This feature allows for a high level of flexibility when mapping tasks to a transputer network. In Chapter 6 we will investigate how this can be used to debug on a single transputer programs intended to run on a multi-transputer network.

Tasks residing on the same transputer can also use their shared memory space to exchange information. When only one of the concurrent tasks accessing the shared data is the producer of those data, then simple variables can often be used. In cases where several tasks have modification privileges over the shared data, though, semaphores offer an reliable mechanism for exchanging and updating the information.

Virtual channels offer still another way for tasks to communicate. Their power is two-fold. Virtual networks are not limited by the actual topology of the physical network, and network with node fan-outs larger than four can be implemented with little effort. On the other hand, the virtual routing layer offers a stratum for I/O messages to travel, linking every node in the virtual network to the host. This yields a system where multiple concurrent I/O activities can be maintained by the nodes of the network. This power, however, comes at a cost, and design decision concerning the use of virtual channels should be reached early in the design stage. Example programs in the next chapters will alternate between simple code adhering rigorously to the hardware topology of the network where nodes communicate with each other via hard channels, and more flexible programs that make use of the virtual router.

This chapter ends the presentation of the parallel constructs of the LS C. The next chapter starts with the more esoteric subject of debugging parallel programs, and the more unambiguous one of writing reliable programs.

[Previous] [HOME] [NEXT]