Parallel Maze Solving

Wendy Hu (whu), Ben Poole (bpoole), David Vetrano (dvetrano)

Abstract

In serial, maze solving is a well-understood problem, with many efficient solutions available for the simple case and its variations. Sequential algorithms in general rely on backtracking, a method which does not lend itself easily to parallelization. We tackle the problem of parallelization of maze solving with two innovative approaches using graph implementations of mazes in a  shared address space environment. A parallel partitioning algorithm divides a maze and assigns individual processors portions of the maze to be responsible for searching and solving. A more sophisticated front-wave expansion algorithm makes processors randomly choose points in the maze and perform breadth-first search from these points (keeping track of intersection points), with results from the processors merged to form a complete solution path.

Introduction

Maze solving is an interesting problem; while there exist natural serial solutions, it is not immediately clear how one could parallelize such a problem. In addition, because maze solving is modestly easy computationally, the problem required that we create infrastructure which supports creation, loading and saving of large mazes. Because this specific problem has not been studied in depth, we were able to experiment with different techniques.

A maze is a problem often used by humans for entertainment in which an individual must find a path from between two special locations called the start and end. Typically, the maze is presented as a labyrinthine series of walls in a two dimensional space, although mazes in arbitrarily high dimensions can be constructed. For clearness of presentation, mazes are often presented in the form of cells separated by walls, where all cells are of equal size and all walls meet at multiples of ninety degrees. Geometrically, we see that for a given cell, this structure yields at most four adjacent cells above, below, on the right and on the left. In general,maze solving is isomorphic to a special case of a single-source, single-target graph search problem, where each node has a maximum degree fixed by the maze geometry.

There are several attractive facets to the maze solving problem. First, the problem is natural. Small enough mazes can be quickly solved and constructed by hand. Second, because the problem can be interpreted as a graph search problem, writing code to deal with mazes is natural, although extensions of serial search algorithms into parallel may be non-trivial. Finally, because the problem is relatively uninvestigated, it requires individual thinking.

Abstractly speaking, maze solving algorithms take as input a maze, often in an adjacency structure, and output a path of nodes. This path has the constraints that it must connect the start and end points and cannot pass through a wall. In addition, a solution path is often required to contain no cycles. It can be easily shown that this condition implies that no node in the path can occur twice. When solving mazes in serial, we can often build this path iteratively. For example, our reference serial solution explores the graph depth-first, outputting the path it finds from the start to the end

However, an approach where we build solution paths iteratively does not easily lend itself to parallel, since different processors explore different regions of the maze, and each processor is capable of finding a solution or part of a solution. In this paper, we propose two methods for solving mazes in parallel. Because this area is relatively unresearched, we suggest that these algorithms may contain unique approaches to the problem and therefore represent our contribution to parallel  maze solving. The first algorithm, parallel partitioning, divides the maze by assigning an owning processor to each cell, or node, in the graph. This processor is responsible for updating adjacencies of its owning regions and determining whether the region it owns contains the end node. The second algorithm presents a different way to conceptually divide work between processing units. In this model, each processing unit picks a node from which to begin, with one processing node always beginning at the start and one at the end. It iteratively expands a region from this node, continuing until it hits a node owned by another processor. In complete generality, it may choose to continue in various ways or stop. Once all processors have stopped exploring, we can guarantee that each region is bordered by at least one other region or does not contain the solution path. Thus we know that we can construct a path between nodes in any two connected regions. Since the start and end nodes are each guaranteed to be in a region owned by some processor, we can reconstruct a solution path between them, if one exists.

Maze solving is related to several other problems. For instance, circuit routing algorithms must often find paths between different locations on a grid which obey certain constraints. The simplest such algorithm is Lee’s routing algorithm, which is based on breadth-first search (Lee, 1961). This algorithm generates a path by storing in each node a distance from the start node as it performs breadth-first search.The search will not expand to occupied regions, for instance those which contain wires or other wired parts. After the search completes, we can work backwards from the end node,  moving to a location with a distance exactly one less than our current node. Using breadth-first search on such a graph has nice properties. Most importantly, since we explore nodes in order of their distance from the start node, we can guarantee that a path we find has shortest length. In 1992, this algorithm was adapted to a transputer network, which is somewhat analogous to a message passing system (Sagar and Haag). The authors adopted a wave expansion method to solve the routing problem in parallel. Interestingly, they find that across all problem sizes, their most efficient solution exhibits speedups which asymptote as more transputers are added. Their second solution exhibits a maximal speedup around 100 transputers, after which speedup quickly falls off.  From these results, we may guess that maze solving in parallel is at least somewhat non-trivial.

