Chapter 9 (continued)

1. Non-blocking (asynchronous) communication

   • Looked at the vast richness of MPI calls available for people who want to write clever, non-blocking message-passing code, including MPI_Wait, MPI_Waitall, MPI_Waitany, MPI_Waitsome, MPI_Probe, MPI_Iprobe, MPI_Test, MPI_Testall, MPI_Testany, MPI_Testsome. We were moved and humbled.

2. Master/worker paradigm --- some important issues

   • One issue is the master: will it be a bottleneck? As the number of workers grows, does communication to/from the master, or processing at the master, become a bottlneck? Another case that can come up when the number of workers is few is that the master node is being 'wasted', i.e., maybe the master node should do some work too once in a while.

   • A main issue is load-balancing. This is deeply connected to granularity (worker task size).

   • The simplest case for load-balancing assumes: (1) number of workers is fixed; (2) capacity of each worker is fixed and uniform; (3) work per task is fixed; and (4) total number of tasks is known ahead of time.

   • As each of the above assumptions is removed, the job of assigning tasks to workers becomes more challenging.

   • We talked about some simple ideas for avoiding serious load imbalance. For example, if the master knows the total number of tasks but they are variable in cost, the master could assign 1/2 of the tasks, in equal size batches, to the workers initially. Then on the next round about 1/2 of the remaining tasks are handed out. And so on. In this way, we reduce the potential cost of having one worker finish very late because it was given a large batch of expensive tasks.

   • If we know how much each task costs ahead of time, another nice idea is to sort the tasks, and hand out the most expensive ones first.

   • Note that any meaningful performance analysis will require that some assumptions be made about the distribution of work/task.