Assignment 1 | |
Parallel Programming Assignments |
60 pts |
Rock, Paper Scissors |
Due: Feb 28 |
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 = 2^{r} | n 2^{r} |
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:
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:
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_{2} 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; } |
1
<< n
is 2^{n}.