guest@BipbopPC:~/writing$ less parallelizing-a-star-with-openmp.md

One OpenMP directive runs 1,000 independent A* solvers for a 2.64x speedup at 3 threads and 88% efficiency. Past that the gains flatten out, because the cores end up sitting around waiting on the memory bus.

A* Pathfinding with OpenMP. CSCI 551 - Final Project Report. Christopher Gemperle.

## 1. Program Description, Goals, and Objectives

This project reuses my old Graphical A* Pathfinding Demo Program that I wrote as a final project for CSCI 411. It computes the (hopefully) shortest path to a target destination for 1000 randomly selected source nodes. Because of its ease of use, I decided to use OpenMP for parallelizing this task. It works well enough, given that all solvers are working off of the same initial data with only the source node changing, and since the number of solvers does not change after compile time.

## 2. Value of the Solution and Applications

The A* algorithm is used in navigation, video games, ai programming (not neural networks, more like GOAP, navmeshes, etc), or just about anywhere else where a shortest path must be found in a mutable graph in real-time.

GOAP (Goal-Oriented Action Planning) is a solid enough example of A* being applied. It circumvents using massive, complicated state machines for controlling game AI by making only two states necessary for a GOAP agent, planning and execution. During planning, a list of goals (sate_hunger, warm_self, defend_self) is evaluated to find the one with the highest priority or usefulness for the agent. Goals are evaluated based on world state flags (float_hunger, float_body_temperature, bool_enemy_aggroed), which can be used as either gating preconditions, or as modifiers to their priority. If a character is hungry, the priority of sate_hunger should be high, but if a character is being attacked and has no weapon, the character should be more likely to choose a goal to run away rather than to fight back. The highest priority goal is selected and the agent tries to form a plan from a list of “actions.” These actions can be things like “gather wood,” “build fire,” “attack enemy,” “run from enemy,” “pick berries,” etc, and each action has an associated cost.

fig.01

This is where A* comes in, each action has a list of preconditions and a list of effects. Preconditions are world state keys that must be equal to, above, or below a certain value, and effects are world state keys that will be changed by an action. A plan is formed by using A* in reverse, from the goal to the current world state, by treating actions as graph nodes, using action cost as H (heuristic cost), and using the number of world state keys not satisfied as G (distance from the starting node), trying to minimize G to zero by traversing the lowest cost actions that satisfy the goal’s preconditions. The search runs until it hits an iteration limit, or until a valid path is found and no other possible traversals could result in a lower cost.

## 3. Numerical Methods Used

Hopefully it counts as one, but the main numerical method used in this program is a graph-search algorithm. Each grid cell in a graph uses G and H costs, the distance from the source node, and the heuristic cost (manhattan distance), respectively. The “implicit cost” of a node traversal is the sum of G and H. When a node is evaluated, all of its neighbors are added to an “open set”, from which the node with the lowest implicit cost will be evaluated next. This happens repeatedly until the lowest cost path is found.

## 4. Parallel Programming Method

I chose to use OpenMP for this assignment, mostly because it’s the easiest one to use, but also because it is well suited for this application. The tasks are relatively even in load at high volume, they are very computationally expensive (the overhead doesn’t matter), and because the problem is “embarrassingly parallel,” with no loop-carried dependencies.

#pragma omp parallel for
for (int s = 0; s < NUM_SOLVERS; s++) {
    while (!run(&solvers[s])) {}
}

I also ended up adding an OpenMP pragma to the loop that builds the AStarSolvers but that code chunk is massive so I won’t add it here.

## 5. Sequential Solution and Timing

Below is a demonstration of the build process:

fig.02

When starting the program, the user will see a 160x150 Grid. The user may then place a target with LMB:

fig.03

They are then prompted to draw/erase walls and then press spacebar when they are ready to execute the search.

fig.04

And finally:

fig.05

The program is timed by sampling the system time at three points in the program after the user hits spacebar. First, the time at which the user pressed spacebar is sampled, then the time after all 1000 A* solvers have been built, and finally after the paths have been built for all 1000 solvers.

Timed trials with no obstacles:

## 6. Parallel Speed-Up Analysis and Amdahl’s Law

The number of threads was set using omp_set_num_threads and a NUM_THREADS preprocessor definition. Grid size was increased to 160x1000 for timed trials.

fig.06

Given that the sequential time of every run was almost equal to zero, and the fact that the operations happening in the sequential portion are essentially no-ops and one variable assignment after the first run, I think it’s fair to say that the sequential portion is near zero.

fig.07

fig.08

## 7. Conclusions and Future Work

At first, I suspected that the drop in efficiency was some sort of threading issue, but all 12 of my available threads were being used. After thinking about it for a bit, it seems that the issue is almost certainly that the CPU cores are sitting and waiting on the data bus between the CPU and RAM, since every single solver has its own individual copy of the grid, rather than having one shared copy and building a graph in non-shared memory from copied nodes.

fig.09

The OpenMP parallelization appears to perform fairly well up to 3 cores, with a speedup of 2.64x and an efficiency of 88%, but beyond that performance drops significantly due to memory bus bottlenecking. To push this project toward hitting the actual Amdahl ideal speedup, it would be necessary to trim the fat off of the solvers by having them start with a black graph that is built from one global navigation grid. With an arbitrarily large navigation grid, chunking, bounding boxes, and grouping navigation agents could also be used to improve performance, but that’s way above my paygrade… in fact, they’re not paying me at all.