Finally, it should be noted that maze solving is a special case of pathfinding with a constrained geometry and where the cost of exploring all edges is equal. For this reason, a brief overview of parallel pathfinding will be considered. Generally speaking pathfinding is usually performed in serial with algorithms like A*. This holds true when solving the problem in parallel. Cohen and Dallas used a modified version of A* to solve this problem on a shared memory system (2010). To solve this problem in parallel, they update paths which pass through nodes owned by a given processor in parallel, allowing processors to find non-optimal paths to the goal. The algorithm terminates when no processors can consume any more nodes which will adjust path lengths. In addition to parallelizing a single search, others have parallelized multiple pathfinding searches on a single graph (Nohra and Champandard, 2010).

Iterative Design and Approach

To begin solving mazes, we needed to write code to create, save  and load mazes. To keep our solutions most general, the maze was internally stored as an adjacency list.  In this way, the maze solvers can be used to solve arbitrary geometry mazes.  After support code was written, we needed to create large mazes. There are many algorithms for maze creation. However, since this project was specifically focused on solving mazes, we used several existing programs to create mazes. All mazes used in the writeup were generated by an implementation of Eller’s algorithm., which builds mazes by keeping track of connections between columns in the maze with set operations. This means that we can generate mazes very quickly. However, it should be noted that these mazes are perfect, meaning that any two points on the edge of the maze can be chosen as the start and end point and a valid maze will still be created. Here, two opposite corners were chosen as the start and end point. However, to ensure that our maze solvers produced correct results for all types of mazes, during the testing phase, other types of mazes were tested. We gathered several image mazes from the internet as well as generating mazes using a recursive partitioning algorithm. These mazes were tested with the code and the maze solvers were shown to produce correct paths.

One challenge associated with solving mazes is that, since mazes can be solved in  O(n^2) and Ω(n), we need large problem sizes to see large runtimes and to effectively evaluate our algorithms. Typically, however, even with very large mazes the fastest parallel solver could solve the problems in a small amount of time.  To solve this problem, we  averaged computation time for several  iterations together. This reduced variance across trials of the solver using any solver which exploited randomness (see below).

Given its simplicity, we approached the problem of writing a serial maze solver first. Maze solving in serial has straightforward solutions using well-known graph algorithms. For our project, we implemented two basic sequential algorithms: a depth-first search implementation using stacks, and a breadth-first search implementation using queues. In either case, the implementation is simple. First, the start node is added to the corresponding data structure. Then after dequeueing a node from the structure, we add all adjacent elements. When we pop the end node from the graph, the solution has been found. By recording depth of a node from the start node when we add it to the data structure, we can reconstruct the solution path backwards from the end node. Our more sophisticated parallel algorithms later build on these basic approaches.

Parallel Partitioning

For a first approach toward maze solving in parallel, we implemented a partitioning algorithm, where maze cells were divided up amongst P processors, who were each responsible for their particular subset of the maze cells. Consecutive maze cells were divided up in “chunks” among processors, in order to facilitate both load balancing and cache optimization. The start cell was initially set as “recently visited”, with all other cells labeled as “unvisited”. Each processor loops over its subset of maze cells, checking for recently visited cells that are within its domain. Upon finding that one of its cells was recently visited, processors mark all neighboring cells as “recently visited”, and the cell in question as “visited” (not to be modified again). When marking a cell as visited or recently visited, the data structure keeps track of which neighboring cell caused it to be visited. Eventually, the end cell will be visited, and given the previously recorded data of which neighboring cells caused visitation of later cells, we backtrack in order to find a path starting from the start node. The data structure that keeps track of which cells are visited and by whom is an array that holds cell IDs. When a cell is unvisited, its array element contains 0. When a cell is recently visited, its array element holds a negative number (the negation of the cell ID that borders it and caused it to be visited). When a cell is visited, it holds a non-zero positive number that indicates the cell ID of its neighbor that tagged it.

