Assignment 1
	Parallel Programming Assignments

Write an MPI program which allows the created tasks to play an epic rock-paper-scissors tournament. The created tasks should play contents in pairs until there is a final, victorious node. Here's what mine looks like:

bennet@jackson:~/mpi/rps$ mpiexec -n 4 rps 0 defeats 1. 3 defeats 2. 3 defeats 0. Task 3 wins. bennet@jackson:~/mpi/rps$ mpiexec -n 4 rps 1 defeats 0. 3 defeats 2. 1 defeats 3. Task 1 wins. bennet@jackson:~/mpi/rps$ mpiexec -n 16 rps 9 defeats 8. 10 defeats 11. 12 defeats 13. 4 defeats 5. 7 defeats 6. 2 defeats 3. 15 defeats 14. 0 defeats 1. 2 defeats 0. 7 defeats 4. 15 defeats 12. 9 defeats 10. 7 defeats 2. 15 defeats 9. 7 defeats 15. Task 7 wins. bennet@jackson:~/mpi/rps$

The processes participate in contests based on their rank. In the first round, the even-numbered nodes each compete with the one-greater odd node (0 and 1, 2 and 3, etc.) The winners of these contests compete in pairs, left-to-right, until a final winner emerges victorious from the tree. The last run above looks like this:

0		1		2		3		4		5		6		7		8		9		10		11		12		13		14		15
	0				2				4				7				9				10				12				15
			2								7								9								15
							7																15
															7

Run each contest by having the contestant nodes exchange random choices of rock, paper or scissors. (The MPI_Sendrecv is a good choice for this, though separated sends and receives should work.) Each side can then determine who won by the rules any child knows: Rock breaks scissors, scissors cuts paper, paper wraps rock. If there is a tie (both sides send the same symbol), simply run the contest repeatedly until there is a winner. Complete each round, then start the next one with the winners.

Announce the winner of each contest, and the winner of the whole tournament.

You may assume the number of processes is a power of two, but you may have a 10-point bonus if your program will function correctly when it isn't. In that case, you will have to introduce some "bys" where a process is allowed to advance to the next round without a contest. You may choose who gets the bys anyway you like. All nodes must have some chance of winning the tournament, and of losing.

My Solution

One problem you must solve is to figure out how to each node finds its opponent so it can exchange symbols. This is easy for the first round, but after that it depends on who wins other contests. My solution was to appoint a referee for each contest. Before each contest, the contestant nodes learn the number of their opponent from the referee. After each contest, the winner reports his id to the referee for the next round. The referee for any contest is the smallest node which could compete in that contest. For instance, in the above, the referee for the contest between 9 and 15 is 8; between 4 and 7 is 4. (A node may be its own referee. It's a computer program, and it doesn't cheat.) For the first round, each even node is a referee.

This helps because any node which needs to find its opponent can compute the referee number from its own rank and the round number. Specifically, if we are very un-computer-science-ish and number the rounds from 1, the referee R for node n entering any contest in round r is given as:

R = 2r

n 2r

Using integer arithmetic. The referee's computable locations allow the nodes to find their contestants.

There is no global record of the state of the contest. Each node keeps track of the the current round and whether or not it has lost. It's main loop body is essentially this:

1. Compute the referee for the current round.

2. Receive the opponent.

3. Battle to the death, or at least lack of a tie.

4. If victorious, increment the round number, compute the (possibly new) referee, and inform it of this glorious victory. Then repeat.

The referee function is independent of the contestant function. A threaded solution would perhaps be the most elegant, but I did not attempt one. Therefore the main loop must essentially do both things with appropriate conditions. So the main loop actually looks a bit more like this:

1. Compute the referee for the current round.

2. If that referee is me, send the name of each contestant to the other contestant.

3. If I haven't lost yet:
   1. Receive my opponent.
   2. Battle to the death, or at least lack of a tie.

4. If this is the last round and I haven't lost, declare myself the overall victor and exit.

5. If this is the last round and I have lost, just exit.

6. Increment the round number.

7. If I'm the new referee, receive the numbers of the two winners for the next round.

8. If I have lost, and I'm not referee, exit.

My solution for dealing with a number of hosts which is not a power of two is essentially to pad the set up to the next power of two with ghosts that always lose. When a node is about to enter a contest, it checks to see if its opponent is a ghost. If so, it takes a by to the next round without trying to contact the ghost machine. Referees must also be careful not to contact ghosts. (It's forbidden Leviticus, after all.)

This solution is inequitable since all the bys are given to higher-numbered machines. If the number of machines is one over a power of two, the last machine must only win a single contest against whichever node has fought through and vanquished all the others. Since the contestants are (still) computer programs, they have not complained. (If this were an AI project, they'd form the Power-of-Two Node Liberation Front (PTNLF), and hire a lawyer node and try to get the rules changed.)

By the way, for N machines, the number of rounds is log₂ N, rounded up to the next integer. Or, in particularly grungy C:

/* Find ceil of log2 of the n. */ int celog2(unsigned int n) {         int ret = 0;         unsigned int limit = 1;         while(n > limit && limit) {                 ++ret;                 limit <<= 1;         }         return ret; }

That operator, <<, is your friend, because 1<< n is 2ⁿ.