Assessment 2 on Message Passing

This assessment tests your knowledge of the history of different message passing systems. The final section test your understanding of how they work and the differences in function and semmantics.

Theory

10 points

For each only give a brief answer.

  1. In most message passing systems, what arguments (values) are generally required? (For example, the data to be sent). (2)
  2. What is the difference between blocking and non-blocking communication? (2)
  3. What is the difference between local blocking and global blocking calls? (2)
  4. Why do non-blocking calls need additional support functions? (2)
  5. As systems become more complex, why has the number of arguments increased so much? (2)

History and particular systems

10 points

For each question give only a brief answer.

  1. Describe why the Caltech Hypercube was considered a difficuilt platform to program? (1)
  2. Which message passing system introduced the concept of 'virtual processes'? (1)
  3. What improvements were made to NX between NX and NX2? (1)
  4. Which system introduced a send and receive operation in a single call, and why was it usefull ? (2)
  5. Which system(s) supported comprehensive collective/group communications? (1)
  6. On a distributed cluster, which system would I use, PVM or MPI, and why? (2)
  7. Is the Linda programming model, message passing or shared memory ? (2)

Operational understanding (i.e. in practice)

10 points

For the following sample of code:

Task 1

send ( task2, data, data-length )

receive ( task2, new-data, new-data-length )

Task 2

send ( task1, data, data-length )

receive ( task1, new-data, new-data-length )

  1. Why could this code fail on some systems rather than others ? (2)
  2. Which systems would this code always work on, and why? (2)
  3. How should the code be changed to allow it to work on any system ? (1)
  4. To work under MPI without changing the order of any calls? (2)
  5. If using either CMMD or MPI, how could it be shortened and still work? (1)
  6. If a code is performing an exchange of boundrary conditions on a 2-D grid (i.e. 4 exchanges), how could you use four non-blocking calls instead of four blocking calls? Why might it be faster? (2)

Fixing a message passing application

20 points

An application that has a master-slave structure is made from two pieces of source code (master.c and slave.c). To prevent errors from coding mistakes between the two codes all constansts are kept in a single header file (cons.h).

The application solves a problem by domain decomposition. The communication pattern used is:

  1. The master sends initial data to the slaves
  2. The slaves do a computation to generate changes in their values (delta values)
  3. The slaves pass partial results to all other slaves (a complete exchange)
  4. The slaves then calculate their own current values
  5. The slaves then pass these new values to the master for logging / plotting etc

At random times the code appears to produce a wrong result which then goes away. It is suspected that the code has a race condition in it (see additional diagram).

The form of the code is:

cons.h

master.c

slave.c

    start

    recv (master, init-data, data)

    for (iterations)

    end

  1. Write a short paragraph using the additional diagram on why a race occurs. (6)
  2. Is it due to the programming style? (2)
  3. Or the choice of semmantics? (2)
  4. What should be changed to fix it? Give 3 methods including the actual changes to the code. One of the methods should involve a collective operation. (7)
  5. How could this race be detected in the first place? (3)

Marking

All answers should be emailed to me at fagg@cs.utk.edu by Tuesday the 2nd of Feburary, 1999. I will cover the answers to this assessment on the 3rd of Feburary.

The numbers in brackets (2) denote the number of marks per question, the maximum score is 50.