With trial and error, we found optimum implementations and a couple of important design choices proved to greatly improve performance of the parallel partitioning algorithm. First, consecutive “chunks” of maze cells partitioned among processors displayed much greater performance than a “scattering” of maze cells among processors (making processor N%P be responsible for cell N). This is most likely due to increased cache hits with the consecutive block partitioning scheme--we access array elements with a stride of 1 in block partitioning, whereas we access them with a much larger stride in the scattering scheme. At first glance, it seemed that “scattering” of maze cells among processors may have the potential to improve load balancing among processors (it seemed reasonable that making each individual processor be responsible for geographically disparate cells may increase the probability of good load balance among the threads), however this is evidently overshadowed by the negative effects of decreased locality.

In addition, considering the large numbers of reads and writes experienced by the array, we suspected that false sharing played a major role in dampening the speed of the algorithm. This suspicion was confirmed and the problem remedied when we decided to add “padding” bytes to each array element, making each 64 bytes, or the usual size of one cache block, and saw marked improvements in run-time, speedup, and scalability of the algorithm.

Parallel Wavefront Expansion

The second parallel implementation was based off of a technique known as wavefront expansion. The serial version of this algorithm is called Lee’s routing algorithm and consists of 2 phases: wave expansion and backtracking. The first phase performs BFS from the starting node, marking each node with the distance from the starting node. The second phase starts at the ending node and backtracks to the starting node by moving to the adjacent node with the minimum distance.

One extension of Lee’s algorithm is to perform BFS in parallel from the starting and ending nodes. When the wave from the starting and ending node intersect, we can reconstruct the path from the start to the finish by reconstructing the path from the intersection to the start, and the intersection to the end, and then joining them. This can be thought of as a parallel version of Lee’s algorithm but restricted to two processors. In some literature this method has been discussed and is called “double fan-out” (Svensson and Montiero, 2008).

However, to our knowledge this algorithm has not been applied to greater than two processors. We extended the algorithm to multiple processors by introducing an additional step into Lee’s algorithm. As before, each processor performs BFS outward from its origin, marking nodes that it visits with the distance to its origin. When two processors intersect, they are marked adjacent in a processor adjacency matrix and we store the point of intersection. After the wave expansion step has completed, we are left with a labeled visited distances structure and an adjacency matrix between processors.

The next step is to identify which processors lie along the path from start to end. This processor path can be recovered by performing BFS on the processor adjacency matrix. Using this processor path, we can then reconstruct the path through the maze by backtracking from each of the intersection points along the processor path. The details of the algorithm are described in the following pseudocode:

Although the parallel algorithm for wavefront expansion is relatively straightforward, the parallel implementation is not. Each processor must have access to the global visited structure, which identifies which nodes in the maze have already been visited by any processor. Keeping this global visited structure updated on all the processors was the largest bottleneck in our parallel implementation. We also had to determine the the origin of the wave for each processor. We always assign processor 0 to the start and processor 1 to the end. For the other processors, we initially just picked evenly spaced nodes in the maze, so having the origin for processor i at i*num_cells/num_procs.

For our first implementation of parallel wavefront expansion, we placed a single lock around any accesses of the visited structure. This created tremendous contention over the visited structure and resulted in extremely poor performance. However, we did not need to place locks around the processor adjacency and intersection structure as modifications to these were guarded using the same lock. We also just chose the first available free cells as origins for the processors. We found that even with 16 processors we were not able to exceed the speed of the serial version.

To improve performance, we used a round robin locking scheme, where we had a large number of locks that are assigned to different cells in the maze. Determining the mapping scheme from cell index to lock index can be quite difficult. We would like this mapping scheme to distribute cells to locks with approximately an equal distribution, and we would like cells that are accessed ad the same time to be mapped to different locks. For this project, we used the simple map of taking the lock index to be the cell index modulo the number of locks. The number of locks to use is another issue which we address in the experiments section. We also played with padding the array of locks structure, but found that it just decreased performance.

