You are in a maze of twisty little passages, all alike.
Updates:
Grading Mazes: 6k, 8k, 12k, 6ku, 8ku, 12ku (the last three have no solution)
Final leader board. Runoff of top 7 is here (results are the average of 13 runs). Here is the final late submissions leaderboard.
You will write a parallel maze solver. The solver will take as input a two-dimensional rectangular maze with at most one solution. The solver will return the solution, if it exists, or null otherwise. This project admits a great deal of flexibility. The aim is to obtain a solution that makes optimal use of parallel resources.
First, import the project archive into Eclipse. This will create the maze_project directory, which contains the source files, javadoc documentation, and the file generate.jar, which will generate random mazes. To run this maze generation program, you can do one of two things. From a terminal window, go to the maze_project directory and type:
java -jar generate.jar <width> <height> <filename> solvable
This will create a solvable maze with the given dimensions and save it with the provided filename. To generate an unsolvable maze, use the command
java -jar generate.jar <width> <height> <filename> unsolvable
Alternatively, you can run this program from Eclipse. Go to
Run > External Tools > External Tool Configurationsand in the upper left, hit the button to make a new configuration (a paper with a plus on it). For the name, type
maze generationFor Location, type
${system_path:java} For Working Directory,
type ${workspace_loc:/maze_project} Finally, for
arguments, type -jar ${workspace_loc:/maze_project/generate.jar} 100 100 100.mz solvable
(where you should replace 100 100 100.mz and solvable with the
parameters you want to pass to the maze generator). Once you run
this configuration, it will generate the file in your main project
directory. To see, select the project in Eclipse and hit F5 to
refresh the working directory and see the file.
The code in the Eclipse project includes three single-threaded example solvers.
STMazeSolverRecis the simplest: a depth-first search defined as a recursive procedure. There is a danger, when using this approach on a very large maze, of running out of stack space.
STMazeSolverDFSuses an optimized depth-first search involving so-called choice points. There is some discussion of this idea below. This second solver also updates the maze while it works, so you can see it graphically; see below. The third solver is
STMazeSolverBFSThis solver performs a breadth-first search. This solution is more complicated that the others. However, since breadth-first search involves exploring from several points of the search space simultaneously, this solver makes the best starting point for a multi-threaded approach.
To run these solvers on the maze you just generated, build
the project in Eclipse and then run the Main class, providing
the filename as an argument. This will run all defined solvers on the
given maze file. The next section explains how to add your own
solvers to the list. To see a graphical depiction of the maze, run
with arguments:
<filename> display(Note that you should not attempt to display mazes more than 200 x 200 or so, or else they will be too large to fit on your screen.)
We provide several classes in the skeleton code. The Position class represents a location in the maze. The Direction class represents the four compass directions. The Maze class stores a representation of the maze and also provides methods that make querying the maze easier. For example, the Maze.getMoves takes a Position and returns the list of directions in which you can move if you are at that position.
The Main class supports the loading of mazes from disk and calls the maze solvers. Solvers are stored in the solvers array in the Main.solve method. Each solver in this array is executed on the maze provided as input at the command line when the program is called in solving mode. You can add multiple solvers to the list to easily compare them. Solvers must be subclasses of abstract class MazeSolver.
The Maze class also provides means to color cells in the maze. The methods getColor and setColor provide access to these features. You do not need to use these methods, but they may be useful for debugging. If the program is being run with the display option, as mentioned above, then a graphical depiction of the maze will be drawn. A solver can color maze cells and then use Maze.display.updateDisplay() to update the graphical depiction of the maze. To aid in stepping through your algorithm, you can call maze.display.waitForMouse(), which will block execution until the user clicks on the maze window.
The Eclipse project includes the JCIP puzzle-solving framework. This is for your convenience. As mentioned in class, you might find it worthwhile to create a class that wraps Maze, and implements the Puzzle interface (taking advantage of methods already present in Maze). By doing so, you can use the puzzle solving framework to solve the maze. As a result, this gives you a way to use the JCIP concurrent puzzle solver to solve small maze instances in a multi-threaded manner.
The JCIP implementation of a concurrent solver makes for a good starting point. However, it is unlikely to beat the single-threaded solvers we have provided. The issue is that the units of work in maze solving are very small: a single move. Completing small units of work in concurrent threads generally results in the concurrency overhead erasing any performance gains.
There are several algorithms that could produce good parallel solvers. Here is a key observation: Any given choice point (i.e., a position with from which multiple outgoing paths are possible) that does not lie on the solution path is likely to quickly lead to dead ends in all directions. Thus, most times an exploration from a single choice point will quickly run out of work. This suggests that, to ensure that threads are mostly doing useful work, tasks ought to consist of exploring several choice points, to increase the amount of useful work per task.
Now, some ideas for algorithms. One approach is to do a depth-first exploration until there are several unexplored paths on the stack. At this point, these paths could be grouped and handed to a new thread.
A related idea is to use the Fork-Join framework and try a divide-and-conquer strategy. For example, each task could return a path from the current position to the end of the maze. When a task reaches a choice point, it could fork new tasks that explore each of the possible branches, and wait from them to return; if any of them return a path, then the current node is added to that path, and it is returned. Consider only creating a child task after some number of recursive calls.
Another approach would be to explore simulataneously from the start and the end, hoping to meet in the middle.
Whatever the approach, make sure that you provide a means to control the number of threads used by the search. If too many threads are spawned, the overhead of thread management will erase any performance gains. Recall from the text that you can figure out the number of processors on the executing machine by calling Runtime.getRuntime().availableProcessors().
STMazeSolverReccan run out of stack space on larger maze instances. To increase stack space available to the Java VM, you can use the "-Xms" argument. Adding
-Xms10mto the "VM arguments" section of your run configuration in Eclipse will increase the available stack space.
Similarly, heap space can be an issue with large mazes for all the solvers. To handle mazes greater than 4000x4000 or so you will have to increase the heap space available to Java. This can be done with the "-Xmx" option. Add
-Xmx2048mto your "VM arguments" to give Java access to 2 Gigs of RAM. Only do this if you have at least 3 Gigs of RAM in your machine. The linuxlab machines all have at least 4 Gigs of RAM.
To obtain full credit, you must create a parallel solver that, when run with at least two processors on the mazes provided at the top of this page, consistently beats the fastest sequential solver included in the skeleton code (STMazeSolverDFS). If you are able to beat STMazeSolverBFS, but not the faster one, you will receive 90% of the performance points. STMazeSolverRec is provided as an example, but is not used in the scoring.
You can use Linuxlab to test your program if your own machine does not have at least two processors (most of those machines do; the server machines you remotely log into have at least four processors).
Submit a short design document directly to the TA (brobbins@umd.edu) as a PDF. You should include details about the design of your multi-threaded solver and your rationale (how you arrived at this design). Feel free to use references as appropriate.
As usual, grading will take into account your code's thread-safety.
Execution time on a large parallel machine (50 cores) will be the metric used to judge submissions. Correct submissions will all receive full points, however the fastest implementations will get a T-shirt and bragging rights. We will give awards in three categories:
Everyone's solution will be evaluated over the same set of large maze instances.
The time taken to solve a maze is proportional to the number of cells explored, so for each of these categories, the biggest gains will come from discovering ways of finding the solution while exploring less of the maze (and while still supporting maximum parallelism).