No doubt, you've heard of the traveling salesperson (salesman?) problem. Well, this is a version of the problem in a world filled with wormholes. Ok. That sounds strange enough... but it really isn't that strange a problem. It's really a rather obvious problem involving our 3D printer.
Like most inexpensive 3D printers, our MakerGear M2 builds things by extruding lines of melted pastic in thin layers. Thus, every 3D model is computationally "sliced" for manufacture into layers, each of which is then translated into a set of lines within that layer. The catch is that what you get is a set of lines for each layer -- the sequence in which to build them is normally taken from the slice in an outline-first-then-fill-in pattern, which is often quite good, but might not be optimal. Given a set of lines to extrude, your program will simply order them such that the total time the printhead spends traveling -- including gaps between lines -- is minimal. The "wormholes" come from the fact that once you've decided to go to one end of a line, you come out of it at the other end. There is also the minor complication that the printhead speed moving between lines can be faster than the speed when depositing a line, although we'll ignore that issue in this project.
How hard is this problem? Well, ignoring the choice of which of the two endpoints on each line to go to, this is quite obviously a factorial problem. 5! is 120. 10! is 3,628,800, 15! is 1,307,674,368,000, and 20! is 2,432,902,008,176,640,000. Of course, for a particulare sequence of N lines there are 2**N possible flips of line segments, so 20 lines really gives (2**20)*20!, or a mere 2,551,082,656,125,828,464,640,000 possible orders. That's big enough to justify using a Genetic Algorithm (GA)... especially when your program is supposed to allow a set of up to at least 1,024 lines as input.
The serial GA code in C is aynil.c. It's pretty straightforward, as discussed in class. The only differences are that the cross() and mutate() are a little more complex in order to give somewhat better performance. There are actually several flavors of mutation and also a little trick involving seeding the initial population. The #ifdef VERBOSE stuff is just for the serial version; to get lots of tracing output, compile it with:
cc aynil.c -o aynil -lm -DVERBOSE
The command line arguments are simple enough. The first is the population size, with a maximum of 1024. The second and third arguments determine the relative frequency of crossover vs. mutation. The fourth argument is the number of individuals (steady-state "generations") to execute. Finally, the last two arguments are the X,Y coordinates of the printhead before printing the input set of lines.
The input comes on stdin as a simple text file. Each set of 4 floating-point numbers gives the X,Y endpoints of a line to extrude. For example:
20 20 20 10 10 20 20 20 10 20 10 10 20 10 10 10
If we specify on the command line that the printhead starts at position 0,0, this would then draw a box between 10,10 and 20,20. Assuming the start position is given as 0,0, here is one of the two optimal sequences for these lines:
10 10 10 20 10 20 20 20 20 20 20 10 20 10 10 10
Note that the 10 20 10 10 line in the input got flipped.
Your task is simply to get some speedup by re-writing this code to use MPI. Now, how do you parallelize this GA code? Well, you simply run many copies of it on different PEs. Each one should have its own population -- what is known as an "island model." Each PE will only have a copy of it's portion of the world population.
The basic idea is simply that each island's population evolves largely independently from the populations on all other islands. However, every so often, we'll copy a "good" individual from each island to some other. How often? Well, we'll talk about that in class....
Island model GAs usually work better than a GA with a single population of the same size because the islands preserve diversity while allowing fast convergence within each island. It doesn't really make much difference how infrequently islands interact or how they interact, so pick a method that is efficient for you to implement.
There is one little trick here: rand(). We'll talk about this in class....
You will be submitting source code, a make file, and a simple HTML-formatted "implementor's notes" document called a2.html, which should explicitly describe how and why you do the message passing as you do (i.e., why did you pick blocking or non-blocking). Please arrange your make file so that the executable file, which should be called a2, is compiled when one simply types make. All of the things needed should be packed into a single tar file for submission by a command like tar -zcvf a2.tgz files -- and that tar is all you submit. Do not include executable files, or other things that can be generated by make, in the tar you submit.
For full consideration, your project should be submitted no later than April 9, 2015. Submit your project tar file here:
Cluster/Multi-Core Computing