Figure 1: Effect of processor origin position on running time. Switching to random positions tremendously decreased running time.

Another improvement we added was to randomly pick origin positions for the processors. This greatly improved the running times as certain origin positions were better than others and we averaged computation times over multiple iterations. This improvement was what really gave us speedups over the original version, and allowed us to beat the serial implementation (Figure 1). Thus choosing good origin position is extremely important in achieving good performance. We believe that one could develop more intelligent heuristics for picking initial positions which could improve these results even more.

Figure 2: Effect of early termination on wavefront expansion runtime
for P=16 on a 5000x5000 maze

Yet another improvement we implemented was early termination in the wave expansion phase. In the original implementation, when one processor no longer has any cells to visit, it waits at a barrier for all other processors to complete before moving onto the next phase. However, it is possible that there already exists a path from the start to the end, and that the future maze exploration will be unnecessary. Instead of waiting at the barrier, when a processor has completed it searches for a path from the starting processor to the ending processor in the processor adjacency matrix. If a path exists, then we can terminate the wave expansion phase as we can already recover a path from the start to the ending cell. Thus if a processor finds such a path, it sets a global “done wave expansion” flag which terminates the other processors. It then advances onto the path reconstruction stage and returns the final path. We found that including early termination greatly improved the results (Figure 2).

Results

We evaluated our algorithms on mazes with sizes from 1000x1000 up to 5000x5000 on the PSC supercomputers Blacklight and Pople. Due to time constraints, we only considered a maximum of 16 processors and were not able to evaluate all mazes on both machines. In the following sections, we only present computation time results and speedup and ignore initialization time. We did this because initialization time was constant for a given maze size for all algorithms (the parallel version’s initialization time was constant, it did not scale with P). Overall, we found that wavefront expansion was able to speed up the maze solving problem, and that parallel partitioning did scale but was unable to improve on sequential run-time.

Parallel Partitioning Results

Performance analysis of the parallel partitioning algorithm, as examined on Blacklight on a 1000 by 1000 maze, shows that the algorithm scales almost linearly. However, as illustrated by the following graph, the algorithm was ultimately unable to improve on the sequential run-time. The overhead of the parallelization evidently overshadowed any performance gains, most likely due to remaining problems with cache locality and false sharing.

Figure 3: Blacklight parallel partitioning results for 1000x1000 maze

Figure 4: Linear speedup for 1000x1000 maze

Wavefront Expansion Results

Before evaluating the performance of the wavefront expansion algorithm, we first had to pick the number of locks to use. We varied the number of locks from 2 to 100000 while fixing the number of processors at 16 and using the 4000x4000 maze (Figure 3). We found that anywhere between 50 and 100,000 locks worked well. This was somewhat surprising as we thought having only 50 locks might cause contention. However, it meant that we could keep a smaller number of locks and still achieve relatively high performance. We chose to use 1,000 locks for the rest of the wavefront expansion evaluations due to it having the minimum runtime and being relatively small compared to other lock numbers tested.

Figure 3: Effect of number of locks on the wavefront expansion runtime where the number of locks is varied between 2 and 100,000 with P=16 on a 4000x4000 maze. When the number of locks is 1 (not pictured), the runtime is nearly 4 times when the number of locks is 2.

Using wavefront expansion, we were able to solve mazes of size 3000, 4000, and 5000. Somewhat surprising to the authors, we were able to achieve speedups greater than 1 using as few as 4 processors (Figure 4). Using 16 processors we reached a speedup of ~2.5 for the larger mazes. We found that our algorithm did not scale linearly with the number of processors, but the runtime was decreasing as the number of processors increased. This is most likely due to the global visited structure which all nodes simultaneously reading and writing to. If this global data structure could be partitioned or stored locally then the speedups could probably be improved. We also see that the problem size effects the speedups in that smaller problem sizes are sped up less. With even larger problem sizes we might expect that speedups would increase further.

Figure 3: Blacklight Wavefront Expansion results for

3000x3000, 4000x4000 and 5000x5000 mazes

On Pople, the runtime and speedup pattern was less clear. We found that speedups increased linearly until 4 processors, but decreased or increased after that depending on the problem size. We believe this discontinuity in the graph is due to the physical layout of the Pople machine. Each blade server contains only 4 cores, thus for >4 processors, we have to share the global visited structure between racks. This increased latency reduces performance for larger mazes where the communication cost is higher. However, for small mazes we were still able to achieve reasonable speeds. On Blacklight we did not see this effect, but that is because the blacklight blade servers contain 16 cores each, so we were not attempting to share information between nodes.

Figure 4: Pople Wavefront expansion results for 1000x1000 and 3000x3000 mazes

Conclusions

We presented two parallel algorithms for solving mazes. Because of the underlying representation of the mazes, these algorithms could be used to solve  any type of maze. In principle, the algorithms could be used to find a path through directed graphs  with a given source and target node. However, in their current version, the algorithms only demonstrate a single path and not the shortest path, as is desired in many cases.

The algorithms presented produce correct solutions and run quickly, in some cases beating the serial implementation. After completing the project, however, we learned that this problem is fairly difficult to implement in parallel. The greatest challenge we encountered was attempting to make our algorithms scalable.

Most of the time spent experimenting with algorithms was consumed in an attempt to create scalable algorithms which did not sacrifice overall speed. This is especially true of the second, wavefront expansion algorithm. Because a visited structure is central to the algorithm, initially, much care was put into the implementation of this structure. While several experiments are described in the above paper, each of which had various success, we did find that the structure is not critical to overall scalability; interestingly we could demonstrate increasing speedups even if the lock array was reduced to the degenerate case, which is analogous to a global lock around cell reads and writes.

Finally, the way processors are used and initialized provides another interesting point for optimization of the wavefront expansion algorithm. First, our wavefront expansion algorithm terminates for each processor before the whole maze is visited. For this reason, one should consider schemes to use these idle processors to solve useful parts of the problem, although this is non-trivial. For example, restarting these processors would require adjusting the implicit adjacency structure formed as well as selecting points in the maze which tend to result in computation which is usable. In practice, it may in fact be more difficult to locate these points than it would be beneficial to begin a new search at these points. For this reason, the problem is considered difficult. It is worth noting that here a successful approach is based both on maze geometry and specific maze properties and would most certainly require the construction of some ideal heuristic which tend to pick good points. Given our result that fixed initialization points produced much worse results than randomly selecting start points, it is suggested that a better initialization scheme could further improve our results. Such a scheme could attempt to distribute points near areas of the maze which, for example, maximize some connectivity heuristic.  In  general, we do not want to distribute points uniformly, however, since much of the maze never needs to be explored.  In fact, somewhat counter-intuitively, we may actually want to distribute the initialization points such that we maximize how long each processor takes to intersect the region formed by another. In this case, we will tend to allocate work better across processors since the minimum time any processor spends exploring is maximized. Generally speaking, this is an open problem and is worthy of further investigation.

Works Cited

Cohen, D. and Dallas, M. (2010) “Implementation of Parallel Pathfinding in a Shared Memory Architecture.” Retrieved on 12 April 2011 from <http://www.cs.rpi.edu/~dallam/Parallel.pdf>.

Lee, C. Y. (1961) “An Algorithm for Path Connections and Its Application.” IRE Transactions on Electronic Computers EC-10 (2): 346–65.

Nohra, J. and Champandard, A.J. (2010) “The Secrets of Parallel Pathfinding on Modern Computer Hardware.” Retrieved  on 5 April 2011 from <http://software.intel.com/en-us/articles/the-secrets-of-parallel-pathfinding-on-modern-computer-hardware/>.

Sagar, V.K. and Haag, B. (1992) “Efficiency of Lee’s Routing Algorithm on a Transputer Network.” Proceedings of the 35th Midwest Symposium on Circuits and Systems. Aug (2): 1090-3.

Svensson, L. and Montiero, J. (2008) “Integrated circuit and system design: power and timing modeling, optimization and simulation.” 18th international workshop, PATMOS 2008, Lisbon, Portugal, September 10-12, 2008. p. 214-7.